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
 // linear-scan register allocation after liveness analysis has been
 // performed.
 //
 //===----------------------------------------------------------------------===//
 
 #include "IceCfg.h"
 #include "IceInst.h"
 #include "IceOperand.h"
 #include "IceRegAlloc.h"
 #include "IceTargetLowering.h"
+#include "llvm/Support/CommandLine.h"
 
 namespace Ice {
 
+namespace cl = ::llvm::cl;
+cl::opt<bool> CLRandomizeRegisterAllocation(
+    "randomize-regalloc", cl::desc("Randomize register allocation"),
+     cl::init(false));

[JF, 2014/08/12 05:27:00]

I don't think SubZero should pull in LLVM's cl as it represents a fairly big
chunk of the translator's footprint.

[Jim Stichnoth, 2014/08/14 01:10:29]

Really?  That's very sad.  cl is already being used quite a bit in other parts
of Subzero so I guess we'll have to deal with all of those.

+
 // Implements the linear-scan algorithm.  Based on "Linear Scan
 // 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_RangesFull) in
 // preparation.  Results are assigned to Variable::RegNum for each
 // Variable.
 void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
   assert(RegMaskFull.any()); // Sanity check
   Unhandled.clear();
   Handled.clear();
   Inactive.clear();
   Active.clear();
   Ostream &Str = Func->getContext()->getStrDump();
   Func->setCurrentNode(NULL);
+  const size_t NumRegisters = RegMaskFull.size();
+  llvm::SmallBitVector PreDefinedRegisters(NumRegisters);
 
   // Gather the live ranges of all variables and add them to the
   // Unhandled set.  TODO: Unhandled is a set<> which is based on a
   // balanced binary tree, so inserting live ranges for N variables is
   // O(N log N) complexity.  N may be proportional to the number of
   // instructions, thanks to temporary generation during lowering.  As
   // a result, it may be useful to design a better data structure for
   // storing Func->getVariables().
   const VarList &Vars = Func->getVariables();
   for (VarList::const_iterator I = Vars.begin(), E = Vars.end(); I != E; ++I) {
     Variable *Var = *I;
     // Explicitly don't consider zero-weight variables, which are
     // meant to be spill slots.
     if (Var->getWeight() == RegWeight::Zero)
       continue;
     // Don't bother if the variable has a null live range, which means
     // it was never referenced.
     if (Var->getLiveRange().isEmpty())
       continue;
     Unhandled.insert(LiveRangeWrapper(Var));
     if (Var->hasReg()) {
-      Var->setRegNumTmp(Var->getRegNum());
+      int32_t RegNum = Var->getRegNum();
+      Var->setRegNumTmp(RegNum);
       Var->setLiveRangeInfiniteWeight();
+      if (Var->getIsArg() || Var->getDefinition()) {
+        PreDefinedRegisters[RegNum] = true;
+      }
     }
   }
 
   // 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 Variable::AllowRegisterOverlap.
-  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());
   UnorderedRanges::iterator Next;
 
   while (!Unhandled.empty()) {
     LiveRangeWrapper Cur = *Unhandled.begin();
     Unhandled.erase(Unhandled.begin());
@@ skipping 307 matching lines @@
   }
   for (UnorderedRanges::iterator I = Inactive.begin(), E = Inactive.end();
        I != E; I = Next) {
     Next = I;
     ++Next;
     Handled.push_back(*I);
     Inactive.erase(I);
   }
   dump(Func);
 
-  // Finish up by assigning RegNumTmp->RegNum for each Variable.
+  TargetLowering::RegisterPermutation Permutation(NumRegisters);
+  if (CLRandomizeRegisterAllocation) {
+    Func->getTarget()->makeRandomRegisterPermutation(Permutation,
+        PreDefinedRegisters | ~RegMaskFull);

[JF, 2014/08/12 05:27:00]

Tab.

[wala, 2014/08/15 03:37:23]

Woops, done.

+  }
+
+  // Finish up by assigning RegNumTmp->RegNum (or a random permutation
+  // thereof) for each Variable.
   for (UnorderedRanges::const_iterator I = Handled.begin(), E = Handled.end();
        I != E; ++I) {
-    LiveRangeWrapper Item = *I;
-    int32_t RegNum = Item.Var->getRegNumTmp();
+    Variable *Var = (*I).Var;

[Jim Stichnoth, 2014/08/14 01:10:29]

I->Var

[wala, 2014/08/15 03:37:23]

Done.

+    int32_t RegNum = Var->getRegNumTmp();
+    int32_t AssignedRegNum = RegNum;
+
+    if (CLRandomizeRegisterAllocation && Var->hasRegTmp() && !Var->hasReg()) {
+      AssignedRegNum = Permutation[RegNum];
+    }
     if (Func->getContext()->isVerbose(IceV_LinearScan)) {
-      if (!Item.Var->hasRegTmp()) {
+      if (!Var->hasRegTmp()) {
         Str << "Not assigning ";
-        Item.Var->dump(Func);
+        Var->dump(Func);
         Str << "\n";
       } else {
-        Str << (RegNum == Item.Var->getRegNum() ? "Reassigning " : "Assigning ")
-            << Func->getTarget()->getRegName(RegNum, IceType_i32) << "(r"
-            << RegNum << ") to ";
-        Item.Var->dump(Func);
+        Str << (RegNum == Var->getRegNum() ? "Reassigning " : "Assigning ")
+            << Func->getTarget()->getRegName(AssignedRegNum, IceType_i32)
+            << "(r" << AssignedRegNum << ") to ";
+        Var->dump(Func);
         Str << "\n";
       }
     }
-    Item.Var->setRegNum(Item.Var->getRegNumTmp());
+    Var->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 39 matching lines @@
   }
   Str << "++++++ Inactive:\n";
   for (UnorderedRanges::const_iterator I = Inactive.begin(), E = Inactive.end();
        I != E; ++I) {
     I->dump(Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice