Subzero: Implement "second-chance bin-packing" for register allocation.

src/IceRegAlloc.h

 //===- subzero/src/IceRegAlloc.h - Linear-scan reg. allocation --*- C++ -*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 14 matching lines @@
 
 class LinearScan {
   LinearScan() = delete;
   LinearScan(const LinearScan &) = delete;
   LinearScan &operator=(const LinearScan &) = delete;
 
 public:
   explicit LinearScan(Cfg *Func);
   void init(RegAllocKind Kind);
   void scan(const llvm::SmallBitVector &RegMask, bool Randomized);
+  // Returns the number of times some variable has been assigned a register but
+  // later evicted because of a higher-priority allocation.  The idea is that we
+  // can implement "second-chance bin-packing" by rerunning register allocation
+  // until there are no more evictions.
+  SizeT getNumEvictions() const { return Evicted.size(); }
+  bool hasEvictions() const { return !Evicted.empty(); }
   void dump(Cfg *Func) const;
 
   // TODO(stichnot): Statically choose the size based on the target being
   // compiled.
   static constexpr size_t REGS_SIZE = 32;
 
 private:
   using OrderedRanges = CfgVector<Variable *>;
   using UnorderedRanges = CfgVector<Variable *>;
   using DefUseErrorList = llvm::SmallVector<SizeT, 10>;
@@ skipping 13 matching lines @@
     llvm::SmallBitVector PrecoloredUnhandledMask; // Note: only used for dumping
     llvm::SmallVector<RegWeight, REGS_SIZE> Weights;
   };
 
   bool livenessValidateIntervals(const DefUseErrorList &DefsWithoutUses,
                                  const DefUseErrorList &UsesBeforeDefs,
                                  const CfgVector<InstNumberT> &LRBegin,
                                  const CfgVector<InstNumberT> &LREnd) const;
   void initForGlobal();
   void initForInfOnly();
+  void initForSecondChance();
   /// Move an item from the From set to the To set. From[Index] is pushed onto
   /// the end of To[], then the item is efficiently removed from From[] by
   /// effectively swapping it with the last item in From[] and then popping it
   /// from the back. As such, the caller is best off iterating over From[] in
   /// reverse order to avoid the need for special handling of the iterator.
   void moveItem(UnorderedRanges &From, SizeT Index, UnorderedRanges &To) {
     To.push_back(From[Index]);
     From[Index] = From.back();
     From.pop_back();
   }
@@ skipping 23 matching lines @@
 
   Cfg *const Func;
   GlobalContext *const Ctx;
   TargetLowering *const Target;
 
   OrderedRanges Unhandled;
   /// UnhandledPrecolored is a subset of Unhandled, specially collected for
   /// faster processing.
   OrderedRanges UnhandledPrecolored;
   UnorderedRanges Active, Inactive, Handled;
+  UnorderedRanges Evicted;
   CfgVector<InstNumberT> Kills;
   RegAllocKind Kind = RAK_Unknown;
   /// RegUses[I] is the number of live ranges (variables) that register I is
   /// currently assigned to. It can be greater than 1 as a result of
   /// AllowOverlap inference.
   llvm::SmallVector<int32_t, REGS_SIZE> RegUses;
   // TODO(jpp): for some architectures a SmallBitVector might not be big
   // enough. Evaluate what the performance impact on those architectures is.
   llvm::SmallVector<const llvm::SmallBitVector *, REGS_SIZE> RegAliases;
   bool FindPreference = false;
   bool FindOverlap = false;
 
   const bool Verbose;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEREGALLOC_H