aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Transforms
Commit message (Collapse)AuthorAgeFilesLines
* Second attempt at fixing the performance regressions introducedOwen Anderson2010-11-271-24/+55
| | | | | | | | | 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
* Treat a call of function pointer like a load of the pointer when consideringNick Lewycky2010-11-241-1/+6
| | | | | | | | 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
* Rename SimplifyDistributed to the more meaningfull name SimplifyByFactorizing.Duncan Sands2010-11-234-15/+15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120051 91177308-0d34-0410-b5e6-96231b3b80d8
* The srem -> urem transform is not safe for any divisor that's not a power of ↵Benjamin Kramer2010-11-231-11/+9
| | | | | | | | | | | 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
* Replace calls to ConstantFoldInstruction with calls to SimplifyInstructionDuncan Sands2010-11-232-11/+12
| | | | | | | | 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
* Constant folding here is pointless, because InstructionSimplifyDuncan Sands2010-11-231-8/+1
| | | | | | | | (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
* InstCombine: Reduce "X shift (A srem B)" to "X shift (A urem B)" iff B is ↵Benjamin Kramer2010-11-231-0/+15
| | | | | | | | | 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
* Propagate LeftDistributes and RightDistributes into their only uses.Duncan Sands2010-11-231-6/+4
| | | | | | | Stylistic improvement suggested by Frits van Bommel. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120026 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix typo pointed out by Frits van Bommel and Marius Wachtler.Duncan Sands2010-11-231-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120025 91177308-0d34-0410-b5e6-96231b3b80d8
* Exploit distributive laws (eg: And distributes over Or, Mul over Add, etc) in aDuncan Sands2010-11-234-42/+133
| | | | | | | | | | | | | 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
* duncan's spider sense was right, I completely reversed the conditionChris Lattner2010-11-231-8/+8
| | | | | | | 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
* InstCombine: Implement X - A*-B -> X + A*B.Benjamin Kramer2010-11-221-0/+9
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119984 91177308-0d34-0410-b5e6-96231b3b80d8
* If a GEP index simply advances by multiples of a type of zero size,Duncan Sands2010-11-221-14/+24
| | | | | | | then replace the index with zero. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119974 91177308-0d34-0410-b5e6-96231b3b80d8
* Move the "gep undef" -> "undef" transform from instcombine toDuncan Sands2010-11-221-3/+0
| | | | | | | InstructionSimplify. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119970 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't keep track of inserted phis in PromoteMemoryToRegister: the informationDuncan Sands2010-11-221-8/+3
| | | | | | | is never used. Patch by Cameron Zwarich. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119963 91177308-0d34-0410-b5e6-96231b3b80d8
* fix commentChris Lattner2010-11-211-1/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119948 91177308-0d34-0410-b5e6-96231b3b80d8
* rework some DSE paths to use the newly-public "getPointerDependencyFrom"Chris Lattner2010-11-211-46/+37
| | | | | | | | 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
* implement PR8576, deleting dead stores with intervening may-alias stores.Chris Lattner2010-11-211-3/+22
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119927 91177308-0d34-0410-b5e6-96231b3b80d8
* optimize:Chris Lattner2010-11-211-2/+72
| | | | | | | | | | | 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
* Implement PR8644: forwarding a memcpy value to a byval,Chris Lattner2010-11-211-44/+127
| | | | | | | | | | | | | 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
* Simplify code. No change in functionality.Benjamin Kramer2010-11-203-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119908 91177308-0d34-0410-b5e6-96231b3b80d8
* Document the new GVN number table structure.Owen Anderson2010-11-191-0/+12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119865 91177308-0d34-0410-b5e6-96231b3b80d8
* When folding addressing modes in CodeGenPrepare, attempt to look through PHI ↵Owen Anderson2010-11-191-3/+29
| | | | | | | | | | 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
* Factor code for testing whether replacing one value with anotherDuncan Sands2010-11-182-20/+23
| | | | | | | | | 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
* Completely rework the datastructure GVN uses to represent the value number ↵Owen Anderson2010-11-181-72/+86
| | | | | | | | | | | | | | | | | | | | | | | | 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
* slightly simplify code and substantially improve comment. Instead of Chris Lattner2010-11-181-20/+23
| | | | | | | 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
* remove a pointless restriction from memcpyopt. It wasChris Lattner2010-11-181-4/+7
| | | | | | | | | | | | | | 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
* remove another pointless noalias check: M is a memcpy, so theChris Lattner2010-11-181-2/+1
| | | | | | | 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
* use AA::isNoAlias instead of open coding it. Remove an extraneous noalias ↵Chris Lattner2010-11-181-11/+7
| | | | | | | | | | 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
* finish a thought.Chris Lattner2010-11-181-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119690 91177308-0d34-0410-b5e6-96231b3b80d8
* rearrange some code, splitting memcpy/memcpy optimizationChris Lattner2010-11-181-45/+56
| | | | | | | out of processMemCpy into its own function. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119687 91177308-0d34-0410-b5e6-96231b3b80d8
* allow eliminating an alloca that is just copied from an constant globalChris Lattner2010-11-181-3/+10
| | | | | | | | | 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
* enhance the "alloca is just a memcpy from constant global"Chris Lattner2010-11-181-0/+7
| | | | | | | | 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
* fix a small oversight in the "eliminate memcpy from constant global"Chris Lattner2010-11-181-3/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Move SCEV::dominates and properlyDominates to ScalarEvolution.Dan Gohman2010-11-171-13/+11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119570 91177308-0d34-0410-b5e6-96231b3b80d8
* Move SCEV::isLoopInvariant and hasComputableLoopEvolution to be memberDan Gohman2010-11-172-15/+15
| | | | | | | | 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
* Reference ScalarEvolution by name rather than directly in LICM,Dan Gohman2010-11-171-2/+1
| | | | | | | to avoid an unneeded dependence. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119557 91177308-0d34-0410-b5e6-96231b3b80d8
* InstCombine: Add a missing irem identity (X % X -> 0).Benjamin Kramer2010-11-171-0/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119538 91177308-0d34-0410-b5e6-96231b3b80d8
* Move some those Xor simplifications which don't require creating newDuncan Sands2010-11-171-31/+2
| | | | | | | | | 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
* Have InlineFunction use SimplifyInstruction rather thanDuncan Sands2010-11-171-9/+11
| | | | | | | | | | 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
* Have RemovePredecessorAndSimplify you SimplifyInstructionDuncan Sands2010-11-171-4/+4
| | | | | | | rather than hasConstantValue. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119457 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove dead code in GVN: now that SimplifyInstruction is calledDuncan Sands2010-11-171-43/+2
| | | | | | | | | | | 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
* Have a few places that want to simplify phi nodes use SimplifyInstructionDuncan Sands2010-11-165-13/+18
| | | | | | | 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
* If dom tree information is available, make it possible to passDuncan Sands2010-11-142-2/+2
| | | | | | | it to get better phi node simplification. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119055 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach InstructionSimplify about phi nodes. I chose to have it simplyDuncan Sands2010-11-141-2/+3
| | | | | | | | | | | 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
* Generalize the reassociation transform in SimplifyCommutative (now renamed toDuncan Sands2010-11-135-46/+128
| | | | | | | | | | | | | | | | | 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
* Have GVN simplify instructions as it goes. For example, considerDuncan Sands2010-11-121-18/+20
| | | | | | | | | | | | | | | | "%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
* Enhance DSE to handle the case where a free call makes more thanDan Gohman2010-11-121-12/+24
| | | | | | | | 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
* Add helper functions for computing the Location of load, store,Dan Gohman2010-11-114-24/+7
| | | | | | | and vaarg instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118845 91177308-0d34-0410-b5e6-96231b3b80d8
* Factor out Instruction::isSafeToSpeculativelyExecute's code forDan Gohman2010-11-111-14/+1
| | | | | | | | | | | | | 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.1 at 2025-06-10 00:43:23 +0000