[IndVars] Change the order to compute WidenAddRec in widenIVUse.

When both WidenIV::getWideRecurrence and WidenIV::getExtendedOperandRecurrence
return non-null but different WideAddRec, if getWideRe

[IndVars] Change the order to compute WidenAddRec in widenIVUse.

When both WidenIV::getWideRecurrence and WidenIV::getExtendedOperandRecurrence
return non-null but different WideAddRec, if getWideRecurrence is called
before getExtendedOperandRecurrence, we won't bother to call
getExtendedOperandRecurrence again. But As we know it is possible that after
SCEV folding, we cannot prove the legality using the SCEVAddRecExpr returned
by getWideRecurrence. Meanwhile if getExtendedOperandRecurrence returns non-null
WideAddRec, we know for sure that it is legal to do widening for current instruction.
So it is better to put getExtendedOperandRecurrence before getWideRecurrence, which
will increase the chance of successful widening.

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

llvm-svn: 286987

show more ...

[IndVarSimplify][DebugLoc] When widening the exit loop condition, correctly reuse the debug location of the original comparison.

When the loop exit condition is canonicalized as a != compaison, reus

[IndVarSimplify][DebugLoc] When widening the exit loop condition, correctly reuse the debug location of the original comparison.

When the loop exit condition is canonicalized as a != compaison, reuse the
debug location of the original (non canonical) comparison.

Before this patch, the debug location of the new icmp was obtained from the
loop latch terminator. This patch fixes the issue by correctly setting the
IRBuilder's "current debug location" to the location of the original compare.

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

llvm-svn: 285185

show more ...

[IndVarSimplify][Dwarf] When widening the IV increment, correctly set the debug loc.

When indvars widened an induction variable, the debug location for the loop
increment computation was incorrectly

[IndVarSimplify][Dwarf] When widening the IV increment, correctly set the debug loc.

When indvars widened an induction variable, the debug location for the loop
increment computation was incorrectly set equal to the debug loc of the loop
latch terminator.

This patch fixes the issue by propagating the correct location from the
original loop increment instruction to the new widened increment.

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

llvm-svn: 285083

show more ...

[IndVarSimplify] Teach calculatePostIncRange to take guards into account

Reviewed By: sanjoy

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

llvm-svn: 284632

[IndVarSimplify] Use control-dependent range information to prove non-negativity

This change is motivated by the case when IndVarSimplify doesn't widen a comparison of IV increment because it ca

[IndVarSimplify] Use control-dependent range information to prove non-negativity

This change is motivated by the case when IndVarSimplify doesn't widen a comparison of IV increment because it can't prove IV increment being non-negative. We end up with a redundant trunc of the widened increment on this example.

for.body:
%i = phi i32 [ %start, %for.body.lr.ph ], [ %i.inc, %for.inc ]
%within_limits = icmp ult i32 %i, 64
br i1 %within_limits, label %continue, label %for.end

continue:
%i.i64 = zext i32 %i to i64
%arrayidx = getelementptr inbounds i32, i32* %base, i64 %i.i64
%val = load i32, i32* %arrayidx, align 4
br label %for.inc

for.inc:
%i.inc = add nsw nuw i32 %i, 1
%cmp = icmp slt i32 %i.inc, %limit
br i1 %cmp, label %for.body, label %for.end

There is a range check inside of the loop which guarantees the IV to be non-negative. NSW on the increment guarantees that the increment is also non-negative. Teach IndVarSimplify to use the range check to prove non-negativity of loop increments.

Reviewed By: sanjoy

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

llvm-svn: 284629

show more ...

[LCSSA] Implement linear algorithm for the isRecursivelyLCSSAForm

For each block check that it doesn't have any uses outside of it's innermost loop.

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

[LCSSA] Implement linear algorithm for the isRecursivelyLCSSAForm

For each block check that it doesn't have any uses outside of it's innermost loop.

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

llvm-svn: 283877

show more ...

Turn cl::values() (for enum) from a vararg function to using C++ variadic template

The core of the change is supposed to be NFC, however it also fixes
what I believe was an undefined behavior when c

Turn cl::values() (for enum) from a vararg function to using C++ variadic template

The core of the change is supposed to be NFC, however it also fixes
what I believe was an undefined behavior when calling:

