diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index dc75ff1..da2f9cb 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1295,8 +1295,13 @@
    */
   bool DynamicBCESeemsProfitable(HLoopInformation* loop, HBasicBlock* block) {
     if (loop != nullptr) {
+      // The loop preheader of an irreducible loop does not dominate all the blocks in
+      // the loop. We would need to find the common dominator of all blocks in the loop.
+      if (loop->IsIrreducible()) {
+        return false;
+      }
       // A try boundary preheader is hard to handle.
-      // TODO: remove this restriction
+      // TODO: remove this restriction.
       if (loop->GetPreHeader()->GetLastInstruction()->IsTryBoundary()) {
         return false;
       }
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index dbeb1cc..b7c24ff 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -42,7 +42,6 @@
 
   void RunBCE() {
     graph_->BuildDominatorTree();
-    graph_->AnalyzeNaturalLoops();
 
     InstructionSimplifier(graph_).Run();
 
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 58feb67..9a1f2b8 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -5980,8 +5980,16 @@
 HInvokeStaticOrDirect::DispatchInfo CodeGeneratorARM::GetSupportedInvokeStaticOrDirectDispatch(
       const HInvokeStaticOrDirect::DispatchInfo& desired_dispatch_info,
       MethodReference target_method) {
-  if (desired_dispatch_info.code_ptr_location ==
-      HInvokeStaticOrDirect::CodePtrLocation::kCallPCRelative) {
+  HInvokeStaticOrDirect::DispatchInfo dispatch_info = desired_dispatch_info;
+  // We disable pc-relative load when there is an irreducible loop, as the optimization
+  // is incompatible with it.
+  if (GetGraph()->HasIrreducibleLoops() &&
+      (dispatch_info.method_load_kind ==
+          HInvokeStaticOrDirect::MethodLoadKind::kDexCachePcRelative)) {
+    dispatch_info.method_load_kind = HInvokeStaticOrDirect::MethodLoadKind::kDexCacheViaMethod;
+  }
+
+  if (dispatch_info.code_ptr_location == HInvokeStaticOrDirect::CodePtrLocation::kCallPCRelative) {
     const DexFile& outer_dex_file = GetGraph()->GetDexFile();
     if (&outer_dex_file != target_method.dex_file) {
       // Calls across dex files are more likely to exceed the available BL range,
@@ -5992,14 +6000,14 @@
           ? HInvokeStaticOrDirect::CodePtrLocation::kCallDirectWithFixup
           : HInvokeStaticOrDirect::CodePtrLocation::kCallArtMethod;
       return HInvokeStaticOrDirect::DispatchInfo {
-        desired_dispatch_info.method_load_kind,
+        dispatch_info.method_load_kind,
         code_ptr_location,
-        desired_dispatch_info.method_load_data,
+        dispatch_info.method_load_data,
         0u
       };
     }
   }
-  return desired_dispatch_info;
+  return dispatch_info;
 }
 
 Register CodeGeneratorARM::GetInvokeStaticOrDirectExtraParameter(HInvokeStaticOrDirect* invoke,
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index a808c27..86327fb 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -4185,19 +4185,28 @@
 HInvokeStaticOrDirect::DispatchInfo CodeGeneratorX86::GetSupportedInvokeStaticOrDirectDispatch(
       const HInvokeStaticOrDirect::DispatchInfo& desired_dispatch_info,
       MethodReference target_method ATTRIBUTE_UNUSED) {
-  switch (desired_dispatch_info.code_ptr_location) {
+  HInvokeStaticOrDirect::DispatchInfo dispatch_info = desired_dispatch_info;
+
+  // We disable pc-relative load when there is an irreducible loop, as the optimization
+  // is incompatible with it.
+  if (GetGraph()->HasIrreducibleLoops() &&
+      (dispatch_info.method_load_kind ==
+          HInvokeStaticOrDirect::MethodLoadKind::kDexCachePcRelative)) {
+    dispatch_info.method_load_kind = HInvokeStaticOrDirect::MethodLoadKind::kDexCacheViaMethod;
+  }
+  switch (dispatch_info.code_ptr_location) {
     case HInvokeStaticOrDirect::CodePtrLocation::kCallDirectWithFixup:
     case HInvokeStaticOrDirect::CodePtrLocation::kCallDirect:
       // For direct code, we actually prefer to call via the code pointer from ArtMethod*.
       // (Though the direct CALL ptr16:32 is available for consideration).
       return HInvokeStaticOrDirect::DispatchInfo {
-        desired_dispatch_info.method_load_kind,
+        dispatch_info.method_load_kind,
         HInvokeStaticOrDirect::CodePtrLocation::kCallArtMethod,
-        desired_dispatch_info.method_load_data,
+        dispatch_info.method_load_data,
         0u
       };
     default:
-      return desired_dispatch_info;
+      return dispatch_info;
   }
 }
 
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 67ff87a..86a695b 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -81,12 +81,6 @@
   }
 }
 
-static void MarkLoopHeadersContaining(const HBasicBlock& block, ArenaBitVector* set) {
-  for (HLoopInformationOutwardIterator it(block); !it.Done(); it.Advance()) {
-    set->SetBit(it.Current()->GetHeader()->GetBlockId());
-  }
-}
-
 void HDeadCodeElimination::MaybeRecordDeadBlock(HBasicBlock* block) {
   if (stats_ != nullptr) {
     stats_->RecordStat(MethodCompilationStat::kRemovedDeadInstruction,
@@ -98,36 +92,45 @@
   // Classify blocks as reachable/unreachable.
   ArenaAllocator* allocator = graph_->GetArena();
   ArenaBitVector live_blocks(allocator, graph_->GetBlocks().size(), false);
-  ArenaBitVector affected_loops(allocator, graph_->GetBlocks().size(), false);
 
   MarkReachableBlocks(graph_, &live_blocks);
   bool removed_one_or_more_blocks = false;
+  // If the graph has irreducible loops we need to reset all graph analysis we have done
+  // before: the irreducible loop can be turned into a reducible one.
+  // For simplicity, we do the full computation regardless of the type of the loops.
+  bool rerun_dominance_and_loop_analysis = false;
 
   // Remove all dead blocks. Iterate in post order because removal needs the
   // block's chain of dominators and nested loops need to be updated from the
   // inside out.
   for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
     HBasicBlock* block  = it.Current();
+    if (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible()) {
+      rerun_dominance_and_loop_analysis = true;
+    }
     int id = block->GetBlockId();
-    if (live_blocks.IsBitSet(id)) {
-      if (affected_loops.IsBitSet(id)) {
-        DCHECK(block->IsLoopHeader());
-        block->GetLoopInformation()->Update();
-      }
-    } else {
+    if (!live_blocks.IsBitSet(id)) {
       MaybeRecordDeadBlock(block);
-      MarkLoopHeadersContaining(*block, &affected_loops);
       block->DisconnectAndDelete();
       removed_one_or_more_blocks = true;
+      if (block->IsInLoop()) {
+        rerun_dominance_and_loop_analysis = true;
+      }
     }
   }
 
   // If we removed at least one block, we need to recompute the full
   // dominator tree and try block membership.
   if (removed_one_or_more_blocks) {
-    graph_->ClearDominanceInformation();
-    graph_->ComputeDominanceInformation();
-    graph_->ComputeTryBlockInformation();
+    if (rerun_dominance_and_loop_analysis) {
+      graph_->ClearLoopInformation();
+      graph_->ClearDominanceInformation();
+      graph_->BuildDominatorTree();
+    } else {
+      graph_->ClearDominanceInformation();
+      graph_->ComputeDominanceInformation();
+      graph_->ComputeTryBlockInformation();
+    }
   }
 
   // Connect successive blocks created by dead branches. Order does not matter.
diff --git a/compiler/optimizing/dex_cache_array_fixups_arm.cc b/compiler/optimizing/dex_cache_array_fixups_arm.cc
index 6582063..3db254a 100644
--- a/compiler/optimizing/dex_cache_array_fixups_arm.cc
+++ b/compiler/optimizing/dex_cache_array_fixups_arm.cc
@@ -83,6 +83,11 @@
 };
 
 void DexCacheArrayFixups::Run() {
+  if (graph_->HasIrreducibleLoops()) {
+    // Do not run this optimization, as irreducible loops do not work with an instruction
+    // that can be live-in at the irreducible loop header.
+    return;
+  }
   DexCacheArrayFixupsVisitor visitor(graph_);
   visitor.VisitInsertionOrder();
   visitor.MoveBasesIfNeeded();
diff --git a/compiler/optimizing/find_loops_test.cc b/compiler/optimizing/find_loops_test.cc
index 9b0eb70..4770fa2 100644
--- a/compiler/optimizing/find_loops_test.cc
+++ b/compiler/optimizing/find_loops_test.cc
@@ -33,7 +33,6 @@
   const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
   builder.BuildGraph(*item);
   graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
   return graph;
 }
 
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 6d0bdbe..d60f3e3 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -391,6 +391,15 @@
     }
   }
 
+  // Ensure dominated blocks have `block` as the dominator.
+  for (HBasicBlock* dominated : block->GetDominatedBlocks()) {
+    if (dominated->GetDominator() != block) {
+      AddError(StringPrintf("Block %d should be the dominator of %d.",
+                            block->GetBlockId(),
+                            dominated->GetBlockId()));
+    }
+  }
+
   // Ensure there is no critical edge (i.e., an edge connecting a
   // block with multiple successors to a block with multiple
   // predecessors). Exceptional edges are synthesized and hence
@@ -467,13 +476,7 @@
   int id = loop_header->GetBlockId();
   HLoopInformation* loop_information = loop_header->GetLoopInformation();
 
-  // Ensure the pre-header block is first in the list of predecessors of a loop
-  // header and that the header block is its only successor.
-  if (!loop_header->IsLoopPreHeaderFirstPredecessor()) {
-    AddError(StringPrintf(
-        "Loop pre-header is not the first predecessor of the loop header %d.",
-        id));
-  } else if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) {
+  if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) {
     AddError(StringPrintf(
         "Loop pre-header %d of loop defined by header %d has %zu successors.",
         loop_information->GetPreHeader()->GetBlockId(),
@@ -532,20 +535,6 @@
     }
   }
 
-  // Ensure all blocks in the loop are live and dominated by the loop header.
-  for (uint32_t i : loop_blocks.Indexes()) {
-    HBasicBlock* loop_block = GetGraph()->GetBlocks()[i];
-    if (loop_block == nullptr) {
-      AddError(StringPrintf("Loop defined by header %d contains a previously removed block %d.",
-                            id,
-                            i));
-    } else if (!loop_header->Dominates(loop_block)) {
-      AddError(StringPrintf("Loop block %d not dominated by loop header %d.",
-                            i,
-                            id));
-    }
-  }
-
   // If this is a nested loop, ensure the outer loops contain a superset of the blocks.
   for (HLoopInformationOutwardIterator it(*loop_header); !it.Done(); it.Advance()) {
     HLoopInformation* outer_info = it.Current();
@@ -556,6 +545,29 @@
                             outer_info->GetHeader()->GetBlockId()));
     }
   }
+
+  // Ensure the pre-header block is first in the list of predecessors of a loop
+  // header and that the header block is its only successor.
+  if (!loop_header->IsLoopPreHeaderFirstPredecessor()) {
+    AddError(StringPrintf(
+        "Loop pre-header is not the first predecessor of the loop header %d.",
+        id));
+  }
+
+  // Ensure all blocks in the loop are live and dominated by the loop header in
+  // the case of natural loops.
+  for (uint32_t i : loop_blocks.Indexes()) {
+    HBasicBlock* loop_block = GetGraph()->GetBlocks()[i];
+    if (loop_block == nullptr) {
+      AddError(StringPrintf("Loop defined by header %d contains a previously removed block %d.",
+                            id,
+                            i));
+    } else if (!loop_information->IsIrreducible() && !loop_header->Dominates(loop_block)) {
+      AddError(StringPrintf("Loop block %d not dominated by loop header %d.",
+                            i,
+                            id));
+    }
+  }
 }
 
 void SSAChecker::VisitInstruction(HInstruction* instruction) {
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 5f1328f..32c3a92 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -486,7 +486,9 @@
         StartAttributeStream("is_low") << interval->IsLowInterval();
         StartAttributeStream("is_high") << interval->IsHighInterval();
       }
