Add deoptimization history to optimized functions.

runtime/vm/flow_graph_optimizer.cc

 // 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/flow_graph_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 3397 matching lines @@
 
 
 LICM::LICM(FlowGraph* flow_graph) : flow_graph_(flow_graph) {
   ASSERT(flow_graph->is_licm_allowed());
 }
 
 
 void LICM::Hoist(ForwardInstructionIterator* it,
                  BlockEntryInstr* pre_header,
                  Instruction* current) {
-  // TODO(fschneider): Avoid repeated deoptimization when
-  // speculatively hoisting checks.
   if (FLAG_trace_optimization) {
     OS::Print("Hoisting instruction %s:%"Pd" from B%"Pd" to B%"Pd"\n",
               current->DebugName(),
               current->GetDeoptId(),
               current->GetBlock()->block_id(),
               pre_header->block_id());
   }
   // Move the instruction out of the loop.
   current->RemoveEnvironment();
   it->RemoveCurrentFromGraph();
@@ skipping 35 matching lines @@
       }
     }
   }
 
   if ((non_smi_input == kNotFound) ||
       (phi->block()->PredecessorAt(non_smi_input) != pre_header)) {
     return;
   }
 
   // Host CheckSmi instruction and make this phi smi one.
-  Hoist(it, pre_header, current);
+  if (MayHoist(current, pre_header)) Hoist(it, pre_header, current);
 
   // Replace value we are checking with phi's input.
   current->value()->BindTo(phi->InputAt(non_smi_input)->definition());
 
   phi->UpdateType(CompileType::FromCid(kSmiCid));
 }
 
 
 static bool IsLoopInvariantLoad(ZoneGrowableArray<BitVector*>* sets,
                                 intptr_t loop_header_index,
                                 Instruction* instr) {
   return (sets != NULL) &&
       instr->HasExprId() &&
       ((*sets)[loop_header_index] != NULL) &&
       (*sets)[loop_header_index]->Contains(instr->expr_id());
 }
 
 
+bool LICM::MayHoist(Instruction* instr, BlockEntryInstr* pre_header) {
+  // TODO(fschneider): Enable hoisting of Assert-instructions
+  // if it safe to do.
+  if (instr->IsAssertAssignable()) return false;
+  if (instr->IsAssertBoolean()) return false;
+
+  if (instr->CanDeoptimize()) {
+    intptr_t target_deopt_id =
+        pre_header->last_instruction()->AsGoto()->GetDeoptId();
+    const Function& function = flow_graph_->parsed_function().function();
+    const Array& deopt_history = Array::Handle(function.deopt_history());
+    if (deopt_history.IsNull()) return true;
+
+    for (intptr_t i = 0; i < deopt_history.Length(); ++i) {
+      const Object& obj = Object::Handle(deopt_history.At(i));
+      if (obj.IsNull()) continue;

[Kevin Millikin (Google), 2013/05/24 11:39:21]

If you just delete this line, I think the result is exactly the same.

[Florian Schneider, 2013/05/24 11:53:02]

Done.

+      if (obj.IsSmi() && Smi::Cast(obj).Value() == target_deopt_id) {

[Kevin Millikin (Google), 2013/05/24 11:39:21]

Can it be non-smi (other than null)?  The Smi::Cast will assert it is.  If it's
always smi or null you can just use:

Smi& deopt_id = Smi::Handle();
deopt_id ^= deopt_history.At(i);
if (!deopt_id.IsNull() && (deopt_id.Value() == target)) {
  return false;
}

[Florian Schneider, 2013/05/24 11:53:02]

Done.

+        return false;
+      }
+    }
+  }
+  return true;
+}
+
+
 void LICM::Optimize() {
   const ZoneGrowableArray<BlockEntryInstr*>& loop_headers =
       flow_graph()->loop_headers();
 
   ZoneGrowableArray<BitVector*>* loop_invariant_loads =
       flow_graph()->loop_invariant_loads();
 
   BlockEffects* block_effects = flow_graph()->block_effects();
 
   for (intptr_t i = 0; i < loop_headers.length(); ++i) {
@@ skipping 14 matching lines @@
              block_effects->CanBeMovedTo(current, pre_header)) ||
              IsLoopInvariantLoad(loop_invariant_loads, i, current)) {
           bool inputs_loop_invariant = true;
           for (int i = 0; i < current->InputCount(); ++i) {
             Definition* input_def = current->InputAt(i)->definition();
             if (!input_def->GetBlock()->Dominates(pre_header)) {
               inputs_loop_invariant = false;
               break;
             }
           }
-          if (inputs_loop_invariant &&
-              !current->IsAssertAssignable() &&
-              !current->IsAssertBoolean()) {
-            // TODO(fschneider): Enable hoisting of Assert-instructions
-            // if it safe to do.
+          if (inputs_loop_invariant && MayHoist(current, pre_header)) {
             Hoist(&it, pre_header, current);
           } else if (current->IsCheckSmi() &&
                      current->InputAt(0)->definition()->IsPhi()) {
             TryHoistCheckSmiThroughPhi(
                 &it, header, pre_header, current->AsCheckSmi());
           }
         }
       }
     }
   }
@@ skipping 2968 matching lines @@
 
   // Insert materializations at environment uses.
   const Class& cls = Class::Handle(alloc->constructor().Owner());
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, cls, *fields);
   }
 }
 
 
 }  // namespace dart