Subzero: Randomize immediates by constant blinding or pooling.

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 118 matching lines @@
 // Stack alignment
 const uint32_t X86_STACK_ALIGNMENT_BYTES = 16;
 // Size of the return address on the stack
 const uint32_t X86_RET_IP_SIZE_BYTES = 4;
 // The base 2 logarithm of the width in bytes of the smallest stack slot
 const uint32_t X86_LOG2_OF_MIN_STACK_SLOT_SIZE = 2;
 // The base 2 logarithm of the width in bytes of the largest stack slot
 const uint32_t X86_LOG2_OF_MAX_STACK_SLOT_SIZE = 4;
 // The number of different NOP instructions
 const uint32_t X86_NUM_NOP_VARIANTS = 5;
+// Randomize integer immediates at least 2 bytes in size.
+const uint64_t X86_INT_IMMEDIATE_RANDOMIZATION_THRESHOLD = 0xffff;
 
 // Value and Alignment are in bytes.  Return Value adjusted to the next
 // highest multiple of Alignment.
 uint32_t applyAlignment(uint32_t Value, uint32_t Alignment) {
   // power of 2
   assert((Alignment & (Alignment - 1)) == 0);
   return (Value + Alignment - 1) & -Alignment;
 }
 
 // Value is in bytes. Return Value adjusted to the next highest multiple
 // of the stack alignment.
 uint32_t applyStackAlignment(uint32_t Value) {
   return applyAlignment(Value, X86_STACK_ALIGNMENT_BYTES);
 }
 
+// This gives a name to the immediate so it can be identified as a
+// constant pool entry.
+IceString nameImmediate(Constant *Immediate) {
+  bool IsRelocatable = llvm::isa<ConstantRelocatable>(Immediate);
+  IceString Name;
+  llvm::raw_string_ostream NameBuf(Name);
+  NameBuf << (IsRelocatable ? "L$__reloc" : "L$") << Immediate->getType() << "$"
+          << Immediate->getPoolEntryID();
+  return NameBuf.str();
+}
+
 // Instruction set options
 namespace cl = ::llvm::cl;
 cl::opt<TargetX8632::X86InstructionSet> CLInstructionSet(
     "mattr", cl::desc("X86 target attributes"),
     cl::init(TargetX8632::SSE2),
     cl::values(
         clEnumValN(TargetX8632::SSE2, "sse2",
                    "Enable SSE2 instructions (default)"),
         clEnumValN(TargetX8632::SSE4_1, "sse4.1",
                    "Enable SSE 4.1 instructions"), clEnumValEnd));
 
+enum RandomizeImmediates {
+  Randomize_None,
+  Randomize_ConstantBlinding,
+  Randomize_ConstantPooling
+};
+
+cl::opt<RandomizeImmediates> CLRandomizeImmediates(
+    "randomize-immediates",
+    cl::desc("Randomize the representation of immediates"),
+    cl::init(Randomize_None),
+    cl::values(clEnumValN(Randomize_None, "none", "Don't randomize (default)"),
+               clEnumValN(Randomize_ConstantBlinding, "constant-blinding",
+                          "Use constant blinding"),
+               clEnumValN(Randomize_ConstantPooling, "constant-pooling",
+                          "Use constant pooling"),
+               clEnumValEnd));
+
+bool immediateShouldBeRandomized(Operand *Immediate) {
+  if (!CLRandomizeImmediates)
+    return false;
+  if (ConstantInteger *ConstInt =
+          llvm::dyn_cast_or_null<ConstantInteger>(Immediate)) {
+    // i64 should have been split at this point.
+    assert(ConstInt->getType() != IceType_i64);
+    return ConstInt->getType() == IceType_i32 &&
+           (ConstInt->getValue() +
+            X86_INT_IMMEDIATE_RANDOMIZATION_THRESHOLD / 2) >=
+               X86_INT_IMMEDIATE_RANDOMIZATION_THRESHOLD;
+  }
+  return false;
+}
+
+// Return a string representation of the type that is suitable for use
+// in an identifier.
+IceString typeIdentString(const Type Ty) {
+  IceString Str;
+  llvm::raw_string_ostream BaseOS(Str);
+  if (isVectorType(Ty)) {
+    BaseOS << "v" << typeNumElements(Ty) << typeElementType(Ty);
+  } else {
+    BaseOS << Ty;
+  }
+  return BaseOS.str();
+}
+
 // In some cases, there are x-macros tables for both high-level and
 // low-level instructions/operands that use the same enum key value.
 // The tables are kept separate to maintain a proper separation
 // between abstraction layers.  There is a risk that the tables
 // could get out of sync if enum values are reordered or if entries
 // are added or deleted.  This dummy function uses static_assert to
 // ensure everything is kept in sync.
 void __attribute__((unused)) xMacroIntegrityCheck() {
   // Validate the enum values in FCMPX8632_TABLE.
   {
@@ skipping 81 matching lines @@
 #undef X
   }
 }
 
 } // end of anonymous namespace
 
 TargetX8632::TargetX8632(Cfg *Func)
     : TargetLowering(Func), InstructionSet(CLInstructionSet),
       IsEbpBasedFrame(false), NeedsStackAlignment(false), FrameSizeLocals(0),
       SpillAreaSizeBytes(0), NextLabelNumber(0), ComputedLiveRanges(false),
