ART: Implement support for instruction inlining

Optimizing HIR contains 'non-materialized' instructions which are
emitted at their use sites rather than their defining sites. This
was not properly handled by the liveness analysis which did not
adjust the use positions of the inputs of such instructions.
Despite the analysis being incorrect, the current use cases never
produce incorrect code.

This patch generalizes the concept of inlined instructions and
updates liveness analysis to set the compute use positions correctly.

Change-Id: Id703c154b20ab861241ae5c715a150385d3ff621

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;
+}