summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Loop strength reduce: fix function name.Tim Northover2014-01-221-8/+8
| | | | llvm-svn: 199801
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-131-8/+8
| | | | | | | | | | | | | | | | | | | | | | | can be used by both the new pass manager and the old. This removes it from any of the virtual mess of the pass interfaces and lets it derive cleanly from the DominatorTreeBase<> template. In turn, tons of boilerplate interface can be nuked and it turns into a very straightforward extension of the base DominatorTree interface. The old analysis pass is now a simple wrapper. The names and style of this split should match the split between CallGraph and CallGraphWrapperPass. All of the users of DominatorTree have been updated to match using many of the same tricks as with CallGraph. The goal is that the common type remains the resulting DominatorTree rather than the pass. This will make subsequent work toward the new pass manager significantly easier. Also in numerous places things became cleaner because I switched from re-running the pass (!!! mid way through some other passes run!!!) to directly recomputing the domtree. llvm-svn: 199104
* [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
* Put the functionality for printing a value to a raw_ostream as anChandler Carruth2014-01-091-7/+6
| | | | | | | | | | | | operand into the Value interface just like the core print method is. That gives a more conistent organization to the IR printing interfaces -- they are all attached to the IR objects themselves. Also, update all the users. This removes the 'Writer.h' header which contained only a single function declaration. llvm-svn: 198836
* Move the LLVM IR asm writer header files into the IR directory, as theyChandler Carruth2014-01-071-1/+1
| | | | | | | | | | | | | | | | | are part of the core IR library in order to support dumping and other basic functionality. Rename the 'Assembly' include directory to 'AsmParser' to match the library name and the only functionality left their -- printing has been in the core IR library for quite some time. Update all of the #includes to match. All of this started because I wanted to have the layering in good shape before I started adding support for printing LLVM IR using the new pass infrastructure, and commandline support for the new pass infrastructure. llvm-svn: 198688
* 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
* Fix SCEVExpander: don't try to expand quadratic recurrences outside a loop.Andrew Trick2013-10-251-2/+19
| | | | | | | | | | | | 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
* LSR: Fix the parameters used to compute the scaling factor cost.Quentin Colombet2013-06-191-5/+13
| | | | | | | | | | | | | 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!") llvm-svn: 184341
* Use 0 instead of NULL.Jakub Staszak2013-06-151-5/+5
| | | | llvm-svn: 184044
* Loop Strength Reduce: Scaling factor cost.Quentin Colombet2013-05-311-3/+43
| | | | | | | | | | | | 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> llvm-svn: 183045
* Modify how the formulae are rated in Loop Strength Reduce.Quentin Colombet2013-05-311-6/+45
| | | | | | | | | | | | | | 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> llvm-svn: 183021
* Replace Count{Leading,Trailing}Zeros_{32,64} with count{Leading,Trailing}Zeros.Michael J. Spencer2013-05-241-1/+1
| | | | llvm-svn: 182680
* Use dyn_cast instead of isa && cast.Jakub Staszak2013-03-241-8/+6
| | | | | | No functionality change. llvm-svn: 177836
* Revert "Cleanup some SCEV logic a bit."Andrew Trick2013-03-191-4/+3
| | | | | | | | This reverts commit 82cd8f7382322bee7a71cdc31f7a923c44d37d32. Just add a comment instead! llvm-svn: 177377
* Cleanup some SCEV logic a bit.Andrew Trick2013-03-191-2/+4
| | | | | | Make the code more obvious to scan-build and humans. llvm-svn: 177375
* Tighten up an internal LSR API that should check for NULL.Andrew Trick2013-03-191-1/+1
| | | | | | No test case, but should fix a scan_build warning. llvm-svn: 177374
* Reduce indents in LSRInstance::NarrowSearchSpaceByCollapsingUnrolledCode method.Jakub Staszak2013-02-161-67/+67
| | | | | | No functionality change. llvm-svn: 175364
* LSR IVChain improvement.Andrew Trick2013-02-091-1/+13
| | | | | | | | | Handle chains in which the same offset is used for both loads and stores to the same array. Fixes rdar://11410078. llvm-svn: 174789
* Remove #includes from the commonly used LoopInfo.h.Jakub Staszak2013-02-091-0/+1
| | | | llvm-svn: 174786
* This patch aims to improve compile time performance by increasingPreston Gurd2013-02-011-13/+13
| | | | | | | | | | | | | 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. llvm-svn: 174219
* Fix an editor goof in r171738 that Bill spotted. He may even have a testChandler Carruth2013-01-121-1/+1
| | | | | | | | case, but looking at the diff this was an obviously unintended change. Thanks for the careful review Bill! =] llvm-svn: 172336
* Remove LSR's use of the random AddrMode struct. These variables wereChandler Carruth2013-01-071-68/+76
| | | | | | | | | | | | 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. llvm-svn: 171738
* Switch the SCEV expander and LoopStrengthReduce to useChandler Carruth2013-01-071-161/+138
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Fix a crash in LSR replaceCongruentIVs.Andrew Trick2013-01-061-1/+1
| | | | | | | Indirect branch in the preheader crashes replaceCongruentIVs. Fixes rdar://12910141. llvm-svn: 171653
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-4/+4
| | | | | | | | | | | | | | | | | | | | | 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-12/+12
| | | | | | | | | | | | | | | | | 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 r166264 because the LTO build is still failingNadav Rotem2012-10-191-69/+65
| | | | llvm-svn: 166340
* recommit the patch that makes LSR and LowerInvoke use the TargetTransform ↵Nadav Rotem2012-10-191-65/+69
| | | | | | interface. llvm-svn: 166264
* Temporarily revert the TargetTransform changes.Bob Wilson2012-10-181-69/+65
| | | | | | | | | | | 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-65/+69
| | | | | | information. llvm-svn: 165665
* Refactor the AddrMode class out of TLI to its own header file.Nadav Rotem2012-10-081-7/+8
| | | | | | | | 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. llvm-svn: 165455
* LSR critical edge splitting fix for PR13756.Andrew Trick2012-09-181-11/+15
| | | | llvm-svn: 164147
* Release build: guard dump functions withManman Ren2012-09-121-7/+7
| | | | | | | | "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163344. llvm-svn: 163679
* Release build: guard dump functions with "ifndef NDEBUG"Manman Ren2012-09-061-0/+14
| | | | | | No functional change. llvm-svn: 163344
* Don't bind a reference to a dereferenced null pointer (for return value of ↵Richard Smith2012-08-211-1/+2
| | | | | | WeakVH::operator*). llvm-svn: 162309
* Reapply r160340. LSR: Limit CollectSubexprs.Andrew Trick2012-07-171-28/+52
| | | | | | Speculatively fix crashes by code inspection. Can't reproduce them yet. llvm-svn: 160344
* Revert "LSR: try not to blow up solving combinatorial problems brute force."Andrew Trick2012-07-171-51/+28
| | | | | | Some units tests crashed on a different platform. llvm-svn: 160341
* LSR: try not to blow up solving combinatorial problems brute force.Andrew Trick2012-07-171-28/+51
| | | | | | | | | | 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. llvm-svn: 160340
* LSR Fix: check SCEV expression safety before expansion.Andrew Trick2012-07-131-1/+1
| | | | | | | | | | 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 expansion of scaled reg in non-address type formulae.Andrew Trick2012-06-151-13/+17
| | | | | | | | | 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. llvm-svn: 158537
* LSR fix: "Special" users are just like "Basic" users but allow -1 scale.Andrew Trick2012-06-151-2/+2
| | | | llvm-svn: 158536
* Fix typos found by http://github.com/lyda/misspell-checkBenjamin Kramer2012-06-021-1/+1
| | | | llvm-svn: 157885
* Make sure HoistInsertPosition finds a position that is dominated by allRafael Espindola2012-04-301-1/+1
| | | | | | inputs. llvm-svn: 155809
* Break up getProfitableChainIncrement().Jakob Stoklund Olesen2012-04-261-39/+47
| | | | | | | | | | | 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. llvm-svn: 155676
* Turn IVChain into a struct.Jakob Stoklund Olesen2012-04-261-19/+42
| | | | | | No functional change intended. llvm-svn: 155675
* Print IV chain numbers while collecting them.Jakob Stoklund Olesen2012-04-251-4/+5
| | | | llvm-svn: 155567
* loop-reduce: Add an early bailout to catch extremely large loops.Andrew Trick2012-04-181-0/+17
| | | | | | | | | | | | | | 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. llvm-svn: 154983
* Pass the right sign to TLI->isLegalICmpImmediate.Jakob Stoklund Olesen2012-04-051-2/+11
| | | | | | | | | | | | | | | | | | 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> llvm-svn: 154079
* LSR ivchain bug fix: corner case with ConstantExpr.Andrew Trick2012-03-261-2/+3
| | | | | | Fixes PR11950. llvm-svn: 153463
* comment typoAndrew Trick2012-03-261-1/+1
| | | | llvm-svn: 153462
OpenPOWER on IntegriCloud