Subzero: Randomly insert nops.

Adds command line options -nop-insertion, -nop-insertion-probability=X, and -max-nops-per-instruction=X.

BUG=none
R=jvoung@chromium.org, stichnot@chromium.org

Review URL: https://codereview.chromium.org/463563006

src/IceCfg.cpp

diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 49e9806..faaabe9 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -121,6 +121,12 @@
   }
 }
 
+void Cfg::doNopInsertion() {
+  for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
+    (*I)->doNopInsertion();
+  }
+}
+
 void Cfg::genCode() {
   for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
     (*I)->genCode();

src/IceCfg.h

diff --git a/src/IceCfg.h b/src/IceCfg.h
index 856b145..e12bc9d 100644
--- a/src/IceCfg.h
+++ b/src/IceCfg.h
@@ -88,6 +88,7 @@
   void deletePhis();
   void doAddressOpt();
   void doArgLowering();
+  void doNopInsertion();
   void genCode();
   void genFrame();
   void livenessLightweight();

src/IceCfgNode.cpp

diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index 22915b2..696a2f0 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -191,6 +191,24 @@
   }
 }
 
+void CfgNode::doNopInsertion() {
+  TargetLowering *Target = Func->getTarget();
+  LoweringContext &Context = Target->getContext();
+  Context.init(this);
+  while (!Context.atEnd()) {
+    Target->doNopInsertion();
+    // Ensure Cur=Next, so that the nops are inserted before the current
+    // instruction rather than after.
+    Context.advanceNext();
+    Context.advanceCur();
+  }
+  // Insert before all instructions.
+  Context.setInsertPoint(getInsts().begin());
+  Context.advanceNext();
+  Context.advanceCur();
+  Target->doNopInsertion();
+}
+
 // Drives the target lowering.  Passes the current instruction and the
 // next non-deleted instruction for target lowering.
 void CfgNode::genCode() {

src/IceCfgNode.h

diff --git a/src/IceCfgNode.h b/src/IceCfgNode.h
index ea50dca..bf11844 100644
--- a/src/IceCfgNode.h
+++ b/src/IceCfgNode.h
@@ -55,6 +55,7 @@
   void placePhiStores();
   void deletePhis();
   void doAddressOpt();
+  void doNopInsertion();
   void genCode();
   void livenessLightweight();
   bool liveness(Liveness *Liveness);

src/IceInstX8632.cpp

diff --git a/src/IceInstX8632.cpp b/src/IceInstX8632.cpp
index 0b99c80..a1a4d68 100644
--- a/src/IceInstX8632.cpp
+++ b/src/IceInstX8632.cpp
@@ -241,6 +241,9 @@
   addSource(Source);
 }
 
+InstX8632Nop::InstX8632Nop(Cfg *Func, InstX8632Nop::NopVariant Variant)
+    : InstX8632(Func, InstX8632::Nop, 0, NULL), Variant(Variant) {}
+
 InstX8632Fld::InstX8632Fld(Cfg *Func, Operand *Src)
     : InstX8632(Func, InstX8632::Fld, 1, NULL) {
   addSource(Src);
@@ -1058,6 +1061,17 @@
   dumpSources(Func);
 }
 
+void InstX8632Nop::emit(const Cfg *Func) const {
+  Ostream &Str = Func->getContext()->getStrEmit();
+  // TODO: Emit the right code for each variant.
+  Str << "\tnop\t# variant = " << Variant << "\n";
+}
+
+void InstX8632Nop::dump(const Cfg *Func) const {
+  Ostream &Str = Func->getContext()->getStrDump();
+  Str << "nop (variant = " << Variant << ")";
+}
+
 void InstX8632Fld::emit(const Cfg *Func) const {
   Ostream &Str = Func->getContext()->getStrEmit();
   assert(getSrcSize() == 1);

src/IceInstX8632.h

diff --git a/src/IceInstX8632.h b/src/IceInstX8632.h
index 64ce4a0..834e061 100644
--- a/src/IceInstX8632.h
+++ b/src/IceInstX8632.h
@@ -175,6 +175,7 @@
     Mulps,
     Mulss,
     Neg,
+    Nop,
     Or,
     Padd,
     Pand,
@@ -1060,6 +1061,28 @@
   virtual ~InstX8632Movzx() {}
 };
 