-      PhysicalRegisters(VarList(Reg_NUM)) {
+      PhysicalRegisters(VarList(Reg_NUM)),
+      ConstantBlindingCookieInitialized(false), ConstantBlindingCookie(0) {
   // TODO: Don't initialize IntegerRegisters and friends every time.
   // Instead, initialize in some sort of static initializer for the
   // class.
   llvm::SmallBitVector IntegerRegisters(Reg_NUM);
   llvm::SmallBitVector IntegerRegistersI8(Reg_NUM);
   llvm::SmallBitVector FloatRegisters(Reg_NUM);
   llvm::SmallBitVector VectorRegisters(Reg_NUM);
   llvm::SmallBitVector InvalidRegisters(Reg_NUM);
   ScratchRegs.resize(Reg_NUM);
 #define X(val, init, name, name16, name8, scratch, preserved, stackptr,        \
@@ skipping 699 matching lines @@
         snprintf(buf, llvm::array_lengthof(buf), T::PrintfString, RawValue);
     assert(CharsPrinted >= 0 &&
            (size_t)CharsPrinted < llvm::array_lengthof(buf));
     (void)CharsPrinted; // avoid warnings if asserts are disabled
     Str << "L$" << Ty << "$" << Const->getPoolEntryID() << ":\n";
     Str << "\t" << T::AsmTag << "\t" << buf << "\t# " << T::TypeName << " "
         << Value << "\n";
   }
 }
 
