First simplistic implementation of escape analysis.

src/hydrogen.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 2595 matching lines @@
         if (!in_worklist.Contains(use->id())) {
           in_worklist.Add(use->id());
           worklist->Add(use, zone());
         }
       }
     }
   }
 }
 
 
+class HEscapeAnalysis BASE_EMBEDDED {
+ public:
+  explicit HEscapeAnalysis(HGraph* graph)
+      : graph_(graph), zone_(graph->zone()), captured_(0, zone_) { }
+
+  void Analyze();
+
+ private:
+  void CollectCapturedValues();
+  void CollectIfNoEscapingUses(HInstruction* instr);
+
+  HGraph* graph_;
+  Zone* zone_;
+  ZoneList<HValue*> captured_;
+};
+
+
+void HEscapeAnalysis::CollectIfNoEscapingUses(HInstruction* instr) {
+  for (HUseIterator it(instr->uses()); !it.Done(); it.Advance()) {
+    HValue* use = it.value();
+    if (use->HasEscapingOperandAt(it.index())) {
+      if (FLAG_trace_escape_analysis) {
+        PrintF("#%d (%s) escapes through #%d (%s) @%d\n", instr->id(),
+               instr->Mnemonic(), use->id(), use->Mnemonic(), it.index());
+      }
+      return;
+    }
+  }
+  if (FLAG_trace_escape_analysis) {
+    PrintF("#%d (%s) is being captured\n", instr->id(), instr->Mnemonic());
+  }
+  captured_.Add(instr, zone_);
+}
+
+
+void HEscapeAnalysis::CollectCapturedValues() {
+  int block_count = graph_->blocks()->length();
+  for (int i = 0; i < block_count; ++i) {
+    HBasicBlock* block = graph_->blocks()->at(i);
+    HInstruction* instr = block->first();
+    while (instr != block->end()) {

[Sven Panne, 2013/06/27 07:18:23]

A for-loop would be more readable. We really need some iterators... :-P

[Michael Starzinger, 2013/06/27 08:17:13]

Done. You want an iterator? I give you an iterator. :)

+      if (instr->IsAllocate() || instr->IsAllocateObject()) {
+        CollectIfNoEscapingUses(instr);
+      }
+      instr = instr->next();
+    }
+  }
+}
+
+
+void HEscapeAnalysis::Analyze() {
+  HPhase phase("H_Escape analysis", graph_);
+  CollectCapturedValues();
+}
+
+
 class HRangeAnalysis BASE_EMBEDDED {
  public:
   explicit HRangeAnalysis(HGraph* graph) :
       graph_(graph), zone_(graph->zone()), changed_ranges_(16, zone_) { }
 
   void Analyze();
 
  private:
   void TraceRange(const char* msg, ...);
   void Analyze(HBasicBlock* block);
@@ skipping 1350 matching lines @@
   // Do a full verify after building the graph and computing dominators.
   Verify(true);
 #endif
 
   if (FLAG_analyze_environment_liveness) {
     EnvironmentSlotLivenessAnalyzer esla(this);
     esla.AnalyzeAndTrim();
   }
 
   PropagateDeoptimizingMark();
+
   if (!CheckConstPhiUses()) {
     *bailout_reason = SmartArrayPointer<char>(StrDup(
         "Unsupported phi use of const variable"));
     return false;
   }
   EliminateRedundantPhis();
   if (!CheckArgumentsPhiUses()) {
     *bailout_reason = SmartArrayPointer<char>(StrDup(
         "Unsupported phi use of arguments"));
     return false;
@@ skipping 26 matching lines @@
 
   InitializeInferredTypes();
 
   // Must be performed before canonicalization to ensure that Canonicalize
   // will not remove semantically meaningful ToInt32 operations e.g. BIT_OR with
   // zero.
   if (FLAG_opt_safe_uint32_operations) ComputeSafeUint32Operations();
 
   if (FLAG_use_canonicalizing) Canonicalize();
 
+  if (FLAG_use_escape_analysis) {
+    HEscapeAnalysis escapeAnalysis(this);
+    escapeAnalysis.Analyze();
+  }
+
   if (FLAG_use_gvn) GlobalValueNumbering();
 
   if (FLAG_use_range) {
     HRangeAnalysis rangeAnalysis(this);
     rangeAnalysis.Analyze();
   }
   ComputeMinusZeroChecks();
 
   // Eliminate redundant stack checks on backwards branches.
   HStackCheckEliminator sce(this);
@@ skipping 7512 matching lines @@
   if (ShouldProduceTraceOutput()) {
     isolate()->GetHTracer()->TraceHydrogen(name(), graph_);
   }
 
 #ifdef DEBUG
   graph_->Verify(false);  // No full verify.
 #endif
 }
 
 } }  // namespace v8::internal