Home | History | Annotate | Download | only in src 
      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 "IceDefs.h"
     22 #include "IceBitVector.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, bool Randomized);
     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.
     41   SizeT getNumEvictions() const { return Evicted.size(); }
     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.
     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                             const SmallBitVector &PreDefinedRegisters,
    110                             bool Randomized);
    111   /// @}
    112 
    113   void dumpLiveRangeTrace(const char *Label, const Variable *Item);
    114 
    115   Cfg *const Func;
    116   GlobalContext *const Ctx;
    117   TargetLowering *const Target;
    118 
    119   OrderedRanges Unhandled;
    120   /// UnhandledPrecolored is a subset of Unhandled, specially collected for
    121   /// faster processing.
    122   OrderedRanges UnhandledPrecolored;
    123   UnorderedRanges Active, Inactive, Handled;
    124   UnorderedRanges Evicted;
    125   CfgVector<InstNumberT> Kills;
    126   RegAllocKind Kind = RAK_Unknown;
    127   /// RegUses[I] is the number of live ranges (variables) that register I is
    128   /// currently assigned to. It can be greater than 1 as a result of
    129   /// AllowOverlap inference.
    130   llvm::SmallVector<int32_t, REGS_SIZE> RegUses;
    131   llvm::SmallVector<const SmallBitVector *, REGS_SIZE> RegAliases;
    132   bool FindPreference = false;
    133   bool FindOverlap = false;
    134   const bool Verbose;
    135   const bool UseReserve;
    136   CfgVector<Variable *> Vars;
    137 };
    138 
    139 } // end of namespace Ice
    140 
    141 #endif // SUBZERO_SRC_ICEREGALLOC_H
    142