[JumpThreading] Consider freeze as a zero-cost instruction

This is a simple patch that makes freeze as a zero-cost instruction, as bitcast already is.

Reviewed By: efriedma

Differential Revision:

[JumpThreading] Consider freeze as a zero-cost instruction

This is a simple patch that makes freeze as a zero-cost instruction, as bitcast already is.

Reviewed By: efriedma

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

show more ...

[JumpThreading] Remove cast's constraint

As discussed in D84949, this removes the constraint to cast since it does not
cause compile time degradation.

Reviewed By: lebedev.ri

Differential Revision

[JumpThreading] Remove cast's constraint

As discussed in D84949, this removes the constraint to cast since it does not
cause compile time degradation.

Reviewed By: lebedev.ri

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

show more ...

[JumpThreading] Don't limit the type of an operand

Compared to the optimized code with branch conditions never frozen,
limiting the type of freeze's operand causes generation of suboptimal code in
s

[JumpThreading] Don't limit the type of an operand

Compared to the optimized code with branch conditions never frozen,
limiting the type of freeze's operand causes generation of suboptimal code in
some cases.
I would like to suggest removing the constraint, as this patch does.
If the number of freeze instructions becomes significant, this can be revisited.

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

show more ...

[JumpThreading] Let SimplifyPartiallyRedundantLoad look into freeze

This patch allows SimplifyPartiallyRedundantLoad work when
the branch condition was frozen.

Reviewed By: efriedma

Differential R

[JumpThreading] Let SimplifyPartiallyRedundantLoad look into freeze

This patch allows SimplifyPartiallyRedundantLoad work when
the branch condition was frozen.

Reviewed By: efriedma

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

show more ...

[JumpThreading] Fold br(freeze(undef))

This patch makes JumpThreading fold br(freeze(undef)) if the freeze instruction
is only used by the branch.

Reviewed By: efriedma

Differential Revision: http

[JumpThreading] Fold br(freeze(undef))

This patch makes JumpThreading fold br(freeze(undef)) if the freeze instruction
is only used by the branch.

Reviewed By: efriedma

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

show more ...

[JumpThreading] Add a basic support for freeze instruction

This patch adds a basic support for freeze instruction to JumpThreading
by making ComputeValueKnownInPredecessorsImpl look into its operand

[JumpThreading] Add a basic support for freeze instruction

This patch adds a basic support for freeze instruction to JumpThreading
by making ComputeValueKnownInPredecessorsImpl look into its operand.

Reviewed By: efriedma, nikic

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

show more ...

[JumpThreading] ProcessBranchOnXOR(): bailout if any pred ends in indirect branch (PR46857)

SplitBlockPredecessors() can not split blocks that have such terminators,
and in two other places we alrea

[JumpThreading] ProcessBranchOnXOR(): bailout if any pred ends in indirect branch (PR46857)

SplitBlockPredecessors() can not split blocks that have such terminators,
and in two other places we already ensure that we don't end up calling
SplitBlockPredecessors() on such blocks. Do so in one more place.

Fixes https://bugs.llvm.org/show_bug.cgi?id=46857

show more ...

[JumpThreading] Handle zero !prof branch_weights

Avoid division by zero in updatePredecessorProfileMetadata().

Reviewers: yamauchi
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D81499

[JumpThreading] Simplify FindMostPopularDest (NFC)

Summary:
This patch simplifies FindMostPopularDest without changing the
functionality.

Given a list of jump threading destinations, the function f

[JumpThreading] Simplify FindMostPopularDest (NFC)

Summary:
This patch simplifies FindMostPopularDest without changing the
functionality.

Given a list of jump threading destinations, the function finds the
most popular destination. To ensure determinism when there are
multiple destinations with the highest popularity, the function picks
the first one in the successor list with the highest popularity.

Without this patch:

- The function populates DestPopularity -- a histogram mapping
destinations to their respective occurrence counts.

- Then we iterate over DestPopularity, looking for the highest
popularity while building a vector of destinations with the highest
popularity.

- Finally, we iterate the successor list, looking for the destination
with the highest popularity.

With this patch:

