summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-151-25/+26
| | | | | | instead of comparing to nullptr. llvm-svn: 206243
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-4/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* [C++11] Convert sort predicates into lambdas.Benjamin Kramer2014-03-071-10/+7
| | | | | | No functionality change. llvm-svn: 203288
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-2/+2
| | | | | | Remove the old functions. llvm-svn: 202636
* Rename some member variables from TD to DL.Rafael Espindola2014-02-181-10/+10
| | | | | | TargetData was renamed DataLayout back in r165242. llvm-svn: 201581
* SCEVExpander: Try hard not to create derived induction variables in other loopsArnold Schwaighofer2014-02-161-25/+136
| | | | | | | | | | | | | | | | | | | During LSR of one loop we can run into a situation where we have to expand the start of a recurrence of a loop induction variable in this loop. This start value is a value derived of the induction variable of a preceeding loop. SCEV has cannonicalized this value to a different recurrence than the recurrence of the preceeding loop's induction variable (the type and/or step direction) has changed). When we come to instantiate this SCEV we created a second induction variable in this preceeding loop. This patch tries to base such derived induction variables of the preceeding loop's induction variable. This helps twolf on arm and seems to help scimark2 on x86. Reapply with a fix for the case of a value derived from a pointer. radar://15970709 llvm-svn: 201496
* Revert "SCEVExpander: Try hard not to create derived induction variables in ↵Arnold Schwaighofer2014-02-151-127/+25
| | | | | | | | other loops" This reverts commit r201465. It broke an arm bot. llvm-svn: 201466
* SCEVExpander: Try hard not to create derived induction variables in other loopsArnold Schwaighofer2014-02-151-25/+127
| | | | | | | | | | | | | | | | | During LSR of one loop we can run into a situation where we have to expand the start of a recurrence of a loop induction variable in this loop. This start value is a value derived of the induction variable of a preceeding loop. SCEV has cannonicalized this value to a different recurrence than the recurrence of the preceeding loop's induction variable (the type and/or step direction) has changed). When we come to instantiate this SCEV we created a second induction variable in this preceeding loop. This patch tries to base such derived induction variables of the preceeding loop's induction variable. This helps twolf on arm and seems to help scimark2 on x86. radar://15970709 llvm-svn: 201465
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-131-1/+1
| | | | | | | | | | | | | | | | | | directory. These passes are already defined in the IR library, and it doesn't make any sense to have the headers in Analysis. Long term, I think there is going to be a much better way to divide these matters. The dominators code should be fully separated into the abstract graph algorithm and have that put in Support where it becomes obvious that evn Clang's CFGBlock's can use it. Then the verifier can manually construct dominance information from the Support-driven interface while the Analysis library can provide a pass which both caches, reconstructs, and supports a nice update API. But those are very long term, and so I don't want to leave the really confusing structure until that day arrives. llvm-svn: 199082
* Re-sort all of the includes with ./utils/sort_includes.py so thatChandler Carruth2014-01-071-1/+1
| | | | | | | | | | subsequent changes are easier to review. About to fix some layering issues, and wanted to separate out the necessary churn. Also comment and sink the include of "Windows.h" in three .inc files to match the usage in Memory.inc. llvm-svn: 198685
* Don't #include heavy Dominators.h file in LoopInfo.h. This change reducesJakub Staszak2013-12-071-0/+1
| | | | | | overall time of LLVM compilation by ~1%. llvm-svn: 196667
* Correct word hyphenationsAlp Toker2013-12-051-1/+1
| | | | | | | This patch tries to avoid unrelated changes other than fixing a few hyphen-related ambiguities and contractions in nearby lines. llvm-svn: 196471
* Fix SCEVExpander: don't try to expand quadratic recurrences outside a loop.Andrew Trick2013-10-251-11/+27
| | | | | | | | | | | | Partial fix for PR17459: wrong code at -O3 on x86_64-linux-gnu (affecting trunk and 3.3) When SCEV expands a recurrence outside of a loop it attempts to scale by the stride of the recurrence. Chained recurrences don't work that way. We could compute binomial coefficients, but would hve to guarantee that the chained AddRec's are in a perfectly reduced form. llvm-svn: 193438
* SCEVExpander: Fix a regression I introduced by to eagerly adding RAII objects.Benjamin Kramer2013-10-011-1/+4
| | | | | | PR17425. llvm-svn: 191741
* Convert manual insert point restores to the new RAII object.Benjamin Kramer2013-09-301-47/+15
| | | | llvm-svn: 191675
* Teach ScalarEvolution about pointer address spacesMatt Arsenault2013-09-101-1/+5
| | | | llvm-svn: 190425
* Fix SCEVExpander creating distinct duplicate PHI entriesHal Finkel2013-08-181-0/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | This fixes SCEVExpander so that it does not create multiple distinct induction variables for duplicate PHI entries. Specifically, given some code like this: do.body6: ; preds = %do.body6, %do.body6, %if.then5 %end.0 = phi i8* [ undef, %if.then5 ], [ %incdec.ptr, %do.body6 ], [ %incdec.ptr, %do.body6 ] ... Note that it is legal to have multiple entries for a basic block so long as the associated value is the same. So the above input is okay, but expanding an AddRec in this loop could produce code like this: do.body6: ; preds = %do.body6, %do.body6, %if.then5 %indvar = phi i64 [ %indvar.next, %do.body6 ], [ %indvar.next1, %do.body6 ], [ 0, %if.then5 ] %end.0 = phi i8* [ undef, %if.then5 ], [ %incdec.ptr, %do.body6 ], [ %incdec.ptr, %do.body6 ] ... %indvar.next = add i64 %indvar, 1 %indvar.next1 = add i64 %indvar, 1 And this is not legal because there are two PHI entries for %do.body6 each with a distinct value. Unfortunately, I don't have an in-tree test case. llvm-svn: 188614
* Remove a bunch of old SCEVExpander FIXME's for preserving NoWrap.Andrew Trick2013-07-141-17/+11
| | | | | | | | | | | | | | | The great thing about the SCEVAddRec No-Wrap flag (unlike nsw/nuw) is that is can be preserved while normalizing (reassociating and factoring). The bad thing is that is can't be tranfered back to IR, which is one of the reasons I don't like the concept of SCEVExpander. Sorry, I can't think of a direct way to test this, which is why these were FIXMEs for so long. I just think it's a good time to finally clean it up. llvm-svn: 186273
* Teach indvars to generate nsw/nuw flags when widening an induction variable.Andrew Trick2013-07-141-1/+6
| | | | | | Fixes PR16600. llvm-svn: 186272
* SCEVExpander fix. RAUW needs to update the InsertedExpressions cache.Andrew Trick2013-01-141-3/+2
| | | | | | | | Note that this bug is only exposed because LTO fails to use TTI. Fixes self-LTO of clang. rdar://13007381. llvm-svn: 172462
* Switch the SCEV expander and LoopStrengthReduce to useChandler Carruth2013-01-071-5/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | TargetTransformInfo rather than TargetLowering, removing one of the primary instances of the layering violation of Transforms depending directly on Target. This is a really big deal because LSR used to be a "special" pass that could only be tested fully using llc and by looking at the full output of it. It also couldn't run with any other loop passes because it had to be created by the backend. No longer is this true. LSR is now just a normal pass and we should probably lift the creation of LSR out of lib/CodeGen/Passes.cpp and into the PassManagerBuilder. =] I've not done this, or updated all of the tests to use opt and a triple, because I suspect someone more familiar with LSR would do a better job. This change should be essentially without functional impact for normal compilations, and only change behvaior of targetless compilations. The conversion required changing all of the LSR code to refer to the TTI interfaces, which fortunately are very similar to TargetLowering's interfaces. However, it also allowed us to *always* expect to have some implementation around. I've pushed that simplification through the pass, and leveraged it to simplify code somewhat. It required some test updates for one of two things: either we used to skip some checks altogether but now we get the default "no" answer for them, or we used to have no information about the target and now we do have some. I've also started the process of removing AddrMode, as the TTI interface doesn't use it any longer. In some cases this simplifies code, and in others it adds some complexity, but I think it's not a bad tradeoff even there. Subsequent patches will try to clean this up even further and use other (more appropriate) abstractions. Yet again, almost all of the formatting changes brought to you by clang-format. =] llvm-svn: 171735
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-3/+3
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-2/+2
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Revert the series of commits starting with r166578 which introduced theChandler Carruth2012-11-011-3/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | getIntPtrType support for multiple address spaces via a pointer type, and also introduced a crasher bug in the constant folder reported in PR14233. These commits also contained several problems that should really be addressed before they are re-committed. I have avoided reverting various cleanups to the DataLayout APIs that are reasonable to have moving forward in order to reduce the amount of churn, and minimize the number of commits that were reverted. I've also manually updated merge conflicts and manually arranged for the getIntPtrType function to stay in DataLayout and to be defined in a plausible way after this revert. Thanks to Duncan for working through this exact strategy with me, and Nick Lewycky for tracking down the really annoying crasher this triggered. (Test case to follow in its own commit.) After discussing with Duncan extensively, and based on a note from Micah, I'm going to continue to back out some more of the more problematic patches in this series in order to ensure we go into the LLVM 3.2 branch with a reasonable story here. I'll send a note to llvmdev explaining what's going on and why. Summary of reverted revisions: r166634: Fix a compiler warning with an unused variable. r166607: Add some cleanup to the DataLayout changes requested by Chandler. r166596: Revert "Back out r166591, not sure why this made it through since I cancelled the command. Bleh, sorry about this! r166591: Delete a directory that wasn't supposed to be checked in yet. r166578: Add in support for getIntPtrType to get the pointer type based on the address space. llvm-svn: 167221
* Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow2012-10-241-1/+3
| | | | | | | | | address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. llvm-svn: 166578
* revert r166264 because the LTO build is still failingNadav Rotem2012-10-191-6/+6
| | | | llvm-svn: 166340
* SCEVExpander: Don't crash when trying to merge two constant phis.Benjamin Kramer2012-10-191-0/+11
| | | | | | Just constant fold them so they can't cause any trouble. Fixes PR12627. llvm-svn: 166286
* recommit the patch that makes LSR and LowerInvoke use the TargetTransform ↵Nadav Rotem2012-10-191-6/+6
| | | | | | interface. llvm-svn: 166264
* Temporarily revert the TargetTransform changes.Bob Wilson2012-10-181-6/+6
| | | | | | | | | | | The TargetTransform changes are breaking LTO bootstraps of clang. I am working with Nadav to figure out the problem, but I am reverting it for now to get our buildbots working. This reverts svn commits: 165665 165669 165670 165786 165787 165997 and I have also reverted clang svn 165741 llvm-svn: 166168
* Add a new interface to allow IR-level passes to access codegen-specific ↵Nadav Rotem2012-10-101-6/+6
| | | | | | information. llvm-svn: 165665
* Move TargetData to DataLayout.Micah Villmow2012-10-081-6/+6
| | | | llvm-svn: 165402
* Fix a typo (the the => the)Sylvestre Ledru2012-07-231-1/+1
| | | | llvm-svn: 160621
* LSR Fix: check SCEV expression safety before expansion.Andrew Trick2012-07-131-0/+41
| | | | | | | | | | All SCEV expressions used by LSR formulae must be safe to expand. i.e. they may not contain UDiv unless we can prove nonzero denominator. Fixes PR11356: LSR hoists UDiv. llvm-svn: 160205
* LSR fix: add a missing phi check during IV hoisting.Andrew Trick2012-05-221-1/+2
| | | | | | Fixes PR12898: SCEVExpander crash. llvm-svn: 157263
* Fix this assert. IP can point to an instruction with strange dominanceRafael Espindola2012-02-271-15/+20
| | | | | | | properties (invoke). Just assert that the instruction we return dominates the insertion point. llvm-svn: 151511
* And update the comment...Rafael Espindola2012-02-261-1/+0
| | | | llvm-svn: 151472
* Enable the assert that got all this dominator work started.Rafael Espindola2012-02-261-1/+1
| | | | llvm-svn: 151471
* Change the implementation of dominates(inst, inst) to one based on what theRafael Espindola2012-02-261-6/+5
| | | | | | | | verifier does. This correctly handles invoke. Thanks to Duncan, Andrew and Chris for the comments. Thanks to Joerg for the early testing. llvm-svn: 151469
* Fix typo.Rafael Espindola2012-02-231-1/+1
| | | | llvm-svn: 151238
* Improve comment. Thanks for Andrew for the suggestion.Rafael Espindola2012-02-221-2/+3
| | | | llvm-svn: 151127
* Semantically revert 151015. Add a comment on why we should be able to assertRafael Espindola2012-02-221-7/+17
| | | | | | | | the dominance once the dominates method is fixed and why we can use the builder's insertion point. Fixes pr12048. llvm-svn: 151125
* s/the the/the/Rafael Espindola2012-02-211-1/+1
| | | | llvm-svn: 151079
* Use more idiomatic assert.Rafael Espindola2012-02-211-2/+2
| | | | llvm-svn: 151026
* Avoid warning on non assert builds.Rafael Espindola2012-02-211-2/+3
| | | | llvm-svn: 151025
* It turns out that with the current scev organization ReuseOrCreateCast cannotRafael Espindola2012-02-211-9/+9
| | | | | | | | | | | | | | know where users will be added. Because of this, it cannot use Builder.GetInsertPoint at all. This patch * removes the FIXME about adding the assert. * adds a comment explaining hy we don't have one. * removes a broken logic that only works for some callers and is not needed since r150884. * adds an assert to caller that would have caught the bug fixed by r150884. llvm-svn: 151015
* Temporarily disable this assert. Looks like it found a similar issue whenRafael Espindola2012-02-181-1/+3
| | | | | | building bullet. llvm-svn: 150885
* Don't skip debug instructions when looking for the insertion point ofRafael Espindola2012-02-181-5/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | the cast. If we do, we can end up with inst1 --------------- < Insertion point dbg inst new inst instead of the desired inst1 new inst --------------- < Insertion point dbg inst Another option would be for InsertNoopCastOfTo (or its callers) to move the insertion point and we would end up with inst1 dbg inst new inst --------------- < Insertion point but that complicates the callers. This fixes PR12018 (and firefox's build). llvm-svn: 150884
* More dead code removal (using -Wunreachable-code)David Blaikie2012-01-201-1/+0
| | | | llvm-svn: 148578
* SCEVExpander fixes. Affects LSR and indvars.Andrew Trick2012-01-201-115/+114
| | | | | | | | | | | | | | | | LSR has gradually been improved to more aggressively reuse existing code, particularly existing phi cycles. This exposed problems with the SCEVExpander's sloppy treatment of its insertion point. I applied some rigor to the insertion point problem that will hopefully avoid an endless bug cycle in this area. Changes: - Always used properlyDominates to check safe code hoisting. - The insertion point provided to SCEV is now considered a lower bound. This is usually a block terminator or the use itself. Under no cirumstance may SCEVExpander insert below this point. - LSR is reponsible for finding a "canonical" insertion point across expansion of different expressions. - Robust logic to determine whether IV increments are in "expanded" form and/or can be safely hoisted above some insertion point. Fixes PR11783: SCEVExpander assert. llvm-svn: 148535
* Fix a corner case hit by redundant phi elimination running after LSR.Andrew Trick2012-01-141-1/+11
| | | | | | Fixes PR11761: bad IR w/ redundant Phi elim llvm-svn: 148177
OpenPOWER on IntegriCloud