Subzero: Randomly insert nops.

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 110 matching lines @@
 }
 
 // The maximum number of arguments to pass in XMM registers
 const uint32_t X86_MAX_XMM_ARGS = 4;
 // The number of bits in a byte
 const uint32_t X86_CHAR_BIT = 8;
 // 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 maximum supported length of a NOP instruction (all smaller
+// lengths are also supported)
+const uint32_t X86_MAX_NOP_LEN = 9;

[jvoung (off chromium), 2014/08/14 15:17:17]

Does it actually help to add nops of up to 9 bytes?

The UCI CGO paper only has a table of 7 nop candidates (of which 5 are not awful
for performance). The choices are just the 1-byte nop, and several 2-byte nop
variants. By default only one of the 5 may be randomly inserted. It sounds like
the main point is that the nop can turn non-bundle-aligned streams of
instructions into things that are less useful when executed -- e.g., some of the
2 byte nops, if jumped into the middle-of, are interpreted as privileged
instructions that cannot be run:
(https://www.ics.uci.edu/~ahomescu/multicompiler_cgo13.pdf)

[wala, 2014/08/14 23:29:50]

Thanks for the link.

That paper makes it clear that length is not the most important attribute of the
nop.

To this end, I've changed the NOP instruction to take a "nop variant" parameter
instead of a "length" parameter.

Variant is currently an integer, but eventually it should be expanded into an
enum once it is decided which nop sequences to use.

 
 // Value is a size in bytes.  Return Value adjusted to the next highest
 // multiple of the stack alignment.
 uint32_t applyStackAlignment(uint32_t Value) {
   // power of 2
   assert((X86_STACK_ALIGNMENT_BYTES & (X86_STACK_ALIGNMENT_BYTES - 1)) == 0);
   return (Value + X86_STACK_ALIGNMENT_BYTES - 1) & -X86_STACK_ALIGNMENT_BYTES;
 }
 
 // Instruction set options
@@ skipping 244 matching lines @@
   T_regAlloc.printElapsedUs(Context, "regAlloc()");
   Func->dump("After linear scan regalloc");
 
   // Stack frame mapping.
   Timer T_genFrame;
   Func->genFrame();
   if (Func->hasError())
     return;
   T_genFrame.printElapsedUs(Context, "genFrame()");
   Func->dump("After stack frame mapping");
+
+  // Nop insertion
+  if (shouldDoNopInsertion()) {
+    Func->doNopInsertion();
+  }
 }
 
 void TargetX8632::translateOm1() {
   GlobalContext *Context = Func->getContext();
   Timer T_placePhiLoads;
   Func->placePhiLoads();
   if (Func->hasError())
     return;
   T_placePhiLoads.printElapsedUs(Context, "placePhiLoads()");
   Timer T_placePhiStores;
@@ skipping 18 matching lines @@
     return;
   T_genCode.printElapsedUs(Context, "genCode()");
   Func->dump("After initial x8632 codegen");
 
   Timer T_genFrame;
   Func->genFrame();
   if (Func->hasError())
     return;
   T_genFrame.printElapsedUs(Context, "genFrame()");
   Func->dump("After stack frame mapping");
+
+  // Nop insertion
+  if (shouldDoNopInsertion()) {
+    Func->doNopInsertion();
+  }
 }
 
 IceString TargetX8632::RegNames[] = {
 #define X(val, init, name, name16, name8, scratch, preserved, stackptr,        \
           frameptr, isI8, isInt, isFP)                                         \
   name,
   REGX8632_TABLE
 #undef X
 };
 
@@ skipping 3147 matching lines @@
   computeAddressOpt(Base, Index, Shift, Offset);
   if (Base && Addr != Base) {
     Constant *OffsetOp = Ctx->getConstantInt(IceType_i32, Offset);
     Addr = OperandX8632Mem::create(Func, Dest->getType(), Base, OffsetOp, Index,
                                    Shift, SegmentReg);
     Inst->setDeleted();
     Context.insert(InstLoad::create(Func, Dest, Addr));
   }
 }
 
+void TargetX8632::randomlyInsertNop(float Probability) {
+  RandomNumberGeneratorWrapper RNG = Ctx->getRNG();
+  if (RNG.getTrueWithProbability(Probability)) {
+    _nop(1 + RNG.next(X86_MAX_NOP_LEN));
+  }
+}
+
 void TargetX8632::lowerPhi(const InstPhi * /*Inst*/) {
   Func->setError("Phi found in regular instruction list");
 }
 
 void TargetX8632::lowerRet(const InstRet *Inst) {
   Variable *Reg = NULL;
   if (Inst->hasRetValue()) {
     Operand *Src0 = legalize(Inst->getRetValue());
     if (Src0->getType() == IceType_i64) {
       Variable *eax = legalizeToVar(loOperand(Src0), false, Reg_eax);
@@ skipping 639 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