Clean up InductionVarAnalysis.
Move temporary members to local variables and allocations
from `ArenaAllocator` to `ScopedArenaAllocator`. While this
requires passing more parameters around, it also exposes
whether these parameters are constant or mutable.
Rewrite the strongly connected component (SCC) search to
avoid recursion. The recursion depth was dependent on the
input code, so essentially arbitrary, and therefore there
was a risk of stack overflow.
Clean up a few other minor things in `InductionVarAnalysis`
and `LoopOptimization`.
Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 216762268
Change-Id: Ifed50b8e62e47487edc683564352880df2158247
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 3a10d58..e6d9079 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -15,45 +15,12 @@
*/
#include "induction_var_analysis.h"
+
#include "induction_var_range.h"
namespace art {
/**
- * Since graph traversal may enter a SCC at any position, an initial representation may be rotated,
- * along dependences, viz. any of (a, b, c, d), (d, a, b, c) (c, d, a, b), (b, c, d, a) assuming
- * a chain of dependences (mutual independent items may occur in arbitrary order). For proper
- * classification, the lexicographically first loop-phi is rotated to the front.
- */
-static void RotateEntryPhiFirst(HLoopInformation* loop,
- ArenaVector<HInstruction*>* scc,
- ArenaVector<HInstruction*>* new_scc) {
- // Find very first loop-phi.
- const HInstructionList& phis = loop->GetHeader()->GetPhis();
- HInstruction* phi = nullptr;
- size_t phi_pos = -1;
- const size_t size = scc->size();
- for (size_t i = 0; i < size; i++) {
- HInstruction* other = (*scc)[i];
- if (other->IsLoopHeaderPhi() && (phi == nullptr || phis.FoundBefore(other, phi))) {
- phi = other;
- phi_pos = i;
- }
- }
-
- // If found, bring that loop-phi to front.
- if (phi != nullptr) {
- new_scc->clear();
- for (size_t i = 0; i < size; i++) {
- new_scc->push_back((*scc)[phi_pos]);
- if (++phi_pos >= size) phi_pos = 0;
- }
- DCHECK_EQ(size, new_scc->size());
- scc->swap(*new_scc);
- }
-}
-
-/**
* Returns true if the from/to types denote a narrowing, integral conversion (precision loss).
*/
static bool IsNarrowingIntegralConversion(DataType::Type from, DataType::Type to) {
@@ -157,10 +124,10 @@
/**
* Relinks the Phi structure after break-loop rewriting.
*/
-bool FixOutsideUse(HLoopInformation* loop,
- HInstruction* instruction,
- HInstruction* replacement,
- bool rewrite) {
+static bool FixOutsideUse(HLoopInformation* loop,
+ HInstruction* instruction,
+ HInstruction* replacement,
+ bool rewrite) {
// Deal with regular uses.
const HUseList<HInstruction*>& uses = instruction->GetUses();
for (auto it = uses.begin(), end = uses.end(); it != end; ) {
@@ -185,9 +152,7 @@
if (replacement == nullptr) {
return false;
} else if (rewrite) {
- user->RemoveAsUserOfInput(index);
- user->SetRawEnvAt(index, replacement);
- replacement->AddEnvUseAt(user, index);
+ user->ReplaceInput(replacement, index);
}
}
}
@@ -197,12 +162,12 @@
/**
* Test and rewrite the loop body of a break-loop. Returns true on success.
*/
-bool RewriteBreakLoopBody(HLoopInformation* loop,
- HBasicBlock* body,
- HInstruction* cond,
- HInstruction* index,
- HInstruction* upper,
- bool rewrite) {
+static bool RewriteBreakLoopBody(HLoopInformation* loop,
+ HBasicBlock* body,
+ HInstruction* cond,
+ HInstruction* index,
+ HInstruction* upper,
+ bool rewrite) {
// Deal with Phis. Outside use prohibited, except for index (which gets exit value).
for (HInstructionIterator it(loop->GetHeader()->GetPhis()); !it.Done(); it.Advance()) {
HInstruction* exit_value = it.Current() == index ? upper : nullptr;
@@ -211,32 +176,46 @@
}
}
// Deal with other statements in header.
- for (HInstruction* m = cond->GetPrevious(), *p = nullptr; m && !m->IsSuspendCheck(); m = p) {
- p = m->GetPrevious();
+ for (HInstruction* m = cond->GetPrevious(); m && !m->IsSuspendCheck();) {
+ HInstruction* p = m->GetPrevious();
if (rewrite) {
m->MoveBefore(body->GetFirstInstruction(), false);
}
if (!FixOutsideUse(loop, m, FindFirstLoopHeaderPhiUse(loop, m), rewrite)) {
return false;
}
+ m = p;
}
return true;
}
//
-// Class methods.
+// Class members.
//
+struct HInductionVarAnalysis::NodeInfo {
+ explicit NodeInfo(uint32_t d) : depth(d), done(false) {}
+ uint32_t depth;
+ bool done;
+};
+
+struct HInductionVarAnalysis::StackEntry {
+ StackEntry(HInstruction* insn, NodeInfo* info, size_t link = std::numeric_limits<size_t>::max())
+ : instruction(insn),
+ node_info(info),
+ user_link(link),
+ num_visited_inputs(0u),
+ low_depth(info->depth) {}
+
+ HInstruction* instruction;
+ NodeInfo* node_info;
+ size_t user_link; // Stack index of the user that is visiting this input.
+ size_t num_visited_inputs;
+ size_t low_depth;
+};
+
HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph, const char* name)
: HOptimization(graph, name),
- global_depth_(0),
- stack_(graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)),
- map_(std::less<HInstruction*>(),
- graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)),
- scc_(graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)),
- cycle_(std::less<HInstruction*>(),
- graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)),
- type_(DataType::Type::kVoid),
induction_(std::less<HLoopInformation*>(),
graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)),
cycles_(std::less<HPhi*>(),
@@ -257,12 +236,13 @@
}
void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) {
+ ScopedArenaAllocator local_allocator(graph_->GetArenaStack());
+ ScopedArenaSafeMap<HInstruction*, NodeInfo> visited_instructions(
+ std::less<HInstruction*>(), local_allocator.Adapter(kArenaAllocInductionVarAnalysis));
+
// Find strongly connected components (SSCs) in the SSA graph of this loop using Tarjan's
// algorithm. Due to the descendant-first nature, classification happens "on-demand".
- global_depth_ = 0;
- DCHECK(stack_.empty());
- map_.clear();
-
+ size_t global_depth = 0;
for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) {
HBasicBlock* loop_block = it_loop.Current();
DCHECK(loop_block->IsInLoop());
@@ -271,108 +251,168 @@
}
// Visit phi-operations and instructions.
for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) {
- HInstruction* instruction = it.Current();
- if (!IsVisitedNode(instruction)) {
- VisitNode(loop, instruction);
- }
+ global_depth = TryVisitNodes(loop, it.Current(), global_depth, &visited_instructions);
}
for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) {
- HInstruction* instruction = it.Current();
- if (!IsVisitedNode(instruction)) {
- VisitNode(loop, instruction);
- }
+ global_depth = TryVisitNodes(loop, it.Current(), global_depth, &visited_instructions);
}
}
- DCHECK(stack_.empty());
- map_.clear();
-
// Determine the loop's trip-count.
VisitControl(loop);
}
-void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) {
- const uint32_t d1 = ++global_depth_;
- map_.Put(instruction, NodeInfo(d1));
- stack_.push_back(instruction);
-
- // Visit all descendants.
- uint32_t low = d1;
- for (HInstruction* input : instruction->GetInputs()) {
- low = std::min(low, VisitDescendant(loop, input));
+size_t HInductionVarAnalysis::TryVisitNodes(
+ HLoopInformation* loop,
+ HInstruction* start_instruction,
+ size_t global_depth,
+ /*inout*/ ScopedArenaSafeMap<HInstruction*, NodeInfo>* visited_instructions) {
+ // This is recursion-free version of the SCC search algorithm. We have limited stack space,
+ // so recursion with the depth dependent on the input is undesirable as such depth is unlimited.
+ auto [it, inserted] =
+ visited_instructions->insert(std::make_pair(start_instruction, NodeInfo(global_depth + 1u)));
+ if (!inserted) {
+ return global_depth;
}
+ NodeInfo* start_info = &it->second;
+ ++global_depth;
+ DCHECK_EQ(global_depth, start_info->depth);
- // Lower or found SCC?
- if (low < d1) {
- map_.find(instruction)->second.depth = low;
- } else {
- scc_.clear();
- cycle_.clear();
+ ScopedArenaVector<StackEntry> stack(visited_instructions->get_allocator());
+ stack.push_back({start_instruction, start_info});
- // Pop the stack to build the SCC for classification.
- while (!stack_.empty()) {
- HInstruction* x = stack_.back();
- scc_.push_back(x);
- stack_.pop_back();
- map_.find(x)->second.done = true;
- if (x == instruction) {
- break;
+ size_t current_entry = 0u;
+ while (!stack.empty()) {
+ StackEntry& entry = stack[current_entry];
+
+ // Look for unvisited inputs (also known as "descentants").
+ bool visit_input = false;
+ auto inputs = entry.instruction->GetInputs();
+ while (entry.num_visited_inputs != inputs.size()) {
+ HInstruction* input = inputs[entry.num_visited_inputs];
+ ++entry.num_visited_inputs;
+ // If the definition is either outside the loop (loop invariant entry value)
+ // or assigned in inner loop (inner exit value), the input is not visited.
+ if (input->GetBlock()->GetLoopInformation() != loop) {
+ continue;
}
+ // Try visiting the input. If already visited, update `entry.low_depth`.
+ auto [input_it, input_inserted] =
+ visited_instructions->insert(std::make_pair(input, NodeInfo(global_depth + 1u)));
+ NodeInfo* input_info = &input_it->second;
+ if (input_inserted) {
+ // Push the input on the `stack` and visit it now.
+ ++global_depth;
+ DCHECK_EQ(global_depth, input_info->depth);
+ stack.push_back({input, input_info, current_entry});
+ current_entry = stack.size() - 1u;
+ visit_input = true;
+ break;
+ } else if (!input_info->done && input_info->depth < entry.low_depth) {
+ entry.low_depth = input_it->second.depth;
+ }
+ continue;
+ }
+ if (visit_input) {
+ continue; // Process the new top of the stack.
}
- // Type of induction.
- type_ = scc_[0]->GetType();
-
- // Classify the SCC.
- if (scc_.size() == 1 && !scc_[0]->IsLoopHeaderPhi()) {
- ClassifyTrivial(loop, scc_[0]);
+ // All inputs of the current node have been visited.
+ // Check if we have found an input below this entry on the stack.
+ DCHECK(!entry.node_info->done);
+ size_t previous_entry = entry.user_link;
+ if (entry.node_info->depth > entry.low_depth) {
+ DCHECK_LT(previous_entry, current_entry) << entry.node_info->depth << " " << entry.low_depth;
+ entry.node_info->depth = entry.low_depth;
+ if (stack[previous_entry].low_depth > entry.low_depth) {
+ stack[previous_entry].low_depth = entry.low_depth;
+ }
} else {
- ClassifyNonTrivial(loop);
+ // Classify the SCC we have just found.
+ ArrayRef<StackEntry> stack_tail = ArrayRef<StackEntry>(stack).SubArray(current_entry);
+ for (StackEntry& tail_entry : stack_tail) {
+ tail_entry.node_info->done = true;
+ }
+ if (current_entry + 1u == stack.size() && !entry.instruction->IsLoopHeaderPhi()) {
+ ClassifyTrivial(loop, entry.instruction);
+ } else {
+ ClassifyNonTrivial(loop, ArrayRef<const StackEntry>(stack_tail));
+ }
+ stack.erase(stack.begin() + current_entry, stack.end());
}
-
- scc_.clear();
- cycle_.clear();
+ current_entry = previous_entry;
}
+
+ return global_depth;
}
-uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) {
- // If the definition is either outside the loop (loop invariant entry value)
- // or assigned in inner loop (inner exit value), the traversal stops.
- HLoopInformation* otherLoop = instruction->GetBlock()->GetLoopInformation();
- if (otherLoop != loop) {
- return global_depth_;
+/**
+ * Since graph traversal may enter a SCC at any position, an initial representation may be rotated,
+ * along dependences, viz. any of (a, b, c, d), (d, a, b, c) (c, d, a, b), (b, c, d, a) assuming
+ * a chain of dependences (mutual independent items may occur in arbitrary order). For proper
+ * classification, the lexicographically first loop-phi is rotated to the front. We do that
+ * as we extract the SCC instructions.
+ */
+void HInductionVarAnalysis::ExtractScc(ArrayRef<const StackEntry> stack_tail,
+ ScopedArenaVector<HInstruction*>* scc) {
+ // Find very first loop-phi.
+ HInstruction* phi = nullptr;
+ size_t split_pos = 0;
+ const size_t size = stack_tail.size();
+ for (size_t i = 0; i != size; ++i) {
+ const StackEntry& entry = stack_tail[i];
+ HInstruction* instruction = entry.instruction;
+ if (instruction->IsLoopHeaderPhi()) {
+ // All loop Phis in SCC come from the same loop header.
+ HBasicBlock* block = instruction->GetBlock();
+ DCHECK(block->GetLoopInformation()->GetHeader() == block);
+ DCHECK(phi == nullptr || phi->GetBlock() == block);
+ if (phi == nullptr || block->GetPhis().FoundBefore(instruction, phi)) {
+ phi = instruction;
+ split_pos = i + 1u;
+ }
+ }
}
- // Inspect descendant node.
- if (!IsVisitedNode(instruction)) {
- VisitNode(loop, instruction);
- return map_.find(instruction)->second.depth;
- } else {
- auto it = map_.find(instruction);
- return it->second.done ? global_depth_ : it->second.depth;
+ // Extract SCC in two chunks.
+ DCHECK(scc->empty());
+ scc->reserve(size);
+ for (const StackEntry& entry : ReverseRange(stack_tail.SubArray(/*pos=*/ 0u, split_pos))) {
+ scc->push_back(entry.instruction);
}
+ for (const StackEntry& entry : ReverseRange(stack_tail.SubArray(/*pos=*/ split_pos))) {
+ scc->push_back(entry.instruction);
+ }
+ DCHECK_EQ(scc->size(), stack_tail.size());
}
void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
+ DataType::Type type = instruction->GetType();
InductionInfo* info = nullptr;
if (instruction->IsPhi()) {
info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 0);
} else if (instruction->IsAdd()) {
info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
- LookupInfo(loop, instruction->InputAt(1)), kAdd);
+ LookupInfo(loop, instruction->InputAt(1)),
+ kAdd,
+ type);
} else if (instruction->IsSub()) {
info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
- LookupInfo(loop, instruction->InputAt(1)), kSub);
+ LookupInfo(loop, instruction->InputAt(1)),
+ kSub,
+ type);
} else if (instruction->IsNeg()) {
- info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)));
+ info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)), type);
} else if (instruction->IsMul()) {
info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
- LookupInfo(loop, instruction->InputAt(1)));
+ LookupInfo(loop, instruction->InputAt(1)),
+ type);
} else if (instruction->IsShl()) {
HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr);
if (mulc != nullptr) {
info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
- LookupInfo(loop, mulc));
+ LookupInfo(loop, mulc),
+ type);
}
} else if (instruction->IsSelect()) {
info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 1);
@@ -390,19 +430,18 @@
}
}
-void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
- const size_t size = scc_.size();
+void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop,
+ ArrayRef<const StackEntry> stack_tail) {
+ const size_t size = stack_tail.size();
DCHECK_GE(size, 1u);
+ DataType::Type type = stack_tail.back().instruction->GetType();
- // Rotate proper loop-phi to front.
- if (size > 1) {
- ArenaVector<HInstruction*> other(
- graph_->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis));
- RotateEntryPhiFirst(loop, &scc_, &other);
- }
+ ScopedArenaAllocator local_allocator(graph_->GetArenaStack());
+ ScopedArenaVector<HInstruction*> scc(local_allocator.Adapter(kArenaAllocInductionVarAnalysis));
+ ExtractScc(ArrayRef<const StackEntry>(stack_tail), &scc);
// Analyze from loop-phi onwards.
- HInstruction* phi = scc_[0];
+ HInstruction* phi = scc[0];
if (!phi->IsLoopHeaderPhi()) {
return;
}
@@ -415,8 +454,8 @@
// Store interesting cycle in each loop phi.
for (size_t i = 0; i < size; i++) {
- if (scc_[i]->IsLoopHeaderPhi()) {
- AssignCycle(scc_[i]->AsPhi());
+ if (scc[i]->IsLoopHeaderPhi()) {
+ AssignCycle(scc[i]->AsPhi(), ArrayRef<HInstruction* const>(scc));
}
}
@@ -429,68 +468,83 @@
initial,
update,
/*fetch*/ nullptr,
- type_));
+ type));
}
return;
}
- // Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns
+ // Inspect remainder of the cycle that resides in `scc`. The `cycle` mapping assigns
// temporary meaning to its nodes, seeded from the phi instruction and back.
+ ScopedArenaSafeMap<HInstruction*, InductionInfo*> cycle(
+ std::less<HInstruction*>(), local_allocator.Adapter(kArenaAllocInductionVarAnalysis));
for (size_t i = 1; i < size; i++) {
- HInstruction* instruction = scc_[i];
+ HInstruction* instruction = scc[i];
InductionInfo* update = nullptr;
if (instruction->IsPhi()) {
- update = SolvePhiAllInputs(loop, phi, instruction);
+ update = SolvePhiAllInputs(loop, phi, instruction, cycle, type);
} else if (instruction->IsAdd()) {
- update = SolveAddSub(
- loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true);
+ update = SolveAddSub(loop,
+ phi,
+ instruction,
+ instruction->InputAt(0),
+ instruction->InputAt(1),
+ kAdd,
+ cycle,
+ type);
} else if (instruction->IsSub()) {
- update = SolveAddSub(
- loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true);
+ update = SolveAddSub(loop,
+ phi,
+ instruction,
+ instruction->InputAt(0),
+ instruction->InputAt(1),
+ kSub,
+ cycle,
+ type);
} else if (instruction->IsMul()) {
update = SolveOp(
- loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kMul);
+ loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kMul, type);
} else if (instruction->IsDiv()) {
update = SolveOp(
- loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kDiv);
+ loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kDiv, type);
} else if (instruction->IsRem()) {
update = SolveOp(
- loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kRem);
+ loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kRem, type);
} else if (instruction->IsShl()) {
HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr);
if (mulc != nullptr) {
- update = SolveOp(loop, phi, instruction, instruction->InputAt(0), mulc, kMul);
+ update = SolveOp(loop, phi, instruction, instruction->InputAt(0), mulc, kMul, type);
}
} else if (instruction->IsShr() || instruction->IsUShr()) {
HInstruction* divc = GetShiftConstant(loop, instruction, initial);
if (divc != nullptr) {
- update = SolveOp(loop, phi, instruction, instruction->InputAt(0), divc, kDiv);
+ update = SolveOp(loop, phi, instruction, instruction->InputAt(0), divc, kDiv, type);
}
} else if (instruction->IsXor()) {
update = SolveOp(
- loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kXor);
+ loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kXor, type);
} else if (instruction->IsEqual()) {
- update = SolveTest(loop, phi, instruction, 0);
+ update = SolveTest(loop, phi, instruction, /*opposite_value=*/ 0, type);
} else if (instruction->IsNotEqual()) {
- update = SolveTest(loop, phi, instruction, 1);
+ update = SolveTest(loop, phi, instruction, /*opposite_value=*/ 1, type);
} else if (instruction->IsSelect()) {
- update = SolvePhi(instruction, /*input_index*/ 0, /*adjust_input_size*/ 1); // acts like Phi
+ // Select acts like Phi.
+ update = SolvePhi(instruction, /*input_index=*/ 0, /*adjust_input_size=*/ 1, cycle);
} else if (instruction->IsTypeConversion()) {
- update = SolveConversion(loop, phi, instruction->AsTypeConversion());
+ update = SolveConversion(loop, phi, instruction->AsTypeConversion(), cycle, &type);
}
if (update == nullptr) {
return;
}
- cycle_.Put(instruction, update);
+ cycle.Put(instruction, update);
}
// Success if all internal links received the same temporary meaning.
- InductionInfo* induction = SolvePhi(phi, /*input_index*/ 1, /*adjust_input_size*/ 0);
+ InductionInfo* induction = SolvePhi(phi, /*input_index=*/ 1, /*adjust_input_size=*/ 0, cycle);
if (induction != nullptr) {
switch (induction->induction_class) {
case kInvariant:
// Construct combined stride of the linear induction.
- induction = CreateInduction(kLinear, kNop, induction, initial, /*fetch*/ nullptr, type_);
+ induction = CreateInduction(kLinear, kNop, induction, initial, /*fetch*/ nullptr, type);
FALLTHROUGH_INTENDED;
case kPolynomial:
case kGeometric:
@@ -499,7 +553,7 @@
// Statements are scanned in order.
AssignInfo(loop, phi, induction);
for (size_t i = 1; i < size; i++) {
- ClassifyTrivial(loop, scc_[i]);
+ ClassifyTrivial(loop, scc[i]);
}
break;
case kPeriodic:
@@ -507,8 +561,8 @@
// rotating each first element to the end. Lastly, phi is classified.
// Statements are scanned in reverse order.
for (size_t i = size - 1; i >= 1; i--) {
- AssignInfo(loop, scc_[i], induction);
- induction = RotatePeriodicInduction(induction->op_b, induction->op_a);
+ AssignInfo(loop, scc[i], induction);
+ induction = RotatePeriodicInduction(induction->op_b, induction->op_a, type);
}
AssignInfo(loop, phi, induction);
break;
@@ -520,7 +574,8 @@
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduction(
InductionInfo* induction,
- InductionInfo* last) {
+ InductionInfo* last,
+ DataType::Type type) {
// Rotates a periodic induction of the form
// (a, b, c, d, e)
// into
@@ -532,14 +587,14 @@
induction,
last,
/*fetch*/ nullptr,
- type_);
+ type);
}
return CreateInduction(kPeriodic,
kNop,
induction->op_a,
- RotatePeriodicInduction(induction->op_b, last),
+ RotatePeriodicInduction(induction->op_b, last, type),
/*fetch*/ nullptr,
- type_);
+ type);
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopInformation* loop,
@@ -561,7 +616,8 @@
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a,
InductionInfo* b,
- InductionOp op) {
+ InductionOp op,
+ DataType::Type type) {
// Transfer over an addition or subtraction: any invariant, linear, polynomial, geometric,
// wrap-around, or periodic can be combined with an invariant to yield a similar result.
// Two linear or two polynomial inputs can be combined too. Other combinations fail.
@@ -573,39 +629,40 @@
} else if ((a->induction_class == kLinear && b->induction_class == kLinear) ||
(a->induction_class == kPolynomial && b->induction_class == kPolynomial)) {
// Rule induc(a, b) + induc(a', b') -> induc(a + a', b + b').
- InductionInfo* new_a = TransferAddSub(a->op_a, b->op_a, op);
- InductionInfo* new_b = TransferAddSub(a->op_b, b->op_b, op);
- if (new_a != nullptr && new_b != nullptr) {
- return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_);
+ InductionInfo* new_a = TransferAddSub(a->op_a, b->op_a, op, type);
+ InductionInfo* new_b = TransferAddSub(a->op_b, b->op_b, op, type);
+ if (new_a != nullptr && new_b != nullptr) {
+ return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type);
}
} else if (a->induction_class == kInvariant) {
// Rule a + induc(a', b') -> induc(a', a + b') or induc(a + a', a + b').
InductionInfo* new_a = b->op_a;
- InductionInfo* new_b = TransferAddSub(a, b->op_b, op);
+ InductionInfo* new_b = TransferAddSub(a, b->op_b, op, type);
if (b->induction_class == kWrapAround || b->induction_class == kPeriodic) {
- new_a = TransferAddSub(a, new_a, op);
+ new_a = TransferAddSub(a, new_a, op, type);
} else if (op == kSub) { // Negation required.
- new_a = TransferNeg(new_a);
+ new_a = TransferNeg(new_a, type);
}
- if (new_a != nullptr && new_b != nullptr) {
- return CreateInduction(b->induction_class, b->operation, new_a, new_b, b->fetch, type_);
+ if (new_a != nullptr && new_b != nullptr) {
+ return CreateInduction(b->induction_class, b->operation, new_a, new_b, b->fetch, type);
}
} else if (b->induction_class == kInvariant) {
// Rule induc(a, b) + b' -> induc(a, b + b') or induc(a + b', b + b').
InductionInfo* new_a = a->op_a;
- InductionInfo* new_b = TransferAddSub(a->op_b, b, op);
+ InductionInfo* new_b = TransferAddSub(a->op_b, b, op, type);
if (a->induction_class == kWrapAround || a->induction_class == kPeriodic) {
- new_a = TransferAddSub(new_a, b, op);
+ new_a = TransferAddSub(new_a, b, op, type);
}
- if (new_a != nullptr && new_b != nullptr) {
- return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_);
+ if (new_a != nullptr && new_b != nullptr) {
+ return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type);
}
}
}
return nullptr;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) {
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a,
+ DataType::Type type) {
// Transfer over a unary negation: an invariant, linear, polynomial, geometric (mul),
// wrap-around, or periodic input yields a similar but negated induction as result.
if (a != nullptr) {
@@ -615,10 +672,10 @@
return CreateInvariantOp(kNeg, nullptr, a); // direct invariant
} else if (a->induction_class != kGeometric || a->operation == kMul) {
// Rule - induc(a, b) -> induc(-a, -b).
- InductionInfo* new_a = TransferNeg(a->op_a);
- InductionInfo* new_b = TransferNeg(a->op_b);
+ InductionInfo* new_a = TransferNeg(a->op_a, type);
+ InductionInfo* new_b = TransferNeg(a->op_b, type);
if (new_a != nullptr && new_b != nullptr) {
- return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_);
+ return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type);
}
}
}
@@ -626,7 +683,8 @@
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a,
- InductionInfo* b) {
+ InductionInfo* b,
+ DataType::Type type) {
// Transfer over a multiplication: any invariant, linear, polynomial, geometric (mul),
// wrap-around, or periodic can be multiplied with an invariant to yield a similar
// but multiplied result. Two non-invariant inputs cannot be multiplied, however.
@@ -638,18 +696,18 @@
} else if (a->induction_class == kInvariant && (b->induction_class != kGeometric ||
b->operation == kMul)) {
// Rule a * induc(a', b') -> induc(a * a', b * b').
- InductionInfo* new_a = TransferMul(a, b->op_a);
- InductionInfo* new_b = TransferMul(a, b->op_b);
+ InductionInfo* new_a = TransferMul(a, b->op_a, type);
+ InductionInfo* new_b = TransferMul(a, b->op_b, type);
if (new_a != nullptr && new_b != nullptr) {
- return CreateInduction(b->induction_class, b->operation, new_a, new_b, b->fetch, type_);
+ return CreateInduction(b->induction_class, b->operation, new_a, new_b, b->fetch, type);
}
} else if (b->induction_class == kInvariant && (a->induction_class != kGeometric ||
a->operation == kMul)) {
// Rule induc(a, b) * b' -> induc(a * b', b * b').
- InductionInfo* new_a = TransferMul(a->op_a, b);
- InductionInfo* new_b = TransferMul(a->op_b, b);
+ InductionInfo* new_a = TransferMul(a->op_a, b, type);
+ InductionInfo* new_b = TransferMul(a->op_b, b, type);
if (new_a != nullptr && new_b != nullptr) {
- return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_);
+ return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type);
}
}
}
@@ -672,17 +730,19 @@
return nullptr;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HInstruction* phi,
- size_t input_index,
- size_t adjust_input_size) {
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(
+ HInstruction* phi,
+ size_t input_index,
+ size_t adjust_input_size,
+ const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle) {
// Match all phi inputs from input_index onwards exactly.
HInputsRef inputs = phi->GetInputs();
DCHECK_LT(input_index, inputs.size());
- auto ita = cycle_.find(inputs[input_index]);
- if (ita != cycle_.end()) {
+ auto ita = cycle.find(inputs[input_index]);
+ if (ita != cycle.end()) {
for (size_t i = input_index + 1, n = inputs.size() - adjust_input_size; i < n; i++) {
- auto itb = cycle_.find(inputs[i]);
- if (itb == cycle_.end() ||
+ auto itb = cycle.find(inputs[i]);
+ if (itb == cycle.end() ||
!HInductionVarAnalysis::InductionEqual(ita->second, itb->second)) {
return nullptr;
}
@@ -695,9 +755,11 @@
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhiAllInputs(
HLoopInformation* loop,
HInstruction* entry_phi,
- HInstruction* phi) {
+ HInstruction* phi,
+ const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
+ DataType::Type type) {
// Match all phi inputs.
- InductionInfo* match = SolvePhi(phi, /*input_index*/ 0, /*adjust_input_size*/ 0);
+ InductionInfo* match = SolvePhi(phi, /*input_index=*/ 0, /*adjust_input_size=*/ 0, cycle);
if (match != nullptr) {
return match;
}
@@ -710,76 +772,84 @@
if (a != nullptr && a->induction_class == kInvariant) {
if (phi->InputAt(1) == entry_phi) {
InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
- return CreateInduction(kPeriodic, kNop, a, initial, /*fetch*/ nullptr, type_);
+ return CreateInduction(kPeriodic, kNop, a, initial, /*fetch*/ nullptr, type);
}
- InductionInfo* b = SolvePhi(phi, /*input_index*/ 1, /*adjust_input_size*/ 0);
+ InductionInfo* b = SolvePhi(phi, /*input_index=*/ 1, /*adjust_input_size=*/ 0, cycle);
if (b != nullptr && b->induction_class == kPeriodic) {
- return CreateInduction(kPeriodic, kNop, a, b, /*fetch*/ nullptr, type_);
+ return CreateInduction(kPeriodic, kNop, a, b, /*fetch*/ nullptr, type);
}
}
}
return nullptr;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop,
- HInstruction* entry_phi,
- HInstruction* instruction,
- HInstruction* x,
- HInstruction* y,
- InductionOp op,
- bool is_first_call) {
- // Solve within a cycle over an addition or subtraction.
- InductionInfo* b = LookupInfo(loop, y);
- if (b != nullptr) {
- if (b->induction_class == kInvariant) {
- // Adding or subtracting an invariant value, seeded from phi,
- // keeps adding to the stride of the linear induction.
- if (x == entry_phi) {
- 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 CreateInvariantOp(op, a, b);
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(
+ HLoopInformation* loop,
+ HInstruction* entry_phi,
+ HInstruction* instruction,
+ HInstruction* x,
+ HInstruction* y,
+ InductionOp op,
+ const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
+ DataType::Type type) {
+ auto main_solve_add_sub = [&]() -> HInductionVarAnalysis::InductionInfo* {
+ // Solve within a cycle over an addition or subtraction.
+ InductionInfo* b = LookupInfo(loop, y);
+ if (b != nullptr) {
+ if (b->induction_class == kInvariant) {
+ // Adding or subtracting an invariant value, seeded from phi,
+ // keeps adding to the stride of the linear induction.
+ if (x == entry_phi) {
+ 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 CreateInvariantOp(op, a, b);
+ }
+ }
+ } else if (b->induction_class == kLinear && b->type == type) {
+ // Solve within a tight cycle that adds a term that is already classified as a linear
+ // induction for a polynomial induction k = k + i (represented as sum over linear terms).
+ if (x == entry_phi &&
+ entry_phi->InputCount() == 2 &&
+ instruction == entry_phi->InputAt(1)) {
+ InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
+ InductionInfo* new_a = op == kAdd ? b : TransferNeg(b, type);
+ if (new_a != nullptr) {
+ return CreateInduction(kPolynomial, kNop, new_a, initial, /*fetch*/ nullptr, type);
+ }
}
}
- } else if (b->induction_class == kLinear && b->type == type_) {
- // Solve within a tight cycle that adds a term that is already classified as a linear
- // induction for a polynomial induction k = k + i (represented as sum over linear terms).
- if (x == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
- InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
- InductionInfo* new_a = op == kAdd ? b : TransferNeg(b);
- if (new_a != nullptr) {
- return CreateInduction(kPolynomial, kNop, new_a, initial, /*fetch*/ nullptr, type_);
+ }
+ return nullptr;
+ };
+ HInductionVarAnalysis::InductionInfo* result = main_solve_add_sub();
+ if (result == nullptr) {
+ // Try some alternatives before failing.
+ if (op == kAdd) {
+ // Try the other way around for an addition.
+ std::swap(x, y);
+ result = main_solve_add_sub();
+ } else if (op == kSub) {
+ // Solve within a tight cycle that is formed by exactly two instructions,
+ // one phi and one update, for a periodic idiom of the form k = c - k.
+ if (y == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
+ InductionInfo* a = LookupInfo(loop, x);
+ if (a != nullptr && a->induction_class == kInvariant) {
+ InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
+ result = CreateInduction(kPeriodic,
+ kNop,
+ CreateInvariantOp(kSub, a, initial),
+ initial,
+ /*fetch*/ nullptr,
+ type);
}
}
}
}
-
- // Try some alternatives before failing.
- if (op == kAdd) {
- // Try the other way around for an addition if considered for first time.
- if (is_first_call) {
- return SolveAddSub(loop, entry_phi, instruction, y, x, op, false);
- }
- } else if (op == kSub) {
- // Solve within a tight cycle that is formed by exactly two instructions,
- // one phi and one update, for a periodic idiom of the form k = c - k.
- if (y == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
- InductionInfo* a = LookupInfo(loop, x);
- if (a != nullptr && a->induction_class == kInvariant) {
- InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
- return CreateInduction(kPeriodic,
- kNop,
- CreateInvariantOp(kSub, a, initial),
- initial,
- /*fetch*/ nullptr,
- type_);
- }
- }
- }
- return nullptr;
+ return result;
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveOp(HLoopInformation* loop,
@@ -787,7 +857,8 @@
HInstruction* instruction,
HInstruction* x,
HInstruction* y,
- InductionOp op) {
+ InductionOp op,
+ DataType::Type type) {
// Solve within a tight cycle for a binary operation k = k op c or, for some op, k = c op k.
if (entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
InductionInfo* c = nullptr;
@@ -811,9 +882,9 @@
return CreateInduction(kGeometric,
op,
initial,
- CreateConstant(0, type_),
+ CreateConstant(0, type),
c->fetch,
- type_);
+ type);
}
break;
case kRem:
@@ -823,7 +894,7 @@
initial,
CreateInvariantOp(kRem, initial, c),
/*fetch*/ nullptr,
- type_);
+ type);
case kXor:
// Idiomatic XOR periodic induction.
return CreateInduction(kPeriodic,
@@ -831,7 +902,7 @@
CreateInvariantOp(kXor, initial, c),
initial,
/*fetch*/ nullptr,
- type_);
+ type);
default:
LOG(FATAL) << op;
UNREACHABLE();
@@ -844,15 +915,16 @@
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveTest(HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* instruction,
- int64_t opposite_value) {
+ int64_t opposite_value,
+ DataType::Type type) {
// Detect hidden XOR construction in x = (x == false) or x = (x != true).
int64_t value = -1;
HInstruction* x = instruction->InputAt(0);
HInstruction* y = instruction->InputAt(1);
if (IsExact(LookupInfo(loop, x), &value) && value == opposite_value) {
- return SolveOp(loop, entry_phi, instruction, graph_->GetIntConstant(1), y, kXor);
+ return SolveOp(loop, entry_phi, instruction, graph_->GetIntConstant(1), y, kXor, type);
} else if (IsExact(LookupInfo(loop, y), &value) && value == opposite_value) {
- return SolveOp(loop, entry_phi, instruction, x, graph_->GetIntConstant(1), kXor);
+ return SolveOp(loop, entry_phi, instruction, x, graph_->GetIntConstant(1), kXor, type);
}
return nullptr;
}
@@ -860,7 +932,9 @@
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveConversion(
HLoopInformation* loop,
HInstruction* entry_phi,
- HTypeConversion* conversion) {
+ HTypeConversion* conversion,
+ const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
+ /*inout*/ DataType::Type* type) {
DataType::Type from = conversion->GetInputType();
DataType::Type to = conversion->GetResultType();
// A narrowing conversion is allowed as *last* operation of the cycle of a linear induction
@@ -875,9 +949,9 @@
if (IsNarrowingIntegralConversion(from, to) &&
IsAtLeast(initial, &value) && value >= min &&
IsAtMost(initial, &value) && value <= max) {
- auto it = cycle_.find(conversion->GetInput());
- if (it != cycle_.end() && it->second->induction_class == kInvariant) {
- type_ = to;
+ auto it = cycle.find(conversion->GetInput());
+ if (it != cycle.end() && it->second->induction_class == kInvariant) {
+ *type = to;
return it->second;
}
}
@@ -1323,10 +1397,10 @@
return nullptr;
}
-void HInductionVarAnalysis::AssignCycle(HPhi* phi) {
+void HInductionVarAnalysis::AssignCycle(HPhi* phi, ArrayRef<HInstruction* const> scc) {
ArenaSet<HInstruction*>* set = &cycles_.Put(phi, ArenaSet<HInstruction*>(
graph_->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)))->second;
- for (HInstruction* i : scc_) {
+ for (HInstruction* i : scc) {
set->insert(i);
}
}