292 Commits

Author SHA1 Message Date
Sanjoy Das
9b2526d03d [ValueTracking] Don't do an unchecked shift in ComputeNumSignBits
Summary:
Previously we used to return a bogus result, 0, for IR like `ashr %val,
-1`.

I've also added an assert checking that `ComputeNumSignBits` at least
returns 1.  That assert found an already checked in test case where we
were returning a bad result for `ashr %val, -1`.

Fixes PR32045.

Reviewers: spatel, majnemer

Reviewed By: spatel, majnemer

Subscribers: efriedma, mcrosier, llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@296273 91177308-0d34-0410-b5e6-96231b3b80d8
2017-02-25 20:30:45 +00:00
Peter Collingbourne
4f50278f40 opt: Rename -default-data-layout flag to -data-layout and make it always override the layout.
There isn't much point in a flag that only works if the data layout is empty.

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@295468 91177308-0d34-0410-b5e6-96231b3b80d8
2017-02-17 17:36:52 +00:00
Wei Mi
334f714ef9 [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


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@286987 91177308-0d34-0410-b5e6-96231b3b80d8
2016-11-15 17:34:52 +00:00
Artur Pilipenko
86fff1f817 [IndVarSimplify] Teach calculatePostIncRange to take guards into account
Reviewed By: sanjoy

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


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@284632 91177308-0d34-0410-b5e6-96231b3b80d8
2016-10-19 19:43:54 +00:00
Artur Pilipenko
6ca75fa2b4 [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


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@284629 91177308-0d34-0410-b5e6-96231b3b80d8
2016-10-19 18:59:03 +00:00
Evgeny Stupachenko
6642664652 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


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@282650 91177308-0d34-0410-b5e6-96231b3b80d8
2016-09-28 23:39:39 +00:00
Artur Pilipenko
d8d6388a44 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.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@279432 91177308-0d34-0410-b5e6-96231b3b80d8
2016-08-22 13:12:07 +00:00
Sanjoy Das
5b64093791 [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.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@278584 91177308-0d34-0410-b5e6-96231b3b80d8
2016-08-13 00:58:31 +00:00
Ehsan Amiri
f11cae6f49 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



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@278421 91177308-0d34-0410-b5e6-96231b3b80d8
2016-08-11 21:31:40 +00:00
Ehsan Amiri
d418a914db revert 278334
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@278337 91177308-0d34-0410-b5e6-96231b3b80d8
2016-08-11 14:51:14 +00:00
Ehsan Amiri
543fef7ea9 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



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@278334 91177308-0d34-0410-b5e6-96231b3b80d8
2016-08-11 13:51:20 +00:00
Andrew Kaylor
9c0625fb5a [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



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@278269 91177308-0d34-0410-b5e6-96231b3b80d8
2016-08-10 18:56:35 +00:00
Sanjoy Das
5494503e0b [IndVars] Un-grepify test; NFC
Some of these tests need to be cleaned up further to make it obvious
what they're testing, but as a first step remove all instances of
"grep".

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@277648 91177308-0d34-0410-b5e6-96231b3b80d8
2016-08-03 20:53:23 +00:00
Artur Pilipenko
525757e9f7 Upgrade other old memset/memcpy signatures in tests causing buildbot failures with rL273568.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@273580 91177308-0d34-0410-b5e6-96231b3b80d8
2016-06-23 16:34:52 +00:00
Sanjoy Das
a55495a2e8 [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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@271846 91177308-0d34-0410-b5e6-96231b3b80d8
2016-06-05 18:01:19 +00:00
Sanjoy Das
fa9013b737 [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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@271845 91177308-0d34-0410-b5e6-96231b3b80d8
2016-06-05 18:01:12 +00:00
Sanjoy Das
59287c36a0 [IndVars] Eliminate op.with.overflow when possible (re-apply)
Summary:
If we can prove that an op.with.overflow intrinsic does not overflow, we
can get rid of the intrinsic, and replace it with non-wrapping
arithmetic.

This was first checked in at r265913 but reverted in r265950 because it
exposed some issues around how SCEV handled post-inc add recurrences.
Those issues have now been fixed.

Reviewers: atrick, regehr

Subscribers: sanjoy, mcrosier, llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@271153 91177308-0d34-0410-b5e6-96231b3b80d8
2016-05-29 00:36:25 +00:00
Sanjoy Das
11ed8edc19 [SCEV] Don't always add no-wrap flags to post-inc add recs
Fixes PR27315.

The post-inc version of an add recurrence needs to "follow the same
rules" as a normal add or subtract expression.  Otherwise we miscompile
programs like

```
int main() {
  int a = 0;
  unsigned a_u = 0;
  volatile long last_value;
  do {
    a_u += 3;
    last_value = (long) ((int) a_u);
    if (will_add_overflow(a, 3)) {
      // Leave, and don't actually do the increment, so no UB.
      printf("last_value = %ld\n", last_value);
      exit(0);
    }
    a += 3;
  } while (a != 46);
  return 0;
}
```

This patch changes SCEV to put no-wrap flags on post-inc add recurrences
only when the poison from a potential overflow will go ahead to cause
undefined behavior.

To avoid regressing performance too much, I've assumed infinite loops
without side effects is undefined behavior to prove poison<->UB
equivalence in more cases.  This isn't ideal, but is not new to LLVM as
a whole, and far better than the situation I'm trying to fix.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@271151 91177308-0d34-0410-b5e6-96231b3b80d8
2016-05-29 00:32:17 +00:00
Mandeep Singh Grang
2599294457 [LLVM] Remove unwanted --check-prefix=CHECK from unit tests. NFC.
Summary: Removed unwanted --check-prefix=CHECK from numerous unit tests.

Reviewers: t.p.northover, dblaikie, uweigand, MatzeB, tstellarAMD, mcrosier

Subscribers: mcrosier, dsanders

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@266834 91177308-0d34-0410-b5e6-96231b3b80d8
2016-04-19 23:51:52 +00:00
Sanjoy Das
5e07ce6898 This reverts commit r265913 and r265912
See PR27315

r265913: "[IndVars] Eliminate op.with.overflow when possible"

r265912: "[SCEV] See through op.with.overflow intrinsics"

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@265950 91177308-0d34-0410-b5e6-96231b3b80d8
2016-04-11 15:26:18 +00:00
Sanjoy Das
0a4c40265b [IndVars] Eliminate op.with.overflow when possible
Summary:
If we can prove that an op.with.overflow intrinsic does not overflow, we
can get rid of the intrinsic, and replace it with non-wrapping
arithmetic.

Reviewers: atrick, regehr

Subscribers: sanjoy, mcrosier, llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@265913 91177308-0d34-0410-b5e6-96231b3b80d8
2016-04-10 22:50:31 +00:00
David Majnemer
82ef54d4b0 [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.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@264926 91177308-0d34-0410-b5e6-96231b3b80d8
2016-03-30 21:12:06 +00:00
Matt Arsenault
bb366db643 AMDGPU: Cost model for basic integer operations
This resolves bug 21148 by preventing promotion to
i64 induction variables.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@264376 91177308-0d34-0410-b5e6-96231b3b80d8
2016-03-25 01:16:40 +00:00
Silviu Baranga
872392e1a9 [IndVars] Fix PR26974: make sure replaceCongruentIVs doesn't break LCSSA
Summary:
replaceCongruentIVs can break LCSSA when trying to replace IV increments
since it tries to replace all uses of a phi node with another phi node
while both of the phi nodes are not necessarily in the processed loop.
This will cause an assert in IndVars.

To fix this, we add a check to make sure that the replacement maintains
LCSSA.

Reviewers: sanjoy

Subscribers: mzolotukhin, llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@263941 91177308-0d34-0410-b5e6-96231b3b80d8
2016-03-21 12:44:29 +00:00
Sanjoy Das
b289a83438 [IndVars] Pass the right loop to isLoopInvariantPredicate
The loop on IVOperand's incoming values assumes IVOperand to be an
induction variable on the loop over which `S Pred X` is invariant;
otherwise loop invariant incoming values to IVOperand are not guaranteed
to dominate the comparision.

This fixes PR26973.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@263827 91177308-0d34-0410-b5e6-96231b3b80d8
2016-03-18 20:37:07 +00:00
Wei Mi
eafb39b656 [SCEV] Try to reuse existing value during SCEV expansion
Current SCEV expansion will expand SCEV as a sequence of operations
and doesn't utilize the value already existed. This will introduce
redundent computation which may not be cleaned up throughly by
following optimizations.

This patch introduces an ExprValueMap which is a map from SCEV to the
set of equal values with the same SCEV. When a SCEV is expanded, the
set of values is checked and reused whenever possible before generating
a sequence of operations.

The original commit triggered regressions in Polly tests. The regressions
exposed two problems which have been fixed in current version.

1. Polly will generate a new function based on the old one. To generate an
instruction for the new function, it builds SCEV for the old instruction,
applies some tranformation on the SCEV generated, then expands the transformed
SCEV and insert the expanded value into new function. Because SCEV expansion
may reuse value cached in ExprValueMap, the value in old function may be
inserted into new function, which is wrong.
   In SCEVExpander::expand, there is a logic to check the cached value to
be used should dominate the insertion point. However, for the above
case, the check always passes. That is because the insertion point is
in a new function, which is unreachable from the old function. However
for unreachable node, DominatorTreeBase::dominates thinks it will be
dominated by any other node.
   The fix is to simply add a check that the cached value to be used in
expansion should be in the same function as the insertion point instruction.

2. When the SCEV is of scConstant type, expanding it directly is cheaper than
reusing a normal value cached. Although in the cached value set in ExprValueMap,
there is a Constant type value, but it is not easy to find it out -- the cached
Value set is not sorted according to the potential cost. Existing reuse logic
in SCEVExpander::expand simply chooses the first legal element from the cached
value set.
   The fix is that when the SCEV is of scConstant type, don't try the reuse
logic. simply expand it.

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



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@259736 91177308-0d34-0410-b5e6-96231b3b80d8
2016-02-04 01:27:38 +00:00
Wei Mi
dcbf7c311e Revert r259662, which caused regressions on polly tests.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@259675 91177308-0d34-0410-b5e6-96231b3b80d8
2016-02-03 18:05:57 +00:00
Wei Mi
e32bfe25a3 [SCEV] Try to reuse existing value during SCEV expansion
Current SCEV expansion will expand SCEV as a sequence of operations
and doesn't utilize the value already existed. This will introduce
redundent computation which may not be cleaned up throughly by
following optimizations.

This patch introduces an ExprValueMap which is a map from SCEV to the
set of equal values with the same SCEV. When a SCEV is expanded, the
set of values is checked and reused whenever possible before generating
a sequence of operations.

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



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@259662 91177308-0d34-0410-b5e6-96231b3b80d8
2016-02-03 17:05:12 +00:00
Chen Li
062e753253 [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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@258912 91177308-0d34-0410-b5e6-96231b3b80d8
2016-01-27 07:40:41 +00:00
Sanjoy Das
96068f9791 [SCEV] Fix PR26207
In some cases, the max backedge taken count can be more conservative
than the exact backedge taken count (for instance, because
ScalarEvolution::getRange is not control-flow sensitive whereas
computeExitLimitFromICmp can be).  In these cases,
computeExitLimitFromCond (specifically the bit that deals with `and` and
`or` instructions) can create an ExitLimit instance with a
`SCEVCouldNotCompute` max backedge count expression, but a computable
exact backedge count expression.  This violates an implicit SCEV
assumption: a computable exact BE count should imply a computable max BE
count.

This change

 - Makes the above implicit invariant explicit by adding an assert to
   ExitLimit's constructor

 - Changes `computeExitLimitFromCond` to be more robust around
   conservative max backedge counts

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@258184 91177308-0d34-0410-b5e6-96231b3b80d8
2016-01-19 20:53:51 +00:00
Sanjoy Das
26e7d2f8d6 [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`.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@258016 91177308-0d34-0410-b5e6-96231b3b80d8
2016-01-17 18:12:52 +00:00
Sanjoy Das
ca40161d4a [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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@254977 91177308-0d34-0410-b5e6-96231b3b80d8
2015-12-08 00:13:21 +00:00
Sanjoy Das
51d40aea3b [SCEVExpander] Have hoistIVInc preserve LCSSA
Summary:
(Note: the problematic invocation of hoistIVInc that caused PR24804 came
from IndVarSimplify, not from SCEVExpander itself)

Fixes PR24804.  Test case by David Majnemer.

Reviewers: hfinkel, majnemer, atrick, mzolotukhin

Subscribers: llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@254976 91177308-0d34-0410-b5e6-96231b3b80d8
2015-12-08 00:13:17 +00:00
Peter Collingbourne
5178bc957a ScalarEvolution: do not set nuw when creating exprs of form <expr> + <all-ones>.
The nuw constraint will not be satisfied unless <expr> == 0.

This bug has been around since r102234 (in 2010!), but was uncovered by
r251052, which introduced more aggressive optimization of nuw scev expressions.

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253627 91177308-0d34-0410-b5e6-96231b3b80d8
2015-11-20 01:26:13 +00:00
Sanjoy Das
edb273f9ae Re-apply r251050 with a for PR25421
The bug: I missed adding break statements in the switch / case.

Original commit message:

[SCEV] Teach SCEV some axioms about non-wrapping arithmetic

Summary:
 - A s<  (A + C)<nsw> if C >  0
 - A s<= (A + C)<nsw> if C >= 0
 - (A + C)<nsw> s<  A if C <  0
 - (A + C)<nsw> s<= A if C <= 0

Right now `C` needs to be a constant, but we can later generalize it to
be a non-constant if needed.

Reviewers: atrick, hfinkel, reames, nlewycky

Subscribers: sanjoy, llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@252236 91177308-0d34-0410-b5e6-96231b3b80d8
2015-11-05 23:45:38 +00:00
Richard Trieu
59970e6f52 Revert r251050 to fix miscompile when running Clang -O1
See bug for details: https://llvm.org/bugs/show_bug.cgi?id=25421
Some comparisons were incorrectly replaced with a constant value.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@252231 91177308-0d34-0410-b5e6-96231b3b80d8
2015-11-05 23:20:36 +00:00
Silviu Baranga
94652aba1f Fix PR25372 - teach replaceCongruentPHIs to handle cases where SE evaluates a PHI to a SCEVConstant
Summary:
Since now Scalar Evolution can create non-add rec expressions for PHI
nodes, it can also create SCEVConstant expressions. This will confuse
replaceCongruentPHIs, which previously relied on the fact that SCEV
could not produce constants in this case.

We will now replace the node with a constant in these cases - or avoid
processing the Phi in case of a type mismatch.

Reviewers: sanjoy

Subscribers: llvm-commits, majnemer

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251938 91177308-0d34-0410-b5e6-96231b3b80d8
2015-11-03 16:27:04 +00:00
Tobias Grosser
0efe7b620e 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.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251901 91177308-0d34-0410-b5e6-96231b3b80d8
2015-11-03 07:14:39 +00:00
Chen Li
fb81c7b828 [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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251839 91177308-0d34-0410-b5e6-96231b3b80d8
2015-11-02 22:00:15 +00:00
Sanjoy Das
2b19a08110 [SCEV] Don't create SCEV expressions that break LCSSA
Prevent `createNodeFromSelectLikePHI` from creating SCEV expressions
that break LCSSA.

A better fix for the same issue is to teach SCEVExpander to not break
LCSSA by inserting PHI nodes at appropriate places.  That's planned for
the future.

Fixes PR25360.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251756 91177308-0d34-0410-b5e6-96231b3b80d8
2015-10-31 23:21:40 +00:00
Chen Li
b63862ff47 Revert r251492 "[IndVarSimplify] Rewrite loop exit values with their
initial values from loop preheader", because it broke some bots.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251498 91177308-0d34-0410-b5e6-96231b3b80d8
2015-10-28 05:15:51 +00:00
Chen Li
0c46270ed3 [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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251492 91177308-0d34-0410-b5e6-96231b3b80d8
2015-10-28 04:45:47 +00:00
Sanjoy Das
221255160a [SCEV] Remove a test case added in r249168
The test case wasn't testing what it was commented to be testing; and
when I tried to fix the test I noticed that SCEV does not support the
simplification that the test was supposed to test.

This change removes the test case to avoid confusion.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251053 91177308-0d34-0410-b5e6-96231b3b80d8
2015-10-22 19:57:41 +00:00
Sanjoy Das
b9d057df5c [SCEV] Opportunistically interpret unsigned constraints as signed
Summary:
An unsigned comparision is equivalent to is corresponding signed version
if both the operands being compared are positive.  Teach SCEV to use
this fact when profitable.

Reviewers: atrick, hfinkel, reames, nlewycky

Subscribers: llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251051 91177308-0d34-0410-b5e6-96231b3b80d8
2015-10-22 19:57:34 +00:00
Sanjoy Das
47b5845e3b [SCEV] Teach SCEV some axioms about non-wrapping arithmetic
Summary:
 - A s<  (A + C)<nsw> if C >  0
 - A s<= (A + C)<nsw> if C >= 0
 - (A + C)<nsw> s<  A if C <  0
 - (A + C)<nsw> s<= A if C <= 0

Right now `C` needs to be a constant, but we can later generalize it to
be a non-constant if needed.

Reviewers: atrick, hfinkel, reames, nlewycky

Subscribers: sanjoy, llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251050 91177308-0d34-0410-b5e6-96231b3b80d8
2015-10-22 19:57:29 +00:00
Sanjoy Das
457377c0d4 [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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@250483 91177308-0d34-0410-b5e6-96231b3b80d8
2015-10-16 01:00:47 +00:00
Sanjoy Das
da2b817d1a [SCEV] Pick backedge values for phi nodes correctly
Summary:
`getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively`
assumed all phi nodes in the loop header have the same order of incoming
values.  This is not correct, and this commit changes
`getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively`
to lookup the backedge value of a phi node using the loop's latch block.

Unfortunately, there is still some code duplication
`getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively`.
At some point in the future we should extract out a helper class /
method that can evolve constant evolution phi nodes across iterations.

Fixes 25060.  Thanks to Mattias Eriksson for the spot-on analysis!

Depends on D13457.

Reviewers: atrick, hfinkel

Subscribers: materi, llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@249712 91177308-0d34-0410-b5e6-96231b3b80d8
2015-10-08 18:28:36 +00:00
Sanjoy Das
d23e55c402 [IndVars] Preserve LCSSA in eliminateIdentitySCEV
Summary:
After r249211, SCEV can see through some LCSSA phis.  Add a
`replacementPreservesLCSSAForm` check before replacing uses of these phi
nodes with a simplified use of the induction variable to avoid breaking
LCSSA.

Fixes 25047.

Depends on D13460.

Reviewers: atrick, hfinkel

Subscribers: llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@249575 91177308-0d34-0410-b5e6-96231b3b80d8
2015-10-07 17:38:31 +00:00
Sanjoy Das
d15cdb7b13 [IndVars] Don't break dominance in eliminateIdentitySCEV
Summary:
After r249211, `getSCEV(X) == getSCEV(Y)` does not guarantee that X and
Y are related in the dominator tree, even if X is an operand to Y (I've
included a toy example in comments, and a real example as a test case).

This commit changes `SimplifyIndVar` to require a `DominatorTree`.  I
don't think this is a problem because `ScalarEvolution` requires it
anyway.

Fixes PR25051.

Depends on D13459.

Reviewers: atrick, hfinkel

Subscribers: joker.eph, llvm-commits, sanjoy

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@249471 91177308-0d34-0410-b5e6-96231b3b80d8
2015-10-06 21:44:49 +00:00
Sanjoy Das
8c0c4322dd [SCEV] Try to prove predicates by splitting them
Summary:
This change teaches SCEV that to prove `A u< B` it is sufficient to
prove each of these facts individually:

 - B >= 0
 - A s< B
 - A >= 0

In practice, SCEV sometimes finds it easier to prove these facts
individually than to prove `A u< B` as one atomic step.

Reviewers: reames, atrick, nlewycky, hfinkel

Subscribers: sanjoy, llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@249168 91177308-0d34-0410-b5e6-96231b3b80d8
2015-10-02 18:50:30 +00:00