[llvm] Don't use Optional::getValue (NFC)

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with
the cleanup of InstructionSimplify in one commit.

This is the alternative to the less invasive clang-format only patch: D126783

Reviewed By: spatel, rengolin

Differential Revision: https://reviews.llvm.org/D126889

show more ...

[unroll] Strengthen verification of analysis updates under expensive asserts

I am suspecting a bug around updates of loop info for unreachable exits, but don't have a test case. Running this locall

[unroll] Strengthen verification of analysis updates under expensive asserts

I am suspecting a bug around updates of loop info for unreachable exits, but don't have a test case. Running this locally on make check didn't reveal anything, we'll see if the expensive checks bots find it.

show more ...

Revert "[unroll] Prune all but first copy of invariant exit"

This reverts commit 9bd22595bad36cd19f5e7ae18ccd9f41cba29dc5.

Seeing some bot failures which look plausibly connected. Revert while inv

Revert "[unroll] Prune all but first copy of invariant exit"

This reverts commit 9bd22595bad36cd19f5e7ae18ccd9f41cba29dc5.

Seeing some bot failures which look plausibly connected. Revert while investigating/waiting for bots to stablize.

e.g. https://lab.llvm.org/buildbot#builders/36/builds/15933

show more ...

[unroll] Prune all but first copy of invariant exit

If we have an exit which is controlled by a loop invariant condition and which dominates the latch, we know only the copy in the first unrolled it

[unroll] Prune all but first copy of invariant exit

If we have an exit which is controlled by a loop invariant condition and which dominates the latch, we know only the copy in the first unrolled iteration can be taken. All other copies are dead.

The change itself is pretty straight forward, but let me add two points of context:
* I'd have expected other transform passes to catch this after unrolling, but I'm seeing multiple examples where we get to the end of O2/O3 without simplifying.
* I'd like to do a stronger change which did CSE during unroll and accounted for invariant expressions (as defined by SCEV instead of trivial ones from LoopInfo), but that doesn't fit cleanly into the current code structure.

Differential Revision: https://reviews.llvm.org/D116496

show more ...

[unroll] Keep unrolled iterations with initial iteration

The unrolling code was previously inserting new cloned blocks at the end of the function. The result of this with typical loop structures is

[unroll] Keep unrolled iterations with initial iteration

The unrolling code was previously inserting new cloned blocks at the end of the function. The result of this with typical loop structures is that the new iterations are placed far from the initial iteration.

With unrolling, the general assumption is that the a) the loop is reasonable hot, and b) the first Count-1 copies of the loop are rarely (if ever) loop exiting. As such, placing Count-1 copies out of line is a fairly poor code placement choice. We'd much rather fall through into the hot (non-exiting) path. For code with branch profiles, later layout would fix this, but this may have a positive impact on non-PGO compiled code.

However, the real motivation for this change isn't performance. Its readability and human understanding. Having to jump around long distances in an IR file to trace an unrolled loop structure is error prone and tedious.

show more ...

[Utils] Use make_early_inc_range (NFC)

[Local] Do not introduce a new `llvm.trap` before `unreachable`

This is the second attempt to remove the `llvm.trap` insertion after
https://reviews.llvm.org/rGe14e7bc4b889dfaffb7180d176a03311df2d4a

[Local] Do not introduce a new `llvm.trap` before `unreachable`

This is the second attempt to remove the `llvm.trap` insertion after
https://reviews.llvm.org/rGe14e7bc4b889dfaffb7180d176a03311df2d4ae6
reverted the first one. It is not clear what the exact issue was back
then and it might already be gone by now, it has been >5 years after
all.

Replaces D106299.

Differential Revision: https://reviews.llvm.org/D106308

show more ...

[LoopUnroll] Push runtime unrolling decision up into tryToUnrollLoop()

Currently, UnrollLoop() is passed an AllowRuntime flag and decides
itself whether runtime unrolling should be used or not. This

[LoopUnroll] Push runtime unrolling decision up into tryToUnrollLoop()

Currently, UnrollLoop() is passed an AllowRuntime flag and decides
itself whether runtime unrolling should be used or not. This patch
pushes the decision into the caller and allows us to eliminate the
ULO.TripCount and ULO.TripMultiple parameters.

Differential Revision: https://reviews.llvm.org/D104487

show more ...

[LoopUnroll] Simplify optimization remarks

Remove dependence on ULO.TripCount/ULO.TripMultiple from ORE and
debug code. For debug code, print information about all exits.
For optimization remarks, o

[LoopUnroll] Simplify optimization remarks

Remove dependence on ULO.TripCount/ULO.TripMultiple from ORE and
debug code. For debug code, print information about all exits.
For optimization remarks, only include the unroll count and the
type of unroll (complete, partial or runtime), but omit detailed
information about exit folding, now that more than one exit may
be folded.

Differential Revision: https://reviews.llvm.org/D104482

show more ...

