VM: Re-format to use at most one newline between functions

runtime/vm/flow_graph.cc

 // Copyright (c) 2012, 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/flow_graph.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
 #include "vm/flow_graph_range_analysis.h"
+#include "vm/growable_array.h"
 #include "vm/il_printer.h"
 #include "vm/intermediate_language.h"
-#include "vm/growable_array.h"
 #include "vm/object_store.h"
 
 namespace dart {
 
 #if defined(TARGET_ARCH_ARM) || defined(TARGET_ARCH_IA32)
 DEFINE_FLAG(bool, trace_smi_widening, false, "Trace Smi->Int32 widening pass.");
 #endif
 DEFINE_FLAG(bool, prune_dead_locals, true, "optimize dead locals away");
 DECLARE_FLAG(bool, verify_compiler);
 
-
 FlowGraph::FlowGraph(const ParsedFunction& parsed_function,
                      GraphEntryInstr* graph_entry,
                      intptr_t max_block_id)
     : thread_(Thread::Current()),
       parent_(),
       current_ssa_temp_index_(0),
       max_block_id_(max_block_id),
       parsed_function_(parsed_function),
       num_copied_params_(parsed_function.num_copied_params()),
       num_non_copied_params_(parsed_function.num_non_copied_params()),
       graph_entry_(graph_entry),
       preorder_(),
       postorder_(),
       reverse_postorder_(),
       optimized_block_order_(),
       constant_null_(NULL),
       constant_dead_(NULL),
       constant_empty_context_(NULL),
       block_effects_(NULL),
       licm_allowed_(true),
       loop_headers_(NULL),
       loop_invariant_loads_(NULL),
       deferred_prefixes_(parsed_function.deferred_prefixes()),
       await_token_positions_(NULL),
       captured_parameters_(new (zone()) BitVector(zone(), variable_count())),
       inlining_id_(-1) {
   DiscoverBlocks();
 }
 
-
 void FlowGraph::EnsureSSATempIndex(Definition* defn, Definition* replacement) {
   if ((replacement->ssa_temp_index() == -1) && (defn->ssa_temp_index() != -1)) {
     AllocateSSAIndexes(replacement);
   }
 }
 
-
 void FlowGraph::ReplaceCurrentInstruction(ForwardInstructionIterator* iterator,
                                           Instruction* current,
                                           Instruction* replacement) {
   Definition* current_defn = current->AsDefinition();
   if ((replacement != NULL) && (current_defn != NULL)) {
     Definition* replacement_defn = replacement->AsDefinition();
     ASSERT(replacement_defn != NULL);
     current_defn->ReplaceUsesWith(replacement_defn);
     EnsureSSATempIndex(current_defn, replacement_defn);
 
@@ skipping 18 matching lines @@
       if (replacement == NULL || i >= replacement->ArgumentCount() ||
           replacement->PushArgumentAt(i) != push) {
         push->ReplaceUsesWith(push->value()->definition());
         push->RemoveFromGraph();
       }
     }
   }
   iterator->RemoveCurrentFromGraph();
 }
 
-
 void FlowGraph::AddToDeferredPrefixes(
     ZoneGrowableArray<const LibraryPrefix*>* from) {
   ZoneGrowableArray<const LibraryPrefix*>* to = deferred_prefixes();
   for (intptr_t i = 0; i < from->length(); i++) {
     const LibraryPrefix* prefix = (*from)[i];
     for (intptr_t j = 0; j < to->length(); j++) {
       if ((*to)[j]->raw() == prefix->raw()) {
         return;
       }
     }
     to->Add(prefix);
   }
 }
 
-
 bool FlowGraph::ShouldReorderBlocks(const Function& function,
                                     bool is_optimized) {
   return is_optimized && FLAG_reorder_basic_blocks && !function.is_intrinsic();
 }
 
-
 GrowableArray<BlockEntryInstr*>* FlowGraph::CodegenBlockOrder(
     bool is_optimized) {
   return ShouldReorderBlocks(function(), is_optimized) ? &optimized_block_order_
                                                        : &reverse_postorder_;
 }
 
-
 ConstantInstr* FlowGraph::GetConstant(const Object& object) {
   ConstantInstr* constant = constant_instr_pool_.LookupValue(object);
   if (constant == NULL) {
     // Otherwise, allocate and add it to the pool.
     constant =
         new (zone()) ConstantInstr(Object::ZoneHandle(zone(), object.raw()));
     constant->set_ssa_temp_index(alloc_ssa_temp_index());
 
     AddToInitialDefinitions(constant);
     constant_instr_pool_.Insert(constant);
   }
   return constant;
 }
 
-
 void FlowGraph::AddToInitialDefinitions(Definition* defn) {
   // TODO(zerny): Set previous to the graph entry so it is accessible by
   // GetBlock. Remove this once there is a direct pointer to the block.
   defn->set_previous(graph_entry_);
   graph_entry_->initial_definitions()->Add(defn);
 }
 
-
 void FlowGraph::InsertBefore(Instruction* next,
                              Instruction* instr,
                              Environment* env,
                              UseKind use_kind) {
   InsertAfter(next->previous(), instr, env, use_kind);
 }
 
-
 void FlowGraph::InsertAfter(Instruction* prev,
                             Instruction* instr,
                             Environment* env,
                             UseKind use_kind) {
   if (use_kind == kValue) {
     ASSERT(instr->IsDefinition());
     AllocateSSAIndexes(instr->AsDefinition());
   }
   instr->InsertAfter(prev);
   ASSERT(instr->env() == NULL);
   if (env != NULL) {
     env->DeepCopyTo(zone(), instr);
   }
 }
 