+void TargetX8632::emitPooledImmediates() const {
+  Ostream &Str = Ctx->getStrEmit();
+  SizeT Align = typeWidthInBytesOnStack(IceType_i32);
+  // TODO: Determine the right directives to place here.
+  Str << "\t.section\t.rodata.cst" << Align << ",\"aM\",@progbits," << Align
+      << "\n";
+  Str << "\t.align\t" << Align << "\n";
+  ConstantList PooledImmediates = Ctx->getImmediatePool();
+  for (ConstantList::const_iterator I = PooledImmediates.begin(),
+                                    E = PooledImmediates.end();
+       I != E; ++I) {
+    Constant *Value = *I;
+    IceString Name = nameImmediate(Value);
+    Str << Name << ":\n";
+    if (ConstantInteger *Int = llvm::dyn_cast<ConstantInteger>(Value)) {
+      assert(Int->getType() == IceType_i32);
+      char buf[30];
+      int CharsPrinted = snprintf(buf, llvm::array_lengthof(buf), "0x%x",
+                                  (uint32_t)Int->getValue());
+      assert(CharsPrinted >= 0 &&
+             (size_t)CharsPrinted < llvm::array_lengthof(buf));
+      Str << "\t.long\t" << buf << "\n";
+    } else if (ConstantRelocatable *Reloc =
+                   llvm::dyn_cast<ConstantRelocatable>(Value)) {
+      Str << "\t.long\t";
+      Reloc->emit(Ctx);
+      Str << "\n";
+    }
+  }
+}
+
 void TargetX8632::emitConstants() const {
   emitConstantPool<PoolTypeConverter<float> >();
   emitConstantPool<PoolTypeConverter<double> >();
+  emitPooledImmediates();
 
   // No need to emit constants from the int pool since (for x86) they
   // are embedded as immediates in the instructions.
 }
 
 void TargetX8632::split64(Variable *Var) {
   switch (Var->getType()) {
   default:
     return;
   case IceType_i64:
@@ skipping 2802 matching lines @@
     _br(InstX8632Br::Br_ne, Label);
     Context.insert(InstFakeUse::create(Func, DestLo));
     Context.insert(InstFakeUse::create(Func, DestHi));
     Operand *SrcFLo = loOperand(SrcF);
     Operand *SrcFHi = hiOperand(SrcF);
     SrcLoRI = legalize(SrcFLo, Legal_Reg | Legal_Imm, true);
     SrcHiRI = legalize(SrcFHi, Legal_Reg | Legal_Imm, true);
     _mov(DestLo, SrcLoRI);
     _mov(DestHi, SrcHiRI);
   } else {
+    // Call legalize() before _cmp, since legalize() may modify flags.
+    SrcT = legalize(SrcT, Legal_Reg | Legal_Imm, true);
     _cmp(ConditionRMI, Zero);
-    SrcT = legalize(SrcT, Legal_Reg | Legal_Imm, true);
     _mov(Dest, SrcT);
     _br(InstX8632Br::Br_ne, Label);
     Context.insert(InstFakeUse::create(Func, Dest));
     SrcF = legalize(SrcF, Legal_Reg | Legal_Imm, true);
     _mov(Dest, SrcF);
   }
 
   Context.insert(Label);
 }
 
@@ skipping 197 matching lines @@
   Type Ty = Src->getType();
   Variable *Reg = makeReg(Ty, RegNum);
   if (isVectorType(Ty)) {
     _movp(Reg, Src);
   } else {
     _mov(Reg, Src);
   }
   return Reg;
 }
 
