runtime/vm/compiler/backend/block_scheduler.cc - sdk.git - Git at Google

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.

 #include "vm/compiler/backend/block_scheduler.h"

 #include "vm/allocation.h"
 #include "vm/code_patcher.h"
 #include "vm/compiler/backend/flow_graph.h"
 #include "vm/compiler/jit/compiler.h"

 namespace dart {

 static intptr_t GetEdgeCount(const Array& edge_counters, intptr_t edge_id) {
   if (!FLAG_reorder_basic_blocks) {
     // Assume everything was visited once.
     return 1;
   }
   return Smi::Value(Smi::RawCast(edge_counters.At(edge_id)));
 }

 // There is an edge from instruction->successor.  Set its weight (edge count
 // per function entry).
 static void SetEdgeWeight(BlockEntryInstr* block,
                           BlockEntryInstr* successor,
                           const Array& edge_counters,
                           intptr_t entry_count) {
   ASSERT(entry_count != 0);
   if (auto target = successor->AsTargetEntry()) {
     // If this block ends in a goto, the edge count of this edge is the same
     // as the count on the single outgoing edge. This is true as long as the
     // block does not throw an exception.
     intptr_t count = GetEdgeCount(edge_counters, target->preorder_number());
     if (count >= 0) {
       double weight =
           static_cast<double>(count) / static_cast<double>(entry_count);
       target->set_edge_weight(weight);
     }
   } else if (auto jump = block->last_instruction()->AsGoto()) {
     intptr_t count = GetEdgeCount(edge_counters, block->preorder_number());
     if (count >= 0) {
       double weight =
           static_cast<double>(count) / static_cast<double>(entry_count);
       jump->set_edge_weight(weight);
     }
   }
 }

 void BlockScheduler::AssignEdgeWeights(FlowGraph* flow_graph) {
   if (!FLAG_reorder_basic_blocks) {
     return;
   }
   if (CompilerState::Current().is_aot()) {
     return;
   }

   const Function& function = flow_graph->parsed_function().function();
   const Array& ic_data_array =
       Array::Handle(flow_graph->zone(), function.ic_data_array());
   if (ic_data_array.IsNull()) {
     DEBUG_ASSERT(IsolateGroup::Current()->HasAttemptedReload() ||
                  function.ForceOptimize());
     return;
   }
   Array& edge_counters = Array::Handle();
   edge_counters ^=
       ic_data_array.At(Function::ICDataArrayIndices::kEdgeCounters);
   if (edge_counters.IsNull()) {
     return;
   }

   auto graph_entry = flow_graph->graph_entry();
   BlockEntryInstr* entry = graph_entry->normal_entry();
   if (entry == nullptr) {
     entry = graph_entry->osr_entry();
     ASSERT(entry != nullptr);
   }
   const intptr_t entry_count =
       GetEdgeCount(edge_counters, entry->preorder_number());
   graph_entry->set_entry_count(entry_count);
   if (entry_count == 0) {
     return;  // Nothing to do.
   }

   for (BlockIterator it = flow_graph->reverse_postorder_iterator(); !it.Done();
        it.Advance()) {
     BlockEntryInstr* block = it.Current();
     Instruction* last = block->last_instruction();
     for (intptr_t i = 0; i < last->SuccessorCount(); ++i) {
       BlockEntryInstr* succ = last->SuccessorAt(i);
       SetEdgeWeight(block, succ, edge_counters, entry_count);
     }
   }
 }

 // A weighted control-flow graph edge.
 struct Edge {
   Edge(BlockEntryInstr* source, BlockEntryInstr* target, double weight)
       : source(source), target(target), weight(weight) {}

   static int LowestWeightFirst(const Edge* a, const Edge* b);

   BlockEntryInstr* source;
   BlockEntryInstr* target;
   double weight;
 };

 // A linked list node in a chain of blocks.
 struct Link : public ZoneAllocated {
   Link(BlockEntryInstr* block, Link* next) : block(block), next(next) {}

   BlockEntryInstr* block;
   Link* next;
 };

 // A chain of blocks with first and last pointers for fast concatenation and
 // a length to support adding a shorter chain's links to a longer chain.
 struct Chain : public ZoneAllocated {
   explicit Chain(BlockEntryInstr* block)
       : first(new Link(block, nullptr)), last(first), length(1) {}

   Link* first;
   Link* last;
   intptr_t length;
 };

 int Edge::LowestWeightFirst(const Edge* a, const Edge* b) {
   if (a->weight < b->weight) {
     return -1;
   }
   return (a->weight > b->weight) ? 1 : 0;
 }

 // Combine two chains by adding the shorter chain's links to the longer
 // chain.
 static void Union(GrowableArray<Chain*>* chains,
                   Chain* source_chain,
                   Chain* target_chain) {
   if (source_chain->length < target_chain->length) {
     for (Link* link = source_chain->first; link != nullptr; link = link->next) {
       (*chains)[link->block->postorder_number()] = target_chain;
     }
     // Link the chains.
     source_chain->last->next = target_chain->first;
     // Update the state of the longer chain.
     target_chain->first = source_chain->first;
     target_chain->length += source_chain->length;
   } else {
     for (Link* link = target_chain->first; link != nullptr; link = link->next) {
       (*chains)[link->block->postorder_number()] = source_chain;
     }
     source_chain->last->next = target_chain->first;
     source_chain->last = target_chain->last;
     source_chain->length += target_chain->length;
   }
 }

 void BlockScheduler::ReorderBlocks(FlowGraph* flow_graph) {
   if (!flow_graph->should_reorder_blocks()) {
     return;
   }

   if (CompilerState::Current().is_aot()) {
     ReorderBlocksAOT(flow_graph);
   } else {
     ReorderBlocksJIT(flow_graph);
   }
 }

 void BlockScheduler::ReorderBlocksJIT(FlowGraph* flow_graph) {
   // Add every block to a chain of length 1 and compute a list of edges
   // sorted by weight.
   intptr_t block_count = flow_graph->preorder().length();
   GrowableArray<Edge> edges(2 * block_count);

   // A map from a block's postorder number to the chain it is in.  Used to
   // implement a simple (ordered) union-find data structure.  Chains are
   // stored by pointer so that they are aliased (mutating one mutates all
   // shared ones).  Find(n) is simply chains[n].
   GrowableArray<Chain*> chains(block_count);

   for (BlockIterator it = flow_graph->postorder_iterator(); !it.Done();
        it.Advance()) {
     BlockEntryInstr* block = it.Current();
     chains.Add(new Chain(block));

     Instruction* last = block->last_instruction();
     for (intptr_t i = 0; i < last->SuccessorCount(); ++i) {
       BlockEntryInstr* succ = last->SuccessorAt(i);
       double weight = 0.0;
       if (succ->IsTargetEntry()) {
         weight = succ->AsTargetEntry()->edge_weight();
       } else if (last->IsGoto()) {
         weight = last->AsGoto()->edge_weight();
       }
       edges.Add(Edge(block, succ, weight));
     }
   }

   // Handle each edge in turn.  The edges are sorted by increasing weight.
   edges.Sort(Edge::LowestWeightFirst);
   while (!edges.is_empty()) {
     Edge edge = edges.RemoveLast();
     Chain* source_chain = chains[edge.source->postorder_number()];
     Chain* target_chain = chains[edge.target->postorder_number()];

     // If the source and target are already in the same chain or if the
     // edge's source or target is not exposed at the appropriate end of a
     // chain skip this edge.
     if ((source_chain == target_chain) ||
         (edge.source != source_chain->last->block) ||
         (edge.target != target_chain->first->block)) {
       continue;
     }

     Union(&chains, source_chain, target_chain);
   }

   // Ensure the checked entry remains first to avoid needing another offset on
   // Instructions, compare Code::EntryPointOf.
   GraphEntryInstr* graph_entry = flow_graph->graph_entry();
   flow_graph->CodegenBlockOrder()->Add(graph_entry);
   FunctionEntryInstr* checked_entry = graph_entry->normal_entry();
   if (checked_entry != nullptr) {
     flow_graph->CodegenBlockOrder()->Add(checked_entry);
   }
   // Build a new block order.  Emit each chain when its first block occurs
   // in the original reverse postorder ordering.
   // Note: the resulting order is not topologically sorted and can't be
   // used a replacement for reverse_postorder in algorithms that expect
   // topological sort.
   for (intptr_t i = block_count - 1; i >= 0; --i) {
     if (chains[i]->first->block == flow_graph->postorder()[i]) {
       for (Link* link = chains[i]->first; link != nullptr; link = link->next) {
         if ((link->block != checked_entry) && (link->block != graph_entry)) {
           flow_graph->CodegenBlockOrder()->Add(link->block);
         }
       }
     }
   }
 }

 // AOT block order is based on reverse post order but with two changes:
 //
 // - Blocks which always throw and their direct predecessors are considered
 // *cold* and moved to the end of the order.
 // - Blocks which belong to the same loop are kept together (where possible)
 // and not interspersed with other blocks.
 //
 namespace {
 class AOTBlockScheduler {
  public:
   explicit AOTBlockScheduler(FlowGraph* flow_graph)
       : flow_graph_(flow_graph),
         block_count_(flow_graph->reverse_postorder().length()),
         marks_(block_count_),
         postorder_(block_count_),
         cold_postorder_(10) {
     marks_.FillWith(0, 0, block_count_);
   }

   void ComputeOrder() {
     ComputeOrderImpl();

     const auto codegen_order = flow_graph_->CodegenBlockOrder();
     for (intptr_t i = postorder_.length() - 1; i >= 0; --i) {
       codegen_order->Add(postorder_[i]);
     }
     for (intptr_t i = cold_postorder_.length() - 1; i >= 0; --i) {
       codegen_order->Add(cold_postorder_[i]);
     }
   }

  private:
   // The algorithm below is almost identical to |FlowGraph::DiscoverBlocks|, but
   // with few tweaks which guarantee improved scheduling for cold code and
   // loops.
   void ComputeOrderImpl() {
     PushBlock(flow_graph_->graph_entry());
     while (!block_stack_.is_empty()) {
       BlockEntryInstr* block = block_stack_.Last();
       auto& marks = MarksOf(block);
       auto last = block->last_instruction();
       const auto successor_count = last->SuccessorCount();

       if ((marks & kVisitedMark) == 0) {
         marks |= kVisitedMark;

         if (last->IsThrow() || last->IsReThrow() || last->IsStop()) {
           marks |= kColdMark;
         } else {
           // When visiting a block inside a loop with two successors
           // push the successor with lesser nesting *last*, so that it is
           // visited first. This helps to keep blocks which belong to the
           // same loop together.
           //
           // This is the main difference from |DiscoverBlocks| which always
           // visits successors in reverse order.
           if (successor_count == 2 && block->loop_info() != nullptr) {
             auto succ0 = last->SuccessorAt(0);
             auto succ1 = last->SuccessorAt(1);

             if (succ0->NestingDepth() < succ1->NestingDepth()) {
               PushBlock(succ1);
               PushBlock(succ0);
             } else {
               PushBlock(succ0);
               PushBlock(succ1);
             }
           } else {
             for (intptr_t i = 0; i < successor_count; i++) {
               PushBlock(last->SuccessorAt(i));
             }
           }

           // We have pushed some successors to the stack. Process them first.
           if (block_stack_.Last() != block) {
             continue;
           }

           // No successors added, fall through.
         }
       }

       // All successors of this block were visited, which means we are
       // done with this block.
       block_stack_.RemoveLast();

       // Propagate cold mark from the successors: if all successors are
       // cold then this block is cold as well.
       if (successor_count > 0) {
         uint8_t cold_mark = kColdMark;
         for (intptr_t i = 0; i < successor_count; i++) {
           cold_mark &= MarksOf(last->SuccessorAt(i));
         }
         marks |= cold_mark;
       }

       if ((marks & (kColdMark | kPinnedMark)) == kColdMark) {
         // This block is cold and not pinned: move it to cold section at
         // the end.
         cold_postorder_.Add(block);
       } else {
         postorder_.Add(block);
       }
     }
   }

   // The block was added to the stack.
   static constexpr uint8_t kSeenMark = 1 << 0;
   // The block was visited and all of its successors were added to the stack.
   static constexpr uint8_t kVisitedMark = 1 << 1;
   // The block terminates with unconditional throw or rethrow.
   static constexpr uint8_t kColdMark = 1 << 2;
   // The block should not move to cold section.
   static constexpr uint8_t kPinnedMark = 1 << 3;

   uint8_t& MarksOf(BlockEntryInstr* block) {
     return marks_[block->preorder_number()];
   }

   void PushBlock(BlockEntryInstr* block) {
     auto& marks = MarksOf(block);
     if ((marks & kSeenMark) == 0) {
       marks |= kSeenMark;
       block_stack_.Add(block);

       if (block->IsFunctionEntry() || block->IsGraphEntry()) {
         marks |= kPinnedMark;
       }
     }
   }

   FlowGraph* const flow_graph_;
   const intptr_t block_count_;

   // Block marks for each block indexed by block preorder number.
   GrowableArray<uint8_t> marks_;

   // Stack of blocks to process.
   GrowableArray<BlockEntryInstr*> block_stack_;

   GrowableArray<BlockEntryInstr*> postorder_;
   GrowableArray<BlockEntryInstr*> cold_postorder_;
 };
 }  // namespace

 void BlockScheduler::ReorderBlocksAOT(FlowGraph* flow_graph) {
   AOTBlockScheduler(flow_graph).ComputeOrder();
 }

 }  // namespace dart
	// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
	// for details. All rights reserved. Use of this source code is governed by a
	// BSD-style license that can be found in the LICENSE file.

	#include "vm/compiler/backend/block_scheduler.h"

	#include "vm/allocation.h"
	#include "vm/code_patcher.h"
	#include "vm/compiler/backend/flow_graph.h"
	#include "vm/compiler/jit/compiler.h"

	namespace dart {

	static intptr_t GetEdgeCount(const Array& edge_counters, intptr_t edge_id) {
	if (!FLAG_reorder_basic_blocks) {
	// Assume everything was visited once.
	return 1;
	}
	return Smi::Value(Smi::RawCast(edge_counters.At(edge_id)));
	}

	// There is an edge from instruction->successor. Set its weight (edge count
	// per function entry).
	static void SetEdgeWeight(BlockEntryInstr* block,
	BlockEntryInstr* successor,
	const Array& edge_counters,
	intptr_t entry_count) {
	ASSERT(entry_count != 0);
	if (auto target = successor->AsTargetEntry()) {
	// If this block ends in a goto, the edge count of this edge is the same
	// as the count on the single outgoing edge. This is true as long as the
	// block does not throw an exception.
	intptr_t count = GetEdgeCount(edge_counters, target->preorder_number());
	if (count >= 0) {
	double weight =
	static_cast<double>(count) / static_cast<double>(entry_count);
	target->set_edge_weight(weight);
	}
	} else if (auto jump = block->last_instruction()->AsGoto()) {
	intptr_t count = GetEdgeCount(edge_counters, block->preorder_number());
	if (count >= 0) {
	double weight =
	static_cast<double>(count) / static_cast<double>(entry_count);
	jump->set_edge_weight(weight);
	}
	}
	}

	void BlockScheduler::AssignEdgeWeights(FlowGraph* flow_graph) {
	if (!FLAG_reorder_basic_blocks) {
	return;
	}
	if (CompilerState::Current().is_aot()) {
	return;
	}

	const Function& function = flow_graph->parsed_function().function();
	const Array& ic_data_array =
	Array::Handle(flow_graph->zone(), function.ic_data_array());
	if (ic_data_array.IsNull()) {
	DEBUG_ASSERT(IsolateGroup::Current()->HasAttemptedReload() \|\|
	function.ForceOptimize());
	return;
	}
	Array& edge_counters = Array::Handle();
	edge_counters ^=
	ic_data_array.At(Function::ICDataArrayIndices::kEdgeCounters);
	if (edge_counters.IsNull()) {
	return;
	}

	auto graph_entry = flow_graph->graph_entry();
	BlockEntryInstr* entry = graph_entry->normal_entry();
	if (entry == nullptr) {
	entry = graph_entry->osr_entry();
	ASSERT(entry != nullptr);
	}
	const intptr_t entry_count =
	GetEdgeCount(edge_counters, entry->preorder_number());
	graph_entry->set_entry_count(entry_count);
	if (entry_count == 0) {
	return; // Nothing to do.
	}

	for (BlockIterator it = flow_graph->reverse_postorder_iterator(); !it.Done();
	it.Advance()) {
	BlockEntryInstr* block = it.Current();
	Instruction* last = block->last_instruction();
	for (intptr_t i = 0; i < last->SuccessorCount(); ++i) {
	BlockEntryInstr* succ = last->SuccessorAt(i);
	SetEdgeWeight(block, succ, edge_counters, entry_count);
	}
	}
	}

	// A weighted control-flow graph edge.
	struct Edge {
	Edge(BlockEntryInstr* source, BlockEntryInstr* target, double weight)
	: source(source), target(target), weight(weight) {}

	static int LowestWeightFirst(const Edge* a, const Edge* b);

	BlockEntryInstr* source;
	BlockEntryInstr* target;
	double weight;
	};

	// A linked list node in a chain of blocks.
	struct Link : public ZoneAllocated {
	Link(BlockEntryInstr* block, Link* next) : block(block), next(next) {}

	BlockEntryInstr* block;
	Link* next;
	};

	// A chain of blocks with first and last pointers for fast concatenation and
	// a length to support adding a shorter chain's links to a longer chain.
	struct Chain : public ZoneAllocated {
	explicit Chain(BlockEntryInstr* block)
	: first(new Link(block, nullptr)), last(first), length(1) {}

	Link* first;
	Link* last;
	intptr_t length;
	};

	int Edge::LowestWeightFirst(const Edge* a, const Edge* b) {
	if (a->weight < b->weight) {
	return -1;
	}
	return (a->weight > b->weight) ? 1 : 0;
	}

	// Combine two chains by adding the shorter chain's links to the longer
	// chain.
	static void Union(GrowableArray<Chain> chains,
	Chain* source_chain,
	Chain* target_chain) {
	if (source_chain->length < target_chain->length) {
	for (Link* link = source_chain->first; link != nullptr; link = link->next) {
	(*chains)[link->block->postorder_number()] = target_chain;
	}
	// Link the chains.
	source_chain->last->next = target_chain->first;
	// Update the state of the longer chain.
	target_chain->first = source_chain->first;
	target_chain->length += source_chain->length;
	} else {
	for (Link* link = target_chain->first; link != nullptr; link = link->next) {
	(*chains)[link->block->postorder_number()] = source_chain;
	}
	source_chain->last->next = target_chain->first;
	source_chain->last = target_chain->last;
	source_chain->length += target_chain->length;
	}
	}

	void BlockScheduler::ReorderBlocks(FlowGraph* flow_graph) {
	if (!flow_graph->should_reorder_blocks()) {
	return;
	}

	if (CompilerState::Current().is_aot()) {
	ReorderBlocksAOT(flow_graph);
	} else {
	ReorderBlocksJIT(flow_graph);
	}
	}

	void BlockScheduler::ReorderBlocksJIT(FlowGraph* flow_graph) {
	// Add every block to a chain of length 1 and compute a list of edges
	// sorted by weight.
	intptr_t block_count = flow_graph->preorder().length();
	GrowableArray<Edge> edges(2 * block_count);

	// A map from a block's postorder number to the chain it is in. Used to
	// implement a simple (ordered) union-find data structure. Chains are
	// stored by pointer so that they are aliased (mutating one mutates all
	// shared ones). Find(n) is simply chains[n].
	GrowableArray<Chain*> chains(block_count);

	for (BlockIterator it = flow_graph->postorder_iterator(); !it.Done();
	it.Advance()) {
	BlockEntryInstr* block = it.Current();
	chains.Add(new Chain(block));

	Instruction* last = block->last_instruction();
	for (intptr_t i = 0; i < last->SuccessorCount(); ++i) {
	BlockEntryInstr* succ = last->SuccessorAt(i);
	double weight = 0.0;
	if (succ->IsTargetEntry()) {
	weight = succ->AsTargetEntry()->edge_weight();
	} else if (last->IsGoto()) {
	weight = last->AsGoto()->edge_weight();
	}
	edges.Add(Edge(block, succ, weight));
	}
	}

	// Handle each edge in turn. The edges are sorted by increasing weight.
	edges.Sort(Edge::LowestWeightFirst);
	while (!edges.is_empty()) {
	Edge edge = edges.RemoveLast();
	Chain* source_chain = chains[edge.source->postorder_number()];
	Chain* target_chain = chains[edge.target->postorder_number()];

	// If the source and target are already in the same chain or if the
	// edge's source or target is not exposed at the appropriate end of a
	// chain skip this edge.
	if ((source_chain == target_chain) \|\|
	(edge.source != source_chain->last->block) \|\|
	(edge.target != target_chain->first->block)) {
	continue;
	}

	Union(&chains, source_chain, target_chain);
	}

	// Ensure the checked entry remains first to avoid needing another offset on
	// Instructions, compare Code::EntryPointOf.
	GraphEntryInstr* graph_entry = flow_graph->graph_entry();
	flow_graph->CodegenBlockOrder()->Add(graph_entry);
	FunctionEntryInstr* checked_entry = graph_entry->normal_entry();
	if (checked_entry != nullptr) {
	flow_graph->CodegenBlockOrder()->Add(checked_entry);
	}
	// Build a new block order. Emit each chain when its first block occurs
	// in the original reverse postorder ordering.
	// Note: the resulting order is not topologically sorted and can't be
	// used a replacement for reverse_postorder in algorithms that expect
	// topological sort.
	for (intptr_t i = block_count - 1; i >= 0; --i) {
	if (chains[i]->first->block == flow_graph->postorder()[i]) {
	for (Link* link = chains[i]->first; link != nullptr; link = link->next) {
	if ((link->block != checked_entry) && (link->block != graph_entry)) {
	flow_graph->CodegenBlockOrder()->Add(link->block);
	}
	}
	}
	}
	}

	// AOT block order is based on reverse post order but with two changes:
	//
	// - Blocks which always throw and their direct predecessors are considered
	// cold and moved to the end of the order.
	// - Blocks which belong to the same loop are kept together (where possible)
	// and not interspersed with other blocks.
	//
	namespace {
	class AOTBlockScheduler {
	public:
	explicit AOTBlockScheduler(FlowGraph* flow_graph)
	: flow_graph_(flow_graph),
	block_count_(flow_graph->reverse_postorder().length()),
	marks_(block_count_),
	postorder_(block_count_),
	cold_postorder_(10) {
	marks_.FillWith(0, 0, block_count_);
	}

	void ComputeOrder() {
	ComputeOrderImpl();

	const auto codegen_order = flow_graph_->CodegenBlockOrder();
	for (intptr_t i = postorder_.length() - 1; i >= 0; --i) {
	codegen_order->Add(postorder_[i]);
	}
	for (intptr_t i = cold_postorder_.length() - 1; i >= 0; --i) {
	codegen_order->Add(cold_postorder_[i]);
	}
	}

	private:
	// The algorithm below is almost identical to \|FlowGraph::DiscoverBlocks\|, but
	// with few tweaks which guarantee improved scheduling for cold code and
	// loops.
	void ComputeOrderImpl() {
	PushBlock(flow_graph_->graph_entry());
	while (!block_stack_.is_empty()) {
	BlockEntryInstr* block = block_stack_.Last();
	auto& marks = MarksOf(block);
	auto last = block->last_instruction();
	const auto successor_count = last->SuccessorCount();

	if ((marks & kVisitedMark) == 0) {
	marks \|= kVisitedMark;

	if (last->IsThrow() \|\| last->IsReThrow() \|\| last->IsStop()) {
	marks \|= kColdMark;
	} else {
	// When visiting a block inside a loop with two successors
	// push the successor with lesser nesting last, so that it is
	// visited first. This helps to keep blocks which belong to the
	// same loop together.
	//
	// This is the main difference from \|DiscoverBlocks\| which always
	// visits successors in reverse order.
	if (successor_count == 2 && block->loop_info() != nullptr) {
	auto succ0 = last->SuccessorAt(0);
	auto succ1 = last->SuccessorAt(1);

	if (succ0->NestingDepth() < succ1->NestingDepth()) {
	PushBlock(succ1);
	PushBlock(succ0);
	} else {
	PushBlock(succ0);
	PushBlock(succ1);
	}
	} else {
	for (intptr_t i = 0; i < successor_count; i++) {
	PushBlock(last->SuccessorAt(i));
	}
	}

	// We have pushed some successors to the stack. Process them first.
	if (block_stack_.Last() != block) {
	continue;
	}

	// No successors added, fall through.
	}
	}

	// All successors of this block were visited, which means we are
	// done with this block.
	block_stack_.RemoveLast();

	// Propagate cold mark from the successors: if all successors are
	// cold then this block is cold as well.
	if (successor_count > 0) {
	uint8_t cold_mark = kColdMark;
	for (intptr_t i = 0; i < successor_count; i++) {
	cold_mark &= MarksOf(last->SuccessorAt(i));
	}
	marks \|= cold_mark;
	}

	if ((marks & (kColdMark \| kPinnedMark)) == kColdMark) {
	// This block is cold and not pinned: move it to cold section at
	// the end.
	cold_postorder_.Add(block);
	} else {
	postorder_.Add(block);
	}
	}
	}

	// The block was added to the stack.
	static constexpr uint8_t kSeenMark = 1 << 0;
	// The block was visited and all of its successors were added to the stack.
	static constexpr uint8_t kVisitedMark = 1 << 1;
	// The block terminates with unconditional throw or rethrow.
	static constexpr uint8_t kColdMark = 1 << 2;
	// The block should not move to cold section.
	static constexpr uint8_t kPinnedMark = 1 << 3;

	uint8_t& MarksOf(BlockEntryInstr* block) {
	return marks_[block->preorder_number()];
	}

	void PushBlock(BlockEntryInstr* block) {
	auto& marks = MarksOf(block);
	if ((marks & kSeenMark) == 0) {
	marks \|= kSeenMark;
	block_stack_.Add(block);

	if (block->IsFunctionEntry() \|\| block->IsGraphEntry()) {
	marks \|= kPinnedMark;
	}
	}
	}

	FlowGraph* const flow_graph_;
	const intptr_t block_count_;

	// Block marks for each block indexed by block preorder number.
	GrowableArray<uint8_t> marks_;

	// Stack of blocks to process.
	GrowableArray<BlockEntryInstr*> block_stack_;

	GrowableArray<BlockEntryInstr*> postorder_;
	GrowableArray<BlockEntryInstr*> cold_postorder_;
	};
	} // namespace

	void BlockScheduler::ReorderBlocksAOT(FlowGraph* flow_graph) {
	AOTBlockScheduler(flow_graph).ComputeOrder();
	}

	} // namespace dart