Subzero: Speed up VariablesMetadata initialization.

src/IceOperand.h

 //===- subzero/src/IceOperand.h - High-level operands -----------*- 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 the Operand class and its target-independent
@@ skipping 493 matching lines @@
   // portion.  TODO: It's wasteful to penalize all variables on all
   // targets this way; use a sparser representation.  It's also
   // wasteful for a 64-bit target.
   Variable *LoVar;
   Variable *HiVar;
   // VarsReal (and Operand::Vars) are set up such that Vars[0] ==
   // this.
   Variable *VarsReal[1];
 };
 
+enum MetadataKind {
+  VMK_Uses,       // Track only uses, not defs
+  VMK_SingleDefs, // Track uses+defs, but only record single def
+  VMK_All         // Track uses+defs, including full def list
+};
 typedef std::vector<const Inst *> InstDefList;
 
 // VariableTracking tracks the metadata for a single variable.  It is
 // only meant to be used internally by VariablesMetadata.
 class VariableTracking {
 public:
   enum MultiDefState {
     // TODO(stichnot): Consider using just a simple counter.
     MDS_Unknown,
     MDS_SingleDef,
     MDS_MultiDefSingleBlock,
     MDS_MultiDefMultiBlock
   };
   enum MultiBlockState {
     MBS_Unknown,
     MBS_SingleBlock,
     MBS_MultiBlock
   };
   VariableTracking()
       : MultiDef(MDS_Unknown), MultiBlock(MBS_Unknown), SingleUseNode(NULL),
-        SingleDefNode(NULL) {}
+        SingleDefNode(NULL), FirstOrSingleDefinition(NULL) {}
   MultiDefState getMultiDef() const { return MultiDef; }
   MultiBlockState getMultiBlock() const { return MultiBlock; }
   const Inst *getFirstDefinition() const;
   const Inst *getSingleDefinition() const;
-  const InstDefList &getDefinitions() const { return Definitions; }
+  const InstDefList &getLatterDefinitions() const { return Definitions; }
   const CfgNode *getNode() const { return SingleUseNode; }
-  void markUse(const Inst *Instr, const CfgNode *Node, bool IsFromDef,
-               bool IsImplicit);
-  void markDef(const Inst *Instr, const CfgNode *Node);
+  void markUse(MetadataKind TrackingKind, const Inst *Instr,
+               const CfgNode *Node, bool IsFromDef, bool IsImplicit);
+  void markDef(MetadataKind TrackingKind, const Inst *Instr,
+               const CfgNode *Node);
 
 private:
   VariableTracking &operator=(const VariableTracking &) = delete;
   MultiDefState MultiDef;
   MultiBlockState MultiBlock;
   const CfgNode *SingleUseNode;
   const CfgNode *SingleDefNode;
   // All definitions of the variable are collected here, in increasing
   // order of instruction number.
-  InstDefList Definitions;
+  InstDefList Definitions;             // Only used if Kind==VMK_All
+  const Inst *FirstOrSingleDefinition; // == Definitions[0] if Kind==VMK_All
 };
 
 // VariablesMetadata analyzes and summarizes the metadata for the
 // complete set of Variables.
 class VariablesMetadata {
 public:
   VariablesMetadata(const Cfg *Func) : Func(Func) {}
   // Initialize the state by traversing all instructions/variables in
   // the CFG.
-  void init();
+  void init(MetadataKind TrackingKind);
   // Returns whether the given Variable is tracked in this object.  It
   // should only return false if changes were made to the CFG after
   // running init(), in which case the state is stale and the results
   // shouldn't be trusted (but it may be OK e.g. for dumping).
   bool isTracked(const Variable *Var) const {
     return Var->getIndex() < Metadata.size();
   }
 
   // Returns whether the given Variable has multiple definitions.
   bool isMultiDef(const Variable *Var) const;
   // Returns the first definition instruction of the given Variable.
   // This is only valid for variables whose definitions are all within
   // the same block, e.g. T after the lowered sequence "T=B; T+=C;
   // A=T", for which getFirstDefinition(T) would return the "T=B"
   // instruction.  For variables with definitions span multiple
   // blocks, NULL is returned.
   const Inst *getFirstDefinition(const Variable *Var) const;
   // Returns the definition instruction of the given Variable, when
   // the variable has exactly one definition.  Otherwise, NULL is
   // returned.
   const Inst *getSingleDefinition(const Variable *Var) const;
   // Returns the list of all definition instructions of the given
   // Variable.
-  const InstDefList &getDefinitions(const Variable *Var) const;
+  const InstDefList &getLatterDefinitions(const Variable *Var) const;
 
   // Returns whether the given Variable is live across multiple
   // blocks.  Mainly, this is used to partition Variables into
   // single-block versus multi-block sets for leveraging sparsity in
   // liveness analysis, and for implementing simple stack slot
   // coalescing.  As a special case, function arguments are always
   // considered multi-block because they are live coming into the
   // entry block.
   bool isMultiBlock(const Variable *Var) const;
   // Returns the node that the given Variable is used in, assuming
   // isMultiBlock() returns false.  Otherwise, NULL is returned.
   const CfgNode *getLocalUseNode(const Variable *Var) const;
 
 private:
   const Cfg *Func;
+  MetadataKind Kind;
   std::vector<VariableTracking> Metadata;
   const static InstDefList NoDefinitions;
   VariablesMetadata(const VariablesMetadata &) = delete;
   VariablesMetadata &operator=(const VariablesMetadata &) = delete;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEOPERAND_H