-
 Instruction* FlowGraph::AppendTo(Instruction* prev,
                                  Instruction* instr,
                                  Environment* env,
                                  UseKind use_kind) {
   if (use_kind == kValue) {
     ASSERT(instr->IsDefinition());
     AllocateSSAIndexes(instr->AsDefinition());
   }
   ASSERT(instr->env() == NULL);
   if (env != NULL) {
     env->DeepCopyTo(zone(), instr);
   }
   return prev->AppendInstruction(instr);
 }
 
-
 // A wrapper around block entries including an index of the next successor to
 // be read.
 class BlockTraversalState {
  public:
   explicit BlockTraversalState(BlockEntryInstr* block)
       : block_(block),
         next_successor_ix_(block->last_instruction()->SuccessorCount() - 1) {}
 
   bool HasNextSuccessor() const { return next_successor_ix_ >= 0; }
   BlockEntryInstr* NextSuccessor() {
     ASSERT(HasNextSuccessor());
     return block_->last_instruction()->SuccessorAt(next_successor_ix_--);
   }
 
   BlockEntryInstr* block() const { return block_; }
 
  private:
   BlockEntryInstr* block_;
   intptr_t next_successor_ix_;
 
   DISALLOW_ALLOCATION();
 };
 
-
 void FlowGraph::DiscoverBlocks() {
   StackZone zone(thread());
 
   // Initialize state.
   preorder_.Clear();
   postorder_.Clear();
   reverse_postorder_.Clear();
   parent_.Clear();
 
   GrowableArray<BlockTraversalState> block_stack;
@@ skipping 24 matching lines @@
   for (intptr_t i = 0; i < block_count; ++i) {
     reverse_postorder_.Add(postorder_[block_count - i - 1]);
   }
 
   // Block effects are using postorder numbering. Discard computed information.
   block_effects_ = NULL;
   loop_headers_ = NULL;
   loop_invariant_loads_ = NULL;
 }
 
-
 void FlowGraph::MergeBlocks() {
   bool changed = false;
   BitVector* merged = new (zone()) BitVector(zone(), postorder().length());
   for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
        block_it.Advance()) {
     BlockEntryInstr* block = block_it.Current();
     if (block->IsGraphEntry()) continue;
     if (merged->Contains(block->postorder_number())) continue;
 
     Instruction* last = block->last_instruction();
@@ skipping 21 matching lines @@
     // The new block inherits the block id of the last successor to maintain
     // the order of phi inputs at its successors consistent with block ids.
     if (successor != NULL) {
       block->set_block_id(successor->block_id());
     }
   }
   // Recompute block order after changes were made.
   if (changed) DiscoverBlocks();
 }
 
-
 // Debugging code to verify the construction of use lists.
 static intptr_t MembershipCount(Value* use, Value* list) {
   intptr_t count = 0;
   while (list != NULL) {
     if (list == use) ++count;
     list = list->next_use();
   }
   return count;
 }
 
-
 static void VerifyUseListsInInstruction(Instruction* instr) {
   ASSERT(instr != NULL);
   ASSERT(!instr->IsJoinEntry());
   for (intptr_t i = 0; i < instr->InputCount(); ++i) {
     Value* use = instr->InputAt(i);
     ASSERT(use->definition() != NULL);
     ASSERT((use->definition() != instr) || use->definition()->IsPhi() ||
            use->definition()->IsMaterializeObject());
     ASSERT(use->instruction() == instr);
     ASSERT(use->use_index() == i);
@@ skipping 68 matching lines @@
       phi->set_is_receiver(PhiInstr::kNotReceiver);
       break;
     }
   }
 
   if (phi->is_receiver() == PhiInstr::kNotReceiver) {
     unmark->Add(phi);
   }
 }
 
-
 void FlowGraph::ComputeIsReceiver(PhiInstr* phi) const {
   GrowableArray<PhiInstr*> unmark;
   ComputeIsReceiverRecursive(phi, &unmark);
 
   // Now drain unmark.
   while (!unmark.is_empty()) {
     PhiInstr* phi = unmark.RemoveLast();
     for (Value::Iterator it(phi->input_use_list()); !it.Done(); it.Advance()) {
       PhiInstr* use = it.Current()->instruction()->AsPhi();
       if ((use != NULL) && (use->is_receiver() == PhiInstr::kReceiver)) {
         use->set_is_receiver(PhiInstr::kNotReceiver);
         unmark.Add(use);
       }
     }
   }
 }
 
-
 bool FlowGraph::IsReceiver(Definition* def) const {
   def = def->OriginalDefinition();  // Could be redefined.
   if (def->IsParameter()) return (def->AsParameter()->index() == 0);
   if (!def->IsPhi() || graph_entry()->catch_entries().is_empty()) return false;
   PhiInstr* phi = def->AsPhi();
   if (phi->is_receiver() != PhiInstr::kUnknownReceiver) {
     return (phi->is_receiver() == PhiInstr::kReceiver);
   }
   // Not known if this phi is the receiver yet. Compute it now.
   ComputeIsReceiver(phi);
   return (phi->is_receiver() == PhiInstr::kReceiver);
 }
 
