Reland "Propagating values from if clauses to its successors"
This reverts commit fa1034c563b44c4f557814c50e2678e14dcd1d13.
Reason for revert: Relanding after float/double fix. In short,
don't deal with floats/doubles since they bring a lot of edge cases e.g.
if (f == 0.0f) {
// f is not guaranteed to be 0.0f, e.g. it could be -0.0f.
}
Bug: 240543764
Change-Id: I400bdab71dba0934e6f1740538fe6e6c0a7bf5fc
diff --git a/compiler/optimizing/constant_folding.cc b/compiler/optimizing/constant_folding.cc
index 2031707..7fa2132 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 @@
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 @@
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,137 @@
}
}
+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;
+
+ // Don't deal with floats/doubles since they bring a lot of edge cases e.g.
+ // if (f == 0.0f) {
+ // // f is not really guaranteed to be 0.0f. It could be -0.0f, for example
+ // }
+ if (DataType::IsFloatingPointType(variable->GetType())) {
+ return;
+ }
+ DCHECK(!DataType::IsFloatingPointType(constant->GetType()));
+
+ // 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;
+
+ // Re-check floating point values.
+ if (DataType::IsFloatingPointType(variable->GetType())) {
+ return;
+ }
+ DCHECK(!DataType::IsFloatingPointType(constant->GetType()));
+ }
+
+ // 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());
diff --git a/compiler/optimizing/constant_folding.h b/compiler/optimizing/constant_folding.h
index 72bd95b..07388d2 100644
--- a/compiler/optimizing/constant_folding.h
+++ b/compiler/optimizing/constant_folding.h
@@ -19,6 +19,7 @@
#include "nodes.h"
#include "optimization.h"
+#include "optimizing/optimizing_compiler_stats.h"
namespace art {
@@ -39,7 +40,8 @@
*/
class HConstantFolding : public HOptimization {
public:
- HConstantFolding(HGraph* graph, const char* name) : HOptimization(graph, name) {}
+ HConstantFolding(HGraph* graph, OptimizingCompilerStats* stats, const char* name)
+ : HOptimization(graph, name, stats) {}
bool Run() override;
diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc
index 74d9d3a..3bcdc1c 100644
--- a/compiler/optimizing/constant_folding_test.cc
+++ b/compiler/optimizing/constant_folding_test.cc
@@ -58,7 +58,7 @@
std::string actual_before = printer_before.str();
EXPECT_EQ(expected_before, actual_before);
- HConstantFolding(graph_, "constant_folding").Run();
+ HConstantFolding(graph_, /* stats= */ nullptr, "constant_folding").Run();
GraphChecker graph_checker_cf(graph_);
graph_checker_cf.Run();
ASSERT_TRUE(graph_checker_cf.IsValid());
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 3a2f7f2..cdd8fb2 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -2104,7 +2104,7 @@
// Note: if the outermost_graph_ is being compiled OSR, we should not run any
// optimization that could lead to a HDeoptimize. The following optimizations do not.
HDeadCodeElimination dce(callee_graph, inline_stats_, "dead_code_elimination$inliner");
- HConstantFolding fold(callee_graph, "constant_folding$inliner");
+ HConstantFolding fold(callee_graph, inline_stats_, "constant_folding$inliner");
InstructionSimplifier simplify(callee_graph, codegen_, inline_stats_);
HOptimization* optimizations[] = {
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 6ac4e07..4fbb033 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1477,6 +1477,10 @@
UNREACHABLE();
}
+bool HInstruction::Dominates(HInstruction* other_instruction) const {
+ return other_instruction == this || StrictlyDominates(other_instruction);
+}
+
bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const {
if (other_instruction == this) {
// An instruction does not strictly dominate itself.
@@ -1536,14 +1540,19 @@
DCHECK(env_uses_.empty());
}
-void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator, HInstruction* replacement) {
+void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator,
+ HInstruction* replacement,
+ bool strictly_dominated) {
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)) {
+ const bool dominated =
+ strictly_dominated ? dominator->StrictlyDominates(user) : dominator->Dominates(user);
+
+ if (dominated) {
user->ReplaceInput(replacement, index);
} else if (user->IsPhi() && !user->AsPhi()->IsCatchPhi()) {
// If the input flows from a block dominated by `dominator`, we can replace it.
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 39cb927..103d318 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -2444,9 +2444,12 @@
return IsRemovable() && !HasUses();
}
- // Does this instruction strictly dominate `other_instruction`?
- // Returns false if this instruction and `other_instruction` are the same.
- // Aborts if this instruction and `other_instruction` are both phis.
+ // Does this instruction dominate `other_instruction`?
+ // Aborts if this instruction and `other_instruction` are different phis.
+ bool Dominates(HInstruction* other_instruction) const;
+
+ // Same but with `strictly dominates` i.e. returns false if this instruction and
+ // `other_instruction` are the same.
bool StrictlyDominates(HInstruction* other_instruction) const;
int GetId() const { return id_; }
@@ -2511,7 +2514,9 @@
void SetLocations(LocationSummary* locations) { locations_ = locations; }
void ReplaceWith(HInstruction* instruction);
- void ReplaceUsesDominatedBy(HInstruction* dominator, HInstruction* replacement);
+ void ReplaceUsesDominatedBy(HInstruction* dominator,
+ HInstruction* replacement,
+ bool strictly_dominated = true);
void ReplaceEnvUsesDominatedBy(HInstruction* dominator, HInstruction* replacement);
void ReplaceInput(HInstruction* replacement, size_t index);
diff --git a/compiler/optimizing/optimization.cc b/compiler/optimizing/optimization.cc
index 2cac38b..7bf6dbb 100644
--- a/compiler/optimizing/optimization.cc
+++ b/compiler/optimizing/optimization.cc
@@ -221,7 +221,7 @@
// Regular passes.
//
case OptimizationPass::kConstantFolding:
- opt = new (allocator) HConstantFolding(graph, pass_name);
+ opt = new (allocator) HConstantFolding(graph, stats, pass_name);
break;
case OptimizationPass::kDeadCodeElimination:
opt = new (allocator) HDeadCodeElimination(graph, stats, pass_name);
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index d458e42..5e316ba 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -73,6 +73,7 @@
kLoopVectorizedIdiom,
kSelectGenerated,
kRemovedInstanceOf,
+ kPropagatedIfValue,
kInlinedInvokeVirtualOrInterface,
kInlinedLastInvokeVirtualOrInterface,
kImplicitNullCheckGenerated,