1 //===- subzero/src/IceRegAlloc.h - Linear-scan reg. allocation --*- C++ -*-===//
2 //
3 //                        The Subzero Code Generator
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief Declares the LinearScan data structure used during linear-scan
12 /// register allocation.
13 ///
14 /// This holds the various work queues for the linear-scan algorithm.
15 ///
16 //===----------------------------------------------------------------------===//
17 
18 #ifndef SUBZERO_SRC_ICEREGALLOC_H
19 #define SUBZERO_SRC_ICEREGALLOC_H
20 
21 #include "IceBitVector.h"
22 #include "IceDefs.h"
23 #include "IceOperand.h"
24 #include "IceTypes.h"
25 
26 namespace Ice {
27 
28 class LinearScan {
29   LinearScan() = delete;
30   LinearScan(const LinearScan &) = delete;
31   LinearScan &operator=(const LinearScan &) = delete;
32 
33 public:
34   explicit LinearScan(Cfg *Func);
35   void init(RegAllocKind Kind, CfgSet<Variable *> ExcludeVars);
36   void scan(const SmallBitVector &RegMask);
37   // Returns the number of times some variable has been assigned a register but
38   // later evicted because of a higher-priority allocation.  The idea is that we
39   // can implement "second-chance bin-packing" by rerunning register allocation
40   // until there are no more evictions.
getNumEvictions()41   SizeT getNumEvictions() const { return Evicted.size(); }
hasEvictions()42   bool hasEvictions() const { return !Evicted.empty(); }
43   void dump(Cfg *Func) const;
44 
45   // TODO(stichnot): Statically choose the size based on the target being
46   // compiled.  For now, choose a value large enough to fit into the
47   // SmallVector's fixed portion, which is 32 for x86-32, 84 for x86-64, and 102
48   // for ARM32.
49   static constexpr size_t REGS_SIZE = 128;
50 
51 private:
52   using OrderedRanges = CfgVector<Variable *>;
53   using UnorderedRanges = CfgVector<Variable *>;
54   using DefUseErrorList = llvm::SmallVector<SizeT, 10>;
55 
56   class IterationState {
57     IterationState(const IterationState &) = delete;
58     IterationState operator=(const IterationState &) = delete;
59 
60   public:
61     IterationState() = default;
62     Variable *Cur = nullptr;
63     Variable *Prefer = nullptr;
64     RegNumT PreferReg;
65     bool AllowOverlap = false;
66     SmallBitVector RegMask;
67     SmallBitVector RegMaskUnfiltered;
68     SmallBitVector Free;
69     SmallBitVector FreeUnfiltered;
70     SmallBitVector PrecoloredUnhandledMask; // Note: only used for dumping
71     llvm::SmallVector<RegWeight, REGS_SIZE> Weights;
72   };
73 
74   bool livenessValidateIntervals(const DefUseErrorList &DefsWithoutUses,
75                                  const DefUseErrorList &UsesBeforeDefs,
76                                  const CfgVector<InstNumberT> &LRBegin,
77                                  const CfgVector<InstNumberT> &LREnd) const;
78   void initForGlobal();
79   void initForInfOnly();
80   void initForSecondChance();
81   /// Move an item from the From set to the To set. From[Index] is pushed onto
82   /// the end of To[], then the item is efficiently removed from From[] by
83   /// effectively swapping it with the last item in From[] and then popping it
84   /// from the back. As such, the caller is best off iterating over From[] in
85   /// reverse order to avoid the need for special handling of the iterator.
moveItem(UnorderedRanges & From,SizeT Index,UnorderedRanges & To)86   void moveItem(UnorderedRanges &From, SizeT Index, UnorderedRanges &To) {
87     To.push_back(From[Index]);
88     From[Index] = From.back();
89     From.pop_back();
90   }
91 
92   /// \name scan helper functions.
93   /// @{
94   /// Free up a register for infinite-weight Cur by spilling and reloading some
95   /// register that isn't used during Cur's live range.
96   void addSpillFill(IterationState &Iter);
97   /// Check for active ranges that have expired or become inactive.
98   void handleActiveRangeExpiredOrInactive(const Variable *Cur);
99   /// Check for inactive ranges that have expired or reactivated.
100   void handleInactiveRangeExpiredOrReactivated(const Variable *Cur);
101   void findRegisterPreference(IterationState &Iter);
102   void filterFreeWithInactiveRanges(IterationState &Iter);
103   void filterFreeWithPrecoloredRanges(IterationState &Iter);
104   void allocatePrecoloredRegister(Variable *Cur);
105   void allocatePreferredRegister(IterationState &Iter);
106   void allocateFreeRegister(IterationState &Iter, bool Filtered);
107   void handleNoFreeRegisters(IterationState &Iter);
108   void assignFinalRegisters(const SmallBitVector &RegMaskFull);
109   /// @}
110 
111   void dumpLiveRangeTrace(const char *Label, const Variable *Item);
112 
113   Cfg *const Func;
114   GlobalContext *const Ctx;
115   TargetLowering *const Target;
116 
117   OrderedRanges Unhandled;
118   /// UnhandledPrecolored is a subset of Unhandled, specially collected for
119   /// faster processing.
120   OrderedRanges UnhandledPrecolored;
121   UnorderedRanges Active, Inactive, Handled;
122   UnorderedRanges Evicted;
123   CfgVector<InstNumberT> Kills;
124   RegAllocKind Kind = RAK_Unknown;
125   /// RegUses[I] is the number of live ranges (variables) that register I is
126   /// currently assigned to. It can be greater than 1 as a result of
127   /// AllowOverlap inference.
128   llvm::SmallVector<int32_t, REGS_SIZE> RegUses;
129   llvm::SmallVector<const SmallBitVector *, REGS_SIZE> RegAliases;
130   bool FindPreference = false;
131   bool FindOverlap = false;
132   const bool Verbose;
133   const bool UseReserve;
134   CfgVector<Variable *> Vars;
135 };
136 
137 } // end of namespace Ice
138 
139 #endif // SUBZERO_SRC_ICEREGALLOC_H
140