Merge "ART: Implement support for instruction inlining"

18 files changed, 175 insertions, 87 deletions

diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 5f00f0a536..2b81dba0f9 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -1632,7 +1632,7 @@ void LocationsBuilderARM::HandleCondition(HCondition* cond) {
     case Primitive::kPrimLong:
       locations->SetInAt(0, Location::RequiresRegister());
       locations->SetInAt(1, Location::RegisterOrConstant(cond->InputAt(1)));
-      if (cond->NeedsMaterialization()) {
+      if (!cond->IsEmittedAtUseSite()) {
         locations->SetOut(Location::RequiresRegister(), Location::kOutputOverlap);
       }
       break;
@@ -1641,7 +1641,7 @@ void LocationsBuilderARM::HandleCondition(HCondition* cond) {
     case Primitive::kPrimDouble:
       locations->SetInAt(0, Location::RequiresFpuRegister());
       locations->SetInAt(1, Location::RequiresFpuRegister());
-      if (cond->NeedsMaterialization()) {
+      if (!cond->IsEmittedAtUseSite()) {
         locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
       }
       break;
@@ -1649,14 +1649,14 @@ void LocationsBuilderARM::HandleCondition(HCondition* cond) {
     default:
       locations->SetInAt(0, Location::RequiresRegister());
       locations->SetInAt(1, Location::RegisterOrConstant(cond->InputAt(1)));
-      if (cond->NeedsMaterialization()) {
+      if (!cond->IsEmittedAtUseSite()) {
         locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
       }
   }
 }
 
 void InstructionCodeGeneratorARM::HandleCondition(HCondition* cond) {
-  if (!cond->NeedsMaterialization()) {
+  if (cond->IsEmittedAtUseSite()) {
     return;
   }
 
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index c0e3959933..788c3a62d5 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -2510,13 +2510,13 @@ void LocationsBuilderARM64::HandleCondition(HCondition* instruction) {
     locations->SetInAt(1, ARM64EncodableConstantOrRegister(instruction->InputAt(1), instruction));
   }
 
-  if (instruction->NeedsMaterialization()) {
+  if (!instruction->IsEmittedAtUseSite()) {
     locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
   }
 }
 
 void InstructionCodeGeneratorARM64::HandleCondition(HCondition* instruction) {
-  if (!instruction->NeedsMaterialization()) {
+  if (instruction->IsEmittedAtUseSite()) {
     return;
   }
 
diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc
index 5bd136a3f0..fec5811082 100644
--- a/compiler/optimizing/code_generator_mips.cc
+++ b/compiler/optimizing/code_generator_mips.cc
@@ -2245,13 +2245,13 @@ void LocationsBuilderMIPS::HandleCondition(HCondition* instruction) {
       locations->SetInAt(1, Location::RequiresFpuRegister());
       break;
   }
-  if (instruction->NeedsMaterialization()) {
+  if (!instruction->IsEmittedAtUseSite()) {
     locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
   }
 }
 
 void InstructionCodeGeneratorMIPS::HandleCondition(HCondition* instruction) {
-  if (!instruction->NeedsMaterialization()) {
+  if (instruction->IsEmittedAtUseSite()) {
     return;
   }
 
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index e3115f416a..e5a5fd4096 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -1872,13 +1872,13 @@ void LocationsBuilderMIPS64::HandleCondition(HCondition* instruction) {
       locations->SetInAt(1, Location::RequiresFpuRegister());
       break;
   }
-  if (instruction->NeedsMaterialization()) {
+  if (!instruction->IsEmittedAtUseSite()) {
     locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
   }
 }
 
 void InstructionCodeGeneratorMIPS64::HandleCondition(HCondition* instruction) {
-  if (!instruction->NeedsMaterialization()) {
+  if (instruction->IsEmittedAtUseSite()) {
     return;
   }
 
diff --git a/compiler/optimizing/code_generator_utils.cc b/compiler/optimizing/code_generator_utils.cc
index 644a3fb75e..96fe2a17e6 100644
--- a/compiler/optimizing/code_generator_utils.cc
+++ b/compiler/optimizing/code_generator_utils.cc
@@ -96,7 +96,7 @@ void CalculateMagicAndShiftForDivRem(int64_t divisor, bool is_long,
 }
 
 bool IsBooleanValueOrMaterializedCondition(HInstruction* cond_input) {
-  return !cond_input->IsCondition() || cond_input->AsCondition()->NeedsMaterialization();
+  return !cond_input->IsCondition() || !cond_input->IsEmittedAtUseSite();
 }
 
 }  // namespace art
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 50c4ba23c5..a4a8c7c103 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -1628,7 +1628,7 @@ void LocationsBuilderX86::HandleCondition(HCondition* cond) {
     case Primitive::kPrimLong: {
       locations->SetInAt(0, Location::RequiresRegister());
       locations->SetInAt(1, Location::RegisterOrConstant(cond->InputAt(1)));
-      if (cond->NeedsMaterialization()) {
+      if (!cond->IsEmittedAtUseSite()) {
         locations->SetOut(Location::RequiresRegister());
       }
       break;
@@ -1637,7 +1637,7 @@ void LocationsBuilderX86::HandleCondition(HCondition* cond) {
     case Primitive::kPrimDouble: {
       locations->SetInAt(0, Location::RequiresFpuRegister());
       locations->SetInAt(1, Location::RequiresFpuRegister());
-      if (cond->NeedsMaterialization()) {
+      if (!cond->IsEmittedAtUseSite()) {
         locations->SetOut(Location::RequiresRegister());
       }
       break;
@@ -1645,7 +1645,7 @@ void LocationsBuilderX86::HandleCondition(HCondition* cond) {
     default:
       locations->SetInAt(0, Location::RequiresRegister());
       locations->SetInAt(1, Location::Any());
-      if (cond->NeedsMaterialization()) {
+      if (!cond->IsEmittedAtUseSite()) {
         // We need a byte register.
         locations->SetOut(Location::RegisterLocation(ECX));
       }
@@ -1654,7 +1654,7 @@ void LocationsBuilderX86::HandleCondition(HCondition* cond) {
 }
 
 void InstructionCodeGeneratorX86::HandleCondition(HCondition* cond) {
-  if (!cond->NeedsMaterialization()) {
+  if (cond->IsEmittedAtUseSite()) {
     return;
   }
 
@@ -2657,7 +2657,11 @@ void LocationsBuilderX86::VisitAdd(HAdd* add) {
     case Primitive::kPrimFloat:
     case Primitive::kPrimDouble: {
       locations->SetInAt(0, Location::RequiresFpuRegister());
-      locations->SetInAt(1, Location::Any());
+      if (add->InputAt(1)->IsX86LoadFromConstantTable()) {
+        DCHECK(add->InputAt(1)->IsEmittedAtUseSite());
+      } else {
+        locations->SetInAt(1, Location::Any());
+      }
       locations->SetOut(Location::SameAsFirstInput());
       break;
     }
@@ -2721,7 +2725,7 @@ void InstructionCodeGeneratorX86::VisitAdd(HAdd* add) {
         __ addss(first.AsFpuRegister<XmmRegister>(), second.AsFpuRegister<XmmRegister>());
       } else if (add->InputAt(1)->IsX86LoadFromConstantTable()) {
         HX86LoadFromConstantTable* const_area = add->InputAt(1)->AsX86LoadFromConstantTable();
-        DCHECK(!const_area->NeedsMaterialization());
+        DCHECK(const_area->IsEmittedAtUseSite());
         __ addss(first.AsFpuRegister<XmmRegister>(),
                  codegen_->LiteralFloatAddress(
                    const_area->GetConstant()->AsFloatConstant()->GetValue(),
@@ -2738,7 +2742,7 @@ void InstructionCodeGeneratorX86::VisitAdd(HAdd* add) {
         __ addsd(first.AsFpuRegister<XmmRegister>(), second.AsFpuRegister<XmmRegister>());
       } else if (add->InputAt(1)->IsX86LoadFromConstantTable()) {
         HX86LoadFromConstantTable* const_area = add->InputAt(1)->AsX86LoadFromConstantTable();
-        DCHECK(!const_area->NeedsMaterialization());
+        DCHECK(const_area->IsEmittedAtUseSite());
         __ addsd(first.AsFpuRegister<XmmRegister>(),
                  codegen_->LiteralDoubleAddress(
                    const_area->GetConstant()->AsDoubleConstant()->GetValue(),
@@ -2769,7 +2773,11 @@ void LocationsBuilderX86::VisitSub(HSub* sub) {
     case Primitive::kPrimFloat:
     case Primitive::kPrimDouble: {
       locations->SetInAt(0, Location::RequiresFpuRegister());
-      locations->SetInAt(1, Location::Any());
+      if (sub->InputAt(1)->IsX86LoadFromConstantTable()) {
+        DCHECK(sub->InputAt(1)->IsEmittedAtUseSite());
+      } else {
+        locations->SetInAt(1, Location::Any());
+      }
       locations->SetOut(Location::SameAsFirstInput());
       break;
     }
@@ -2819,7 +2827,7 @@ void InstructionCodeGeneratorX86::VisitSub(HSub* sub) {
         __ subss(first.AsFpuRegister<XmmRegister>(), second.AsFpuRegister<XmmRegister>());
       } else if (sub->InputAt(1)->IsX86LoadFromConstantTable()) {
         HX86LoadFromConstantTable* const_area = sub->InputAt(1)->AsX86LoadFromConstantTable();
-        DCHECK(!const_area->NeedsMaterialization());
+        DCHECK(const_area->IsEmittedAtUseSite());
         __ subss(first.AsFpuRegister<XmmRegister>(),
                  codegen_->LiteralFloatAddress(
                    const_area->GetConstant()->AsFloatConstant()->GetValue(),
@@ -2836,7 +2844,7 @@ void InstructionCodeGeneratorX86::VisitSub(HSub* sub) {
         __ subsd(first.AsFpuRegister<XmmRegister>(), second.AsFpuRegister<XmmRegister>());
       } else if (sub->InputAt(1)->IsX86LoadFromConstantTable()) {
         HX86LoadFromConstantTable* const_area = sub->InputAt(1)->AsX86LoadFromConstantTable();
-        DCHECK(!const_area->NeedsMaterialization());
+        DCHECK(const_area->IsEmittedAtUseSite());
         __ subsd(first.AsFpuRegister<XmmRegister>(),
                  codegen_->LiteralDoubleAddress(
                      const_area->GetConstant()->AsDoubleConstant()->GetValue(),
@@ -2879,7 +2887,11 @@ void LocationsBuilderX86::VisitMul(HMul* mul) {
     case Primitive::kPrimFloat:
     case Primitive::kPrimDouble: {
       locations->SetInAt(0, Location::RequiresFpuRegister());
-      locations->SetInAt(1, Location::Any());
+      if (mul->InputAt(1)->IsX86LoadFromConstantTable()) {
+        DCHECK(mul->InputAt(1)->IsEmittedAtUseSite());
+      } else {
+        locations->SetInAt(1, Location::Any());
+      }
       locations->SetOut(Location::SameAsFirstInput());
       break;
     }
@@ -3000,7 +3012,7 @@ void InstructionCodeGeneratorX86::VisitMul(HMul* mul) {
         __ mulss(first.AsFpuRegister<XmmRegister>(), second.AsFpuRegister<XmmRegister>());
       } else if (mul->InputAt(1)->IsX86LoadFromConstantTable()) {
         HX86LoadFromConstantTable* const_area = mul->InputAt(1)->AsX86LoadFromConstantTable();
-        DCHECK(!const_area->NeedsMaterialization());
+        DCHECK(const_area->IsEmittedAtUseSite());
         __ mulss(first.AsFpuRegister<XmmRegister>(),
                  codegen_->LiteralFloatAddress(
                      const_area->GetConstant()->AsFloatConstant()->GetValue(),
@@ -3018,7 +3030,7 @@ void InstructionCodeGeneratorX86::VisitMul(HMul* mul) {
         __ mulsd(first.AsFpuRegister<XmmRegister>(), second.AsFpuRegister<XmmRegister>());
       } else if (mul->InputAt(1)->IsX86LoadFromConstantTable()) {
         HX86LoadFromConstantTable* const_area = mul->InputAt(1)->AsX86LoadFromConstantTable();
-        DCHECK(!const_area->NeedsMaterialization());
+        DCHECK(const_area->IsEmittedAtUseSite());
         __ mulsd(first.AsFpuRegister<XmmRegister>(),
                  codegen_->LiteralDoubleAddress(
                      const_area->GetConstant()->AsDoubleConstant()->GetValue(),
@@ -3372,7 +3384,11 @@ void LocationsBuilderX86::VisitDiv(HDiv* div) {
     case Primitive::kPrimFloat:
     case Primitive::kPrimDouble: {
       locations->SetInAt(0, Location::RequiresFpuRegister());
-      locations->SetInAt(1, Location::Any());
+      if (div->InputAt(1)->IsX86LoadFromConstantTable()) {
+        DCHECK(div->InputAt(1)->IsEmittedAtUseSite());
+      } else {
+        locations->SetInAt(1, Location::Any());
+      }
       locations->SetOut(Location::SameAsFirstInput());
       break;
     }
@@ -3399,7 +3415,7 @@ void InstructionCodeGeneratorX86::VisitDiv(HDiv* div) {
         __ divss(first.AsFpuRegister<XmmRegister>(), second.AsFpuRegister<XmmRegister>());
       } else if (div->InputAt(1)->IsX86LoadFromConstantTable()) {
         HX86LoadFromConstantTable* const_area = div->InputAt(1)->AsX86LoadFromConstantTable();
-        DCHECK(!const_area->NeedsMaterialization());
+        DCHECK(const_area->IsEmittedAtUseSite());
         __ divss(first.AsFpuRegister<XmmRegister>(),
                  codegen_->LiteralFloatAddress(
                    const_area->GetConstant()->AsFloatConstant()->GetValue(),
@@ -3416,7 +3432,7 @@ void InstructionCodeGeneratorX86::VisitDiv(HDiv* div) {
         __ divsd(first.AsFpuRegister<XmmRegister>(), second.AsFpuRegister<XmmRegister>());
       } else if (div->InputAt(1)->IsX86LoadFromConstantTable()) {
         HX86LoadFromConstantTable* const_area = div->InputAt(1)->AsX86LoadFromConstantTable();
-        DCHECK(!const_area->NeedsMaterialization());
+        DCHECK(const_area->IsEmittedAtUseSite());
         __ divsd(first.AsFpuRegister<XmmRegister>(),
                  codegen_->LiteralDoubleAddress(
                    const_area->GetConstant()->AsDoubleConstant()->GetValue(),
@@ -6865,7 +6881,7 @@ void LocationsBuilderX86::VisitX86LoadFromConstantTable(
   locations->SetInAt(1, Location::ConstantLocation(insn->GetConstant()));
 
   // If we don't need to be materialized, we only need the inputs to be set.
-  if (!insn->NeedsMaterialization()) {
+  if (insn->IsEmittedAtUseSite()) {
     return;
   }
 
@@ -6885,7 +6901,7 @@ void LocationsBuilderX86::VisitX86LoadFromConstantTable(
 }
 
 void InstructionCodeGeneratorX86::VisitX86LoadFromConstantTable(HX86LoadFromConstantTable* insn) {
-  if (!insn->NeedsMaterialization()) {
+  if (insn->IsEmittedAtUseSite()) {
     return;
   }
 
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index fd188346e4..1781f419f1 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -1638,13 +1638,13 @@ void LocationsBuilderX86_64::HandleCondition(HCondition* cond) {
       locations->SetInAt(1, Location::Any());
       break;
   }
-  if (cond->NeedsMaterialization()) {
+  if (!cond->IsEmittedAtUseSite()) {
     locations->SetOut(Location::RequiresRegister());
   }
 }
 
 void InstructionCodeGeneratorX86_64::HandleCondition(HCondition* cond) {
-  if (!cond->NeedsMaterialization()) {
+  if (cond->IsEmittedAtUseSite()) {
     return;
   }
 
diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
index 926f9399a5..991f8f70ea 100644
--- a/compiler/optimizing/live_ranges_test.cc
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -278,9 +278,9 @@ TEST_F(LiveRangesTest, Loop1) {
   // Test for the phi.
   interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
   range = interval->GetFirstRange();
-  // Instruction is consumed by the if.
+  // Instruction is input of non-materialized Equal and hence live until If.
   ASSERT_EQ(14u, range->GetStart());
-  ASSERT_EQ(17u, range->GetEnd());
+  ASSERT_EQ(19u, range->GetEnd());
   ASSERT_TRUE(range->GetNext() == nullptr);
 }
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 41c2f17cd9..922696bb5d 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1819,6 +1819,7 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
         dex_pc_(dex_pc),
         id_(-1),
         ssa_index_(-1),
+        emitted_at_use_site_(false),
         environment_(nullptr),
         locations_(nullptr),
         live_interval_(nullptr),
@@ -2081,6 +2082,9 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
   // The caller must ensure that this is safe to do.
   void RemoveEnvironmentUsers();
 
+  bool IsEmittedAtUseSite() const { return emitted_at_use_site_; }
+  void MarkEmittedAtUseSite() { emitted_at_use_site_ = true; }
+
  protected:
   virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0;
   virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0;
@@ -2102,6 +2106,10 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
   // When doing liveness analysis, instructions that have uses get an SSA index.
   int ssa_index_;
 
+  // If set, the machine code for this instruction is assumed to be generated by
+  // its users. Used by liveness analysis to compute use positions accordingly.
+  bool emitted_at_use_site_;
+
   // List of instructions that have this instruction as input.
   HUseList<HInstruction*> uses_;
 
@@ -2711,12 +2719,8 @@ class HCondition : public HBinaryOperation {
  public:
   HCondition(HInstruction* first, HInstruction* second, uint32_t dex_pc = kNoDexPc)
       : HBinaryOperation(Primitive::kPrimBoolean, first, second, SideEffects::None(), dex_pc),
-        needs_materialization_(true),
         bias_(ComparisonBias::kNoBias) {}
 
-  bool NeedsMaterialization() const { return needs_materialization_; }
-  void ClearNeedsMaterialization() { needs_materialization_ = false; }
-
   // For code generation purposes, returns whether this instruction is just before
   // `instruction`, and disregard moves in between.
   bool IsBeforeWhenDisregardMoves(HInstruction* instruction) const;
@@ -2748,10 +2752,6 @@ class HCondition : public HBinaryOperation {
   }
 
  private:
-  // For register allocation purposes, returns whether this instruction needs to be
-  // materialized (that is, not just be in the processor flags).
-  bool needs_materialization_;
-
   // Needed if we merge a HCompare into a HCondition.
   ComparisonBias bias_;
 
diff --git a/compiler/optimizing/nodes_x86.h b/compiler/optimizing/nodes_x86.h
index 556217bf74..b1bf939b36 100644
--- a/compiler/optimizing/nodes_x86.h
+++ b/compiler/optimizing/nodes_x86.h
@@ -36,16 +36,12 @@ class HX86ComputeBaseMethodAddress : public HExpression<0> {
 class HX86LoadFromConstantTable : public HExpression<2> {
  public:
   HX86LoadFromConstantTable(HX86ComputeBaseMethodAddress* method_base,
-                            HConstant* constant,
-                            bool needs_materialization = true)
-      : HExpression(constant->GetType(), SideEffects::None(), kNoDexPc),
-        needs_materialization_(needs_materialization) {
+                            HConstant* constant)
+      : HExpression(constant->GetType(), SideEffects::None(), kNoDexPc) {
     SetRawInputAt(0, method_base);
     SetRawInputAt(1, constant);
   }
 
-  bool NeedsMaterialization() const { return needs_materialization_; }
-
   HX86ComputeBaseMethodAddress* GetBaseMethodAddress() const {
     return InputAt(0)->AsX86ComputeBaseMethodAddress();
   }
@@ -57,8 +53,6 @@ class HX86LoadFromConstantTable : public HExpression<2> {
   DECLARE_INSTRUCTION(X86LoadFromConstantTable);
 
  private:
-  const bool needs_materialization_;
-
   DISALLOW_COPY_AND_ASSIGN(HX86LoadFromConstantTable);
 };
 
diff --git a/compiler/optimizing/pc_relative_fixups_x86.cc b/compiler/optimizing/pc_relative_fixups_x86.cc
index 1394dfaf5d..a2180bc9d7 100644
--- a/compiler/optimizing/pc_relative_fixups_x86.cc
+++ b/compiler/optimizing/pc_relative_fixups_x86.cc
@@ -115,7 +115,10 @@ class PCRelativeHandlerVisitor : public HGraphVisitor {
   void ReplaceInput(HInstruction* insn, HConstant* value, int input_index, bool materialize) {
     InitializePCRelativeBasePointer();
     HX86LoadFromConstantTable* load_constant =
-        new (GetGraph()->GetArena()) HX86LoadFromConstantTable(base_, value, materialize);
+        new (GetGraph()->GetArena()) HX86LoadFromConstantTable(base_, value);
+    if (!materialize) {
+      load_constant->MarkEmittedAtUseSite();
+    }
     insn->GetBlock()->InsertInstructionBefore(load_constant, insn);
     insn->ReplaceInput(load_constant, input_index);
   }
diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc
index 63ef600756..ec0fc3a814 100644
--- a/compiler/optimizing/prepare_for_register_allocation.cc
+++ b/compiler/optimizing/prepare_for_register_allocation.cc
@@ -127,25 +127,26 @@ void PrepareForRegisterAllocation::VisitNewInstance(HNewInstance* instruction) {
   }
 }
 
+bool PrepareForRegisterAllocation::CanEmitConditionAt(HCondition* condition,
+                                                      HInstruction* user) const {
+  if (condition->GetNext() != user) {
+    return false;
+  }
+
+  if (user->IsIf() || user->IsDeoptimize()) {
+    return true;
+  }
+
+  return false;
+}
+
 void PrepareForRegisterAllocation::VisitCondition(HCondition* condition) {
-  bool needs_materialization = false;
-  if (!condition->GetUses().HasOnlyOneUse() || !condition->GetEnvUses().IsEmpty()) {
-    needs_materialization = true;
-  } else {
+  if (condition->HasOnlyOneNonEnvironmentUse()) {
     HInstruction* user = condition->GetUses().GetFirst()->GetUser();
-    if (!user->IsIf() && !user->IsDeoptimize()) {
-      needs_materialization = true;
-    } else {
-      // TODO: if there is no intervening instructions with side-effect between this condition
-      // and the If instruction, we should move the condition just before the If.
-      if (condition->GetNext() != user) {
-        needs_materialization = true;
-      }
+    if (CanEmitConditionAt(condition, user)) {
+      condition->MarkEmittedAtUseSite();
     }
   }
-  if (!needs_materialization) {
-    condition->ClearNeedsMaterialization();
-  }
 }
 
 void PrepareForRegisterAllocation::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) {
@@ -165,7 +166,8 @@ void PrepareForRegisterAllocation::VisitInvokeStaticOrDirect(HInvokeStaticOrDire
   }
 }
 
-bool PrepareForRegisterAllocation::CanMoveClinitCheck(HInstruction* input, HInstruction* user) {
+bool PrepareForRegisterAllocation::CanMoveClinitCheck(HInstruction* input,
+                                                      HInstruction* user) const {
   // Determine if input and user come from the same dex instruction, so that we can move
   // the clinit check responsibility from one to the other, i.e. from HClinitCheck (user)
   // to HLoadClass (input), or from HClinitCheck (input) to HInvokeStaticOrDirect (user).
diff --git a/compiler/optimizing/prepare_for_register_allocation.h b/compiler/optimizing/prepare_for_register_allocation.h
index 9b2434250d..c8b8b0dcfa 100644
--- a/compiler/optimizing/prepare_for_register_allocation.h
+++ b/compiler/optimizing/prepare_for_register_allocation.h
@@ -42,7 +42,8 @@ class PrepareForRegisterAllocation : public HGraphDelegateVisitor {
   void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE;
   void VisitNewInstance(HNewInstance* instruction) OVERRIDE;
 
-  bool CanMoveClinitCheck(HInstruction* input, HInstruction* user);
+  bool CanMoveClinitCheck(HInstruction* input, HInstruction* user) const;
+  bool CanEmitConditionAt(HCondition* condition, HInstruction* user) const;
 
   DISALLOW_COPY_AND_ASSIGN(PrepareForRegisterAllocation);
 };
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index a5609fc466..7ed3c84f13 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -242,19 +242,53 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
           }
           if (instruction != nullptr) {
             instruction->GetLiveInterval()->AddUse(
-                current, environment, i, should_be_live);
+                current, environment, i, /* actual_user */ nullptr, should_be_live);
           }
         }
       }
 
-      // All inputs of an instruction must be live.
-      for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
-        HInstruction* input = current->InputAt(i);
-        // Some instructions 'inline' their inputs, that is they do not need
-        // to be materialized.
-        if (input->HasSsaIndex() && current->GetLocations()->InAt(i).IsValid()) {
-          live_in->SetBit(input->GetSsaIndex());
-          input->GetLiveInterval()->AddUse(current, /* environment */ nullptr, i);
+      // Process inputs of instructions.
+      if (current->IsEmittedAtUseSite()) {
+        if (kIsDebugBuild) {
+          DCHECK(!current->GetLocations()->Out().IsValid());
+          for (HUseIterator<HInstruction*> use_it(current->GetUses());
+               !use_it.Done();
+               use_it.Advance()) {
+            HInstruction* user = use_it.Current()->GetUser();
+            size_t index = use_it.Current()->GetIndex();
+            DCHECK(!user->GetLocations()->InAt(index).IsValid());
+          }
+          DCHECK(!current->HasEnvironmentUses());
+        }
+      } else {
+        for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
+          HInstruction* input = current->InputAt(i);
+          bool has_in_location = current->GetLocations()->InAt(i).IsValid();
+          bool has_out_location = input->GetLocations()->Out().IsValid();
+
+          if (has_in_location) {
+            DCHECK(has_out_location);
+            DCHECK(input->HasSsaIndex());
+            // `Input` generates a result used by `current`. Add use and update
+            // the live-in set.
+            input->GetLiveInterval()->AddUse(current, /* environment */ nullptr, i);
+            live_in->SetBit(input->GetSsaIndex());
+          } else if (has_out_location) {
+            // `Input` generates a result but it is not used by `current`.
+          } else {
+            // `Input` is inlined into `current`. Walk over its inputs and record
+            // uses at `current`.
+            DCHECK(input->IsEmittedAtUseSite());
+            for (size_t i2 = 0, e2 = input->InputCount(); i2 < e2; ++i2) {
+              HInstruction* inlined_input = input->InputAt(i2);
+              DCHECK(inlined_input->HasSsaIndex()) << "Recursive inlining not allowed.";
+              if (input->GetLocations()->InAt(i2).IsValid()) {
+                live_in->SetBit(inlined_input->GetSsaIndex());
+                inlined_input->GetLiveInterval()->AddUse(
+                    /* owner */ input, /* environment */ nullptr, i2, /* actual_user */ current);
+              }
+            }
+          }
         }
       }
     }
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 572a7b6a53..a78aedcff5 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -113,10 +113,6 @@ class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
         input_index_(input_index),
         position_(position),
         next_(next) {
-    DCHECK((user == nullptr)
-        || user->IsPhi()
-        || (GetPosition() == user->GetLifetimePosition() + 1)
-        || (GetPosition() == user->GetLifetimePosition()));
     DCHECK(environment == nullptr || user == nullptr);
     DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
   }
@@ -243,21 +239,30 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
     AddRange(position, position + 1);
   }
 
+  // Record use of an input. The use will be recorded as an environment use if
+  // `environment` is not null and as register use otherwise. If `actual_user`
+  // is specified, the use will be recorded at `actual_user`'s lifetime position.
   void AddUse(HInstruction* instruction,
               HEnvironment* environment,
               size_t input_index,
+              HInstruction* actual_user = nullptr,
               bool keep_alive = false) {
-    // Set the use within the instruction.
     bool is_environment = (environment != nullptr);
-    size_t position = instruction->GetLifetimePosition() + 1;
     LocationSummary* locations = instruction->GetLocations();
+    if (actual_user == nullptr) {
+      actual_user = instruction;
+    }
+
+    // Set the use within the instruction.
+    size_t position = actual_user->GetLifetimePosition() + 1;
     if (!is_environment) {
       if (locations->IsFixedInput(input_index) || locations->OutputUsesSameAs(input_index)) {
         // For fixed inputs and output same as input, the register allocator
         // requires to have inputs die at the instruction, so that input moves use the
         // location of the input just before that instruction (and not potential moves due
         // to splitting).
-        position = instruction->GetLifetimePosition();
+        DCHECK_EQ(instruction, actual_user);
+        position = actual_user->GetLifetimePosition();
       } else if (!locations->InAt(input_index).IsValid()) {
         return;
       }
@@ -267,11 +272,8 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
       AddBackEdgeUses(*instruction->GetBlock());
     }
 
-    DCHECK(position == instruction->GetLifetimePosition()
-           || position == instruction->GetLifetimePosition() + 1);
-
     if ((first_use_ != nullptr)
-        && (first_use_->GetUser() == instruction)
+        && (first_use_->GetUser() == actual_user)
         && (first_use_->GetPosition() < position)) {
       // The user uses the instruction multiple times, and one use dies before the other.
       // We update the use list so that the latter is first.
diff --git a/test/565-checker-condition-liveness/expected.txt b/test/565-checker-condition-liveness/expected.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/565-checker-condition-liveness/expected.txt
diff --git a/test/565-checker-condition-liveness/info.txt b/test/565-checker-condition-liveness/info.txt
new file mode 100644
index 0000000000..67b6ceb53f
--- /dev/null
+++ b/test/565-checker-condition-liveness/info.txt
@@ -0,0 +1 @@
+Test the use positions of inputs of non-materialized conditions.
\ No newline at end of file
diff --git a/test/565-checker-condition-liveness/src/Main.java b/test/565-checker-condition-liveness/src/Main.java
new file mode 100644
index 0000000000..a811e5bb16
--- /dev/null
+++ b/test/565-checker-condition-liveness/src/Main.java
@@ -0,0 +1,35 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+public class Main {
+
+  /// CHECK-START: void Main.main(java.lang.String[]) liveness (after)
+  /// CHECK:         <<X:i\d+>>    ArrayLength uses:[<<UseInput:\d+>>]
+  /// CHECK:         <<Y:i\d+>>    StaticFieldGet uses:[<<UseInput>>]
+  /// CHECK:         <<Cond:z\d+>> LessThanOrEqual [<<X>>,<<Y>>]
+  /// CHECK-NEXT:                  If [<<Cond>>] liveness:<<LivIf:\d+>>
+  /// CHECK-EVAL:    <<UseInput>> == <<LivIf>> + 1
+
+  public static void main(String[] args) {
+    int x = args.length;
+    int y = field;
+    if (x > y) {
+      System.nanoTime();
+    }
+  }
+
+  public static int field = 42;
+}