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);
}
}
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index a48aa90..616100b 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -19,6 +19,9 @@
#include <string>
+#include "base/arena_containers.h"
+#include "base/array_ref.h"
+#include "base/scoped_arena_containers.h"
#include "nodes.h"
#include "optimization.h"
@@ -42,11 +45,8 @@
static constexpr const char* kInductionPassName = "induction_var_analysis";
private:
- struct NodeInfo {
- explicit NodeInfo(uint32_t d) : depth(d), done(false) {}
- uint32_t depth;
- bool done;
- };
+ struct NodeInfo;
+ struct StackEntry;
enum InductionClass {
kInvariant,
@@ -118,9 +118,6 @@
DataType::Type type; // precision of operation
};
- bool IsVisitedNode(HInstruction* instruction) const {
- return map_.find(instruction) != map_.end();
- }
InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
@@ -153,47 +150,65 @@
// Methods for analysis.
void VisitLoop(HLoopInformation* loop);
- void VisitNode(HLoopInformation* loop, HInstruction* instruction);
- uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
+ size_t TryVisitNodes(HLoopInformation* loop,
+ HInstruction* start_instruction,
+ size_t global_depth,
+ /*inout*/ ScopedArenaSafeMap<HInstruction*, NodeInfo>* visited_instructions);
+ void ExtractScc(ArrayRef<const StackEntry> stack_tail, ScopedArenaVector<HInstruction*>* scc);
void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
- void ClassifyNonTrivial(HLoopInformation* loop);
- InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
+ void ClassifyNonTrivial(HLoopInformation* loop, ArrayRef<const StackEntry> stack_tail);
+ InductionInfo* RotatePeriodicInduction(InductionInfo* induction,
+ InductionInfo* last,
+ DataType::Type type);
// Transfer operations.
InductionInfo* TransferPhi(HLoopInformation* loop,
HInstruction* phi,
size_t input_index,
size_t adjust_input_size);
- InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
- InductionInfo* TransferNeg(InductionInfo* a);
- InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
+ InductionInfo* TransferAddSub(InductionInfo* a,
+ InductionInfo* b,
+ InductionOp op,
+ DataType::Type type);
+ InductionInfo* TransferNeg(InductionInfo* a, DataType::Type type);
+ InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b, DataType::Type type);
InductionInfo* TransferConversion(InductionInfo* a, DataType::Type from, DataType::Type to);
// Solvers.
- InductionInfo* SolvePhi(HInstruction* phi, size_t input_index, size_t adjust_input_size);
+ InductionInfo* SolvePhi(HInstruction* phi,
+ size_t input_index,
+ size_t adjust_input_size,
+ const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle);
InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
HInstruction* entry_phi,
- HInstruction* phi);
+ HInstruction* phi,
+ const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
+ DataType::Type type);
InductionInfo* SolveAddSub(HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* instruction,
HInstruction* x,
HInstruction* y,
InductionOp op,
- bool is_first_call); // possibly swaps x and y to try again
+ const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
+ DataType::Type type);
InductionInfo* SolveOp(HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* instruction,
HInstruction* x,
HInstruction* y,
- InductionOp op);
+ InductionOp op,
+ DataType::Type type);
InductionInfo* SolveTest(HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* instruction,
- int64_t oppositive_value);
+ int64_t opposite_value,
+ DataType::Type type);
InductionInfo* SolveConversion(HLoopInformation* loop,
HInstruction* entry_phi,
- HTypeConversion* conversion);
+ HTypeConversion* conversion,
+ const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
+ /*inout*/ DataType::Type* type);
//
// Loop trip count analysis methods.
@@ -241,7 +256,7 @@
HInstruction* GetShiftConstant(HLoopInformation* loop,
HInstruction* instruction,
InductionInfo* initial);
- void AssignCycle(HPhi* phi);
+ void AssignCycle(HPhi* phi, ArrayRef<HInstruction* const> scc);
ArenaSet<HInstruction*>* LookupCycle(HPhi* phi);
// Constants.
@@ -255,16 +270,6 @@
static std::string FetchToString(HInstruction* fetch);
static std::string InductionToString(InductionInfo* info);
- // TODO: fine tune the following data structures, only keep relevant data.
-
- // Temporary book-keeping during the analysis.
- uint32_t global_depth_;
- ArenaVector<HInstruction*> stack_;
- ArenaSafeMap<HInstruction*, NodeInfo> map_;
- ArenaVector<HInstruction*> scc_;
- ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
- DataType::Type type_;
-
/**
* Maintains the results of the analysis as a mapping from loops to a mapping from instructions
* to the induction information for that instruction in that loop.
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 23c86ce..9e298a5 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -2387,7 +2387,7 @@
}
bool HLoopOptimization::TrySetPhiReduction(HPhi* phi) {
- DCHECK(iset_->empty());
+ DCHECK(phi->IsLoopHeaderPhi());
// Only unclassified phi cycles are candidates for reductions.
if (induction_range_.IsClassified(phi)) {
return false;
@@ -2399,15 +2399,18 @@
HInstruction* reduction = inputs[1];
if (HasReductionFormat(reduction, phi)) {
HLoopInformation* loop_info = phi->GetBlock()->GetLoopInformation();
- uint32_t use_count = 0;
- bool single_use_inside_loop =
+ DCHECK(loop_info->Contains(*reduction->GetBlock()));
+ const bool single_use_inside_loop =
// Reduction update only used by phi.
reduction->GetUses().HasExactlyOneElement() &&
!reduction->HasEnvironmentUses() &&
// Reduction update is only use of phi inside the loop.
- IsOnlyUsedAfterLoop(loop_info, phi, /*collect_loop_uses*/ true, &use_count) &&
- iset_->size() == 1;
- iset_->clear(); // leave the way you found it
+ std::none_of(phi->GetUses().begin(),
+ phi->GetUses().end(),
+ [loop_info, reduction](const HUseListNode<HInstruction*>& use) {
+ HInstruction* user = use.GetUser();
+ return user != reduction && loop_info->Contains(*user->GetBlock());
+ });
if (single_use_inside_loop) {
// Link reduction back, and start recording feed value.
reductions_->Put(reduction, phi);
@@ -2497,8 +2500,7 @@
for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
HInstruction* user = use.GetUser();
if (iset_->find(user) == iset_->end()) { // not excluded?
- HLoopInformation* other_loop_info = user->GetBlock()->GetLoopInformation();
- if (other_loop_info != nullptr && other_loop_info->IsIn(*loop_info)) {
+ if (loop_info->Contains(*user->GetBlock())) {
// If collect_loop_uses is set, simply keep adding those uses to the set.
// Otherwise, reject uses inside the loop that were not already in the set.
if (collect_loop_uses) {
diff --git a/libartbase/base/safe_map.h b/libartbase/base/safe_map.h
index 9419860..0d7a8c1 100644
--- a/libartbase/base/safe_map.h
+++ b/libartbase/base/safe_map.h
@@ -81,6 +81,7 @@
node_type extract(const_iterator pos) { return map_.extract(pos); }
node_type extract(const key_type& k) { return map_.extract(k); }
+ std::pair<iterator, bool> insert(value_type&& value) { return map_.insert(std::move(value)); }
insert_return_type insert(node_type&& node) { return map_.insert(std::move(node)); }
insert_return_type insert(const_iterator hint, node_type&& node) {
return map_.insert(hint, std::move(node));