va_start(ValueArgs, Desc);

with Desc being a StringRef.

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

llvm-svn: 283671

show more ...

Wisely choose sext or zext when widening IV.

Summary:
The patch fixes regression caused by two earlier patches D18777 and D18867.

Reviewers: reames, sanjoy

Differential Revision: http://reviews.ll

Wisely choose sext or zext when widening IV.

Summary:
The patch fixes regression caused by two earlier patches D18777 and D18867.

Reviewers: reames, sanjoy

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

From: Li Huang
llvm-svn: 282650

show more ...

Revert -r278269 [IndVarSimplify] Eliminate zext of a signed IV when the IV is known to be non-negative

This change needs to be reverted in order to revert -r278267 which cause performance regression

Revert -r278269 [IndVarSimplify] Eliminate zext of a signed IV when the IV is known to be non-negative

This change needs to be reverted in order to revert -r278267 which cause performance regression on MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt from LNT and some other bechmarks.

See comments on https://reviews.llvm.org/D18777 for details.

llvm-svn: 279432

show more ...

Scalar: Avoid dereferencing end() in IndVarSimplify

IndVarSimplify::sinkUnusedInvariants calls
BasicBlock::getFirstInsertionPt on the ExitBlock and moves instructions
before it. This can return end

Scalar: Avoid dereferencing end() in IndVarSimplify

IndVarSimplify::sinkUnusedInvariants calls
BasicBlock::getFirstInsertionPt on the ExitBlock and moves instructions
before it. This can return end(), so it's not safe to dereference. Add
an iterator-based overload to Instruction::moveBefore to avoid the UB.

llvm-svn: 278886

show more ...

[IndVars] Ignore (s|z)exts that don't extend the induction variable

`IVVisitor::visitCast` used to have the invariant that if the
instruction it was passed was a sext or zext instruction, the result

[IndVars] Ignore (s|z)exts that don't extend the induction variable

`IVVisitor::visitCast` used to have the invariant that if the
instruction it was passed was a sext or zext instruction, the result of
the instruction would be wider than the induction variable. This is no
longer true after rL275037, so this change teaches `IndVarSimplify` s
implementation of `IVVisitor::visitCast` to work with the relaxed
invariant.

A corresponding change to SimplifyIndVar to preserve the said invariant
after rL275037 would also work, but given how `IVVisitor::visitCast` is
spelled (no indication of said invariant), I figured the current fix is
cleaner.

Fixes PR28935.

llvm-svn: 278584

show more ...

Extend trip count instead of truncating IV in LFTR, when legal

When legal, extending trip count in the loop control logic generates better code compared to truncating IV. This is because

(1) extend

Extend trip count instead of truncating IV in LFTR, when legal

When legal, extending trip count in the loop control logic generates better code compared to truncating IV. This is because

(1) extending trip count is a loop invariant operation (see genLoopLimit where we prove trip count is loop invariant).
(2) Scalar Evolution seems to have problems understanding trunc when computing loop trip count. So removing them allows better analysis performed in Scalar Evolution. (In particular this fixes PR 28363 which is the motivation for this change).

I am not going to perform any performance test. Any degradation caused by this should be an indication of a bug elsewhere.

To prove legality, we rely on SCEV to prove zext(trunc(IV)) == IV (or similarly for sext). If this holds, we can prove equivalence of trunc(IV)==ExitCnt (1) and IV == zext(ExitCnt). Simply take zext of boths sides of (1) and apply the proven equivalence.

This commit contains changes in a newly added testcase which was not included in the previous commit (which was reverted later on).

https://reviews.llvm.org/D23075

llvm-svn: 278421

show more ...

revert 278334

llvm-svn: 278337

Extend trip count instead of truncating IV in LFTR, when legal

When legal, extending trip count in the loop control logic generates better code compared to truncating IV. This is because

(1) extend

Extend trip count instead of truncating IV in LFTR, when legal

When legal, extending trip count in the loop control logic generates better code compared to truncating IV. This is because

(1) extending trip count is a loop invariant operation (see genLoopLimit where we prove trip count is loop invariant).
(2) Scalar Evolution seems to have problems understanding trunc when computing loop trip count. So removing them allows better analysis performed in Scalar Evolution. (In particular this fixes PR 28363 which is the motivation for this change).

