Subzero: Randomize register assignment.

src/IceTargetLoweringX8632.cpp

 //===- subzero/src/IceTargetLoweringX8632.cpp - x86-32 lowering -----------===//
 //
 //                        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 TargetLoweringX8632 class, which
@@ skipping 4127 matching lines @@
   else
     Reg->setRegNum(RegNum);
   return Reg;
 }
 
 void TargetX8632::postLower() {
   if (Ctx->getOptLevel() != Opt_m1)
     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
   // assignments, those registers need to be black-listed here as
   // well.
   for (InstList::iterator I = Context.getCur(), E = Context.getEnd(); I != E;
        ++I) {
     const Inst *Inst = *I;
     if (Inst->isDeleted())
       continue;
     if (llvm::isa<InstFakeKill>(Inst))
       continue;
     for (SizeT SrcNum = 0; SrcNum < Inst->getSrcSize(); ++SrcNum) {
       Operand *Src = Inst->getSrc(SrcNum);
       SizeT NumVars = Src->getNumVars();
       for (SizeT J = 0; J < NumVars; ++J) {
         const Variable *Var = Src->getVar(J);
         if (!Var->hasReg())
           continue;
         WhiteList[Var->getRegNum()] = false;
       }
     }
   }
   // 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) {
     const Inst *Inst = *I;
     if (Inst->isDeleted())
       continue;
     for (SizeT SrcNum = 0; SrcNum < Inst->getSrcSize(); ++SrcNum) {
       Operand *Src = Inst->getSrc(SrcNum);
       SizeT NumVars = Src->getNumVars();
       for (SizeT J = 0; J < NumVars; ++J) {
         Variable *Var = Src->getVar(J);
         if (Var->hasReg())
           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";
+    }
+  }
+}
 
 template <> void ConstantInteger::emit(GlobalContext *Ctx) const {
   Ostream &Str = Ctx->getStrEmit();
   Str << (int64_t) getValue();
 }
 
 template <> void ConstantFloat::emit(GlobalContext *Ctx) const {
   Ostream &Str = Ctx->getStrEmit();
   // It would be better to prefix with ".L$" instead of "L$", but
   // llvm-mc doesn't parse "dword ptr [.L$foo]".
@@ skipping 99 matching lines @@
     Str << "\t.align\t" << Align << "\n";
     Str << MangledName << ":\n";
     for (SizeT i = 0; i < Size; ++i) {
       Str << "\t.byte\t" << (((unsigned)Data[i]) & 0xff) << "\n";
     }
     Str << "\t.size\t" << MangledName << ", " << Size << "\n";
   }
 }
 
 } // end of namespace Ice