aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/LoopStrengthReduce.cpp
AgeCommit message (Collapse)Author
2007-10-29Fix a typo in a comment.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43461 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-29Avoid calling ValidStride when not all uses are addresses.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43460 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-26A number of LSR fixes:Evan Cheng
- 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43408 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-26Fix a crash. Make sure TLI is not null.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43384 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-26Loosen up iv reuse to allow reuse of the same stride but a larger type when ↵Evan Cheng
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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43375 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-25Do not rewrite compare instruction using iv of a different stride if the newEvan Cheng
stride may be rewritten using the stride of the compare instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43367 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-25Remove code that's commented out.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43356 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-25If a loop termination compare instruction is the only use of its stride,Evan Cheng
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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43336 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-22Strength reduction improvements.Dan Gohman
- 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43231 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-22Move the SCEV object factors from being static members of the individualDan Gohman
SCEV subclasses to being non-static member functions of the ScalarEvolution class. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43224 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-01Fix stride computations for long double arrays.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42508 91177308-0d34-0410-b5e6-96231b3b80d8
2007-08-02wrap some long lines. Major offenders that are left includeChris Lattner
gvn, gvnpre, dse, and predsimplify. To see these, use: make check-line-length git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40738 91177308-0d34-0410-b5e6-96231b3b80d8
2007-08-01More explicit keywords.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40673 91177308-0d34-0410-b5e6-96231b3b80d8
2007-07-31Use SCEVExpander::InsertCastOfTo instead of calling new IntToPtrInstDan Gohman
directly, because the insert point used by the SCEVExpander may vary from what LSR originally computes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40641 91177308-0d34-0410-b5e6-96231b3b80d8
2007-06-19Rename ScalarEvolution::deleteInstructionFromRecords toDan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37657 91177308-0d34-0410-b5e6-96231b3b80d8
2007-06-15Add a SCEV class and supporting code for sign-extend expressions.Dan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37591 91177308-0d34-0410-b5e6-96231b3b80d8
2007-06-07Use DominatorTree instead of ETForest.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37499 91177308-0d34-0410-b5e6-96231b3b80d8
2007-06-06Fix PR1495 and CodeGen/X86/2007-06-05-LSR-Dominator.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37454 91177308-0d34-0410-b5e6-96231b3b80d8
2007-05-19Handle negative strides much more optimally. This compiles ↵Chris Lattner
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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37252 91177308-0d34-0410-b5e6-96231b3b80d8
2007-05-11significantly improve debug output of lsrChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36996 91177308-0d34-0410-b5e6-96231b3b80d8
2007-05-04Use IntrinsicInst to test for prefetch instructions, which is ever soDan Gohman
slightly nicer than using CallInst with an extra check; thanks Chris. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36743 91177308-0d34-0410-b5e6-96231b3b80d8
2007-05-03Allow strength reduction to make use of addressing modes for theDan Gohman
address operand in a prefetch intrinsic. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36713 91177308-0d34-0410-b5e6-96231b3b80d8
2007-05-03Drop 'const'Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36662 91177308-0d34-0410-b5e6-96231b3b80d8
2007-05-02Use 'static const char' instead of 'static const int'.Devang Patel
Due to darwin gcc bug, one version of darwin linker coalesces static const int, which defauts PassID based pass identification. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36652 91177308-0d34-0410-b5e6-96231b3b80d8
2007-05-01Do not use typeinfo to identify pass in pass manager.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36632 91177308-0d34-0410-b5e6-96231b3b80d8
2007-04-23FixDevang Patel
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070423/048333.html git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36380 91177308-0d34-0410-b5e6-96231b3b80d8
2007-04-15Remove ImmediateDominator analysis. The same information can be obtained ↵Owen Anderson
from DomTree. A lot of code for constructing ImmediateDominator is now folded into DomTree construction. This is part of the ongoing work for PR217. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36063 91177308-0d34-0410-b5e6-96231b3b80d8
2007-04-13Now that codegen prepare isn't defeating me, I can finally fix what I setChris Lattner
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 :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35972 91177308-0d34-0410-b5e6-96231b3b80d8
2007-04-09switch LSR to use isLegalAddressingMode instead of other simpler hooksChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35837 91177308-0d34-0410-b5e6-96231b3b80d8
2007-04-07Completely purge DomSet. This is the (hopefully) final patch for PR1171.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35731 91177308-0d34-0410-b5e6-96231b3b80d8
2007-04-03split some code out into a helper functionChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35615 91177308-0d34-0410-b5e6-96231b3b80d8
2007-04-02allow -1 strides to reuse "1" strides.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35607 91177308-0d34-0410-b5e6-96231b3b80d8
2007-04-02Pass the type of the store access, not the type of the store, into theChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35592 91177308-0d34-0410-b5e6-96231b3b80d8
2007-04-01print the type of an inserted IV in -debug mode.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35563 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-26Look through bitcast when finding IVs. (Chris' patch really.)Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35347 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-20do not share old induction variables when this would result in invalidDale Johannesen
instructions (that would have to be split later) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35227 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-20Fix some VC++ warnings.Jeff Cohen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35224 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-20use types of loads and stores, not address, in CheckForIVReuseDale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35197 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-13Correct type info for isLegalAddressImmediate() check.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35086 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-12Use new TargetLowering addressing modes hooks.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35072 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-09Increment iterator now because IVUseShouldUsePostIncValue may removeDevang Patel
User from the list of I users. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35051 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-06Now LoopStrengthReduce is a LoopPass.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34984 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-02Finally get this patch right :)Reid Spencer
Replace expensive getZExtValue() == 0 calls with isZero() calls. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34861 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-02Dang, I've done that twice now! Undo previous commit.Reid Spencer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34860 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-02Use more efficient test for one value in a ConstantInt.Reid Spencer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34859 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-02Reverse a premature commital.Reid Spencer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34822 91177308-0d34-0410-b5e6-96231b3b80d8
2007-03-02Prefer non-virtual calls to ConstantInt::isZero over virtual calls toReid Spencer
Constant::isNullValue() in situations where it is possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34821 91177308-0d34-0410-b5e6-96231b3b80d8
2007-02-10Privatize StructLayout::MemberOffsets, adding an accessorChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34156 91177308-0d34-0410-b5e6-96231b3b80d8
2007-02-05Apply the VISIBILITY_HIDDEN field to the remaining anonymous classes inReid Spencer
the Transforms library. This reduces debug library size by 132 KB, debug binary size by 376 KB, and reduces link time for llvm tools slightly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33939 91177308-0d34-0410-b5e6-96231b3b80d8
2007-01-15rename Type::isIntegral to Type::isInteger, eliminating the old Type::isInteger.Chris Lattner
rename Type::getIntegralTypeMask to Type::getIntegerTypeMask. This makes naming much more consistent. For example, there are now no longer any instances of IntegerType that are not considered isInteger! :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33225 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-06-22 11:15:39 +0000