Simplify loop invariant operations during induction analysis.
Rationale:
Saves some memory for nodes that are not really required, and
yields slightly more readable debugging strings.
Change-Id: I95b64b48869699137b5d49e26eb20091e264de7a
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 8b38414..300ffbe 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -42,33 +42,6 @@
instruction->GetBlock() == loop->GetHeader();
}
-/**
- * Returns true for 32/64-bit integral constant, passing its value as output parameter.
- */
-static bool IsIntAndGet(HInstruction* instruction, int64_t* value) {
- if (instruction->IsIntConstant()) {
- *value = instruction->AsIntConstant()->GetValue();
- return true;
- } else if (instruction->IsLongConstant()) {
- *value = instruction->AsLongConstant()->GetValue();
- return true;
- }
- return false;
-}
-
-/**
- * Returns a string representation of an instruction
- * (for testing and debugging only).
- */
-static std::string InstructionToString(HInstruction* instruction) {
- if (instruction->IsIntConstant()) {
- return std::to_string(instruction->AsIntConstant()->GetValue());
- } else if (instruction->IsLongConstant()) {
- return std::to_string(instruction->AsLongConstant()->GetValue()) + "L";
- }
- return std::to_string(instruction->GetId()) + ":" + instruction->DebugName();
-}
-
//
// Class methods.
//
@@ -242,7 +215,7 @@
if (size == 1) {
InductionInfo* update = LookupInfo(loop, internal);
if (update != nullptr) {
- AssignInfo(loop, phi, NewInduction(kWrapAround, initial, update));
+ AssignInfo(loop, phi, CreateInduction(kWrapAround, initial, update));
}
return;
}
@@ -275,7 +248,7 @@
case kInvariant:
// Classify phi (last element in scc_) and then the rest of the cycle "on-demand".
// Statements are scanned in the Tarjan SCC order, with phi first.
- AssignInfo(loop, phi, NewInduction(kLinear, induction, initial));
+ AssignInfo(loop, phi, CreateInduction(kLinear, induction, initial));
for (size_t i = 0; i < size - 1; i++) {
ClassifyTrivial(loop, scc_[i]);
}
@@ -305,9 +278,9 @@
// (b, c, d, e, a)
// in preparation of assigning this to the previous variable in the sequence.
if (induction->induction_class == kInvariant) {
- return NewInduction(kPeriodic, induction, last);
+ return CreateInduction(kPeriodic, induction, last);
}
- return NewInduction(kPeriodic, induction->op_a, RotatePeriodicInduction(induction->op_b, last));
+ return CreateInduction(kPeriodic, induction->op_a, RotatePeriodicInduction(induction->op_b, last));
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(InductionInfo* a,
@@ -327,9 +300,9 @@
// be combined. All other combinations fail, however.
if (a != nullptr && b != nullptr) {
if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
- return NewInvariantOp(op, a, b);
+ return CreateInvariantOp(op, a, b);
} else if (a->induction_class == kLinear && b->induction_class == kLinear) {
- return NewInduction(
+ return CreateInduction(
kLinear, TransferAddSub(a->op_a, b->op_a, op), TransferAddSub(a->op_b, b->op_b, op));
} else if (a->induction_class == kInvariant) {
InductionInfo* new_a = b->op_a;
@@ -340,7 +313,7 @@
} else if (op == kSub) { // Negation required.
new_a = TransferNeg(new_a);
}
- return NewInduction(b->induction_class, new_a, new_b);
+ return CreateInduction(b->induction_class, new_a, new_b);
} else if (b->induction_class == kInvariant) {
InductionInfo* new_a = a->op_a;
InductionInfo* new_b = TransferAddSub(a->op_b, b, op);
@@ -348,7 +321,7 @@
DCHECK(a->induction_class == kWrapAround || a->induction_class == kPeriodic);
new_a = TransferAddSub(new_a, b, op);
}
- return NewInduction(a->induction_class, new_a, new_b);
+ return CreateInduction(a->induction_class, new_a, new_b);
}
}
return nullptr;
@@ -361,11 +334,11 @@
// Two non-invariant inputs cannot be multiplied, however.
if (a != nullptr && b != nullptr) {
if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
- return NewInvariantOp(kMul, a, b);
+ return CreateInvariantOp(kMul, a, b);
} else if (a->induction_class == kInvariant) {
- return NewInduction(b->induction_class, TransferMul(a, b->op_a), TransferMul(a, b->op_b));
+ return CreateInduction(b->induction_class, TransferMul(a, b->op_a), TransferMul(a, b->op_b));
} else if (b->induction_class == kInvariant) {
- return NewInduction(a->induction_class, TransferMul(a->op_a, b), TransferMul(a->op_b, b));
+ return CreateInduction(a->induction_class, TransferMul(a->op_a, b), TransferMul(a->op_b, b));
}
}
return nullptr;
@@ -375,19 +348,17 @@
InductionInfo* b,
Primitive::Type t) {
// Transfer over a shift left: treat shift by restricted constant as equivalent multiplication.
- if (a != nullptr && b != nullptr && b->induction_class == kInvariant && b->operation == kFetch) {
- int64_t value = -1;
+ int64_t value = -1;
+ if (a != nullptr && IsIntAndGet(b, &value)) {
// Obtain the constant needed for the multiplication. This yields an existing instruction
// if the constants is already there. Otherwise, this has a side effect on the HIR.
// The restriction on the shift factor avoids generating a negative constant
// (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that generalization
// for shift factors outside [0,32) and [0,64) ranges is done by earlier simplification.
- if (IsIntAndGet(b->fetch, &value)) {
- if (t == Primitive::kPrimInt && 0 <= value && value < 31) {
- return TransferMul(a, NewInvariantFetch(graph_->GetIntConstant(1 << value)));
- } else if (t == Primitive::kPrimLong && 0 <= value && value < 63) {
- return TransferMul(a, NewInvariantFetch(graph_->GetLongConstant(1L << value)));
- }
+ if (t == Primitive::kPrimInt && 0 <= value && value < 31) {
+ return TransferMul(a, CreateInvariantFetch(graph_->GetIntConstant(1 << value)));
+ } else if (t == Primitive::kPrimLong && 0 <= value && value < 63) {
+ return TransferMul(a, CreateInvariantFetch(graph_->GetLongConstant(1L << value)));
}
}
return nullptr;
@@ -398,9 +369,9 @@
// yields a similar but negated induction as result.
if (a != nullptr) {
if (a->induction_class == kInvariant) {
- return NewInvariantOp(kNeg, nullptr, a);
+ return CreateInvariantOp(kNeg, nullptr, a);
}
- return NewInduction(a->induction_class, TransferNeg(a->op_a), TransferNeg(a->op_b));
+ return CreateInduction(a->induction_class, TransferNeg(a->op_a), TransferNeg(a->op_b));
}
return nullptr;
}
@@ -429,13 +400,13 @@
if (a != nullptr && a->induction_class == kInvariant) {
if (instruction->InputAt(1) == phi) {
InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
- return NewInduction(kPeriodic, a, initial);
+ return CreateInduction(kPeriodic, a, initial);
}
auto it = cycle_.find(instruction->InputAt(1));
if (it != cycle_.end()) {
InductionInfo* b = it->second;
if (b->induction_class == kPeriodic) {
- return NewInduction(kPeriodic, a, b);
+ return CreateInduction(kPeriodic, a, b);
}
}
}
@@ -456,13 +427,13 @@
InductionInfo* b = LookupInfo(loop, y);
if (b != nullptr && b->induction_class == kInvariant) {
if (x == phi) {
- return (op == kAdd) ? b : NewInvariantOp(kNeg, nullptr, b);
+ return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b);
}
auto it = cycle_.find(x);
if (it != cycle_.end()) {
InductionInfo* a = it->second;
if (a->induction_class == kInvariant) {
- return NewInvariantOp(op, a, b);
+ return CreateInvariantOp(op, a, b);
}
}
}
@@ -479,7 +450,7 @@
InductionInfo* a = LookupInfo(loop, x);
if (a != nullptr && a->induction_class == kInvariant) {
InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
- return NewInduction(kPeriodic, NewInvariantOp(kSub, a, initial), initial);
+ return CreateInduction(kPeriodic, CreateInvariantOp(kSub, a, initial), initial);
}
}
}
@@ -509,13 +480,59 @@
}
}
if (IsLoopInvariant(loop, instruction)) {
- InductionInfo* info = NewInvariantFetch(instruction);
+ InductionInfo* info = CreateInvariantFetch(instruction);
AssignInfo(loop, instruction, info);
return info;
}
return nullptr;
}
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant(
+ InductionOp op,
+ InductionInfo* a,
+ InductionInfo* b) {
+ // Perform some light-weight simplifications during construction of a new invariant.
+ // This often safes memory and yields a more concise representation of the induction.
+ // More exhaustive simplifications are done by later phases once induction nodes are
+ // translated back into HIR code (e.g. by loop optimizations or BCE).
+ int64_t value = -1;
+ if (IsIntAndGet(a, &value)) {
+ if (value == 0) {
+ // Simplify 0 + b = b, 0 * b = 0.
+ if (op == kAdd) {
+ return b;
+ } else if (op == kMul) {
+ return a;
+ }
+ } else if (value == 1 && op == kMul) {
+ // Simplify 1 * b = b.
+ return b;
+ }
+ }
+ if (IsIntAndGet(b, &value)) {
+ if (value == 0) {
+ // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, - 0 = 0.
+ if (op == kAdd || op == kSub) {
+ return a;
+ } else if (op == kMul || op == kNeg) {
+ return b;
+ }
+ } else if (value == 1 && (op == kMul || op == kDiv)) {
+ // Simplify a * 1 = a, a / 1 = a.
+ return a;
+ }
+ } else if (b->operation == kNeg) {
+ // Simplify a + (-b) = a - b, a - (-b) = a + b, - (-b) = b.
+ switch (op) {
+ case kAdd: op = kSub; b = b->op_b; break;
+ case kSub: op = kAdd; b = b->op_b; break;
+ case kNeg: return b->op_b;
+ default: break;
+ }
+ }
+ return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr);
+}
+
bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
InductionInfo* info2) {
// Test structural equality only, without accounting for simplifications.
@@ -531,9 +548,24 @@
return info1 == info2;
}
+bool HInductionVarAnalysis::IsIntAndGet(InductionInfo* info, int64_t* value) {
+ if (info != nullptr && info->induction_class == kInvariant && info->operation == kFetch) {
+ DCHECK(info->fetch);
+ if (info->fetch->IsIntConstant()) {
+ *value = info->fetch->AsIntConstant()->GetValue();
+ return true;
+ } else if (info->fetch->IsLongConstant()) {
+ *value = info->fetch->AsLongConstant()->GetValue();
+ return true;
+ }
+ }
+ return false;
+}
+
std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
if (info != nullptr) {
if (info->induction_class == kInvariant) {
+ int64_t value = -1;
std::string inv = "(";
inv += InductionToString(info->op_a);
switch (info->operation) {
@@ -545,7 +577,11 @@
case kDiv: inv += " / "; break;
case kFetch:
DCHECK(info->fetch);
- inv += InstructionToString(info->fetch);
+ if (IsIntAndGet(info, &value)) {
+ inv += std::to_string(value);
+ } else {
+ inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName();
+ }
break;
}
inv += InductionToString(info->op_b);
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index db00f58..180d1f7 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -100,17 +100,17 @@
return map_.find(instruction) != map_.end();
}
- InductionInfo* NewInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
+ InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
- return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr);
+ return CreateSimplifiedInvariant(op, a, b);
}
- InductionInfo* NewInvariantFetch(HInstruction* f) {
+ InductionInfo* CreateInvariantFetch(HInstruction* f) {
DCHECK(f != nullptr);
return new (graph_->GetArena()) InductionInfo(kInvariant, kFetch, nullptr, nullptr, f);
}
- InductionInfo* NewInduction(InductionClass ic, InductionInfo* a, InductionInfo* b) {
+ InductionInfo* CreateInduction(InductionClass ic, InductionInfo* a, InductionInfo* b) {
DCHECK(a != nullptr && b != nullptr);
return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr);
}
@@ -145,9 +145,11 @@
// Assign and lookup.
void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
+ InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
// Helpers.
static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
+ static bool IsIntAndGet(InductionInfo* info, int64_t* value);
static std::string InductionToString(InductionInfo* info);
// TODO: fine tune the following data structures, only keep relevant data.
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index b569fbe..cfd0b16 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -230,7 +230,7 @@
PerformInductionVarAnalysis();
EXPECT_STREQ("((1) * i + (0))", GetInductionInfo(store->InputAt(1), 0).c_str());
- EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(increment_[0], 0).c_str());
+ EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[0], 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindDerivedInduction) {
@@ -260,11 +260,11 @@
InsertLocalStore(induc_, neg, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ("((1) * i + ((100) + (0)))", GetInductionInfo(add, 0).c_str());
- EXPECT_STREQ("(( - (1)) * i + ((100) - (0)))", GetInductionInfo(sub, 0).c_str());
- EXPECT_STREQ("(((100) * (1)) * i + ((100) * (0)))", GetInductionInfo(mul, 0).c_str());
- EXPECT_STREQ("(((1) * (2)) * i + ((0) * (2)))", GetInductionInfo(shl, 0).c_str());
- EXPECT_STREQ("(( - (1)) * i + ( - (0)))", GetInductionInfo(neg, 0).c_str());
+ EXPECT_STREQ("((1) * i + (100))", GetInductionInfo(add, 0).c_str());
+ EXPECT_STREQ("(( - (1)) * i + (100))", GetInductionInfo(sub, 0).c_str());
+ EXPECT_STREQ("((100) * i + (0))", GetInductionInfo(mul, 0).c_str());
+ EXPECT_STREQ("((2) * i + (0))", GetInductionInfo(shl, 0).c_str());
+ EXPECT_STREQ("(( - (1)) * i + (0))", GetInductionInfo(neg, 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindChainInduction) {
@@ -287,9 +287,9 @@
HInstruction* store2 = InsertArrayStore(induc_, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ("(((100) - (1)) * i + ((0) + (100)))",
+ EXPECT_STREQ("(((100) - (1)) * i + (100))",
GetInductionInfo(store1->InputAt(1), 0).c_str());
- EXPECT_STREQ("(((100) - (1)) * i + (((0) + (100)) - (1)))",
+ EXPECT_STREQ("(((100) - (1)) * i + ((100) - (1)))",
GetInductionInfo(store2->InputAt(1), 0).c_str());
}
@@ -321,7 +321,7 @@
HInstruction* store = InsertArrayStore(induc_, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(store->InputAt(1), 0).c_str());
+ EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(store->InputAt(1), 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindTwoWayDerivedInduction) {
@@ -351,7 +351,7 @@
HInstruction* store = InsertArrayStore(induc_, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(store->InputAt(1), 0).c_str());
+ EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(store->InputAt(1), 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) {
@@ -368,7 +368,7 @@
InsertLocalStore(induc_, sub, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ("wrap((0), (( - (1)) * i + ((100) - (0))))",
+ EXPECT_STREQ("wrap((0), (( - (1)) * i + (100)))",
GetInductionInfo(store->InputAt(1), 0).c_str());
}
@@ -389,7 +389,7 @@
InsertLocalStore(tmp_, sub, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ("wrap((0), wrap((100), (( - (1)) * i + ((100) - (0)))))",
+ EXPECT_STREQ("wrap((0), wrap((100), (( - (1)) * i + (100))))",
GetInductionInfo(store->InputAt(1), 0).c_str());
}
@@ -427,16 +427,11 @@
HShl(Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0), constant1_), 0), 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ("wrap(((0) + (100)), (((1) * (2)) * i + (((0) * (2)) + (100))))",
- GetInductionInfo(add, 0).c_str());
- EXPECT_STREQ("wrap(((0) - (100)), (((1) * (2)) * i + (((0) * (2)) - (100))))",
- GetInductionInfo(sub, 0).c_str());
- EXPECT_STREQ("wrap(((0) * (100)), ((((1) * (2)) * (100)) * i + (((0) * (2)) * (100))))",
- GetInductionInfo(mul, 0).c_str());
- EXPECT_STREQ("wrap(((0) * (2)), ((((1) * (2)) * (2)) * i + (((0) * (2)) * (2))))",
- GetInductionInfo(shl, 0).c_str());
- EXPECT_STREQ("wrap(( - (0)), (( - ((1) * (2))) * i + ( - ((0) * (2)))))",
- GetInductionInfo(neg, 0).c_str());
+ EXPECT_STREQ("wrap((100), ((2) * i + (100)))", GetInductionInfo(add, 0).c_str());
+ EXPECT_STREQ("wrap(((0) - (100)), ((2) * i + ((0) - (100))))", GetInductionInfo(sub, 0).c_str());
+ EXPECT_STREQ("wrap((0), (((2) * (100)) * i + (0)))", GetInductionInfo(mul, 0).c_str());
+ EXPECT_STREQ("wrap((0), (((2) * (2)) * i + (0)))", GetInductionInfo(shl, 0).c_str());
+ EXPECT_STREQ("wrap((0), (( - (2)) * i + (0)))", GetInductionInfo(neg, 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindPeriodicInduction) {
@@ -477,8 +472,8 @@
InsertLocalStore(induc_, sub, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ("periodic((0), ((1) - (0)))", GetInductionInfo(store->InputAt(1), 0).c_str());
- EXPECT_STREQ("periodic(((1) - (0)), (0))", GetInductionInfo(sub, 0).c_str());
+ EXPECT_STREQ("periodic((0), (1))", GetInductionInfo(store->InputAt(1), 0).c_str());
+ EXPECT_STREQ("periodic((1), (0))", GetInductionInfo(sub, 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) {
@@ -515,11 +510,11 @@
InsertLocalStore(tmp_, neg, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ("periodic((((1) - (0)) + (100)), ((0) + (100)))", GetInductionInfo(add, 0).c_str());
- EXPECT_STREQ("periodic((((1) - (0)) - (100)), ((0) - (100)))", GetInductionInfo(sub, 0).c_str());
- EXPECT_STREQ("periodic((((1) - (0)) * (100)), ((0) * (100)))", GetInductionInfo(mul, 0).c_str());
- EXPECT_STREQ("periodic((((1) - (0)) * (2)), ((0) * (2)))", GetInductionInfo(shl, 0).c_str());
- EXPECT_STREQ("periodic(( - ((1) - (0))), ( - (0)))", GetInductionInfo(neg, 0).c_str());
+ EXPECT_STREQ("periodic(((1) + (100)), (100))", GetInductionInfo(add, 0).c_str());
+ EXPECT_STREQ("periodic(((1) - (100)), ((0) - (100)))", GetInductionInfo(sub, 0).c_str());
+ EXPECT_STREQ("periodic((100), (0))", GetInductionInfo(mul, 0).c_str());
+ EXPECT_STREQ("periodic((2), (0))", GetInductionInfo(shl, 0).c_str());
+ EXPECT_STREQ("periodic(( - (1)), (0))", GetInductionInfo(neg, 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
@@ -550,7 +545,7 @@
} else {
EXPECT_STREQ("", GetInductionInfo(store->InputAt(1), d).c_str());
}
- EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(increment_[d], d).c_str());
+ EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[d], d).c_str());
}
}