[NFC] Switch a few uses of undef to poison as placeholders for unreachble code

[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 ...

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cl

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120817

show more ...

[LoopDeletion] Add back statistic update lost in 523573e

Caught by a couple of builders as an unused variable warning (e.g. https://lab.llvm.org/buildbot#builders/57/builds/13973).

[LoopDeletion] Revert 3af8a11 and add test coverage for breakage

This reverts 3af8a11 because I'd used an upper bound where an lower bound was required. The included reduced test case demonstrates

[LoopDeletion] Revert 3af8a11 and add test coverage for breakage

This reverts 3af8a11 because I'd used an upper bound where an lower bound was required. The included reduced test case demonstrates the issue.

show more ...

[NFC][LoopDeletion] Count the number of broken backedges

Those don't contribute to the number of deleted loops.

[LoopDeletion] Support selects when symbolically evaluating 1st iteration

Adds support for selects for which we know value on the 1st iteration.

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

[LoopDeletion] Support selects when symbolically evaluating 1st iteration

Adds support for selects for which we know value on the 1st iteration.

Differential Revision: https://reviews.llvm.org/D104111
Reviewed By: nikic

show more ...

[LoopDeletion] Move ICmpInst handling to getValueOnFirstIteration()

As noticed in https://reviews.llvm.org/D105688, it would be great to move
handling of ICmpInst which was in canProveExitOnFirstIte

[LoopDeletion] Move ICmpInst handling to getValueOnFirstIteration()

As noticed in https://reviews.llvm.org/D105688, it would be great to move
handling of ICmpInst which was in canProveExitOnFirstIteration() to
getValueOnFirstIteration().

Patch by Dmitry Makogon!

Differential Revision: https://reviews.llvm.org/D108978
Reviewed By: reames

show more ...

[LoopDeletion] Separate logic in breakBackedgeIfNotTaken using symboic max trip count [nfc]

As mentioned in D108833, the logic for figuring out if a backedge is dead was somewhat interwoven with the

[LoopDeletion] Separate logic in breakBackedgeIfNotTaken using symboic max trip count [nfc]

As mentioned in D108833, the logic for figuring out if a backedge is dead was somewhat interwoven with the SCEV based logic and the symbolic eval logic. This is my attempt at making the code easier to follow.

Note that this is only NFC after the work done in 29fa37ec. Thanks to Nikita for catching that case.

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

show more ...

[LoopDeletion] Use max trip count to break backedge in addition to exact one

We'd added support a while back from breaking the backedge if SCEV can prove the trip count is zero. However, we used the

[LoopDeletion] Use max trip count to break backedge in addition to exact one

We'd added support a while back from breaking the backedge if SCEV can prove the trip count is zero. However, we used the exact trip count which requires *all* exits be analyzeable. I noticed while writing test cases for another patch that this disallows cases where one exit is provably taken paired with another which is unknown. This patch adds the upper bound case.

We could use a symbolic max trip count here instead, but we use an isKnownNonZero filter (presumably for compile time?) for the first-iteration reasoning. I decided this was a more obvious incremental step, and we could go back and untangle the schemes separately.

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

show more ...

[LoopDeletion] Handle switch in proving that loop exits on first iteration

Added check for switch-terminated blocks in loops.
Now if a block is terminated with a switch, we try to find out which of

[LoopDeletion] Handle switch in proving that loop exits on first iteration

Added check for switch-terminated blocks in loops.
Now if a block is terminated with a switch, we try to find out which of the
cases is taken on 1st iteration and mark corresponding edge from the block
to the case successor as live.

Patch by Dmitry Makogon!

Differential Revision: https://reviews.llvm.org/D105688
Reviewed By: nikic, mkazantsev

show more ...

[NFC] Remove duplicate function calls

Removed repeated call of L->getHeader(). Now using previously stored return value.

Patch by Dmitry Makogon!

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

[NFC] Remove duplicate function calls

Removed repeated call of L->getHeader(). Now using previously stored return value.

Patch by Dmitry Makogon!

Differential Revision: https://reviews.llvm.org/D105535
Reviewed By: mkazantsev

show more ...

[LoopDeletion] Benefit from branches by undef conditions when symbolically executing 1st iteration

We can exploit branches by `undef` condition. Frankly, the LangRef says that
such branches are UB,

[LoopDeletion] Benefit from branches by undef conditions when symbolically executing 1st iteration

We can exploit branches by `undef` condition. Frankly, the LangRef says that
such branches are UB, so we can assume that all outgoing edges of such blocks
are dead.

However, from practical perspective, we know that this is not supported correctly
in some other places. So we are being conservative about it.

Branch by undef is treated in the following way:
- If it is a loop-exiting branch, we always assume it exits the loop;
- If not, we arbitrarily assume it takes `true` value.

Differential Revision: https://reviews.llvm.org/D104689
Reviewed By: nikic

show more ...

[LoopDeletion] Exploit undef Phi inputs when symbolically executing 1st iteration

Follow-up on Roman's idea expressed in D103959.
- If a Phi has undefined inputs from live blocks:
- and no other

[LoopDeletion] Exploit undef Phi inputs when symbolically executing 1st iteration

Follow-up on Roman's idea expressed in D103959.
- If a Phi has undefined inputs from live blocks:
- and no other inputs, assume it is undef itself;
- and exactly one non-undef input, we can assume that all undefs are equal to this input.

Differential Revision: https://reviews.llvm.org/D104618
Reviewed By: lebedev.ri, nikic

show more ...

Re-land "[LoopDeletion] Handle Phis with similar inputs from different blocks"

Patch was reverted due to a bug that existed before it and was exposed
by it. Returning after the underlying bug has be

Re-land "[LoopDeletion] Handle Phis with similar inputs from different blocks"

Patch was reverted due to a bug that existed before it and was exposed
by it. Returning after the underlying bug has been fixed.

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

show more ...

[LoopDeletion] Require loop to have a predecessor when executing 1st iteration symbolically

Two predecessors break the further logic, and the loop may come to the
opt in non-canonicalized state.

Revert "[LoopDeletion] Handle Phis with similar inputs from different blocks"

This reverts commit bb1dc876ebb8a2eef38d5183d00c2db1437f1c91.

This patch causes an assertion failure when building an a

Revert "[LoopDeletion] Handle Phis with similar inputs from different blocks"

This reverts commit bb1dc876ebb8a2eef38d5183d00c2db1437f1c91.

This patch causes an assertion failure when building an arm64 defconfig
Linux kernel.

See https://reviews.llvm.org/D103959 for a link to the original bug
report and a reduced reproducer.

show more ...

[LoopDeletion] Handle Phis with similar inputs from different blocks

This patch lifts the requirement to have the only incoming live block
for Phis. There can be multiple live blocks if the same val

[LoopDeletion] Handle Phis with similar inputs from different blocks

This patch lifts the requirement to have the only incoming live block
for Phis. There can be multiple live blocks if the same value comes to
phi from all of them.

Differential Revision: https://reviews.llvm.org/D103959
Reviewed By: nikic, lebedev.ri

show more ...

[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3)

This patch handles one particular case of one-iteration loops for which SCEV
cannot straightforwardly p

[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3)

This patch handles one particular case of one-iteration loops for which SCEV
cannot straightforwardly prove BECount = 1. The idea of the optimization is to
symbolically execute conditional branches on the 1st iteration, moving in topoligical
order, and only visiting blocks that may be reached on the first iteration. If we find out
that we never reach header via the latch, then the backedge can be broken.

This implementation uses InstSimplify. SCEV version was rejected due to high
compile time impact.

Differential Revision: https://reviews.llvm.org/D102615
Reviewed By: nikic

show more ...

[LoopDeletion] Check for irreducible cycles when deleting loops.

Loops with irreducible cycles may loop infinitely. Those cannot be
removed, unless the loop/function is marked as mustprogress.

Also

[LoopDeletion] Check for irreducible cycles when deleting loops.

Loops with irreducible cycles may loop infinitely. Those cannot be
removed, unless the loop/function is marked as mustprogress.

Also discussed in D103382.

Reviewed By: nikic

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

show more ...

[LoopDeletion] Consider infinite loops alive, unless mustprogress.

The current loop or any of its sub-loops may be infinite. Unless the
function or the loops are marked as mustprogress, this in itse

[LoopDeletion] Consider infinite loops alive, unless mustprogress.

The current loop or any of its sub-loops may be infinite. Unless the
function or the loops are marked as mustprogress, this in itself makes
the loop *not* dead.

This patch moves the logic to check whether the current loop is finite
or mustprogress to `isLoopDead` and also extends it to check the
sub-loops. This should fix PR50511.

Reviewed By: nikic

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

show more ...

Revert "Return "[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration" (try 2)"

This reverts commit be1a23203b1de655b8c7dac7549818d975a0cbbf.

Revert "[NFCI][LoopDeletion] Only query SCEV about loop successor if another successor is also in loop"

This reverts commit b0b2bf3b5da950679db1431aae431a6dedea2245.

Revert "[NFC] Formatting fix"

This reverts commit 59d938e649e62db0cef4903d495e838fbc6a6eb8.

Revert "[NFC] Reuse existing variables instead of re-requesting successors"

This reverts commit c467585682dcdda75e645ef3ab47c8b48440db12.