-
 // Use CHA to determine if the call needs a class check: if the callee's
 // receiver is the same as the caller's receiver and there are no overridden
 // callee functions, then no class check is needed.
 bool FlowGraph::InstanceCallNeedsClassCheck(InstanceCallInstr* call,
                                             RawFunction::Kind kind) const {
   if (!FLAG_use_cha_deopt && !isolate()->all_classes_finalized()) {
     // Even if class or function are private, lazy class finalization
     // may later add overriding methods.
     return true;
   }
@@ skipping 14 matching lines @@
             "no overrides of '%s' '%s'\n",
             name.ToCString(), cls.ToCString());
       }
       thread()->cha()->AddToGuardedClasses(cls, subclass_count);
       return false;
     }
   }
   return true;
 }
 
-
 Instruction* FlowGraph::CreateCheckClass(Definition* to_check,
                                          const Cids& cids,
                                          intptr_t deopt_id,
                                          TokenPosition token_pos) {
   if (cids.IsMonomorphic() && cids.MonomorphicReceiverCid() == kSmiCid) {
     return new (zone())
         CheckSmiInstr(new (zone()) Value(to_check), deopt_id, token_pos);
   }
   return new (zone())
       CheckClassInstr(new (zone()) Value(to_check), deopt_id, cids, token_pos);
 }
 
-
 bool FlowGraph::VerifyUseLists() {
   // Verify the initial definitions.
   for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); ++i) {
     VerifyUseListsInInstruction((*graph_entry_->initial_definitions())[i]);
   }
 
   // Verify phis in join entries and the instructions in each block.
   for (intptr_t i = 0; i < preorder_.length(); ++i) {
     BlockEntryInstr* entry = preorder_[i];
     JoinEntryInstr* join = entry->AsJoinEntry();
     if (join != NULL) {
       for (PhiIterator it(join); !it.Done(); it.Advance()) {
         PhiInstr* phi = it.Current();
         ASSERT(phi != NULL);
         VerifyUseListsInInstruction(phi);
       }
     }
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       VerifyUseListsInInstruction(it.Current());
     }
   }
 
   return true;  // Return true so we can ASSERT validation.
 }
 
-
 // Verify that a redefinition dominates all uses of the redefined value.
 bool FlowGraph::VerifyRedefinitions() {
   for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
        block_it.Advance()) {
     for (ForwardInstructionIterator instr_it(block_it.Current());
          !instr_it.Done(); instr_it.Advance()) {
       RedefinitionInstr* redefinition = instr_it.Current()->AsRedefinition();
       if (redefinition != NULL) {
         Definition* original = redefinition->value()->definition();
         for (Value::Iterator it(original->input_use_list()); !it.Done();
              it.Advance()) {
           Value* original_use = it.Current();
           if (original_use->instruction() == redefinition) {
             continue;
           }
           if (original_use->instruction()->IsDominatedBy(redefinition)) {
             FlowGraphPrinter::PrintGraph("VerifyRedefinitions", this);
             THR_Print("%s\n", redefinition->ToCString());
             THR_Print("use=%s\n", original_use->instruction()->ToCString());
             return false;
           }
         }
       }
     }
   }
   return true;
 }
 
-
 LivenessAnalysis::LivenessAnalysis(
     intptr_t variable_count,
     const GrowableArray<BlockEntryInstr*>& postorder)
     : zone_(Thread::Current()->zone()),
       variable_count_(variable_count),
       postorder_(postorder),
       live_out_(postorder.length()),
       kill_(postorder.length()),
       live_in_(postorder.length()) {}
 
-
 bool LivenessAnalysis::UpdateLiveOut(const BlockEntryInstr& block) {
   BitVector* live_out = live_out_[block.postorder_number()];
   bool changed = false;
   Instruction* last = block.last_instruction();
   ASSERT(last != NULL);
   for (intptr_t i = 0; i < last->SuccessorCount(); i++) {
     BlockEntryInstr* succ = last->SuccessorAt(i);
     ASSERT(succ != NULL);
     if (live_out->AddAll(live_in_[succ->postorder_number()])) {
       changed = true;
     }
   }
   return changed;
 }
 
-
 bool LivenessAnalysis::UpdateLiveIn(const BlockEntryInstr& block) {
   BitVector* live_out = live_out_[block.postorder_number()];
   BitVector* kill = kill_[block.postorder_number()];
   BitVector* live_in = live_in_[block.postorder_number()];
   return live_in->KillAndAdd(kill, live_out);
 }
 
-
 void LivenessAnalysis::ComputeLiveInAndLiveOutSets() {
   const intptr_t block_count = postorder_.length();
   bool changed;
   do {
     changed = false;
 
     for (intptr_t i = 0; i < block_count; i++) {
       const BlockEntryInstr& block = *postorder_[i];
 
       // Live-in set depends only on kill set which does not
       // change in this loop and live-out set.  If live-out
       // set does not change there is no need to recompute
       // live-in set.
       if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
         changed = true;
       }
     }
   } while (changed);
 }
 
-
 void LivenessAnalysis::Analyze() {
   const intptr_t block_count = postorder_.length();
   for (intptr_t i = 0; i < block_count; i++) {
     live_out_.Add(new (zone()) BitVector(zone(), variable_count_));
     kill_.Add(new (zone()) BitVector(zone(), variable_count_));
     live_in_.Add(new (zone()) BitVector(zone(), variable_count_));
   }
 
   ComputeInitialSets();
   ComputeLiveInAndLiveOutSets();
 }
 
