Subzero: Randomize register assignment.

src/IceTargetLoweringX8632.cpp

Index: src/IceTargetLoweringX8632.cpp
diff --git a/src/IceTargetLoweringX8632.cpp b/src/IceTargetLoweringX8632.cpp
index ebc0bae319fc44d9d509e67999f088e905586076..837aa35cf5803b7a96578b13147faa8bcd40a002 100644
--- a/src/IceTargetLoweringX8632.cpp
+++ b/src/IceTargetLoweringX8632.cpp
@@ -4072,6 +4072,8 @@ Variable *TargetX8632::makeReg(Type Type, int32_t RegNum) {
   return Reg;
 }
 
+extern cl::opt<bool> CLRandomizeRegisterAllocation;

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

This should be imported from the class instead.

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

Done.

+
 void TargetX8632::postLower() {
   if (Ctx->getOptLevel() != Opt_m1)
     return;
@@ -4104,6 +4106,14 @@ void TargetX8632::postLower() {
     }
   }
   // The second pass colors infinite-weight variables.
+
+  RegisterPermutation Permutation(WhiteList.size());
+  if (CLRandomizeRegisterAllocation) {
+    const llvm::SmallBitVector ExcludeRegisters =
+        ~WhiteList | getRegisterSet(RegExclude, RegSet_None);
+    makeRandomRegisterPermutation(Permutation, ExcludeRegisters);
+  }
+
   llvm::SmallBitVector AvailableRegisters = WhiteList;
   for (InstList::iterator I = Context.getCur(), E = Context.getEnd(); I != E;
        ++I) {
@@ -4131,13 +4141,90 @@ void TargetX8632::postLower() {
         }
         assert(AvailableTypedRegisters.any());
         int32_t RegNum = AvailableTypedRegisters.find_first();
-        Var->setRegNum(RegNum);
+        if (CLRandomizeRegisterAllocation) {
+          Var->setRegNum(Permutation[RegNum]);
+        } else {
+          Var->setRegNum(RegNum);
+        }
         AvailableRegisters[RegNum] = false;
       }
     }
   }
 }
 
+void TargetX8632::makeRandomRegisterPermutation(

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

I know this has already been discussed offline, but this is an awfully
heavy-handed function for every instruction in Om1 mode.

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

Done.

+    RegisterPermutation &Permutation,
+    const llvm::SmallBitVector &ExcludeRegisters) {
+  assert(Permutation.size() == Reg_NUM);
+  typedef llvm::SmallVector<int32_t, 8> RegisterList;
+  typedef std::map<uint8_t, RegisterList> EquivalenceClassMap;
+  EquivalenceClassMap EquivalenceClasses;
+  SizeT NumShuffled = 0, NumPreserved = 0;
+
+  // Build up the equivalence classes of registers by looking at the
+  // register properties as well as whether the registers should be
+  // explicitly excluded from shuffling.
+#define X(val, init, name, name16, name8, scratch, preserved, stackptr,        \
+          frameptr, isI8, isInt, isFP)                                         \
+  if (ExcludeRegisters[val]) {                                                 \
+    /* val stays the same in the resulting permutation. */                     \
+    Permutation[val] = val;                                                    \
+    ++NumPreserved;                                                            \
+  } else {                                                                     \
+     union {                                                                   \
+      uint8_t ClassNum;                                                        \
+      struct {                                                                 \
+        uint8_t IsScratch:1;                                                   \

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

For bitfields I think you can just use unsigned.

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

Done.

+        uint8_t IsPreserved:1;                                                 \
+        uint8_t IsI8:1;                                                        \
+        uint8_t IsInt:1;                                                       \
+        uint8_t IsFP:1;                                                        \
+      } Bits;                                                                  \
+    } Class = {0};                                                             \
+    Class.Bits.IsScratch = scratch;                                            \
+    Class.Bits.IsPreserved = preserved;                                        \
+    Class.Bits.IsI8 = isI8;                                                    \
+    Class.Bits.IsInt = isInt;                                                  \
+    Class.Bits.IsFP = isFP;                                                    \
+    /* val is assigned to an equivalence class based on its properties. */     \
+    EquivalenceClasses[Class.ClassNum].push_back(val);                         \
+  }
+  REGX8632_TABLE
+#undef X
+
+  RandomNumberGeneratorWrapper RNG = Ctx->getRNG();
+
+  // Shuffle the resulting equivalence classes.
+  for (EquivalenceClassMap::const_iterator I = EquivalenceClasses.begin(),
+           E = EquivalenceClasses.end(); I != E; ++I) {
+    const RegisterList &List = I->second;
+    RegisterList Shuffled(List);
+    std::random_shuffle(Shuffled.begin(), Shuffled.end(), RNG);
+    for (size_t SI = 0, SE = Shuffled.size(); SI < SE; ++SI) {
+      Permutation[List[SI]] = Shuffled[SI];
+      ++NumShuffled;
+    }
+  }
+
+  assert(NumShuffled + NumPreserved == Reg_NUM);
+
+  if (Func->getContext()->isVerbose(IceV_Random)) {
+    Ostream &Str = Func->getContext()->getStrDump();
+    Str << "Register equivalence classes:\n";
+    for (EquivalenceClassMap::const_iterator I = EquivalenceClasses.begin(),
+           E = EquivalenceClasses.end(); I != E; ++I) {
+      Str << "{";
+      const RegisterList &List = I->second;
+      for (SizeT RI = 0, RE = List.size(); RI != RE; ++RI) {
+        if (RI > 0)
+          Str << " ";
+        Str << getRegName(List[RI], IceType_i32);
+      }
+      Str << "}\n";
+    }
+  }
+}
+
 template <> void ConstantInteger::emit(GlobalContext *Ctx) const {
   Ostream &Str = Ctx->getStrEmit();
   Str << (int64_t) getValue();