Subzero: Randomize register assignment.

src/IceTargetLoweringX8632.cpp

Index: src/IceTargetLoweringX8632.cpp
diff --git a/src/IceTargetLoweringX8632.cpp b/src/IceTargetLoweringX8632.cpp
index 35792aaac0aebc38cafca62a0744a7e8c9fe4572..ea56ee84da3b686489a3968fa1dc0c1e8019d7c4 100644
--- a/src/IceTargetLoweringX8632.cpp
+++ b/src/IceTargetLoweringX8632.cpp
@@ -4145,9 +4145,7 @@ void TargetX8632::postLower() {
     return;
   // TODO: Avoid recomputing WhiteList every instruction.
   RegSetMask RegInclude = RegSet_All;
-  RegSetMask RegExclude = RegSet_None;
-  if (hasFramePointer())
-    RegExclude |= RegSet_FramePointer;
+  RegSetMask RegExclude = RegSet_FramePointer;
   llvm::SmallBitVector WhiteList = getRegisterSet(RegInclude, RegExclude);
   // Make one pass to black-list pre-colored registers.  TODO: If
   // there was some prior register allocation pass that made register
@@ -4172,6 +4170,17 @@ void TargetX8632::postLower() {
     }
   }
   // The second pass colors infinite-weight variables.
+
+  // Indices from which to start looking for the next register in the
+  // free list.
+  int32_t PrevFreeRegisterForType[IceType_NUM];
+  int32_t Uninitialized = -1;
+  std::fill_n(PrevFreeRegisterForType, IceType_NUM, Uninitialized);
+  RandomNumberGeneratorWrapper RNG(Ctx->getRNG());
+
+  // TODO: The randomized register allocation should choose scratch
+  // registers before callee save registers.
+
   llvm::SmallBitVector AvailableRegisters = WhiteList;
   for (InstList::iterator I = Context.getCur(), E = Context.getEnd(); I != E;
        ++I) {
@@ -4187,21 +4196,120 @@ void TargetX8632::postLower() {
           continue;
         if (!Var->getWeight().isInf())
           continue;
+        Type Ty = Var->getType();
+
         llvm::SmallBitVector AvailableTypedRegisters =
-            AvailableRegisters & getRegisterSetForType(Var->getType());
+            AvailableRegisters & getRegisterSetForType(Ty);
+
         if (!AvailableTypedRegisters.any()) {
           // This is a hack in case we run out of physical registers due
           // to an excessively long code sequence, as might happen when
           // lowering arguments in lowerCall().
           AvailableRegisters = WhiteList;
           AvailableTypedRegisters =
-              AvailableRegisters & getRegisterSetForType(Var->getType());
+              AvailableRegisters & getRegisterSetForType(Ty);
         }
         assert(AvailableTypedRegisters.any());
-        int32_t RegNum = AvailableTypedRegisters.find_first();
+
+        if (PrevFreeRegisterForType[Ty] == Uninitialized &&
+            RandomizeRegisterAllocation) {
+          // Start at a random offset in the free list; follow the
+          // linear order from there.
+          SizeT StartingRegister = RNG.next(AvailableTypedRegisters.count());
+          SizeT Index = -1;
+          for (size_t I = 0; I < StartingRegister; ++I) {
+            Index = AvailableTypedRegisters.find_next(Index);
+          }
+          PrevFreeRegisterForType[Ty] = Index;
+        }
+
+        int32_t PrevRegNum = PrevFreeRegisterForType[Ty];
+        int32_t RegNum = AvailableTypedRegisters.find_next(PrevRegNum);
+        if (RegNum == -1) {
+          // Wraparound
+          RegNum = AvailableTypedRegisters.find_first();
+        }
+        assert(RegNum != -1);
+
         Var->setRegNum(RegNum);
         AvailableRegisters[RegNum] = false;
+        PrevFreeRegisterForType[Ty] = RegNum;
+      }
+    }
+  }
+}
+
+void TargetX8632::makeRandomRegisterPermutation(
+    llvm::SmallVectorImpl<int32_t> &Permutation,
+    const llvm::SmallBitVector &ExcludeRegisters) {
+  assert(Permutation.size() >= Reg_NUM);
+  typedef llvm::SmallVector<int32_t, 8> RegisterList;
+  typedef std::map<unsigned, 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 {                                                                    \
+      unsigned ClassNum;                                                       \
+      struct {                                                                 \
+        unsigned IsScratch : 1;                                                \
+        unsigned IsPreserved : 1;                                              \
+        unsigned IsI8 : 1;                                                     \
+        unsigned IsInt : 1;                                                    \
+        unsigned 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";
     }
   }
 }