-
 static void PrintBitVector(const char* tag, BitVector* v) {
   OS::Print("%s:", tag);
   for (BitVector::Iterator it(v); !it.Done(); it.Advance()) {
     OS::Print(" %" Pd "", it.Current());
   }
   OS::Print("\n");
 }
 
-
 void LivenessAnalysis::Dump() {
   const intptr_t block_count = postorder_.length();
   for (intptr_t i = 0; i < block_count; i++) {
     BlockEntryInstr* block = postorder_[i];
     OS::Print("block @%" Pd " -> ", block->block_id());
 
     Instruction* last = block->last_instruction();
     for (intptr_t j = 0; j < last->SuccessorCount(); j++) {
       BlockEntryInstr* succ = last->SuccessorAt(j);
       OS::Print(" @%" Pd "", succ->block_id());
     }
     OS::Print("\n");
 
     PrintBitVector("  live out", live_out_[i]);
     PrintBitVector("  kill", kill_[i]);
     PrintBitVector("  live in", live_in_[i]);
   }
 }
 
-
 // Computes liveness information for local variables.
 class VariableLivenessAnalysis : public LivenessAnalysis {
  public:
   explicit VariableLivenessAnalysis(FlowGraph* flow_graph)
       : LivenessAnalysis(flow_graph->variable_count(), flow_graph->postorder()),
         flow_graph_(flow_graph),
         num_non_copied_params_(flow_graph->num_non_copied_params()),
         assigned_vars_() {}
 
   // For every block (in preorder) compute and return set of variables that
@@ skipping 56 matching lines @@
   }
 
  private:
   virtual void ComputeInitialSets();
 
   const FlowGraph* flow_graph_;
   const intptr_t num_non_copied_params_;
   GrowableArray<BitVector*> assigned_vars_;
 };
 
-
 void VariableLivenessAnalysis::ComputeInitialSets() {
   const intptr_t block_count = postorder_.length();
 
   BitVector* last_loads = new (zone()) BitVector(zone(), variable_count_);
   for (intptr_t i = 0; i < block_count; i++) {
     BlockEntryInstr* block = postorder_[i];
 
     BitVector* kill = kill_[i];
     BitVector* live_in = live_in_[i];
     last_loads->Clear();
@@ skipping 40 matching lines @@
           }
           kill->Add(index);
         }
         live_in->Remove(index);
         continue;
       }
     }
   }
 }
 
-
 void FlowGraph::ComputeSSA(
     intptr_t next_virtual_register_number,
     ZoneGrowableArray<Definition*>* inlining_parameters) {
   ASSERT((next_virtual_register_number == 0) || (inlining_parameters != NULL));
   current_ssa_temp_index_ = next_virtual_register_number;
   GrowableArray<BitVector*> dominance_frontier;
   ComputeDominators(&dominance_frontier);
 
   VariableLivenessAnalysis variable_liveness(this);
   variable_liveness.Analyze();
 
   GrowableArray<PhiInstr*> live_phis;
 
   InsertPhis(preorder_, variable_liveness.ComputeAssignedVars(),
              dominance_frontier, &live_phis);
 
-
   // Rename uses to reference inserted phis where appropriate.
   // Collect phis that reach a non-environment use.
   Rename(&live_phis, &variable_liveness, inlining_parameters);
 
   // Propagate alive mark transitively from alive phis and then remove
   // non-live ones.
   RemoveDeadPhis(&live_phis);
 }
 
-
 // Compute immediate dominators and the dominance frontier for each basic
 // block.  As a side effect of the algorithm, sets the immediate dominator
 // of each basic block.
 //
 // dominance_frontier: an output parameter encoding the dominance frontier.
 //     The array maps the preorder block number of a block to the set of
 //     (preorder block numbers of) blocks in the dominance frontier.
 void FlowGraph::ComputeDominators(
     GrowableArray<BitVector*>* dominance_frontier) {
   // Use the SEMI-NCA algorithm to compute dominators.  This is a two-pass
@@ skipping 83 matching lines @@
     for (intptr_t i = 0; i < count; ++i) {
       BlockEntryInstr* runner = block->PredecessorAt(i);
       while (runner != block->dominator()) {
         (*dominance_frontier)[runner->preorder_number()]->Add(block_index);
         runner = runner->dominator();
       }
     }
   }
 }
 
-
 void FlowGraph::CompressPath(intptr_t start_index,
                              intptr_t current_index,
                              GrowableArray<intptr_t>* parent,
                              GrowableArray<intptr_t>* label) {
   intptr_t next_index = (*parent)[current_index];
   if (next_index > start_index) {
     CompressPath(start_index, next_index, parent, label);
     (*label)[current_index] =
         Utils::Minimum((*label)[current_index], (*label)[next_index]);
     (*parent)[current_index] = (*parent)[next_index];
   }
 }
 
-
 void FlowGraph::InsertPhis(const GrowableArray<BlockEntryInstr*>& preorder,
                            const GrowableArray<BitVector*>& assigned_vars,
                            const GrowableArray<BitVector*>& dom_frontier,
                            GrowableArray<PhiInstr*>* live_phis) {
   const intptr_t block_count = preorder.length();
   // Map preorder block number to the highest variable index that has a phi
   // in that block.  Use it to avoid inserting multiple phis for the same
   // variable.
   GrowableArray<intptr_t> has_already(block_count);
   // Map preorder block number to the highest variable index for which the
@@ skipping 39 matching lines @@
           if (work[index] < var_index) {
             work[index] = var_index;
             worklist.Add(block);
           }
         }
       }
     }
   }
 }
 
