summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/GVN.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Revert "Resurrect r191017 " GVN proceeds in the presence of dead code" plus ↵Bill Wendling2013-11-101-168/+6
| | | | | | | | | | | | | a fix to PR17307 & 17308." This causes PR17852. This reverts commit d93e8a06b2ca09ab18f390cd514b7443e2e571f7. Conflicts: test/Transforms/GVN/cond_br2.ll llvm-svn: 194348
* Fix GVN creating bitcast between address spacesMatt Arsenault2013-10-301-5/+7
| | | | llvm-svn: 193710
* Use more type helper functionsMatt Arsenault2013-10-211-1/+1
| | | | llvm-svn: 193109
* Resurrect r191017 " GVN proceeds in the presence of dead code" plus a fix to ↵Shuxin Yang2013-09-201-6/+168
| | | | | | | | | PR17307 & 17308. The problem of r191017 is that when GVN fabricate a val-number for a dead instruction (in order to make following expr-PRE happy), it forget to fabricate a leader-table entry for it as well. llvm-svn: 191118
* Revert r191017, it results in segmentation faults in Qt.Joerg Sonnenberger2013-09-201-164/+6
| | | | llvm-svn: 191104
* GVN proceeds in the presence of dead code.Shuxin Yang2013-09-191-6/+164
| | | | | | | | | | | | | | | | | | | | | | This is how it ignores the dead code: 1) When a dead branch target, say block B, is identified, all the blocks dominated by B is dead as well. 2) The PHIs of those blocks in dominance-frontier(B) is updated such that the operands corresponding to dead predecessors are replaced by "UndefVal". Using lattice's jargon, the "UndefVal" is the "Top" in essence. Phi node like this "phi(v1 bb1, undef xx)" will be optimized into "v1" if v1 is constant, or v1 is an instruction which dominate this PHI node. 3) When analyzing the availability of a load L, all dead mem-ops which L depends on disguise as a load which evaluate exactly same value as L. 4) The dead mem-ops will be materialized as "UndefVal" during code motion. llvm-svn: 191017
* Reimplement isPotentiallyReachable to make nocapture deduction much stronger.Nick Lewycky2013-07-271-0/+1
| | | | | | | | | | Adds unit tests for it too. Split BasicBlockUtils into an analysis-half and a transforms-half, and put the analysis bits into a new Analysis/CFG.{h,cpp}. Promote isPotentiallyReachable into llvm::isPotentiallyReachable and move it into Analysis/CFG. llvm-svn: 187283
* Use SmallVectorImpl::iterator/const_iterator instead of SmallVector to avoid ↵Craig Topper2013-07-041-2/+2
| | | | | | specifying the vector size. llvm-svn: 185606
* [GVN] Split critical-edge on the fly, instead of postpone edge-splitting to nextShuxin Yang2013-05-091-13/+39
| | | | | | | | | | iteration. This on step toward non-iterative GVN. My local hack suggests that getting rid of iteration will speedup GVN by 30%+ on a medium sized input (2k LOC, C++). I cannot explain why not 2x or more at this moment. llvm-svn: 181532
* Decompose GVN::processNonLocalLoad() (about 400 LOC) into smaller helper ↵Shuxin Yang2013-05-031-169/+194
| | | | | | | | | | | | | | functions. No function change. This function consists of following steps: 1. Collect dependent memory accesses. 2. Analyze availability. 3. Perform fully redundancy elimination, or 4. Perform PRE, depending on the availability Step 2, 3 and 4 are now moved to three helper routines. llvm-svn: 181047
* [GV] Remove dead code which is really difficult to decipher.Shuxin Yang2013-05-021-26/+2
| | | | | | | | | | | Actually it took me couple of hours trying to make sense of them and only to find they are dead code. I guess the original author used "allSingleSucc" to indicate if there are any critial edge emanating from some blocks, and tried to perform code motion (actually speculation) in the presence of these critical edges; but later on he/she changed mind and decided to perform edge-splitting first. llvm-svn: 180951
* Change the order of the operands in patchAndReplaceAllUsesWith soDan Gohman2013-03-121-5/+5
| | | | | | that they're more consistent with Value::replaceAllUsesWith. llvm-svn: 176872
* Actually delete this code, since it's really not clear what it'sDan Gohman2013-02-121-24/+0
| | | | | | trying to do. llvm-svn: 175014
* Record PRE predecessors with a SmallVector instead of a DenseMap, andDan Gohman2013-02-121-8/+9
| | | | | | avoid a second pred_iterator traversal. llvm-svn: 175001
* When disabling PRE for a value is directly redundant with itselfDan Gohman2013-02-121-0/+2
| | | | | | | (through a loop), don't continue to iterate through the reamining predecessors. llvm-svn: 174994
* Check that pointers are removed from maps before calling delete on the pointers,Dan Gohman2013-02-121-3/+3
| | | | | | for tidiness' sake. llvm-svn: 174988
* Minor code simplification.Dan Gohman2013-02-121-1/+1
| | | | llvm-svn: 174985
* Change GetPointerBaseWithConstantOffset's DataLayout argument from aDan Gohman2013-01-311-3/+3
| | | | | | | reference to a pointer, so that it can handle the case where DataLayout is not available and behave conservatively. llvm-svn: 174024
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-6/+6
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-6/+6
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Fix an obvious typo that causes an assertion failure when runningDuncan Sands2012-11-021-1/+1
| | | | | | | test/Transforms/GVN/rle.ll if the (currently disabled) check for a pointer type in getIntPtrType is turned on. llvm-svn: 167285
* Remove a wrapper around getIntPtrType added to GVN by Hal in commit 166624 (theDuncan Sands2012-10-291-14/+4
| | | | | | | | | wrapper returns a vector of integers when passed a vector of pointers) by having getIntPtrType itself return a vector of integers in this case. Outside of this wrapper, I didn't find anywhere in the codebase that was relying on the old behaviour for vectors of pointers, so give this a whirl through the buildbots. llvm-svn: 166939
* Update GVN to support vectors of pointers.Hal Finkel2012-10-241-20/+30
| | | | | | | GVN will now generate ptrtoint instructions for vectors of pointers. Fixes PR14166. llvm-svn: 166624
* Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow2012-10-241-4/+5
| | | | | | | | | address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. llvm-svn: 166578
* Move TargetData to DataLayout.Micah Villmow2012-10-081-15/+15
| | | | llvm-svn: 165402
* Release build: guard dump functions withManman Ren2012-09-121-1/+1
| | | | | | | | "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163344. llvm-svn: 163679
* Move spaces to the right places. No functionality change.Nick Lewycky2012-09-091-4/+4
| | | | llvm-svn: 163485
* Release build: guard dump functions with "ifndef NDEBUG"Manman Ren2012-09-061-0/+2
| | | | | | No functional change. llvm-svn: 163344
* Make MemoryBuiltins aware of TargetLibraryInfo.Benjamin Kramer2012-08-291-2/+2
| | | | | | | | | | | | | | | | This disables malloc-specific optimization when -fno-builtin (or -ffreestanding) is specified. This has been a problem for a long time but became more severe with the recent memory builtin improvements. Since the memory builtin functions are used everywhere, this required passing TLI in many places. This means that functions that now have an optional TLI argument, like RecursivelyDeleteTriviallyDeadFunctions, won't remove dead mallocs anymore if the TLI argument is missing. I've updated most passes to do the right thing. Fixes PR13694 and probably others. llvm-svn: 162841
* GVN: Fix quadratic runtime on the number of switch cases.Benjamin Kramer2012-08-241-2/+10
| | | | | | | | No intended behavior change. This was introduced in r162023. With the fixed algorithm a Release build of ARMInstPrinter.cpp goes from 16s to 10s on a 2011 MBP. llvm-svn: 162559
* Teach GVN to reason about edges dominating uses. This allows it to handle casesRafael Espindola2012-08-161-47/+48
| | | | | | | | | | | | | where some fact lake a=b dominates a use in a phi, but doesn't dominate the basic block itself. This feature could also be implemented by splitting critical edges, but at least with the current algorithm reasoning about the dominance directly is faster. The time for running "opt -O2" in the testcase in pr10584 is 1.003 times slower and on gcc as a single file it is 1.0007 times faster. llvm-svn: 162023
* Constify some basic blocks, no functionality change.Rafael Espindola2012-08-101-8/+8
| | | | llvm-svn: 161668
* Clean whitespaces.Nadav Rotem2012-07-241-133/+133
| | | | llvm-svn: 160668
* Move llvm/Support/IRBuilder.h -> llvm/IRBuilder.hChandler Carruth2012-06-291-11/+11
| | | | | | | | | | | | | | | | | This was always part of the VMCore library out of necessity -- it deals entirely in the IR. The .cpp file in fact was already part of the VMCore library. This is just a mechanical move. I've tried to go through and re-apply the coding standard's preferred header sort, but at 40-ish files, I may have gotten some wrong. Please let me know if so. I'll be committing the corresponding updates to Clang and Polly, and Duncan has DragonEgg. Thanks to Bill and Eric for giving the green light for this bit of cleanup. llvm-svn: 159421
* refactor the MemoryBuiltin analysis:Nuno Lopes2012-06-211-2/+2
| | | | | | | | | | | | - provide more extensive set of functions to detect library allocation functions (e.g., malloc, calloc, strdup, etc) - provide an API to compute the size and offset of an object pointed by Move a few clients (GVN, AA, instcombine, ...) to the new API. This implementation is a lot more aggressive than each of the custom implementations being replaced. Patch reviewed by Nick Lewycky and Chandler Carruth, thanks. llvm-svn: 158919
* Move the Metadata merging methods from GVN and make them public in MDNode.Hal Finkel2012-06-161-153/+3
| | | | | | | There are other passes, BBVectorize specifically, that also need some of this functionality. llvm-svn: 158605
* When gvn decides to replace an instruction with another, we have to patch theRafael Espindola2012-06-041-2/+200
| | | | | | | | | | | | replacement to make it at least as generic as the instruction being replaced. This includes: * dropping nsw/nuw flags * getting the least restrictive tbaa and fpmath metadata * merging ranges Fixes PR12979. llvm-svn: 157958
* Fix PR12858, a crash due to GVN's PRE not fully removing an instruction from theDuncan Sands2012-05-221-6/+12
| | | | | | | | | | | | leader table. That's because it wasn't expecting instructions to turn up as leader for a value number that is not its own, but equality propagation could create this situation. One solution is to have the leader table use a WeakVH but this slows down GVN by about 5%. Instead just have equality propagation not add instructions to the leader table, only constants and arguments. In theory this might cause GVN to run more (each time it changes something it runs again) but it doesn't seem to occur enough to cause a slow down. llvm-svn: 157251
* Change recurse depth limit to uint32 to fix warning.David Blaikie2012-04-271-1/+1
| | | | llvm-svn: 155727
* Add an early bailout to IsValueFullyAvailableInBlock from deeply nested blocks.Mon P Wang2012-04-271-3/+12
| | | | | | | The limit is set to an arbitrary 1000 recursion depth to avoid stack overflow issues. <rdar://problem/11286839>. llvm-svn: 155722
* Make GVN's propagateEquality non-recursive. No intended functionality change.Duncan Sands2012-04-061-98/+105
| | | | | | The modifications are a lot more trivial than they appear to be in the diff! llvm-svn: 154174
* Don't PRE compares.Jakob Stoklund Olesen2012-03-291-1/+8
| | | | | | | | | | | | CodeGenPrepare sinks compare instructions down to their uses to prevent live flags and predicate registers across basic blocks. PRE of a compare instruction prevents that, forcing the i1 compare result into a general purpose register. That is usually more expensive than the redundant compare PRE was trying to eliminate in the first place. llvm-svn: 153657
* When propagating equalities, eg replacing A with B in every basic blockDuncan Sands2012-03-231-0/+3
| | | | | | | | dominated by Root, check that B is available throughout the scope. This is obviously true (famous last words?) given the current logic, but the check may be helpful if more complicated reasoning is added one day. llvm-svn: 153323
* llvm::SwitchInstStepan Dyatkovskiy2012-03-111-1/+1
| | | | | | | Renamed methods caseBegin, caseEnd and caseDefault with case_begin, case_end, and case_default. Added some notes relative to case iterators. llvm-svn: 152532
* Taken into account Duncan's comments for r149481 dated by 2nd Feb 2012:Stepan Dyatkovskiy2012-03-081-3/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120130/136146.html Implemented CaseIterator and it solves almost all described issues: we don't need to mix operand/case/successor indexing anymore. Base iterator class is implemented as a template since it may be initialized either from "const SwitchInst*" or from "SwitchInst*". ConstCaseIt is just a read-only iterator. CaseIt is read-write iterator; it allows to change case successor and case value. Usage of iterator allows totally remove resolveXXXX methods. All indexing convertions done automatically inside the iterator's getters. Main way of iterator usage looks like this: SwitchInst *SI = ... // intialize it somehow for (SwitchInst::CaseIt i = SI->caseBegin(), e = SI->caseEnd(); i != e; ++i) { BasicBlock *BB = i.getCaseSuccessor(); ConstantInt *V = i.getCaseValue(); // Do something. } If you want to convert case number to TerminatorInst successor index, just use getSuccessorIndex iterator's method. If you want initialize iterator from TerminatorInst successor index, use CaseIt::fromSuccessorIndex(...) method. There are also related changes in llvm-clients: klee and clang. llvm-svn: 152297
* This is not a common case, in fact it never happens!Duncan Sands2012-03-051-4/+0
| | | | llvm-svn: 152027
* Replace the ad-hoc hashing in GVN with the new hashing infrastructure.Chandler Carruth2012-03-051-10/+13
| | | | | | | | | | | | | | | | | This implicitly fixes a nasty bug in the GVN hashing (that thankfully could only manifest as a performance bug): actually include the opcode in the hash. The old code started the hash off with the opcode, but then overwrote it with the type pointer. Since this is likely to be pretty hot (GVN being already pretty expensive) I've included a micro-optimization to just not bother with the varargs hashing if they aren't present. I can't measure any change in GVN performance due to this, even with a big test case like Duncan's sqlite one. Everything I see is in the noise floor. That said, this closes a loop hole for a potential scaling problem due to collisions if the opcode were the differentiating aspect of the expression. llvm-svn: 152025
* Nick pointed out on IRC that GVN's propagateEquality wasn't propagatingDuncan Sands2012-03-041-1/+11
| | | | | | | | | | equalities into phi node operands for which the equality is known to hold in the incoming basic block. That's because replaceAllDominatedUsesWith wasn't handling phi nodes correctly in general (that this didn't give wrong results was just luck: the specific way GVN uses replaceAllDominatedUsesWith precluded wrong changes to phi nodes). llvm-svn: 152006
* Have GVN also do condition propagation when the right-hand side is notDuncan Sands2012-02-291-11/+20
| | | | | | a constant. This fixes PR1768. llvm-svn: 151713
* Micro-optimization, no functionality change.Duncan Sands2012-02-271-7/+12
| | | | llvm-svn: 151524
OpenPOWER on IntegriCloud