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

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
-/// 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.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef SUBZERO_SRC_ICEREGALLOC_H
 #define SUBZERO_SRC_ICEREGALLOC_H
 
 #include "IceDefs.h"
+#include "IceOperand.h"
 #include "IceTypes.h"
 
 namespace Ice {
 
 class LinearScan {
   LinearScan() = delete;
   LinearScan(const LinearScan &) = delete;
   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;
 
 private:
   typedef std::vector<Variable *> OrderedRanges;
   typedef std::vector<Variable *> UnorderedRanges;
 
   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(Variable *Cur, llvm::SmallBitVector RegMask);

[Jim Stichnoth, 2015/08/24 15:08:31]

I think all these SmallBitVectors should be passed by ref, and by const ref
where possible.

[ascull, 2015/08/24 19:53:48]

This gets taken care of by passing IterationState by reference.

+  /// Check for active ranges that have expired or become inactive.
+  void handleActiveRangeExpiredOrInactive(Variable *Cur);
+  /// Check for inactive ranges that have expired or reactivated.
+  void handleInctiveRangeExpiredOrReactived(Variable *Cur);

[Jim Stichnoth, 2015/08/24 15:08:31]

Reactivated

[jvoung (off chromium), 2015/08/24 15:33:01]

Inctive -> Inactive

[ascull, 2015/08/24 19:53:48]

Done.

[ascull, 2015/08/24 19:53:48]

Done.

+  void findRegisterPreference(Variable *Cur, llvm::SmallBitVector RegMask);
+  void filterFreeWithInactiveRanges(Variable *Cur);
+  void filterFreeWithPrecoloredRanges(Variable *Cur);
+  void allocatePrecoloredRegister(Variable *Cur);
+  void allocatePreferedRegister(Variable *Cur);

[Jim Stichnoth, 2015/08/24 15:08:31]

Preferred

[ascull, 2015/08/24 19:53:48]

Done.

+  void allocateFreeRegister(Variable *Cur);
+  void handleNoFreeRegisters(Variable *Cur, llvm::SmallBitVector RegMask);
+  void assignFinalRegisters(llvm::SmallBitVector RegMaskFull,
+                            llvm::SmallBitVector PreDefinedRegisters,
+                            bool Randomized);
+  /// @}
+
+  // TODO(stichnot): Statically choose the size based on the target being
+  // compiled.
+  static constexpr size_t REGS_SIZE = 32;

[Jim Stichnoth, 2015/08/24 15:08:31]

Make this public, so that the Machine could potentially static_assert against
this.

[ascull, 2015/08/24 19:53:48]

Done.

+
   Cfg *const Func;
+  GlobalContext *const Ctx;
+  const bool Verbose;

[jvoung (off chromium), 2015/08/24 15:33:01]

nit: Cluster some of the bools together for better use of alignment-padding? I
suppose the "AllowOverlap" can stay with the Iteration state block since it's
logically related. 

[ascull, 2015/08/24 19:53:47]

Done.

+
   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;
   bool FindPreference = false;
   bool FindOverlap = false;
+
+  /// 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 below.

[Jim Stichnoth, 2015/08/24 15:08:31]

Probably just remove the word "below".

[ascull, 2015/08/24 19:53:47]

Done.

+  llvm::SmallVector<int, REGS_SIZE> RegUses;

[Jim Stichnoth, 2015/08/24 15:08:31]

Can you change int to int32_t ?

[ascull, 2015/08/24 19:53:48]

Done.

+
+  /// \name Iteration state

[Jim Stichnoth, 2015/08/24 15:08:31]

I wonder if you could move the iteration-specific stuff into a separate class. 
This class would be defined only within IceRegAlloc.cpp so it would be otherwise
completely hidden.  You could hold a pointer to that object within this class. 
The object could be created at the beginning of scan() and delete before scan()
returns.  As such, it would be better to make it a unique_ptr, but I think you
need to complete class definition available, not just forward-declared.

The rationale is that the rest of the fields of this class have some meaning and
consistency between calls to the public methods, whereas these fields have
meaning only within scan(), and are essentially undefined otherwise.

[ascull, 2015/08/24 19:53:48]

No need to go to the heap or pollute the class. Putting this on the stack in
scan() does the trick. This brings it back to the original C-style
implementation I proposed.

+  /// @{
+  llvm::SmallBitVector Free;
+  llvm::SmallVector<RegWeight, REGS_SIZE> Weights;
+  llvm::SmallBitVector PrecoloredUnhandledMask; // Note: only used for dumping.
+  Variable *Prefer;
+  int32_t PreferReg;
+  bool AllowOverlap;
+  /// @}
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEREGALLOC_H