GVN-hoist: limit the length of dependent instructions

[sebpop]

Summary

Limit the number of times the while(1) loop is executed.
With this restriction the number of hoisted instructions does not change in a significant way on the test-suite.

llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp

static cl::opt<int> MaxNumberOfBBSInPath(
     cl::desc("Max number of basic blocks on the path between "
              "hoisting locations (default = 4, unlimited = -1)"));
 
 static cl::opt<int> MaxDepthInBB(
     "gvn-hoist-max-depth", cl::Hidden, cl::init(100),
     cl::desc("Hoist instructions from the beginning of the BB up to the "
              "maximum specified depth (default = 100, unlimited = -1)"));
 
+static cl::opt<int> MaxChainLength(
+    "gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
+    cl::desc("Maximum length of dependent chains to hoist "
+             "(default = 10, unlimited = -1)"));
+
 namespace {
 
 // Provides a sorting function based on the execution order of two instructions.
 struct SortByDFSIn {
 private:
   DenseMap<const Value *, unsigned> &DFSNumber;
 
 public:
bool run(Function &F) {
     unsigned BBI = 0;
     for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) {
       DFSNumber[BB] = ++BBI;
       unsigned I = 0;
       for (auto &Inst: *BB)
         DFSNumber[&Inst] = ++I;
     }
 
+    int ChainLength = 0;
+
     // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
     while (1) {
+      if (MaxChainLength != -1 && ++ChainLength >= MaxChainLength)
+        return Res;
+
       auto HoistStat = hoistExpressions(F);
       if (HoistStat.first + HoistStat.second == 0)
         return Res;
 
       if (HoistStat.second > 0)
         // To address a limitation of the current GVN, we need to rerun the
         // hoisting after we hoisted loads or stores in order to be able to
         // hoist all scalars dependent on the hoisted ld/st.