Subzero: Improve performance of liveness analysis and live range construction.

src/IceDefs.h

 //===- subzero/src/IceDefs.h - Common Subzero declaraions -------*- C++ -*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file declares various useful types and classes that have
@@ skipping 51 matching lines @@
 
 // SizeT is for holding small-ish limits like number of source
 // operands in an instruction.  It is used instead of size_t (which
 // may be 64-bits wide) when we want to save space.
 typedef uint32_t SizeT;
 
 // InstNumberT is for holding an instruction number.  Instruction
 // numbers are used for representing Variable live ranges.
 typedef int32_t InstNumberT;
 
+typedef llvm::BitVector LivenessBV;
+typedef std::pair<SizeT, InstNumberT> BeginEndMapEntry;

[jvoung (off chromium), 2014/10/13 20:50:50]

Could you leave a comment about the structure of the BeginEndMaps? (what is the
SizeT in the pairs?).

Also, it might be good to call the type LiveBeginEnd..., though that's a bit
longer and the variable names usually have "Live" in it...

[Jim Stichnoth, 2014/10/13 23:15:22]

Both suggestions done.

+typedef std::vector<BeginEndMapEntry> BeginEndMap;
+
 typedef uint32_t TimerStackIdT;
 typedef uint32_t TimerIdT;
 
 enum LivenessMode {
   // Basic version of live-range-end calculation.  Marks the last uses
   // of variables based on dataflow analysis.  Records the set of
   // live-in and live-out variables for each block.  Identifies and
   // deletes dead instructions (primarily stores).
   Liveness_Basic,
 
@@ skipping 19 matching lines @@
   IceV_All = ~IceV_None,
   IceV_Most = IceV_All & ~IceV_LinearScan
 };
 typedef uint32_t VerboseMask;
 
 typedef llvm::raw_ostream Ostream;
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEDEFS_H