[PM] Port LVI to the new PM.

This is a bit gnarly since LVI is maintaining its own cache.
I think this port could be somewhat cleaner, but I'd rather not spend
too much time on it while we still hav

[PM] Port LVI to the new PM.

This is a bit gnarly since LVI is maintaining its own cache.
I think this port could be somewhat cleaner, but I'd rather not spend
too much time on it while we still have the old pass hanging around and
limiting how much we can clean things up.
Once the old pass is gone it will be easier (less time spent) to clean
it up anyway.

This is the last dependency needed for porting JumpThreading which I'll
do in a follow-up commit (there's no printer pass for LVI or anything to
test it, so porting a pass that depends on it seems best).

I've been mostly following:
r269370 / D18834 which ported Dependence Analysis
r268601 / D19839 which ported BPI

llvm-svn: 272593

show more ...

[ValueTracking] Improve isImpliedCondition when the dominating cond is false.

llvm-svn: 267430

Re-commit optimization bisect support (r267022) without new pass manager support.

The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the

Re-commit optimization bisect support (r267022) without new pass manager support.

The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the OptBisect handling).

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

llvm-svn: 267231

show more ...

Revert "Initial implementation of optimization bisect support."

This reverts commit r267022, due to an ASan failure:

http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549

llvm-s

Revert "Initial implementation of optimization bisect support."

This reverts commit r267022, due to an ASan failure:

http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549

llvm-svn: 267115

show more ...

Initial implementation of optimization bisect support.

This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to trac

Initial implementation of optimization bisect support.

This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations.

The bisection is enabled using a new command line option (-opt-bisect-limit). Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit. A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used.

The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check. Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute. A new function call has been added for module and SCC passes that behaves in a similar way.

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

llvm-svn: 267022

show more ...

[ValueTracking] Make isImpliedCondition return an Optional<bool>. NFC.

Phabricator Revision: http://reviews.llvm.org/D19277

llvm-svn: 266904

[ValueTracking] Improve isImpliedCondition for conditions with matching operands.

This patch improves SimplifyCFG to catch cases like:

