Refactor LinearScan::scan from one huge function into smaller functions.

src/IceRegAlloc.h

Index: src/IceRegAlloc.h
diff --git a/src/IceRegAlloc.h b/src/IceRegAlloc.h
index 207b2761267da17260b9dbd39be321e156f5ba39..9fc25b5c14f404c188ae97acf7761529223e4db6 100644
--- a/src/IceRegAlloc.h
+++ b/src/IceRegAlloc.h
@@ -8,9 +8,9 @@
 //===----------------------------------------------------------------------===//
 ///
 /// \file
-/// This file declares the LinearScan data structure used during
-/// linear-scan register allocation, which holds the various work
-/// queues for the linear-scan algorithm.
+/// This file declares the LinearScan data structure used during linear-scan
+/// register allocation, which holds the various work queues for the linear-scan
+/// algorithm.
 ///
 //===----------------------------------------------------------------------===//
 
@@ -18,6 +18,7 @@
 #define SUBZERO_SRC_ICEREGALLOC_H
 
 #include "IceDefs.h"
+#include "IceOperand.h"
 #include "IceTypes.h"
 
 namespace Ice {
@@ -28,42 +29,84 @@ class LinearScan {
   LinearScan &operator=(const LinearScan &) = delete;
 
 public:
-  explicit LinearScan(Cfg *Func) : Func(Func) {}
+  explicit LinearScan(Cfg *Func);
   void init(RegAllocKind Kind);
   void scan(const llvm::SmallBitVector &RegMask, bool Randomized);
   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:
   typedef std::vector<Variable *> OrderedRanges;
   typedef std::vector<Variable *> UnorderedRanges;
 
+  struct IterationState {

[Jim Stichnoth, 2015/08/25 05:36:08]

I think it would be safer to call this a class instead of a struct and
explicitly initialize its fields:

class IterationState {
  // delete default copy ctor / assignment operator
public:
  IterationState() = default;
  Variable *Cur = nullptr;
  Variable *Prefer = nullptr;
  int32_t PreferReg = Variable::NoRegister;
  bool AllowOverlap = false;
  ...
};

+    Variable *Cur;
+    llvm::SmallBitVector RegMask;

[Jim Stichnoth, 2015/08/25 05:36:08]

Maybe move the llvm:: fields to the end.

+    llvm::SmallBitVector Free;
+    llvm::SmallVector<RegWeight, REGS_SIZE> Weights;
+    llvm::SmallBitVector PrecoloredUnhandledMask; // Note: only used for dumping
+    Variable *Prefer;
+    int32_t PreferReg;
+    bool AllowOverlap;
+  };
+
   void initForGlobal();
   void initForInfOnly();
-  /// Free up a register for infinite-weight Cur by spilling and reloading some
-  /// register that isn't used during Cur's live range.
-  void addSpillFill(Variable *Cur, llvm::SmallBitVector RegMask);
-  /// 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.
+  /// 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();
   }
 
+  /// \name scan helper functions.
+  /// @{
+  /// Free up a register for infinite-weight Cur by spilling and reloading some
+  /// register that isn't used during Cur's live range.
+  void addSpillFill(IterationState &Iter);
+  /// Check for active ranges that have expired or become inactive.
+  void handleActiveRangeExpiredOrInactive(const Variable *Cur);
+  /// Check for inactive ranges that have expired or reactivated.
+  void handleInactiveRangeExpiredOrReactivated(const Variable *Cur);
+  void findRegisterPreference(IterationState &Iter);
+  void filterFreeWithInactiveRanges(IterationState &Iter);
+  void filterFreeWithPrecoloredRanges(IterationState &Iter);
+  void allocatePrecoloredRegister(Variable *Cur);
+  void allocatePreferredRegister(IterationState &Iter);
+  void allocateFreeRegister(IterationState &Iter);
+  void handleNoFreeRegisters(IterationState &Iter);
+  void assignFinalRegisters(llvm::SmallBitVector RegMaskFull,

[jvoung (off chromium), 2015/08/25 12:50:48]

re: passing llvm::SmallBitVector arguments which Jim brought up earlier -- these
are also passed by value.

It looks like it's only one field (either used as a pointer, or the bits
themselves for the small variant of the vector), but how complicated the
pass-by-value is depends on whether the class is "non-trivial" or not. If POD,
it would be pretty nice and simple and cheaper than pass by ref, but if not,
then...

[Jim Stichnoth, 2015/08/25 15:19:03]

Oh yeah, I missed this.  Please pass these by ref, ideally const ref.

+                            llvm::SmallBitVector PreDefinedRegisters,
+                            bool Randomized);
+  /// @}
+
+  void dumpLiveRangeTrace(const char *Label, const Variable *Item);
+
   Cfg *const Func;
+  GlobalContext *const Ctx;
+
   OrderedRanges Unhandled;
-  /// UnhandledPrecolored is a subset of Unhandled, specially collected
-  /// for faster processing.
+  /// UnhandledPrecolored is a subset of Unhandled, specially collected for
+  /// faster processing.
   OrderedRanges UnhandledPrecolored;
   UnorderedRanges Active, Inactive, Handled;
   std::vector<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;
   bool FindPreference = false;
   bool FindOverlap = false;
+
+  const bool Verbose;
 };
 
 } // end of namespace Ice