[Transforms] Remove unused includes (NFC) (#115263)

Identified with misc-include-cleaner.

[LLVM] Add `Intrinsic::getDeclarationIfExists` (#112428)

Add `Intrinsic::getDeclarationIfExists` to lookup an existing
declaration of an intrinsic in a `Module`.

[SCEV] Use const SCEV * explicitly in more places.

Use const SCEV * explicitly in more places to prepare for
https://github.com/llvm/llvm-project/pull/91961. Split off as suggested.

Revert "[IR][NFC] Update IRBuilder to use InsertPosition (#96497)"

Reverts the above commit, as it updates a common header function and
did not update all callsites:

https://lab.llvm.org/buildbot

Revert "[IR][NFC] Update IRBuilder to use InsertPosition (#96497)"

Reverts the above commit, as it updates a common header function and
did not update all callsites:

https://lab.llvm.org/buildbot/#/builders/29/builds/382

This reverts commit 6481dc57612671ebe77fe9c34214fba94e1b3b27.

show more ...

[IR][NFC] Update IRBuilder to use InsertPosition (#96497)

Uses the new InsertPosition class (added in #94226) to simplify some of
the IRBuilder interface, and removes the need to pass a BasicBlock

[IR][NFC] Update IRBuilder to use InsertPosition (#96497)

Uses the new InsertPosition class (added in #94226) to simplify some of
the IRBuilder interface, and removes the need to pass a BasicBlock
alongside a BasicBlock::iterator, using the fact that we can now get the
parent basic block from the iterator even if it points to the sentinel.
This patch removes the BasicBlock argument from each constructor or call
to setInsertPoint.

This has no functional effect, but later on as we look to remove the
`Instruction *InsertBefore` argument from instruction-creation
(discussed
[here](https://discourse.llvm.org/t/psa-instruction-constructors-changing-to-iterator-only-insertion/77845)),
this will simplify the process by allowing us to deprecate the
InsertPosition constructor directly and catch all the cases where we use
instructions rather than iterators.

show more ...

[NewPM] Remove LoopPredicationLegacyPass (#72944)

This pass isn't used/tested upstream anywhere, so remove it.

[LoopPredication] Fix division by zero in case of zero branch weights (#66506)

Treat the case where all branch weights are zero as if there was no
profile.
Fixes #66382

[llvm] Fix duplicate word typos. NFC

Those fixes were taken from https://reviews.llvm.org/D137338

[NFC][GuardUtils] Add util to extract widenable conditions

This is the next preparation patch to support widenable conditions
widening instead of branches widening.

We've added parseWidenableGuard

[NFC][GuardUtils] Add util to extract widenable conditions

This is the next preparation patch to support widenable conditions
widening instead of branches widening.

We've added parseWidenableGuard util which parses guard condition and
collects all checks existing in the expression tree: D157276

Here we are adding util which walks similar way through the expression
tree but looks up for widenable condition without collecting the checks.
Therefore llvm::extractWidenableCondition could parse widenable branches
with arbitrary position of widenable condition in the expression tree.

llvm::parseWidenableBranch which is we are going to get rid of is being
replaced by llvm::extractWidenableCondition where it's possible.

Reviewed By: anna

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

show more ...

[LoopPredication] Rework assumes of widened conditions

Currently after widening br(WC && (c1 && c2)) we insert assume of
(c1 && c2) which is joined to WC by And operation.
But we are going to suppor

[LoopPredication] Rework assumes of widened conditions

Currently after widening br(WC && (c1 && c2)) we insert assume of
(c1 && c2) which is joined to WC by And operation.
But we are going to support more flexible form of widenable branches
where WC could be placed arbitrary in the expression tree, e.g:
br(c1 && (c2 && WC)).
In that case we won't have (c1 && c2) in the IR. So we need to add
explicit (c1 && c2) and then create an assumption of it.

Reviewed By: anna

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

show more ...

Revert "[NFC][LoopPredication] Add parsed checks logging"

This reverts commit aa603c41caab63e246f4a4258c8b96e6ea06fdc9.

Revert due to LLVM Buildbot failure

[NFC][LoopPredication] Add parsed checks logging

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

[NFC][LoopPredication] Extract guard parsing to GuardUtils

Extract logic of parsing guards and widenable branches in order to reuse
it in the GuardWidening

Reviewed By: anna

Differential Revision:

[NFC][LoopPredication] Extract guard parsing to GuardUtils

Extract logic of parsing guards and widenable branches in order to reuse
it in the GuardWidening

Reviewed By: anna

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

show more ...

Revert "[GuardUtils] Add asserts about loop varying widenable conditions"

This reverts commit 5675757f5fc6e27ce01b3b12bdfd04044df53aa3.

Assert maybe too strict. revert and investigate why assert fi

Revert "[GuardUtils] Add asserts about loop varying widenable conditions"

This reverts commit 5675757f5fc6e27ce01b3b12bdfd04044df53aa3.

Assert maybe too strict. revert and investigate why assert fires.

show more ...

[GuardUtils] Add asserts about loop varying widenable conditions

We have now seen two miscompiles because of widening widenable
conditions at incorrect IR points and thereby changing a branch's loop

[GuardUtils] Add asserts about loop varying widenable conditions

We have now seen two miscompiles because of widening widenable
conditions at incorrect IR points and thereby changing a branch's loop
invariant condition to a loop-varying one (see PR60234 and PR61963).

This patch adds asserts in common guard utilities that we use for
widening to proactively catch these bugs in future.
Note that these asserts will not fire if we were to sink a widenable
condition from out of a loop into a loop (that's also incorrect for the
same reason as above).

Tested this without the fix for PR60234 (guard widening miscompile) and
confirmed the assert fires.

WARNING: Sometimes, the assert can fire if we failed to hoist the
invariant condition out of the loop. This is a pass-ordering issue or a
limitation in LICM, which would need an investigation. See details in
review.

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

show more ...

[LoopPredication] Fix where we generate widened condition. PR61963

Loop predication's predicateLoopExit pass does two incorrect things:

It sinks the widenable call into the loop, thereby converting

[LoopPredication] Fix where we generate widened condition. PR61963

Loop predication's predicateLoopExit pass does two incorrect things:

It sinks the widenable call into the loop, thereby converting an invariant condition to a variant one
It widens the widenable call at a branch thereby converting the branch into a loop-varying one.

The latter is problematic when the branch may have been loop-invariant
and prior optimizations (such as indvars) may have relied on this
fact, and updated the deopt state accordingly.

Now, when we widen this with a loop-varying condition, the deopt state
is no longer correct.
https://github.com/llvm/llvm-project/issues/61963 fixed.

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

show more ...

[LoopPredication] Fix the LoopPredication by feezing the result of predication.

LoopPredication introduces the use of possibly posion value in branch (guard)
instruction, so to avoid introducing und

[LoopPredication] Fix the LoopPredication by feezing the result of predication.

LoopPredication introduces the use of possibly posion value in branch (guard)
instruction, so to avoid introducing undefined behavior it should be frozen.

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

show more ...

[LoopPredication] Account for critical edges when inserting assumes. PR26496

Loop predication can insert assumes to preserve knowledge about some facts that
may otherwise be lost, because loop predi

[LoopPredication] Account for critical edges when inserting assumes. PR26496

Loop predication can insert assumes to preserve knowledge about some facts that
may otherwise be lost, because loop predication is a lossy transform. When a guard
is represented as branch by widenable condition, it should insert it in the guarded
block. However, if the guarded block has other predecessors than the guard block,
then the condition might not dominate it. Currently we generate invalid code here.

One possible fix here is to split critical edge and insert the assume there, but in
this case we should modify CFG, which Loop Predication is not currently doing, and we
want to keep it that way.

The fix is to handle this case by inserting a Phi which takes `Cond` as input from the
guard block and `true` from any other blocks. This is valid in terms of IR and does
not introduce any new knowledge if we came from another block.

Differential Revision: https://reviews.llvm.org/D144859
Reviewed By: nikic, skatkov

show more ...

[llvm][ir] Purge MD_prof custom accessors

This commit purges direct accesses to MD_prof metadata and replaces them
with the accessors provided from the utility file wherever possible.
This commit ca

[llvm][ir] Purge MD_prof custom accessors

This commit purges direct accesses to MD_prof metadata and replaces them
with the accessors provided from the utility file wherever possible.
This commit can be seen as the first step towards switching the branch weights to 64 bits.
See post here: https://discourse.llvm.org/t/extend-md-prof-branch-weights-metadata-from-32-to-64-bits/67492

Reviewed By: davidxl, paulkirth

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

show more ...

[NFC] Use TypeSize::geFixedValue() instead of TypeSize::getFixedSize()

This change is one of a series to implement the discussion from
https://reviews.llvm.org/D141134.

[Transforms/Scalar] llvm::Optional => std::optional

[llvm] Use std::nullopt instead of None in comments (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalu

[llvm] Use std::nullopt instead of None in comments (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[Transforms] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount

[Transforms] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount of manual work required in migrating from Optional to
std::optional.

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[Scalar] Use std::optional in LoopPredication.cpp (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-

[Scalar] Use std::optional in LoopPredication.cpp (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[LoopPredication][NFCI] Perform 'visited' check before pushing to worklist

This prevents duplicates to be pushed into the stack and hypothetically
should reduce memory footprint on ugly cornercases

[LoopPredication][NFCI] Perform 'visited' check before pushing to worklist

This prevents duplicates to be pushed into the stack and hypothetically
should reduce memory footprint on ugly cornercases with multiple repeating
duplicates in 'and' tree.

show more ...