[JumpThreading] Insert freeze when unfolding select

JumpThreading may convert selects into branch instructions,
in which case the condition needs to be frozen (as branch on
poison is immediate undef

[JumpThreading] Insert freeze when unfolding select

JumpThreading may convert selects into branch instructions,
in which case the condition needs to be frozen (as branch on
poison is immediate undefined behavior, unlike select on poison).

The necessary code for this is already in place, this just enables
the option.

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

show more ...

[JumpThreading] Regenerate test checks (NFC)

[JumpThreading] add a miscompile test based on discussion in D76332; NFC

[JumpThreading] Fix threading with unusual PHI nodes.

If the block being cloned contains a PHI node, in general, we need to
clone that PHI node, even though it's trivial. If the operand of the PHI
i

[JumpThreading] Fix threading with unusual PHI nodes.

If the block being cloned contains a PHI node, in general, we need to
clone that PHI node, even though it's trivial. If the operand of the PHI
is an instruction in the block being cloned, the correct value for the
operand doesn't exist until SSAUpdater constructs it.

We usually don't hit this issue because we try to avoid threading across
loop headers, but it's possible to hit this in some cases involving
irreducible CFGs. I added a flag to allow threading across loop headers
to make the testcase easier to understand.

Thanks to Brian Rzycki for reducing the testcase.

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

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

llvm-svn: 365094

show more ...

Revert "Temporarily Revert "Add basic loop fusion pass.""

The reversion apparently deleted the test/Transforms directory.

Will be re-reverting again.

llvm-svn: 358552

[Jump Threading] Unfold a select insn that feeds a switch via a phi node

Currently when a select has a constant value in one branch and the select feeds
a conditional branch (via a compare/ phi and

[Jump Threading] Unfold a select insn that feeds a switch via a phi node

Currently when a select has a constant value in one branch and the select feeds
a conditional branch (via a compare/ phi and compare) we unfold the select
statement. This results in threading the conditional branch later on. Similar
opportunity exists when a select (with a constant in one branch) feeds a
switch (via a phi node). The patch unfolds select under this condition.
A testcase is provided.

llvm-svn: 350931

show more ...

[JumpThreading] Track unreachable BBs to avoid processing

JumpThreading iterates over F until the IR quiesces. Transforming
unreachable BBs increases compile time and it is also possible to
never st

[JumpThreading] Track unreachable BBs to avoid processing

JumpThreading iterates over F until the IR quiesces. Transforming
unreachable BBs increases compile time and it is also possible to
never stabilize causing JumpThreading to hang. An older attempt at
fixing this problem was D3991 where removeUnreachableBlocks(F)
was called before JumpThreading began. This has a few drawbacks:
* expensive - the routine attempts to fix up the IR to identify
additional BBs that can be removed along with unreachable BBs.
* aggressive - does not identify and preserve the shape of the IR.
At a minimum it does not preserve loop hierarchies.
* invasive - altering reachable blocks it may disrupt IR shapes
that could have otherwise been JumpThreaded.

This patch avoids removeUnreachableBlocks(F) and instead tracks
unreachable BBs in a SmallPtrSet using DominatorTree to validate the
initial state of all BBs. We then rely on subsequent passes to identify
and remove these unreachable blocks from F.

Reviewers: dberlin, sebpop, kuhar, dinesh.d

Reviewed by: sebpop, kuhar

Subscribers: hiraditya, uabelho, llvm-commits

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

llvm-svn: 327713

show more ...

[JumpThreading] Add a pattern to TryToUnfoldSelectInCurrBB()

Add the following pattern to TryToUnfoldSelectInCurrBB()

bb:
%p = phi [0, %bb1], [1, %bb2], [0, %bb3], [1, %bb4], ...
%c = cmp %p,

[JumpThreading] Add a pattern to TryToUnfoldSelectInCurrBB()

Add the following pattern to TryToUnfoldSelectInCurrBB()

bb:
%p = phi [0, %bb1], [1, %bb2], [0, %bb3], [1, %bb4], ...
%c = cmp %p, 0
%s = select %c, trueval, falseval

The Select in the above pattern will be unfolded and then jump-threaded. The
current implementation does not allow CMP in the middle of PHI and Select.

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

llvm-svn: 308050

show more ...

[JumpThreading] Split select that has constant conditions coming from the PHI node

Look for PHI/Select in the same BB of the form

bb:
%p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %

[JumpThreading] Split select that has constant conditions coming from the PHI node

Look for PHI/Select in the same BB of the form

bb:
%p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ...
%s = select p, trueval, falseval

And expand the select into a branch structure. This later enables
jump-threading over bb in this pass.

Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold
select if the associated PHI has at least one constant. If the unfolded
select is not jump-threaded, it will be folded again in the later
optimizations.

llvm-svn: 257198

show more ...

[JumpThreading] Fix opcode bonus in getJumpThreadDuplicationCost()

The code that was meant to adjust the duplication cost based on the
terminator opcode was not being executed in cases where the ini

[JumpThreading] Fix opcode bonus in getJumpThreadDuplicationCost()

The code that was meant to adjust the duplication cost based on the
terminator opcode was not being executed in cases where the initial
threshold was hit inside the loop.

Subscribers: mcrosier, llvm-commits

Differential Revision: http://reviews.llvm.org/D15536

llvm-svn: 256568

show more ...

[opaque pointer type] Add textual IR support for explicit type parameter to load instruction

Essentially the same as the GEP change in r230786.

A similar migration script can be used to update test

[opaque pointer type] Add textual IR support for explicit type parameter to load instruction

Essentially the same as the GEP change in r230786.

A similar migration script can be used to update test cases, though a few more
test case improvements/changes were required this time around: (r229269-r229278)

import fileinput
import sys
import re

pat = re.compile(r"((?:=|:|^)\s*load (?:atomic )?(?:volatile )?(.*?))(| addrspace\(\d+\) *)\*($| *(?:%|@|null|undef|blockaddress|getelementptr|addrspacecast|bitcast|inttoptr|\[\[[a-zA-Z]|\{\{).*$)")

for line in sys.stdin:
sys.stdout.write(re.sub(pat, r"\1, \2\3*\4", line))

Reviewers: rafael, dexonsmith, grosser

Differential Revision: http://reviews.llvm.org/D7649

llvm-svn: 230794

show more ...

Fixed jump threading going to infinite loop.

This patch add code to remove unreachable blocks from function
as they may cause jump threading to stuck in infinite loop.

Differential Revision: http:/

Fixed jump threading going to infinite loop.

This patch add code to remove unreachable blocks from function
as they may cause jump threading to stuck in infinite loop.

Differential Revision: http://reviews.llvm.org/D3991

llvm-svn: 211103

show more ...

JumpThreading: Turn a select instruction into branching if it allows to thread one half of the select.

This is a common pattern coming out of simplifycfg generating gross code.

a:

JumpThreading: Turn a select instruction into branching if it allows to thread one half of the select.

This is a common pattern coming out of simplifycfg generating gross code.

a: ; preds = %entry
%sel = select i1 %cmp1, double %add, double 0.000000e+00
br label %b

b:
%cond5 = phi double [ %sel, %a ], [ %sub, %entry ]
%cmp6 = fcmp oeq double %cond5, 0.000000e+00
br i1 %cmp6, label %if.then, label %if.end

becomes

a:
br i1 %cmp1, label %b, label %if.then

b:
%cond5 = phi double [ %sub, %entry ], [ %add, %a ]
%cmp6 = fcmp oeq double %cond5, 0.000000e+00
br i1 %cmp6, label %if.then, label %if.end

Skipping block b completely if possible.

llvm-svn: 187880

show more ...

Update Transforms tests to use CHECK-LABEL for easier debugging. No functionality change.

This update was done with the following bash script:

find test/Transforms -name "*.ll" | \
while read N

Update Transforms tests to use CHECK-LABEL for easier debugging. No functionality change.

This update was done with the following bash script:

find test/Transforms -name "*.ll" | \
while read NAME; do
echo "$NAME"
if ! grep -q "^; *RUN: *llc" $NAME; then
TEMP=`mktemp -t temp`
cp $NAME $TEMP
sed -n "s/^define [^@]*@\([A-Za-z0-9_]*\)(.*$/\1/p" < $NAME | \
while read FUNC; do
sed -i '' "s/;\(.*\)\([A-Za-z0-9_]*\):\( *\)@$FUNC\([( ]*\)\$/;\1\2-LABEL:\3@$FUNC(/g" $TEMP
done
mv $TEMP $NAME
fi
done

llvm-svn: 186268

show more ...

JumpThreading: when default destination is the destination of some cases in a
switch, make sure we include the value for the cases when calculating edge
value from switch to the default destination.

JumpThreading: when default destination is the destination of some cases in a
switch, make sure we include the value for the cases when calculating edge
value from switch to the default destination.

rdar://12241132

llvm-svn: 163270

show more ...

Teach jump threading to "look through" a select when the branch direction of a terminator depends on it.
When it sees a promising select it now tries to figure out whether the condition of the select

Teach jump threading to "look through" a select when the branch direction of a terminator depends on it.
When it sees a promising select it now tries to figure out whether the condition of the select is known in any of the predecessors and if so it maps the operands appropriately.

llvm-svn: 121859

show more ...