- We implement DestPopularity with MapVector instead of DenseMap. We
populate the map with popularity 0 for all successors in the order
they appear in the successor list.

- We build the histogram in the same way as before.

- We simply use std::max_element on DestPopularity to find the most
popular destination. The use of MapVector ensures determinism.

Reviewers: wmi, efriedma

Reviewed By: wmi

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[JumpThreading] Use emplace_back instead of push_back (NFC)

Summary: This patch replaces push_back with emplace_back where appropriate.

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differenti

[JumpThreading] Use emplace_back instead of push_back (NFC)

Summary: This patch replaces push_back with emplace_back where appropriate.

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[BrachProbablityInfo] Set edge probabilities at once and fix calcMetadataWeights()

Hide the method that allows setting probability for particular edge
and introduce a public method that sets probabi

[BrachProbablityInfo] Set edge probabilities at once and fix calcMetadataWeights()

Hide the method that allows setting probability for particular edge
and introduce a public method that sets probabilities for all
outgoing edges at once.
Setting individual edge probability is error prone. More over it is
difficult to check that the total probability is 1.0 because there is
no easy way to know when the user finished setting all
the probabilities.

Related bug is fixed in BranchProbabilityInfo::calcMetadataWeights().
Changing unreachable branch probabilities to raw(1) and distributing
the rest (oldProbability - raw(1)) over the reachable branches could
introduce total probability inaccuracy bigger than 1/numOfBranches.

Reviewers: yamauchi, ebrevnov
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D79396

show more ...

[LVI] Don't require DominatorTree in LVI (NFC)

After D76797 the dominator tree is no longer used in LVI, so we
can remove it as a pass dependency, and also get rid of the
dominator tree enabling/dis

[LVI] Don't require DominatorTree in LVI (NFC)

After D76797 the dominator tree is no longer used in LVI, so we
can remove it as a pass dependency, and also get rid of the
dominator tree enabling/disabling logic in JumpThreading.

Apart from cleaning up the code, this also clarifies LVI
cache consistency, in that the LVI cache can no longer
depend on whether the DT was or wasn't enabled due to
pending DT updates at any given time.

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

show more ...

Revert "[BrachProbablityInfo] Set edge probabilities at once. NFC."

This reverts commit eef95f2746c3347b8dad19091ffb82a88d73acd3.

The new assertion about branch propability sums does not hold.

[BrachProbablityInfo] Set edge probabilities at once. NFC.

Hide the method that allows setting probability for particular
edge and introduce a public method that sets probabilities for
all outgoing

[BrachProbablityInfo] Set edge probabilities at once. NFC.

Hide the method that allows setting probability for particular
edge and introduce a public method that sets probabilities for
all outgoing edges at once.
Setting individual edge probability is error prone. More over
it is difficult to check that the total probability is 1.0
because there is no easy way to know when the user finished
setting all the probabilities.

Reviewers: yamauchi, ebrevnov
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D79396

show more ...

[JumpThreading] NFC: Simplify ComputeValueKnownInPredecessorsImpl

Summary:
ComputeValueKnownInPredecessorsImpl is the main folding mechanism in
JumpThreading.cpp. To avoid potential infinite recurs

[JumpThreading] NFC: Simplify ComputeValueKnownInPredecessorsImpl

Summary:
ComputeValueKnownInPredecessorsImpl is the main folding mechanism in
JumpThreading.cpp. To avoid potential infinite recursion while
chasing use-def chains, it uses:

DenseSet<std::pair<Value *, BasicBlock *>> &RecursionSet

to keep track of Value-BB pairs that we've processed.

Now, when ComputeValueKnownInPredecessorsImpl recursively calls
itself, it always passes BB as is, so the second element is always BB.

This patch simplifes the function by dropping "BasicBlock *" from
RecursionSet.

Reviewers: wmi, efriedma

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[NFC] Modernize misc. uses of Align/MaybeAlign APIs.

Use the current getAlign() APIs where it makes sense, and use Align
instead of MaybeAlign when we know the value is non-zero.

Fix MSan false positive due to select folding.

