Subzero: Randomize register assignment.

src/IceRegAlloc.cpp

Index: src/IceRegAlloc.cpp
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 10a02a3ee381dfd44c8574a75e16b735f3c56cf3..44d9e2666da16d64acca9ae12e52b7d5f2562641 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -18,9 +18,15 @@
 #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,
@@ -40,6 +46,8 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
   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
@@ -61,15 +69,19 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
       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());
@@ -397,25 +409,37 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
   }
   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