+// Nop instructions of varying length
+class InstX8632Nop : public InstX8632 {
+public:
+  // TODO: Replace with enum.
+  typedef unsigned NopVariant;
+
+  static InstX8632Nop *create(Cfg *Func, NopVariant Variant) {
+    return new (Func->allocate<InstX8632Nop>()) InstX8632Nop(Func, Variant);
+  }
+  virtual void emit(const Cfg *Func) const;
+  virtual void dump(const Cfg *Func) const;
+  static bool classof(const Inst *Inst) { return isClassof(Inst, Nop); }
+
+private:
+  InstX8632Nop(Cfg *Func, SizeT Length);
+  InstX8632Nop(const InstX8632Nop &) LLVM_DELETED_FUNCTION;
+  InstX8632Nop &operator=(const InstX8632Nop &) LLVM_DELETED_FUNCTION;
+  virtual ~InstX8632Nop() {}
+
+  NopVariant Variant;
+};
+
 // Fld - load a value onto the x87 FP stack.
 class InstX8632Fld : public InstX8632 {
 public:

src/IceRNG.cpp

diff --git a/src/IceRNG.cpp b/src/IceRNG.cpp
index 6a9f515..b874d83 100644
--- a/src/IceRNG.cpp
+++ b/src/IceRNG.cpp
@@ -26,6 +26,8 @@
 RandomSeed("rng-seed", cl::desc("Seed the random number generator"),
            cl::init(time(0)));
 
+const unsigned MAX = 2147483647;
+
 } // end of anonymous namespace
 
 // TODO(wala,stichnot): Switch to RNG implementation from LLVM or C++11.
@@ -39,8 +41,12 @@
 
 uint64_t RandomNumberGenerator::next(uint64_t Max) {
   // Lewis, Goodman, and Miller (1969)
-  State = (16807 * State) % 2147483647;
+  State = (16807 * State) % MAX;
   return State % Max;
 }
 
+bool RandomNumberGeneratorWrapper::getTrueWithProbability(float Probability) {
+  return RNG.next(MAX) < Probability * MAX;
+}
+
 } // end of namespace Ice

src/IceRNG.h

diff --git a/src/IceRNG.h b/src/IceRNG.h
index 423aee0..4d6c397 100644
--- a/src/IceRNG.h
+++ b/src/IceRNG.h
@@ -16,6 +16,7 @@
 
 #include <stdint.h>
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Compiler.h"
 
 namespace Ice {
 
@@ -25,9 +26,31 @@
   uint64_t next(uint64_t Max);
 
 private:
+  RandomNumberGenerator(const RandomNumberGenerator &) LLVM_DELETED_FUNCTION;
+  RandomNumberGenerator &
+  operator=(const RandomNumberGenerator &) LLVM_DELETED_FUNCTION;
+
   uint64_t State;
 };
 
+// This class adds additional random number generator utilities. The
+// reason for the wrapper class is that we want to keep the
+// RandomNumberGenerator interface identical to LLVM's.
+class RandomNumberGeneratorWrapper {
+public:
+  uint64_t next(uint64_t Max) { return RNG.next(Max); }
+  bool getTrueWithProbability(float Probability);
+  RandomNumberGeneratorWrapper(RandomNumberGenerator &RNG) : RNG(RNG) {}
+
+private:
+  RandomNumberGeneratorWrapper(const RandomNumberGeneratorWrapper &)
+      LLVM_DELETED_FUNCTION;
+  RandomNumberGeneratorWrapper &
+  operator=(const RandomNumberGeneratorWrapper &) LLVM_DELETED_FUNCTION;
+
+  RandomNumberGenerator &RNG;
+};
+
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICERNG_H

src/IceTargetLowering.cpp

diff --git a/src/IceTargetLowering.cpp b/src/IceTargetLowering.cpp
index 0034de5..057a3ea 100644
--- a/src/IceTargetLowering.cpp
+++ b/src/IceTargetLowering.cpp
@@ -22,8 +22,25 @@
 #include "IceTargetLowering.h"
 #include "IceTargetLoweringX8632.h"
 
