[BasicBlockUtils] Fix typo in API name (NFC)

detatch -> detach. As this requires touching all uses, also
lower-case it in accordance with the style guide.

Use a deterministic order when updating the DominatorTree

This solves a problem with non-deterministic output from opt due
to not performing dominator tree updates in a deterministic order.

The pro

Use a deterministic order when updating the DominatorTree

This solves a problem with non-deterministic output from opt due
to not performing dominator tree updates in a deterministic order.

The problem that was analysed indicated that JumpThreading was using
the DomTreeUpdater via llvm::MergeBasicBlockIntoOnlyPred. When
preparing the list of updates to send to DomTreeUpdater::applyUpdates
we iterated over a SmallPtrSet, which didn't give a well-defined
order of updates to perform.

The added domtree-updates.ll test case is an example that would
result in non-deterministic printouts of the domtree. Semantically
those domtree:s are equivalent, but it show the fact that when we
use the domtree iterator the order in which nodes are visited depend
on the order in which dominator tree updates are performed.

Since some passes (at least EarlyCSE) are iterating over nodes in the
dominator tree in a similar fashion as the domtree printer, then the
order in which transforms are applied by such passes, transitively,
also depend on the order in which dominator tree updates are
performed. And taking EarlyCSE as an example the end result could be
different depending on in which order the transforms are applied.

Reviewed By: nikic, kuhar

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

show more ...

[LoopPeel] Peel loops with exits followed by an unreachable or deopt block

Added support for peeling loops with exits that are followed either by an
unreachable-terminated block or block that has a

[LoopPeel] Peel loops with exits followed by an unreachable or deopt block

Added support for peeling loops with exits that are followed either by an
unreachable-terminated block or block that has a terminatnig deoptimize call.
All blocks in the sequence must have an unique successor, maybe except
for the last one.

Reviewed By: mkazantsev

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

show more ...

Revert "Recommit "[LoopPeel] Peel loops with deoptimizing exits""

This reverts commit d68b59f3ebb253ee7119a25a71c51cf19b73e030.

This is causing crashes, see D110922 for details.

Recommit "[LoopPeel] Peel loops with deoptimizing exits"

Removed obsolete DT verification that should not be there because the
strategy of DT updates has changed.

Differential Revision: https://rev

Recommit "[LoopPeel] Peel loops with deoptimizing exits"

Removed obsolete DT verification that should not be there because the
strategy of DT updates has changed.

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

show more ...

Revert "[LoopPeel] Peel loops with deoptimizing exits"

This reverts commit 8a959625c433f311233682afa7bfe1c76367700d.

Reported failures with LLVM_ENABLE_EXPENSIVE_CHECKS, need to investigate.

[LoopPeel] Peel loops with deoptimizing exits

Added support for peeling loops with "deoptimizing" exits -
such exits that it or any of its children (or any of their
children, etc) either has a @llvm

[LoopPeel] Peel loops with deoptimizing exits

Added support for peeling loops with "deoptimizing" exits -
such exits that it or any of its children (or any of their
children, etc) either has a @llvm.experimental.deoptimize call
prior to the terminating return instruction of this basic block
or is terminated with unreachable. All blocks in the the
sequence must have a single successor, maybe except for the last
one.

Previously we only checked the exit block for being deoptimizing.
Now we check if the last reachable block from the exit is deoptimizing.

Patch by Dmitry Makogon!

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

show more ...

[BasicBlockUtils] Fixup of an assumed typo in MergeBlockIntoPredecessor

The NFC commit e5692a564a73ef63b7b changed the logic for
DomTreeUpdates to use the range [succ_begin, succ_begin) when
looking

[BasicBlockUtils] Fixup of an assumed typo in MergeBlockIntoPredecessor

The NFC commit e5692a564a73ef63b7b changed the logic for
DomTreeUpdates to use the range [succ_begin, succ_begin) when
looking for SuccsOfPredBB rather than using [succ_begin, succ_end).

As the commit was NFC this is identified as a typo (it has been
discussed briefly in phabricator).

The typo was found when inspecting the code, so I've got no idea if
changing back to the old range has any significant impact (such as
solving any PR:s or causing some new problems). But at least this
restores the code to the originally indented behavior.

show more ...

[NFC][BasicBlockUtils] Refactor GetIfCondition() to return the branch, not it's condition

