ART: Try to statically evaluate some conditions.

If a condition 'cond' is evaluated in an HIf instruction then in
the successors of the this HIF_BLOCK we statically know the value
of the condition (TRUE in TRUE_SUCC, FALSE in FALSE_SUCC). Using
that we could replace another evaluation (use) EVAL of the same
'cond' with TRUE value (FALSE value) if every path from the
ENTRY_BLOCK to EVAL_BLOCK contains the edge HIF_BLOCK->TRUE_SUCC
(HIF_BLOCK->FALSE_SUCC).

  if (cond) {
    ...
    if (cond) {
      ...
    }
    ...
    int a = cond ? 5 : 105;
    ...
  }

The patch is a prerequisite step for "Loop peeling to eliminate
invariant exits" however it brings some value on its own with
a tiny code size reduction in boot-framework.oat (-8Kb).

Test: 458-checker-instruct-simplification
Test: test-art-target, test-art-host.
Change-Id: Ifbe45097dc2b5f098176fa1a1d023ea90b76d396
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 4c18e16..4c98d83 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -994,6 +994,27 @@
     instruction->GetBlock()->SwapSuccessors();
     RecordSimplification();
   }
+  HInstruction* input = instruction->InputAt(0);
+
+  // If a condition 'cond' is evaluated in an HIf instruction then in the successors of the
+  // IF_BLOCK we statically know the value of the condition (TRUE in TRUE_SUCC, FALSE in
+  // FALSE_SUCC). Using that we can replace another evaluation (use) EVAL of the same 'cond'
+  // with TRUE value (FALSE value) if every path from the ENTRY_BLOCK to EVAL_BLOCK contains the
+  // edge HIF_BLOCK->TRUE_SUCC (HIF_BLOCK->FALSE_SUCC).
+  if (!input->IsConstant()) {
+    HBasicBlock* true_succ = instruction->IfTrueSuccessor();
+    HBasicBlock* false_succ = instruction->IfFalseSuccessor();
+
+    DCHECK_EQ(true_succ->GetPredecessors().size(), 1u);
+    input->ReplaceUsesDominatedBy(
+        true_succ->GetFirstInstruction(), GetGraph()->GetIntConstant(1), /* strictly */ false);
+    RecordSimplification();
+
+    DCHECK_EQ(false_succ->GetPredecessors().size(), 1u);
+    input->ReplaceUsesDominatedBy(
+        false_succ->GetFirstInstruction(), GetGraph()->GetIntConstant(0), /* strictly */ false);
+    RecordSimplification();
+  }
 }
 
 void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) {
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index fa580d9..dda0243 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1110,10 +1110,10 @@
   return true;
 }
 
-bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const {
+bool HInstruction::Dominates(HInstruction* other_instruction, bool strictly) const {
   if (other_instruction == this) {
     // An instruction does not strictly dominate itself.
-    return false;
+    return !strictly;
   }
   HBasicBlock* block = GetBlock();
   HBasicBlock* other_block = other_instruction->GetBlock();
@@ -1147,6 +1147,10 @@
   }
 }
 
+bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const {
+  return Dominates(other_instruction, /* strictly */ true);
+}
+
 void HInstruction::RemoveEnvironment() {
   RemoveEnvironmentUses(this);
   environment_ = nullptr;
@@ -1169,14 +1173,16 @@
   DCHECK(env_uses_.empty());
 }
 
-void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator, HInstruction* replacement) {
+void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator,
+                                          HInstruction* replacement,
+                                          bool strictly) {
   const HUseList<HInstruction*>& uses = GetUses();
   for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
     HInstruction* user = it->GetUser();
     size_t index = it->GetIndex();
     // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput().
     ++it;
-    if (dominator->StrictlyDominates(user)) {
+    if (dominator->Dominates(user, strictly)) {
       user->ReplaceInput(replacement, index);
     }
   }
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 66d5bfe..07ab325 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -2098,9 +2098,13 @@
     return IsRemovable() && !HasUses();
   }
 
-  // Does this instruction strictly dominate `other_instruction`?
-  // Returns false if this instruction and `other_instruction` are the same.
+  // Does this instruction dominate (strictly or in regular sense depending on 'strictly')
+  // `other_instruction`?
+  // Returns '!strictly' if this instruction and `other_instruction` are the same.
   // Aborts if this instruction and `other_instruction` are both phis.
+  bool Dominates(HInstruction* other_instruction, bool strictly) const;
+
+  // Return 'Dominates(other_instruction, /*strictly*/ true)'.
   bool StrictlyDominates(HInstruction* other_instruction) const;
 
   int GetId() const { return id_; }
@@ -2161,7 +2165,13 @@
   void SetLocations(LocationSummary* locations) { locations_ = locations; }
 
   void ReplaceWith(HInstruction* instruction);
