aboutsummaryrefslogtreecommitdiff
path: root/test/Transforms/LoopIdiom
AgeCommit message (Collapse)Author
2013-01-10PR14904: Segmentation fault running pass 'Recognize loop idioms'Shuxin Yang
The root cause is mistakenly taking for granted that "dyn_cast<Instruction>(a-Value)" return a non-NULL instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172145 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-07Fix a mistaken commit that included some debugging code.David Tweed
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171734 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-07There was a switch fall-through in the parser for textual LLVM that causedDavid Tweed
bogus comparison operands to default to eq/oeq. Fix that, fix a couple of tests that accidentally passed and test for bogus comparison opeartors explicitly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171733 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-09- Re-enable population count loop idiom recognization Shuxin Yang
- fix a bug which cause sigfault. - add two testing cases which was causing crash git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169687 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-08Revert the patches adding a popcount loop idiom recognition pass.Chandler Carruth
There are still bugs in this pass, as well as other issues that are being worked on, but the bugs are crashers that occur pretty easily in the wild. Test cases have been sent to the original commit's review thread. This reverts the commits: r169671: Fix a logic error. r169604: Move the popcnt tests to an X86 subdirectory. r168931: Initial commit adding the pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169683 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-07The test unconditionally assumes a particular cpu has a backend build in the ↵David Tweed
target. Buildbots for some hosts may choose to build only their own backend in order to maximise testing-turnaround time. Move the test into a prefixed directory so lit's standard "backend specific" suppression can be done. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169604 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-29rdar://12100355 (part 1)Shuxin Yang
This revision attempts to recognize following population-count pattern: while(a) { c++; ... ; a &= a - 1; ... }, where <c> and <a>could be used multiple times in the loop body. TODO: On X8664 and ARM, __buildin_ctpop() are not expanded to a efficent instruction sequence, which need to be improved in the following commits. Reviewed by Nadav, really appreciate! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168931 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-02Add a testcase to loop-idiom to cover PR14241 when we start handlingChandler Carruth
strided loops again. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167287 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-02Revert the switch of loop-idiom to use the new dependence analysis.Chandler Carruth
The new analysis is not yet ready for prime time. It has a *critical* flawed assumption, and some troubling shortages of testing. Until it's been hammered into better shape, let's stick with the working code. This should be easy to revert itself when the analysis is ready. Fixes PR14241, a miscompile of any memcpy-able loop which uses a pointer as the induction mechanism. If you have been seeing miscompiles in this revision range, you really want to test with this backed out. The results of this miscompile are a bit subtle as they can lead to downstream passes concluding things are impossible which are in fact possible. Thanks to David Blaikie for the majority of the reduction of this miscompile. I'll be checking in the test case in a non-revert commit. Revesions reverted here: r167045: LoopIdiom: Fix a serious missed optimization: we only turned top-level loops into memmove. r166877: LoopIdiom: Add checks to avoid turning memmove into an infinite loop. r166875: LoopIdiom: Recognize memmove loops. r166874: LoopIdiom: Replace custom dependence analysis with DependenceAnalysis. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167286 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-31LCSSA: Add a workaround for another nasty SCEV cache invalidation issue.Benjamin Kramer
I'm not entirely happy with this solution, but I don't see a smarter way currently. Fixes PR14214. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167112 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-31DependenceAnalysis: Don't crash if there is no constant operand.Benjamin Kramer
This makes the code match the comments. Resolves a crash in loop idiom (PR14219). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167110 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-30LoopIdiom: Fix a serious missed optimization: we only turned top-level loops ↵Benjamin Kramer
into memmove. Thanks to Preston Briggs for catching this! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167045 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-27LoopIdiom: Add checks to avoid turning memmove into an infinite loop.Benjamin Kramer
I don't think this is possible with the current implementation but that may change eventually. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166877 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-27LoopIdiom: Recognize memmove loops.Benjamin Kramer
This turns loops like for (unsigned i = 0; i != n; ++i) p[i] = p[i+1]; into memmove, which has a highly optimized implementation in most libcs. This was really easy with the new DependenceAnalysis :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166875 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-27LoopIdiom: Replace custom dependence analysis with DependenceAnalysis.Benjamin Kramer
Requires a lot less code and complexity on loop-idiom's side and the more precise analysis can catch more cases, like the one I included as a test case. This also fixes the edge-case miscompilation from PR9481. Compile time performance seems to be slightly worse, but this is mostly due to an extra LCSSA run scheduled by the PassManager and should be fixed there. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166874 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-21Revert r166390 "LoopIdiom: Replace custom dependence analysis with ↵Benjamin Kramer
LoopDependenceAnalysis." It passes all tests, produces better results than the old code but uses the wrong pass, LoopDependenceAnalysis, which is old and unmaintained. "Why is it still in tree?", you might ask. The answer is obviously: "To confuse developers." Just swapping in the new dependency pass sends the pass manager into an infinte loop, I'll try to figure out why tomorrow. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166399 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-21LoopIdiom: Replace custom dependence analysis with LoopDependenceAnalysis.Benjamin Kramer
Requires a lot less code and complexity on loop-idiom's side and the more precise analysis can catch more cases, like the one I included as a test case. This also fixes the edge-case miscompilation from PR9481. I'm not entirely sure that all cases are handled that the old checks handled but LDA will certainly become smarter in the future. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166390 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-21LoopIdiom: Give up when the loop is not in canonical form.Benjamin Kramer
We rely on it when doing the transforms. This can happen when there is an indirectbr in the loop. Fixes PR13892. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164383 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-16Replace all instances of dg.exp file with lit.local.cfg, since all tests are ↵Eli Bendersky
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
2011-09-27Stop emitting instructions with the name "tmp" they eat up memory and have ↵Benjamin Kramer
to be uniqued, without any benefit. If someone prefers %tmp42 to %42, run instnamer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140634 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-15A real testcase for r135286.Chad Rosier
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135299 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-15Add testcase for r135286.Chad Rosier
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135291 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-22Fix PR9815: I was trying to get out of "generating code and thenChris Lattner
failing to form a memset, then having to delete it" but my approximation isn't safe for self recurrent loops. Instead of doign a hack, just do it the right way. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131858 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-07Preserve line no. info.Devang Patel
Radar 9097659 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127182 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-19rewrite the memset_pattern pattern generation stuff to accept any 2/4/8/16-byteChris Lattner
constant, including globals. This makes us generate much more "pretty" pattern globals as well because it doesn't break it down to an array of bytes all the time. This enables us to handle stores of relocatable globals. This kicks in about 48 times in 254.gap, giving us stuff like this: @.memset_pattern40 = internal constant [2 x %struct.TypHeader* (%struct.TypHeader*, %struct.TypHeader*)*] [%struct.TypHeader* (%struct.TypHeader*, %struct .TypHeader*)* @IsFalse, %struct.TypHeader* (%struct.TypHeader*, %struct.TypHeader*)* @IsFalse], align 16 ... call void @memset_pattern16(i8* %scevgep5859, i8* bitcast ([2 x %struct.TypHeader* (%struct.TypHeader*, %struct.TypHeader*)*]* @.memset_pattern40 to i8* ), i64 %tmp75) nounwind git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126044 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-19Stores of null pointers should turn into memset, we weren't recognizingChris Lattner
them as splat values. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126041 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-19Implement rdar://9009151, transforming strided loop stores ofChris Lattner
unsplatable values into memset_pattern16 when it is available (recent darwins). This transforms lots of strided loop stores of ints for example, like 5 in vpr: Formed memset: call void @memset_pattern16(i8* %4, i8* getelementptr inbounds ([16 x i8]* @.memset_pattern9, i32 0, i32 0), i64 %tmp25) from store to: {%3,+,4}<%11> at: store i32 3, i32* %scevgep, align 4, !tbaa !4 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126040 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-04Teach loop-idiom to turn a loop containing a memset into a larger memsetChris Lattner
when safe. The testcase is basically this nested loop: void foo(char *X) { for (int i = 0; i != 100; ++i) for (int j = 0; j != 100; ++j) X[j+i*100] = 0; } which gets turned into a single memset now. clang -O3 doesn't optimize this yet though due to a phase ordering issue I haven't analyzed yet. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122806 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02fix a miscompilation of tramp3d-v4: when forming a memcpy, we have to makeChris Lattner
sure that the loop we're promoting into a memcpy doesn't mutate the input of the memcpy. Before we were just checking that the dest of the memcpy wasn't mod/ref'd by the loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122712 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02If a loop iterates exactly once (has backedge count = 0) then don'tChris Lattner
mess with it. We'd rather peel/unroll it than convert all of its stores into memsets. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122711 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02enhance loop idiom recognition to scan *all* unconditionally executedChris Lattner
blocks in a loop, instead of just the header block. This makes it more aggressive, able to handle Duncan's Ada examples. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122704 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02Allow loop-idiom to run on multiple BB loops, but still only scan the loop Chris Lattner
header for now for memset/memcpy opportunities. It turns out that loop-rotate is successfully rotating loops, but *DOESN'T MERGE THE BLOCKS*, turning "for loops" into 2 basic block loops that loop-idiom was ignoring. With this fix, we form many *many* more memcpy and memsets than before, including on the "history" loops in the viterbi benchmark, which look like this: for (j=0; j<MAX_history; ++j) { history_new[i][j+1] = history[2*i][j]; } Transforming these loops into memcpy's speeds up the viterbi benchmark from 11.98s to 3.55s on my machine. Woo. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122685 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02teach loop idiom recognition to form memcpy's from simple loops.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122678 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-01add a validity check that was missed, fixing a crash on theChris Lattner
new testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122662 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-01improve validity check to handle constant-trip-count loops moreChris Lattner
aggressively. In practice, this doesn't help anything though, see the todo. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122660 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-01implement the "no aliasing accesses in loop" safety check. This passChris Lattner
should be correct now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122659 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-26implement enough of the memset inference algorithm to recognize and insert Chris Lattner
memsets. This is still missing one important validity check, but this is enough to compile stuff like this: void test0(std::vector<char> &X) { for (std::vector<char>::iterator I = X.begin(), E = X.end(); I != E; ++I) *I = 0; } void test1(std::vector<int> &X) { for (long i = 0, e = X.size(); i != e; ++i) X[i] = 0x01010101; } With: $ clang t.cpp -S -o - -O2 -emit-llvm | opt -loop-idiom | opt -O3 | llc to: __Z5test0RSt6vectorIcSaIcEE: ## @_Z5test0RSt6vectorIcSaIcEE ## BB#0: ## %entry subq $8, %rsp movq (%rdi), %rax movq 8(%rdi), %rsi cmpq %rsi, %rax je LBB0_2 ## BB#1: ## %bb.nph subq %rax, %rsi movq %rax, %rdi callq ___bzero LBB0_2: ## %for.end addq $8, %rsp ret ... __Z5test1RSt6vectorIiSaIiEE: ## @_Z5test1RSt6vectorIiSaIiEE ## BB#0: ## %entry subq $8, %rsp movq (%rdi), %rax movq 8(%rdi), %rdx subq %rax, %rdx cmpq $4, %rdx jb LBB1_2 ## BB#1: ## %for.body.preheader andq $-4, %rdx movl $1, %esi movq %rax, %rdi callq _memset LBB1_2: ## %for.end addq $8, %rsp ret git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122573 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-02-16 15:56:25 +0000