Otherwise e.g. the FoldTwoEntryPHINode() has to do a lot of legwork
to re-deduce what is the dominant block

[NFC][BasicBlockUtils] Refactor GetIfCondition() to return the branch, not it's condition

Otherwise e.g. the FoldTwoEntryPHINode() has to do a lot of legwork
to re-deduce what is the dominant block (i.e. for which block
is this branch the terminator).

show more ...

[SimpleLoopUnswitch] Don't non-trivially unswitch loops with catchswitch exits

SplitBlock() can't handle catchswitch.

Fixes PR50973.

Reviewed By: aheejin

Differential Revision: https://reviews.ll

[SimpleLoopUnswitch] Don't non-trivially unswitch loops with catchswitch exits

SplitBlock() can't handle catchswitch.

Fixes PR50973.

Reviewed By: aheejin

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

show more ...

[CSSPGO] Undoing the concept of dangling pseudo probe

As a follow-up to https://reviews.llvm.org/D104129, I'm cleaning up the danling probe related code in both the compiler and llvm-profgen.

I'm s

[CSSPGO] Undoing the concept of dangling pseudo probe

As a follow-up to https://reviews.llvm.org/D104129, I'm cleaning up the danling probe related code in both the compiler and llvm-profgen.

I'm seeing a 5% size win for the pseudo_probe section for SPEC2017 and 10% for Ciner. Certain benchmark such as 602.gcc has a 20% size win. No obvious difference seen on build time for SPEC2017 and Cinder.

Reviewed By: wenlei

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

show more ...

[NFCI][Local] MergeBlockIntoPredecessor(): use DeleteDeadBlocks()

[IR] Add BasicBlock::isEntryBlock() (NFC)

This is a recurring and somewhat awkward pattern. Add a helper
method for it.

[NFCI][BasicBlockUtils] MergeBlockIntoPredecessor(): improve Dominator Tree updating

Same as with TryToSimplifyUncondBranchFromEmptyBlock() patch.

[SplitEdge] Update SplitCriticalEdge to return a nullptr only when the edge is not critical

Summary:
The function SplitCriticalEdge (called by SplitEdge) can return a nullptr in
cases where the edge

[SplitEdge] Update SplitCriticalEdge to return a nullptr only when the edge is not critical

Summary:
The function SplitCriticalEdge (called by SplitEdge) can return a nullptr in
cases where the edge is a critical. SplitEdge uses SplitCriticalEdge assuming it
can always split all critical edges, which is an incorrect assumption.

The three cases where the function SplitCriticalEdge will return a nullptr is:
1. DestBB is an exception block
2. Options.IgnoreUnreachableDests is set to true and
isa(DestBB->getFirstNonPHIOrDbgOrLifetime()) is not equal to a nullptr
3. LoopSimplify form must be preserved (Options.PreserveLoopSimplify is true)
and it cannot be maintained for a loop due to indirect branches

For each of these situations they are handled in the following way:
1. Modified the function ehAwareSplitEdge originally from
llvm/lib/Transforms/Coroutines/CoroFrame.cpp to handle the cases when the DestBB
is an exception block. This function is called directly in SplitEdge.
SplitEdge does not call SplitCriticalEdge in this case
2. Options.IgnoreUnreachableDests is set to false by default, so this situation
does not apply.
3. Return a nullptr in this situation since the SplitCriticalEdge also returned
nullptr. Nothing we can do in this case.

Reviewed By: asbirlea

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

show more ...

[NFCI][SimplifyCFG] Don't pay for a Small{Map,Set}Vector when plain SmallSet will suffice

This *only* changes the cases where we *really* don't care
about the iteration order of the underlying conta

[NFCI][SimplifyCFG] Don't pay for a Small{Map,Set}Vector when plain SmallSet will suffice

This *only* changes the cases where we *really* don't care
about the iteration order of the underlying contained,
namely when we will use the values from it to form DTU updates.

show more ...

Reapply "[DebugInfo] Handle multiple variable location operands in IR"

Fixed section of code that iterated through a SmallDenseMap and added
instructions in each iteration, causing non-deterministic

Reapply "[DebugInfo] Handle multiple variable location operands in IR"

Fixed section of code that iterated through a SmallDenseMap and added
instructions in each iteration, causing non-deterministic code; replaced
SmallDenseMap with MapVector to prevent non-determinism.

