aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/LoopStrengthReduce.cpp
AgeCommit message (Collapse)Author
2008-07-14Fix uninitialized use of the Changed variable.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53564 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-07Fix two serious LSR bugs.Evan Cheng
1. LSR runOnLoop is always returning false regardless if any transformation is made. 2. AddUsersIfInteresting can create new instructions that are added to DeadInsts. But there is a later early exit which prevents them from being freed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53193 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-23Fix spelling and grammar in a comment.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52648 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-22Improve LSR's dead-phi detection to handle use-def cyclesDan Gohman
with more than two nodes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52617 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-18Move LSR's private isZero function to a public SCEV memberDan Gohman
function, and make use of it in several places. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52463 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-16Refine the change in r52258 for avoiding use-before-def conditionsDan Gohman
when changing the stride of a comparison so that it's slightly more precise, by having it scan the instruction list to determine if there is a use of the condition after the point where the condition will be inserted. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52371 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-16Switch over to SetVector to ensure same order of iterations do not vary ↵Evan Cheng
across runs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52361 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-16Iterating over SmallPtrSet is not deterministic.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52339 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-13Protect ChangeCompareStride from situations in which it is possibleDan Gohman
for it to generate use-before-def IR, such as in this testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52258 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-11op_iterator-ify some loops, fix 80col violationsGabor Greif
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52226 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-24Remove x86.sse2.loadh.pd and x86.sse2.loadl.pd. These will be lowered into ↵Evan Cheng
load and shuffle instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51521 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-21When LSR is replacing an instruction, callDan Gohman
ScalarEvolution::deleteValueFromRecords on it before doing the replaceAllUsesWith, because ScalarEvolution looks at the instruction's users to find SCEV references to the instruction's SCEV object in its internal maps. Move all of LSR's loop-related state clearing after processing the loop and before cleaning up dead PHI nodes. This eliminates all of LSR's SCEV references just before the calls to ScalarEvolution::deleteValueFromRecords so that when ScalarEvolution drops its own SCEV references, the reference counts will reach zero and the SCEVs will be deleted immediately. These changes fix some compiler aborts involving ScalarEvolution holding onto and reusing SCEV objects for instructions that have been deleted. No regression test unfortunately; because the symptoms were due to dangling pointers, reduced testcases ended up being fairly arbitrary. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51359 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-20Refine the fix in r51169 to only apply when the operand val beingDan Gohman
replaced is a PHI. This prevents it from inserting uses before defs in the case that it isn't a PHI and it depends on other instructions later in the block. This fixes the 447.dealII regression on x86-64. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51292 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-15Fix a bug in LoopStrengthReduce that caused it to emit IR withDan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51169 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-13Clean up the use of static and anonymous namespaces. This turned upDan Gohman
several things that were neither in an anonymous namespace nor static but not intended to be global. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51017 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-14Minor whitespace and comment cleanups.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49671 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-06API changes for class Use size reduction, wave 1.Gabor Greif
Specifically, introduction of XXX::Create methods for Users that have a potentially variable number of Uses. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49277 91177308-0d34-0410-b5e6-96231b3b80d8
2008-03-19Remove dead options.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48556 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-29Use empty() instead of comparing size() with zero.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46514 91177308-0d34-0410-b5e6-96231b3b80d8
2007-12-29Remove attribution from file headers, per discussion on llvmdev.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45418 91177308-0d34-0410-b5e6-96231b3b80d8
2007-12-20Clean up previous patch: PHI uses should not prevent iv reuse if all other ↵Evan Cheng
uses are addresses. This trades a constant multiply for one fewer iv. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45251 91177308-0d34-0410-b5e6-96231b3b80d8
2007-12-19Allow iv reuse if the user is a PHI node which is in turn used as addresses.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45230 91177308-0d34-0410-b5e6-96231b3b80d8
2007-11-17Remove indeterminism from a loop. We think this willDale Johannesen
fix an occasional nonrepeatable bootstrap failure we've been seeing on Darwin. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44202 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-30At end of LSR, replace uses of now constant (as result of SplitCriticalEdge) ↵Evan Cheng
PHI node with the constant value. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43533 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-30It's not safe to tell SplitCriticalEdge to merge identical edges. It may ↵Evan Cheng
delete the phi instruction that's being processed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43524 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-29- Bug fixes.Evan Cheng
- Allow icmp rewrite using an iv / stride of a smaller integer type. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43480 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-29Update a comment to reflect the current code.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43463 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-29Remove an unused function argument.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43462 91177308-0d34-0410-b5e6-96231b3b80d8
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
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-01 22:22:26 +0000