Subzero: Randomize register assignment. Randomize the order that registers appear in the free list. Only randomize fully "equivalent" registers to ensure no extra spills. This adds the -randomize-regalloc option. This is a continuation of https://codereview.chromium.org/456033003/ which Matt owns. BUG= none R=jfb@chromium.org Review URL: https://codereview.chromium.org/807293003
diff --git a/src/IceDefs.h b/src/IceDefs.h index 4160fec..6434077 100644 --- a/src/IceDefs.h +++ b/src/IceDefs.h
@@ -122,6 +122,7 @@ IceV_LinearScan = 1 << 8, IceV_Frame = 1 << 9, IceV_AddrOpt = 1 << 10, + IceV_Random = 1 << 11, IceV_All = ~IceV_None, IceV_Most = IceV_All & ~IceV_LinearScan };
diff --git a/src/IceRNG.h b/src/IceRNG.h index 5f862a8..bb2ac45 100644 --- a/src/IceRNG.h +++ b/src/IceRNG.h
@@ -42,7 +42,7 @@ operator=(const RandomNumberGeneratorWrapper &) = delete; public: - uint64_t next(uint64_t Max) { return RNG.next(Max); } + uint64_t operator()(uint64_t Max) { return RNG.next(Max); } bool getTrueWithProbability(float Probability); RandomNumberGeneratorWrapper(RandomNumberGenerator &RNG) : RNG(RNG) {}
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp index 2d5ff9b..3601846 100644 --- a/src/IceRegAlloc.cpp +++ b/src/IceRegAlloc.cpp
@@ -141,7 +141,7 @@ // // Some properties we aren't (yet) taking advantage of: // -// * Because live ranges are a single segment, the Unhandled set will +// * Because live ranges are a single segment, the Inactive set will // always be empty, and the live range trimming operation is // unnecessary. // @@ -258,7 +258,8 @@ // Requires running Cfg::liveness(Liveness_Intervals) in // preparation. Results are assigned to Variable::RegNum for each // Variable. -void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) { +void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull, + bool Randomized) { TimerMarker T(TimerStack::TT_linearScan, Func); assert(RegMaskFull.any()); // Sanity check Ostream &Str = Func->getContext()->getStrDump(); @@ -266,6 +267,13 @@ ALLOW_DUMP && Func->getContext()->isVerbose(IceV_LinearScan); Func->resetCurrentNode(); VariablesMetadata *VMetadata = Func->getVMetadata(); + const size_t NumRegisters = RegMaskFull.size(); + llvm::SmallBitVector PreDefinedRegisters(NumRegisters); + if (Randomized) { + for (Variable *Var : UnhandledPrecolored) { + PreDefinedRegisters[Var->getRegNum()] = true; + } + } // Build a LiveRange representing the Kills list. LiveRange KillsRange(Kills); @@ -274,7 +282,7 @@ // RegUses[I] is the number of live ranges (variables) that register // I is currently assigned to. It can be greater than 1 as a result // of AllowOverlap inference below. - std::vector<int> RegUses(RegMaskFull.size()); + std::vector<int> RegUses(NumRegisters); // Unhandled is already set to all ranges in increasing order of // start points. assert(Active.empty()); @@ -662,23 +670,39 @@ Inactive.clear(); dump(Func); - // Finish up by assigning RegNumTmp->RegNum for each Variable. + // TODO(stichnot): Statically choose the size based on the target + // being compiled. + const size_t REGS_SIZE = 32; + llvm::SmallVector<int32_t, REGS_SIZE> Permutation(NumRegisters); + if (Randomized) { + Func->getTarget()->makeRandomRegisterPermutation( + Permutation, PreDefinedRegisters | ~RegMaskFull); + } + + // Finish up by assigning RegNumTmp->RegNum (or a random permutation + // thereof) for each Variable. for (Variable *Item : Handled) { int32_t RegNum = Item->getRegNumTmp(); + int32_t AssignedRegNum = RegNum; + + if (Randomized && Item->hasRegTmp() && !Item->hasReg()) { + AssignedRegNum = Permutation[RegNum]; + } if (Verbose) { if (!Item->hasRegTmp()) { Str << "Not assigning "; Item->dump(Func); Str << "\n"; } else { - Str << (RegNum == Item->getRegNum() ? "Reassigning " : "Assigning ") - << Func->getTarget()->getRegName(RegNum, IceType_i32) << "(r" - << RegNum << ") to "; + Str << (AssignedRegNum == Item->getRegNum() ? "Reassigning " + : "Assigning ") + << Func->getTarget()->getRegName(AssignedRegNum, IceType_i32) + << "(r" << AssignedRegNum << ") to "; Item->dump(Func); Str << "\n"; } } - Item->setRegNum(Item->getRegNumTmp()); + Item->setRegNum(AssignedRegNum); } // TODO: Consider running register allocation one more time, with
diff --git a/src/IceRegAlloc.h b/src/IceRegAlloc.h index 4ecae52..c5c1c9e 100644 --- a/src/IceRegAlloc.h +++ b/src/IceRegAlloc.h
@@ -29,7 +29,7 @@ LinearScan(Cfg *Func) : Func(Func), FindPreference(false), FindOverlap(false) {} void init(RegAllocKind Kind); - void scan(const llvm::SmallBitVector &RegMask); + void scan(const llvm::SmallBitVector &RegMask, bool Randomized); void dump(Cfg *Func) const; private:
diff --git a/src/IceTargetLowering.cpp b/src/IceTargetLowering.cpp index bab46f6..be1d2e1 100644 --- a/src/IceTargetLowering.cpp +++ b/src/IceTargetLowering.cpp
@@ -29,6 +29,7 @@ namespace { +// TODO(stichnot): Move this machinery into llvm2ice.cpp. namespace cl = llvm::cl; cl::opt<bool> DoNopInsertion("nop-insertion", cl::desc("Randomly insert NOPs"), cl::init(false)); @@ -40,6 +41,11 @@ cl::opt<int> NopProbabilityAsPercentage( "nop-insertion-percentage", cl::desc("Nop insertion probability as percentage"), cl::init(10)); + +cl::opt<bool> +CLRandomizeRegisterAllocation("randomize-regalloc", + cl::desc("Randomize register allocation"), + cl::init(false)); } // end of anonymous namespace void LoweringContext::init(CfgNode *N) { @@ -95,6 +101,12 @@ return NULL; } +TargetLowering::TargetLowering(Cfg *Func) + : Func(Func), Ctx(Func->getContext()), + RandomizeRegisterAllocation(CLRandomizeRegisterAllocation), + HasComputedFrame(false), CallsReturnsTwice(false), StackAdjustment(0), + Context() {} + Assembler *TargetLowering::createAssembler(TargetArch Target, Cfg *Func) { // These statements can be #ifdef'd to specialize the assembler // to a subset of the available targets. TODO: use CRTP. @@ -236,7 +248,7 @@ RegExclude |= RegSet_FramePointer; LinearScan.init(Kind); llvm::SmallBitVector RegMask = getRegisterSet(RegInclude, RegExclude); - LinearScan.scan(RegMask); + LinearScan.scan(RegMask, RandomizeRegisterAllocation); } TargetGlobalInitLowering *
diff --git a/src/IceTargetLowering.h b/src/IceTargetLowering.h index 3e2243a..d2bd6f8 100644 --- a/src/IceTargetLowering.h +++ b/src/IceTargetLowering.h
@@ -191,6 +191,10 @@ virtual const llvm::SmallBitVector &getRegisterSetForType(Type Ty) const = 0; void regAlloc(RegAllocKind Kind); + virtual void makeRandomRegisterPermutation( + llvm::SmallVectorImpl<int32_t> &Permutation, + const llvm::SmallBitVector &ExcludeRegisters) const = 0; + virtual void emitVariable(const Variable *Var) const = 0; // Performs target-specific argument lowering. @@ -204,9 +208,7 @@ virtual ~TargetLowering() {} protected: - TargetLowering(Cfg *Func) - : Func(Func), Ctx(Func->getContext()), HasComputedFrame(false), - CallsReturnsTwice(false), StackAdjustment(0) {} + TargetLowering(Cfg *Func); virtual void lowerAlloca(const InstAlloca *Inst) = 0; virtual void lowerArithmetic(const InstArithmetic *Inst) = 0; virtual void lowerAssign(const InstAssign *Inst) = 0; @@ -235,6 +237,7 @@ Cfg *Func; GlobalContext *Ctx; + const bool RandomizeRegisterAllocation; bool HasComputedFrame; bool CallsReturnsTwice; // StackAdjustment keeps track of the current stack offset from its
diff --git a/src/IceTargetLoweringX8632.cpp b/src/IceTargetLoweringX8632.cpp index d049cbd..71f860f 100644 --- a/src/IceTargetLoweringX8632.cpp +++ b/src/IceTargetLoweringX8632.cpp
@@ -3869,7 +3869,7 @@ void TargetX8632::randomlyInsertNop(float Probability) { RandomNumberGeneratorWrapper RNG(Ctx->getRNG()); if (RNG.getTrueWithProbability(Probability)) { - _nop(RNG.next(X86_NUM_NOP_VARIANTS)); + _nop(RNG(X86_NUM_NOP_VARIANTS)); } } @@ -4530,6 +4530,72 @@ } } +void TargetX8632::makeRandomRegisterPermutation( + llvm::SmallVectorImpl<int32_t> &Permutation, + const llvm::SmallBitVector &ExcludeRegisters) const { + // TODO(stichnot): Declaring Permutation this way loses type/size + // information. Fix this in conjunction with the caller-side TODO. + assert(Permutation.size() >= RegX8632::Reg_NUM); + // Expected upper bound on the number of registers in a single + // equivalence class. For x86-32, this would comprise the 8 XMM + // registers. This is for performance, not correctness. + static const unsigned MaxEquivalenceClassSize = 8; + typedef llvm::SmallVector<int32_t, MaxEquivalenceClassSize> RegisterList; + typedef std::map<uint32_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, 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 { \ + const uint32_t Index = (scratch << 0) | (preserved << 1) | (isI8 << 2) | \ + (isInt << 3) | (isFP << 4); \ + /* val is assigned to an equivalence class based on its properties. */ \ + EquivalenceClasses[Index].push_back(RegX8632::val); \ + } + REGX8632_TABLE +#undef X + + RandomNumberGeneratorWrapper RNG(Ctx->getRNG()); + + // Shuffle the resulting equivalence classes. + for (auto I : EquivalenceClasses) { + 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 == RegX8632::Reg_NUM); + + if (Func->getContext()->isVerbose(IceV_Random)) { + Ostream &Str = Func->getContext()->getStrDump(); + Str << "Register equivalence classes:\n"; + for (auto I : EquivalenceClasses) { + Str << "{"; + const RegisterList &List = I.second; + bool First = true; + for (int32_t Register : List) { + if (!First) + Str << " "; + First = false; + Str << getRegName(Register, IceType_i32); + } + Str << "}\n"; + } + } +} + template <> void ConstantInteger32::emit(GlobalContext *Ctx) const { if (!ALLOW_DUMP) return;
diff --git a/src/IceTargetLoweringX8632.h b/src/IceTargetLoweringX8632.h index 2846ac9..6e2bed9 100644 --- a/src/IceTargetLoweringX8632.h +++ b/src/IceTargetLoweringX8632.h
@@ -180,6 +180,10 @@ OperandX8632Mem *getMemoryOperandForStackSlot(Type Ty, Variable *Slot, uint32_t Offset = 0); + void makeRandomRegisterPermutation( + llvm::SmallVectorImpl<int32_t> &Permutation, + const llvm::SmallBitVector &ExcludeRegisters) const; + // The following are helpers that insert lowered x86 instructions // with minimal syntactic overhead, so that the lowering code can // look as close to assembly as practical.
diff --git a/src/llvm2ice.cpp b/src/llvm2ice.cpp index 92bb839..53c90ee 100644 --- a/src/llvm2ice.cpp +++ b/src/llvm2ice.cpp
@@ -47,6 +47,7 @@ clEnumValN(Ice::IceV_LinearScan, "regalloc", "Linear scan details"), clEnumValN(Ice::IceV_Frame, "frame", "Stack frame layout details"), clEnumValN(Ice::IceV_AddrOpt, "addropt", "Address mode optimization"), + clEnumValN(Ice::IceV_Random, "random", "Randomization details"), clEnumValN(Ice::IceV_All, "all", "Use all verbose options"), clEnumValN(Ice::IceV_Most, "most", "Use all verbose options except 'regalloc' and 'time'"),