+// Insert code to randomize the representation of the immediate.  Return
+// a register that holds the (derandomized) value of the immediate.
+// WARNING: Constant blinding overwrites the flags register.
+Variable *TargetX8632::randomizeImmediate(Constant *Immediate) {
+  assert(llvm::isa<ConstantInteger>(Immediate) ||
+         llvm::isa<ConstantRelocatable>(Immediate));
+
+  if (CLRandomizeImmediates == Randomize_None)
+    return legalizeToVar(Immediate);
+
+  Variable *Dest = makeReg(Immediate->getType());
+
+  if (CLRandomizeImmediates == Randomize_ConstantPooling) {
+    const Type Ty = Immediate->getType();
+    const int64_t Offset = 0;
+    const IceString Name = nameImmediate(Immediate);
+    const bool SuppressMangling = true;
+    Ctx->addConstantPooledImmediate(Name, Immediate);
+    Constant *Sym = Ctx->getConstantSym(Ty, Offset, Name, SuppressMangling);
+    // LEAHACK: Once a proper assembler is used, change this to be
+    // mov Dest, [Sym].
+    _mov(Dest, OperandX8632Mem::create(Func, Ty, NULL, Sym));
+  } else {
+    assert(CLRandomizeImmediates == Randomize_ConstantBlinding);
+    // Mask integer immediates with a random XOR key.
+    ConstantInteger *IntegerImmediate = llvm::cast<ConstantInteger>(Immediate);
+    assert(IntegerImmediate->getType() != IceType_i64);
+    uint64_t Value = IntegerImmediate->getValue();
+    if (!ConstantBlindingCookieInitialized) {
+      RandomNumberGeneratorWrapper RNG(Ctx->getRNG());
+      ConstantBlindingCookie =
+          RNG.next((uint64_t)std::numeric_limits<uint32_t>::max() + 1);
+      ConstantBlindingCookieInitialized = true;
+    }
+    uint32_t Mask1 = ConstantBlindingCookie;
+    uint32_t Mask2 = Mask1 ^ Value;
+    _mov(Dest, Ctx->getConstantInt(IceType_i32, Mask1));
+    _xor(Dest, Ctx->getConstantInt(IceType_i32, Mask2));
+  }
+
+  return Dest;
+}
+
 Operand *TargetX8632::legalize(Operand *From, LegalMask Allowed,
                                bool AllowOverlap, int32_t RegNum) {
   // Assert that a physical register is allowed.  To date, all calls
   // to legalize() allow a physical register.  If a physical register
   // needs to be explicitly disallowed, then new code will need to be
   // written to force a spill.
   assert(Allowed & Legal_Reg);
   // If we're asking for a specific physical register, make sure we're
   // not allowing any other operand kinds.  (This could be future
   // work, e.g. allow the shl shift amount to be either an immediate
   // or in ecx.)
   assert(RegNum == Variable::NoRegister || Allowed == Legal_Reg);
   if (OperandX8632Mem *Mem = llvm::dyn_cast<OperandX8632Mem>(From)) {
     // Before doing anything with a Mem operand, we need to ensure
     // that the Base and Index components are in physical registers.
     Variable *Base = Mem->getBase();
     Variable *Index = Mem->getIndex();
+    Constant *Offset = Mem->getOffset();
     Variable *RegBase = NULL;
     Variable *RegIndex = NULL;
     if (Base) {
       RegBase = legalizeToVar(Base, true);
     }
     if (Index) {
       RegIndex = legalizeToVar(Index, true);
     }
+
+    if (immediateShouldBeRandomized(Offset)) {
+      // lea new_base [base + randomize(offset)]
+      Variable *RegOffset = randomizeImmediate(Offset);
+      OperandX8632Mem *NewBaseAddr = OperandX8632Mem::create(
+          Func, Mem->getType(), RegBase, NULL, RegOffset, 0);
+      Variable *NewBase = makeReg(IceType_i32);
+      _lea(NewBase, NewBaseAddr);
+      RegBase = NewBase;
+      Offset = NULL;
+    }
+
     if (Base != RegBase || Index != RegIndex) {
-      From = OperandX8632Mem::create(
-          Func, Mem->getType(), RegBase, Mem->getOffset(), RegIndex,
-          Mem->getShift(), Mem->getSegmentRegister());
+      From = OperandX8632Mem::create(Func, Mem->getType(), RegBase, Offset,
+                                     RegIndex, Mem->getShift(),
+                                     Mem->getSegmentRegister());
     }
 
     if (!(Allowed & Legal_Mem)) {
       From = copyToReg(From, RegNum);
     }
     return From;
   }
   if (llvm::isa<Constant>(From)) {
     if (llvm::isa<ConstantUndef>(From)) {
       // Lower undefs to zero.  Another option is to lower undefs to an
       // uninitialized register; however, using an uninitialized register
       // results in less predictable code.
       //
       // If in the future the implementation is changed to lower undef
       // values to uninitialized registers, a FakeDef will be needed:
       //     Context.insert(InstFakeDef::create(Func, Reg));
       // This is in order to ensure that the live range of Reg is not
       // overestimated.  If the constant being lowered is a 64 bit value,
       // then the result should be split and the lo and hi components will
       // need to go in uninitialized registers.
       if (isVectorType(From->getType()))
         return makeVectorOfZeros(From->getType());
       From = Ctx->getConstantZero(From->getType());
     }
     // There should be no constants of vector type (other than undef).
     assert(!isVectorType(From->getType()));
+
+    if (immediateShouldBeRandomized(From)) {
+      return randomizeImmediate(llvm::cast<Constant>(From));
+    }
+
     bool NeedsReg = false;
     if (!(Allowed & Legal_Imm))
       // Immediate specifically not allowed
       NeedsReg = true;
     // TODO(stichnot): LEAHACK: remove Legal_Reloc once a proper
     // emitter is used.
     if (!(Allowed & Legal_Reloc) && llvm::isa<ConstantRelocatable>(From))
       // Relocatable specifically not allowed
       NeedsReg = true;
     if (!(Allowed & Legal_Mem) &&
@@ skipping 241 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