[LoopUnroll] Fold all exits based on known trip count/multiple

Fold all exits based on known trip count/multiple information from
SCEV. Previously only the latch exit or the single exit were folded.

[LoopUnroll] Fold all exits based on known trip count/multiple

Fold all exits based on known trip count/multiple information from
SCEV. Previously only the latch exit or the single exit were folded.

This doesn't yet eliminate ULO.TripCount and ULO.TripMultiple
entirely: They're still used to a) decide whether runtime unrolling
should be performed and b) for ORE remarks. However, the core
unrolling logic is independent of them now.

Differential Revision: https://reviews.llvm.org/D104203

show more ...

[LoopUnroll] Clamp unroll count to MaxTripCount

Unrolling with more iterations than MaxTripCount is pointless, as
those iterations can never be executed. As such, we clamp ULO.Count
to MaxTripCount

[LoopUnroll] Clamp unroll count to MaxTripCount

Unrolling with more iterations than MaxTripCount is pointless, as
those iterations can never be executed. As such, we clamp ULO.Count
to MaxTripCount if it is known. This means we no longer need to
consider iterations after MaxTripCount for exit folding, and the
CompletelyUnroll flag becomes independent of ULO.TripCount.

Differential Revision: https://reviews.llvm.org/D103748

show more ...

[LoopUnroll] Separate peeling from unrolling

Loop peeling is currently performed as part of UnrollLoop().
Outside test scenarios, it is always performed with an unroll
count of 1. This means that un

[LoopUnroll] Separate peeling from unrolling

Loop peeling is currently performed as part of UnrollLoop().
Outside test scenarios, it is always performed with an unroll
count of 1. This means that unrolling doesn't actually do anything
apart from performing post-unroll simplification.

When testing, it's currently possible to specify both an explicit
peel count and an explicit unroll count. This doesn't perform any
sensible operation and may result in miscompiles, see
https://bugs.llvm.org/show_bug.cgi?id=45939.

This patch moves peeling from UnrollLoop() into tryToUnrollLoop(),
so that peeling does not also perform a susequent unroll. We only
run the post-unroll simplifications. Specifying both an explicit
peel count and unroll count is forbidden.

In the future, we may want to support both (non-PGO) peeling a
loop and unrolling it, but this needs to be done by first performing
the peel and then recalculating unrolling heuristics on a now
possibly analyzable loop.

Differential Revision: https://reviews.llvm.org/D103362

show more ...

Kill a variable which is unused after cddcc4cf [nfc]

A couple style tweaks on top of 5c0d1b2f9 [nfc]

[LoopUnroll] Eliminate PreserveCondBr parameter and fix a bug in the process

This builds on D103584. The change eliminates the coupling between unroll heuristic and implementation w.r.t. knowing whe

[LoopUnroll] Eliminate PreserveCondBr parameter and fix a bug in the process

This builds on D103584. The change eliminates the coupling between unroll heuristic and implementation w.r.t. knowing when the passed in trip count is an exact trip count or a max trip count. In theory the new code is slightly less powerful (since it relies on exact computable trip counts), but in practice, it appears to cover all the same cases. It can also be extended if needed.

The test change shows what appears to be a bug in the existing code around the interaction of peeling and unrolling. The original loop only ran 8 iterations. The previous output had the loop peeled by 2, and then an exact unroll of 8. This meant the loop ran a total of 10 iterations which appears to have been a miscompile.

Differential Revision: https://reviews.llvm.org/D103620

show more ...

[LoopUnroll] Eliminate PreserveOnlyFirst parameter [nfc]

