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 4054 matching lines @@
   // There aren't any 64-bit integer registers for x86-32.
   assert(Type != IceType_i64);
   Variable *Reg = Func->makeVariable(Type, Context.getNode());
   if (RegNum == Variable::NoRegister)
     Reg->setWeightInfinite();
   else
     Reg->setRegNum(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;
   // TODO: Avoid recomputing WhiteList every instruction.
   RegSetMask RegInclude = RegSet_All;
   RegSetMask RegExclude = RegSet_None;
   if (hasFramePointer())
     RegExclude |= RegSet_FramePointer;
   llvm::SmallBitVector WhiteList = getRegisterSet(RegInclude, RegExclude);
   // Make one pass to black-list pre-colored registers.  TODO: If
@@ skipping 12 matching lines @@
       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.
+
+  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) {
     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;
         llvm::SmallBitVector AvailableTypedRegisters =
             AvailableRegisters & getRegisterSetForType(Var->getType());
         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());
         }
         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();
 }
 
 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]".
   Str << "dword ptr [L$" << IceType_f32 << "$" << getPoolEntryID() << "]";
@@ skipping 98 matching lines @@
     for (SizeT i = 0; i < Size; ++i) {
       Str << "\t.byte\t" << (((unsigned)Data[i]) & 0xff) << "\n";
     }
     Str << "\t.size\t" << MangledName << ", " << Size << "\n";
   }
   Str << "\t" << (IsInternal ? ".local" : ".global") << "\t" << MangledName
       << "\n";
 }
 
 } // end of namespace Ice