Summary:
Select folding in JumpThreading can create a conditional branch on a
code patch that did not have one in the original program. This is not a
v

Fix MSan false positive due to select folding.

Summary:
Select folding in JumpThreading can create a conditional branch on a
code patch that did not have one in the original program. This is not a
valid transformation in sanitize_memory functions.

Note that JumpThreading does select folding in 3 different places. Two
of them seem safe - they apply to a select instruction in a BB that ends
with an unconditional branch to another BB, which (in turn) ends with a
conditional branch or a switch with the same condition.

Fixes PR45220.

Reviewers: glider, dvyukov, efriedma

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[JumpThreading] Fix infinite loop (PR44611)

Summary:
This patch fixes https://bugs.llvm.org/show_bug.cgi?id=44611 by
preventing an infinite loop in the jump threading pass when
-jump-threading-acros

[JumpThreading] Fix infinite loop (PR44611)

Summary:
This patch fixes https://bugs.llvm.org/show_bug.cgi?id=44611 by
preventing an infinite loop in the jump threading pass when
-jump-threading-across-loop-headers is on. Specifically, without this
patch, jump threading through two basic blocks would trigger on the
same area of the CFG over and over, resulting in an infinite loop.

Consider testcase PR44611-across-header-hang.ll in this patch. The
first opportunity to thread through two basic blocks is:

from bb_body2 through bb_header and bb_body1 to bb_body2.

The pass duplicates bb_header and bb_body1 as, say, bb_header.thread1
and bb_body1.thread1. Since bb_header contains a successor edge back
to itself, bb_header.thread1 also contains a successor edge to
bb_header, immediately giving rise to the next jump threading
opportunity:

from bb_header.thread1 through bb_header and bb_body1 to bb_body2.

After that, we repeatedly thread an incoming edge into bb_header
through bb_header and bb_body1 to bb_body2. In other words, we keep
peeling one iteration from bb_header's self loop.

The patch fixes the problem by preventing the pass from duplicating a
basic block containing a self loop.

Reviewers: wmi, junparser, efriedma

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[JumpThreading] Skip unconditional PredBB when threading jumps through two basic blocks

Fixes https://bugs.llvm.org/show_bug.cgi?id=44922 (caused by 4698bf145d583e26ed438026ef7fde031ef322b1)

Thread

[JumpThreading] Skip unconditional PredBB when threading jumps through two basic blocks

Fixes https://bugs.llvm.org/show_bug.cgi?id=44922 (caused by 4698bf145d583e26ed438026ef7fde031ef322b1)

ThreadThroughTwoBasicBlocks assumes PredBBBranch is conditional. The following code can segfault.

AddPHINodeEntriesForMappedBlock(PredBBBranch->getSuccessor(1), PredBB, NewBB,
ValueMapping);

We can also allow unconditional PredBB, but the produced code is not
better.

Reviewed By: kazu

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

show more ...

Reapply "[DebugInfo] Prevent explosion of debug intrinsics during jump threading"

This reverts commit 6ded69f294a9a62a68b0a07aa987c8165a4b31e7.

Revert "[DebugInfo] Prevent explosion of debug intrinsics during jump threading"

This reverts commit fe6f6cd6b8e647c5b4ac82f4fcd56c057c2ef8ce.

Found test failure on several buildbots.

[DebugInfo] Prevent explosion of debug intrinsics during jump threading

