summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils
Commit message (Collapse)AuthorAgeFilesLines
* [ValueTracking] Add parameters to isImpliedCondition; NFCSanjoy Das2015-11-061-1/+1
| | | | | | | | | | | | | | | | Summary: This change makes the `isImpliedCondition` interface similar to the rest of the functions in ValueTracking (in that it takes a DataLayout, AssumptionCache etc.). This is an NFC, intended to make a later diff less noisy. Depends on D14369 Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14391 llvm-svn: 252333
* DI: Reverse direction of subprogram -> function edge.Peter Collingbourne2015-11-051-3/+1
| | | | | | | | | | | | | | | | | | | | | | | Previously, subprograms contained a metadata reference to the function they described. Because most clients need to get or set a subprogram for a given function rather than the other way around, this created unneeded inefficiency. For example, many passes needed to call the function llvm::makeSubprogramMap() to build a mapping from functions to subprograms, and the IR linker needed to fix up function references in a way that caused quadratic complexity in the IR linking phase of LTO. This change reverses the direction of the edge by storing the subprogram as function-level metadata and removing DISubprogram's function field. Since this is an IR change, a bitcode upgrade has been provided. Fixes PR23367. An upgrade script for textual IR for out-of-tree clients is attached to the PR. Differential Revision: http://reviews.llvm.org/D14265 llvm-svn: 252219
* [SimplifyLibCalls] Use hasFloatVersion(). NFCI.Davide Italiano2015-11-051-15/+13
| | | | llvm-svn: 252186
* [SimplifyCFG] Tweak heuristic for merging conditional storesJames Molloy2015-11-051-7/+13
| | | | | | We were correctly skipping dbginfo intrinsics and terminators, but the initial bailout wasn't, causing it to bail out on almost any block. llvm-svn: 252152
* [SimplifyLibCalls] New transformation: tan(atan(x)) -> xDavide Italiano2015-11-041-1/+38
| | | | | | | | | | | | | | | | | | | | This is enabled only under -ffast-math. So, instead of emitting: 4007b0: 50 push %rax 4007b1: e8 8a fd ff ff callq 400540 <atanf@plt> 4007b6: 58 pop %rax 4007b7: e9 94 fd ff ff jmpq 400550 <tanf@plt> 4007bc: 0f 1f 40 00 nopl 0x0(%rax) for: float mytan(float x) { return tanf(atanf(x)); } we emit a single retq. Differential Revision: http://reviews.llvm.org/D14302 llvm-svn: 252098
* [SimplifyCFG] Merge conditional storesJames Molloy2015-11-041-3/+312
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | We can often end up with conditional stores that cannot be speculated. They can come from fairly simple, idiomatic code: if (c & flag1) *a = x; if (c & flag2) *a = y; ... There is no dominating or post-dominating store to a, so it is not legal to move the store unconditionally to the end of the sequence and cache the intermediate result in a register, as we would like to. It is, however, legal to merge the stores together and do the store once: tmp = undef; if (c & flag1) tmp = x; if (c & flag2) tmp = y; if (c & flag1 || c & flag2) *a = tmp; The real power in this optimization is that it allows arbitrary length ladders such as these to be completely and trivially if-converted. The typical code I'd expect this to trigger on often uses binary-AND with constants as the condition (as in the above example), which means the ending condition can simply be truncated into a single binary-AND too: 'if (c & (flag1|flag2))'. As in the general case there are bitwise operators here, the ladder can often be optimized further too. This optimization involves potentially increasing register pressure. Even in the simplest case, the lifetime of the first predicate is extended. This can be elided in some cases such as using binary-AND on constants, but not in the general case. Threading 'tmp' through all branches can also increase register pressure. The optimization as in this patch is enabled by default but kept in a very conservative mode. It will only optimize if it thinks the resultant code should be if-convertable, and additionally if it can thread 'tmp' through at least one existing PHI, so it will only ever in the worst case create one more PHI and extend the lifetime of a predicate. This doesn't trigger much in LNT, unfortunately, but it does trigger in a big way in a third party test suite. llvm-svn: 252051
* [SimplifyLibCalls] Add a new transformation: pow(exp(x), y) -> exp(x*y)Davide Italiano2015-11-031-0/+26
| | | | | | | | | | | | | | | | | | | | | | | | This one is enabled only under -ffast-math (due to rounding/overflows) but allows us to emit shorter code. Before (on FreeBSD x86-64): 4007f0: 50 push %rax 4007f1: f2 0f 11 0c 24 movsd %xmm1,(%rsp) 4007f6: e8 75 fd ff ff callq 400570 <exp2@plt> 4007fb: f2 0f 10 0c 24 movsd (%rsp),%xmm1 400800: 58 pop %rax 400801: e9 7a fd ff ff jmpq 400580 <pow@plt> 400806: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1) 40080d: 00 00 00 After: 4007b0: f2 0f 59 c1 mulsd %xmm1,%xmm0 4007b4: e9 87 fd ff ff jmpq 400540 <exp2@plt> 4007b9: 0f 1f 80 00 00 00 00 nopl 0x0(%rax) Differential Revision: http://reviews.llvm.org/D14045 llvm-svn: 251976
* [SimplifyLibCalls] Remove variables that are not used. NFC.Davide Italiano2015-11-021-7/+2
| | | | llvm-svn: 251852
* [SimplifyLibCalls] Merge two if statements. NFC.Davide Italiano2015-11-021-4/+1
| | | | llvm-svn: 251845
* Preserve load alignment and dereferenceable metadata during some transformationsArtur Pilipenko2015-11-022-1/+12
| | | | | | | | Reviewed By: hfinkel Differential Revision: http://reviews.llvm.org/D13953 llvm-svn: 251809
* Simplify a check. NFC.Davide Italiano2015-11-011-2/+2
| | | | llvm-svn: 251757
* [SimplifyLibCalls] Factor out other common code.Davide Italiano2015-10-311-21/+10
| | | | llvm-svn: 251754
* [SimplifyLibCalls] Remove dead code.Davide Italiano2015-10-311-6/+0
| | | | llvm-svn: 251737
* Recommit r251680 (also need to update clang test)Dehao Chen2015-10-301-11/+12
| | | | | | | | | | | | | | | | | | | Update the discriminator assignment algorithm * If a scope has already been assigned a discriminator, do not reassign a nested discriminator for it. * If the file and line both match, even if the column does not match, we should assign a new discriminator for the stmt. original code: ; #1 int foo(int i) { ; #2 if (i == 3 || i == 5) return 100; else return 99; ; #3 } ; i == 3: discriminator 0 ; i == 5: discriminator 2 ; return 100: discriminator 1 ; return 99: discriminator 3 llvm-svn: 251689
* Revert r251680:Dehao Chen2015-10-301-12/+11
| | | | | | | | | | | | | | | | | | | Update the discriminator assignment algorithm * If a scope has already been assigned a discriminator, do not reassign a nested discriminator for it. * If the file and line both match, even if the column does not match, we should assign a new discriminator for the stmt. original code: ; #1 int foo(int i) { ; #2 if (i == 3 || i == 5) return 100; else return 99; ; #3 } ; i == 3: discriminator 0 ; i == 5: discriminator 2 ; return 100: discriminator 1 ; return 99: discriminator 3 llvm-svn: 251685
* Update the discriminator assignment algorithmDehao Chen2015-10-301-11/+12
| | | | | | | | | | | | | | | | | * If a scope has already been assigned a discriminator, do not reassign a nested discriminator for it. * If the file and line both match, even if the column does not match, we should assign a new discriminator for the stmt. original code: ; #1 int foo(int i) { ; #2 if (i == 3 || i == 5) return 100; else return 99; ; #3 } ; i == 3: discriminator 0 ; i == 5: discriminator 2 ; return 100: discriminator 1 ; return 99: discriminator 3 llvm-svn: 251680
* clang-format lib/Transforms/Utils/AddDiscriminators.cppDehao Chen2015-10-291-12/+11
| | | | llvm-svn: 251656
* [SimplifyCFG] Constant fold a branch implied by it's incoming edgePhilip Reames2015-10-291-0/+13
| | | | | | | | | | | The most common use case is when eliminating redundant range checks in an example like the following: c = a[i+1] + a[i]; Note that all the smarts of the transform (the implication engine) is already in ValueTracking and is tested directly through InstructionSimplify. Differential Revision: http://reviews.llvm.org/D13040 llvm-svn: 251596
* [SimplifyLibCalls] Factor out common unsafe-math checks.Davide Italiano2015-10-291-29/+23
| | | | llvm-svn: 251595
* [SimplifyCFG] Don't DCE catchret because the successor is unreachableDavid Majnemer2015-10-271-2/+1
| | | | | | | CatchReturnInst has side-effects: it runs a destructor. This destructor could conceivably run forever/call exit/etc. and should not be removed. llvm-svn: 251461
* [SimplifyLibCalls] Use range-based loop. No functional change.Davide Italiano2015-10-271-4/+2
| | | | llvm-svn: 251383
* Move the canonical header to the top of its matching cpp file as per coding ↵David Blaikie2015-10-261-1/+2
| | | | | | | | | convention This ensures that the header will be verified to be standalone (and avoid mistakes like the one fixed in r251178) llvm-svn: 251326
* [LCSSA] Unbreak build, don't reuse L; NFCSanjoy Das2015-10-251-2/+2
| | | | | | The build broke in r251248. llvm-svn: 251251
* [LCSSA] Use range for loops; NFCSanjoy Das2015-10-251-28/+21
| | | | llvm-svn: 251248
* Revert rL251061 [SimplifyCFG] Extend SimplifyResume to handle phi of trivial ↵Chen Li2015-10-231-65/+11
| | | | | | landing pad. llvm-svn: 251149
* [Inliner] Don't inline through callsites with operand bundlesSanjoy Das2015-10-231-0/+4
| | | | | | | | | | | | | | | | Summary: This change teaches the LLVM inliner to not inline through callsites with unknown operand bundles. Currently all operand bundles are "unknown" operand bundles but in the near future we will add support for inlining through some select kinds of operand bundles. Reviewers: reames, chandlerc, majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14001 llvm-svn: 251141
* [SimplifyCFG] Extend SimplifyResume to handle phi of trivial landing pad.Chen Li2015-10-221-11/+65
| | | | | | | | | | | | Summary: Currently SimplifyResume can convert an invoke instruction to a call instruction if its landing pad is trivial. In practice we could have several invoke instructions with trivial landing pads and share a common rethrow block, and in the common rethrow block, all the landing pads join to a phi node. The patch extends SimplifyResume to check the phi of landing pad and their incoming blocks. If any of them is trivial, remove it from the phi node and convert the invoke instruction to a call instruction. Reviewers: hfinkel, reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13718 llvm-svn: 251061
* [SimplifyCFG] Don't use-after-free an SSA valueDavid Majnemer2015-10-211-1/+2
| | | | | | | | | SimplifyTerminatorOnSelect didn't consider the possibility that the condition might be related to one of PHI nodes. This fixes PR25267. llvm-svn: 250922
* Revert 250343 and 250344Philip Reames2015-10-151-117/+0
| | | | | | | | | | | | | | | | | | | | | | | | Turns out this approach is buggy. In discussion about follow on work, Sanjoy pointed out that we could be subject to circular logic problems. Consider: if (i u< L) leave() if ((i + 1) u< L) leave() print(a[i] + a[i+1]) If we know that L is less than UINT_MAX, we could possible prove (in a control dependent way) that i + 1 does not overflow. This gives us: if (i u< L) leave() if ((i +nuw 1) u< L) leave() print(a[i] + a[i+1]) If we now do the transform this patch proposed, we end up with: if ((i +nuw 1) u< L) leave_appropriately() print(a[i] + a[i+1]) That would be a miscompile when i==-1. The problem here is that the control dependent nuw bits got used to prove something about the first condition. That's obviously invalid. This won't happen today, but since I plan to enhance LVI/CVP with exactly that transform at some point in the not too distant future... llvm-svn: 250430
* [SimplifyCFG] Speculatively flatten CFG based on profiling metadataPhilip Reames2015-10-141-7/+124
| | | | | | | | | | If we have a series of branches which are all unlikely to fail, we can possibly combine them into a single check on the fastpath combined with a bit of dispatch logic on the slowpath. We don't want to do this unconditionally since it requires speculating instructions past a branch, but if the profiling metadata on the branch indicates profitability, this can reduce the number of checks needed along the fast path. The canonical example this is trying to handle is removing the second bounds check implied by the Java code: a[i] + a[i+1]. Note that it can currently only do so for really simple conditions and the values of a[i] can't be used anywhere except in the addition. (i.e. the load has to have been sunk already and not prevent speculation.) I plan on extending this transform over the next few days to handle alternate sequences. Differential Revision: http://reviews.llvm.org/D13070 llvm-svn: 250343
* [InlineFunction] Correctly inline TerminatePadInstDavid Majnemer2015-10-131-5/+10
| | | | | | | | | | | We forgot to append the terminatepad's arguments which resulted in us treating the old terminatepad as an argument to the new terminatepad causing us to crash immediately. Instead, add the old terminatepad's arguments to the new terminatepad. This fixes PR25155. llvm-svn: 250234
* TransformUtils: Remove implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-10-1325-254/+253
| | | | | | | | | | | Continuing the work from last week to remove implicit ilist iterator conversions. First related commit was probably r249767, with some more motivation in r249925. This edition gets LLVMTransformUtils compiling without the implicit conversions. No functional change intended. llvm-svn: 250142
* GlobalOpt does not treat externally_initialized globals correctlyOliver Stannard2015-10-121-0/+4
| | | | | | | | GlobalOpt currently merges stores into the initialisers of internal, externally_initialized globals, but should not do so as the value of the global may change between the initialiser and any code in the module being run. llvm-svn: 250035
* [PlaceSafeopints] Extract out `callsGCLeafFunction`, NFCSanjoy Das2015-10-081-0/+17
| | | | | | | | | | | | | Summary: This will be used in a later change to RewriteStatepointsForGC. Reviewers: reames, swaroop.sridhar Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13490 llvm-svn: 249777
* [IndVars] Preserve LCSSA in `eliminateIdentitySCEV`Sanjoy Das2015-10-071-0/+3
| | | | | | | | | | | | | | | | | | | | Summary: After r249211, SCEV can see through some LCSSA phis. Add a `replacementPreservesLCSSAForm` check before replacing uses of these phi nodes with a simplified use of the induction variable to avoid breaking LCSSA. Fixes 25047. Depends on D13460. Reviewers: atrick, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13461 llvm-svn: 249575
* Fix Clang-tidy modernize-use-nullptr warnings in source directories and ↵Hans Wennborg2015-10-062-4/+4
| | | | | | | | | | generated files; other minor cleanups. Patch by Eugene Zelenko! Differential Revision: http://reviews.llvm.org/D13321 llvm-svn: 249482
* [IndVars] Don't break dominance in `eliminateIdentitySCEV`Sanjoy Das2015-10-062-10/+34
| | | | | | | | | | | | | | | | | | | | | | | Summary: After r249211, `getSCEV(X) == getSCEV(Y)` does not guarantee that X and Y are related in the dominator tree, even if X is an operand to Y (I've included a toy example in comments, and a real example as a test case). This commit changes `SimplifyIndVar` to require a `DominatorTree`. I don't think this is a problem because `ScalarEvolution` requires it anyway. Fixes PR25051. Depends on D13459. Reviewers: atrick, hfinkel Subscribers: joker.eph, llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D13460 llvm-svn: 249471
* [IndVars] Extract out eliminateIdentitySCEV, NFCSanjoy Das2015-10-061-4/+14
| | | | | | | | | | | Summary: Reflow a comment while at it. Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13459 llvm-svn: 249470
* inariant.group handling in GVNPiotr Padlewski2015-10-022-7/+17
| | | | | | | | | | | | The most important part required to make clang devirtualization works ( ͡°͜ʖ ͡°). The code is able to find non local dependencies, but unfortunatelly because the caller can only handle local dependencies, I had to add some restrictions to look for dependencies only in the same BB. http://reviews.llvm.org/D12992 llvm-svn: 249196
* [SimplifyLibCalls] Fix instruction misplacement in string/memory libcall ↵Bruno Cardoso Lopes2015-10-011-2/+6
| | | | | | | | | | | | | | | | | | optimization When trying to optimize fortified library functions use the right location to insert new instructions in order to preserve correct def-use order. This fixes an issue where a misplaced instruction definition would happen to be *after* one of its use after a RAUW, forming invalid IR. This behavior was introduced by r227250. Differential Revision: http://reviews.llvm.org/D13301 rdar://problem/22802369 llvm-svn: 249092
* Fix debug info with SafeStack.Evgeniy Stepanov2015-09-301-3/+11
| | | | llvm-svn: 248933
* Move dbg.declare intrinsics when merging and replacing allocas.Evgeniy Stepanov2015-09-291-4/+4
| | | | | | | | | | | | | | Place new and update dbg.declare calls immediately after the corresponding alloca. Current code in replaceDbgDeclareForAlloca puts the new dbg.declare at the end of the basic block. LLVM codegen has problems emitting debug info in a situation when dbg.declare appears after all uses of the variable. This usually kinda works for inlining and ASan (two users of this function) but not for SafeStack (see the pending change in http://reviews.llvm.org/D13178). llvm-svn: 248769
* Improve performance of SimplifyInstructionsInBlockFiona Glaser2015-09-281-12/+60
| | | | | | | | | | | | | | | | | | | | 1. Use a worklist, not a recursive approach, to avoid needless revisitation and being repeatedly forced to jump back to the start of the BB if a handle is invalidated. 2. Only insert operands to the worklist if they become unused after a dead instruction is removed, so we don’t have to visit them again in most cases. 3. Use a SmallSetVector to track the worklist. 4. Instead of pre-initting the SmallSetVector like in DeadCodeEliminationPass, only put things into the worklist if they have to be revisited after the first run-through. This minimizes how much the actual SmallSetVector gets used, which saves a lot of time. llvm-svn: 248727
* [EH] Create removeUnwindEdge utilityJoseph Tremoulet2015-09-272-99/+55
| | | | | | | | | | | | | | | | | Summary: Factor the code that rewrites invokes to calls and rewrites WinEH terminators to their "unwind to caller" equivalents into a helper in Utils/Local, and use it in the three places I'm aware of that need to do this. Reviewers: andrew.w.kaylor, majnemer, rnk Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13152 llvm-svn: 248677
* [Unroll] When completely unrolling the loop, replace conditinal branches ↵Michael Zolotukhin2015-09-231-2/+3
| | | | | | | | | | | | | | | with unconditional. Nothing is expected to change, except we do less redundant work in clean-up. Reviewers: hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12951 llvm-svn: 248444
* [Inline] Use AssumptionCache from the right FunctionVedant Kumar2015-09-231-1/+1
| | | | | | | | | | | | | | | This changes the behavior of AddAligntmentAssumptions to match its comment. I.e, prove the asserted alignment in the context of the caller, not the callee. Thanks to Mehdi Amini for seeing the issue here! Also to Artur Pilipenko who also saw a fix for the issue. rdar://22521387 Differential Revision: http://reviews.llvm.org/D12997 llvm-svn: 248390
* [SCEV] Introduce ScalarEvolution::getOne and getZero.Sanjoy Das2015-09-231-2/+1
| | | | | | | | | | | | | | | | | | Summary: It is fairly common to call SE->getConstant(Ty, 0) or SE->getConstant(Ty, 1); this change makes such uses a little bit briefer. I've refactored the call sites I could find easily to use getZero / getOne. Reviewers: hfinkel, majnemer, reames Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12947 llvm-svn: 248362
* [LoopUtils,LV] Propagate fast-math flags on generated FCmp instructionsJames Molloy2015-09-211-0/+7
| | | | | | | | | We're currently losing any fast-math flags when synthesizing fcmps for min/max reductions. In LV, make sure we copy over the scalar inst's flags. In LoopUtils, we know we only ever match patterns with hasUnsafeAlgebra, so apply that to any synthesized ops. llvm-svn: 248201
* don't repeat function names in comments; NFCSanjay Patel2015-09-161-29/+24
| | | | llvm-svn: 247813
* more space; NFCSanjay Patel2015-09-151-0/+1
| | | | llvm-svn: 247699
OpenPOWER on IntegriCloud