[turbofan] Don't introduce additional computation when hoisting out of loops.

src/compiler/scheduler.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/scheduler.h"
 
 #include "src/bit-vector.h"
 #include "src/compiler/common-operator.h"
 #include "src/compiler/control-equivalence.h"
 #include "src/compiler/graph.h"
@@ skipping 569 matching lines @@
 class SpecialRPONumberer : public ZoneObject {
  public:
   SpecialRPONumberer(Zone* zone, Schedule* schedule)
       : zone_(zone),
         schedule_(schedule),
         order_(NULL),
         beyond_end_(NULL),
         loops_(zone),
         backedges_(zone),
         stack_(zone),
-        previous_block_count_(0) {}
+        previous_block_count_(0),
+        empty_(0, zone) {}
 
   // Computes the special reverse-post-order for the main control flow graph,
   // that is for the graph spanned between the schedule's start and end blocks.
   void ComputeSpecialRPO() {
     DCHECK(schedule_->end()->SuccessorCount() == 0);
     DCHECK(!order_);  // Main order does not exist yet.
     ComputeAndInsertSpecialRPO(schedule_->start(), schedule_->end());
   }
 
   // Computes the special reverse-post-order for a partial control flow graph,
@@ skipping 16 matching lines @@
   }
 
   // Print and verify the special reverse-post-order.
   void PrintAndVerifySpecialRPO() {
 #if DEBUG
     if (FLAG_trace_turbo_scheduler) PrintRPO();
     VerifySpecialRPO();
 #endif
   }
 
+  const ZoneList<BasicBlock*>& GetOutgoingBlocks(BasicBlock* block) {
+    if (HasLoopNumber(block)) {
+      LoopInfo const& loop = loops_[GetLoopNumber(block)];
+      if (loop.outgoing) return *loop.outgoing;
+    }
+    return empty_;
+  }
+
  private:
   typedef std::pair<BasicBlock*, size_t> Backedge;
 
   // Numbering for BasicBlock::rpo_number for this block traversal:
   static const int kBlockOnStack = -2;
   static const int kBlockVisited1 = -3;
   static const int kBlockVisited2 = -4;
   static const int kBlockUnvisited1 = -1;
   static const int kBlockUnvisited2 = kBlockVisited1;
 
@@ skipping 402 matching lines @@
 #endif  // DEBUG
 
   Zone* zone_;
   Schedule* schedule_;
   BasicBlock* order_;
   BasicBlock* beyond_end_;
   ZoneVector<LoopInfo> loops_;
   ZoneVector<Backedge> backedges_;
   ZoneVector<SpecialRPOStackFrame> stack_;
   size_t previous_block_count_;
+  ZoneList<BasicBlock*> const empty_;
 };
 
 
 BasicBlockVector* Scheduler::ComputeSpecialRPO(Zone* zone, Schedule* schedule) {
   SpecialRPONumberer numberer(zone, schedule);
   numberer.ComputeSpecialRPO();
   numberer.SerializeRPOIntoSchedule();
   numberer.PrintAndVerifySpecialRPO();
   return schedule->rpo_order();
 }
@@ skipping 280 matching lines @@
     // The schedule early block dominates the schedule late block.
     BasicBlock* min_block = scheduler_->GetData(node)->minimum_block_;
     DCHECK_EQ(min_block, BasicBlock::GetCommonDominator(block, min_block));
     Trace("Schedule late of #%d:%s is B%d at loop depth %d, minimum = B%d\n",
           node->id(), node->op()->mnemonic(), block->id().ToInt(),
           block->loop_depth(), min_block->id().ToInt());
 
     // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
     // into enclosing loop pre-headers until they would preceed their schedule
     // early position.
-    BasicBlock* hoist_block = GetPreHeader(block);
+    BasicBlock* hoist_block = GetHoistBlock(block);
     if (hoist_block &&
         hoist_block->dominator_depth() >= min_block->dominator_depth()) {
       do {
         Trace("  hoisting #%d:%s to block B%d\n", node->id(),
               node->op()->mnemonic(), hoist_block->id().ToInt());
         DCHECK_LT(hoist_block->loop_depth(), block->loop_depth());
         block = hoist_block;
-        hoist_block = GetPreHeader(hoist_block);
+        hoist_block = GetHoistBlock(hoist_block);
       } while (hoist_block &&
                hoist_block->dominator_depth() >= min_block->dominator_depth());
     } else if (scheduler_->flags_ & Scheduler::kSplitNodes) {
       // Split the {node} if beneficial and return the new {block} for it.
       block = SplitNode(block, node);
     }
 
     // Schedule the node or a floating control structure.
     if (IrOpcode::IsMergeOpcode(node->opcode())) {
       ScheduleFloatingControl(block, node);
@@ skipping 90 matching lines @@
           Trace("  cloning #%d:%s for B%d\n", use_node->id(),
                 use_node->op()->mnemonic(), use_block->id().ToInt());
           scheduler_->schedule_queue_.push(use_node);
         }
       }
       edge.UpdateTo(use_node);
     }
     return block;
   }
 
-  BasicBlock* GetPreHeader(BasicBlock* block) {
-    if (block->IsLoopHeader()) {
-      return block->dominator();
-    } else if (block->loop_header() != NULL) {
-      return block->loop_header()->dominator();
-    } else {
-      return NULL;
+  BasicBlock* GetHoistBlock(BasicBlock* block) {
+    if (block->IsLoopHeader()) return block->dominator();
+    // We have to check to make sure that the {block} dominates all
+    // of the outgoing blocks.  If it doesn't, then there is a path
+    // out of the loop which does not execute this {block}, so we
+    // can't hoist operations from this {block} out of the loop, as
+    // that would introduce additional computations.
+    if (BasicBlock* header_block = block->loop_header()) {
+      for (BasicBlock* outgoing_block :
+           scheduler_->special_rpo_->GetOutgoingBlocks(header_block)) {
+        if (BasicBlock::GetCommonDominator(block, outgoing_block) != block) {
+          return nullptr;
+        }
+      }
+      return header_block->dominator();
     }
+    return nullptr;
   }
 
   BasicBlock* GetCommonDominatorOfUses(Node* node) {
     BasicBlock* block = nullptr;
     for (Edge edge : node->use_edges()) {
       BasicBlock* use_block = GetBlockForUse(edge);
       block = block == NULL ? use_block : use_block == NULL
                                               ? block
                                               : BasicBlock::GetCommonDominator(
                                                     block, use_block);
@@ skipping 174 matching lines @@
   for (Node* const node : *nodes) {
     schedule_->SetBlockForNode(to, node);
     scheduled_nodes_[to->id().ToSize()].push_back(node);
   }
   nodes->clear();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8