[LoopUnrollRuntime] Add option to assume the non latch exit block to be predictable.

[Whitney]

Summary

Add option -unroll-runtime-other-exit-predictable to assume the non latch exit block to be predictable.

[bmahjour]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

507

IIUC this is basically trying to avoid the check for the "deoptimize" call on line 514, right? In that case can we just add this check to that line and update the comments on line 512 with something like: ". When UnrollRuntimeAtMostTwoExits is specified we assume the other exit branch is predictable even if it has no deoptimize call"?

llvm/test/Transforms/LoopUnroll/runtime-loop-at-most-two-exits.ll

98 ↗

(On Diff #327321)

how come it is still unrolled?

[Whitney]

Fixed LIT

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

507

When UnrollRuntimeAtMostTwoExits is specified, we also allows OtherExits.size() == 0.

llvm/test/Transforms/LoopUnroll/runtime-loop-at-most-two-exits.ll

98 ↗

(On Diff #327321)

I should remove -unroll-count=2

[Whitney]

update comment.

[bmahjour]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

507

I would have expected that when OtherExits is empty, we are not in a multi-exit-loop scenario so the result of this function won't matter...but I guess it's better to be cautious and explicitly handle that case.

[Meinersbur]

What is the motivation for the switch? Why wouldn't we want to unroll loops with 3 or more exits provided we can and the heuristic sais its profitable? Why is the cutoff at 3? Could we also pass the cutoff-point as an option?

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

499–502

OtherExits.size() > 1 will also make the getTerminatingDeoptimizeCall heuristic fail, so this is not a semantics change. However, I find the structure confusing, especially if we want to add more conditions that enable the optimization. Did you consider the following structure?

if (OtherExits.size() <= 1 && UnrollRuntimeAtMostTwoExits)
  return true;

if (OtherExits.size() == 1 && OtherExits[0]->getTerminatingDeoptimizeCall())
  return true;

// More conditions can be added here
  
return false;

[bmahjour]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

57

I think we can avoid this extra option by initializing the Cutoff to 0. Any number larger than 0 would mean a valid cutoff. (ie 0 means no cutoff enabled, 1 means no multi-exit, 2 means at most 2 exits, etc). It would also render UnrollRuntimeMultiExit obsolete, which can be replaced in this patch or a subsequent one.

[Whitney]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

57

Why UnrollRuntimeMultiExit is obsolete? Do you mean the user of UnrollRuntimeMultiExit can put a very big number?

499–502

What do you think of the current structure? I have added a cutoff option.

[bmahjour]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

57

Yes. I suppose a value of say 10 would be big enough for most cases....the bigger the number of exiting blocks, the less likely it will be profitable to unroll.

[Whitney]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

57

ok, I can put a review for that after this patch get landed.

[Meinersbur]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

490–492

I think @bmahjour's suggestion (and mine) was to completely disable UnrollRuntimeCutoffPoint if it is 0

if (UnrollRuntimeCutoffPoint == 0 ||
      (ExitingBlocks.size() <= UnrollRuntimeCutoffPoint &&
      OtherExits.size() < UnrollRuntimeCutoffPoint))
    return true;

I don't really understand why it bounds both, ExitingBlock and OtherExists (instead of only one of them or the sum of such blocks). Could you explain?

@bmahjour's other point is that it makes UnrollRuntimeMultiExit redundant: -unroll-runtime-multi-exit=true is equivalent to -unroll-runtime-cutoff-point=0 and -unroll-runtime-multi-exit=false` is equivalent to -unroll-runtime-cutoff-point=1 (I think in this case I think canProfitablyUnrollMultiExitLoop would not be called anyway). Do I understand correctly that you would remove the -unroll-runtime-multi-exit in a followup-patch?

[bmahjour]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

57

Yes. I suppose a value of say 10 would be big enough for most cases....the bigger the number of exiting blocks, the less likely it will be profitable to unroll.

...just to clarify this, as Michael pointed out my original intention was to have 0 mean no cutoff (ie any number of exit/exiting blocks are allowed)....but the same thing can effectively be achieved with a large value specified for the option.

[Meinersbur]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

57

IMHO having 0 as no cutoff is more idiomatic than having an arbitrary-large cutoff (of 0 has otherwise no meaning).

Alternatively, -1, interpreted as an unsigned number, would be the largest possible value, sometimes used to represent "infinity".

[Whitney]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

490–492

Current behaviour:
-unroll-runtime-multi-exit==true => return true
-unroll-runtime-multi-exit==false => return false
-unroll-runtime-multi-exit not specified => return (ExitingBlocks.size() <= 2 && OtherExits.size() == 1 && OtherExits[0]->getTerminatingDeoptimizeCall())

If we use this code:

if (UnrollRuntimeCutoffPoint == 0 ||
      (ExitingBlocks.size() <= UnrollRuntimeCutoffPoint &&
      OtherExits.size() < UnrollRuntimeCutoffPoint))
    return true;

-unroll-runtime-cutoff-point==0 => return true
-unroll-runtime-cutoff-point==1 => return (ExitingBlocks.size() <= 1 OtherExits.size() < 1) || (ExitingBlocks.size() <= 2 && OtherExits.size() == 1 && OtherExits[0]->getTerminatingDeoptimizeCall())
There is no initial value that can keep the current behaviour of (ExitingBlocks.size() <= 2 && OtherExits.size() == 1 && OtherExits[0]->getTerminatingDeoptimizeCall()).

You are right that there is no direct relation between number of exiting blocks and other exits, so we would have to use two cutoff points.

After rethinking about it more, to achieve my original need, which is to allow unrolling a loop with at most 2 exiting blocks and at most 1 other exit block, I added an option to assume the other exit is predictable.

[bmahjour]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

490–492

ok, this diff is now more like what I had in mind in the beginning (see https://reviews.llvm.org/D97747#inline-916962). Could you please also update the comments on line 506?

[Whitney]

Add comment.

[Meinersbur]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

499–501

This seems to make sense, but isn't this already covered by !L->getExitingBlock() || OtherExits.size() in the function that calls canProfitablyUnrollMultiExitLoop? (I think we could keep it here, just to make it more explicit)

510–511

Looks sensible to me. @bmahjour ?

[bmahjour]

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

510–511

LGTM too.

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

 #define DEBUG_TYPE "loop-unroll"
 
 STATISTIC(NumRuntimeUnrolled,
           "Number of loops unrolled with run-time trip counts");
 static cl::opt<bool> UnrollRuntimeMultiExit(
     "unroll-runtime-multi-exit", cl::init(false), cl::Hidden,
     cl::desc("Allow runtime unrolling for loops with multiple exits, when "
              "epilog is generated"));
+static cl::opt<bool> UnrollRuntimeOtherExitPredictable(
+    "unroll-runtime-other-exit-predictable", cl::init(false), cl::Hidden,
+    cl::desc("Assume the non latch exit block to be predictable"));
 
 /// Connect the unrolling prolog code to the original loop.
 /// The unrolling prolog code contains code to execute the
 /// 'extra' iterations if the run-time trip count modulo the
 /// unroll count is non-zero.
 ///
 /// This function performs the following:
 /// - Create PHI nodes at prolog end block to combine values
 ///   that exit the prolog code and jump around the prolog.
 /// - Add a PHI operand to a PHI node at the loop exit block
#endif
   // The second point is the increase in code size, but this is true
   // irrespective of multiple exits.
 
   // Note: Both the heuristics below are coarse grained. We are essentially
   // enabling unrolling of loops that have a single side exit other than the
   // normal LatchExit (i.e. exiting into a deoptimize block).
   // The heuristics considered are:
   // 1. low number of branches in the unrolled version.
   // 2. high predictability of these extra branches.
   // We avoid unrolling loops that have more than two exiting blocks. This
   // limits the total number of branches in the unrolled loop to be atmost
   // the unroll factor (since one of the exiting blocks is the latch block).
   SmallVector<BasicBlock*, 4> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
   if (ExitingBlocks.size() > 2)
     return false;
 
+  // Allow unrolling of loops with no non latch exit blocks.
+  if (OtherExits.size() == 0)
+    return true;
+
   // The second heuristic is that L has one exit other than the latchexit and
   // that exit is a deoptimize block. We know that deoptimize blocks are rarely
   // taken, which also implies the branch leading to the deoptimize block is
-  // highly predictable.
+  // highly predictable. When UnrollRuntimeOtherExitPredictable is specified, we
+  // assume the other exit branch is predictable even if it has no deoptimize
+  // call.
   return (OtherExits.size() == 1 &&
-          OtherExits[0]->getTerminatingDeoptimizeCall());
+          (UnrollRuntimeOtherExitPredictable ||
+           OtherExits[0]->getTerminatingDeoptimizeCall()));
   // TODO: These can be fine-tuned further to consider code size or deopt states
   // that are captured by the deoptimize exit block.
   // Also, we can extend this to support more cases, if we actually
   // know of kinds of multiexit loops that would benefit from unrolling.
 }
 
 // Assign the maximum possible trip count as the back edge weight for the
 // remainder loop if the original loop comes with a branch weight.