if (a < b) {
if (a > b) <- known to be false
unrea

[ValueTracking] Improve isImpliedCondition for conditions with matching operands.

This patch improves SimplifyCFG to catch cases like:

if (a < b) {
if (a > b) <- known to be false
unreachable;
}

Phabricator Revision: http://reviews.llvm.org/D18905

llvm-svn: 266767

show more ...

[SimlifyCFG] Prevent passes from destroying canonical loop structure, especially for nested loops

When eliminating or merging almost empty basic blocks, the existence of non-trivial PHI nodes
is

[SimlifyCFG] Prevent passes from destroying canonical loop structure, especially for nested loops

When eliminating or merging almost empty basic blocks, the existence of non-trivial PHI nodes
is currently used to recognize potential loops of which the block is the header and keep the block.
However, the current algorithm fails if the loops' exit condition is evaluated only with volatile
values hence no PHI nodes in the header. Especially when such a loop is an outer loop of a nested
loop, the loop is collapsed into a single loop which prevent later optimizations from being
applied (e.g., transforming nested loops into simplified forms and loop vectorization).

The patch augments the existing PHI node-based check by adding a pre-test if the BB actually
belongs to a set of loop headers and not eliminating it if yes.

llvm-svn: 264697

show more ...

Revert "[SimlifyCFG] Prevent passes from destroying canonical loop structure, especially for nested loops"

This reverts commit r264596.

It does not compile.

llvm-svn: 264604

[SimlifyCFG] Prevent passes from destroying canonical loop structure, especially for nested loops

When eliminating or merging almost empty basic blocks, the existence of non-trivial PHI nodes
is cur

[SimlifyCFG] Prevent passes from destroying canonical loop structure, especially for nested loops

When eliminating or merging almost empty basic blocks, the existence of non-trivial PHI nodes
is currently used to recognize potential loops of which the block is the header and keep the block.
However, the current algorithm fails if the loops' exit condition is evaluated only with volatile
values hence no PHI nodes in the header. Especially when such a loop is an outer loop of a nested
loop, the loop is collapsed into a single loop which prevent later optimizations from being
applied (e.g., transforming nested loops into simplified forms and loop vectorization).

The patch augments the existing PHI node-based check by adding a pre-test if the BB actually
belongs to a set of loop headers and not eliminating it if yes.

llvm-svn: 264596

show more ...

[JumpThreading] See through Cast Instructions

To capture more jump-thread opportunity.

llvm-svn: 263618

Revert "[JumpThreading] Simplify Instructions first in ComputeValueKnownInPredecessors()"

Not sure it handles undef properly.

llvm-svn: 263605

[JumpThreading] Simplify Instructions first in ComputeValueKnownInPredecessors()

This change tries to find more opportunities to thread over basic blocks.

llvm-svn: 261981

[JumpThreading] Change a return of ComputeValueKnownInPredecessors()

Change a return statement of ComputeValueKnownInPredecessors() to be the same as
the rest return statements of the function. Othe

[JumpThreading] Change a return of ComputeValueKnownInPredecessors()

Change a return statement of ComputeValueKnownInPredecessors() to be the same as
the rest return statements of the function. Otherwise, it might return true with
an empty Result when the current basic block has no predecessors and trigger the
first assert of JumpThreading::ProcessThreadableEdges().

llvm-svn: 260110

show more ...

[opaque pointer types] [NFC] FindAvailableLoadedValue: take LoadInst instead of just the pointer.

Reviewers: mjacob, dblaikie

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.o

[opaque pointer types] [NFC] FindAvailableLoadedValue: take LoadInst instead of just the pointer.

Reviewers: mjacob, dblaikie

Subscribers: llvm-commits

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

llvm-svn: 258477

show more ...

[JumpThreading] Don't forget to report that the IR changed

JumpThreading's runOnFunction is supposed to return true if it made any
changes. JumpThreading has a call to removeUnreachableBlocks which

[JumpThreading] Don't forget to report that the IR changed

JumpThreading's runOnFunction is supposed to return true if it made any
changes. JumpThreading has a call to removeUnreachableBlocks which may
result in changes to the IR but runOnFunction didn't appropriate account
for this possibility, leading to badness.

While we are here, make sure to call LazyValueInfo::eraseBlock in
removeUnreachableBlocks; JumpThreading preserves LVI.

This fixes PR26096.

llvm-svn: 257279

show more ...

[JumpThreading] Use range-based for loops.

No functionality change intended.

llvm-svn: 257262

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

[BPI] Fix two potential divide-by-zero operations that are introduced in r256263.

llvm-svn: 256303

[BPI] Replace weights by probabilities in BPI.

This patch removes all weight-related interfaces from BPI and replace
them by probability versions. With this patch, we won't use edge weight
anymore i

[BPI] Replace weights by probabilities in BPI.

This patch removes all weight-related interfaces from BPI and replace
them by probability versions. With this patch, we won't use edge weight
anymore in either IR or MC passes. Edge probabilitiy is a better
representation in terms of CFG update and validation.


Differential revision: http://reviews.llvm.org/D15519

llvm-svn: 256263

show more ...

[ValueTracking] Add parameters to isImpliedCondition; NFC

Summary:
This change makes the `isImpliedCondition` interface similar to the rest
of the functions in ValueTracking (in that it takes a Data

[ValueTracking] Add parameters to isImpliedCondition; NFC

Summary:
This change makes the `isImpliedCondition` interface similar to the rest
of the functions in ValueTracking (in that it takes a DataLayout,
AssumptionCache etc.). This is an NFC, intended to make a later diff
less noisy.

Depends on D14369

Subscribers: llvm-commits

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

llvm-svn: 252333

show more ...

[JumpThreading] Use dominating conditions to prove implications

Summary:
If P branches to Q conditional on C and Q branches to R conditional on
C' and C => C' then the branch conditional on C' can b

[JumpThreading] Use dominating conditions to prove implications

Summary:
If P branches to Q conditional on C and Q branches to R conditional on
C' and C => C' then the branch conditional on C' can be folded to an
unconditional branch.

Reviewers: reames

Subscribers: llvm-commits

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

llvm-svn: 251557

show more ...

Recommit r250345, it was reverted in r250366 to investigate a bot failure.

Our internal bot is still red after r250366.

llvm-svn: 250415

Temporarily revert r250345 to sort out bot failure.

With r250345 and r250343, we start to observe the following failure
when bootstrap clang with lto and pgo:
PHI node entries do not match predecess

Temporarily revert r250345 to sort out bot failure.

With r250345 and r250343, we start to observe the following failure
when bootstrap clang with lto and pgo:
PHI node entries do not match predecessors!
%.sroa.029.3.i = phi %"class.llvm::SDNode.13298"* [ null, %30953 ], [ null, %31017 ], [ null, %30998 ], [ null, %_ZN4llvm8dyn_castINS_14ConstantSDNodeENS_7SDValueEEENS_10cast_rettyIT_T0_E8ret_typeERS5_.exit.i.1804 ], [ null, %30975 ], [ null, %30991 ], [ null, %_ZNK4llvm3EVT13getScalarTypeEv.exit.i.1812 ], [ %..sroa.029.0.i, %_ZN4llvm11SmallVectorIiLj8EED1Ev.exit.i.1826 ], !dbg !451895
label %30998
label %_ZNK4llvm3EVTeqES0_.exit19.thread.i
LLVM ERROR: Broken function found, compilation aborted!

I will re-commit this if the bot does not recover.

llvm-svn: 250366

show more ...