Propagating values from if clauses to its successors

We have knowledge of the value of some variables at compile time due
to the fact they are used in if clauses. For example:

  if (variable == constant) {
    // SSA `variable` guaranteed to be equal to constant here.
  } else {
    // No guarantees can be made here (except for booleans since
    // they only have two values).
  }

Similarly with `variable != constant`.

We can also apply this to boolean parameters e.g.

  void foo (boolean val) {
    if (val) {
      // `val` guaranteed to be true here.
      ...
    }
    ...
   }

Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: I55df0252d672870993d06e5ac92f5bba44d902bd

1 files changed, 127 insertions, 3 deletions

diff --git a/compiler/optimizing/constant_folding.cc b/compiler/optimizing/constant_folding.cc
index 2031707759..862abd345d 100644
--- a/compiler/optimizing/constant_folding.cc
+++ b/compiler/optimizing/constant_folding.cc
@@ -16,14 +16,19 @@
 
 #include "constant_folding.h"
 
+#include <algorithm>
+
+#include "optimizing/data_type.h"
+#include "optimizing/nodes.h"
+
 namespace art {
 
 // This visitor tries to simplify instructions that can be evaluated
 // as constants.
 class HConstantFoldingVisitor : public HGraphDelegateVisitor {
  public:
-  explicit HConstantFoldingVisitor(HGraph* graph)
-      : HGraphDelegateVisitor(graph) {}
+  explicit HConstantFoldingVisitor(HGraph* graph, OptimizingCompilerStats* stats)
+      : HGraphDelegateVisitor(graph, stats) {}
 
  private:
   void VisitBasicBlock(HBasicBlock* block) override;
@@ -33,6 +38,9 @@ class HConstantFoldingVisitor : public HGraphDelegateVisitor {
 
   void VisitTypeConversion(HTypeConversion* inst) override;
   void VisitDivZeroCheck(HDivZeroCheck* inst) override;
+  void VisitIf(HIf* inst) override;
+
+  void PropagateValue(HBasicBlock* starting_block, HInstruction* variable, HConstant* constant);
 
   DISALLOW_COPY_AND_ASSIGN(HConstantFoldingVisitor);
 };
@@ -69,7 +77,7 @@ class InstructionWithAbsorbingInputSimplifier : public HGraphVisitor {
 
 
 bool HConstantFolding::Run() {
-  HConstantFoldingVisitor visitor(graph_);
+  HConstantFoldingVisitor visitor(graph_, stats_);
   // Process basic blocks in reverse post-order in the dominator tree,
   // so that an instruction turned into a constant, used as input of
   // another instruction, may possibly be used to turn that second
@@ -130,6 +138,122 @@ void HConstantFoldingVisitor::VisitDivZeroCheck(HDivZeroCheck* inst) {
   }
 }
 
+void HConstantFoldingVisitor::PropagateValue(HBasicBlock* starting_block,
+                                             HInstruction* variable,
+                                             HConstant* constant) {
+  const bool recording_stats = stats_ != nullptr;
+  size_t uses_before = 0;
+  size_t uses_after = 0;
+  if (recording_stats) {
+    uses_before = variable->GetUses().SizeSlow();
+  }
+
+  variable->ReplaceUsesDominatedBy(
+      starting_block->GetFirstInstruction(), constant, /* strictly_dominated= */ false);
+
+  if (recording_stats) {
+    uses_after = variable->GetUses().SizeSlow();
+    DCHECK_GE(uses_after, 1u) << "we must at least have the use in the if clause.";
+    DCHECK_GE(uses_before, uses_after);
+    MaybeRecordStat(stats_, MethodCompilationStat::kPropagatedIfValue, uses_before - uses_after);
+  }
+}
+
+void HConstantFoldingVisitor::VisitIf(HIf* inst) {
+  // Consistency check: the true and false successors do not dominate each other.
+  DCHECK(!inst->IfTrueSuccessor()->Dominates(inst->IfFalseSuccessor()) &&
+         !inst->IfFalseSuccessor()->Dominates(inst->IfTrueSuccessor()));
+
+  HInstruction* if_input = inst->InputAt(0);
+
+  // Already a constant.
+  if (if_input->IsConstant()) {
+    return;
+  }
+
+  // if (variable) {
+  //   SSA `variable` guaranteed to be true
+  // } else {
+  //   and here false
+  // }
+  PropagateValue(inst->IfTrueSuccessor(), if_input, GetGraph()->GetIntConstant(1));
+  PropagateValue(inst->IfFalseSuccessor(), if_input, GetGraph()->GetIntConstant(0));
+
+  // If the input is a condition, we can propagate the information of the condition itself.
+  if (!if_input->IsCondition()) {
+    return;
+  }
+  HCondition* condition = if_input->AsCondition();
+
+  // We want either `==` or `!=`, since we cannot make assumptions for other conditions e.g. `>`
+  if (!condition->IsEqual() && !condition->IsNotEqual()) {
+    return;
+  }
+
+  HInstruction* left = condition->GetLeft();
+  HInstruction* right = condition->GetRight();
+
+  // We want one of them to be a constant and not the other.
+  if (left->IsConstant() == right->IsConstant()) {
+    return;
+  }
+
+  // At this point we have something like:
+  // if (variable == constant) {
+  //   SSA `variable` guaranteed to be equal to constant here
+  // } else {
+  //   No guarantees can be made here (usually, see boolean case below).
+  // }
+  // Similarly with variable != constant, except that we can make guarantees in the else case.
+
+  HConstant* constant = left->IsConstant() ? left->AsConstant() : right->AsConstant();
+  HInstruction* variable = left->IsConstant() ? right : left;
+
+  // Sometimes we have an HCompare flowing into an Equals/NonEquals, which can act as a proxy. For
+  // example: `Equals(Compare(var, constant), 0)`. This is common for long, float, and double.
+  if (variable->IsCompare()) {
+    // We only care about equality comparisons so we skip if it is a less or greater comparison.
+    if (!constant->IsArithmeticZero()) {
+      return;
+    }
+
+    // Update left and right to be the ones from the HCompare.
+    left = variable->AsCompare()->GetLeft();
+    right = variable->AsCompare()->GetRight();
+
+    // Re-check that one of them to be a constant and not the other.
+    if (left->IsConstant() == right->IsConstant()) {
+      return;
+    }
+
+    constant = left->IsConstant() ? left->AsConstant() : right->AsConstant();
+    variable = left->IsConstant() ? right : left;
+  }
+
+  // From this block forward we want to replace the SSA value. We use `starting_block` and not the
+  // `if` block as we want to update one of the branches but not the other.
+  HBasicBlock* starting_block =
+      condition->IsEqual() ? inst->IfTrueSuccessor() : inst->IfFalseSuccessor();
+
+  PropagateValue(starting_block, variable, constant);
+
+  // Special case for booleans since they have only two values so we know what to propagate in the
+  // other branch. However, sometimes our boolean values are not compared to 0 or 1. In those cases
+  // we cannot make an assumption for the `else` branch.
+  if (variable->GetType() == DataType::Type::kBool &&
+      constant->IsIntConstant() &&
+      (constant->AsIntConstant()->IsTrue() || constant->AsIntConstant()->IsFalse())) {
+    HBasicBlock* other_starting_block =
+        condition->IsEqual() ? inst->IfFalseSuccessor() : inst->IfTrueSuccessor();
+    DCHECK_NE(other_starting_block, starting_block);
+
+    HConstant* other_constant = constant->AsIntConstant()->IsTrue() ?
+                                    GetGraph()->GetIntConstant(0) :
+                                    GetGraph()->GetIntConstant(1);
+    DCHECK_NE(other_constant, constant);
+    PropagateValue(other_starting_block, variable, other_constant);
+  }
+}
 
 void InstructionWithAbsorbingInputSimplifier::VisitShift(HBinaryOperation* instruction) {
   DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());