summaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Commit message (Collapse)AuthorAge
* Merging r202273:Tom Stellard2014-04-08
| | | | | | | | | | | | | ------------------------------------------------------------------------ r202273 | atrick | 2014-02-26 11:31:56 -0500 (Wed, 26 Feb 2014) | 4 lines Fix PR18165: LSR must avoid scaling factors that exceed the limit on truncated use. Patch by Michael Zolotukhin! ------------------------------------------------------------------------ git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_34@205796 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
* LSR: Fix the parameters used to compute the scaling factor cost.Quentin Colombet2013-06-19
| | | | | | | | | | | | | | Prior to this change, the considered addressing modes may be invalid since the maximum and minimum offsets were not taking into account. This was causing an assertion failure. The added test case exercices that behavior. <rdar://problem/14199725> Assertion failed: (CurScaleCost >= 0 && "Legal addressing mode has an illegal cost!") git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@184341 91177308-0d34-0410-b5e6-96231b3b80d8
* Use 0 instead of NULL.Jakub Staszak2013-06-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@184044 91177308-0d34-0410-b5e6-96231b3b80d8
* Loop Strength Reduce: Scaling factor cost.Quentin Colombet2013-05-31
| | | | | | | | | | | | | Account for the cost of scaling factor in Loop Strength Reduce when rating the formulae. This uses a target hook. The default implementation of the hook is: if the addressing mode is legal, the scaling factor is free. <rdar://problem/13806271> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@183045 91177308-0d34-0410-b5e6-96231b3b80d8
* Modify how the formulae are rated in Loop Strength Reduce.Quentin Colombet2013-05-31
| | | | | | | | | | | | | | | Namely, check if the target allows to fold more that one register in the addressing mode and if yes, adjust the cost accordingly. Prior to this commit, reg1 + scale * reg2 accesses were artificially preferred to reg1 + reg2 accesses. Indeed, the cost model wrongly assumed that reg1 + reg2 needs a temporary register for the computation, whereas it was correctly estimated for reg1 + scale * reg2. <rdar://problem/13973908> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@183021 91177308-0d34-0410-b5e6-96231b3b80d8
* Replace Count{Leading,Trailing}Zeros_{32,64} with count{Leading,Trailing}Zeros.Michael J. Spencer2013-05-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@182680 91177308-0d34-0410-b5e6-96231b3b80d8
* Use dyn_cast instead of isa && cast.Jakub Staszak2013-03-24
| | | | | | | No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@177836 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "Cleanup some SCEV logic a bit."Andrew Trick2013-03-19
| | | | | | | | This reverts commit 82cd8f7382322bee7a71cdc31f7a923c44d37d32. Just add a comment instead! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@177377 91177308-0d34-0410-b5e6-96231b3b80d8
* Cleanup some SCEV logic a bit.Andrew Trick2013-03-19
| | | | | | Make the code more obvious to scan-build and humans. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@177375 91177308-0d34-0410-b5e6-96231b3b80d8
* Tighten up an internal LSR API that should check for NULL.Andrew Trick2013-03-19
| | | | | | No test case, but should fix a scan_build warning. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@177374 91177308-0d34-0410-b5e6-96231b3b80d8
* Reduce indents in LSRInstance::NarrowSearchSpaceByCollapsingUnrolledCode method.Jakub Staszak2013-02-16
| | | | | | | No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175364 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR IVChain improvement.Andrew Trick2013-02-09
| | | | | | | | | Handle chains in which the same offset is used for both loads and stores to the same array. Fixes rdar://11410078. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174789 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove #includes from the commonly used LoopInfo.h.Jakub Staszak2013-02-09
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174786 91177308-0d34-0410-b5e6-96231b3b80d8
* This patch aims to improve compile time performance by increasingPreston Gurd2013-02-01
| | | | | | | | | | | | | | | | the SCEV vector size in LoopStrengthReduce. It is observed that the BaseRegs vector size is 4 in most cases, and elements are frequently copied when it is initialized as SmallVector<const SCEV *, 2> BaseRegs. Our benchmark results show that the compilation time performance improved by ~0.5%. Patch by Wan Xiaofei. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174219 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix an editor goof in r171738 that Bill spotted. He may even have a testChandler Carruth2013-01-12
| | | | | | | | case, but looking at the diff this was an obviously unintended change. Thanks for the careful review Bill! =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172336 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove LSR's use of the random AddrMode struct. These variables wereChandler Carruth2013-01-07
| | | | | | | | | | | | already in a class, just inline the four of them. I suspect that this class could be simplified some to not always keep distinct variables for these things, but it wasn't clear to me how given the usage so I opted for a trivial and mechanical translation. This removes one of the two remaining users of a header in include/llvm which does nothing more than define a 4 member struct. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171738 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
* Fix a crash in LSR replaceCongruentIVs.Andrew Trick2013-01-06
| | | | | | | Indirect branch in the preheader crashes replaceCongruentIVs. Fixes rdar://12910141. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171653 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 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
* 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
* Refactor the AddrMode class out of TLI to its own header file.Nadav Rotem2012-10-08
| | | | | | | | | | This class is used by LSR and a number of places in the codegen. This is the first step in de-coupling LSR from TLI, and creating a new interface in between them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165455 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR critical edge splitting fix for PR13756.Andrew Trick2012-09-18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164147 91177308-0d34-0410-b5e6-96231b3b80d8
* Release build: guard dump functions withManman Ren2012-09-12
| | | | | | | | | "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163344. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163679 91177308-0d34-0410-b5e6-96231b3b80d8
* Release build: guard dump functions with "ifndef NDEBUG"Manman Ren2012-09-06
| | | | | | | No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163344 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't bind a reference to a dereferenced null pointer (for return value of ↵Richard Smith2012-08-21
| | | | | | WeakVH::operator*). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162309 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply r160340. LSR: Limit CollectSubexprs.Andrew Trick2012-07-17
| | | | | | Speculatively fix crashes by code inspection. Can't reproduce them yet. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160344 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "LSR: try not to blow up solving combinatorial problems brute force."Andrew Trick2012-07-17
| | | | | | Some units tests crashed on a different platform. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160341 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR: try not to blow up solving combinatorial problems brute force.Andrew Trick2012-07-17
| | | | | | | | | | This places limits on CollectSubexprs to constrains the number of reassociation possibilities. It limits the recursion depth and skips over chains of nested recurrences outside the current loop. Fixes PR13361. Although underlying SCEV behavior is still potentially bad. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160340 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 expansion of scaled reg in non-address type formulae.Andrew Trick2012-06-15
| | | | | | | | | For non-address users, Base and Scaled registers are not specially associated to fit an address mode, so SCEVExpander should apply normal expansion rules. Otherwise we may sink computation into inner loops that have already been optimized. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158537 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR fix: "Special" users are just like "Basic" users but allow -1 scale.Andrew Trick2012-06-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158536 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix typos found by http://github.com/lyda/misspell-checkBenjamin Kramer2012-06-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157885 91177308-0d34-0410-b5e6-96231b3b80d8
* Make sure HoistInsertPosition finds a position that is dominated by allRafael Espindola2012-04-30
| | | | | | inputs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155809 91177308-0d34-0410-b5e6-96231b3b80d8
* Break up getProfitableChainIncrement().Jakob Stoklund Olesen2012-04-26
| | | | | | | | | | | The required checks are moved to ChainInstruction() itself and the policy decisions are moved to IVChain::isProfitableInc(). Also cache the ExprBase in IVChain to avoid frequent recomputations. No functional change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155676 91177308-0d34-0410-b5e6-96231b3b80d8
* Turn IVChain into a struct.Jakob Stoklund Olesen2012-04-26
| | | | | | No functional change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155675 91177308-0d34-0410-b5e6-96231b3b80d8
* Print IV chain numbers while collecting them.Jakob Stoklund Olesen2012-04-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155567 91177308-0d34-0410-b5e6-96231b3b80d8
* loop-reduce: Add an early bailout to catch extremely large loops.Andrew Trick2012-04-18
| | | | | | | | | | | | | | This introduces a threshold of 200 IV Users, which is very conservative but should be sufficient to avoid serious compile time sink or stack overflow. The llvm test-suite with LTO never exceeds 190 users per loop. The bug doesn't relate to a specific type of loop. Checking in an arbitrary giant loop as a unit test would be silly. Fixes rdar://11262507. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154983 91177308-0d34-0410-b5e6-96231b3b80d8
* Pass the right sign to TLI->isLegalICmpImmediate.Jakob Stoklund Olesen2012-04-05
| | | | | | | | | | | | | | | | | | LSR can fold three addressing modes into its ICmpZero node: ICmpZero BaseReg + Offset => ICmp BaseReg, -Offset ICmpZero -1*ScaleReg + Offset => ICmp ScaleReg, Offset ICmpZero BaseReg + -1*ScaleReg => ICmp BaseReg, ScaleReg The first two cases are only used if TLI->isLegalICmpImmediate() likes the offset. Make sure the right Offset sign is passed to this method in the second case. The ARM version is not symmetric. <rdar://problem/11184260> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154079 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR ivchain bug fix: corner case with ConstantExpr.Andrew Trick2012-03-26
| | | | | | Fixes PR11950. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153463 91177308-0d34-0410-b5e6-96231b3b80d8
* comment typoAndrew Trick2012-03-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153462 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR cleanup: potential bug caught by PVS-Studio.Andrew Trick2012-03-26
| | | | | | Thanks Andrey. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153451 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove -enable-lsr-retry in time for 3.1.Andrew Trick2012-03-22
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153287 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove -enable-lsr-nested in time for 3.1.Andrew Trick2012-03-22
| | | | | | Tests cases have been removed but attached to open PR12330. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153286 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR fix: Add isSimplifiedLoopNest to IVUsers analysis.Andrew Trick2012-03-16
| | | | | | | | | | | | | | Only record IVUsers that are dominated by simplified loop headers. Otherwise SCEVExpander will crash while looking for a preheader. I previously tried to work around this in LSR itself, but that was insufficient. This way, LSR can continue to run if some uses are not in simple loops, as long as we don't attempt to analyze those users. Fixes <rdar://problem/11049788> Segmentation fault: 11 in LoopStrengthReduce git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152892 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
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-28 18:11:03 +0000