Reland of [ignition/turbo] Perform liveness analysis on the bytecodes

src/compiler/bytecode-analysis.h

 // Copyright 2016 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_COMPILER_BYTECODE_ANALYSIS_H_
 #define V8_COMPILER_BYTECODE_ANALYSIS_H_
 
+#include "src/base/hashmap.h"
+#include "src/bit-vector.h"
 #include "src/handles.h"
 #include "src/zone/zone-containers.h"
 
 namespace v8 {
 namespace internal {
 
 class BytecodeArray;
 
 namespace compiler {
 
 class BytecodeAnalysis BASE_EMBEDDED {
  public:
   BytecodeAnalysis(Handle<BytecodeArray> bytecode_array, Zone* zone);
 
   // Analyze the bytecodes to find the loop ranges and nesting. No other
   // methods in this class return valid information until this has been called.
   void Analyze();
 
   // Return true if the given offset is a loop header
   bool IsLoopHeader(int offset) const;
   // Get the loop header offset of the containing loop for arbitrary
   // {offset}, or -1 if the {offset} is not inside any loop.
   int GetLoopOffsetFor(int offset) const;
   // Gets the loop header offset of the parent loop of the loop header
   // at {header_offset}, or -1 for outer-most loops.
   int GetParentLoopFor(int header_offset) const;
 
+  const BitVector* GetInLivenessFor(int offset) const;
+
+  const BitVector* GetOutLivenessFor(int offset) const;
+
+  struct Liveness {
+    BitVector* in;
+    BitVector* out;
+
+    Liveness(int size, Zone* zone);
+  };
+
+  typedef base::TemplateHashMapImpl<
+      int, Liveness, base::KeyEqualityMatcher<int>, ZoneAllocationPolicy>
+      LivenessMap;

[Jarin, 2016/11/24 12:47:17]

Does this offer significant advantage over std::unordered_map?

[Leszek Swirski, 2016/11/25 17:31:27]

I haven't measured here, but I've measured advantages over std::unordered_map
elsewhere (in the ConstantArrayBuilder).

Might be worth revisiting, but I want to think harder about the data structure
here anyway (in a subsequent CL) because I think we can take advantage of the
fact that offsets are reasonably dense and often accessed in order.

+
  private:
   void PushLoop(int loop_header, int loop_end);
 
   Zone* zone() const { return zone_; }
   Handle<BytecodeArray> bytecode_array() const { return bytecode_array_; }
 
   Handle<BytecodeArray> bytecode_array_;
   Zone* zone_;
 
   ZoneStack<int> loop_stack_;
 
   ZoneMap<int, int> end_to_header_;
   ZoneMap<int, int> header_to_parent_;
 
+  LivenessMap liveness_;
+
   DISALLOW_COPY_AND_ASSIGN(BytecodeAnalysis);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_BYTECODE_ANALYSIS_H_