Rewrite topological sort order and improve GVN.

Rewrite the topological sort order to include a full loop
before the blocks that go after the loop. Add a new iterator
class LoopRepeatingTopologicalSortIterator that differs from
the RepeatingTopologicalSortIterator by repeating only loops
and repeating them early. It returns to the loop head if the
head needs recalculation when we reach the end of the loop.

In GVN, use the new loop-repeating topological sort iterator
and for a loop head merge only the preceding blocks' LVNs
if we're not currently recalculating this loop.

Also fix LocalValueNumbering::InPlaceIntersectMaps() which
was keeping only the last element of the intersection, avoid
some unnecessary processing during LVN merge and add some
missing braces to MIRGraph::InferTypeAndSize().

Bug: 16398693
Change-Id: I4e10d4acb626a5b8a28ec0de106a7b37f9cbca32

1 files changed, 44 insertions, 44 deletions

diff --git a/compiler/dex/global_value_numbering.cc b/compiler/dex/global_value_numbering.cc
index 614e826..d86be4e 100644
--- a/compiler/dex/global_value_numbering.cc
+++ b/compiler/dex/global_value_numbering.cc
@@ -22,8 +22,10 @@ namespace art {
 
 GlobalValueNumbering::GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator)
     : cu_(cu),
+      mir_graph_(cu->mir_graph.get()),
       allocator_(allocator),
-      repeat_count_(0u),
+      bbs_processed_(0u),
+      max_bbs_to_process_(kMaxBbsToProcessMultiplyFactor * mir_graph_->GetNumReachableBlocks()),
       last_value_(0u),
       modifications_allowed_(false),
       global_value_map_(std::less<uint64_t>(), allocator->Adapter()),
@@ -32,10 +34,9 @@ GlobalValueNumbering::GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAlloc
       array_location_map_(ArrayLocationComparator(), allocator->Adapter()),
       array_location_reverse_map_(allocator->Adapter()),
       ref_set_map_(std::less<ValueNameSet>(), allocator->Adapter()),
