Subzero: Randomize register assignment.

src/IceRegAlloc.cpp

Index: src/IceRegAlloc.cpp
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 10a02a3ee381dfd44c8574a75e16b735f3c56cf3..fc6d2bdd879879791f04f635559dc26d3a3c7407 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -32,7 +32,8 @@ namespace Ice {
 // Requires running Cfg::liveness(Liveness_RangesFull) 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) {
   assert(RegMaskFull.any()); // Sanity check
   Unhandled.clear();
   Handled.clear();
@@ -40,6 +41,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 +64,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 +404,40 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
   }
   dump(Func);
 
-  // Finish up by assigning RegNumTmp->RegNum for each Variable.
+  // TODO: 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 (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;
+    int32_t RegNum = Var->getRegNumTmp();
+    int32_t AssignedRegNum = RegNum;
+
+    if (Randomized && 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