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 4512 matching lines @@
     if (Variable *Dest = Inst->getDest()) {
       // TODO(stichnot): We may need to consider all source
       // operands, not just the first one, if using 3-address
       // instructions.
       if (Inst->getSrcSize() > 0 && Inst->getSrc(0) == Dest)
         Inst->setDestNonKillable();
     }
   }
 }
 
+void TargetX8632::makeRandomRegisterPermutation(
+    llvm::SmallVectorImpl<int32_t> &Permutation,
+    const llvm::SmallBitVector &ExcludeRegisters) const {
+  assert(Permutation.size() >= RegX8632::Reg_NUM);
+  typedef llvm::SmallVector<int32_t, 8> RegisterList;

[JF, 2014/12/17 18:56:19]

Make 8 a constant somewhere, with an explanation.

[Jim Stichnoth, 2014/12/18 18:52:03]

Done.

+  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, encode, name, name16, name8, scratch, preserved, stackptr,      \
+          frameptr, isI8, isInt, isFP)                                         \
+  if (ExcludeRegisters[RegX8632::val]) {                                       \
+    /* val stays the same in the resulting permutation. */                     \
+    Permutation[RegX8632::val] = RegX8632::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(RegX8632::val);               \

[JF, 2014/12/17 18:56:19]

You can't access Class.ClassNum here: the union's active type is Bits. Undefined
behavior.

[Jim Stichnoth, 2014/12/18 18:52:03]

Done.

+  }
+  REGX8632_TABLE
+#undef X

[JF, 2014/12/17 18:56:19]

Can't this table be in rodata?

[Jim Stichnoth, 2014/12/18 18:52:03]

Not so readily, since the table is dependent on the input arg ExcludeRegisters. 
Hopefully the simplified code makes that more clear?

+
+  RandomNumberGeneratorWrapper RNG(Ctx->getRNG());
+
+  // Shuffle the resulting equivalence classes.
+  for (EquivalenceClassMap::const_iterator I = EquivalenceClasses.begin(),
+                                           E = EquivalenceClasses.end();
+       I != E; ++I) {

[JF, 2014/12/17 18:56:19]

C++11.

[Jim Stichnoth, 2014/12/18 18:52:03]

Done.

+    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) {

[JF, 2014/12/17 18:56:19]

C++11.

[Jim Stichnoth, 2014/12/18 18:52:03]

I don't think much can be done here, since the index SI is being used directly
(Permutation[List[SI]]) in addition to Shuffled[SI].

+      Permutation[List[SI]] = Shuffled[SI];
+      ++NumShuffled;
+    }
+  }
+
+  assert(NumShuffled + NumPreserved == RegX8632::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) {

[JF, 2014/12/17 18:56:18]

C++11.

[Jim Stichnoth, 2014/12/18 18:52:03]

Done.

+      Str << "{";
+      const RegisterList &List = I->second;
+      for (SizeT RI = 0, RE = List.size(); RI != RE; ++RI) {

[JF, 2014/12/17 18:56:19]

C++11.

[Jim Stichnoth, 2014/12/18 18:52:03]

Done.

+        if (RI > 0)
+          Str << " ";
+        Str << getRegName(List[RI], IceType_i32);
+      }
+      Str << "}\n";
+    }
+  }
+}
+
 template <> void ConstantInteger32::emit(GlobalContext *Ctx) const {
   if (!ALLOW_DUMP)
     return;
   Ostream &Str = Ctx->getStrEmit();
   Str << "$" << (int32_t)getValue();
 }
 
 template <> void ConstantInteger64::emit(GlobalContext *) const {
   llvm_unreachable("Not expecting to emit 64-bit integers");
 }
@@ skipping 109 matching lines @@
   } else if (IsConstant || IsExternal)
     Str << "\t.zero\t" << Size << "\n";
   // Size is part of .comm.
 
   if (IsConstant || HasNonzeroInitializer || IsExternal)
     Str << "\t.size\t" << MangledName << ", " << Size << "\n";
   // Size is part of .comm.
 }
 
 } // end of namespace Ice