summaryrefslogtreecommitdiff
path: root/test/Transforms/LoopRotate
Commit message (Collapse)AuthorAge
* Rotate multi-exit loops even if the latch was simplified.Andrew Trick2013-05-06
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Test case by Michele Scandale! Fixes PR10293: Load not hoisted out of loop with multiple exits. There are few regressions with this patch, now tracked by rdar:13817079, and a roughly equal number of improvements. The regressions are almost certainly back luck because LoopRotate has very little idea of whether rotation is profitable. Doing better requires a more comprehensive solution. This checkin is a quick fix that lacks generality (PR10293 has a counter-example). But it trivially fixes the case in PR10293 without interfering with other cases, and it does satify the criteria that LoopRotate is a loop canonicalization pass that should avoid heuristics and special cases. I can think of two approaches that would probably be better in the long run. Ultimately they may both make sense. (1) LoopRotate should check that the current header would make a good loop guard, and that the loop does not already has a sufficient guard. The artifical SimplifiedLoopLatch check would be unnecessary, and the design would be more general and canonical. Two difficulties: - We need a strong guarantee that we won't endlessly rotate, so the analysis would need to be precise in order to avoid the SimplifiedLoopLatch precondition. - Analysis like this are usually based on SCEV, which we don't want to rely on. (2) Rotate on-demand in late loop passes. This could even be done by shoving the loop back on the queue after the optimization that needs it. This could work well when we find LICM opportunities in multi-branch loops. This requires some work, and it doesn't really solve the problem of SCEV wanting a loop guard before the analysis. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181230 91177308-0d34-0410-b5e6-96231b3b80d8
* Tests: rewrite 'opt ... %s' to 'opt ... < %s' so that opt does not emit a ↵Dmitri Gribenko2012-12-30
| | | | | | | | | ModuleID This is done to avoid odd test failures, like the one fixed in r171243. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171250 91177308-0d34-0410-b5e6-96231b3b80d8
* Tests: rewrite 'opt ... %s' to 'opt ... < %s' so that opt does not emit a ↵Dmitri Gribenko2012-12-30
| | | | | | | | | ModuleID This is done to avoid odd test failures, like the one fixed in r171243. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171246 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a new attribute, 'noduplicate'. If a function contains a noduplicate ↵James Molloy2012-12-20
| | | | | | | | | | 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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@170704 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopRotation: Make the brute force DomTree update more brute force.Benjamin Kramer2012-09-02
| | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163091 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix test case.Benjamin Kramer2012-08-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162913 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopRotate: Also rotate loops with multiple exits.Benjamin Kramer2012-08-30
| | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162912 91177308-0d34-0410-b5e6-96231b3b80d8
* llvm/test/Transforms/LoopRotate/PhiRename-1.ll: FileCheck-ize. It fixes PR13301.NAKAMURA Takumi2012-07-17
| | | | | | It began choking since Chandler's r159547, possibly due to improper expression on grep from TclParser to ShParser. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160367 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix the remaining TCL-style quotes found in the testsuite. This isChandler Carruth2012-07-02
| | | | | | | | | | | | | | | | | another mechanical change accomplished though the power of terrible Perl scripts. I have manually switched some "s to 's to make escaping simpler. While I started this to fix tests that aren't run in all configurations, the massive number of tests is due to a really frustrating fragility of our testing infrastructure: things like 'grep -v', 'not grep', and 'expected failures' can mask broken tests all too easily. Essentially, I'm deeply disturbed that I can change the testsuite so radically without causing any change in results for most platforms. =/ git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159547 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix ValueTracking to conclude that debug intrinsics are safe toChandler Carruth2012-04-07
| | | | | | | | | | | | | | | | | | speculate. Without this, loop rotate (among many other places) would suddenly stop working in the presence of debug info. I found this looking at loop rotate, and have augmented its tests with a reduction out of a very hot loop in yacr2 where failing to do this rotation costs sometimes more than 10% in runtime performance, perturbing numerous downstream optimizations. This should have no impact on performance without debug info, but the change in performance when debug info is enabled can be extreme. As a consequence (and this how I got to this yak) any profiling of performance problems should be treated with deep suspicion -- they may have been wildly innacurate of debug info was enabled for profiling. =/ Just a heads up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154263 91177308-0d34-0410-b5e6-96231b3b80d8
* Replace all instances of dg.exp file with lit.local.cfg, since all tests are ↵Eli Bendersky2012-02-16
| | | | | | | | | | | run with LIT now and now Dejagnu. dg.exp is no longer needed. Patch reviewed by Daniel Dunbar. It will be followed by additional cleanup patches. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150664 91177308-0d34-0410-b5e6-96231b3b80d8
* loop-rotate shouldn't hoist alloca instructions out of a loop. Patch by ↵Eli Friedman2012-02-16
| | | | | | Patrik Hägglund, with slightly modified test. Issue reported by Patrik Hägglund on llvmdev. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150642 91177308-0d34-0410-b5e6-96231b3b80d8
* Add simplifyLoopLatch to LoopRotate pass.Andrew Trick2012-02-14
| | | | | | 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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150439 91177308-0d34-0410-b5e6-96231b3b80d8
* remove asmparser support for the old getresult instruction, which has been ↵Chris Lattner2011-06-17
| | | | | | subsumed by extractvalue. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133247 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove support for using "foo" as symbols instead of %"foo". This is ancientChris Lattner2011-06-17
| | | | | | | | syntax and has been long obsolete. As usual, updating the tests is the nasty part of this. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133242 91177308-0d34-0410-b5e6-96231b3b80d8
* fix PR9523, a crash in looprotate on a non-canonical loop made out of ↵Chris Lattner2011-04-09
| | | | | | indirectbr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129203 91177308-0d34-0410-b5e6-96231b3b80d8
* Do not hoist @llvm.dbg.value. Here, @llvm.dbg.value is "referring" a value ↵Devang Patel2011-02-14
| | | | | | that is modified inside loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125529 91177308-0d34-0410-b5e6-96231b3b80d8
* merge tests into one crash.ll test.Chris Lattner2011-01-11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123220 91177308-0d34-0410-b5e6-96231b3b80d8
* remove a bogus assertion: the latch block of a loop is not Chris Lattner2011-01-11
| | | | | | | | neccesarily an uncond branch to the header. This fixes PR8955 (the assertion tripping). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123219 91177308-0d34-0410-b5e6-96231b3b80d8
* When loop rotation happens, it is *very* common for the duplicated condbrChris Lattner2011-01-08
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123079 91177308-0d34-0410-b5e6-96231b3b80d8
* Three major changes:Chris Lattner2011-01-08
| | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123072 91177308-0d34-0410-b5e6-96231b3b80d8
* Have loop-rotate simplify instructions (yay instsimplify!) as it clonesChris Lattner2011-01-08
| | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123060 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach loop rotate to hoist trivially invariant instructionsChris Lattner2010-09-06
| | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113134 91177308-0d34-0410-b5e6-96231b3b80d8
* When rotating loops, put the original header at the bottom of theDan Gohman2010-08-17
| | | | | | | | loop, making the resulting loop significantly less ugly. Also, zap its trivial PHI nodes, since it's easy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111255 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix some tests that didn't test anything.Benjamin Kramer2010-06-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106954 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete useless trailing semicolons.Dan Gohman2010-01-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92740 91177308-0d34-0410-b5e6-96231b3b80d8
* fix PR5837 by having SSAUpdate reuse phi nodes for theChris Lattner2009-12-21
| | | | | | | | | | | 'GetValueInMiddleOfBlock' case, instead of inserting duplicates. A similar fix is almost certainly needed by the machine-level SSAUpdate implementation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91820 91177308-0d34-0410-b5e6-96231b3b80d8
* Make Loop::getLoopLatch() work on loops which don't have preheaders, asDan Gohman2009-11-20
| | | | | | | | | | | | | it may be used in contexts where preheader insertion may have failed due to an indirectbr. Make LoopSimplify's LoopSimplify::SeparateNestedLoop properly fail in the case that it would require splitting an indirectbr edge. These fix PR5502. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@89484 91177308-0d34-0410-b5e6-96231b3b80d8
* Make these tests more interesting by usingDan Gohman2009-10-24
| | | | | | | | -verify-dom-info and -verify-loop-info, which enable additional (expensive) consistency checks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85017 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a testcase to help test analysis preservation.Dan Gohman2009-09-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83002 91177308-0d34-0410-b5e6-96231b3b80d8
* Change tests from "opt %s" to "opt < %s" so that opt doesn't see theDan Gohman2009-09-11
| | | | | | | | | input filename so that opt doesn't print the input filename in the output so that grep lines in the tests don't unintentionally match strings in the input filename. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81537 91177308-0d34-0410-b5e6-96231b3b80d8
* Use opt -S instead of piping bitcode output through llvm-dis.Dan Gohman2009-09-08
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81257 91177308-0d34-0410-b5e6-96231b3b80d8
* Change these tests to feed the assembly files to opt directly, insteadDan Gohman2009-09-08
| | | | | | | of using llvm-as, now that opt supports this. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81226 91177308-0d34-0410-b5e6-96231b3b80d8
* Testcase for PR2639.Owen Anderson2009-04-23
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69867 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix PR3408 by making a non-obvious assumption very obvious, and Chris Lattner2009-01-26
| | | | | | | handling the flaw inherent in that assumption. :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62984 91177308-0d34-0410-b5e6-96231b3b80d8
* sabre brings to my attention that the 'tr' suffix is also obsoleteGabor Greif2008-05-20
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51349 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename the last test with .llx extension to .ll, resolve duplicate test by ↵Gabor Greif2008-05-20
| | | | | | renaming to isnan2. Now that no test has llx ending there is no need to search for them from dg.exp too. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51328 91177308-0d34-0410-b5e6-96231b3b80d8
* New test for bug fixed in 50545.Dale Johannesen2008-05-01
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50548 91177308-0d34-0410-b5e6-96231b3b80d8
* remove this testcase. It isn't testing loop rotate, it is testing allChris Lattner2008-04-23
| | | | | | | | | of -std-compile-opts and is now failing because other passes are generating IR that looks different to input of loop rotate. Devang, please introduce a testcase that only runs loop rotate. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50136 91177308-0d34-0410-b5e6-96231b3b80d8
* Byebye llvm-upgrade!Tanya Lattner2008-03-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48762 91177308-0d34-0410-b5e6-96231b3b80d8
* Ding dong, the DoesntAccessMemoryFns andDuncan Sands2007-11-23
| | | | | | | | | | OnlyReadsMemoryFns tables are dead! We get more, and more accurate, information from gcc via the readnone and readonly function attributes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44288 91177308-0d34-0410-b5e6-96231b3b80d8
* Bunch of tests to check loop passes.Devang Patel2007-07-31
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40629 91177308-0d34-0410-b5e6-96231b3b80d8
* New test.Devang Patel2007-07-11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@39768 91177308-0d34-0410-b5e6-96231b3b80d8
* Convert .cvsignore filesJohn Criswell2007-06-29
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37801 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a .cvsignore file.Reid Spencer2007-04-21
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36323 91177308-0d34-0410-b5e6-96231b3b80d8
* For PR1319:Reid Spencer2007-04-16
| | | | | | | | | Remove && from the end of the lines to prevent tests from throwing run lines into the background. Also, clean up places where the same command is run multiple times by using a temporary file. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36142 91177308-0d34-0410-b5e6-96231b3b80d8
* For PR1319:Reid Spencer2007-04-15
| | | | | | | Upgrade to use new Tcl exec based test harness. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36062 91177308-0d34-0410-b5e6-96231b3b80d8
* The "implementation" keyword is no more!Reid Spencer2007-04-11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35919 91177308-0d34-0410-b5e6-96231b3b80d8
* Make the llvm-runtest function much more amenable by eliminating all theReid Spencer2007-04-11
| | | | | | | | | global variables that needed to be passed in. This makes it possible to add new global variables with only a couple changes (Makefile and llvm-dg.exp) instead of touching every single dg.exp file. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35918 91177308-0d34-0410-b5e6-96231b3b80d8
* Add test case for PR 1154.Devang Patel2007-04-10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35865 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-12 20:45:28 +0000