-      lvns_(cu_->mir_graph->GetNumBlocks(), nullptr, allocator->Adapter()),
+      lvns_(mir_graph_->GetNumBlocks(), nullptr, allocator->Adapter()),
       work_lvn_(nullptr),
       merge_lvns_(allocator->Adapter()) {
-  cu_->mir_graph->ClearAllVisitedFlags();
 }
 
 GlobalValueNumbering::~GlobalValueNumbering() {
@@ -46,21 +47,15 @@ LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb) {
   if (UNLIKELY(!Good())) {
     return nullptr;
   }
-  if (bb->data_flow_info == nullptr) {
+  if (UNLIKELY(bb->data_flow_info == nullptr)) {
     return nullptr;
   }
-  if (bb->block_type == kEntryBlock) {
-    repeat_count_ += 1u;
-    if (repeat_count_ > kMaxRepeatCount) {
-      last_value_ = kNoValue;  // Make bad.
-      return nullptr;
-    }
-  }
-  if (bb->block_type == kExitBlock) {
+  if (UNLIKELY(bb->block_type == kExitBlock)) {
     DCHECK(bb->first_mir_insn == nullptr);
     return nullptr;
   }
-  if (bb->visited) {
+  if (UNLIKELY(bbs_processed_ == max_bbs_to_process_)) {
+    last_value_ = kNoValue;  // Make bad.
     return nullptr;
   }
   DCHECK(work_lvn_.get() == nullptr);
@@ -72,13 +67,34 @@ LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb) {
       work_lvn_->SetSRegNullChecked(this_reg);
     }
   } else {
-    // Merge all incoming arcs.
     // To avoid repeated allocation on the ArenaStack, reuse a single vector kept as a member.
     DCHECK(merge_lvns_.empty());
+    // If we're running the full GVN, the RepeatingTopologicalSortIterator keeps the loop
+    // head stack in the MIRGraph up to date and for a loop head we need to check whether
+    // we're making the initial computation and need to merge only preceding blocks in the
+    // topological order, or we're recalculating a loop head and need to merge all incoming
+    // LVNs. When we're not at a loop head (including having an empty loop head stack) all
+    // predecessors should be preceding blocks and we shall merge all of them anyway.
+    //
+    // If we're running the modification phase of the full GVN, the loop head stack will be
+    // empty and we need to merge all incoming LVNs. If we're running just a simple LVN,
+    // the loop head stack will also be empty and there will be nothing to merge anyway.
+    bool use_all_predecessors = true;
+    uint16_t loop_head_idx = 0u;  // Used only if !use_all_predecessors.
+    if (mir_graph_->GetTopologicalSortOrderLoopHeadStack()->Size() != 0) {
+      // Full GVN inside a loop, see if we're at the loop head for the first time.
+      auto top = mir_graph_->GetTopologicalSortOrderLoopHeadStack()->Peek();
+      loop_head_idx = top.first;
+      bool recalculating = top.second;
+      use_all_predecessors = recalculating ||
+          loop_head_idx != mir_graph_->GetTopologicalSortOrderIndexes()->Get(bb->id);
+    }
     GrowableArray<BasicBlockId>::Iterator iter(bb->predecessors);
-    for (BasicBlock* pred_bb = cu_->mir_graph->GetBasicBlock(iter.Next());
-         pred_bb != nullptr; pred_bb = cu_->mir_graph->GetBasicBlock(iter.Next())) {
-      if (lvns_[pred_bb->id] != nullptr) {
+    for (BasicBlock* pred_bb = mir_graph_->GetBasicBlock(iter.Next());
+         pred_bb != nullptr; pred_bb = mir_graph_->GetBasicBlock(iter.Next())) {
+      if (lvns_[pred_bb->id] != nullptr &&
+          (use_all_predecessors ||
+              mir_graph_->GetTopologicalSortOrderIndexes()->Get(pred_bb->id) < loop_head_idx)) {
         merge_lvns_.push_back(lvns_[pred_bb->id]);
       }
     }
@@ -87,19 +103,22 @@ LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb) {
     if (bb->catch_entry) {
       merge_type = LocalValueNumbering::kCatchMerge;
     } else if (bb->last_mir_insn != nullptr &&
-        (bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN ||
+        (bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN_VOID ||
+         bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN ||
          bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN_OBJECT ||
          bb->last_mir_insn->dalvikInsn.opcode == Instruction::RETURN_WIDE) &&
         (bb->first_mir_insn == bb->last_mir_insn ||
-         (bb->first_mir_insn->next == bb->last_mir_insn &&
-          static_cast<int>(bb->first_mir_insn->dalvikInsn.opcode) == kMirOpPhi))) {
+         (static_cast<int>(bb->first_mir_insn->dalvikInsn.opcode) == kMirOpPhi &&
+          (bb->first_mir_insn->next == bb->last_mir_insn ||
+           (static_cast<int>(bb->first_mir_insn->next->dalvikInsn.opcode) == kMirOpPhi &&
+            bb->first_mir_insn->next->next == bb->last_mir_insn))))) {
       merge_type = LocalValueNumbering::kReturnMerge;
     }
     // At least one predecessor must have been processed before this bb.
     CHECK(!merge_lvns_.empty());
     if (merge_lvns_.size() == 1u) {
       work_lvn_->MergeOne(*merge_lvns_[0], merge_type);
-      BasicBlock* pred_bb = cu_->mir_graph->GetBasicBlock(merge_lvns_[0]->Id());
+      BasicBlock* pred_bb = mir_graph_->GetBasicBlock(merge_lvns_[0]->Id());
       if (HasNullCheckLastInsn(pred_bb, bb->id)) {
         work_lvn_->SetSRegNullChecked(pred_bb->last_mir_insn->ssa_rep->uses[0]);
       }
@@ -112,32 +131,13 @@ LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb) {
 
 bool GlobalValueNumbering::FinishBasicBlock(BasicBlock* bb) {
   DCHECK(work_lvn_ != nullptr);
-  DCHECK(bb->id == work_lvn_->Id());
+  DCHECK_EQ(bb->id, work_lvn_->Id());
+  ++bbs_processed_;
   merge_lvns_.clear();
 
-  bool change = false;
-  // Look for a branch to self or an already processed child.
-  // (No need to repeat the LVN if all children are processed later.)
-  ChildBlockIterator iter(bb, cu_->mir_graph.get());
-  for (BasicBlock* child = iter.Next(); child != nullptr; child = iter.Next()) {
-    if (child == bb || lvns_[child->id] != nullptr) {
-      // If we found an already processed child, check if the LVN actually differs.
-      change = (lvns_[bb->id] == nullptr || !lvns_[bb->id]->Equals(*work_lvn_));
-      break;
-    }
-  }
-
   std::unique_ptr<const LocalValueNumbering> old_lvn(lvns_[bb->id]);
   lvns_[bb->id] = work_lvn_.release();
-
-  bb->visited = true;
-  if (change) {
-    ChildBlockIterator iter(bb, cu_->mir_graph.get());
-    for (BasicBlock* child = iter.Next(); child != nullptr; child = iter.Next()) {
-      child->visited = false;
-    }
-  }
-  return change;
+  return (old_lvn == nullptr) || !old_lvn->Equals(*lvns_[bb->id]);
 }
 
 uint16_t GlobalValueNumbering::GetFieldId(const MirFieldInfo& field_info, uint16_t type) {
@@ -188,7 +188,7 @@ bool GlobalValueNumbering::NullCheckedInAllPredecessors(
     uint16_t value_name = merge_names[i];
     if (!pred_lvn->IsValueNullChecked(value_name)) {
       // Check if the predecessor has an IF_EQZ/IF_NEZ as the last insn.
-      const BasicBlock* pred_bb = cu_->mir_graph->GetBasicBlock(pred_lvn->Id());
+      const BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_lvn->Id());
       if (!HasNullCheckLastInsn(pred_bb, work_lvn_->Id())) {
         return false;
       }