Optimistically hoist SmiCheck through phi when the only value of unknown type coming into the phi i…

runtime/vm/flow_graph_optimizer.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_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/hash_map.h"
@@ skipping 1139 matching lines @@
   for (intptr_t j = 0; j < header->PredecessorCount(); ++j) {
     BlockEntryInstr* candidate = header->PredecessorAt(j);
     if (header->dominator() == candidate) {
       return candidate;
     }
   }
   return NULL;
 }
 
 
+void LICM::Hoist(ForwardInstructionIterator* it,
+                 BlockEntryInstr* pre_header,
+                 Definition* 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->deopt_id(),
+              current->GetBlock()->block_id(),
+              pre_header->block_id());
+  }
+  // Move the instruction out of the loop.
+  it->RemoveCurrentFromGraph();
+  GotoInstr* last = pre_header->last_instruction()->AsGoto();
+  current->InsertBefore(last);
+  // Attach the environment of the Goto instruction to the hoisted
+  // instruction and set the correct deopt_id.
+  ASSERT(last->env() != NULL);
+  last->env()->CopyTo(current);
+  current->deopt_id_ = last->GetDeoptId();
+}
+
+
+void LICM::TryHoistCheckSmiThroughPhi(ForwardInstructionIterator* it,
+                                      BlockEntryInstr* header,
+                                      BlockEntryInstr* pre_header,
+                                      Definition* current) {
+  PhiInstr* phi = current->InputAt(0)->definition()->AsPhi();
+  if (!header->loop_info()->Contains(phi->block()->preorder_number())) {
+    return;
+  }
+
+  if (phi->GetPropagatedCid() == kSmiCid) {
+    it->RemoveCurrentFromGraph();
+    return;
+  }
+
+  // Check if there is only a single kDynamicCid input to the phi that
+  // comes from the pre-header.
+  const intptr_t kNotFound = -1;
+  intptr_t non_smi_input = kNotFound;
+  for (intptr_t i = 0; i < phi->InputCount(); ++i) {
+    Value* input = phi->InputAt(i);
+    if (input->ResultCid() != kSmiCid) {
+      if ((non_smi_input != kNotFound) || (input->ResultCid() != kDynamicCid)) {
+        // There are multiple kDynamicCid inputs or there is an input that is
+        // known to be non-smi.
+        return;
+      } else {
+        non_smi_input = i;
+      }
+    }
+  }
+
+  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);
+  current->SetInputAt(non_smi_input, phi->InputAt(non_smi_input));
+  phi->SetPropagatedCid(kSmiCid);
+}
+
+
 void LICM::Optimize(FlowGraph* flow_graph) {
   GrowableArray<BlockEntryInstr*> loop_headers;
   flow_graph->ComputeLoops(&loop_headers);
 
   for (intptr_t i = 0; i < loop_headers.length(); ++i) {
     BlockEntryInstr* header = loop_headers[i];
     // Skip loop that don't have a pre-header block.
     BlockEntryInstr* pre_header = FindPreHeader(header);
     if (pre_header == NULL) continue;
 
@@ skipping 10 matching lines @@
             !current->HasSideEffect()) {
           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) {
-            // 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->deopt_id(),
-                        current->GetBlock()->block_id(),
-                        pre_header->block_id());
-            }
-            // Move the instruction out of the loop.
-            it.RemoveCurrentFromGraph();
-            GotoInstr* last = pre_header->last_instruction()->AsGoto();
-            current->InsertBefore(last);
-            // Attach the environment of the Goto instruction to the hoisted
-            // instruction and set the correct deopt_id.
-            ASSERT(last->env() != NULL);
-            last->env()->CopyTo(current);
-            current->deopt_id_ = last->GetDeoptId();
+            Hoist(&it, pre_header, current);
+          } else if (current->IsCheckSmi() &&
+                     current->InputAt(0)->definition()->IsPhi()) {
+            TryHoistCheckSmiThroughPhi(&it, header, pre_header, current);
           }
         }
       }
     }
   }
 }
 
 
 void DominatorBasedCSE::Optimize(BlockEntryInstr* graph_entry) {
   ASSERT(graph_entry->IsGraphEntry());
@@ skipping 31 matching lines @@
       DirectChainedHashMap<Definition*> child_map(*map);  // Copy map.
       OptimizeRecursive(child, &child_map);
     } else {
       OptimizeRecursive(child, map);  // Reuse map for the last child.
     }
   }
 }
 
 
 }  // namespace dart