-
 void FlowGraph::Rename(GrowableArray<PhiInstr*>* live_phis,
                        VariableLivenessAnalysis* variable_liveness,
                        ZoneGrowableArray<Definition*>* inlining_parameters) {
   GraphEntryInstr* entry = graph_entry();
 
   // Initial renaming environment.
   GrowableArray<Definition*> env(variable_count());
 
   // Add global constants to the initial definitions.
   constant_null_ = GetConstant(Object::ZoneHandle());
@@ skipping 73 matching lines @@
 
   if (entry->SuccessorCount() > 1) {
     // Functions with try-catch have a fixed area of stack slots reserved
     // so that all local variables are stored at a known location when
     // on entry to the catch.
     entry->set_fixed_slot_count(num_stack_locals() + num_copied_params());
   }
   RenameRecursive(entry, &env, live_phis, variable_liveness);
 }
 
-
 void FlowGraph::AttachEnvironment(Instruction* instr,
                                   GrowableArray<Definition*>* env) {
   Environment* deopt_env =
       Environment::From(zone(), *env, num_non_copied_params_, parsed_function_);
   if (instr->IsClosureCall()) {
     deopt_env =
         deopt_env->DeepCopy(zone(), deopt_env->Length() - instr->InputCount());
   }
   instr->SetEnvironment(deopt_env);
   for (Environment::DeepIterator it(deopt_env); !it.Done(); it.Advance()) {
     Value* use = it.CurrentValue();
     use->definition()->AddEnvUse(use);
   }
   if (instr->ComputeCanDeoptimize()) {
     instr->env()->set_deopt_id(instr->deopt_id());
   }
 }
 
-
 void FlowGraph::RenameRecursive(BlockEntryInstr* block_entry,
                                 GrowableArray<Definition*>* env,
                                 GrowableArray<PhiInstr*>* live_phis,
                                 VariableLivenessAnalysis* variable_liveness) {
   // 1. Process phis first.
   if (block_entry->IsJoinEntry()) {
     JoinEntryInstr* join = block_entry->AsJoinEntry();
     if (join->phis() != NULL) {
       for (intptr_t i = 0; i < join->phis()->length(); ++i) {
         PhiInstr* phi = (*join->phis())[i];
@@ skipping 178 matching lines @@
         if (phi != NULL) {
           // Rename input operand.
           Value* use = new (zone()) Value((*env)[i]);
           phi->SetInputAt(pred_index, use);
         }
       }
     }
   }
 }
 
-
 void FlowGraph::RemoveDeadPhis(GrowableArray<PhiInstr*>* live_phis) {
   // Augment live_phis with those that have implicit real used at
   // potentially throwing instructions if there is a try-catch in this graph.
   if (graph_entry()->SuccessorCount() > 1) {
     for (BlockIterator it(postorder_iterator()); !it.Done(); it.Advance()) {
       JoinEntryInstr* join = it.Current()->AsJoinEntry();
       if (join == NULL) continue;
       for (PhiIterator phi_it(join); !phi_it.Done(); phi_it.Advance()) {
         PhiInstr* phi = phi_it.Current();
         if (phi == NULL || phi->is_alive() || (phi->input_use_list() != NULL) ||
@@ skipping 25 matching lines @@
       }
     }
   }
 
   for (BlockIterator it(postorder_iterator()); !it.Done(); it.Advance()) {
     JoinEntryInstr* join = it.Current()->AsJoinEntry();
     if (join != NULL) join->RemoveDeadPhis(constant_dead());
   }
 }
 
-
 RedefinitionInstr* FlowGraph::EnsureRedefinition(Instruction* prev,
                                                  Definition* original,
                                                  CompileType compile_type) {
   RedefinitionInstr* first = prev->next()->AsRedefinition();
   if (first != NULL && (first->constrained_type() != NULL)) {
     if ((first->value()->definition() == original) &&
         first->constrained_type()->IsEqualTo(&compile_type)) {
       // Already redefined. Do nothing.
       return NULL;
     }
   }
   RedefinitionInstr* redef = new RedefinitionInstr(new Value(original));
   redef->set_constrained_type(new CompileType(compile_type));
   InsertAfter(prev, redef, NULL, FlowGraph::kValue);
   RenameDominatedUses(original, redef, redef);
   return redef;
 }
 
-
 void FlowGraph::RemoveRedefinitions() {
   // Remove redefinition instructions inserted to inhibit hoisting.
   for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
        block_it.Advance()) {
     thread()->CheckForSafepoint();
     for (ForwardInstructionIterator instr_it(block_it.Current());
          !instr_it.Done(); instr_it.Advance()) {
       RedefinitionInstr* redefinition = instr_it.Current()->AsRedefinition();
       if (redefinition != NULL) {
         Definition* original;
         do {
           original = redefinition->value()->definition();
         } while (original->IsRedefinition());
         redefinition->ReplaceUsesWith(original);
         instr_it.RemoveCurrentFromGraph();
       }
     }
   }
 }
 
