summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Revert -r278269 [IndVarSimplify] Eliminate zext of a signed IV when the IV ↵Artur Pilipenko2016-08-221-7/+2
| | | | | | | | | | 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
* Scalar: Avoid dereferencing end() in IndVarSimplifyDuncan P. N. Exon Smith2016-08-171-3/+3
| | | | | | | | | 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
* [IndVars] Ignore (s|z)exts that don't extend the induction variableSanjoy Das2016-08-131-0/+8
| | | | | | | | | | | | | | | | | | `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
* Extend trip count instead of truncating IV in LFTR, when legalEhsan Amiri2016-08-111-0/+27
| | | | | | | | | | | | | | | | | 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
* revert 278334Ehsan Amiri2016-08-111-27/+0
| | | | llvm-svn: 278337
* Extend trip count instead of truncating IV in LFTR, when legalEhsan Amiri2016-08-111-2/+30
| | | | | | | | | | | | | | | 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
* [IndVarSimplify] Eliminate zext of a signed IV when the IV is known to be ↵Andrew Kaylor2016-08-101-2/+7
| | | | | | | | | | 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 ↵Wei Mi2016-08-091-1/+1
| | | | | | | | | | | | | | 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
* Consistently use LoopAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | | | | | | | 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
* [IndVars] Reflow oddly formatted condition; NFCSanjoy Das2016-07-211-2/+2
| | | | llvm-svn: 276319
* [PM] Normalize FIXMEs for missing PreserveCFG to have the same wording.Michael Kuperstein2016-06-281-2/+1
| | | | llvm-svn: 273974
* [IndVarSimplify] Run clang-format over some oddly formatted bitsSanjoy Das2016-06-241-16/+15
| | | | | | NFC (whitespace only change) llvm-svn: 273732
* [PM] Port IndVarSimplify to the new pass managerSanjoy Das2016-06-051-0/+27
| | | | | | | | | | | | | | | | | 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
* [IndVars] Remove -liv-reduceSanjoy Das2016-06-051-5/+0
| | | | | | | | | | 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
* [IndVars] Assert that the incoming IR is in LCSSASanjoy Das2016-05-301-0/+3
| | | | | | | | | | | 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
* [IndVarSimplify] Extract the logic of `-indvars` out into a class; NFCSanjoy Das2016-05-291-51/+57
| | | | | | 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 ↵Andrew Kaylor2016-04-221-1/+1
| | | | | | | | | | 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
* Revert "Initial implementation of optimization bisect support."Vedant Kumar2016-04-221-1/+1
| | | | | | | | 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
* Initial implementation of optimization bisect support.Andrew Kaylor2016-04-211-1/+1
| | | | | | | | | | | | 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
* [NFC] Header cleanupMehdi Amini2016-04-181-1/+0
| | | | | | | | | | | | | | 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
* [IndVarSimplify] Don't insert after a catchswitchDavid Majnemer2016-03-301-0/+6
| | | | | | | | | | 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
* [LPM] Factor all of the loop analysis usage updates into a common helperChandler Carruth2016-02-191-14/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [IndVars] Hoist DataLayout load out of loop; NFCSanjoy Das2016-01-271-2/+2
| | | | llvm-svn: 258946
* [IndVars] Use isSCEVable; NFCSanjoy Das2016-01-271-2/+1
| | | | llvm-svn: 258945
* [IndVars] Use range-for; NFCSanjoy Das2016-01-271-3/+1
| | | | llvm-svn: 258944
* [IndVarSimplify] Rewrite loop exit values with their initial values from ↵Chen Li2016-01-271-0/+80
| | | | | | | | | | | | | | | | | | | | | | 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
* [IndVars] Fix PR25576Sanjoy Das2016-01-171-23/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | `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
* [IndVars] Use emplace_back; NFCSanjoy Das2016-01-171-4/+3
| | | | llvm-svn: 258015
* [SCEV] Add and use SCEVConstant::getAPInt; NFCISanjoy Das2015-12-171-2/+2
| | | | llvm-svn: 255921
* LPM: Stop threading `Pass *` through all of the loop utility APIs. NFCJustin Bogner2015-12-151-4/+4
| | | | | | | | | | | | | | | | | | | | | | 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
* [IndVars] Use any_of and foreach instead of explicit for loops; NFCSanjoy Das2015-12-081-11/+6
| | | | llvm-svn: 255077
* [IndVars] Have getInsertPointForUses preserve LCSSASanjoy Das2015-12-081-14/+28
| | | | | | | | | | | | | | | 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
* use convenience function for copying IR flags; NFCISanjay Patel2015-11-241-12/+2
| | | | llvm-svn: 253996
* Revert "[IndVarSimplify] Rewrite loop exit values with their initial values ↵Tobias Grosser2015-11-031-73/+0
| | | | | | | | | | | | | | | | | | | 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
* [IndVarSimplify] Rewrite loop exit values with their initial values from ↵Chen Li2015-11-021-0/+73
| | | | | | | | | | | | | | | | | 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
* Revert r251492 "[IndVarSimplify] Rewrite loop exit values with their Chen Li2015-10-281-71/+0
| | | | | | initial values from loop preheader", because it broke some bots. llvm-svn: 251498
* [IndVarSimplify] Rewrite loop exit values with their initial values from ↵Chen Li2015-10-281-0/+71
| | | | | | | | | | | | | | | | | 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
* [IndVars] Rename getExtend; NFCSanjoy Das2015-10-161-17/+17
| | | | | | | Rename `IndVarSimplify::getExtend` to `IndVarSimplify::createExtendInst` to make it obvious that it creates `llvm::Instruction` s. llvm-svn: 250484
* [IndVars] Have `cloneArithmeticIVUser` guess betterSanjoy Das2015-10-161-12/+74
| | | | | | | | | | | | | | | | | | | | | 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
* [IndVars] Extract out a few local variables; NFCSanjoy Das2015-10-161-24/+32
| | | | llvm-svn: 250482
* [IndVars] Split `WidenIV::cloneIVUser`; NFCSanjoy Das2015-10-161-25/+71
| | | | | | | | | | | | | | | 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
* Scalar: Remove some implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-10-131-6/+6
| | | | | | | Remove some of the implicit ilist iterator conversions in LLVMScalarOpts. More to go. llvm-svn: 250197
* [IndVars] NFC Cleanup.Sanjoy Das2015-10-131-66/+62
| | | | | | | | - Rename methods according to the LLVM Coding Style - Merge adjacent anonymous namespace block - Use `auto` in two places llvm-svn: 250152
* [IndVars] Use `auto`; NFCSanjoy Das2015-10-101-6/+4
| | | | llvm-svn: 249944
* [IndVars] Don't break dominance in `eliminateIdentitySCEV`Sanjoy Das2015-10-061-1/+1
| | | | | | | | | | | | | | | | | | | | | | | 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 llvm-svn: 249471
* [SCEV] Introduce ScalarEvolution::getOne and getZero.Sanjoy Das2015-09-231-1/+1
| | | | | | | | | | | | | | | | | | Summary: It is fairly common to call SE->getConstant(Ty, 0) or SE->getConstant(Ty, 1); this change makes such uses a little bit briefer. I've refactored the call sites I could find easily to use getZero / getOne. Reviewers: hfinkel, majnemer, reames Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12947 llvm-svn: 248362
* [IndVars] Use C++11 style field initialization; NFCI.Sanjoy Das2015-09-201-14/+7
| | | | llvm-svn: 248131
* [IndVars] Don't add a level of indentation for namespace {. NFC.Sanjoy Das2015-09-201-77/+77
| | | | | | Whitespace-only change. llvm-svn: 248130
* [IndVars] Don't repeat function names in comment; NFC.Sanjoy Das2015-09-201-65/+62
| | | | | | Only changes comments. llvm-svn: 248112
* [IndVars] Fix a bug in r248045.Sanjoy Das2015-09-201-14/+19
| | | | | | | | | | | | | | Because -indvars widens induction variables through arithmetic, `NeverNegative` cannot be a property of the `WidenIV` (a `WidenIV` manages information for all transitive uses of an IV being widened, including uses of `-1 * IV`). Instead it must live on `NarrowIVDefUse` which manages information for a specific def-use edge in the transitive use list of an induction variable. This change also adds a test case that demonstrates the problem with r248045. llvm-svn: 248107
OpenPOWER on IntegriCloud