summaryrefslogtreecommitdiff
path: root/lib/Analysis/ScalarEvolutionExpander.cpp
Commit message (Collapse)AuthorAge
* SCEVExpander: Fold constant PHIs harder. The logic below only understands ↵Benjamin Kramer2014-06-21
| | | | | | | | proper IVs. PR20093. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211433 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-15
| | | | | | instead of comparing to nullptr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206243 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-09
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@203364 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Convert sort predicates into lambdas.Benjamin Kramer2014-03-07
| | | | | | No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@203288 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-02
| | | | | | Remove the old functions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202636 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename some member variables from TD to DL.Rafael Espindola2014-02-18
| | | | | | TargetData was renamed DataLayout back in r165242. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201581 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVExpander: Try hard not to create derived induction variables in other loopsArnold Schwaighofer2014-02-16
| | | | | | | | | | | | | | | | | | | 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201496 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "SCEVExpander: Try hard not to create derived induction variables in ↵Arnold Schwaighofer2014-02-15
| | | | | | | | other loops" This reverts commit r201465. It broke an arm bot. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201466 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVExpander: Try hard not to create derived induction variables in other loopsArnold Schwaighofer2014-02-15
| | | | | | | | | | | | | | | | | 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201465 91177308-0d34-0410-b5e6-96231b3b80d8
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-13
| | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@199082 91177308-0d34-0410-b5e6-96231b3b80d8
* Re-sort all of the includes with ./utils/sort_includes.py so thatChandler Carruth2014-01-07
| | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@198685 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't #include heavy Dominators.h file in LoopInfo.h. This change reducesJakub Staszak2013-12-07
| | | | | | | overall time of LLVM compilation by ~1%. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@196667 91177308-0d34-0410-b5e6-96231b3b80d8
* Correct word hyphenationsAlp Toker2013-12-05
| | | | | | | This patch tries to avoid unrelated changes other than fixing a few hyphen-related ambiguities and contractions in nearby lines. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@196471 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix SCEVExpander: don't try to expand quadratic recurrences outside a loop.Andrew Trick2013-10-25
| | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193438 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVExpander: Fix a regression I introduced by to eagerly adding RAII objects.Benjamin Kramer2013-10-01
| | | | | | PR17425. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191741 91177308-0d34-0410-b5e6-96231b3b80d8
* Convert manual insert point restores to the new RAII object.Benjamin Kramer2013-09-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191675 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach ScalarEvolution about pointer address spacesMatt Arsenault2013-09-10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190425 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix SCEVExpander creating distinct duplicate PHI entriesHal Finkel2013-08-18
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188614 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove a bunch of old SCEVExpander FIXME's for preserving NoWrap.Andrew Trick2013-07-14
| | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186273 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach indvars to generate nsw/nuw flags when widening an induction variable.Andrew Trick2013-07-14
| | | | | | Fixes PR16600. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186272 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVExpander fix. RAUW needs to update the InsertedExpressions cache.Andrew Trick2013-01-14
| | | | | | | | Note that this bug is only exposed because LTO fails to use TTI. Fixes self-LTO of clang. rdar://13007381. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172462 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch the SCEV expander and LoopStrengthReduce to useChandler Carruth2013-01-07
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171735 91177308-0d34-0410-b5e6-96231b3b80d8
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-02
| | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171366 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-03
| | | | | | | | | | | | | | | | | 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. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert the series of commits starting with r166578 which introduced theChandler Carruth2012-11-01
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167221 91177308-0d34-0410-b5e6-96231b3b80d8
* Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow2012-10-24
| | | | | | | | | | address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166578 91177308-0d34-0410-b5e6-96231b3b80d8
* revert r166264 because the LTO build is still failingNadav Rotem2012-10-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166340 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVExpander: Don't crash when trying to merge two constant phis.Benjamin Kramer2012-10-19
| | | | | | Just constant fold them so they can't cause any trouble. Fixes PR12627. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166286 91177308-0d34-0410-b5e6-96231b3b80d8
* recommit the patch that makes LSR and LowerInvoke use the TargetTransform ↵Nadav Rotem2012-10-19
| | | | | | interface. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166264 91177308-0d34-0410-b5e6-96231b3b80d8
* Temporarily revert the TargetTransform changes.Bob Wilson2012-10-18
| | | | | | | | | | | 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166168 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a new interface to allow IR-level passes to access codegen-specific ↵Nadav Rotem2012-10-10
| | | | | | information. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165665 91177308-0d34-0410-b5e6-96231b3b80d8
* Move TargetData to DataLayout.Micah Villmow2012-10-08
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165402 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a typo (the the => the)Sylvestre Ledru2012-07-23
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160621 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR Fix: check SCEV expression safety before expansion.Andrew Trick2012-07-13
| | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160205 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR fix: add a missing phi check during IV hoisting.Andrew Trick2012-05-22
| | | | | | Fixes PR12898: SCEVExpander crash. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157263 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix this assert. IP can point to an instruction with strange dominanceRafael Espindola2012-02-27
| | | | | | | properties (invoke). Just assert that the instruction we return dominates the insertion point. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151511 91177308-0d34-0410-b5e6-96231b3b80d8
* And update the comment...Rafael Espindola2012-02-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151472 91177308-0d34-0410-b5e6-96231b3b80d8
* Enable the assert that got all this dominator work started.Rafael Espindola2012-02-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151471 91177308-0d34-0410-b5e6-96231b3b80d8
* Change the implementation of dominates(inst, inst) to one based on what theRafael Espindola2012-02-26
| | | | | | | | verifier does. This correctly handles invoke. Thanks to Duncan, Andrew and Chris for the comments. Thanks to Joerg for the early testing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151469 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix typo.Rafael Espindola2012-02-23
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151238 91177308-0d34-0410-b5e6-96231b3b80d8
* Improve comment. Thanks for Andrew for the suggestion.Rafael Espindola2012-02-22
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151127 91177308-0d34-0410-b5e6-96231b3b80d8
* Semantically revert 151015. Add a comment on why we should be able to assertRafael Espindola2012-02-22
| | | | | | | | the dominance once the dominates method is fixed and why we can use the builder's insertion point. Fixes pr12048. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151125 91177308-0d34-0410-b5e6-96231b3b80d8
* s/the the/the/Rafael Espindola2012-02-21
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151079 91177308-0d34-0410-b5e6-96231b3b80d8
* Use more idiomatic assert.Rafael Espindola2012-02-21
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151026 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid warning on non assert builds.Rafael Espindola2012-02-21
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151025 91177308-0d34-0410-b5e6-96231b3b80d8
* It turns out that with the current scev organization ReuseOrCreateCast cannotRafael Espindola2012-02-21
| | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151015 91177308-0d34-0410-b5e6-96231b3b80d8
* Temporarily disable this assert. Looks like it found a similar issue whenRafael Espindola2012-02-18
| | | | | | building bullet. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150885 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't skip debug instructions when looking for the insertion point ofRafael Espindola2012-02-18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150884 91177308-0d34-0410-b5e6-96231b3b80d8
* More dead code removal (using -Wunreachable-code)David Blaikie2012-01-20
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148578 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVExpander fixes. Affects LSR and indvars.Andrew Trick2012-01-20
| | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148535 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-14 01:43:15 +0000