-
 // Find the natural loop for the back edge m->n and attach loop information
 // to block n (loop header). The algorithm is described in "Advanced Compiler
 // Design & Implementation" (Muchnick) p192.
 BitVector* FlowGraph::FindLoop(BlockEntryInstr* m, BlockEntryInstr* n) const {
   GrowableArray<BlockEntryInstr*> stack;
   BitVector* loop = new (zone()) BitVector(zone(), preorder_.length());
 
   loop->Add(n->preorder_number());
   if (n != m) {
     loop->Add(m->preorder_number());
     stack.Add(m);
   }
 
   while (!stack.is_empty()) {
     BlockEntryInstr* p = stack.RemoveLast();
     for (intptr_t i = 0; i < p->PredecessorCount(); ++i) {
       BlockEntryInstr* q = p->PredecessorAt(i);
       if (!loop->Contains(q->preorder_number())) {
         loop->Add(q->preorder_number());
         stack.Add(q);
       }
     }
   }
   return loop;
 }
 
-
 ZoneGrowableArray<BlockEntryInstr*>* FlowGraph::ComputeLoops() const {
   ZoneGrowableArray<BlockEntryInstr*>* loop_headers =
       new (zone()) ZoneGrowableArray<BlockEntryInstr*>();
 
   for (BlockIterator it = postorder_iterator(); !it.Done(); it.Advance()) {
     BlockEntryInstr* block = it.Current();
     for (intptr_t i = 0; i < block->PredecessorCount(); ++i) {
       BlockEntryInstr* pred = block->PredecessorAt(i);
       if (block->Dominates(pred)) {
         if (FLAG_trace_optimization) {
@@ skipping 24 matching lines @@
       OS::Print("Loop header B%" Pd "\n", header->block_id());
       for (BitVector::Iterator it(header->loop_info()); !it.Done();
            it.Advance()) {
         OS::Print("  B%" Pd "\n", preorder_[it.Current()]->block_id());
       }
     }
   }
   return loop_headers;
 }
 
-
 intptr_t FlowGraph::InstructionCount() const {
   intptr_t size = 0;
   // Iterate each block, skipping the graph entry.
   for (intptr_t i = 1; i < preorder_.length(); ++i) {
     for (ForwardInstructionIterator it(preorder_[i]); !it.Done();
          it.Advance()) {
       ++size;
     }
   }
   return size;
 }
 
-
 void FlowGraph::ComputeBlockEffects() {
   block_effects_ = new (zone()) BlockEffects(this);
 }
 
-
 BlockEffects::BlockEffects(FlowGraph* flow_graph)
     : available_at_(flow_graph->postorder().length()) {
   // We are tracking a single effect.
   ASSERT(EffectSet::kLastEffect == 1);
   Zone* zone = flow_graph->zone();
   const intptr_t block_count = flow_graph->postorder().length();
 
   // Set of blocks that contain side-effects.
   BitVector* kill = new (zone) BitVector(zone, block_count);
 
@@ skipping 60 matching lines @@
           available_after[block_num]->CopyFrom(temp);
           // Block is always available after itself.
           available_after[block_num]->Add(block_num);
         }
         changed = true;
       }
     }
   } while (changed);
 }
 
-
 bool BlockEffects::IsAvailableAt(Instruction* instr,
                                  BlockEntryInstr* block) const {
   return (instr->Dependencies().IsNone()) ||
          IsSideEffectFreePath(instr->GetBlock(), block);
 }
 
-
 bool BlockEffects::CanBeMovedTo(Instruction* instr,
                                 BlockEntryInstr* block) const {
   return (instr->Dependencies().IsNone()) ||
          IsSideEffectFreePath(block, instr->GetBlock());
 }
 
-
 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from,
                                         BlockEntryInstr* to) const {
   return available_at_[to->postorder_number()]->Contains(
       from->postorder_number());
 }
 
-
 // Quick access to the current zone.
 #define Z (zone())
 
-
 void FlowGraph::ConvertUse(Value* use, Representation from_rep) {
   const Representation to_rep =
       use->instruction()->RequiredInputRepresentation(use->use_index());
   if (from_rep == to_rep || to_rep == kNoRepresentation) {
     return;
   }
   InsertConversion(from_rep, to_rep, use, /*is_environment_use=*/false);
 }
 
-
 static bool IsUnboxedInteger(Representation rep) {
   return (rep == kUnboxedInt32) || (rep == kUnboxedUint32) ||
          (rep == kUnboxedMint);
 }
 
-
 static bool ShouldInlineSimd() {
   return FlowGraphCompiler::SupportsUnboxedSimd128();
 }
 
-
 static bool CanUnboxDouble() {
   return FlowGraphCompiler::SupportsUnboxedDoubles();
 }
 
-
 static bool CanConvertUnboxedMintToDouble() {
   return FlowGraphCompiler::CanConvertUnboxedMintToDouble();
 }
 
-
 void FlowGraph::InsertConversion(Representation from,
                                  Representation to,
                                  Value* use,
                                  bool is_environment_use) {
   Instruction* insert_before;
   Instruction* deopt_target;
   PhiInstr* phi = use->instruction()->AsPhi();
   if (phi != NULL) {
     ASSERT(phi->is_alive());
     // For phis conversions have to be inserted in the predecessor.
@@ skipping 51 matching lines @@
     use->BindTo(converted);
   }
 
   if ((to == kUnboxedInt32) && (phi != NULL)) {
     // Int32 phis are unboxed optimistically. Ensure that unboxing
     // has deoptimization target attached from the goto instruction.
     CopyDeoptTarget(converted, insert_before);
   }
 }
 
-
 void FlowGraph::ConvertEnvironmentUse(Value* use, Representation from_rep) {
   const Representation to_rep = kTagged;
   if (from_rep == to_rep) {
     return;
   }
   InsertConversion(from_rep, to_rep, use, /*is_environment_use=*/true);
 }
 