This patch is a fix following the revert of 72ce759
(https://reviews.llvm.org/rG72ce759928e6dfee6a9efa310b966c19722352ba)
and

[DebugInfo] Prevent explosion of debug intrinsics during jump threading

This patch is a fix following the revert of 72ce759
(https://reviews.llvm.org/rG72ce759928e6dfee6a9efa310b966c19722352ba)
and fixes the failure that it caused.

The above patch failed on the Thread Sanitizer buildbot with an out of
memory error. After an investigation, the cause was identified as an
explosion in debug intrinsics while running the Jump Threading pass on
ModuleMap.ll. The above patched prevented debug intrinsics from being
dropped when their Basic Block was deleted due to being "empty". In this
case, one of the functions in ModuleMap.ll had (after many optimization
passes) a very large number of debug intrinsics representing a set of
repeatedly inlined variables. Previously the vast majority of these were
silently dropped during Jump Threading when their blocks were deleted,
but as of the above patch they survived for longer, causing a large
increase in the number of debug intrinsics. These intrinsics were then
repeatedly cloned by the Jump Threading pass as edges were threaded,
multiplying the intrinsic count further. The memory consumed by this
process spiralled out of control, crashing the buildbot that uses TSan
(which has an estimated 5-10x memory overhead compared to non-sanitized
builds).

This patch adds RemoveRedundantDbgInstrs to the Jump Threading pass, in
order to reduce the number of debug intrinsics down to a manageable
amount in cases where many intrinsics for the same variable end up
bunched together contiguously, as in this case.

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

show more ...

Resubmit^2: [JumpThreading] Thread jumps through two basic blocks

This reverts commit 41784bed01543315a1d03141e6ddc023fd914c0b.

Since the original revision ead815924e6ebeaf02c31c37ebf7a560b5fdf67b,

Resubmit^2: [JumpThreading] Thread jumps through two basic blocks

This reverts commit 41784bed01543315a1d03141e6ddc023fd914c0b.

Since the original revision ead815924e6ebeaf02c31c37ebf7a560b5fdf67b,
this revision fixes three issues:

- This revision fixes the Windows build. My original patch improperly
copied EH pads on Windows. This patch disregards jump threading
opportunities having to do with EH pads.

- This revision fixes jump threading to a wrong destination.
Specifically, my original patch treated any Constant other than 0 as 1
while evaluating the branch condition. This bug led to treating
constant expressions like:

icmp ugt i8* null, inttoptr (i64 4 to i8*)

to "true". This patch fixes the bug by calling isOneValue.

- This revision fixes the cost calculation of two basic blocks being
threaded through. Note that getJumpThreadDuplicationCost returns
"(unsigned)~0" for those basic blocks that cannot be duplicated. If
we sum of two return values from getJumpThreadDuplicationCost, we
could have an unsigned overflow like:

(unsigned)~0 + 5 = 4

and mistakenly determine that it's safe and profitable to proceed
with the jump threading opportunity. The patch fixes the bug by
checking each return value before summing them up.

[JumpThreading] Thread jumps through two basic blocks

Summary:
This patch teaches JumpThreading.cpp to thread through two basic
blocks like:

bb3:
%var = phi i32* [ null, %bb1 ], [ @a, %bb2 ]
%tobool = icmp eq i32 %cond, 0
br i1 %tobool, label %bb4, label ...

bb4:
%cmp = icmp eq i32* %var, null
br i1 %cmp, label bb5, label bb6

by duplicating basic blocks like bb3 above. Once we duplicate bb3 as
bb3.dup and redirect edge bb2->bb3 to bb2->bb3.dup, we have:

bb3:
%var = phi i32* [ @a, %bb2 ]
%tobool = icmp eq i32 %cond, 0
br i1 %tobool, label %bb4, label ...

bb3.dup:
%var = phi i32* [ null, %bb1 ]
%tobool = icmp eq i32 %cond, 0
br i1 %tobool, label %bb4, label ...

bb4:
%cmp = icmp eq i32* %var, null
br i1 %cmp, label bb5, label bb6

Then the existing code in JumpThreading.cpp can thread edge
bb3.dup->bb4 through bb4 and eventually create bb3.dup->bb5.

Reviewers: wmi

Subscribers: hiraditya, jfb, llvm-commits

Tags: #llvm

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

show more ...

[JumpThreading] Half the duplicate threshold at Oz

Duplicating instructions can lead to code size increases but using
a threshold of 3 is good for reducing code size.

Differential Revision: https:/

[JumpThreading] Half the duplicate threshold at Oz

Duplicating instructions can lead to code size increases but using
a threshold of 3 is good for reducing code size.

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

show more ...

Revert "Resubmit: [JumpThreading] Thread jumps through two basic blocks"

This reverts commit 53b68e676faf208b4a8f817e9bd4ddd522cc6006.

Our internal tests are showing breakage with this patch.