This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by Whitney on Mar 1 2021, 4:41 PM.

Details

Diff Detail

Event Timeline

Whitney created this revision.Mar 1 2021, 4:41 PM
Whitney requested review of this revision.Mar 1 2021, 4:41 PM
bmahjour added inline comments.Mar 2 2021, 8:42 AM
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 updated this revision to Diff 327497.Mar 2 2021, 9:52 AM
Whitney marked an inline comment as done.

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 updated this revision to Diff 327499.Mar 2 2021, 9:56 AM

update comment.

bmahjour added inline comments.Mar 2 2021, 10:48 AM
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.

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;
Whitney updated this revision to Diff 327773.Mar 3 2021, 6:38 AM
Whitney marked 3 inline comments as done.
Whitney edited the summary of this revision. (Show Details)
bmahjour added inline comments.Mar 3 2021, 7:03 AM
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 updated this revision to Diff 327792.Mar 3 2021, 7:25 AM
Whitney added inline comments.
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 added inline comments.Mar 3 2021, 7:38 AM
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 edited the summary of this revision. (Show Details)Mar 3 2021, 7:42 AM
Whitney retitled this revision from [LoopUnrollRuntime] Add option to unroll loops with at most two exit/exiting blocks. to [LoopUnrollRuntime] Add option to unroll loops with at most a specified number of exit/exiting blocks..
Whitney marked 2 inline comments as done.
Whitney added inline comments.
llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp
57

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

Meinersbur added inline comments.Mar 3 2021, 8:24 AM
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 added inline comments.Mar 3 2021, 8:39 AM
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 added inline comments.Mar 3 2021, 9:18 AM
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 updated this revision to Diff 327835.Mar 3 2021, 9:52 AM
Whitney marked 3 inline comments as done.
Whitney retitled this revision from [LoopUnrollRuntime] Add option to unroll loops with at most a specified number of exit/exiting blocks. to [LoopUnrollRuntime] Add option to assume the non latch exit block to be predictable..
Whitney edited the summary of this revision. (Show Details)
Whitney added inline comments.
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 added inline comments.Mar 3 2021, 10:03 AM
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 updated this revision to Diff 327848.Mar 3 2021, 10:16 AM

Add comment.

Whitney marked an inline comment as done.Mar 3 2021, 10:17 AM
Meinersbur added inline comments.Mar 3 2021, 10:41 AM
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 ?

Whitney marked 2 inline comments as done.Mar 3 2021, 10:51 AM
bmahjour accepted this revision.Mar 3 2021, 10:55 AM
bmahjour added inline comments.
llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp
510–511

LGTM too.

This revision is now accepted and ready to land.Mar 3 2021, 10:55 AM
Meinersbur accepted this revision.Mar 3 2021, 11:06 AM
This revision was landed with ongoing or failed builds.Mar 3 2021, 12:43 PM
This revision was automatically updated to reflect the committed changes.