Weight variables by their number of uses for register allocation.

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.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 314 matching lines @@
   const static uint32_t Zero = 0; /// Force regalloc NOT to give a register
   void addWeight(uint32_t Delta) {
     if (Delta == Inf)
       Weight = Inf;
     else if (Weight != Inf)
       Weight += Delta;
   }
   void addWeight(const RegWeight &Other) { addWeight(Other.Weight); }
   void setWeight(uint32_t Val) { Weight = Val; }
   uint32_t getWeight() const { return Weight; }
-  bool isInf() const { return Weight == Inf; }
-  bool isZero() const { return Weight == Zero; }
 
 private:
   uint32_t Weight = 0;
 };
 Ostream &operator<<(Ostream &Str, const RegWeight &W);
 bool operator<(const RegWeight &A, const RegWeight &B);
 bool operator<=(const RegWeight &A, const RegWeight &B);
 bool operator==(const RegWeight &A, const RegWeight &B);
 
 /// LiveRange is a set of instruction number intervals representing
 /// a variable's live range.  Generally there is one interval per basic
 /// block where the variable is live, but adjacent intervals get
-/// coalesced into a single interval.  LiveRange also includes a
-/// weight, in case e.g. we want a live range to have higher weight
-/// inside a loop.
+/// coalesced into a single interval.
 class LiveRange {
 public:
   LiveRange() = default;
   /// Special constructor for building a kill set.  The advantage is
   /// that we can reserve the right amount of space in advance.
   explicit LiveRange(const std::vector<InstNumberT> &Kills) {
     Range.reserve(Kills.size());
     for (InstNumberT I : Kills)
       addSegment(I, I);
   }
   LiveRange(const LiveRange &) = default;
   LiveRange &operator=(const LiveRange &) = default;
 
   void reset() {
     Range.clear();
-    Weight.setWeight(0);
     untrim();
   }
   void addSegment(InstNumberT Start, InstNumberT End);
 
   bool endsBefore(const LiveRange &Other) const;
   bool overlaps(const LiveRange &Other, bool UseTrimmed = false) const;
   bool overlapsInst(InstNumberT OtherBegin, bool UseTrimmed = false) const;
   bool containsValue(InstNumberT Value, bool IsDest) const;
   bool isEmpty() const { return Range.empty(); }
   InstNumberT getStart() const {
     return Range.empty() ? -1 : Range.begin()->first;
   }
   InstNumberT getEnd() const {
     return Range.empty() ? -1 : Range.rbegin()->second;
   }
 
   void untrim() { TrimmedBegin = Range.begin(); }
   void trim(InstNumberT Lower);
 
-  RegWeight getWeight() const { return Weight; }
-  void setWeight(const RegWeight &NewWeight) { Weight = NewWeight; }
-  void addWeight(uint32_t Delta) { Weight.addWeight(Delta); }
   void dump(Ostream &Str) const;
 
 private:
   typedef std::pair<InstNumberT, InstNumberT> RangeElementType;
   /// RangeType is arena-allocated from the Cfg's allocator.
   typedef std::vector<RangeElementType, CfgLocalAllocator<RangeElementType>>
       RangeType;
   RangeType Range;
-  RegWeight Weight = RegWeight(0);
   /// TrimmedBegin is an optimization for the overlaps() computation.
   /// Since the linear-scan algorithm always calls it as overlaps(Cur)
   /// and Cur advances monotonically according to live range start, we
   /// can optimize overlaps() by ignoring all segments that end before
   /// the start of Cur's range.  The linear-scan code enables this by
   /// calling trim() on the ranges of interest as Cur advances.  Note
   /// that linear-scan also has to initialize TrimmedBegin at the
   /// beginning by calling untrim().
   RangeType::const_iterator TrimmedBegin;
 };
 
 Ostream &operator<<(Ostream &Str, const LiveRange &L);
 
 /// Variable represents an operand that is register-allocated or
 /// stack-allocated.  If it is register-allocated, it will ultimately
 /// have a non-negative RegNum field.
 class Variable : public Operand {
   Variable() = delete;
   Variable(const Variable &) = delete;
   Variable &operator=(const Variable &) = delete;
 
+  enum RegRequirement {
+    RR_MayHaveRegister,
+    RR_MustHaveRegister,
+    RR_MustNotHaveRegister,
+  };
+
 public:
   static Variable *create(Cfg *Func, Type Ty, SizeT Index) {
     return new (Func->allocate<Variable>()) Variable(kVariable, Ty, Index);
   }
 
   SizeT getIndex() const { return Number; }
   IceString getName(const Cfg *Func) const;
   void setName(Cfg *Func, const IceString &NewName) {
     // Make sure that the name can only be set once.
     assert(NameIndex == Cfg::IdentifierIndexInvalid);
@@ skipping 17 matching lines @@
   int32_t getRegNum() const { return RegNum; }
   void setRegNum(int32_t NewRegNum) {
     // Regnum shouldn't be set more than once.
     assert(!hasReg() || RegNum == NewRegNum);
     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 = RegWeight(NewWeight); }
-  void setWeightInfinite() { setWeight(RegWeight::Inf); }
+  RegWeight getWeight(const Cfg *Func) const;
+
+  void setMustHaveReg() { RegRequirement = RR_MustHaveRegister; }
+  bool mustHaveReg() const { return RegRequirement == RR_MustHaveRegister; }
+  void setMustNotHaveReg() { RegRequirement = RR_MustNotHaveRegister; }
+  bool mustNotHaveReg() const {
+    return RegRequirement == RR_MustNotHaveRegister;
+  }
 
   LiveRange &getLiveRange() { return Live; }
   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) {
+  void addLiveRange(InstNumberT Start, InstNumberT End) {
     assert(!getIgnoreLiveness());
-    assert(WeightDelta != RegWeight::Inf);
     Live.addSegment(Start, End);
-    if (Weight.isInf())
-      Live.setWeight(RegWeight(RegWeight::Inf));
-    else
-      Live.addWeight(WeightDelta * Weight.getWeight());
-  }
-  void setLiveRangeInfiniteWeight() {
-    Live.setWeight(RegWeight(RegWeight::Inf));
   }
   void trimLiveRange(InstNumberT Start) { Live.trim(Start); }
   void untrimLiveRange() { Live.untrim(); }
   bool rangeEndsBefore(const Variable *Other) const {
     return Live.endsBefore(Other->Live);
   }
   bool rangeOverlaps(const Variable *Other) const {
     const bool UseTrimmed = true;
     return Live.overlaps(Other->Live, UseTrimmed);
   }
   bool rangeOverlapsStart(const Variable *Other) const {
     const bool UseTrimmed = true;
     return Live.overlapsInst(Other->Live.getStart(), UseTrimmed);
   }
 
   Variable *getLo() const { return LoVar; }
   Variable *getHi() const { return HiVar; }
   void setLoHi(Variable *Lo, Variable *Hi) {
     assert(LoVar == nullptr);
     assert(HiVar == nullptr);
     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 IsArgument, IsImplicitArgument, IgnoreLiveness,
   /// RegNumTmp, Weight, Live, LoVar, HiVar, VarsReal.

[jvoung (off chromium), 2015/08/28 20:31:45]

can remove Weight field comment too

[ascull, 2015/08/28 21:22:36]

Done.

   Variable *asType(Type Ty);
 
   void emit(const Cfg *Func) const override;
   using Operand::dump;
   void dump(const Cfg *Func, Ostream &Str) const override;
 
   /// Return reg num of base register, if different from stack/frame register.
   virtual int32_t getBaseRegNum() const { return NoRegister; }
 
   static bool classof(const Operand *Operand) {
@@ skipping 19 matching lines @@
   /// reserved for the stack pointer.
   bool IgnoreLiveness = false;
   /// StackOffset is the canonical location on stack (only if
   /// RegNum==NoRegister || IsArgument).
   int32_t StackOffset = 0;
   /// RegNum is the allocated register, or NoRegister if it isn't
   /// register-allocated.
   int32_t RegNum = NoRegister;
   /// RegNumTmp is the tentative assignment during register allocation.
   int32_t RegNumTmp = NoRegister;
-  RegWeight Weight = RegWeight(1); // Register allocation priority
+  /// \name Register allocation priority
+  /// @{
+  RegRequirement RegRequirement = RR_MayHaveRegister;
+  /// @}
   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 = nullptr;
   Variable *HiVar = nullptr;
@@ skipping 24 matching lines @@
   };
   enum MultiBlockState { MBS_Unknown, MBS_SingleBlock, MBS_MultiBlock };
   VariableTracking() = default;
   VariableTracking(const VariableTracking &) = default;
   MultiDefState getMultiDef() const { return MultiDef; }
   MultiBlockState getMultiBlock() const { return MultiBlock; }
   const Inst *getFirstDefinition() const;
   const Inst *getSingleDefinition() const;
   const InstDefList &getLatterDefinitions() const { return Definitions; }
   CfgNode *getNode() const { return SingleUseNode; }
+  uint32_t getUseWeight() const { return UseWeight; }
   void markUse(MetadataKind TrackingKind, const Inst *Instr, CfgNode *Node,
                bool IsImplicit);
   void markDef(MetadataKind TrackingKind, const Inst *Instr, CfgNode *Node);
 
 private:
   MultiDefState MultiDef = MDS_Unknown;
   MultiBlockState MultiBlock = MBS_Unknown;
   CfgNode *SingleUseNode = nullptr;
   CfgNode *SingleDefNode = nullptr;
   /// All definitions of the variable are collected here, in increasing
   /// order of instruction number.
   InstDefList Definitions; /// Only used if Kind==VMK_All
   const Inst *FirstOrSingleDefinition =
       nullptr; /// Is a copy of Definitions[0] if Kind==VMK_All
+  uint32_t UseWeight = 0;
 };
 
-/// VariablesMetadata analyzes and summarizes the metadata for the
-/// complete set of Variables.
+/// VariablesMetadata analyzes and summarizes the metadata for the complete set
+/// of Variables.
 class VariablesMetadata {
   VariablesMetadata() = delete;
   VariablesMetadata(const VariablesMetadata &) = delete;
   VariablesMetadata &operator=(const VariablesMetadata &) = delete;
 
 public:
   explicit VariablesMetadata(const Cfg *Func) : Func(Func) {}
   /// Initialize the state by traversing all instructions/variables in
   /// the CFG.
   void init(MetadataKind TrackingKind);
   /// Add a single node.  This is called by init(), and can be called
   /// incrementally from elsewhere, e.g. after edge-splitting.
   void addNode(CfgNode *Node);
-  /// 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).
+  /// 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, nullptr is returned.
+  /// 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, nullptr 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, nullptr is
   /// returned.
   const Inst *getSingleDefinition(const Variable *Var) const;
-  /// Returns the list of all definition instructions of the given
-  /// Variable.
+  /// Returns the list of all definition instructions of the given Variable.
   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, nullptr is returned.
   CfgNode *getLocalUseNode(const Variable *Var) const;
 
+  /// Returns the total use weight computed as the sum of uses multiplied by a
+  /// loop nest depth facter for each use.

[jvoung (off chromium), 2015/08/28 20:31:45]

facter -> factor

[ascull, 2015/08/28 21:22:36]

Done.

+  uint32_t getUseWeight(const Variable *Var) const;
+
 private:
   const Cfg *Func;
   MetadataKind Kind;
   std::vector<VariableTracking> Metadata;
   const static InstDefList NoDefinitions;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEOPERAND_H