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

[NFC] Header cleanup

Removed some unused headers, replaced some headers with forward class declarations.

Found using simple scripts like this one:
clear && ack --cpp -l '#include "llvm/ADT/IndexedM

[NFC] Header cleanup

Removed some unused headers, replaced some headers with forward class declarations.

Found using simple scripts like this one:
clear && ack --cpp -l '#include "llvm/ADT/IndexedMap.h"' | xargs grep -L 'IndexedMap[<]' | xargs grep -n --color=auto 'IndexedMap'

Patch by Eugene Kosov <claprix@yandex.ru>

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

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 266595

show more ...

[IndVarSimplify] Don't insert after a catchswitch

Widening a PHI requires us to insert a trunc.
The logical place for this trunc is in the same BB as the PHI.
This is not possible if the BB is termi

[IndVarSimplify] Don't insert after a catchswitch

Widening a PHI requires us to insert a trunc.
The logical place for this trunc is in the same BB as the PHI.
This is not possible if the BB is terminated by a catchswitch.

This fixes PR27133.

llvm-svn: 264926

show more ...

[LPM] Factor all of the loop analysis usage updates into a common helper
routine.

We were getting this wrong in small ways and generally being very
inconsistent about it across loop passes. Instead,

[LPM] Factor all of the loop analysis usage updates into a common helper
routine.

We were getting this wrong in small ways and generally being very
inconsistent about it across loop passes. Instead, let's have a common
place where we do this. One minor downside is that this will require
some analyses like SCEV in more places than they are strictly needed.
However, this seems benign as these analyses are complete no-ops, and
without this consistency we can in many cases end up with the legacy
pass manager scheduling deciding to split up a loop pass pipeline in
order to run the function analysis half-way through. It is very, very
annoying to fix these without just being very pedantic across the board.

The only loop passes I've not updated here are ones that use
AU.setPreservesAll() such as IVUsers (an analysis) and the pass printer.
They seemed less relevant.

With this patch, almost all of the problems in PR24804 around loop pass
pipelines are fixed. The one remaining issue is that we run simplify-cfg
and instcombine in the middle of the loop pass pipeline. We've recently
added some loop variants of these passes that would seem substantially
cleaner to use, but this at least gets us much closer to the previous
state. Notably, the seven loop pass managers is down to three.

I've not updated the loop passes using LoopAccessAnalysis because that
analysis hasn't been fully wired into LoopSimplify/LCSSA, and it isn't
clear that those transforms want to support those forms anyways. They
all run late anyways, so this is harmless. Similarly, LSR is left alone
because it already carefully manages its forms and doesn't need to get
fused into a single loop pass manager with a bunch of other loop passes.

LoopReroll didn't use loop simplified form previously, and I've updated
the test case to match the trivially different output.

Finally, I've also factored all the pass initialization for the passes
that use this technique as well, so that should be done regularly and
reliably.

Thanks to James for the help reviewing and thinking about this stuff,
and Ben for help thinking about it as well!

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

llvm-svn: 261316

show more ...

[IndVars] Hoist DataLayout load out of loop; NFC

llvm-svn: 258946

[IndVars] Use isSCEVable; NFC

llvm-svn: 258945

[IndVars] Use range-for; NFC

llvm-svn: 258944

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This is a revised version of D13974, and the following quoted summary are from D13974

"This patch ad

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This is a revised version of D13974, and the following quoted summary are from D13974

"This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If so, we know that if the exit path is taken, it is at the first loop iteration. If there is an induction variable used in that exit path whose value has not been updated, it will keep its initial value passing from loop preheader. We can therefore rewrite the exit value with
its initial value. This will help remove phis created by LCSSA and enable other optimizations like loop unswitch."

D13974 was committed but failed one lnt test. The bug was that we only checked the condition from loop exit's incoming block was a loop invariant. But there could be another condition from loop header to that incoming block not being a loop invariant. This would produce miscompiled code.

This patch fixes the issue by checking if the incoming block is loop header, and if not, don't perform the rewrite. The could be further improved by recursively checking all conditions leading to loop exit block, but I'd like to check in this simple version first and improve it with future patches.

Reviewers: sanjoy

Subscribers: llvm-commits

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

llvm-svn: 258912

show more ...

[IndVars] Fix PR25576

`LCSSASafePhiForRAUW` as computed was incorrect -- in cases like
these (this exact example does not actually trigger the bug):

