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,

[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);
 
   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