-
 void FlowGraph::InsertConversionsFor(Definition* def) {
   const Representation from_rep = def->representation();
 
   for (Value::Iterator it(def->input_use_list()); !it.Done(); it.Advance()) {
     ConvertUse(it.Current(), from_rep);
   }
 
   if (graph_entry()->SuccessorCount() > 1) {
     for (Value::Iterator it(def->env_use_list()); !it.Done(); it.Advance()) {
       Value* use = it.Current();
       if (use->instruction()->MayThrow() &&
           use->instruction()->GetBlock()->InsideTryBlock()) {
         // Environment uses at calls inside try-blocks must be converted to
         // tagged representation.
         ConvertEnvironmentUse(it.Current(), from_rep);
       }
     }
   }
 }
 
-
 static void UnboxPhi(PhiInstr* phi) {
   Representation unboxed = phi->representation();
 
   switch (phi->Type()->ToCid()) {
     case kDoubleCid:
       if (CanUnboxDouble()) {
         unboxed = kUnboxedDouble;
       }
       break;
     case kFloat32x4Cid:
@@ skipping 60 matching lines @@
       unboxed =
           RangeUtils::Fits(phi->range(), RangeBoundary::kRangeBoundaryInt32)
               ? kUnboxedInt32
               : kUnboxedMint;
     }
   }
 
   phi->set_representation(unboxed);
 }
 
-
 void FlowGraph::SelectRepresentations() {
   // Conservatively unbox all phis that were proven to be of Double,
   // Float32x4, or Int32x4 type.
   for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
        block_it.Advance()) {
     JoinEntryInstr* join_entry = block_it.Current()->AsJoinEntry();
     if (join_entry != NULL) {
       for (PhiIterator it(join_entry); !it.Done(); it.Advance()) {
         PhiInstr* phi = it.Current();
         UnboxPhi(phi);
@@ skipping 29 matching lines @@
     }
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       Definition* def = it.Current()->AsDefinition();
       if (def != NULL) {
         InsertConversionsFor(def);
       }
     }
   }
 }
 
-
 #if defined(TARGET_ARCH_ARM) || defined(TARGET_ARCH_IA32)
 // Smi widening pass is only meaningful on platforms where Smi
 // is smaller than 32bit. For now only support it on ARM and ia32.
 static bool CanBeWidened(BinarySmiOpInstr* smi_op) {
   return BinaryInt32OpInstr::IsSupported(smi_op->op_kind(), smi_op->left(),
                                          smi_op->right());
 }
 
-
 static bool BenefitsFromWidening(BinarySmiOpInstr* smi_op) {
   // TODO(vegorov): when shifts with non-constants shift count are supported
   // add them here as we save untagging for the count.
   switch (smi_op->op_kind()) {
     case Token::kMUL:
     case Token::kSHR:
       // For kMUL we save untagging of the argument for kSHR
       // we save tagging of the result.
       return true;
 
     default:
       return false;
   }
 }
 
-
 void FlowGraph::WidenSmiToInt32() {
   GrowableArray<BinarySmiOpInstr*> candidates;
 
   // Step 1. Collect all instructions that potentially benefit from widening of
   // their operands (or their result) into int32 range.
   for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
        block_it.Advance()) {
     for (ForwardInstructionIterator instr_it(block_it.Current());
          !instr_it.Done(); instr_it.Advance()) {
       BinarySmiOpInstr* smi_op = instr_it.Current()->AsBinarySmiOp();
@@ skipping 169 matching lines @@
 }
 #else
 void FlowGraph::WidenSmiToInt32() {
   // TODO(vegorov) ideally on 64-bit platforms we would like to narrow smi
   // operations to 32-bit where it saves tagging and untagging and allows
   // to use shorted (and faster) instructions. But we currently don't
   // save enough range information in the ICData to drive this decision.
 }
 #endif
 
-
 void FlowGraph::EliminateEnvironments() {
   // After this pass we can no longer perform LICM and hoist instructions
   // that can deoptimize.
 
   disallow_licm();
   for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
        block_it.Advance()) {
     BlockEntryInstr* block = block_it.Current();
     if (!block->IsCatchBlockEntry()) {
       block->RemoveEnvironment();
     }
     for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
       Instruction* current = it.Current();
       if (!current->ComputeCanDeoptimize() &&
           (!current->MayThrow() || !current->GetBlock()->InsideTryBlock())) {
         // Instructions that can throw need an environment for optimized
         // try-catch.
         // TODO(srdjan): --source-lines needs deopt environments to get at
         // the code for this instruction, however, leaving the environment
         // changes code.
         current->RemoveEnvironment();
       }
     }
   }
 }
 
-
 bool FlowGraph::Canonicalize() {
   bool changed = false;
 
   for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
        block_it.Advance()) {
     for (ForwardInstructionIterator it(block_it.Current()); !it.Done();
          it.Advance()) {
       Instruction* current = it.Current();
       if (current->HasUnmatchedInputRepresentations()) {
         // Can't canonicalize this instruction until all conversions for its
         // inputs are inserted.
         continue;
       }
 
       Instruction* replacement = current->Canonicalize(this);
 
       if (replacement != current) {
         // For non-definitions Canonicalize should return either NULL or
         // this.
         ASSERT((replacement == NULL) || current->IsDefinition());
         ReplaceCurrentInstruction(&it, current, replacement);
         changed = true;
       }
     }
   }
   return changed;
 }
 