+#include "llvm/Support/CommandLine.h"
+
 namespace Ice {
 
+namespace {
+
+namespace cl = llvm::cl;
+cl::opt<bool> DoNopInsertion("nop-insertion", cl::desc("Randomly insert NOPs"),
+                             cl::init(false));
+
+cl::opt<int> MaxNopsPerInstruction(
+    "max-nops-per-instruction",
+    cl::desc("Max number of nops to insert per instruction"), cl::init(1));
+
+cl::opt<int> NopProbabilityAsPercentage(
+    "nop-insertion-percentage",
+    cl::desc("Nop insertion probability as percentage"), cl::init(10));
+} // end of anonymous namespace
+
 void LoweringContext::init(CfgNode *N) {
   Node = N;
   Begin = getNode()->getInsts().begin();
@@ -90,6 +107,20 @@
   Context.advanceNext();
 }
 
+bool TargetLowering::shouldDoNopInsertion() const { return DoNopInsertion; }
+
+void TargetLowering::doNopInsertion() {
+  Inst *I = *Context.getCur();
+  bool ShouldSkip = llvm::isa<InstFakeUse>(I) || llvm::isa<InstFakeDef>(I) ||
+                    llvm::isa<InstFakeKill>(I) || I->isRedundantAssign() ||
+                    I->isDeleted();
+  if (!ShouldSkip) {
+    for (int I = 0; I < MaxNopsPerInstruction; ++I) {
+      randomlyInsertNop(NopProbabilityAsPercentage / 100.0);
+    }
+  }
+}
+
 // Lowers a single instruction according to the information in
 // Context, by checking the Context.Cur instruction kind and calling
 // the appropriate lowering method.  The lowering method should insert

src/IceTargetLowering.h

diff --git a/src/IceTargetLowering.h b/src/IceTargetLowering.h
index 39e08de..6bf1424 100644
--- a/src/IceTargetLowering.h
+++ b/src/IceTargetLowering.h
@@ -121,6 +121,8 @@
 
   // Tries to do address mode optimization on a single instruction.
   void doAddressOpt();
+  // Randomly insert NOPs.
+  void doNopInsertion();
   // Lowers a single instruction.
   void lower();
 
@@ -136,6 +138,7 @@
   virtual SizeT getFrameOrStackReg() const = 0;
   virtual size_t typeWidthInBytesOnStack(Type Ty) const = 0;
   bool hasComputedFrame() const { return HasComputedFrame; }
+  bool shouldDoNopInsertion() const;
   int32_t getStackAdjustment() const { return StackAdjustment; }
   void updateStackAdjustment(int32_t Offset) { StackAdjustment += Offset; }
   void resetStackAdjustment() { StackAdjustment = 0; }
@@ -193,6 +196,7 @@
 
   virtual void doAddressOptLoad() {}
   virtual void doAddressOptStore() {}
+  virtual void randomlyInsertNop(float Probability) = 0;
   // This gives the target an opportunity to post-process the lowered
   // expansion before returning.  The primary intention is to do some
   // Register Manager activity as necessary, specifically to eagerly

src/IceTargetLoweringX8632.cpp

diff --git a/src/IceTargetLoweringX8632.cpp b/src/IceTargetLoweringX8632.cpp
index 35792aa..d36ad16 100644
--- a/src/IceTargetLoweringX8632.cpp
+++ b/src/IceTargetLoweringX8632.cpp
@@ -134,6 +134,8 @@
 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;
 
 // Value and Alignment are in bytes.  Return Value adjusted to the next
 // highest multiple of Alignment.
@@ -391,6 +393,11 @@
     return;
   T_genFrame.printElapsedUs(Context, "genFrame()");
   Func->dump("After stack frame mapping");
+
+  // Nop insertion
+  if (shouldDoNopInsertion()) {
+    Func->doNopInsertion();
+  }
 }
 
 void TargetX8632::translateOm1() {
@@ -429,6 +436,11 @@
     return;
   T_genFrame.printElapsedUs(Context, "genFrame()");
   Func->dump("After stack frame mapping");
+
+  // Nop insertion
+  if (shouldDoNopInsertion()) {
+    Func->doNopInsertion();
+  }
 }
 
 IceString TargetX8632::RegNames[] = {
@@ -3670,6 +3682,13 @@
   }
 }
 
+void TargetX8632::randomlyInsertNop(float Probability) {
+  RandomNumberGeneratorWrapper RNG(Ctx->getRNG());
+  if (RNG.getTrueWithProbability(Probability)) {
+    _nop(RNG.next(X86_NUM_NOP_VARIANTS));
+  }
+}
+
 void TargetX8632::lowerPhi(const InstPhi * /*Inst*/) {
   Func->setError("Phi found in regular instruction list");
 }

src/IceTargetLoweringX8632.h

diff --git a/src/IceTargetLoweringX8632.h b/src/IceTargetLoweringX8632.h
index ebe6ba9..499790e 100644
--- a/src/IceTargetLoweringX8632.h
+++ b/src/IceTargetLoweringX8632.h
@@ -104,6 +104,7 @@
   virtual void lowerUnreachable(const InstUnreachable *Inst);
   virtual void doAddressOptLoad();
   virtual void doAddressOptStore();
+  virtual void randomlyInsertNop(float Probability);
 
   // Naive lowering of cmpxchg.
   void lowerAtomicCmpxchg(Variable *DestPrev, Operand *Ptr, Operand *Expected,
@@ -327,6 +328,9 @@
   void _neg(Variable *SrcDest) {
     Context.insert(InstX8632Neg::create(Func, SrcDest));
   }
+  void _nop(SizeT Variant) {
+    Context.insert(InstX8632Nop::create(Func, Variant));
+  }
   void _or(Variable *Dest, Operand *Src0) {
     Context.insert(InstX8632Or::create(Func, Dest, Src0));
   }