This is a first step towards simplifying the transform interface to be less error prone. The basic idea is that querying SCEV is cheap (since

[LoopUnroll] Eliminate PreserveOnlyFirst parameter [nfc]

This is a first step towards simplifying the transform interface to be less error prone. The basic idea is that querying SCEV is cheap (since it's cached) and we can just check for properties related to branch folding in the transform method instead of relying on the heuristic part to pass everything in correctly.

Differential Revision: https://reviews.llvm.org/D103584

show more ...

[LoopUnroll] Reorder code to max dom tree update more obvious [nfc]

This cleans up the unroll action into two phases. Phase 1 does the mechanical act of unrolling, and leaves all conditional branche

[LoopUnroll] Reorder code to max dom tree update more obvious [nfc]

This cleans up the unroll action into two phases. Phase 1 does the mechanical act of unrolling, and leaves all conditional branches in place. Phase 2 optimizes away some of the conditional branches and then simplifies the loop. The primary benefit of the reordering is that we can delete some special cases dom tree update logic.

Differential Revision: https://reviews.llvm.org/D103561

show more ...

[LoopUnroll] Make DomTree explicitly required (NFC)

Some of the code was already assuming that DT is non-null, so
make that requirement more explicit and remove unnecessary null
checks.

[LoopUnroll] Use changeToUnreachable() (NFC)

When fulling unrolling with a non-latch exit, the latch block is
folded to unreachable. Replace this folding with the existing
changeToUnreachable() help

[LoopUnroll] Use changeToUnreachable() (NFC)

When fulling unrolling with a non-latch exit, the latch block is
folded to unreachable. Replace this folding with the existing
changeToUnreachable() helper, rather than performing it manually.

This also moves the fold to happen after the manual DT update
for exit blocks. I believe this is correct in that the conversion
of an unconditional backedge into unreachable should not affect
the DT at all.

Differential Revision: https://reviews.llvm.org/D103340

show more ...

[LoopUnroll] Clean up exit folding (NFC)

This does some non-functional cleanup of exit folding during
unrolling. The two main changes are:

* First rewrite latch->header edges, which is unrelated t

[LoopUnroll] Clean up exit folding (NFC)

This does some non-functional cleanup of exit folding during
unrolling. The two main changes are:

* First rewrite latch->header edges, which is unrelated to exit
folding.
* Combine folding for latch and non-latch exits. After the
previous change, the only difference in their logic is that
for non-latch exits we currently only fold "known non-exit"
cases, but not "known exit" cases.

I think this helps a lot to clarify this code and prepare it for
future changes.

Differential Revision: https://reviews.llvm.org/D103333

show more ...

Do actual DCE in LoopUnroll (try 4)

Turns out simplifyLoopIVs sometimes returns a non-dead instruction in it's DeadInsts out param. I had done a bit of NFC cleanup which was only NFC if simplifyLoo

Do actual DCE in LoopUnroll (try 4)

Turns out simplifyLoopIVs sometimes returns a non-dead instruction in it's DeadInsts out param. I had done a bit of NFC cleanup which was only NFC if simplifyLoopIVs obeyed it's documentation. I'm simplfy dropping that part of the change.

Commit message from try 3:

Recommitting after fixing a bug found post commit. Amusingly, try 1 had been correct, and by reverting to incorporate last minute review feedback, I introduce the bug. Oops. :)

Original commit message:

The problem was that recursively deleting an instruction can delete instructions beyond the current iterator (via a dead phi), thus invalidating iteration. Test case added in LoopUnroll/dce.ll to cover this case.

LoopUnroll does a limited DCE pass after unrolling, but if you have a chain of dead instructions, it only deletes the last one. Improve the code to recursively delete all trivially dead instructions.

Differential Revision: https://reviews.llvm.org/D102511

show more ...

Revert "Do actual DCE in LoopUnroll (try 3)"

This reverts commit b6320eeb8622f05e4a5d4c7f5420523357490fca
as it causes clang to assert; see
https://reviews.llvm.org/rGb6320eeb8622f05e4a5d4c7f5420523

Revert "Do actual DCE in LoopUnroll (try 3)"

This reverts commit b6320eeb8622f05e4a5d4c7f5420523357490fca
as it causes clang to assert; see
https://reviews.llvm.org/rGb6320eeb8622f05e4a5d4c7f5420523357490fca.

show more ...

[SampleFDO] New hierarchical discriminator for Flow Sensitive SampleFDO

This patch implements first part of Flow Sensitive SampleFDO (FSAFDO).
It has the following changes:
(1) disable current discr

[SampleFDO] New hierarchical discriminator for Flow Sensitive SampleFDO

This patch implements first part of Flow Sensitive SampleFDO (FSAFDO).
It has the following changes:
(1) disable current discriminator encoding scheme,
(2) new hierarchical discriminator for FSAFDO.

For this patch, option "-enable-fs-discriminator=true" turns on the new
functionality. Option "-enable-fs-discriminator=false" (the default)
keeps the current SampleFDO behavior. When the fs-discriminator is
enabled, we insert a flag variable, namely, llvm_fs_discriminator, to
the object. This symbol will checked by create_llvm_prof tool, and used
to generate a profile with FS-AFDO discriminators enabled. If this
happens, for an extbinary format profile, create_llvm_prof tool
will add a flag to profile summary section.

Differential Revision: https://reviews.llvm.org/D102246

show more ...

Do actual DCE in LoopUnroll (try 3)

Recommitting after fixing a bug found post commit. Amusingly, try 1 had been correct, and by reverting to incorporate last minute review feedback, I introduce th

Do actual DCE in LoopUnroll (try 3)

Recommitting after fixing a bug found post commit. Amusingly, try 1 had been correct, and by reverting to incorporate last minute review feedback, I introduce the bug. Oops. :)

The problem was that recursively deleting an instruction can delete instructions beyond the current iterator (via a dead phi), thus invalidating iteration. Test case added in LoopUnroll/dce.ll to cover this case.

LoopUnroll does a limited DCE pass after unrolling, but if you have a chain of dead instructions, it only deletes the last one. Improve the code to recursively delete all trivially dead instructions.

Differential Revision: https://reviews.llvm.org/D102511

show more ...