GVN-hoist: limit hoisting depth (PR28670)

[sebpop]

Summary

This patch adds an option to specify the maximum depth in a BB at which to consider hoisting instructions.
Hoisting instructions from a deeper level is not profitable as it increases register pressure and compilation time.

[• dberlin]

Two things:

1. I'd rather not add knobs till we have to. So far, i didn't see that the compile time is being hurt once the other issue is fixed.

Am i missing something?

2. Assuming i missed something and we want to do that, do you have any data on how this magic number affects performance at different numbers?

IE do you have any data that says "100" is right?

It would be ideal to have some data that says:

"at 0, we get no benefit
at 10, we get x benefit and no regressions
..
at 10000, we get x benefit and x regressions"

or something that gives us an idea that "100" is the right knob.

[sebpop]

Data from compiling the test-suite for x86_64-linux with -mllvm -stats and varying the flag:
from the RegAlloc metrics we see that the minimum number of spills occurs for 100 and starts increasing back at 125.

-gvn-hoist-max-depth=0:
Number of rematerialized defs for spilling: 18286
Number of rematerialized defs for splitting: 5727
Number of spill slots allocated: 44014
Number of spilled live ranges: 62657
Number of spills inserted: 51753
gvn-hoist.*: 0

-gvn-hoist-max-depth=50:
Number of rematerialized defs for spilling: 18213
Number of rematerialized defs for splitting: 5827
Number of spill slots allocated: 43956
Number of spilled live ranges: 62539
Number of spills inserted: 51643
gvn-hoist.*Number of instructions hoisted: 21564
gvn-hoist.*Number of instructions removed: 30019
gvn-hoist.*Number of loads hoisted: 14697
gvn-hoist.*Number of loads removed: 20247
gvn-hoist.*Number of stores hoisted: 15
gvn-hoist.*Number of stores removed: 15
gvn-hoist.*Number of calls hoisted: 8
gvn-hoist.*Number of calls removed: 8

-gvn-hoist-max-depth=100:
Number of rematerialized defs for spilling: 18223
Number of rematerialized defs for splitting: 5817
Number of spill slots allocated: 43961
Number of spilled live ranges: 62521
Number of spills inserted: 51623
gvn-hoist.*Number of instructions hoisted: 21941
gvn-hoist.*Number of instructions removed: 31106
gvn-hoist.*Number of loads hoisted: 14951
gvn-hoist.*Number of loads removed: 21063
gvn-hoist.*Number of stores hoisted: 15
gvn-hoist.*Number of stores removed: 15
gvn-hoist.*Number of calls hoisted: 8
gvn-hoist.*Number of calls removed: 8

-gvn-hoist-max-depth=125:
Number of rematerialized defs for spilling: 18223
Number of rematerialized defs for splitting: 5817
Number of spill slots allocated: 43969
Number of spilled live ranges: 62520
Number of spills inserted: 51632
gvn-hoist.*Number of instructions hoisted: 22044
gvn-hoist.*Number of instructions removed: 31308
gvn-hoist.*Number of loads hoisted: 15034
gvn-hoist.*Number of loads removed: 21221
gvn-hoist.*Number of stores hoisted: 15
gvn-hoist.*Number of stores removed: 15
gvn-hoist.*Number of calls hoisted: 8
gvn-hoist.*Number of calls removed: 8

-gvn-hoist-max-depth=150:
Number of rematerialized defs for spilling: 18223
Number of rematerialized defs for splitting: 5817
Number of spill slots allocated: 43970
Number of spilled live ranges: 62516
Number of spills inserted: 51627
gvn-hoist.*Number of instructions hoisted: 22128
gvn-hoist.*Number of instructions removed: 31467
gvn-hoist.*Number of loads hoisted: 15086
gvn-hoist.*Number of loads removed: 21322
gvn-hoist.*Number of stores hoisted: 15
gvn-hoist.*Number of stores removed: 15
gvn-hoist.*Number of calls hoisted: 8
gvn-hoist.*Number of calls removed: 8

-gvn-hoist-max-depth=200:
Number of rematerialized defs for spilling: 18223
Number of rematerialized defs for splitting: 5817
Number of spill slots allocated: 43993
Number of spilled live ranges: 62552
Number of spills inserted: 51661
gvn-hoist.*Number of instructions hoisted: 22348
gvn-hoist.*Number of instructions removed: 31864
gvn-hoist.*Number of loads hoisted: 15200
gvn-hoist.*Number of loads removed: 21542
gvn-hoist.*Number of stores hoisted: 15
gvn-hoist.*Number of stores removed: 15
gvn-hoist.*Number of calls hoisted: 8
gvn-hoist.*Number of calls removed: 8

-gvn-hoist-max-depth=-1: (i.e., no bounds)
Number of rematerialized defs for spilling: 18244
Number of rematerialized defs for splitting: 5817
Number of spill slots allocated: 44070
Number of spilled live ranges: 62619
Number of spills inserted: 51740
gvn-hoist.*Number of instructions hoisted: 22508
gvn-hoist.*Number of instructions removed: 32925
gvn-hoist.*Number of loads hoisted: 15239
gvn-hoist.*Number of loads removed: 22004
gvn-hoist.*Number of stores hoisted: 15
gvn-hoist.*Number of stores removed: 15
gvn-hoist.*Number of calls hoisted: 8
gvn-hoist.*Number of calls removed: 8

llvm/lib/Transforms/Scalar/GVNHoist.cpp

static cl::opt<int>
     MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1),
                         cl::desc("Max number of instructions to hoist "
                                  "(default unlimited = -1)"));
 static cl::opt<int> MaxNumberOfBBSInPath(
     "gvn-hoist-max-bbs", cl::Hidden, cl::init(4),
     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)"));
+
 namespace {
 
 // Provides a sorting function based on the execution order of two instructions.
 struct SortByDFSIn {
 private:
   DenseMap<const BasicBlock *, unsigned> &DFSNumber;
 
 public:
public:
   // Hoist all expressions. Returns Number of scalars hoisted
   // and number of non-scalars hoisted.
   std::pair<unsigned, unsigned> hoistExpressions(Function &F) {
     InsnInfo II;
     LoadInfo LI;
     StoreInfo SI;
     CallInfo CI;
     for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
+      int InstructionNb = 0;
       for (Instruction &I1 : *BB) {
+        // Only hoist the first instructions in BB up to MaxDepthInBB. Hoisting
+        // deeper may increase the register pressure and compilation time.
+        if (MaxDepthInBB != -1 && InstructionNb++ >= MaxDepthInBB)
+          break;
+
         if (auto *Load = dyn_cast<LoadInst>(&I1))
           LI.insert(Load, VN);
         else if (auto *Store = dyn_cast<StoreInst>(&I1))
           SI.insert(Store, VN);
         else if (auto *Call = dyn_cast<CallInst>(&I1)) {
           if (auto *Intr = dyn_cast<IntrinsicInst>(Call)) {
             if (isa<DbgInfoIntrinsic>(Intr) ||
                 Intr->getIntrinsicID() == Intrinsic::assume)