I am not going to perform any performance test. Any degradation caused by this should be an indication of a bug elsewhere.

To prove legality, we rely on SCEV to prove zext(trunc(IV)) == IV (or similarly for sext). If this holds, we can prove equivalence of trunc(IV)==ExitCnt (1) and IV == zext(ExitCnt). Simply take zext of boths sides of (1) and apply the proven equivalence.

https://reviews.llvm.org/D23075

llvm-svn: 278334

show more ...

[IndVarSimplify] Eliminate zext of a signed IV when the IV is known to be non-negative

Patch by Li Huang

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

llvm-svn: 278269

Fix the runtime error caused by "Use ValueOffsetPair to enhance value reuse during SCEV expansion".

The patch is to fix the bug in PR28705. It was caused by setting wrong return
value for SCEVExpand

Fix the runtime error caused by "Use ValueOffsetPair to enhance value reuse during SCEV expansion".

The patch is to fix the bug in PR28705. It was caused by setting wrong return
value for SCEVExpander::findExistingExpansion. The return values of findExistingExpansion
have different meanings when the function is used in different ways so it is easy to make
mistake. The fix creates two new interfaces to replace SCEVExpander::findExistingExpansion,
and specifies where each interface is expected to be used.

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

llvm-svn: 278161

show more ...

Consistently use LoopAnalysisManager

One exception here is LoopInfo which must forward-declare it (because
the typedef is in LoopPassManager.h which depends on LoopInfo).

Also, some includes for Lo

Consistently use LoopAnalysisManager

One exception here is LoopInfo which must forward-declare it (because
the typedef is in LoopPassManager.h which depends on LoopInfo).

Also, some includes for LoopPassManager.h were needed since that file
provides the typedef.

Besides a general consistently benefit, the extra layer of indirection
allows the mechanical part of https://reviews.llvm.org/D23256 that
requires touching every transformation and analysis to be factored out
cleanly.

Thanks to David for the suggestion.

llvm-svn: 278079

show more ...

[IndVars] Reflow oddly formatted condition; NFC

llvm-svn: 276319

[PM] Normalize FIXMEs for missing PreserveCFG to have the same wording.

llvm-svn: 273974

[IndVarSimplify] Run clang-format over some oddly formatted bits

NFC (whitespace only change)

llvm-svn: 273732

[PM] Port IndVarSimplify to the new pass manager

Summary:
There are some rough corners, since the new pass manager doesn't have
(as far as I can tell) LoopSimplify and LCSSA, so I've updated the
tes

[PM] Port IndVarSimplify to the new pass manager

Summary:
There are some rough corners, since the new pass manager doesn't have
(as far as I can tell) LoopSimplify and LCSSA, so I've updated the
tests to run them separately in the old pass manager in the lit tests.
We also don't have an equivalent for AU.setPreservesCFG() in the new
pass manager, so I've left a FIXME.

Reviewers: bogner, chandlerc, davide

Subscribers: sanjoy, mcrosier, llvm-commits

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

llvm-svn: 271846

show more ...

[IndVars] Remove -liv-reduce

It is an off-by-default option that no one seems to use[0], and given
that SCEV directly understands the overflow instrinsics there is no real
need for it anymore.

[0]:

[IndVars] Remove -liv-reduce

It is an off-by-default option that no one seems to use[0], and given
that SCEV directly understands the overflow instrinsics there is no real
need for it anymore.

[0]: http://lists.llvm.org/pipermail/llvm-dev/2016-April/098181.html

llvm-svn: 271845

show more ...

[IndVars] Assert that the incoming IR is in LCSSA

Since we already assert that the outgoing IR is in LCSSA, it is easy to
get misled into thinking that -indvars broke LCSSA if the incoming IR is
non

[IndVars] Assert that the incoming IR is in LCSSA

Since we already assert that the outgoing IR is in LCSSA, it is easy to
get misled into thinking that -indvars broke LCSSA if the incoming IR is
non-LCSSA. Checking this pre-condition will make such cases break in
more obvious ways.

Inspired by (but does _not_ fix) PR26682.

llvm-svn: 271196

show more ...

[IndVarSimplify] Extract the logic of `-indvars` out into a class; NFC

This will be used later to port IndVarSimplify to the new pass manager.

llvm-svn: 271190

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