Liveness analysis for environment slots in Hydrogen

src/hydrogen-environment-liveness.h

Index: src/hydrogen-environment-liveness.h
diff --git a/src/hydrogen-environment-liveness.h b/src/hydrogen-environment-liveness.h
new file mode 100644
index 0000000000000000000000000000000000000000..09c5c2eb74c881effcd2df67c5c660e97a7e4bc2
--- /dev/null
+++ b/src/hydrogen-environment-liveness.h
@@ -0,0 +1,100 @@
+// Copyright 2013 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
+//       with the distribution.
+//     * Neither the name of Google Inc. nor the names of its
+//       contributors may be used to endorse or promote products derived
+//       from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#ifndef V8_HYDROGEN_ENVIRONMENT_LIVENESS_H_
+#define V8_HYDROGEN_ENVIRONMENT_LIVENESS_H_
+
+
+#include "hydrogen.h"
+
+namespace v8 {
+namespace internal {
+
+

[titzer, 2013/05/29 16:58:05]

Documentation. At least a sentence. Perhaps EnvironmentSlotLivenessAnalyzer
instead of *Analysis?

[Jakob Kummerow, 2013/06/03 17:50:38]

Done.

+class EnvironmentSlotLivenessAnalysis {
+ public:
+  explicit EnvironmentSlotLivenessAnalysis(HGraph* graph)

[titzer, 2013/05/29 16:58:05]

Please put this constructor in the .cc file, if C++ will allow you.

[Jakob Kummerow, 2013/06/03 17:50:38]

Done. Good point, dunno why it didn't occur to me before.

+      : graph_(graph),
+        zone_(graph->isolate()),
+        zone_scope_(&zone_, DELETE_ON_EXIT),
+        block_count_(graph->blocks()->length()),
+        maximum_environment_size_(graph->maximum_environment_size()),
+        collect_markers_(true),
+        last_simulate_(NULL) {
+    if (maximum_environment_size_ == 0) return;
+
+    live_at_block_start_ =
+        new(zone()) ZoneList<BitVector*>(block_count_, zone());
+    first_simulate_ = new(zone()) ZoneList<HSimulate*>(block_count_, zone());
+    first_simulate_invalid_for_index_ =
+        new(zone()) ZoneList<BitVector*>(block_count_, zone());
+    markers_ = new(zone())
+        ZoneList<HEnvironmentMarker*>(maximum_environment_size_, zone());
+    live_ = new(zone()) BitVector(maximum_environment_size_, zone());
+    went_live_since_last_simulate_ =
+        new(zone()) BitVector(maximum_environment_size_, zone());
+
+    for (int i = 0; i < block_count_; ++i) {
+      live_at_block_start_->Add(
+          new(zone()) BitVector(maximum_environment_size_, zone()), zone());
+      first_simulate_->Add(NULL, zone());
+      first_simulate_invalid_for_index_->Add(
+          new(zone()) BitVector(maximum_environment_size_, zone()), zone());
+    }
+  }
+
+  void AnalyzeAndPrune();
+
+ private:
+  void ZapEnvironmentSlot(int index, HSimulate* simulate);
+  void ZapEnvironmentSlotsInSuccessors(HBasicBlock* block);
+  void ZapEnvironmentSlotsForInstruction(HEnvironmentMarker* marker);
+  void UpdateLivenessAtBlockEnd(HBasicBlock* block);
+  void UpdateLivenessAtInstruction(HInstruction* instr);
+
+  Zone* zone() { return &zone_; }
+
+  HGraph* graph_;
+  Zone zone_;
+  ZoneScope zone_scope_;

[titzer, 2013/05/29 16:58:05]

Would like to see some comments on these fields, e.g. that the various lists are
indexed by blockid.

[Jakob Kummerow, 2013/06/03 17:50:38]

Done.

+  int block_count_;
+  int maximum_environment_size_;
+  ZoneList<BitVector*>* live_at_block_start_;
+  ZoneList<HSimulate*>* first_simulate_;
+  ZoneList<BitVector*>* first_simulate_invalid_for_index_;
+  ZoneList<HEnvironmentMarker*>* markers_;
+
+  bool collect_markers_;
+  BitVector* live_;

[titzer, 2013/05/29 16:58:05]

I think it's best to turn this field into a local and pass it between the
various methods; following the effects in the Update* methods will be easier.

[Jakob Kummerow, 2013/06/03 17:50:38]

Done.

+  HSimulate* last_simulate_;
+  BitVector* went_live_since_last_simulate_;
+};
+
+
+} }  // namespace v8::internal
+
+#endif /* V8_HYDROGEN_ENVIRONMENT_LIVENESS_H_ */