summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Fix a bug in LoopStrengthReduce that caused it to emit IR withDan Gohman2008-05-151-3/+21
| | | | | | | | | | | | | | | | | use-before-def. The problem comes up in code with multiple PHIs where one PHI is being rewritten in terms of the other, but the other needs to be casted first. LLVM rules requre the cast instruction to be inserted after any PHI instructions, but when instructions were inserted to replace the second PHI value with a function of the first, they were ended up going before the cast instruction. Avoid this problem by remembering the location of the cast instruction, when one is needed, and inserting the expansion of the new value after it. This fixes a bug that surfaced in 255.vortex on x86-64 when instcombine was removed from the middle of the loop optimization passes. llvm-svn: 51169
* Clean up the use of static and anonymous namespaces. This turned upDan Gohman2008-05-131-2/+4
| | | | | | | several things that were neither in an anonymous namespace nor static but not intended to be global. llvm-svn: 51017
* Minor whitespace and comment cleanups.Dan Gohman2008-04-141-3/+3
| | | | llvm-svn: 49671
* API changes for class Use size reduction, wave 1.Gabor Greif2008-04-061-1/+1
| | | | | | | | Specifically, introduction of XXX::Create methods for Users that have a potentially variable number of Uses. llvm-svn: 49277
* Remove dead options.Evan Cheng2008-03-191-13/+3
| | | | llvm-svn: 48556
* Use empty() instead of comparing size() with zero.Dan Gohman2008-01-291-1/+1
| | | | llvm-svn: 46514
* Remove attribution from file headers, per discussion on llvmdev.Chris Lattner2007-12-291-2/+2
| | | | llvm-svn: 45418
* Clean up previous patch: PHI uses should not prevent iv reuse if all other ↵Evan Cheng2007-12-201-35/+16
| | | | | | uses are addresses. This trades a constant multiply for one fewer iv. llvm-svn: 45251
* Allow iv reuse if the user is a PHI node which is in turn used as addresses.Evan Cheng2007-12-191-29/+82
| | | | llvm-svn: 45230
* Remove indeterminism from a loop. We think this willDale Johannesen2007-11-171-2/+6
| | | | | | | fix an occasional nonrepeatable bootstrap failure we've been seeing on Darwin. llvm-svn: 44202
* At end of LSR, replace uses of now constant (as result of SplitCriticalEdge) ↵Evan Cheng2007-10-301-9/+33
| | | | | | PHI node with the constant value. llvm-svn: 43533
* It's not safe to tell SplitCriticalEdge to merge identical edges. It may ↵Evan Cheng2007-10-301-11/+9
| | | | | | delete the phi instruction that's being processed. llvm-svn: 43524
* - Bug fixes.Evan Cheng2007-10-291-10/+38
| | | | | | - Allow icmp rewrite using an iv / stride of a smaller integer type. llvm-svn: 43480
* Update a comment to reflect the current code.Dan Gohman2007-10-291-2/+2
| | | | llvm-svn: 43463
* Remove an unused function argument.Dan Gohman2007-10-291-6/+6
| | | | llvm-svn: 43462
* Fix a typo in a comment.Dan Gohman2007-10-291-1/+1
| | | | llvm-svn: 43461
* Avoid calling ValidStride when not all uses are addresses.Dan Gohman2007-10-291-6/+5
| | | | llvm-svn: 43460
* A number of LSR fixes:Evan Cheng2007-10-261-21/+32
| | | | | | | | | - ChangeCompareStride only reuse stride that is larger than current stride. It will let the general reuse mechanism to try to reuse a smaller stride. - Watch out for multiplication overflow in ChangeCompareStride. - Replace std::set with SmallPtrSet. llvm-svn: 43408
* Fix a crash. Make sure TLI is not null.Evan Cheng2007-10-261-1/+1
| | | | llvm-svn: 43384
* Loosen up iv reuse to allow reuse of the same stride but a larger type when ↵Evan Cheng2007-10-261-17/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | truncating from the larger type to smaller type is free. e.g. Turns this loop: LBB1_1: # entry.bb_crit_edge xorl %ecx, %ecx xorw %dx, %dx movw %dx, %si LBB1_2: # bb movl L_X$non_lazy_ptr, %edi movw %si, (%edi) movl L_Y$non_lazy_ptr, %edi movw %dx, (%edi) addw $4, %dx incw %si incl %ecx cmpl %eax, %ecx jne LBB1_2 # bb into LBB1_1: # entry.bb_crit_edge xorl %ecx, %ecx xorw %dx, %dx LBB1_2: # bb movl L_X$non_lazy_ptr, %esi movw %cx, (%esi) movl L_Y$non_lazy_ptr, %esi movw %dx, (%esi) addw $4, %dx incl %ecx cmpl %eax, %ecx jne LBB1_2 # bb llvm-svn: 43375
* Do not rewrite compare instruction using iv of a different stride if the newEvan Cheng2007-10-251-36/+80
| | | | | | stride may be rewritten using the stride of the compare instruction. llvm-svn: 43367
* Remove code that's commented out.Evan Cheng2007-10-251-2/+0
| | | | llvm-svn: 43356
* If a loop termination compare instruction is the only use of its stride,Evan Cheng2007-10-251-34/+163
| | | | | | | | | | | | | | | | | | | and the compaison is against a constant value, try eliminate the stride by moving the compare instruction to another stride and change its constant operand accordingly. e.g. loop: ... v1 = v1 + 3 v2 = v2 + 1 if (v2 < 10) goto loop => loop: ... v1 = v1 + 3 if (v1 < 30) goto loop llvm-svn: 43336
* Strength reduction improvements.Dan Gohman2007-10-221-20/+61
| | | | | | | | | | | | | | | | | | | | | | - Avoid attempting stride-reuse in the case that there are users that aren't addresses. In that case, there will be places where the multiplications won't be folded away, so it's better to try to strength-reduce them. - Several SSE intrinsics have operands that strength-reduction can treat as addresses. The previous item makes this more visible, as any non-address use of an IV can inhibit stride-reuse. - Make ValidStride aware of whether there's likely to be a base register in the address computation. This prevents it from thinking that things like stride 9 are valid on x86 when the base register is already occupied. Also, XFAIL the 2007-08-10-LEA16Use32.ll test; the new logic to avoid stride-reuse elimintes the LEA in the loop, so the test is no longer testing what it was intended to test. llvm-svn: 43231
* Move the SCEV object factors from being static members of the individualDan Gohman2007-10-221-74/+80
| | | | | | | SCEV subclasses to being non-static member functions of the ScalarEvolution class. llvm-svn: 43224
* Fix stride computations for long double arrays.Dale Johannesen2007-10-011-1/+1
| | | | llvm-svn: 42508
* wrap some long lines. Major offenders that are left includeChris Lattner2007-08-021-3/+4
| | | | | | | | gvn, gvnpre, dse, and predsimplify. To see these, use: make check-line-length llvm-svn: 40738
* More explicit keywords.Dan Gohman2007-08-011-1/+1
| | | | llvm-svn: 40673
* Use SCEVExpander::InsertCastOfTo instead of calling new IntToPtrInstDan Gohman2007-07-311-5/+12
| | | | | | | directly, because the insert point used by the SCEVExpander may vary from what LSR originally computes. llvm-svn: 40641
* Rename ScalarEvolution::deleteInstructionFromRecords toDan Gohman2007-06-191-2/+2
| | | | | | | | | deleteValueFromRecords and loosen the types to all it to accept Value* instead of just Instruction*, since this is what ScalarEvolution uses internally anyway. This allows more flexibility for future uses. llvm-svn: 37657
* Add a SCEV class and supporting code for sign-extend expressions.Dan Gohman2007-06-151-12/+16
| | | | | | | | | | This created an ambiguity for expandInTy to decide when to use sign-extension or zero-extension, but it turns out that most of its callers don't actually need a type conversion, now that LLVM types don't have explicit signedness. Drop expandInTy in favor of plain expand, and change the few places that actually need a type conversion to do it themselves. llvm-svn: 37591
* Use DominatorTree instead of ETForest.Devang Patel2007-06-071-8/+7
| | | | llvm-svn: 37499
* Fix PR1495 and CodeGen/X86/2007-06-05-LSR-Dominator.llChris Lattner2007-06-061-0/+6
| | | | llvm-svn: 37454
* Handle negative strides much more optimally. This compiles ↵Chris Lattner2007-05-191-3/+26
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | X86/lsr-negative-stride.ll into: _t: movl 8(%esp), %ecx movl 4(%esp), %eax cmpl %ecx, %eax je LBB1_3 #bb17 LBB1_1: #bb cmpl %ecx, %eax jg LBB1_4 #cond_true LBB1_2: #cond_false subl %eax, %ecx cmpl %ecx, %eax jne LBB1_1 #bb LBB1_3: #bb17 ret LBB1_4: #cond_true subl %ecx, %eax cmpl %ecx, %eax jne LBB1_1 #bb jmp LBB1_3 #bb17 instead of: _t: subl $4, %esp movl %esi, (%esp) movl 12(%esp), %ecx movl 8(%esp), %eax cmpl %ecx, %eax je LBB1_4 #bb17 LBB1_1: #bb.outer movl %ecx, %edx negl %edx LBB1_2: #bb cmpl %ecx, %eax jle LBB1_5 #cond_false LBB1_3: #cond_true addl %edx, %eax cmpl %ecx, %eax jne LBB1_2 #bb LBB1_4: #bb17 movl (%esp), %esi addl $4, %esp ret LBB1_5: #cond_false movl %ecx, %edx subl %eax, %edx movl %eax, %esi addl %esi, %esi cmpl %ecx, %esi je LBB1_4 #bb17 LBB1_6: #cond_false.bb.outer_crit_edge movl %edx, %ecx jmp LBB1_1 #bb.outer llvm-svn: 37252
* significantly improve debug output of lsrChris Lattner2007-05-111-6/+13
| | | | llvm-svn: 36996
* Use IntrinsicInst to test for prefetch instructions, which is ever soDan Gohman2007-05-041-6/+5
| | | | | | slightly nicer than using CallInst with an extra check; thanks Chris. llvm-svn: 36743
* Allow strength reduction to make use of addressing modes for theDan Gohman2007-05-031-1/+10
| | | | | | address operand in a prefetch intrinsic. llvm-svn: 36713
* Drop 'const'Devang Patel2007-05-031-2/+2
| | | | llvm-svn: 36662
* Use 'static const char' instead of 'static const int'.Devang Patel2007-05-021-2/+2
| | | | | | | Due to darwin gcc bug, one version of darwin linker coalesces static const int, which defauts PassID based pass identification. llvm-svn: 36652
* Do not use typeinfo to identify pass in pass manager.Devang Patel2007-05-011-1/+4
| | | | llvm-svn: 36632
* FixDevang Patel2007-04-231-5/+9
| | | | | | http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070423/048333.html llvm-svn: 36380
* Remove ImmediateDominator analysis. The same information can be obtained ↵Owen Anderson2007-04-151-1/+0
| | | | | | | | | | from DomTree. A lot of code for constructing ImmediateDominator is now folded into DomTree construction. This is part of the ongoing work for PR217. llvm-svn: 36063
* Now that codegen prepare isn't defeating me, I can finally fix what I setChris Lattner2007-04-131-1/+19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | out to do! :) This fixes a problem where LSR would insert a bunch of code into each MBB that uses a particular subexpression (e.g. IV+base+C). The problem is that this code cannot be CSE'd back together if inserted into different blocks. This patch changes LSR to attempt to insert a single copy of this code and share it, allowing codegenprepare to duplicate the code if it can be sunk into various addressing modes. On CodeGen/ARM/lsr-code-insertion.ll, for example, this gives us code like: add r8, r0, r5 str r6, [r8, #+4] .. ble LBB1_4 @cond_next LBB1_3: @cond_true str r10, [r8, #+4] LBB1_4: @cond_next ... LBB1_5: @cond_true55 ldr r6, LCPI1_1 str r6, [r8, #+4] instead of: add r10, r0, r6 str r8, [r10, #+4] ... ble LBB1_4 @cond_next LBB1_3: @cond_true add r8, r0, r6 str r10, [r8, #+4] LBB1_4: @cond_next ... LBB1_5: @cond_true55 add r8, r0, r6 ldr r10, LCPI1_1 str r10, [r8, #+4] Besides being smaller and more efficient, this makes it immediately obvious that it is profitable to predicate LBB1_3 now :) llvm-svn: 35972
* switch LSR to use isLegalAddressingMode instead of other simpler hooksChris Lattner2007-04-091-18/+21
| | | | llvm-svn: 35837
* Completely purge DomSet. This is the (hopefully) final patch for PR1171.Owen Anderson2007-04-071-1/+0
| | | | llvm-svn: 35731
* split some code out into a helper functionChris Lattner2007-04-031-18/+30
| | | | llvm-svn: 35615
* allow -1 strides to reuse "1" strides.Chris Lattner2007-04-021-1/+2
| | | | llvm-svn: 35607
* Pass the type of the store access, not the type of the store, into theChris Lattner2007-04-021-2/+9
| | | | | | | | | | | | | | | | | | | | | | | | | target hook. This allows us to codegen a loop as: LBB1_1: @cond_next mov r2, #0 str r2, [r0, +r3, lsl #2] add r3, r3, #1 cmn r3, #1 bne LBB1_1 @cond_next instead of: LBB1_1: @cond_next mov r2, #0 str r2, [r0], #+4 add r3, r3, #1 cmn r3, #1 bne LBB1_1 @cond_next This looks the same, but has one fewer induction variable (and therefore, one fewer register) live in the loop. llvm-svn: 35592
* print the type of an inserted IV in -debug mode.Chris Lattner2007-04-011-3/+4
| | | | llvm-svn: 35563
* Look through bitcast when finding IVs. (Chris' patch really.)Dale Johannesen2007-03-261-0/+10
| | | | llvm-svn: 35347
OpenPOWER on IntegriCloud