aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/GVN.cpp
AgeCommit message (Collapse)Author
2013-05-09[GVN] Split critical-edge on the fly, instead of postpone edge-splitting to nextShuxin Yang
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181532 91177308-0d34-0410-b5e6-96231b3b80d8
2013-05-03Decompose GVN::processNonLocalLoad() (about 400 LOC) into smaller helper ↵Shuxin Yang
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181047 91177308-0d34-0410-b5e6-96231b3b80d8
2013-05-02[GV] Remove dead code which is really difficult to decipher.Shuxin Yang
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@180951 91177308-0d34-0410-b5e6-96231b3b80d8
2013-03-12Change the order of the operands in patchAndReplaceAllUsesWith soDan Gohman
that they're more consistent with Value::replaceAllUsesWith. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176872 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-12Actually delete this code, since it's really not clear what it'sDan Gohman
trying to do. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175014 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-12Record PRE predecessors with a SmallVector instead of a DenseMap, andDan Gohman
avoid a second pred_iterator traversal. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175001 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-12When disabling PRE for a value is directly redundant with itselfDan Gohman
(through a loop), don't continue to iterate through the reamining predecessors. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174994 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-12Check that pointers are removed from maps before calling delete on the pointers,Dan Gohman
for tidiness' sake. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174988 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-12Minor code simplification.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174985 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-31Change GetPointerBaseWithConstantOffset's DataLayout argument from aDan Gohman
reference to a pointer, so that it can handle the case where DataLayout is not available and behave conservatively. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174024 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-02Move all of the header files which are involved in modelling the LLVM IRChandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171366 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-03Use the new script to sort the includes of every file under lib.Chandler Carruth
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. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-02Fix an obvious typo that causes an assertion failure when runningDuncan Sands
test/Transforms/GVN/rle.ll if the (currently disabled) check for a pointer type in getIntPtrType is turned on. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167285 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-29Remove a wrapper around getIntPtrType added to GVN by Hal in commit 166624 (theDuncan Sands
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166939 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-24Update GVN to support vectors of pointers.Hal Finkel
GVN will now generate ptrtoint instructions for vectors of pointers. Fixes PR14166. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166624 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-24Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow
address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166578 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-08Move TargetData to DataLayout.Micah Villmow
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165402 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-12Release build: guard dump functions withManman Ren
"#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163344. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163679 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-09Move spaces to the right places. No functionality change.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163485 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-06Release build: guard dump functions with "ifndef NDEBUG"Manman Ren
No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163344 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-29Make MemoryBuiltins aware of TargetLibraryInfo.Benjamin Kramer
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162841 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-24GVN: Fix quadratic runtime on the number of switch cases.Benjamin Kramer
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162559 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-16Teach GVN to reason about edges dominating uses. This allows it to handle casesRafael Espindola
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162023 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-10Constify some basic blocks, no functionality change.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161668 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-24Clean whitespaces.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160668 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-29Move llvm/Support/IRBuilder.h -> llvm/IRBuilder.hChandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159421 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-21refactor the MemoryBuiltin analysis:Nuno Lopes
- 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158919 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-16Move the Metadata merging methods from GVN and make them public in MDNode.Hal Finkel
There are other passes, BBVectorize specifically, that also need some of this functionality. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158605 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-04When gvn decides to replace an instruction with another, we have to patch theRafael Espindola
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157958 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-22Fix PR12858, a crash due to GVN's PRE not fully removing an instruction from theDuncan Sands
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157251 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-27Change recurse depth limit to uint32 to fix warning.David Blaikie
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155727 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-27Add an early bailout to IsValueFullyAvailableInBlock from deeply nested blocks.Mon P Wang
The limit is set to an arbitrary 1000 recursion depth to avoid stack overflow issues. <rdar://problem/11286839>. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155722 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-06Make GVN's propagateEquality non-recursive. No intended functionality change.Duncan Sands
The modifications are a lot more trivial than they appear to be in the diff! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154174 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-29Don't PRE compares.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153657 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-23When propagating equalities, eg replacing A with B in every basic blockDuncan Sands
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153323 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-11llvm::SwitchInstStepan Dyatkovskiy
Renamed methods caseBegin, caseEnd and caseDefault with case_begin, case_end, and case_default. Added some notes relative to case iterators. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152532 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-08Taken into account Duncan's comments for r149481 dated by 2nd Feb 2012:Stepan Dyatkovskiy
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152297 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-05This is not a common case, in fact it never happens!Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152027 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-05Replace the ad-hoc hashing in GVN with the new hashing infrastructure.Chandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152025 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-04Nick pointed out on IRC that GVN's propagateEquality wasn't propagatingDuncan Sands
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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152006 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-29Have GVN also do condition propagation when the right-hand side is notDuncan Sands
a constant. This fixes PR1768. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151713 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-27Micro-optimization, no functionality change.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151524 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-27The value numbering function is recursive, so it is possible for multiple newDuncan Sands
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151522 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-27When performing a conditional branch depending on the value of a comparisonDuncan Sands
%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%. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151517 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-24Teach GVN that x+y is the same as y+x and that x<y is the same as y>x.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151365 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-08Use Use::set rather than finding the operand number of the useDuncan Sands
and setting that. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150074 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-05Neaten up this method. Check that if there is only oneDuncan Sands
predecessor then it's Src. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149843 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-05Fix a thinko pointed out by Eli and the buildbots.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149839 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-05Reduce the number of dom queries made by GVN's conditional propagationDuncan Sands
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!). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149838 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-05Reduce the number of non-trivial domtree queries by about 1% whenDuncan Sands
compiling sqlite3, by only doing dom queries after the cheap check rather than interleaved with it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149836 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-14 17:19:41 +0000