-
 // Optimize (a << b) & c pattern: if c is a positive Smi or zero, then the
 // shift can be a truncating Smi shift-left and result is always Smi.
 // Merging occurs only per basic-block.
 void FlowGraph::TryOptimizePatterns() {
   if (!FLAG_truncating_left_shift) return;
   GrowableArray<BinarySmiOpInstr*> div_mod_merge;
   GrowableArray<InvokeMathCFunctionInstr*> sin_cos_merge;
   for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
        block_it.Advance()) {
     // Merging only per basic-block.
@@ skipping 27 matching lines @@
           if (math_unary->HasUses()) {
             sin_cos_merge.Add(math_unary);
           }
         }
       }
     }
     TryMergeTruncDivMod(&div_mod_merge);
   }
 }
 
-
 // Returns true if use is dominated by the given instruction.
 // Note: uses that occur at instruction itself are not dominated by it.
 static bool IsDominatedUse(Instruction* dom, Value* use) {
   BlockEntryInstr* dom_block = dom->GetBlock();
 
   Instruction* instr = use->instruction();
 
   PhiInstr* phi = instr->AsPhi();
   if (phi != NULL) {
     return dom_block->Dominates(phi->block()->PredecessorAt(use->use_index()));
   }
 
   BlockEntryInstr* use_block = instr->GetBlock();
   if (use_block == dom_block) {
     // Fast path for the case of block entry.
     if (dom_block == dom) return true;
 
     for (Instruction* curr = dom->next(); curr != NULL; curr = curr->next()) {
       if (curr == instr) return true;
     }
 
     return false;
   }
 
   return dom_block->Dominates(use_block);
 }
 
-
 void FlowGraph::RenameDominatedUses(Definition* def,
                                     Instruction* dom,
                                     Definition* other) {
   for (Value::Iterator it(def->input_use_list()); !it.Done(); it.Advance()) {
     Value* use = it.Current();
     if (IsDominatedUse(dom, use)) {
       use->BindTo(other);
     }
   }
 }
 
-
 void FlowGraph::RenameUsesDominatedByRedefinitions() {
   for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
        block_it.Advance()) {
     for (ForwardInstructionIterator instr_it(block_it.Current());
          !instr_it.Done(); instr_it.Advance()) {
       RedefinitionInstr* redefinition = instr_it.Current()->AsRedefinition();
       if (redefinition != NULL) {
         Definition* original = redefinition->value()->definition();
         RenameDominatedUses(original, redefinition, redefinition);
       }
     }
   }
 }
 
-
 static bool IsPositiveOrZeroSmiConst(Definition* d) {
   ConstantInstr* const_instr = d->AsConstant();
   if ((const_instr != NULL) && (const_instr->value().IsSmi())) {
     return Smi::Cast(const_instr->value()).Value() >= 0;
   }
   return false;
 }
 
-
 static BinarySmiOpInstr* AsSmiShiftLeftInstruction(Definition* d) {
   BinarySmiOpInstr* instr = d->AsBinarySmiOp();
   if ((instr != NULL) && (instr->op_kind() == Token::kSHL)) {
     return instr;
   }
   return NULL;
 }
 
-
 void FlowGraph::OptimizeLeftShiftBitAndSmiOp(
     ForwardInstructionIterator* current_iterator,
     Definition* bit_and_instr,
     Definition* left_instr,
     Definition* right_instr) {
   ASSERT(bit_and_instr != NULL);
   ASSERT((left_instr != NULL) && (right_instr != NULL));
 
   // Check for pattern, smi_shift_left must be single-use.
   bool is_positive_or_zero = IsPositiveOrZeroSmiConst(left_instr);
@@ skipping 16 matching lines @@
   ASSERT(bit_and_instr->IsBinarySmiOp() || bit_and_instr->IsBinaryMintOp());
   if (bit_and_instr->IsBinaryMintOp()) {
     // Replace Mint op with Smi op.
     BinarySmiOpInstr* smi_op = new (Z) BinarySmiOpInstr(
         Token::kBIT_AND, new (Z) Value(left_instr), new (Z) Value(right_instr),
         Thread::kNoDeoptId);  // BIT_AND cannot deoptimize.
     bit_and_instr->ReplaceWith(smi_op, current_iterator);
   }
 }
 
-
 // Dart:
 //  var x = d % 10;
 //  var y = d ~/ 10;
 //  var z = x + y;
 //
 // IL:
 //  v4 <- %(v2, v3)
 //  v5 <- ~/(v2, v3)
 //  v6 <- +(v4, v5)
 //
@@ skipping 50 matching lines @@
         other_binop->RemoveFromGraph();
         // Only one merge possible. Because canonicalization happens later,
         // more candidates are possible.
         // TODO(srdjan): Allow merging of trunc-div/mod into truncDivMod.
         break;
       }
     }
   }
 }
 
-
 void FlowGraph::AppendExtractNthOutputForMerged(Definition* instr,
                                                 intptr_t index,
                                                 Representation rep,
                                                 intptr_t cid) {
   ExtractNthOutputInstr* extract =
       new (Z) ExtractNthOutputInstr(new (Z) Value(instr), index, rep, cid);
   instr->ReplaceUsesWith(extract);
   InsertAfter(instr, extract, NULL, FlowGraph::kValue);
 }
 
-
 }  // namespace dart