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

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
diff --git a/runtime/vm/flow_graph_optimizer.cc b/runtime/vm/flow_graph_optimizer.cc
index 8e51cc26450f43e76d9d7ba878213d1bef33cb93..2b35df2e8c66299b08c57c7dbb2469328f04a8ff 100644
--- a/runtime/vm/flow_graph_optimizer.cc
+++ b/runtime/vm/flow_graph_optimizer.cc
@@ -1157,6 +1157,73 @@ static BlockEntryInstr* FindPreHeader(BlockEntryInstr* header) {
 }
 
 
+void LICM::Hoist(ForwardInstructionIterator* it,

[Florian Schneider, 2012/09/07 09:37:00]

You could make this a static top-level functions:

static void Hoist(...

[Vyacheslav Egorov (Google), 2012/09/07 12:06:00]

Unfortunately I can't: it uses friendship relation to access private state.

+                 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();

[srdjan, 2012/09/07 07:55:26]

Could you add tests that have deoptimization caused by optimistic hoisting of
smi checks? Have you observed them on any of benchmarks?

[Vyacheslav Egorov (Google), 2012/09/07 12:06:00]

Done.

+}
+
+
+void LICM::TryHoistCheckSmiThroughPhi(ForwardInstructionIterator* it,

[Florian Schneider, 2012/09/07 09:37:00]

You could make this a static top-level functions:

static void TryHoist(...

[Vyacheslav Egorov (Google), 2012/09/07 12:06:00]

See above.

+                                      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) {

[Florian Schneider, 2012/09/07 09:37:00]

It should not be necessary to check for redundant smi-checks here since they are
already eliminated in the Canonicalize pass. Right now, this pass is run before
LICM, but maybe we should do another round anyway later to catch secondary
effects.

[Vyacheslav Egorov (Google), 2012/09/07 12:06:00]

There are might be smi checks that are not dominated or come from the outer loop
after smi in the inner loop was promoted to smi. 

This allows to remove them quickly without any special processing:

outer:
  inner:
    phi1 = phi(v0, v1)
    check-smi phi1
  check-smi phi1 ;; <- this phi

+    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)) {

[Florian Schneider, 2012/09/07 09:37:00]

It's fine to have the restrict the block where the smi-check will be inserted to
only the pre-header for now.

As an improvement, you could allow non-smi predecessors other than the
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);

[srdjan, 2012/09/07 07:55:26]

Could/should we run type propagation after LICM again?

[Florian Schneider, 2012/09/07 09:37:00]

Yes, how about building  worklist of changed phis and process the worklist after
LICM finished?

A later pass (OptimizeComputations) would eliminate checks that become redundant
as a secondary effect.

[Vyacheslav Egorov (Google), 2012/09/07 12:06:00]

Yes, we can. For now I would like to keep it minimal to minimize impact on the
compile time.

+}
+
+
 void LICM::Optimize(FlowGraph* flow_graph) {
   GrowableArray<BlockEntryInstr*> loop_headers;
   flow_graph->ComputeLoops(&loop_headers);
@@ -1187,24 +1254,10 @@ void LICM::Optimize(FlowGraph* flow_graph) {
             }
           }
           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);
           }
         }
       }