Subzero: Automatically infer regalloc preferences and overlap.

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 367 matching lines @@
     RegNum = NewRegNum;
   }
   bool hasRegTmp() const { return getRegNumTmp() != NoRegister; }
   int32_t getRegNumTmp() const { return RegNumTmp; }
   void setRegNumTmp(int32_t NewRegNum) { RegNumTmp = NewRegNum; }
 
   RegWeight getWeight() const { return Weight; }
   void setWeight(uint32_t NewWeight) { Weight = NewWeight; }
   void setWeightInfinite() { Weight = RegWeight::Inf; }
 
-  Variable *getPreferredRegister() const { return RegisterPreference; }
-  bool getRegisterOverlap() const { return AllowRegisterOverlap; }
-  void setPreferredRegister(Variable *Prefer, bool Overlap) {
-    RegisterPreference = Prefer;
-    AllowRegisterOverlap = Overlap;
-  }
-
   const LiveRange &getLiveRange() const { return Live; }
   void setLiveRange(const LiveRange &Range) { Live = Range; }
   void resetLiveRange() { Live.reset(); }
   void addLiveRange(InstNumberT Start, InstNumberT End, uint32_t WeightDelta) {
     assert(WeightDelta != RegWeight::Inf);
     Live.addSegment(Start, End);
     if (Weight.isInf())
       Live.setWeight(RegWeight::Inf);
     else
       Live.addWeight(WeightDelta * Weight.getWeight());
   }
   void setLiveRangeInfiniteWeight() { Live.setWeight(RegWeight::Inf); }
 
   Variable *getLo() const { return LoVar; }
   Variable *getHi() const { return HiVar; }
   void setLoHi(Variable *Lo, Variable *Hi) {
     assert(LoVar == NULL);
     assert(HiVar == NULL);
     LoVar = Lo;
     HiVar = Hi;
   }
   // Creates a temporary copy of the variable with a different type.
   // Used primarily for syntactic correctness of textual assembly
   // emission.  Note that only basic information is copied, in
-  // particular not DefInst, IsArgument, Weight, RegisterPreference,
-  // AllowRegisterOverlap, LoVar, HiVar, VarsReal.
+  // particular not DefInst, IsArgument, Weight, LoVar, HiVar,
+  // VarsReal.
   Variable asType(Type Ty);
 
   virtual void emit(const Cfg *Func) const;
   using Operand::dump;
   virtual void dump(const Cfg *Func, Ostream &Str) const;
 
   static bool classof(const Operand *Operand) {
     OperandKind Kind = Operand->getKind();
     return Kind >= kVariable && Kind <= kVariable_Num;
   }
 
   // The destructor is public because of the asType() method.
   virtual ~Variable() {}
 
 protected:
   Variable(OperandKind K, Type Ty, SizeT Index, const IceString &Name)
       : Operand(K, Ty), Number(Index), Name(Name), IsArgument(false),
         IsImplicitArgument(false), StackOffset(0), RegNum(NoRegister),
-        RegNumTmp(NoRegister), Weight(1), RegisterPreference(NULL),
-        AllowRegisterOverlap(false), LoVar(NULL), HiVar(NULL) {
+        RegNumTmp(NoRegister), Weight(1), LoVar(NULL), HiVar(NULL) {
     Vars = VarsReal;
     Vars[0] = this;
     NumVars = 1;
   }
   // Number is unique across all variables, and is used as a
   // (bit)vector index for liveness analysis.
   const SizeT Number;
   // Name is optional.
   IceString Name;
   bool IsArgument;
   bool IsImplicitArgument;
   // StackOffset is the canonical location on stack (only if
-  // RegNum<0 || IsArgument).
+  // RegNum==NoRegister || IsArgument).
   int32_t StackOffset;
   // RegNum is the allocated register, or NoRegister if it isn't
   // register-allocated.
   int32_t RegNum;
   // RegNumTmp is the tentative assignment during register allocation.
   int32_t RegNumTmp;
   RegWeight Weight; // Register allocation priority
-  // RegisterPreference says that if possible, the register allocator
-  // should prefer the register that was assigned to this linked
-  // variable.  It also allows a spill slot to share its stack
-  // location with another variable, if that variable does not get
-  // register-allocated and therefore has a stack location.
-  Variable *RegisterPreference;
-  // AllowRegisterOverlap says that it is OK to honor
-  // RegisterPreference and "share" a register even if the two live
-  // ranges overlap.
-  bool AllowRegisterOverlap;
   LiveRange Live;
   // LoVar and HiVar are needed for lowering from 64 to 32 bits.  When
   // lowering from I64 to I32 on a 32-bit architecture, we split the
   // variable into two machine-size pieces.  LoVar is the low-order
   // machine-size portion, and HiVar is the remaining high-order
   // 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];
 };
 
-// VariableTracking tracks the metadata for a single variable.
+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_MultiDef
+    MDS_MultiDefSingleBlock,
+    MDS_MultiDefMultiBlock
   };
   enum MultiBlockState {
     MBS_Unknown,
     MBS_SingleBlock,
     MBS_MultiBlock
   };
   VariableTracking()
       : MultiDef(MDS_Unknown), MultiBlock(MBS_Unknown), SingleUseNode(NULL),
-        SingleDefInst(NULL) {}
+        SingleDefNode(NULL) {}
   MultiDefState getMultiDef() const { return MultiDef; }
   MultiBlockState getMultiBlock() const { return MultiBlock; }
-  const Inst *getDefinition() const { return SingleDefInst; }
+  const Inst *getFirstDefinition() const;
+  const Inst *getSingleDefinition() const;
+  const InstDefList &getDefinitions() 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);
 
 private:
   VariableTracking &operator=(const VariableTracking &) LLVM_DELETED_FUNCTION;
   MultiDefState MultiDef;
   MultiBlockState MultiBlock;
   const CfgNode *SingleUseNode;
-  const Inst *SingleDefInst;
+  const CfgNode *SingleDefNode;
+  // All definitions of the variable are collected here, in the order
+  // encountered.  Definitions in the same basic block are in
+  // instruction order, but there's no guarantee for the basic block
+  // order.
+  InstDefList Definitions;
 };
 
 // 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();
+  // 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;
-  const Inst *getDefinition(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;
+
+  // 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;
   std::vector<VariableTracking> Metadata;
+  const static InstDefList NoDefinitions;
   VariablesMetadata(const VariablesMetadata &) LLVM_DELETED_FUNCTION;
   VariablesMetadata &operator=(const VariablesMetadata &) LLVM_DELETED_FUNCTION;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEOPERAND_H