This reverts commit 01ac6d1587e8613ba4278786e8341f8b492ac941.

show more ...

Revert "[DebugInfo] Handle multiple variable location operands in IR"

This caused non-deterministic compiler output; see comment on the
code review.

> This patch updates the various IR passes to co

Revert "[DebugInfo] Handle multiple variable location operands in IR"

This caused non-deterministic compiler output; see comment on the
code review.

> This patch updates the various IR passes to correctly handle dbg.values with a
> DIArgList location. This patch does not actually allow DIArgLists to be produced
> by salvageDebugInfo, and it does not affect any pass after codegen-prepare.
> Other than that, it should cover every IR pass.
>
> Most of the changes simply extend code that operated on a single debug value to
> operate on the list of debug values in the style of any_of, all_of, for_each,
> etc. Instances of setOperand(0, ...) have been replaced with with
> replaceVariableLocationOp, which takes the value that is being replaced as an
> additional argument. In places where this value isn't readily available, we have
> to track the old value through to the point where it gets replaced.
>
> Differential Revision: https://reviews.llvm.org/D88232

This reverts commit df69c69427dea7f5b3b3a4d4564bc77b0926ec88.

show more ...

[DebugInfo] Handle multiple variable location operands in IR

This patch updates the various IR passes to correctly handle dbg.values with a
DIArgList location. This patch does not actually allow DIA

[DebugInfo] Handle multiple variable location operands in IR

This patch updates the various IR passes to correctly handle dbg.values with a
DIArgList location. This patch does not actually allow DIArgLists to be produced
by salvageDebugInfo, and it does not affect any pass after codegen-prepare.
Other than that, it should cover every IR pass.

Most of the changes simply extend code that operated on a single debug value to
operate on the list of debug values in the style of any_of, all_of, for_each,
etc. Instances of setOperand(0, ...) have been replaced with with
replaceVariableLocationOp, which takes the value that is being replaced as an
additional argument. In places where this value isn't readily available, we have
to track the old value through to the point where it gets replaced.

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

show more ...

[CSSPGO] Deduplicating dangling pseudo probes.

Same dangling probes are redundant since they all have the same semantic that is to rely on the counts inference tool to get reasonable count for the s

[CSSPGO] Deduplicating dangling pseudo probes.

Same dangling probes are redundant since they all have the same semantic that is to rely on the counts inference tool to get reasonable count for the same original block. Therefore, there's no need to keep multiple copies of them. I've seen jump threading created tons of redundant dangling probes that slowed down the compiler dramatically. Other optimization passes can also result in redundant probes though without an observed impact so far.

This change removes block-wise redundant dangling probes specifically introduced by jump threading. To support removing redundant dangling probes caused by all other passes, a final function-wise deduplication is also added.

An 18% size win of the .pseudo_probe section was seen for SPEC2017. No performance difference was observed.

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

show more ...

[Transforms/Utils] Use range-based for loops (NFC)

[llvm] Use llvm::is_contained (NFC)

[Transforms/Utils] Use range-based for loops (NFC)

[SimplifyCFG][BasicBlockUtils] Port SplitBlockPredecessors()/SplitLandingPadPredecessors() to DomTreeUpdater

This is not nice, but it's the best transient solution possible,
and is better than just

[SimplifyCFG][BasicBlockUtils] Port SplitBlockPredecessors()/SplitLandingPadPredecessors() to DomTreeUpdater

This is not nice, but it's the best transient solution possible,
and is better than just duplicating the whole function.

The problem is, this function is widely used,
and it is not at all obvious that all the users
could be painlessly switched to operate on DomTreeUpdater,
and somehow i don't feel like porting all those users first.

This function is one of last three that not operate on DomTreeUpdater.

show more ...

[SimplifyCFG] Port SplitBlockAndInsertIfThen() to DomTreeUpdater

This is not nice, but it's the best transient solution possible,
and is better than just duplicating the whole function.

The problem

[SimplifyCFG] Port SplitBlockAndInsertIfThen() to DomTreeUpdater

This is not nice, but it's the best transient solution possible,
and is better than just duplicating the whole function.

The problem is, this function is widely used,
and it is not at all obvious that all the users
could be painlessly switched to operate on DomTreeUpdater,
and somehow i don't feel like porting all those users first.

This function is one of last three that not operate on DomTreeUpdater.

show more ...