aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar
AgeCommit message (Collapse)Author
2012-06-13Allow SROA to look at a vector type and see if the offset is out of range to ↵Pete Cooper
be replaced with a scalar access git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158407 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-13It is possible for several constants which aren't individually absorbing toDuncan Sands
combine to the absorbing element. Thanks to nbjoerg on IRC for pointing this out. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158399 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-13When linearizing a multiplication, return at once if we see a factor of zero,Duncan Sands
since then the entire expression must equal zero (similarly for other operations with an absorbing element). With this in place a bunch of reassociate code for handling constants is dead since it is all taken care of when linearizing. No intended functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158398 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-12Use DenseMap as SmallMap workaround rather than std::map, at Chandler's request.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158371 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-12Use std::map rather than SmallMap because SmallMap assumes that the value hasDuncan Sands
POD type, causing memory corruption when mapping to APInts with bitwidth > 64. Merge another crash testcase into crash.ll while there. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158369 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-12Now that Reassociate's LinearizeExprTree can look through arbitrary expressionDuncan Sands
topologies, it is quite possible for a leaf node to have huge multiplicity, for example: x0 = x*x, x1 = x0*x0, x2 = x1*x1, ... rapidly gives a value which is x raised to a vast power (the multiplicity, or weight, of x). This patch fixes the computation of weights by correctly computing them no matter how big they are, rather than just overflowing and getting a wrong value. It turns out that the weight for a value never needs more bits to represent than the value itself, so it is enough to represent weights as APInts of the same bitwidth and do the right overflow-avoiding dance steps when computing weights. As a side-effect it reduces the number of multiplies needed in some cases of large powers. While there, in view of external uses (eg by the vectorizer) I made LinearizeExprTree static, pushing the rank computation out into users. This is progress towards fixing PR13021. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158358 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-08Reapply commit 158073 with a fix (the testcase was already committed). TheDuncan Sands
problem was that by moving instructions around inside the function, the pass could accidentally move the iterator being used to advance over the function too. Fix this by only processing the instruction equal to the iterator, and leaving processing of instructions that might not be equal to the iterator to later (later = after traversing the basic block; it could also wait until after traversing the entire function, but this might make the sets quite big). Original commit message: Grab-bag of reassociate tweaks. Unify handling of dead instructions and instructions to reoptimize. Exploit this to more systematically eliminate dead instructions (this isn't very useful in practice but is convenient for analysing some testcase I am working on). No need for WeakVH any more: use an AssertingVH instead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158226 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-08BoundsChecking: add support for ConstantPointerNull. fixes a bunch of ↵Nuno Lopes
instrumentation failures in loops with reallocs git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158210 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-08Revert commit 158073 while waiting for a fix. The issue is that reassociateDuncan Sands
can move instructions within the instruction list. If the instruction just happens to be the one the basic block iterator is pointing to, and it is moved to a different basic block, then we get into an infinite loop due to the iterator running off the end of the basic block (for some reason this doesn't fire any assertions). Original commit message: Grab-bag of reassociate tweaks. Unify handling of dead instructions and instructions to reoptimize. Exploit this to more systematically eliminate dead instructions (this isn't very useful in practice but is convenient for analysing some testcase I am working on). No need for WeakVH any more: use an AssertingVH instead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158199 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-06Grab-bag of reassociate tweaks. Unify handling of dead instructions andDuncan Sands
instructions to reoptimize. Exploit this to more systematically eliminate dead instructions (this isn't very useful in practice but is convenient for analysing some testcase I am working on). No need for WeakVH any more: use an AssertingVH instead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158073 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-06-02Fix typos found by http://github.com/lyda/misspell-checkBenjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157885 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-01BoundsChecking: fix a bug when the handling of recursive PHIs failed and ↵Nuno Lopes
could leave dangling references in the cache add regression tests for this problem. Can already compile & run: PHP, PCRE, and ICU (i.e., all the software I tried) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157822 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-31add -bounds-checking-multiple-traps option to make one trap BB per checkNuno Lopes
disabled by default for now; we can discusse the default value (& name) later git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157777 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-31revamp BoundsChecking considerably:Nuno Lopes
- compute size & offset at the same time. The side-effects of this are that we now support negative GEPs. It's now approaching a phase that it can be reused by other passes (e.g., lowering of the objectsize intrinsic) - use APInt throughout to handle wrap-arounds - add support for PHI instrumentation - add a cache (required for recursive PHIs anyway) - remove hoisting support for now, since it was wrong in a few cases sorry for the churn here.. tests will follow soon. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157775 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-31Enhance the sinking code to handle diamond patterns. Patch byDuncan Sands
Carlo Alberto Ferraris. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157736 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-29bounds checking:Nuno Lopes
- hoist checks out of loops where SCEV is smart enough - add additional statistics to measure how much we loose for not supporting interprocedural and pointers loaded from memory git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157649 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-27Reimplement the intrinsic verifier to use the same table as ↵Chris Lattner
Intrinsic::getDefinition, making it stronger and more sane. Delete the code from tblgen that produced the old code. Besides being a path forward in intrinsic sanity, this also eliminates a bunch of machine generated code that was compiled into Function.o git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157545 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-26Since commit 157467, if reassociate isn't actually going to change an expressionDuncan Sands
then it doesn't alter the instructions composing it, however it would continue to move the instructions to just before the expression root. Ensure it doesn't move them either, so now it really does nothing if there is nothing to do. That commit also ensured that nsw etc flags weren't cleared if the expression was not being changed. Tweak this a bit so that it doesn't clear flags on the initial part of a computation either if that part didn't change but later bits did. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157518 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-26Move this debug statement earlier so it is easy to see the order inDuncan Sands
which operands come flying out of the linearization stage. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157512 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-25bounds checking: add support for byval argumentsNuno Lopes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157498 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-25boundschecking:Nuno Lopes
add support for select add experimental support for alloc_size metadata git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157481 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-25Make the reassociation pass more powerful so that it can handle expressionsDuncan Sands
with arbitrary topologies (previously it would give up when hitting a diamond in the use graph for example). The testcase from PR12764 is now reduced from a pile of additions to the optimal 1617*%x0+208. In doing this I changed the previous strategy of dropping all uses for expression leaves to one of dropping all but one use. This works out more neatly (but required a bunch of tweaks) and is also safer: some recently fixed bugs during recursive linearization were because the linearization code thinks it completely owns a node if it has no uses outside the expression it is linearizing. But if the node was also in another expression that had been linearized (and thus all uses of the node from that expression dropped) then the conclusion that it is completely owned by the expression currently being linearized is wrong. Keeping one use from within each linearized expression avoids this kind of mistake. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157467 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-23BoundsChecking: add a couple of simple tests and fix a bug in branch emitionNuno Lopes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157329 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-22address some of John Criswell's commentsNuno Lopes
teach computeAllocSize about realloc, reallocf, and valloc git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157298 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-22hopefully fix the CMake build. sorry for breakageNuno Lopes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157264 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-22add a new pass to instrument loads and stores for run-time bounds checkingNuno Lopes
move EmitGEPOffset from InstCombine to Transforms/Utils/Local.h (a draft of this) patch reviewed by Andrew, thanks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157261 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-05-21Mark an unreachable region of code with llvm_unreachable.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157197 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-20Do not pass an invalid domtree to SimplifyInstruction fromPeter Collingbourne
LoopUnswitch. Fixes PR12887. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157140 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-19Do not eliminate allocas whose alignment exceeds that of thePeter Collingbourne
copied-in constant, as a subsequent user may rely on over alignment. Fixes PR12885. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157134 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-18Fix replacing all the users of objc weak runtime routinesDan Gohman
when deleting them. rdar://11434915. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157080 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-15Teach SimplifyLibCalls about stpcpy.David Majnemer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156815 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-14Move the capture analysis from MemoryDependencyAnalysis to a more general placeChad Rosier
so that it can be reused in MemCpyOptimizer. This analysis is needed to remove an unnecessary memcpy when returning a struct into a local variable. rdar://11341081 PR12686 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156776 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-10Teach DeadStoreElimination to eliminate exit-block stores with phi addresses.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156558 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-10teach DSE and isInstructionTriviallyDead() about callocNuno Lopes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156553 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-09Fix the objc_storeStrong recognizer to stop before walking off theDan Gohman
end of a basic block if there's no store. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156520 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-09Remove unused variable to get rid of warning.Craig Topper
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156466 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-08Miscellaneous accumulated cleanups.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156445 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-08Fix objc_storeStrong pattern matching to catch a potential use of theDan Gohman
old value after the store but before it is released. This fixes rdar:/11116986. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156442 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-08Calling ReassociateExpression recursively is extremely dangerous since it willDuncan Sands
replace the operands of expressions with only one use with undef and generate a new expression for the original without using RAUW to update the original. Thus any copies of the original expression held in a vector may end up referring to some bogus value - and using a ValueHandle won't help since there is no RAUW. There is already a mechanism for getting the effect of recursion non-recursively: adding the value to be recursed on to RedoInsts. But it wasn't being used systematically. Have various places where recursion had snuck in at some point use the RedoInsts mechanism instead. Fixes PR12169. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156379 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-07Teach reassociate to commute FMul's and FAdd's in order to canonicalize the ↵Owen Anderson
order of their operands across instructions. This allows for greater CSE opportunities. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156323 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-06Switch the select to branch transformation on by default.Benjamin Kramer
The primitive conservative heuristic seems to give a slight overall improvement while not regressing stuff. Make it available to wider testing. If you notice any speed regressions (or significant code size regressions) let me know! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156258 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-05CodeGenPrepare: Add a transform to turn selects into branches in some cases.Benjamin Kramer
This came up when a change in block placement formed a cmov and slowed down a hot loop by 50%: ucomisd (%rdi), %xmm0 cmovbel %edx, %esi cmov is a really bad choice in this context because it doesn't get branch prediction. If we emit it as a branch, an out-of-order CPU can do a better job (if the branch is predicted right) and avoid waiting for the slow load+compare instruction to finish. Of course it won't help if the branch is unpredictable, but those are really rare in practice. This patch uses a dumb conservative heuristic, it turns all cmovs that have one use and a direct memory operand into branches. cmovs usually save some code size, so we disable the transform in -Os mode. In-Order architectures are unlikely to benefit as well, those are included in the "predictableSelectIsExpensive" flag. It would be better to reuse branch probability info here, but BPI doesn't support select instructions currently. It would make sense to use the same heuristics as the if-converter pass, which does the opposite direction of this transform. Test suite shows a small improvement here and there on corei7-level machines, but the actual results depend a lot on the used microarchitecture. The transformation is currently disabled by default and available by passing the -enable-cgp-select2branch flag to the code generator. Thanks to Chandler for the initial test case to him and Evan Cheng for providing me with comments and test-suite numbers that were more stable than mine :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156234 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-04Add 'landingpad' instructions to the list of instructions to ignore.Bill Wendling
Also combine the code in the 'assert' statement. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156155 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-04A pile of long over-due refactorings here. There are some very, *very*Chandler Carruth
minor behavior changes with this, but nothing I have seen evidence of in the wild or expect to be meaningful. The real goal is unifying our logic and simplifying the interfaces. A summary of the changes follows: - Make 'callIsSmall' actually accept a callsite so it can handle intrinsics, and simplify callers appropriately. - Nuke a completely bogus declaration of 'callIsSmall' that was still lurking in InlineCost.h... No idea how this got missed. - Teach the 'isInstructionFree' about the various more intelligent 'free' heuristics that got added to the inline cost analysis during review and testing. This mostly surrounds int->ptr and ptr->int casts. - Switch most of the interesting parts of the inline cost analysis that were essentially computing 'is this instruction free?' to use the code metrics routine instead. This way we won't keep duplicating logic. All of this is motivated by the desire to allow other passes to compute a roughly equivalent 'cost' metric for a particular basic block as the inline cost analysis. Sadly, re-using the same analysis for both is really messy because only the actual inline cost analysis is ever going to go to the contortions required for simplification, SROA analysis, etc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156140 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-02Whitespace cleanup.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156034 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-02The value held in the vector may be RAUW'ed by some of the canonicalizationBill Wendling
methods. Use a weak value handle to keep up with this. PR12245 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155984 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-01An instruction in a loop is not guaranteed to be executed just because the loopNick Lewycky
has no exit blocks. Fixes PR12706! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155884 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-30Second attempt at PR12573:Bill Wendling
Allow the "SplitCriticalEdge" function to split the edge to a landing pad. If the pass is *sure* that it thinks it knows what it's doing, then it may go ahead and specify that the landing pad can have its critical edge split. The loop unswitch pass is one of these passes. It will split the critical edges of all edges coming from a loop to a landing pad not within the loop. Doing so will retain important loop analysis information, such as loop simplify. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155817 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-04 19:53:42 +0000