-  void ReplaceUsesDominatedBy(HInstruction* dominator, HInstruction* replacement);
+
+  // Replace all uses of the instruction which are dominated by 'dominator' with 'replacement'.
+  // 'strictly' determines whether strict or regular domination relation should be checked.
+  void ReplaceUsesDominatedBy(HInstruction* dominator,
+                              HInstruction* replacement,
+                              bool strictly = true);
+
   void ReplaceInput(HInstruction* replacement, size_t index);
 
   // This is almost the same as doing `ReplaceWith()`. But in this helper, the
diff --git a/test/458-checker-instruct-simplification/src/Main.java b/test/458-checker-instruct-simplification/src/Main.java
index 7797f31..ccaba61 100644
--- a/test/458-checker-instruct-simplification/src/Main.java
+++ b/test/458-checker-instruct-simplification/src/Main.java
@@ -2602,6 +2602,124 @@
     return (byte)((int)(((long)(b & 0xff)) & 255L));
   }
 
+  /// CHECK-START: void Main.$noinline$testIfCondStaticEvaluation(int[], boolean) instruction_simplifier (before)
+  /// CHECK-DAG: <<Param:z\d+>>     ParameterValue
+  /// CHECK-DAG: <<Const0:i\d+>>    IntConstant 0
+  /// CHECK-DAG: <<Const1:i\d+>>    IntConstant 1
+  /// CHECK-DAG: <<Cond0:z\d+>>     Equal [<<Param>>,<<Const0>>]
+  /// CHECK-DAG:                    If [<<Cond0>>]
+  /// CHECK-DAG: <<Cond1:z\d+>>     Equal [<<Param>>,<<Const0>>]
+  /// CHECK-DAG:                    If [<<Cond1>>]
+  /// CHECK-DAG:                    ArraySet [{{l\d+}},{{i\d+}},<<Const0>>]
+  /// CHECK-DAG: <<Cond2:z\d+>>     Equal [<<Param>>,<<Const0>>]
+  /// CHECK-DAG:                    If [<<Cond2>>]
+  /// CHECK-DAG:                    ArraySet [{{l\d+}},{{i\d+}},<<Const1>>]
+  //
+  /// CHECK-NOT:                    If
+  /// CHECK-NOT:                    ArraySet
+
+  /// CHECK-START: void Main.$noinline$testIfCondStaticEvaluation(int[], boolean) instruction_simplifier (after)
+  /// CHECK-DAG: <<Param:z\d+>>     ParameterValue
+  /// CHECK-DAG: <<Const0:i\d+>>    IntConstant 0
+  /// CHECK-DAG: <<Const1:i\d+>>    IntConstant 1
+  /// CHECK-DAG:                    If [<<Param>>]
+  /// CHECK-DAG: <<Cond1:z\d+>>     Equal [<<Const1>>,<<Const0>>]
+  /// CHECK-DAG:                    If [<<Cond1>>]
+  /// CHECK-DAG:                    ArraySet [{{l\d+}},{{i\d+}},<<Const1>>]
+  /// CHECK-DAG: <<Cond2:z\d+>>     Equal [<<Const0>>,<<Const0>>]
+  /// CHECK-DAG:                    If [<<Cond2>>]
+  /// CHECK-DAG:                    ArraySet [{{l\d+}},{{i\d+}},<<Const0>>]
+  //
+  /// CHECK-NOT:                    If
+  /// CHECK-NOT:                    ArraySet
+
+  /// CHECK-START: void Main.$noinline$testIfCondStaticEvaluation(int[], boolean) dead_code_elimination$after_inlining (after)
+  /// CHECK-DAG: <<Param:z\d+>>     ParameterValue
+  /// CHECK-DAG: <<Const1:i\d+>>    IntConstant 1
+  /// CHECK-DAG:                    If [<<Param>>]
+  /// CHECK-DAG:                    ArraySet [{{l\d+}},{{i\d+}},<<Const1>>]
+  //
+  /// CHECK-NOT:                    IntConstant 0
+  /// CHECK-NOT:                    If [<<Param>>]
+  /// CHECK-NOT:                    ArraySet
+  private static void $noinline$testIfCondStaticEvaluation(int[] a, boolean f) {
+    if (f) {
+      if (f) {
+        a[0] = 1;
+      }
+    } else {
+      if (f) {
+        a[0] = 0;
+      }
+    }
+  }
+
+  /// CHECK-START: void Main.$noinline$testManualUnrollWithInvarExits(int[], boolean) instruction_simplifier (before)
+  /// CHECK-DAG: <<Param:z\d+>>     ParameterValue                            loop:none
+  /// CHECK-DAG: <<Const0:i\d+>>    IntConstant 0                             loop:none
+  /// CHECK-DAG: <<Const1:i\d+>>    IntConstant 1                             loop:none
+  /// CHECK-DAG: <<Cond0:z\d+>>     Equal [<<Param>>,<<Const0>>]              loop:none
+  /// CHECK-DAG:                    If [<<Cond0>>]                            loop:none
+  /// CHECK-DAG:                    ArraySet [{{l\d+}},{{i\d+}},<<Const1>>]   loop:none
+  /// CHECK-DAG: <<Phi:i\d+>>       Phi                                       loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: <<LoopCheck:z\d+>> GreaterThanOrEqual                        loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:                    If [<<LoopCheck>>]                        loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: <<Cond1:z\d+>>     NotEqual [<<Param>>,<<Const0>>]           loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:                    If [<<Cond1>>]                            loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:                    ArraySet [{{l\d+}},{{i\d+}},<<Const1>>]   loop:<<Loop>>      outer_loop:none
+  //
+  /// CHECK-NOT:                    If
+  /// CHECK-NOT:                    ArraySet
+
+  /// CHECK-START: void Main.$noinline$testManualUnrollWithInvarExits(int[], boolean) instruction_simplifier (after)
+  /// CHECK-DAG: <<Param:z\d+>>     ParameterValue                            loop:none
+  /// CHECK-DAG: <<Const0:i\d+>>    IntConstant 0                             loop:none
+  /// CHECK-DAG: <<Const1:i\d+>>    IntConstant 1                             loop:none
+  /// CHECK-DAG:                    If [<<Param>>]                            loop:none
+  /// CHECK-DAG:                    ArraySet [{{l\d+}},{{i\d+}},<<Const1>>]   loop:none
+  /// CHECK-DAG: <<Phi:i\d+>>       Phi                                       loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: <<LoopCheck:z\d+>> GreaterThanOrEqual                        loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:                    If [<<LoopCheck>>]                        loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: <<Cond1:z\d+>>     NotEqual [<<Const0>>,<<Const0>>]          loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:                    If [<<Cond1>>]                            loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:                    ArraySet [{{l\d+}},{{i\d+}},<<Const1>>]   loop:<<Loop>>      outer_loop:none
+  //
+  /// CHECK-NOT:                    If
+  /// CHECK-NOT:                    ArraySet
+
+  /// CHECK-START: void Main.$noinline$testManualUnrollWithInvarExits(int[], boolean) dead_code_elimination$after_inlining (after)
+  /// CHECK-DAG: <<Param:z\d+>>     ParameterValue                            loop:none
+  /// CHECK-DAG: <<Const1:i\d+>>    IntConstant 1                             loop:none
+  /// CHECK-DAG:                    If [<<Param>>]                            loop:none
+  /// CHECK-DAG:                    ArraySet [{{l\d+}},{{i\d+}},<<Const1>>]   loop:none
+  /// CHECK-DAG: <<Phi:i\d+>>       Phi                                       loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: <<LoopCheck:z\d+>> GreaterThanOrEqual                        loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:                    If [<<LoopCheck>>]                        loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:                    ArraySet [{{l\d+}},{{i\d+}},<<Const1>>]   loop:<<Loop>>      outer_loop:none
+  //
+  /// CHECK-NOT:                    If
+  /// CHECK-NOT:                    ArraySet
+  private static void $noinline$testManualUnrollWithInvarExits(int[] a, boolean f) {
+    if (f) {
+      return;
+    }
+    a[0] = 1;
+    for (int i = 1; i < a.length; i++) {
+      if (f) {
+        return;
+      }
+      a[i] = 1;
+    }
+  }
+
+  public static final int LENGTH = 1024;
+
+  private static final void initArray(int[] a) {
+    for (int i = 0; i < a.length; i++) {
+      a[i] = 0;
+    }
+  }
+
   public static void main(String[] args) {
     int arg = 123456;
     float floatArg = 123456.125f;
@@ -2845,6 +2963,26 @@
     assertIntEquals(1, $noinline$bug68142795Boolean(true));
     assertIntEquals(0x7f, $noinline$bug68142795Elaborate((byte) 0x7f));
     assertIntEquals((byte) 0x80, $noinline$bug68142795Elaborate((byte) 0x80));
+
+    int[] array = new int[LENGTH];
+
+    array[0] = 0;
+    $noinline$testIfCondStaticEvaluation(array, true);
+    assertIntEquals(array[0], 1);
+    array[0] = 0;
+    $noinline$testIfCondStaticEvaluation(array, false);
+    assertIntEquals(array[0], 0);
+
+    initArray(array);
+    $noinline$testManualUnrollWithInvarExits(array, false);
+    for (int i = 0; i < array.length; i++) {
+      assertIntEquals(array[i], 1);
+    }
+    initArray(array);
+    $noinline$testManualUnrollWithInvarExits(array, true);
+    for (int i = 0; i < array.length; i++) {
+      assertIntEquals(array[i], 0);
+    }
   }
 
   private static boolean $inline$true() { return true; }