define i32 @f(i32 %n, i1* %c) {
entry:
br labe

[IndVars] Fix PR25576

`LCSSASafePhiForRAUW` as computed was incorrect -- in cases like
these (this exact example does not actually trigger the bug):

define i32 @f(i32 %n, i1* %c) {
entry:
br label %outer.loop

outer.loop:
br label %inner.loop

inner.loop:
%iv = phi i32 [ 0, %outer.loop ], [ %iv.inc, %inner.loop ]
%iv.inc = add nuw nsw i32 %iv, 1
%tc = udiv i32 %n, 13
%be.cond = icmp ult i32 %iv, %tc
br i1 %be.cond, label %inner.loop, label %inner.exit

inner.exit:
%iv.lcssa = phi i32 [ %iv, %inner.loop ]
%outer.be.cond = load volatile i1, i1* %c
br i1 %outer.be.cond, label %outer.loop, label %leave

leave:
%iv.lcssa.lcssa = phi i32 [ %iv.lcssa, %inner.exit ]
ret i32 %iv.lcssa.lcssa
}

`LCSSASafePhiForRAUW` is true for `%iv.lcssa` when re-rewriting the exit
value of `%iv` for `%inner.loop` to `%tc` (this can happen due to
`SCEVExpander::findExistingExpansion`), but the RAUW breaks LCSSA.

To fix this, instead of computing `SafePhi` with special logic, decide
the safety of RAUW directly via `replacementPreservesLCSSAForm`.

llvm-svn: 258016

show more ...

[IndVars] Use emplace_back; NFC

llvm-svn: 258015

[SCEV] Add and use SCEVConstant::getAPInt; NFCI

llvm-svn: 255921

LPM: Stop threading `Pass *` through all of the loop utility APIs. NFC

A large number of loop utility functions take a `Pass *` and reach
into it to find out which analyses to preserve. There are a

LPM: Stop threading `Pass *` through all of the loop utility APIs. NFC

A large number of loop utility functions take a `Pass *` and reach
into it to find out which analyses to preserve. There are a number of
problems with this:

- The APIs have access to pretty well any Pass state they want, so
it's hard to tell what they may or may not do.

- Other APIs have copied these and pass around a `Pass *` even though
they don't even use it. Some of these just hand a nullptr to the API
since the callers don't even have a pass available.

- Passes in the new pass manager don't work like the current ones, so
the APIs can't be used as is there.

Instead, we should explicitly thread the analysis results that we
actually care about through these APIs. This is both simpler and more
reusable.

llvm-svn: 255669

show more ...

[IndVars] Use any_of and foreach instead of explicit for loops; NFC

llvm-svn: 255077

[IndVars] Have getInsertPointForUses preserve LCSSA

Summary:
Also add a stricter post-condition for IndVarSimplify.

Fixes PR25578. Test case by Michael Zolotukhin.

Reviewers: hfinkel, atrick, mzo

[IndVars] Have getInsertPointForUses preserve LCSSA

Summary:
Also add a stricter post-condition for IndVarSimplify.

Fixes PR25578. Test case by Michael Zolotukhin.

Reviewers: hfinkel, atrick, mzolotukhin

Subscribers: llvm-commits

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

llvm-svn: 254977

show more ...

use convenience function for copying IR flags; NFCI

llvm-svn: 253996

Revert "[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader"

Commit 251839 triggers miscompiles on some bots:

http://lab.llvm.org:8011/builders/perf-x86_64-penry

Revert "[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader"

Commit 251839 triggers miscompiles on some bots:

http://lab.llvm.org:8011/builders/perf-x86_64-penryn-O3-polly-fast/builds/13723

(The commit is listed in 13722, but due to an existing failure introduced in
13721 and reverted in 13723 the failure is only visible in 13723)

To verify r251839 is indeed the only change that triggered the buildbot failures
and to ensure the buildbots remain green while investigating I temporarily
revert this commit. At the current state it is unclear if this commit introduced
some miscompile or if it only exposed code to Polly that is subsequently
miscompiled by Polly.

llvm-svn: 251901

show more ...

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If so, we know that if the exit path is taken, it is at the first loop iteration. If there is an induction variable used in that exit path whose value has not been updated, it will keep its initial value passing from loop preheader. We can therefore rewrite the exit value with
its initial value. This will help remove phis created by LCSSA and enable other optimizations like loop unswitch.


Reviewers: sanjoy

Subscribers: llvm-commits

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

llvm-svn: 251839

show more ...

Revert r251492 "[IndVarSimplify] Rewrite loop exit values with their
initial values from loop preheader", because it broke some bots.

llvm-svn: 251498

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If so, we know that if the exit path is taken, it is at the first loop iteration. If there is an induction variable used in that exit path whose value has not been updated, it will keep its initial value passing from loop preheader. We can therefore rewrite the exit value with
its initial value. This will help remove phis created by LCSSA and enable other optimizations like loop unswitch.


Reviewers: sanjoy

Subscribers: llvm-commits

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

llvm-svn: 251492

show more ...

[IndVars] Rename getExtend; NFC

Rename `IndVarSimplify::getExtend` to `IndVarSimplify::createExtendInst`
to make it obvious that it creates `llvm::Instruction` s.

llvm-svn: 250484

[IndVars] Have `cloneArithmeticIVUser` guess better

Summary:
`cloneArithmeticIVUser` currently trips over expression like `add %iv,
-1` when `%iv` is being zero extended -- it tries to construct the

[IndVars] Have `cloneArithmeticIVUser` guess better

Summary:
`cloneArithmeticIVUser` currently trips over expression like `add %iv,
-1` when `%iv` is being zero extended -- it tries to construct the
widened use as `add %iv.zext, zext(-1)` and (correctly) fails to prove
equivalence to `zext(add %iv, -1)` (here the SCEV for `%iv` is
`{1,+,1}`).

This change teaches `IndVars` to try sign extending the non-IV operand
if that makes the newly constructed IV use equivalent to the widened
narrow IV use.

Reviewers: atrick, hfinkel, reames

Subscribers: sanjoy, llvm-commits

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

llvm-svn: 250483

show more ...

[IndVars] Extract out a few local variables; NFC

llvm-svn: 250482

[IndVars] Split `WidenIV::cloneIVUser`; NFC

Summary:
This NFC splitting is intended to make a later diff easier to follow.
It just tail duplicates `cloneIVUser` into `cloneArithmeticIVUser` and
`clo

[IndVars] Split `WidenIV::cloneIVUser`; NFC

Summary:
This NFC splitting is intended to make a later diff easier to follow.
It just tail duplicates `cloneIVUser` into `cloneArithmeticIVUser` and
`cloneBitwiseIVUser`.

Reviewers: atrick, hfinkel, reames

Subscribers: llvm-commits

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

llvm-svn: 250481

show more ...

Scalar: Remove some implicit ilist iterator conversions, NFC

Remove some of the implicit ilist iterator conversions in
LLVMScalarOpts. More to go.

llvm-svn: 250197