aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms
AgeCommit message (Collapse)Author
2010-11-19Document the new GVN number table structure.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119865 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19When folding addressing modes in CodeGenPrepare, attempt to look through PHI ↵Owen Anderson
nodes if all the operands of the PHI are equivalent. This allows CodeGenPrepare to undo unprofitable PRE transforms. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119853 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-18Factor code for testing whether replacing one value with anotherDuncan Sands
preserves LCSSA form out of ScalarEvolution and into the LoopInfo class. Use it to check that SimplifyInstruction simplifications are not breaking LCSSA form. Fixes PR8622. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119727 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-18Completely rework the datastructure GVN uses to represent the value number ↵Owen Anderson
to leader mapping. Previously, this was a tree of hashtables, and a query recursed into the table for the immediate dominator ad infinitum if the initial lookup failed. This led to really bad performance on tall, narrow CFGs. We can instead replace it with what is conceptually a multimap of value numbers to leaders (actually represented by a hashtable with a list of Value*'s as the value type), and then determine which leader from that set to use very cheaply thanks to the DFS numberings maintained by DominatorTree. Because there are typically few duplicates of a given value, this scan tends to be quite fast. Additionally, we use a custom linked list and BumpPtr allocation to avoid any unnecessary allocation in representing the value-side of the multimap. This change brings with it a 15% (!) improvement in the total running time of GVN on 403.gcc, which I think is pretty good considering that includes all the "real work" being done by MemDep as well. The one downside to this approach is that we can no longer use GVN to perform simple conditional progation, but that seems like an acceptable loss since we now have LVI and CorrelatedValuePropagation to pick up the slack. If you see conditional propagation that's not happening, please file bugs against LVI or CVP. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119714 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-18slightly simplify code and substantially improve comment. Instead of Chris Lattner
saying "it would be bad", give an example of what is going on. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119695 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-18remove a pointless restriction from memcpyopt. It wasChris Lattner
refusing to optimize two memcpy's like this: copy A <- B copy C <- A if it couldn't prove that noalias(B,C). We can eliminate the copy by producing a memmove instead of memcpy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119694 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-18remove another pointless noalias check: M is a memcpy, so theChris Lattner
source and dest are known to not overlap. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119692 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-18use AA::isNoAlias instead of open coding it. Remove an extraneous noalias ↵Chris Lattner
check: there is no need to check to see if the source and dest of a memcpy are noalias, behavior is undefined if not. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119691 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-18finish a thought.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119690 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-18rearrange some code, splitting memcpy/memcpy optimizationChris Lattner
out of processMemCpy into its own function. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119687 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-18allow eliminating an alloca that is just copied from an constant globalChris Lattner
if it is passed as a byval argument. The byval argument will just be a read, so it is safe to read from the original global instead. This allows us to promote away the %agg.tmp alloca in PR8582 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119686 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-18enhance the "alloca is just a memcpy from constant global"Chris Lattner
to ignore calls that obviously can't modify the alloca because they are readonly/readnone. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119683 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-18fix a small oversight in the "eliminate memcpy from constant global"Chris Lattner
optimization. If the alloca that is "memcpy'd from constant" also has a memcpy from *it*, ignore it: it is a load. We now optimize the testcase to: define void @test2() { %B = alloca %T %a = bitcast %T* @G to i8* %b = bitcast %T* %B to i8* call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %a, i64 124, i32 4, i1 false) call void @bar(i8* %b) ret void } previously we would generate: define void @test() { %B = alloca %T %b = bitcast %T* %B to i8* %G.0 = getelementptr inbounds %T* @G, i32 0, i32 0 %tmp3 = load i8* %G.0, align 4 %G.1 = getelementptr inbounds %T* @G, i32 0, i32 1 %G.15 = bitcast [123 x i8]* %G.1 to i8* %1 = bitcast [123 x i8]* %G.1 to i984* %srcval = load i984* %1, align 1 %B.0 = getelementptr inbounds %T* %B, i32 0, i32 0 store i8 %tmp3, i8* %B.0, align 4 %B.1 = getelementptr inbounds %T* %B, i32 0, i32 1 %B.12 = bitcast [123 x i8]* %B.1 to i8* %2 = bitcast [123 x i8]* %B.1 to i984* store i984 %srcval, i984* %2, align 1 call void @bar(i8* %b) ret void } git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119682 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-17Move SCEV::dominates and properlyDominates to ScalarEvolution.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119570 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-17Move SCEV::isLoopInvariant and hasComputableLoopEvolution to be memberDan Gohman
functions of ScalarEvolution, in preparation for memoization and other optimizations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119562 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-17Reference ScalarEvolution by name rather than directly in LICM,Dan Gohman
to avoid an unneeded dependence. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119557 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-17InstCombine: Add a missing irem identity (X % X -> 0).Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119538 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-17Move some those Xor simplifications which don't require creating newDuncan Sands
instructions out of InstCombine and into InstructionSimplify. While there, introduce an m_AllOnes pattern to simplify matching with integers and vectors with all bits equal to one. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119536 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-17Have InlineFunction use SimplifyInstruction rather thanDuncan Sands
hasConstantValue. I was leery of using SimplifyInstruction while the IR was still in a half-baked state, which is the reason for delaying the simplification until the IR is fully cooked. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119494 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-17Have RemovePredecessorAndSimplify you SimplifyInstructionDuncan Sands
rather than hasConstantValue. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119457 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-17Remove dead code in GVN: now that SimplifyInstruction is calledDuncan Sands
systematically, CollapsePhi will always return null here. Note that CollapsePhi did an extra check, isSafeReplacement, which the SimplifyInstruction logic does not do. I think that check was bogus - I guess we will soon find out! (It was originally added in commit 41998 without a testcase). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119456 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-16Have a few places that want to simplify phi nodes use SimplifyInstructionDuncan Sands
rather than calling hasConstantValue. No intended functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119352 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-14If dom tree information is available, make it possible to passDuncan Sands
it to get better phi node simplification. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119055 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-14Teach InstructionSimplify about phi nodes. I chose to have it simplyDuncan Sands
offload the work to hasConstantValue rather than do something more complicated (such handling mutually recursive phis) because (1) it is not clear it is worth it; and (2) if it is worth it, maybe such logic would be better placed in hasConstantValue. Adjust some GVN tests which are now cleaned up much further (eg: all phi nodes are removed). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119043 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-13Generalize the reassociation transform in SimplifyCommutative (now renamed toDuncan Sands
SimplifyAssociativeOrCommutative) "(A op C1) op C2" -> "A op (C1 op C2)", which previously was only done if C1 and C2 were constants, to occur whenever "C1 op C2" simplifies (a la InstructionSimplify). Since the simplifying operand combination can no longer be assumed to be the right-hand terms, consider all of the possible permutations. When compiling "gcc as one big file", transform 2 (i.e. using right-hand operands) fires about 4000 times but it has to be said that most of the time the simplifying operands are both constants. Transforms 3, 4 and 5 each fired once. Transform 6, which is an existing transform that I didn't change, never fired. With this change, the testcase is now optimized perfectly with one run of instcombine (previously it required instcombine + reassociate + instcombine, and it may just have been luck that this worked). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119002 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-12Have GVN simplify instructions as it goes. For example, considerDuncan Sands
"%z = %x and %y". If GVN can prove that %y equals %x, then it turns this into "%z = %x and %x". With the new code, %z will be replaced with %x everywhere (and then deleted). Previously %z would be value numbered too, which is a waste of time. Also, while a clever value numbering algorithm would give %z the same value number as %x, our current one doesn't do so (at least I don't think it does). The new logic has an essentially equivalent effect to what you would get if %z was given the same value number as %x, i.e. it should make value numbering smarter. While there, get hold of target data once at the start rather than a gazillion times all over the place. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118923 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-12Enhance DSE to handle the case where a free call makes more thanDan Gohman
one store dead. This is especially noticeable in SingleSource/Benchmarks/Shootout/objinst. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118875 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-11Add helper functions for computing the Location of load, store,Dan Gohman
and vaarg instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118845 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-11Factor out Instruction::isSafeToSpeculativelyExecute's code forDan Gohman
testing for dereferenceable pointers into a helper function, isDereferenceablePointer. Teach it how to reason about GEPs with simple non-zero indices. Also eliminate ArgumentPromtion's IsAlwaysValidPointer, which didn't check for weak externals or out of range gep indices. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118840 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-11TBAA-enable ArgumentPromotion.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118804 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-11Make Sink tbaa-aware.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118788 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-11It's safe to sink some instructions which are not safe to speculativelyDan Gohman
execute. Make Sink's predicate more precise. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118787 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-10Enhance GVN to do more precise alias queries for non-local memoryDan Gohman
references. For example, this allows gvn to eliminate the load in this example: void foo(int n, int* p, int *q) { p[0] = 0; p[1] = 1; if (n) { *q = p[0]; } } git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118714 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-10Use getValueOperand() and getPointerOperand() on load and storeDan Gohman
instructions instead of hard-coding operand numbers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118698 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-10Add a doesAccessArgPointees helper function, and update code to useDan Gohman
it, and to be consistent. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118692 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-10Factor out the code for testing whether a function accessesDan Gohman
arbitrary memory into a helper function, and adjust some comments. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118687 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-10When checking that the necessary bits are zero inDale Johannesen
order to reduce ((x<<30)>>24) to x<<6, check the correct bits. PR 8547. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118665 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-10Make ModRefBehavior a lattice. Use this to clean up AliasAnalysisDan Gohman
chaining and simplify FunctionAttrs' GetModRefBehavior logic. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118660 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-09Teach FunctionAttrs about the VAArg instruction.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118627 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-09Use the AliasAnalysis interface to determine how a Function accessesDan Gohman
memory. This isn't a real improvement with present day AliasAnalysis implementations; it's mainly for consistency. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118624 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-09Teach LICM and AliasSetTracker about AccessesArgumentsReadonly.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118618 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-09Teach FunctionAttrs about AccessesArgumentsReadonly.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118617 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-08Fix a thinko that Duncan spotted.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118430 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-08Make FunctionAttrs TBAA-aware.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118417 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-08Extend the AliasAnalysis::pointsToConstantMemory interface to allow itDan Gohman
to optionally look for constant or local (alloca) memory. Teach BasicAliasAnalysis::pointsToConstantMemory to look through Select and Phi nodes, and to support looking for local memory. Remove FunctionAttrs' PointsToLocalOrConstantMemory function, now that AliasAnalysis knows all the tricks that it knew. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118412 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-08Make FunctionAttrs use AliasAnalysis::getModRefBehavior, now that itDan Gohman
knows about intrinsic functions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118410 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-03Rename PointsToLocalMemory to PointsToLocalOrConstantMemory to makeDuncan Sands
the code more self-documenting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118171 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-02Let the -inline-threshold command line argument take precedence over theJakob Stoklund Olesen
threshold given to createFunctionInliningPass(). Both opt -O3 and clang would silently ignore the -inline-threshold option. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118117 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-01When folding away a (shl (shr)) pair, we need to check that the bits that ↵Owen Anderson
will BECOME the low bits are zero, not that the current low bits are zero. Fixes <rdar://problem/8606771>. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117953 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-30Now that the MallocInst no longer exists, this workaround forDuncan Sands
it claiming not to have side-effects is no longer needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117789 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-02 11:10:44 +0000