-    } else if (IsPass(RegisterAllocator::kRegisterAllocatorPassName) && is_after_pass_) {
+    }
+
+    if (IsPass(RegisterAllocator::kRegisterAllocatorPassName) && is_after_pass_) {
       StartAttributeStream("liveness") << instruction->GetLifetimePosition();
       LocationSummary* locations = instruction->GetLocations();
       if (locations != nullptr) {
@@ -498,15 +500,29 @@
         attr << inputs << "->";
         DumpLocation(attr, locations->Out());
       }
-    } else if (IsPass(LICM::kLoopInvariantCodeMotionPassName)
-               || IsPass(HDeadCodeElimination::kFinalDeadCodeEliminationPassName)) {
+    }
+
+    if (IsPass(LICM::kLoopInvariantCodeMotionPassName)
+        || IsPass(HDeadCodeElimination::kFinalDeadCodeEliminationPassName)
+        || IsPass(HDeadCodeElimination::kInitialDeadCodeEliminationPassName)
+        || IsPass(SsaBuilder::kSsaBuilderPassName)) {
       HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
       if (info == nullptr) {
         StartAttributeStream("loop") << "none";
       } else {
         StartAttributeStream("loop") << "B" << info->GetHeader()->GetBlockId();
+        HLoopInformation* outer = info->GetPreHeader()->GetLoopInformation();
+        if (outer != nullptr) {
+          StartAttributeStream("outer_loop") << "B" << outer->GetHeader()->GetBlockId();
+        } else {
+          StartAttributeStream("outer_loop") << "none";
+        }
+        StartAttributeStream("irreducible")
+            << std::boolalpha << info->IsIrreducible() << std::noboolalpha;
       }
-    } else if ((IsPass(SsaBuilder::kSsaBuilderPassName)
+    }
+
+    if ((IsPass(SsaBuilder::kSsaBuilderPassName)
         || IsPass(HInliner::kInlinerPassName))
         && (instruction->GetType() == Primitive::kPrimNot)) {
       ReferenceTypeInfo info = instruction->IsLoadClass()
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index 4af111b..b492278 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -125,6 +125,14 @@
     });
   }
 
+  void Clear() {
+    num_entries_ = 0;
+    for (size_t i = 0; i < num_buckets_; ++i) {
+      buckets_[i] = nullptr;
+    }
+    buckets_owned_.SetInitialBits(num_buckets_);
+  }
+
   // Updates this set by intersecting with instructions in a predecessor's set.
   void IntersectWith(ValueSet* predecessor) {
     if (IsEmpty()) {
@@ -191,14 +199,6 @@
     return clone_iterator;
   }
 
-  void Clear() {
-    num_entries_ = 0;
-    for (size_t i = 0; i < num_buckets_; ++i) {
-      buckets_[i] = nullptr;
-    }
-    buckets_owned_.SetInitialBits(num_buckets_);
-  }
-
   // Iterates over buckets with impure instructions (even indices) and deletes
   // the ones on which 'cond' returns true.
   template<typename Functor>
@@ -261,11 +261,14 @@
     }
   }
 
