aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms
AgeCommit message (Collapse)Author
2010-11-27Second attempt at fixing the performance regressions introducedOwen Anderson
by my recent GVN improvement. Looking through a single layer of PHI nodes when attempting to sink GEPs, we need to iteratively look through arbitrary PHI nests. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120202 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-24Treat a call of function pointer like a load of the pointer when consideringNick Lewycky
whether the pointer can be replaced with the global variable it is a copy of. Fixes PR8680. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120126 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-23Rename SimplifyDistributed to the more meaningfull name SimplifyByFactorizing.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120051 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-23The srem -> urem transform is not safe for any divisor that's not a power of ↵Benjamin Kramer
two. E.g. -5 % 5 is 0 with srem and 1 with urem. Also addresses Frits van Bommel's comments. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120049 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-23Replace calls to ConstantFoldInstruction with calls to SimplifyInstructionDuncan Sands
in two places that are really interested in simplified instructions, not constants. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120044 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-23Constant folding here is pointless, because InstructionSimplifyDuncan Sands
(which does constant folding and more) is called a few lines later. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120042 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-23InstCombine: Reduce "X shift (A srem B)" to "X shift (A urem B)" iff B is ↵Benjamin Kramer
positive. This allows to transform the rem in "1 << ((int)x % 8);" to an and. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120028 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-23Propagate LeftDistributes and RightDistributes into their only uses.Duncan Sands
Stylistic improvement suggested by Frits van Bommel. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120026 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-23Fix typo pointed out by Frits van Bommel and Marius Wachtler.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120025 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-23Exploit distributive laws (eg: And distributes over Or, Mul over Add, etc) in aDuncan Sands
fairly systematic way in instcombine. Some of these cases were already dealt with, in which case I removed the existing code. The case of Add has a bunch of funky logic which covers some of this plus a few variants (considers shifts to be a form of multiplication), which I didn't touch. The simplification performed is: A*B+A*C -> A*(B+C). The improvement is to do this in cases that were not already handled [such as A*B-A*C -> A*(B-C), which was reported on the mailing list], and also to do it more often by not checking for "only one use" if "B+C" simplifies. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120024 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-23duncan's spider sense was right, I completely reversed the conditionChris Lattner
on this instcombine xform. This fixes a miscompilation of 403.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119988 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-22InstCombine: Implement X - A*-B -> X + A*B.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119984 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-22If a GEP index simply advances by multiples of a type of zero size,Duncan Sands
then replace the index with zero. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119974 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-22Move the "gep undef" -> "undef" transform from instcombine toDuncan Sands
InstructionSimplify. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119970 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-22Don't keep track of inserted phis in PromoteMemoryToRegister: the informationDuncan Sands
is never used. Patch by Cameron Zwarich. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119963 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-21fix commentChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119948 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-21rework some DSE paths to use the newly-public "getPointerDependencyFrom"Chris Lattner
method in MemDep instead of inserting an instruction, doing a query, then removing it. Neither operation is effectively cached. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119930 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-21implement PR8576, deleting dead stores with intervening may-alias stores.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119927 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-21optimize:Chris Lattner
void a(int x) { if (((1<<x)&8)==0) b(); } into "x != 3", which occurs over 100 times in 403.gcc but in no other program in llvm-test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119922 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-21Implement PR8644: forwarding a memcpy value to a byval,Chris Lattner
allowing the memcpy to be eliminated. Unfortunately, the requirements on byval's without explicit alignment are really weak and impossible to predict in the mid-level optimizer, so this doesn't kick in much with current frontends. The fix is to change clang to set alignment on all byval arguments. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119916 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-20Simplify code. No change in functionality.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119908 91177308-0d34-0410-b5e6-96231b3b80d8
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
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-06-24 16:52:55 +0000