summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopRotation.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Switch CodeMetrics itself over to use TTI to determine if an instructionChandler Carruth2013-01-211-1/+6
| | | | | | | | | | | | is free. The whole CodeMetrics API should probably be reworked more, but this is enough to allow deleting the duplicate code there for computing whether an instruction is free. All of the passes using this have been updated to pull in TTI and hand it to the CodeMetrics stuff. Further, a dead CodeMetrics API (analyzeFunction) is nuked for lack of users. llvm-svn: 173036
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-2/+2
| | | | | | | | | | | | | | | | | | | | | 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
* Add a new attribute, 'noduplicate'. If a function contains a noduplicate ↵James Molloy2012-12-201-1/+7
| | | | | | | | call, the call cannot be duplicated - Jump threading, loop unrolling, loop unswitching, and loop rotation are inhibited if they would duplicate the call. Similarly inlining of the function is inhibited, if that would duplicate the call (in particular inlining is still allowed when there is only one callsite and the function has internal linkage). llvm-svn: 170704
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-7/+7
| | | | | | | | | | | | | | | | | 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
* LoopRotation: Make the brute force DomTree update more brute force.Benjamin Kramer2012-09-021-32/+21
| | | | | | | | | | | | | | We update until we hit a fixpoint. This is probably slow but also slightly simplifies the code. It should also fix the occasional invalid domtrees observed when building with expensive checking. I couldn't find a case where this had a measurable slowdown, but if someone finds a pathological case where it does we may have to find a cleverer way of updating dominators here. Thanks to Duncan for the test case. llvm-svn: 163091
* LoopRotation: Check some invariants of the dominator updating code.Benjamin Kramer2012-09-011-0/+3
| | | | llvm-svn: 163058
* LoopRotate: Also rotate loops with multiple exits.Benjamin Kramer2012-08-301-13/+60
| | | | | | | | | | | | | | | The old PHI updating code in loop-rotate was replaced with SSAUpdater a while ago, it has no problems with comples PHIs. What had to be fixed is detecting whether a loop was already rotated and updating dominators when multiple exits were present. This change increases overall code size a bit, mostly due to additional loop unrolling opportunities. Passes test-suite and selfhost with -verify-dom-info. Fixes PR7447. Thanks to Andy for the input on the domtree updating code. llvm-svn: 162912
* Clean whitespaces.Nadav Rotem2012-07-241-3/+4
| | | | llvm-svn: 160668
* loop-rotate shouldn't hoist alloca instructions out of a loop. Patch by ↵Eli Friedman2012-02-161-1/+2
| | | | | | Patrik Hägglund, with slightly modified test. Issue reported by Patrik Hägglund on llvmdev. llvm-svn: 150642
* Add simplifyLoopLatch to LoopRotate pass.Andrew Trick2012-02-141-0/+103
| | | | | | This folds a simple loop tail into a loop latch. It covers the common (in fortran) case of postincrement loops. It's a "free" way to expose this type of loop to downstream loop optimizations that bail out on non-canonical loops (getLoopLatch is a heavily used check). llvm-svn: 150439
* whitespaceAndrew Trick2012-02-141-30/+30
| | | | llvm-svn: 150438
* Make better use of the PHINode API.Jay Foad2011-06-201-1/+1
| | | | | | | | Change various bits of code to make better use of the existing PHINode API, to insulate them from forthcoming changes in how PHINodes store their operands. llvm-svn: 133434
* Preserve line number information.Devang Patel2011-04-291-1/+2
| | | | llvm-svn: 130536
* fix PR9523, a crash in looprotate on a non-canonical loop made out of ↵Chris Lattner2011-04-091-1/+5
| | | | | | indirectbr. llvm-svn: 129203
* Do not hoist @llvm.dbg.value. Here, @llvm.dbg.value is "referring" a value ↵Devang Patel2011-02-141-1/+2
| | | | | | that is modified inside loop. llvm-svn: 125529
* remove a bogus assertion: the latch block of a loop is not Chris Lattner2011-01-111-6/+5
| | | | | | | neccesarily an uncond branch to the header. This fixes PR8955 (the assertion tripping). llvm-svn: 123219
* When loop rotation happens, it is *very* common for the duplicated condbrChris Lattner2011-01-081-21/+48
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | to be foldable into an uncond branch. When this happens, we can make a much simpler CFG for the loop, which is important for nested loop cases where we want the outer loop to be aggressively optimized. Handle this case more aggressively. For example, previously on phi-duplicate.ll we would get this: define void @test(i32 %N, double* %G) nounwind ssp { entry: %cmp1 = icmp slt i64 1, 1000 br i1 %cmp1, label %bb.nph, label %for.end bb.nph: ; preds = %entry br label %for.body for.body: ; preds = %bb.nph, %for.cond %j.02 = phi i64 [ 1, %bb.nph ], [ %inc, %for.cond ] %arrayidx = getelementptr inbounds double* %G, i64 %j.02 %tmp3 = load double* %arrayidx %sub = sub i64 %j.02, 1 %arrayidx6 = getelementptr inbounds double* %G, i64 %sub %tmp7 = load double* %arrayidx6 %add = fadd double %tmp3, %tmp7 %arrayidx10 = getelementptr inbounds double* %G, i64 %j.02 store double %add, double* %arrayidx10 %inc = add nsw i64 %j.02, 1 br label %for.cond for.cond: ; preds = %for.body %cmp = icmp slt i64 %inc, 1000 br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge for.cond.for.end_crit_edge: ; preds = %for.cond br label %for.end for.end: ; preds = %for.cond.for.end_crit_edge, %entry ret void } Now we get the much nicer: define void @test(i32 %N, double* %G) nounwind ssp { entry: br label %for.body for.body: ; preds = %entry, %for.body %j.01 = phi i64 [ 1, %entry ], [ %inc, %for.body ] %arrayidx = getelementptr inbounds double* %G, i64 %j.01 %tmp3 = load double* %arrayidx %sub = sub i64 %j.01, 1 %arrayidx6 = getelementptr inbounds double* %G, i64 %sub %tmp7 = load double* %arrayidx6 %add = fadd double %tmp3, %tmp7 %arrayidx10 = getelementptr inbounds double* %G, i64 %j.01 store double %add, double* %arrayidx10 %inc = add nsw i64 %j.01, 1 %cmp = icmp slt i64 %inc, 1000 br i1 %cmp, label %for.body, label %for.end for.end: ; preds = %for.body ret void } With all of these recent changes, we are now able to compile: void foo(char *X) { for (int i = 0; i != 100; ++i) for (int j = 0; j != 100; ++j) X[j+i*100] = 0; } into a single memset of 10000 bytes. This series of changes should also be helpful for other nested loop scenarios as well. llvm-svn: 123079
* split ssa updating code out to its own helper function. Don't botherChris Lattner2011-01-081-74/+78
| | | | | | | moving the OrigHeader block anymore: we just merge it away anyway so its code layout doesn't matter. llvm-svn: 123077
* Implement a TODO: Enhance loopinfo to merge away the unconditional branchChris Lattner2011-01-081-11/+7
| | | | | | | | | | that it was leaving in loops after rotation (between the original latch block and the original header. With this change, it is possible for rotated loops to have just a single basic block, which is useful. llvm-svn: 123075
* inline preserveCanonicalLoopForm now that it is simple.Chris Lattner2011-01-081-39/+17
| | | | llvm-svn: 123073
* Three major changes:Chris Lattner2011-01-081-115/+20
| | | | | | | | | | | | | | | 1. Rip out LoopRotate's domfrontier updating code. It isn't needed now that LICM doesn't use DF and it is super complex and gross. 2. Make DomTree updating code a lot simpler and faster. The old loop over all the blocks was just to find a block?? 3. Change the code that inserts the new preheader to just use SplitCriticalEdge instead of doing an overcomplex reimplementation of it. No behavior change, except for the name of the inserted preheader. llvm-svn: 123072
* LoopRotate requires canonical loop form, so it always has preheadersChris Lattner2011-01-081-15/+11
| | | | | | | and latch blocks. Reorder entry conditions to make hte pass faster and more logical. llvm-svn: 123069
* use the LI ivar.Chris Lattner2011-01-081-3/+2
| | | | llvm-svn: 123068
* some cleanups: remove dead arguments and eliminate ivarsChris Lattner2011-01-081-55/+36
| | | | | | that are just passed to one function. llvm-svn: 123067
* fix an issue duncan pointed out, which could cause loop rotateChris Lattner2011-01-081-12/+16
| | | | | | to violate LCSSA form llvm-svn: 123066
* Have loop-rotate simplify instructions (yay instsimplify!) as it clonesChris Lattner2011-01-081-5/+21
| | | | | | | | | | | | them into the loop preheader, eliminating silly instructions like "icmp i32 0, 100" in fixed tripcount loops. This also better exposes the bigger problem with loop rotate that I'd like to fix: once this has been folded, the duplicated conditional branch *often* turns into an uncond branch. Not aggressively handling this is pessimizing later loop optimizations somethin' fierce by making "dominates all exit blocks" checks fail. llvm-svn: 123060
* Revamp the ValueMapper interfaces in a couple ways:Chris Lattner2011-01-081-1/+1
| | | | | | | | | | | | | | | | 1. Take a flags argument instead of a bool. This makes it more clear to the reader what it is used for. 2. Add a flag that says that "remapping a value not in the map is ok". 3. Reimplement MapValue to share a bunch of code and be a lot more efficient. For lookup failures, don't drop null values into the map. 4. Using the new flag a bunch of code can vaporize in LinkModules and LoopUnswitch, kill it. No functionality change. llvm-svn: 123058
* two minor changes: switch to the standard ValueToValueMapTyChris Lattner2011-01-081-2/+7
| | | | | | | | map from ValueMapper.h (giving us access to its utilities) and add a fastpath in the loop rotation code, avoiding expensive ssa updator manipulation for values with nothing to update. llvm-svn: 123057
* split dom frontier handling stuff out to its own DominanceFrontier header,Chris Lattner2011-01-021-1/+1
| | | | | | so that Dominators.h is *just* domtree. Also prune #includes a bit. llvm-svn: 122714
* improve loop rotation to use CodeMetrics to analyze theChris Lattner2011-01-021-16/+7
| | | | | | | size of a loop header instead of its own code size estimator. This allows it to handle bitcasts etc more precisely. llvm-svn: 122681
* Passes do not need to recursively initialize passes that they preserve, ifOwen Anderson2010-10-191-3/+0
| | | | | | | they do not also require them. This allows us to reduce inter-pass linkage dependencies. llvm-svn: 116854
* Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson2010-10-191-1/+3
| | | | | | | | | | | | | | | | | exposes an initializeMyPassFunction(), which must be called in the pass's constructor. This function uses static dependency declarations to recursively initialize the pass's dependencies. Clients that only create passes through the createFooPass() APIs will require no changes. Clients that want to use the CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h before parsing commandline arguments. I have tested this with all standard configurations of clang and llvm-gcc on Darwin. It is possible that there are problems with the static dependencies that will only be visible with non-standard options. If you encounter any crash in pass registration/creation, please send the testcase to me directly. llvm-svn: 116820
* Begin adding static dependence information to passes, which will allow us toOwen Anderson2010-10-121-1/+8
| | | | | | | | | perform initialization without static constructors AND without explicit initialization by the client. For the moment, passes are required to initialize both their (potential) dependencies and any passes they preserve. I hope to be able to relax the latter requirement in the future. llvm-svn: 116334
* Now with fewer extraneous semicolons!Owen Anderson2010-10-071-1/+1
| | | | llvm-svn: 115996
* Teach loop rotate to hoist trivially invariant instructionsChris Lattner2010-09-061-10/+27
| | | | | | | | | | | | | | | in the duplicated block instead of duplicating them. Duplicating them into the end of the loop and the preheader means that we got a phi node in the header of the loop, which prevented LICM from hoisting them. GVN would usually come around later and merge the duplicated instructions so we'd get reasonable output... except that anything dependent on the shoulda-been-hoisted value can't be hoisted. In PR5319 (which this fixes), a memory value didn't get promoted. llvm-svn: 113134
* Reapply commit 112699, speculatively reverted by echristo, sinceDuncan Sands2010-09-021-1/+1
| | | | | | | | | I'm sure it is harmless. Original commit message: If PrototypeValue is erased in the middle of using the SSAUpdator then the SSAUpdator may access freed memory. Instead, simply pass in the type and name explicitly, which is all that was used anyway. llvm-svn: 112810
* Speculatively revert 112699 and 112702, they seem to be causingEric Christopher2010-09-011-1/+1
| | | | | | self host errors on clang-x86-64. llvm-svn: 112719
* If PrototypeValue is erased in the middle of using the SSAUpdatorDuncan Sands2010-09-011-1/+1
| | | | | | | then the SSAUpdator may access freed memory. Instead, simply pass in the type and name explicitly, which is all that was used anyway. llvm-svn: 112699
* When rotating loops, put the original header at the bottom of theDan Gohman2010-08-171-0/+20
| | | | | | | loop, making the resulting loop significantly less ugly. Also, zap its trivial PHI nodes, since it's easy. llvm-svn: 111255
* Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson2010-08-061-1/+1
| | | | llvm-svn: 110460
* Revert r110396 to fix buildbots.Owen Anderson2010-08-061-1/+1
| | | | llvm-svn: 110410
* Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson2010-08-051-1/+1
| | | | | | | | address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. llvm-svn: 110396
* Fix batch of converting RegisterPass<> to INTIALIZE_PASS().Owen Anderson2010-07-211-1/+1
| | | | llvm-svn: 109045
* Reorder the contents of various getAnalysisUsage functions, eliminatingDan Gohman2010-07-161-4/+4
| | | | | | a redundant loopsimplify run from the default -O2 sequence. llvm-svn: 108539
* Use pre-increment instead of post-increment when the result is not used.Dan Gohman2010-06-221-2/+2
| | | | llvm-svn: 106542
* Update various Loop optimization passes to cope with the possibility thatDan Gohman2009-11-051-4/+5
| | | | | | LoopSimplify form may not be available. llvm-svn: 86175
* Call getAnalysis<LoopInfo> the normal way, instead of asking passed-inDan Gohman2009-11-051-2/+2
| | | | | | LoopPassManager for it. llvm-svn: 86163
* Rename forgetLoopBackedgeTakenCount to forgetLoop, because itDan Gohman2009-10-311-1/+1
| | | | | | clears out more information than just the stored backedge taken count. llvm-svn: 85664
* Fix a typo in a comment.Dan Gohman2009-10-261-1/+1
| | | | llvm-svn: 85120
* Rename isLoopExit to isLoopExiting, for consistency with the wordingDan Gohman2009-10-241-1/+1
| | | | | | | | used elsewhere - an exit block is a block outside the loop branched to from within the loop. An exiting block is a block inside the loop that branches out. llvm-svn: 85019
OpenPOWER on IntegriCloud