-  // Generates a hash code for an instruction. Pure instructions are put into
-  // odd buckets to speed up deletion.
+  // Generates a hash code for an instruction.
   size_t HashCode(HInstruction* instruction) const {
     size_t hash_code = instruction->ComputeHashCode();
-    if (instruction->GetSideEffects().HasDependencies()) {
+    // Pure instructions are put into odd buckets to speed up deletion. Note that in the
+    // case of irreducible loops, we don't put pure instructions in odd buckets, as we
+    // need to delete them when entering the loop.
+    if (instruction->GetSideEffects().HasDependencies() ||
+        instruction->GetBlock()->GetGraph()->HasIrreducibleLoops()) {
       return (hash_code << 1) | 0;
     } else {
       return (hash_code << 1) | 1;
@@ -360,8 +363,14 @@
     }
     if (!set->IsEmpty()) {
       if (block->IsLoopHeader()) {
-        DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader());
-        set->Kill(side_effects_.GetLoopEffects(block));
+        if (block->GetLoopInformation()->IsIrreducible()) {
+          // To satisfy our linear scan algorithm, no instruction should flow in an irreducible
+          // loop header.
+          set->Clear();
+        } else {
+          DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader());
+          set->Kill(side_effects_.GetLoopEffects(block));
+        }
       } else if (predecessors.size() > 1) {
         for (HBasicBlock* predecessor : predecessors) {
           set->IntersectWith(sets_[predecessor->GetBlockId()]);
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index eef6cef..37f2d79 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -76,7 +76,9 @@
   // range analysis on outer loop while visiting inner loops.
   for (HReversePostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
     HBasicBlock* graph_block = it_graph.Current();
-    if (graph_block->IsLoopHeader()) {
+    // Don't analyze irreducible loops.
+    // TODO(ajcbik): could/should we remove this restriction?
+    if (graph_block->IsLoopHeader() && !graph_block->GetLoopInformation()->IsIrreducible()) {
       VisitLoop(graph_block->GetLoopInformation());
     }
   }
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 48d3299..293282e 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -539,7 +539,7 @@
     return false;
   }
 
-  if (callee_graph->TryBuildingSsa(handles_) != kBuildSsaSuccess) {
+  if (callee_graph->TryBuildingSsa(handles_) != kAnalysisSuccess) {
     VLOG(compiler) << "Method " << PrettyMethod(method_index, callee_dex_file)
                    << " could not be transformed to SSA";
     return false;
diff --git a/compiler/optimizing/licm.cc b/compiler/optimizing/licm.cc
index 02befc0..a6b4078 100644
--- a/compiler/optimizing/licm.cc
+++ b/compiler/optimizing/licm.cc
@@ -94,6 +94,16 @@
     SideEffects loop_effects = side_effects_.GetLoopEffects(block);
     HBasicBlock* pre_header = loop_info->GetPreHeader();
 
+    bool contains_irreducible_loop = false;
+    if (graph_->HasIrreducibleLoops()) {
+      for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
+        if (it_loop.Current()->GetLoopInformation()->IsIrreducible()) {
+          contains_irreducible_loop = true;
+          break;
+        }
+      }
+    }
+
     for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
       HBasicBlock* inner = it_loop.Current();
       DCHECK(inner->IsInLoop());
@@ -104,6 +114,12 @@
       }
       visited.SetBit(inner->GetBlockId());
 
+      if (contains_irreducible_loop) {
+        // We cannot licm in an irreducible loop, or in a natural loop containing an
+        // irreducible loop.
+        continue;
+      }
+
       // We can move an instruction that can throw only if it is the first
       // throwing instruction in the loop. Note that the first potentially
       // throwing instruction encountered that is not hoisted stops this
diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc
index 2b313f6..c4492c8 100644
--- a/compiler/optimizing/load_store_elimination.cc
+++ b/compiler/optimizing/load_store_elimination.cc
@@ -582,9 +582,22 @@
     DCHECK(block->IsLoopHeader());
     int block_id = block->GetBlockId();
     ArenaVector<HInstruction*>& heap_values = heap_values_for_[block_id];
+
+    // Don't eliminate loads in irreducible loops. This is safe for singletons, because
+    // they are always used by the non-eliminated loop-phi.
+    if (block->GetLoopInformation()->IsIrreducible()) {
+      if (kIsDebugBuild) {
+        for (size_t i = 0; i < heap_values.size(); i++) {
+          DCHECK_EQ(heap_values[i], kUnknownHeapValue);
+        }
+      }
+      return;
+    }
+
     HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader();
     ArenaVector<HInstruction*>& pre_header_heap_values =
         heap_values_for_[pre_header->GetBlockId()];
+
     // Inherit the values from pre-header.
     for (size_t i = 0; i < heap_values.size(); i++) {
       heap_values[i] = pre_header_heap_values[i];
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index c85e573..f5a7048 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -13,7 +13,6 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-
 #include "nodes.h"
 
 #include "code_generator.h"
@@ -90,6 +89,7 @@
   for (size_t i = 0; i < blocks_.size(); ++i) {
     if (!visited.IsBitSet(i)) {
       HBasicBlock* block = blocks_[i];
+      if (block == nullptr) continue;
       DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage";
       for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
         RemoveAsUser(it.Current());
@@ -102,6 +102,7 @@
   for (size_t i = 0; i < blocks_.size(); ++i) {
     if (!visited.IsBitSet(i)) {
       HBasicBlock* block = blocks_[i];
+      if (block == nullptr) continue;
       // We only need to update the successor, which might be live.
       for (HBasicBlock* successor : block->GetSuccessors()) {
         successor->RemovePredecessor(block);
@@ -113,7 +114,7 @@
   }
 }
 
-void HGraph::BuildDominatorTree() {
+GraphAnalysisResult HGraph::BuildDominatorTree() {
   // (1) Simplify the CFG so that catch blocks have only exceptional incoming
   //     edges. This invariant simplifies building SSA form because Phis cannot
   //     collect both normal- and exceptional-flow values at the same time.
@@ -130,7 +131,7 @@
   RemoveInstructionsAsUsersFromDeadBlocks(visited);
 
   // (4) Remove blocks not visited during the initial DFS.
-  //     Step (4) requires dead blocks to be removed from the
+  //     Step (5) requires dead blocks to be removed from the
   //     predecessors list of live blocks.
   RemoveDeadBlocks(visited);
 
@@ -140,6 +141,20 @@
 
   // (6) Compute the dominance information and the reverse post order.
   ComputeDominanceInformation();
+
+  // (7) Analyze loops discover through back edge analysis, and
+  //     set the loop information on each block.
+  GraphAnalysisResult result = AnalyzeLoops();
+  if (result != kAnalysisSuccess) {
+    return result;
+  }
+
+  // (8) Precompute per-block try membership before entering the SSA builder,
+  //     which needs the information to build catch block phis from values of
+  //     locals at throwing instructions inside try blocks.
+  ComputeTryBlockInformation();
+
+  return kAnalysisSuccess;
 }
 
 void HGraph::ClearDominanceInformation() {
@@ -149,6 +164,17 @@
   reverse_post_order_.clear();
 }
 
+void HGraph::ClearLoopInformation() {
+  SetHasIrreducibleLoops(false);
+  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+    HBasicBlock* current = it.Current();
+    if (current->IsLoopHeader()) {
+      current->RemoveInstruction(current->GetLoopInformation()->GetSuspendCheck());
+    }
+    current->SetLoopInformation(nullptr);
+  }
+}
+
 void HBasicBlock::ClearDominanceInformation() {
   dominated_blocks_.clear();
   dominator_ = nullptr;
@@ -190,31 +216,28 @@
       // dominator of the block. We can then start visiting its successors.
       if (++visits[successor->GetBlockId()] ==
           successor->GetPredecessors().size() - successor->NumberOfBackEdges()) {
-        successor->GetDominator()->AddDominatedBlock(successor);
         reverse_post_order_.push_back(successor);
         worklist.push_back(successor);
       }
     }
   }
+
+  // Populate `dominated_blocks_` information after computing all dominators.
+  // The potential presence of irreducible loops require to do it after.
+  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+    if (!block->IsEntryBlock()) {
+      block->GetDominator()->AddDominatedBlock(block);
+    }
+  }
 }
 
-BuildSsaResult HGraph::TryBuildingSsa(StackHandleScopeCollection* handles) {
-  BuildDominatorTree();
-
-  // The SSA builder requires loops to all be natural. Specifically, the dead phi
-  // elimination phase checks the consistency of the graph when doing a post-order
-  // visit for eliminating dead phis: a dead phi can only have loop header phi
-  // users remaining when being visited.
-  BuildSsaResult result = AnalyzeNaturalLoops();
-  if (result != kBuildSsaSuccess) {
+GraphAnalysisResult HGraph::TryBuildingSsa(StackHandleScopeCollection* handles) {
+  GraphAnalysisResult result = BuildDominatorTree();
+  if (result != kAnalysisSuccess) {
     return result;
   }
 
-  // Precompute per-block try membership before entering the SSA builder,
-  // which needs the information to build catch block phis from values of
-  // locals at throwing instructions inside try blocks.
-  ComputeTryBlockInformation();
-
   // Create the inexact Object reference type and store it in the HGraph.
   ScopedObjectAccess soa(Thread::Current());
   ClassLinker* linker = Runtime::Current()->GetClassLinker();
@@ -224,12 +247,12 @@
 
   // Tranforms graph to SSA form.
   result = SsaBuilder(this, handles).BuildSsa();
-  if (result != kBuildSsaSuccess) {
+  if (result != kAnalysisSuccess) {
     return result;
   }
 
   in_ssa_form_ = true;
-  return kBuildSsaSuccess;
+  return kAnalysisSuccess;
 }
 
 HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) {
@@ -331,7 +354,7 @@
   // can be invalidated. We remember the initial size to avoid iterating over the new blocks.
   for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) {
     HBasicBlock* catch_block = blocks_[block_id];
-    if (!catch_block->IsCatchBlock()) {
+    if (catch_block == nullptr || !catch_block->IsCatchBlock()) {
       continue;
     }
 
@@ -438,7 +461,7 @@
   }
 }
 
-BuildSsaResult HGraph::AnalyzeNaturalLoops() const {
+GraphAnalysisResult HGraph::AnalyzeLoops() const {
   // Order does not matter.
   for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
@@ -446,16 +469,26 @@
       if (block->IsCatchBlock()) {
         // TODO: Dealing with exceptional back edges could be tricky because
         //       they only approximate the real control flow. Bail out for now.
-        return kBuildSsaFailThrowCatchLoop;
+        return kAnalysisFailThrowCatchLoop;
       }
-      HLoopInformation* info = block->GetLoopInformation();
-      if (!info->Populate()) {
-        // Abort if the loop is non natural. We currently bailout in such cases.
-        return kBuildSsaFailNonNaturalLoop;
-      }
+      block->GetLoopInformation()->Populate();
     }
   }
-  return kBuildSsaSuccess;
+  return kAnalysisSuccess;
+}
+
+void HLoopInformation::Dump(std::ostream& os) {
+  os << "header: " << header_->GetBlockId() << std::endl;
+  os << "pre header: " << GetPreHeader()->GetBlockId() << std::endl;
+  for (HBasicBlock* block : back_edges_) {
+    os << "back edge: " << block->GetBlockId() << std::endl;
+  }
+  for (HBasicBlock* block : header_->GetPredecessors()) {
+    os << "predecessor: " << block->GetBlockId() << std::endl;
+  }
+  for (uint32_t idx : blocks_.Indexes()) {
+    os << "  in loop: " << idx << std::endl;
+  }
 }
 
 void HGraph::InsertConstant(HConstant* constant) {
@@ -555,61 +588,65 @@
   }
 }
 
-bool HLoopInformation::Populate() {
+void HLoopInformation::PopulateIrreducibleRecursive(HBasicBlock* block) {
+  if (blocks_.IsBitSet(block->GetBlockId())) {
+    return;
+  }
+
+  if (block->IsLoopHeader()) {
+    // If we hit a loop header in an irreducible loop, we first check if the
+    // pre header of that loop belongs to the currently analyzed loop. If it does,
+    // then we visit the back edges.
+    // Note that we cannot use GetPreHeader, as the loop may have not been populated
+    // yet.
+    HBasicBlock* pre_header = block->GetPredecessors()[0];
+    PopulateIrreducibleRecursive(pre_header);
+    if (blocks_.IsBitSet(pre_header->GetBlockId())) {
+      blocks_.SetBit(block->GetBlockId());
+      block->SetInLoop(this);
+      HLoopInformation* info = block->GetLoopInformation();
+      for (HBasicBlock* back_edge : info->GetBackEdges()) {
+        PopulateIrreducibleRecursive(back_edge);
+      }
+    }
+  } else {
+    // Visit all predecessors. If one predecessor is part of the loop, this
+    // block is also part of this loop.
+    for (HBasicBlock* predecessor : block->GetPredecessors()) {
+      PopulateIrreducibleRecursive(predecessor);
+      if (blocks_.IsBitSet(predecessor->GetBlockId())) {
+        blocks_.SetBit(block->GetBlockId());
+        block->SetInLoop(this);
+      }
+    }
+  }
+}
+
+void HLoopInformation::Populate() {
   DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated";
+  // Populate this loop: starting with the back edge, recursively add predecessors
+  // that are not already part of that loop. Set the header as part of the loop
+  // to end the recursion.
+  // This is a recursive implementation of the algorithm described in
+  // "Advanced Compiler Design & Implementation" (Muchnick) p192.
+  blocks_.SetBit(header_->GetBlockId());
+  header_->SetInLoop(this);
   for (HBasicBlock* back_edge : GetBackEdges()) {
     DCHECK(back_edge->GetDominator() != nullptr);
     if (!header_->Dominates(back_edge)) {
-      // This loop is not natural. Do not bother going further.
-      return false;
+      irreducible_ = true;
+      header_->GetGraph()->SetHasIrreducibleLoops(true);
+      PopulateIrreducibleRecursive(back_edge);
+    } else {
+      PopulateRecursive(back_edge);
     }
-
-    // Populate this loop: starting with the back edge, recursively add predecessors
-    // that are not already part of that loop. Set the header as part of the loop
-    // to end the recursion.
-    // This is a recursive implementation of the algorithm described in
-    // "Advanced Compiler Design & Implementation" (Muchnick) p192.
-    blocks_.SetBit(header_->GetBlockId());
-    PopulateRecursive(back_edge);
-  }
-  return true;
-}
-
-void HLoopInformation::Update() {
-  HGraph* graph = header_->GetGraph();
-  for (uint32_t id : blocks_.Indexes()) {
-    HBasicBlock* block = graph->GetBlocks()[id];
-    // Reset loop information of non-header blocks inside the loop, except
-    // members of inner nested loops because those should already have been
-    // updated by their own LoopInformation.
-    if (block->GetLoopInformation() == this && block != header_) {
-      block->SetLoopInformation(nullptr);
-    }
-  }
-  blocks_.ClearAllBits();
-
-  if (back_edges_.empty()) {
-    // The loop has been dismantled, delete its suspend check and remove info
-    // from the header.
-    DCHECK(HasSuspendCheck());
-    header_->RemoveInstruction(suspend_check_);
-    header_->SetLoopInformation(nullptr);
-    header_ = nullptr;
-    suspend_check_ = nullptr;
-  } else {
-    if (kIsDebugBuild) {
-      for (HBasicBlock* back_edge : back_edges_) {
-        DCHECK(header_->Dominates(back_edge));
-      }
-    }
-    // This loop still has reachable back edges. Repopulate the list of blocks.
-    bool populate_successful = Populate();
-    DCHECK(populate_successful);
   }
 }
 
 HBasicBlock* HLoopInformation::GetPreHeader() const {
-  return header_->GetDominator();
+  HBasicBlock* block = header_->GetPredecessors()[0];
+  DCHECK(irreducible_ || (block == header_->GetDominator()));
+  return block;
 }
 
 bool HLoopInformation::Contains(const HBasicBlock& block) const {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 1a7cbde..59c0769 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -98,11 +98,10 @@
   kCondAE,  // >=
 };
 
-enum BuildSsaResult {
-  kBuildSsaFailNonNaturalLoop,
-  kBuildSsaFailThrowCatchLoop,
-  kBuildSsaFailAmbiguousArrayOp,
-  kBuildSsaSuccess,
+enum GraphAnalysisResult {
+  kAnalysisFailThrowCatchLoop,
+  kAnalysisFailAmbiguousArrayOp,
+  kAnalysisSuccess,
 };
 
 class HInstructionList : public ValueObject {
@@ -289,6 +288,7 @@
         temporaries_vreg_slots_(0),
         has_bounds_checks_(false),
         has_try_catch_(false),
+        has_irreducible_loops_(false),
         debuggable_(debuggable),
         current_instruction_id_(start_instruction_id),
         dex_file_(dex_file),
@@ -324,20 +324,20 @@
   // Try building the SSA form of this graph, with dominance computation and
   // loop recognition. Returns a code specifying that it was successful or the
   // reason for failure.
-  BuildSsaResult TryBuildingSsa(StackHandleScopeCollection* handles);
+  GraphAnalysisResult TryBuildingSsa(StackHandleScopeCollection* handles);
 
   void ComputeDominanceInformation();
   void ClearDominanceInformation();
-
-  void BuildDominatorTree();
+  void ClearLoopInformation();
+  void FindBackEdges(ArenaBitVector* visited);
+  GraphAnalysisResult BuildDominatorTree();
   void SimplifyCFG();
   void SimplifyCatchBlocks();
 
   // Analyze all natural loops in this graph. Returns a code specifying that it
   // was successful or the reason for failure. The method will fail if a loop
-  // is not natural, that is the header does not dominate a back edge, or if it
   // is a throw-catch loop, i.e. the header is a catch block.
-  BuildSsaResult AnalyzeNaturalLoops() const;
+  GraphAnalysisResult AnalyzeLoops() const;
 
   // Iterate over blocks to compute try block membership. Needs reverse post
   // order and loop information.
@@ -482,6 +482,9 @@
   bool HasTryCatch() const { return has_try_catch_; }
   void SetHasTryCatch(bool value) { has_try_catch_ = value; }
 
+  bool HasIrreducibleLoops() const { return has_irreducible_loops_; }
+  void SetHasIrreducibleLoops(bool value) { has_irreducible_loops_ = value; }
+
   ArtMethod* GetArtMethod() const { return art_method_; }
   void SetArtMethod(ArtMethod* method) { art_method_ = method; }
 
@@ -491,7 +494,6 @@
   HInstruction* InsertOppositeCondition(HInstruction* cond, HInstruction* cursor);
 
  private:
-  void FindBackEdges(ArenaBitVector* visited);
   void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const;
   void RemoveDeadBlocks(const ArenaBitVector& visited);
 
@@ -558,6 +560,9 @@
   // try/catch-related passes if false.
   bool has_try_catch_;
 
+  // Flag whether there are any irreducible loops in the graph.
+  bool has_irreducible_loops_;
+
   // Indicates whether the graph should be compiled in a way that
   // ensures full debuggability. If false, we can apply more
   // aggressive optimizations that may limit the level of debugging.
@@ -613,12 +618,17 @@
   HLoopInformation(HBasicBlock* header, HGraph* graph)
       : header_(header),
         suspend_check_(nullptr),
+        irreducible_(false),
         back_edges_(graph->GetArena()->Adapter(kArenaAllocLoopInfoBackEdges)),
         // Make bit vector growable, as the number of blocks may change.
         blocks_(graph->GetArena(), graph->GetBlocks().size(), true) {
     back_edges_.reserve(kDefaultNumberOfBackEdges);
   }
 
+  bool IsIrreducible() const { return irreducible_; }
+
+  void Dump(std::ostream& os);
+
   HBasicBlock* GetHeader() const {
     return header_;
   }
@@ -661,15 +671,8 @@
     ReplaceElement(back_edges_, existing, new_back_edge);
   }
 
-  // Finds blocks that are part of this loop. Returns whether the loop is a natural loop,
-  // that is the header dominates the back edge.
-  bool Populate();
-
-  // Reanalyzes the loop by removing loop info from its blocks and re-running
-  // Populate(). If there are no back edges left, the loop info is completely
-  // removed as well as its SuspendCheck instruction. It must be run on nested
-  // inner loops first.
-  void Update();
+  // Finds blocks that are part of this loop.
+  void Populate();
 
   // Returns whether this loop information contains `block`.
   // Note that this loop information *must* be populated before entering this function.
@@ -690,9 +693,11 @@
  private:
   // Internal recursive implementation of `Populate`.
   void PopulateRecursive(HBasicBlock* block);
+  void PopulateIrreducibleRecursive(HBasicBlock* block);
 
   HBasicBlock* header_;
   HSuspendCheck* suspend_check_;
+  bool irreducible_;
   ArenaVector<HBasicBlock*> back_edges_;
   ArenaBitVector blocks_;
 
@@ -1019,6 +1024,11 @@
     return GetPredecessors()[0] == GetLoopInformation()->GetPreHeader();
   }
 
+  bool IsFirstPredecessorBackEdge() const {
+    DCHECK(IsLoopHeader());
+    return GetLoopInformation()->IsBackEdge(*GetPredecessors()[0]);
+  }
+
   HLoopInformation* GetLoopInformation() const {
     return loop_information_;
   }
@@ -1831,7 +1841,10 @@
   void SetBlock(HBasicBlock* block) { block_ = block; }
   bool IsInBlock() const { return block_ != nullptr; }
   bool IsInLoop() const { return block_->IsInLoop(); }
-  bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); }
+  bool IsLoopHeaderPhi() const { return IsPhi() && block_->IsLoopHeader(); }
+  bool IsIrreducibleLoopHeaderPhi() const {
+    return IsLoopHeaderPhi() && GetBlock()->GetLoopInformation()->IsIrreducible();
+  }
 
   virtual size_t InputCount() const = 0;
   HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); }
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 3eb7274..cafc6c5 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -777,19 +777,16 @@
 
     {
       PassScope scope(SsaBuilder::kSsaBuilderPassName, &pass_observer);
-      BuildSsaResult result = graph->TryBuildingSsa(&handles);
-      if (result != kBuildSsaSuccess) {
+      GraphAnalysisResult result = graph->TryBuildingSsa(&handles);
+      if (result != kAnalysisSuccess) {
         switch (result) {
-          case kBuildSsaFailNonNaturalLoop:
-            MaybeRecordStat(MethodCompilationStat::kNotCompiledNonNaturalLoop);
-            break;
-          case kBuildSsaFailThrowCatchLoop:
+          case kAnalysisFailThrowCatchLoop:
             MaybeRecordStat(MethodCompilationStat::kNotCompiledThrowCatchLoop);
             break;
-          case kBuildSsaFailAmbiguousArrayOp:
+          case kAnalysisFailAmbiguousArrayOp:
             MaybeRecordStat(MethodCompilationStat::kNotCompiledAmbiguousArrayOp);
             break;
-          case kBuildSsaSuccess:
+          case kAnalysisSuccess:
             UNREACHABLE();
         }
         pass_observer.SetGraphInBadState();
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index bca1632..f8035aa 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -38,7 +38,6 @@
   kRemovedDeadInstruction,
   kRemovedNullCheck,
   kNotCompiledBranchOutsideMethodCode,
-  kNotCompiledNonNaturalLoop,
   kNotCompiledThrowCatchLoop,
   kNotCompiledAmbiguousArrayOp,
   kNotCompiledHugeMethod,
@@ -106,7 +105,6 @@
       case kRemovedDeadInstruction: name = "RemovedDeadInstruction"; break;
       case kRemovedNullCheck: name = "RemovedNullCheck"; break;
       case kNotCompiledBranchOutsideMethodCode: name = "NotCompiledBranchOutsideMethodCode"; break;
-      case kNotCompiledNonNaturalLoop : name = "NotCompiledNonNaturalLoop"; break;
       case kNotCompiledThrowCatchLoop : name = "NotCompiledThrowCatchLoop"; break;
       case kNotCompiledAmbiguousArrayOp : name = "NotCompiledAmbiguousArrayOp"; break;
       case kNotCompiledHugeMethod : name = "NotCompiledHugeMethod"; break;
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index af3a005..5a91043 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -117,7 +117,7 @@
 inline void TransformToSsa(HGraph* graph) {
   ScopedObjectAccess soa(Thread::Current());
   StackHandleScopeCollection handles(soa.Self());
-  EXPECT_EQ(graph->TryBuildingSsa(&handles), kBuildSsaSuccess);
+  EXPECT_EQ(graph->TryBuildingSsa(&handles), kAnalysisSuccess);
 }
 
 }  // namespace art
diff --git a/compiler/optimizing/pc_relative_fixups_x86.cc b/compiler/optimizing/pc_relative_fixups_x86.cc
index a385448..1394dfa 100644
--- a/compiler/optimizing/pc_relative_fixups_x86.cc
+++ b/compiler/optimizing/pc_relative_fixups_x86.cc
@@ -145,6 +145,11 @@
 };
 
 void PcRelativeFixups::Run() {
+  if (graph_->HasIrreducibleLoops()) {
+    // Do not run this optimization, as irreducible loops do not work with an instruction
+    // that can be live-in at the irreducible loop header.
+    return;
+  }
   PCRelativeHandlerVisitor visitor(graph_);
   visitor.VisitInsertionOrder();
   visitor.MoveBaseIfNeeded();
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index d399bc2..5ab4547 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -179,9 +179,11 @@
       ProcessInstruction(inst_it.Current());
     }
 
-    if (block->IsCatchBlock()) {
-      // By blocking all registers at the top of each catch block, we force
-      // intervals used after catch to spill.
+    if (block->IsCatchBlock() ||
+        (block->GetLoopInformation() != nullptr && block->GetLoopInformation()->IsIrreducible())) {
+      // By blocking all registers at the top of each catch block or irreducible loop, we force
+      // intervals belonging to the live-in set of the catch/header block to be spilled.
+      // TODO(ngeoffray): Phis in this block could be allocated in register.
       size_t position = block->GetLifetimeStart();
       BlockRegisters(position, position + 1);
     }
@@ -1864,8 +1866,10 @@
   // Resolve non-linear control flow across branches. Order does not matter.
   for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
-    if (block->IsCatchBlock()) {
-      // Instructions live at the top of catch blocks were forced to spill.
+    if (block->IsCatchBlock() ||
+        (block->GetLoopInformation() != nullptr && block->GetLoopInformation()->IsIrreducible())) {
+      // Instructions live at the top of catch blocks or irreducible loop header
+      // were forced to spill.
       if (kIsDebugBuild) {
         BitVector* live = liveness_.GetLiveInSet(*block);
         for (uint32_t idx : live->Indexes()) {
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 306a457..572faa8 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -535,7 +535,7 @@
   (*phi)->AddInput(*input2);
 
   graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
+  graph->AnalyzeLoops();
   return graph;
 }
 
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index f6bab8e..207e3f3 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -68,7 +68,7 @@
       // should be replaced with a null constant.
       // Both type propagation and redundant phi elimination ensure `int_operand`
       // can only be the 0 constant.
-      DCHECK(int_operand->IsIntConstant());
+      DCHECK(int_operand->IsIntConstant()) << int_operand->DebugName();
       DCHECK_EQ(0, int_operand->AsIntConstant()->GetValue());
       equality_instr->ReplaceInput(GetGraph()->GetNullConstant(), int_operand == right ? 1 : 0);
     }
@@ -422,7 +422,7 @@
   return true;
 }
 
-BuildSsaResult SsaBuilder::BuildSsa() {
+GraphAnalysisResult SsaBuilder::BuildSsa() {
   // 1) Visit in reverse post order. We need to have all predecessors of a block
   // visited (with the exception of loops) in order to create the right environment
   // for that block. For loops, we create phis whose inputs will be set in 2).
@@ -462,7 +462,7 @@
   // computed the type of the array input, the ambiguity can be resolved and the
   // correct equivalents kept.
   if (!FixAmbiguousArrayOps()) {
-    return kBuildSsaFailAmbiguousArrayOp;
+    return kAnalysisFailAmbiguousArrayOp;
   }
 
   // 8) Mark dead phis. This will mark phis which are not used by instructions
@@ -497,7 +497,7 @@
     }
   }
 
-  return kBuildSsaSuccess;
+  return kAnalysisSuccess;
 }
 
 ArenaVector<HInstruction*>* SsaBuilder::GetLocalsFor(HBasicBlock* block) {
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 0fcc3a1..743dabd 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -49,7 +49,7 @@
  */
 class SsaBuilder : public HGraphVisitor {
  public:
-  explicit SsaBuilder(HGraph* graph, StackHandleScopeCollection* handles)
+  SsaBuilder(HGraph* graph, StackHandleScopeCollection* handles)
       : HGraphVisitor(graph),
         handles_(handles),
         agets_fixed_(false),
@@ -63,7 +63,7 @@
     loop_headers_.reserve(kDefaultNumberOfLoops);
   }
 
-  BuildSsaResult BuildSsa();
+  GraphAnalysisResult BuildSsa();
 
   // Returns locals vector for `block`. If it is a catch block, the vector will be
   // prepopulated with catch phis for vregs which are defined in `current_locals_`.
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index b9d8731..a5609fc 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -273,6 +273,18 @@
     }
 
     if (block->IsLoopHeader()) {
+      if (kIsDebugBuild && block->GetLoopInformation()->IsIrreducible()) {
+        // To satisfy our liveness algorithm, we need to ensure loop headers of
+        // irreducible loops do not have any live-in instructions, except constants
+        // and the current method, which can be trivially re-materialized.
+        for (uint32_t idx : live_in->Indexes()) {
+          HInstruction* instruction = GetInstructionFromSsaIndex(idx);
+          DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
+          DCHECK(!instruction->IsParameterValue()) << instruction->DebugName();
+          DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
+              << instruction->DebugName();
+        }
+      }
       size_t last_position = block->GetLoopInformation()->GetLifetimeEnd();
       // For all live_in instructions at the loop header, we need to create a range
       // that covers the full loop.
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 2eef307..6816b6a 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -154,6 +154,7 @@
     cycle_worklist.push_back(phi);
     visited_phis_in_cycle.insert(phi->GetId());
     bool catch_phi_in_cycle = phi->IsCatchPhi();
+    bool irreducible_loop_phi_in_cycle = phi->IsIrreducibleLoopHeaderPhi();
 
     // First do a simple loop over inputs and check if they are all the same.
     for (size_t j = 0; j < phi->InputCount(); ++j) {
@@ -187,6 +188,7 @@
               cycle_worklist.push_back(input->AsPhi());
               visited_phis_in_cycle.insert(input->GetId());
               catch_phi_in_cycle |= input->AsPhi()->IsCatchPhi();
+              irreducible_loop_phi_in_cycle |= input->IsIrreducibleLoopHeaderPhi();
             } else {
               // Already visited, nothing to do.
             }
@@ -206,6 +208,15 @@
       continue;
     }
 
+    if (irreducible_loop_phi_in_cycle && !candidate->IsConstant()) {
+      // For irreducible loops, we need to keep the phis to satisfy our linear scan
+      // algorithm.
+      // There is one exception for constants, as the type propagation requires redundant
+      // cyclic phis of a constant to be removed. This is ok for the linear scan as it
+      // has to deal with constants anyway, and they can trivially be rematerialized.
+      continue;
+    }
+
     for (HPhi* current : cycle_worklist) {
       // The candidate may not dominate a phi in a catch block: there may be non-throwing
       // instructions at the beginning of a try range, that may be the first input of
diff --git a/test/559-checker-irreducible-loop/expected.txt b/test/559-checker-irreducible-loop/expected.txt
new file mode 100644
index 0000000..b64be7a
--- /dev/null
+++ b/test/559-checker-irreducible-loop/expected.txt
@@ -0,0 +1,7 @@
+84
+30
+168
+126
+class Main
+42
+-42
diff --git a/test/559-checker-irreducible-loop/info.txt b/test/559-checker-irreducible-loop/info.txt
new file mode 100644
index 0000000..e0ace18
--- /dev/null
+++ b/test/559-checker-irreducible-loop/info.txt
@@ -0,0 +1 @@
+Tests for irreducible loop support in compiler.
diff --git a/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali b/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali
new file mode 100644
index 0000000..30a648d
--- /dev/null
+++ b/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali
@@ -0,0 +1,561 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+.class public LIrreducibleLoop;
+
+.super Ljava/lang/Object;
+
+# Back-edges in the ascii-art graphs are represented with dash '-'.
+
+# Test that we support a simple irreducible loop.
+#
+#        entry
+#       /    \
+#      /      \
+# loop_entry   \
+#    /    \-    \
+#  exit    \-    \
+#           other_loop_entry
+#
+## CHECK-START: int IrreducibleLoop.simpleLoop(int) dead_code_elimination (before)
+## CHECK: irreducible:true
+.method public static simpleLoop(I)I
+   .registers 2
+   const/16 v0, 42
+   if-eq v1, v0, :other_loop_entry
+   :loop_entry
+   if-ne v1, v0, :exit
+   add-int v0, v0, v0
+   :other_loop_entry
+   add-int v0, v0, v0
+   goto :loop_entry
+   :exit
+   return v0
+.end method
+
+# Test that lse does not wrongly optimize loads in irreducible loops. At the
+# SSA level, since we create redundant phis for irreducible loop headers, lse
+# does not see the relation between the dex register and the phi.
+#
+#               entry
+#                p1
+#             /     \
+#            /       \
+#           /         \
+#          /           \
+#   loop_pre_entry      \
+# set 42 in p1:myField   \
+#        /                \
+#   loop_entry             \
+#  get p1.myField           \
+#    /         \-            \
+#  exit         \-            \
+#                \-            \
+#                other_loop_entry
+#              set 30 in p1:myField
+#
+## CHECK-START: int IrreducibleLoop.lse(int, Main) dead_code_elimination (after)
+## CHECK: irreducible:true
+#
+## CHECK-START: int IrreducibleLoop.lse(int, Main) load_store_elimination (after)
+## CHECK: InstanceFieldGet
+.method public static lse(ILMain;)I
+   .registers 4
+   const/16 v0, 42
+   const/16 v1, 30
+   if-eq p0, v0, :other_loop_pre_entry
+   goto: loop_pre_entry
+   :loop_pre_entry
+   iput v0, p1, LMain;->myField:I
+   :loop_entry
+   if-ne v1, v0, :exit
+   :other_loop_entry
+   iget v0, p1, LMain;->myField:I
+   if-eq v1, v0, :exit
+   goto :loop_entry
+   :exit
+   return v0
+   :other_loop_pre_entry
+   iput v1, p1, LMain;->myField:I
+   goto :other_loop_entry
+.end method
+
+# Check that if a irreducible loop entry is dead, the loop can become
+# natural.
+# We start with:
+#
+#        entry
+#       /    \
+#      /      \
+# loop_entry   \
+#    /    \-    \
+#  exit    \-    \
+#           other_loop_entry
+#
+## CHECK-START: int IrreducibleLoop.dce(int) dead_code_elimination (before)
+## CHECK: irreducible:true
+
+# And end with:
+#
+#        entry
+#       /
+#      /
+# loop_entry
+#    /    \-
+#  exit    \-
+#           other_loop_entry
+
+## CHECK-START: int IrreducibleLoop.dce(int) dead_code_elimination (after)
+## CHECK-NOT: irreducible:true
+.method public static dce(I)I
+   .registers 3
+   const/16 v0, 42
+   const/16 v1, 168
+   if-ne v0, v0, :other_loop_pre_entry
+   :loop_entry
+   if-ne v0, v0, :exit
+   add-int v0, v0, v0
+   :other_loop_entry
+   add-int v0, v0, v0
+   if-eq v0, v1, :exit
+   goto :loop_entry
+   :exit
+   return v0
+   :other_loop_pre_entry
+   add-int v0, v0, v0
+   goto :other_loop_entry
+.end method
+
+# Check that a dex register only used in the loop header remains live thanks
+# to the (redundant) Phi created at the loop header for it.
+#
+#           entry
+#            p0
+#          /   \
+#         /     \
+#        /       \
+#   loop_entry    \
+# i0 = phi(p0,i1)  \
+#    /    \-        \
+#  exit    \-        \
+#        other_loop_entry
+#        i1 = phi(p0, i0)
+#
+## CHECK-START: int IrreducibleLoop.liveness(int) liveness (after)
+## CHECK-DAG: <<Arg:i\d+>>      ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopPhiUse:\d+>>)}
+## CHECK-DAG: <<LoopPhi:i\d+>>  Phi [<<Arg>>,<<PhiInLoop:i\d+>>] liveness:<<ArgLoopPhiUse>> ranges:{[<<ArgLoopPhiUse>>,<<PhiInLoopUse:\d+>>)}
+## CHECK-DAG: <<PhiInLoop>>     Phi [<<Arg>>,<<LoopPhi>>] liveness:<<PhiInLoopUse>> ranges:{[<<PhiInLoopUse>>,<<BackEdgeLifetimeEnd:\d+>>)}
+## CHECK:                       Return liveness:<<ReturnLiveness:\d+>>
+## CHECK-EVAL:    <<ReturnLiveness>> == <<BackEdgeLifetimeEnd>> + 2
+.method public static liveness(I)I
+   .registers 2
+   const/16 v0, 42
+   if-eq p0, v0, :other_loop_entry
+   :loop_entry
+   add-int v0, v0, p0
+   if-ne v1, v0, :exit
+   :other_loop_entry
+   add-int v0, v0, v0
+   goto :loop_entry
+   :exit
+   return v0
+.end method
+
+# Check that we don't GVN across irreducible loops:
+# "const-class 1" in loop_entry should not be GVN with
+# "const-class 1" in entry.
+#
+#        entry
+#     const-class 1
+#       /    \
+#      /      \
+# loop_entry   \
+# const-class 1 \
+#    /    \-     \
+#  exit    \-     \
+#           other_loop_entry
+#             const-class 2
+#
+## CHECK-START: java.lang.Class IrreducibleLoop.gvn() GVN (before)
+## CHECK: LoadClass
+## CHECK: LoadClass
+## CHECK: LoadClass
+## CHECK-NOT: LoadClass
+
+## CHECK-START: java.lang.Class IrreducibleLoop.gvn() GVN (after)
+## CHECK: LoadClass
+## CHECK: LoadClass
+## CHECK: LoadClass
+## CHECK-NOT: LoadClass
+
+.method public static gvn()Ljava/lang/Class;
+  .registers 3
+  const/4 v2, 0
+  const-class v0, LMain;
+  if-ne v0, v2, :other_loop_entry
+  :loop_entry
+  const-class v0, LMain;
+  if-ne v0, v2, :exit
+  :other_loop_entry
+  const-class v1, LIrreducibleLoop;
+  goto :loop_entry
+  :exit
+  return-object v0
+.end method
+
+# Check that we don't LICM across irreducible loops:
+# "add" in loop_entry should not be LICMed.
+#
+#        entry
+#        /   \
+#       /     \
+#  loop_entry  \
+#      add      \
+#    /    \-     \
+#  exit    \-     \
+#           other_loop_entry
+#
+## CHECK-START: int IrreducibleLoop.licm1(int) licm (after)
+## CHECK: Add irreducible:true
+.method public static licm1(I)I
+  .registers 3
+  const/4 v0, 0
+  if-ne p0, v0, :other_loop_entry
+  :loop_entry
+  add-int v0, p0, p0
+  if-ne v0, p0, :exit
+  :other_loop_entry
+  sub-int v1, p0, p0
+  goto :loop_entry
+  :exit
+  sub-int v0, v0, p0
+  return v0
+.end method
+
+# Check that we don't LICM across irreducible loops:
+# "const-class" in loop_entry should not be LICMed.
+#
+#        entry
+#        /   \
+#       /     \
+#  loop_entry  \
+#  const-class  \
+#    /    \-     \
+#  exit    \-     \
+#           other_loop_entry
+#
+## CHECK-START: int IrreducibleLoop.licm2(int) licm (after)
+## CHECK: LoadClass irreducible:true
+.method public static licm2(I)I
+  .registers 3
+  const/4 v0, 0
+  if-ne p0, v0, :other_loop_entry
+  :loop_entry
+  const-class v1, LIrreducibleLoop;
+  if-ne v0, p0, :exit
+  :other_loop_entry
+  sub-int v1, p0, p0
+  goto :loop_entry
+  :exit
+  sub-int v0, v0, p0
+  return v0
+.end method
+
+# Check that we don't LICM in a natural loop that contains an irreducible loop:
+# "const-class" should not be LICMed.
+#
+#        entry
+#          |
+#       loop_entry
+#       const-class -------------------
+#        /        \                   -
+#       /          \                  -
+#     exit         loop_body          -
+#                  /       \          -
+#                 /         \         -
+#   irreducible_loop_entry   \        -
+#        -      \             \       -
+#        -       \             \      -
+#        -      irreducible_loop_other_entry
+#        -                  |
+#        -                  |
+#        ------ irreducible_loop_back_edge
+#
+## CHECK-START: int IrreducibleLoop.licm3(int, int, int) licm (after)
+## CHECK: LoadClass loop:<<OuterLoop:B\d+>>  irreducible:false
+## CHECK: Goto outer_loop:<<OuterLoop>>  irreducible:true
+.method public static licm3(III)I
+  .registers 4
+  :loop_entry
+  const-class v0, LIrreducibleLoop;
+  if-ne p1, p2, :exit
+  goto :loop_body
+
+  :loop_body
+  if-eq p0, p1, :irreducible_loop_entry
+  goto :irreducible_loop_other_entry
+
+  :irreducible_loop_entry
+  goto :irreducible_loop_other_entry
+
+  :irreducible_loop_other_entry
+  if-eq p0, p2, :loop_entry
+  goto :irreducible_loop_back_edge
+
+  :irreducible_loop_back_edge
+  goto :irreducible_loop_entry
+  :exit
+  return p0
+.end method
+
+# Check a loop within an irreducible loop
+#
+#                      entry
+#                    /       \
+#                   /         \
+# irreducible_loop_entry       \
+#    / -       \         irreducible_loop_pre_other_entry
+# exit -        \              /
+#      -    irreducible_loop_body
+#      -              |
+#      -              |
+#      -      loop_within_header
+#      -        /               \-
+#      -       /                 \-
+# irreducible_loop_back_edge    loop_within_back_edge
+#
+## CHECK-START: void IrreducibleLoop.analyze1(int) ssa_builder (after)
+## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true
+## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:false
+.method public static analyze1(I)V
+  .registers 1
+  if-eq p0, p0, :irreducible_loop_entry
+  goto :irreducible_loop_pre_other_entry
+
+  :irreducible_loop_entry
+  if-eq p0, p0, :exit
+  goto :irreducible_loop_body
+
+  :irreducible_loop_body
+  :loop_within_header
+  if-eq p0, p0, :irreducible_loop_back_edge
+  goto :loop_within_back_edge
+
+  :loop_within_back_edge
+  goto :loop_within_header
+
+  :irreducible_loop_back_edge
+  goto :irreducible_loop_entry
+
+  :irreducible_loop_pre_other_entry
+  goto :irreducible_loop_body
+
+  :exit
+  return-void
+.end method
+
+# Check than a loop before an irreducible loop is not part of the
+# irreducible loop.
+#
+#                      entry
+#                        |
+#                        |
+#                   loop_header
+#                    /        \-
+#                   /          \-
+# irreducible_loop_pre_entry  loop_body
+#           /             \
+#          /               \
+#  irreducible_loop_entry   \
+#    /        \-       irreducible_loop_other_pre_entry
+#   /          \-           /
+# exit          \-         /
+#          irreducible_loop_body
+#
+## CHECK-START: void IrreducibleLoop.analyze2(int) ssa_builder (after)
+## CHECK-DAG: Goto outer_loop:none irreducible:false
+## CHECK-DAG: Goto outer_loop:none irreducible:true
+.method public static analyze2(I)V
+  .registers 1
+  :loop_header
+  if-eq p0, p0, :irreducible_loop_pre_entry
+  goto :loop_body
+  :loop_body
+  goto :loop_header
+
+  :irreducible_loop_pre_entry
+  if-eq p0, p0, :irreducible_loop_other_pre_entry
+  goto :irreducible_loop_entry
+
+  :irreducible_loop_entry
+  if-eq p0, p0, :exit
+  goto :irreducible_loop_body
+
+  :irreducible_loop_body
+  goto :irreducible_loop_entry
+
+  :irreducible_loop_other_pre_entry
+  goto :irreducible_loop_body
+
+  :exit
+  return-void
+.end method
+
+# Check two irreducible loops, one within another.
+#
+#                      entry
+#                    /       \
+#                   /         \
+#           loop1_header   loop2_header
+#           -   |          /       -
+#           -   |         /        -
+#           -   |        /         -
+#           -   |       /          -
+#           -  loop2_body          -
+#           -    /     \           -
+#           -   /       \          -
+#         loop1_body   loop2_back_edge
+#             |
+#             |
+#           exit
+#
+## CHECK-START: void IrreducibleLoop.analyze3(int) ssa_builder (after)
+## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true
+## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:true
+.method public static analyze3(I)V
+  .registers 1
+  if-eq p0, p0, :loop2_header
+  goto :loop1_header
+
+  :loop1_header
+  goto :loop2_body
+
+  :loop2_header
+  goto :loop2_body
+
+  :loop2_body
+  if-eq p0, p0, :loop2_back_edge
+  goto :loop1_body
+
+  :loop2_back_edge
+  goto :loop2_header
+
+  :loop1_body
+  if-eq p0, p0, :exit
+  goto :loop1_header
+
+  :exit
+  return-void
+.end method
+
+# Check two irreducible loops, one within another. Almost identical
+# to analyze3 except the branches of the first 'if' are swapped, to
+# ensure the order at which we find the back edges does not matter.
+#
+#                      entry
+#                    /       \
+#                   /         \
+#           loop1_header   loop2_header
+#           -   |          /       -
+#           -   |         /        -
+#           -   |        /         -
+#           -   |       /          -
+#           -  loop2_body          -
+#           -    /     \           -
+#           -   /       \          -
+#         loop1_body   loop2_back_edge
+#             |
+#             |
+#           exit
+#
+## CHECK-START: void IrreducibleLoop.analyze4(int) ssa_builder (after)
+## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true
+## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:true
+.method public static analyze4(I)V
+  .registers 1
+  if-eq p0, p0, :loop1_header
+  goto :loop2_header
+
+  :loop1_header
+  goto :loop2_body
+
+  :loop2_header
+  goto :loop2_body
+
+  :loop2_body
+  if-eq p0, p0, :loop2_back_edge
+  goto :loop1_body
+
+  :loop2_back_edge
+  goto :loop2_header
+
+  :loop1_body
+  if-eq p0, p0, :exit
+  goto :loop1_header
+
+  :exit
+  return-void
+.end method
+
+# Check two irreducible loops, one within another. Almost identical
+# to analyze3 and analyze4, except that the inner loop exits from the
+# back edge, and not the body.
+#
+#                      entry
+#                    /       \
+#                   /         \
+#           loop1_header   loop2_header
+#           -   \            /       -
+#           -    \          /        -
+#           -     \        /         -
+#           -      \      /          -
+#           -     loop2_body         -
+#           -        |               -
+#           -        |               -
+#           -   loop2_back_edge ------
+#           -        |
+#           -        |
+#           ----- loop1_body
+#                    |
+#                    |
+#                   exit
+#
+## CHECK-START: void IrreducibleLoop.analyze5(int) ssa_builder (after)
+## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true
+## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:true
+.method public static analyze5(I)V
+  .registers 1
+  if-eq p0, p0, :loop1_header
+  goto :loop2_header
+
+  :loop1_header
+  goto :loop2_body
+
+  :loop2_header
+  goto :loop2_body
+
+  :loop2_body
+  goto :loop2_back_edge
+
+  :loop2_back_edge
+  if-eq p0, p0, :loop2_header
+  goto :loop1_body
+
+  :loop1_body
+  if-eq p0, p0, :exit
+  goto :loop1_header
+
+  :exit
+  return-void
+.end method
diff --git a/test/559-checker-irreducible-loop/src/Main.java b/test/559-checker-irreducible-loop/src/Main.java
new file mode 100644
index 0000000..ab84f81
--- /dev/null
+++ b/test/559-checker-irreducible-loop/src/Main.java
@@ -0,0 +1,69 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.lang.reflect.Method;
+
+public class Main {
+  // Workaround for b/18051191.
+  class InnerClass {}
+
+  public static void main(String[] args) throws Exception {
+    Class<?> c = Class.forName("IrreducibleLoop");
+    {
+      Method m = c.getMethod("simpleLoop", int.class);
+      Object[] arguments = { 42 };
+      System.out.println(m.invoke(null, arguments));
+    }
+
+    {
+      Method m = c.getMethod("lse", int.class, Main.class);
+      Object[] arguments = { 42, new Main() };
+      System.out.println(m.invoke(null, arguments));
+    }
+
+    {
+      Method m = c.getMethod("dce", int.class);
+      Object[] arguments = { 42 };
+      System.out.println(m.invoke(null, arguments));
+    }
+
+    {
+      Method m = c.getMethod("liveness", int.class);
+      Object[] arguments = { 42 };
+      System.out.println(m.invoke(null, arguments));
+    }
+
+    {
+      Method m = c.getMethod("gvn");
+      Object[] arguments = { };
+      System.out.println(m.invoke(null, arguments));
+    }
+
+    {
+      Method m = c.getMethod("licm1", int.class);
+      Object[] arguments = { 42 };
+      System.out.println(m.invoke(null, arguments));
+    }
+
+    {
+      Method m = c.getMethod("licm2", int.class);
+      Object[] arguments = { 42 };
+      System.out.println(m.invoke(null, arguments));
+    }
+  }
+
+  int myField;
+}