Subzero: Randomize register assignment.

src/IceRegAlloc.cpp

 //===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the LinearScan class, which performs the
@@ skipping 123 matching lines @@
 // * We don't need to renumber instructions before computing live
 //   ranges because all the high-level ICE instructions are deleted
 //   prior to lowering, and the low-level instructions are added in
 //   monotonically increasing order.
 //
 // * There are no opportunities for register preference or allowing
 //   overlap.
 //
 // Some properties we aren't (yet) taking advantage of:
 //
-// * Because live ranges are a single segment, the Unhandled set will
+// * Because live ranges are a single segment, the Inactive set will
 //   always be empty, and the live range trimming operation is
 //   unnecessary.
 //
 // * Calculating overlap of single-segment live ranges could be
 //   optimized a bit.
 void LinearScan::initForInfOnly() {
   TimerMarker T(TimerStack::TT_initUnhandled, Func);
   FindPreference = false;
   FindOverlap = false;
   SizeT NumVars = 0;
@@ skipping 96 matching lines @@
 // Register Allocation in the Context of SSA Form and Register
 // Constraints" by Hanspeter Mössenböck and Michael Pfeiffer,
 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF .  This
 // implementation is modified to take affinity into account and allow
 // two interfering variables to share the same register in certain
 // cases.
 //
 // Requires running Cfg::liveness(Liveness_Intervals) in
 // preparation.  Results are assigned to Variable::RegNum for each
 // Variable.
-void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
+void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
+                      bool Randomized) {
   TimerMarker T(TimerStack::TT_linearScan, Func);
   assert(RegMaskFull.any()); // Sanity check
   Ostream &Str = Func->getContext()->getStrDump();
   const bool Verbose =
       ALLOW_DUMP && Func->getContext()->isVerbose(IceV_LinearScan);
   Func->resetCurrentNode();
   VariablesMetadata *VMetadata = Func->getVMetadata();
+  const size_t NumRegisters = RegMaskFull.size();
+  llvm::SmallBitVector PreDefinedRegisters(NumRegisters);
+  if (Randomized) {
+    for (Variable *Var : UnhandledPrecolored) {
+      PreDefinedRegisters[Var->getRegNum()] = true;
+    }
+  }
 
   // Build a LiveRange representing the Kills list.
   LiveRange KillsRange(Kills);
   KillsRange.untrim();
 
   // 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.
-  std::vector<int> RegUses(RegMaskFull.size());
+  std::vector<int> RegUses(NumRegisters);
   // Unhandled is already set to all ranges in increasing order of
   // start points.
   assert(Active.empty());
   assert(Inactive.empty());
   assert(Handled.empty());
   const TargetLowering::RegSetMask RegsInclude =
       TargetLowering::RegSet_CallerSave;
   const TargetLowering::RegSetMask RegsExclude = TargetLowering::RegSet_None;
   const llvm::SmallBitVector KillsMask =
       Func->getTarget()->getRegisterSet(RegsInclude, RegsExclude);
@@ skipping 367 matching lines @@
   }
   // Move anything Active or Inactive to Handled for easier handling.
   for (Variable *I : Active)
     Handled.push_back(I);
   Active.clear();
   for (Variable *I : Inactive)
     Handled.push_back(I);
   Inactive.clear();
   dump(Func);
 
-  // Finish up by assigning RegNumTmp->RegNum for each Variable.
+  // TODO(stichnot): Statically choose the size based on the target
+  // being compiled.
+  const size_t REGS_SIZE = 32;
+  llvm::SmallVector<int32_t, REGS_SIZE> Permutation(NumRegisters);
+  if (Randomized) {
+    Func->getTarget()->makeRandomRegisterPermutation(
+        Permutation, PreDefinedRegisters | ~RegMaskFull);
+  }
+
+  // Finish up by assigning RegNumTmp->RegNum (or a random permutation
+  // thereof) for each Variable.
   for (Variable *Item : Handled) {
     int32_t RegNum = Item->getRegNumTmp();
+    int32_t AssignedRegNum = RegNum;
+
+    if (Randomized && Item->hasRegTmp() && !Item->hasReg()) {
+      AssignedRegNum = Permutation[RegNum];
+    }
     if (Verbose) {
       if (!Item->hasRegTmp()) {
         Str << "Not assigning ";
         Item->dump(Func);
         Str << "\n";
       } else {
-        Str << (RegNum == Item->getRegNum() ? "Reassigning " : "Assigning ")
-            << Func->getTarget()->getRegName(RegNum, IceType_i32) << "(r"
-            << RegNum << ") to ";
+        Str << (AssignedRegNum == Item->getRegNum() ? "Reassigning "
+                                                    : "Assigning ")
+            << Func->getTarget()->getRegName(AssignedRegNum, IceType_i32)
+            << "(r" << AssignedRegNum << ") to ";
         Item->dump(Func);
         Str << "\n";
       }
     }
-    Item->setRegNum(Item->getRegNumTmp());
+    Item->setRegNum(AssignedRegNum);
   }
 
   // TODO: Consider running register allocation one more time, with
   // infinite registers, for two reasons.  First, evicted live ranges
   // get a second chance for a register.  Second, it allows coalescing
   // of stack slots.  If there is no time budget for the second
   // register allocation run, each unallocated variable just gets its
   // own slot.
   //
   // Another idea for coalescing stack slots is to initialize the
@@ skipping 27 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice