summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/GVN.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* The value numbering function is recursive, so it is possible for multiple newDuncan Sands2012-02-271-2/+2
| | | | | | | | value numbers to be assigned when calculating any particular value number. Enhance the logic that detects new value numbers to take this into account, for a tiny compile time speedup. Fix a comment typo while there. llvm-svn: 151522
* When performing a conditional branch depending on the value of a comparisonDuncan Sands2012-02-271-4/+62
| | | | | | | | | %cmp (eg: A==B) we already replace %cmp with "true" under the true edge, and with "false" under the false edge. This change enhances this to replace the negated compare (A!=B) with "false" under the true edge and "true" under the false edge. Reported to improve perlbench results by 1%. llvm-svn: 151517
* Teach GVN that x+y is the same as y+x and that x<y is the same as y>x.Duncan Sands2012-02-241-1/+16
| | | | llvm-svn: 151365
* Use Use::set rather than finding the operand number of the useDuncan Sands2012-02-081-6/+3
| | | | | | and setting that. llvm-svn: 150074
* Neaten up this method. Check that if there is only oneDuncan Sands2012-02-051-3/+3
| | | | | | predecessor then it's Src. llvm-svn: 149843
* Fix a thinko pointed out by Eli and the buildbots.Duncan Sands2012-02-051-1/+1
| | | | llvm-svn: 149839
* Reduce the number of dom queries made by GVN's conditional propagationDuncan Sands2012-02-051-31/+9
| | | | | | | | | | | | logic by half: isOnlyReachableViaThisEdge was trying to be clever and handle the case of a branch to a basic block which is contained in a loop. This costs a domtree lookup and is completely useless due to GVN's position in the pass pipeline: all loops have preheaders at this point, which means it is enough for isOnlyReachableViaThisEdge to check that Dst has only one predecessor. (I checked this theoretical argument by running over the entire nightly testsuite, and indeed it is so!). llvm-svn: 149838
* Reduce the number of non-trivial domtree queries by about 1% whenDuncan Sands2012-02-051-15/+17
| | | | | | | compiling sqlite3, by only doing dom queries after the cheap check rather than interleaved with it. llvm-svn: 149836
* SwitchInst refactoring.Stepan Dyatkovskiy2012-02-011-2/+2
| | | | | | | | | | | | | | | | | The purpose of refactoring is to hide operand roles from SwitchInst user (programmer). If you want to play with operands directly, probably you will need lower level methods than SwitchInst ones (TerminatorInst or may be User). After this patch we can reorganize SwitchInst operands and successors as we want. What was done: 1. Changed semantics of index inside the getCaseValue method: getCaseValue(0) means "get first case", not a condition. Use getCondition() if you want to resolve the condition. I propose don't mix SwitchInst case indexing with low level indexing (TI successors indexing, User's operands indexing), since it may be dangerous. 2. By the same reason findCaseValue(ConstantInt*) returns actual number of case value. 0 means first case, not default. If there is no case with given value, ErrorIndex will returned. 3. Added getCaseSuccessor method. I propose to avoid usage of TerminatorInst::getSuccessor if you want to resolve case successor BB. Use getCaseSuccessor instead, since internal SwitchInst organization of operands/successors is hidden and may be changed in any moment. 4. Added resolveSuccessorIndex and resolveCaseIndex. The main purpose of these methods is to see how case successors are really mapped in TerminatorInst. 4.1 "resolveSuccessorIndex" was created if you need to level down from SwitchInst to TerminatorInst. It returns TerminatorInst's successor index for given case successor. 4.2 "resolveCaseIndex" converts low level successors index to case index that curresponds to the given successor. Note: There are also related compatability fix patches for dragonegg, klee, llvm-gcc-4.0, llvm-gcc-4.2, safecode, clang. llvm-svn: 149481
* Increase the initial vector size to be equivalent to the size of the DepsBill Wendling2012-01-311-2/+2
| | | | | | vector. This potentially saves a resizing. llvm-svn: 149369
* Cache the size of the vector instead of calling .size() all over the place.Bill Wendling2012-01-311-5/+5
| | | | llvm-svn: 149368
* Typo.Chad Rosier2012-01-301-1/+1
| | | | llvm-svn: 149289
* Typo.Chad Rosier2012-01-301-1/+1
| | | | llvm-svn: 149275
* Propagate TargetLibraryInfo throughout ConstantFolding.cpp and Chad Rosier2011-12-011-2/+7
| | | | | | | InstructionSimplify.cpp. Other fixups as needed. Part of rdar://10500969 llvm-svn: 145559
* Don't replace all dominated uses if there is only one use, since thatDuncan Sands2011-10-151-4/+9
| | | | | | use can't be dominated, saving one domtree lookup. llvm-svn: 142066
* Enhance the memdep interface so that users can tell the difference between a ↵Eli Friedman2011-10-131-10/+10
| | | | | | | | dependency which cannot be calculated and a path reaching the entry point of the function. This patch introduces isNonFuncLocal, which replaces isUnknown in some cases. Patch by Xiaoyi Guo. llvm-svn: 141896
* Teach GVN to also propagate switch cases. For example, in this codeDuncan Sands2011-10-071-31/+59
| | | | | | | | | | | | | | switch (n) { case 27: do_something(x); ... } the call do_something(x) will be replaced with do_something(27). In gcc-as-one-big-file this results in the removal of about 500 lines of bitcode (about 0.02%), so has about 1/10 of the effect of propagating branch conditions. llvm-svn: 141360
* GVN does simple propagation of conditions: when it sees a conditionalDuncan Sands2011-10-051-14/+111
| | | | | | | | | | | | | | | | | | | branch "br i1 %x, label %if_true, label %if_false" then it replaces "%x" with "true" in places only reachable via the %if_true arm, and with "false" in places only reachable via the %if_false arm. Except that actually it doesn't: if value numbering shows that %y is equal to %x then, yes, %y will be turned into true/false in this way, but any occurrences of %x itself are not transformed. Fix this. What's more, it's often the case that %x is an equality comparison such as "%x = icmp eq %A, 0", in which case every occurrence of %A that is only reachable via the %if_true arm can be replaced with 0. Implement this and a few other variations on this theme. This reduces the number of lines of LLVM IR in "GCC as one big file" by 0.2%. It has a bigger impact on Ada code, typically reducing the number of lines of bitcode by around 0.4% by removing repeated compiler generated checks. Passes the LLVM nightly testsuite and the Ada ACATS testsuite. llvm-svn: 141177
* Generalize GVN's conditional propagation logic slightly:Duncan Sands2011-10-051-4/+29
| | | | | | | | it's OK for the false/true destination to have multiple predecessors as long as the extra ones are dominated by the branch destination. llvm-svn: 141176
* Stop emitting instructions with the name "tmp" they eat up memory and have ↵Benjamin Kramer2011-09-271-6/+4
| | | | | | | | to be uniqued, without any benefit. If someone prefers %tmp42 to %42, run instnamer. llvm-svn: 140634
* Compare type size instead of type _store_ size to make sure that BitCastInstJakub Staszak2011-09-021-2/+2
| | | | | | will be valid. This fixes PR10820. llvm-svn: 139005
* Atomic load/store handling for the passes using memdep (GVN, DSE, memcpyopt).Eli Friedman2011-08-171-3/+3
| | | | llvm-svn: 137888
* Disable PRE for landing pads.Bill Wendling2011-08-171-2/+14
| | | | | | | | PRE needs the landing pads to have their critical edges split. Doing this for a landing pad is non-trivial. Abandon the attempt to perform PRE when we come across a landing pad. (Reviewed by Owen!) llvm-svn: 137876
* Convert ConstantExpr::getGetElementPtr andJay Foad2011-07-211-2/+2
| | | | | | ConstantExpr::getInBoundsGetElementPtr to use ArrayRef. llvm-svn: 135673
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-181-16/+16
| | | | llvm-svn: 135375
* Added recognition for signed add/sub/mul with overflow intrinsics to GVN as ↵Lang Hames2011-07-091-0/+3
| | | | | | per Chris and Frits suggestion. llvm-svn: 134777
* Make GVN look through extractvalues for recognised intrinsics. GVN can then ↵Lang Hames2011-07-081-7/+54
| | | | | | CSE ops that match values produced by the intrinsics. llvm-svn: 134677
* Make better use of the PHINode API.Jay Foad2011-06-201-4/+9
| | | | | | | | Change various bits of code to make better use of the existing PHINode API, to insulate them from forthcoming changes in how PHINodes store their operands. llvm-svn: 133434
* Add "unknown" results for memdep, which mean "I don't know whether a ↵Eli Friedman2011-06-151-8/+24
| | | | | | dependence for the given instruction exists in the given block". This cleans up all the existing hacks in memdep which represent this concept by returning clobber with various unrelated instructions. llvm-svn: 133031
* fix PR9841 by having GVN not process dead loads. This wasChris Lattner2011-05-221-0/+5
| | | | | | | causing it to get into infinite loops when it would widen a load (which can necessarily leave around dead loads). llvm-svn: 131847
* Preserve line number information.Devang Patel2011-05-171-0/+1
| | | | llvm-svn: 131482
* Set debug loc for new load instruction.Devang Patel2011-05-171-0/+3
| | | | llvm-svn: 131481
* Set debug loc for new instructions.Devang Patel2011-05-041-3/+3
| | | | llvm-svn: 130895
* improve comment.Chris Lattner2011-04-281-1/+6
| | | | llvm-svn: 130426
* final step needed to resolve PR6627, which allows us to flatten the code down toChris Lattner2011-04-281-3/+7
| | | | | | | | | | | | a nice and tidy: %x1 = load i32* %0, align 4 %1 = icmp eq i32 %x1, 1179403647 br i1 %1, label %if.then, label %if.end instead of doing lots of loads and branches. May the FreeBSD bootloader long fit in its allocated space. llvm-svn: 130416
* code cleanups only.Chris Lattner2011-04-281-36/+32
| | | | llvm-svn: 130414
* centralize "marking for deletion" into a helper function. Pass GVN around to Chris Lattner2011-04-281-52/+56
| | | | | | static functions instead of passing around tons of random ivars. llvm-svn: 130403
* Promote toErase to be an ivar of the GVN class.Chris Lattner2011-04-281-39/+35
| | | | llvm-svn: 130401
* teach GVN to widen integer loads when they are overaligned, when doing an Chris Lattner2011-04-281-20/+123
| | | | | | | | | | | wider load would allow elimination of subsequent loads, and when the wider load is still a native integer type. This eliminates a ton of loads on various benchmarks involving struct fields, though it is somewhat hobbled by clang not being very aggressive about field alignment. This is yet another step along the way towards resolving PR6627. llvm-svn: 130390
* Improve the bail-out predicate to really only kick in when phiChris Lattner2011-04-261-1/+2
| | | | | | | translation fails. We were bailing out in some cases that would cause us to miss GVN'ing some non-local cases away. llvm-svn: 130206
* Enhance MemDep: When alias analysis returns a partial alias result,Chris Lattner2011-04-261-24/+78
| | | | | | | | | | | | | | | | | | | | | | | | | | return it as a clobber. This allows GVN to do smart things. Enhance GVN to be smart about the case when a small load is clobbered by a larger overlapping load. In this case, forward the value. This allows us to compile stuff like this: int test(void *P) { int tmp = *(unsigned int*)P; return tmp+*((unsigned char*)P+1); } into: _test: ## @test movl (%rdi), %ecx movzbl %ch, %eax addl %ecx, %eax ret which has one load. We already handled the case where the smaller load was from a must-aliased base pointer. llvm-svn: 130180
* Remove PHINode::reserveOperandSpace(). Instead, add a parameter toJay Foad2011-03-301-2/+1
| | | | | | PHINode::Create() giving the (known or expected) number of operands. llvm-svn: 128537
* (Almost) always call reserveOperandSpace() on newly created PHINodes.Jay Foad2011-03-301-2/+3
| | | | llvm-svn: 128535
* Give GetUnderlyingObject a TargetData, to keep it in syncDan Gohman2011-01-241-1/+1
| | | | | | | | | | | with BasicAA's DecomposeGEPExpression, which recently began using a TargetData. This fixes PR8968, though the testcase is awkward to reduce. Also, update several off GetUnderlyingObject's users which happen to have a TargetData handy to pass it in. llvm-svn: 124134
* Remove the PR8954 workaround.Jakob Stoklund Olesen2011-01-111-4/+0
| | | | llvm-svn: 123288
* Dial back the speculative fix for PR8954 a bit, so that we only recompute ↵Cameron Zwarich2011-01-111-1/+3
| | | | | | | | dominators once at the beginning of GVN instead of once per iteration. llvm-svn: 123278
* Attempt to fix the bootstrap buildbot. Rafael says this works for him on ↵Cameron Zwarich2011-01-111-0/+1
| | | | | | x86-64 Linux. llvm-svn: 123270
* update memdep when an instruction is deleted. This code isn'tChris Lattner2011-01-111-2/+5
| | | | | | | actually reached in the testcase in PR8954, but it's safe and good practice. llvm-svn: 123224
* Fix FoldSingleEntryPHINodes to update memdep and AA when it deletesChris Lattner2011-01-111-2/+2
| | | | | | | | | | phi nodes. It is called from MergeBlockIntoPredecessor which is called from GVN, which claims to preserve these. I'm skeptical that this is the actual problem behind PR8954, but this is a stab in the right direction. llvm-svn: 123222
* Don't bother value numbering instructions with void types in GVN. In theory ↵Owen Anderson2011-01-041-0/+4
| | | | | | | | | this should allow us to insert fewer things into the value numbering maps, but any speedup is beneath the noise threshold on my machine on 403.gcc. llvm-svn: 122844
OpenPOWER on IntegriCloud