summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [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
* Preserve load alignment and dereferenceable metadata during some transformationsArtur Pilipenko2015-11-021-1/+3
| | | | | | | | Reviewed By: hfinkel Differential Revision: http://reviews.llvm.org/D13953 llvm-svn: 251809
* [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
* [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
* Revert rL251061 [SimplifyCFG] Extend SimplifyResume to handle phi of trivial ↵Chen Li2015-10-231-65/+11
| | | | | | landing pad. llvm-svn: 251149
* [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
* TransformUtils: Remove implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-10-131-47/+49
| | | | | | | | | | | 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
* inariant.group handling in GVNPiotr Padlewski2015-10-021-6/+3
| | | | | | | | | | | | 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
* [EH] Create removeUnwindEdge utilityJoseph Tremoulet2015-09-271-99/+18
| | | | | | | | | | | | | | | | | 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
* more space; NFCSanjay Patel2015-09-151-0/+1
| | | | llvm-svn: 247699
* Remove gcc warning when comparing an unsigned var for >= 0Filipe Cabecinhas2015-09-101-1/+1
| | | | llvm-svn: 247352
* [SimplifyCFG] Use known bits to eliminate dead switch defaultsPhilip Reames2015-09-101-3/+9
| | | | | | | | | | | | This is a follow up to http://reviews.llvm.org/D11995 implementing the suggestion by Hans. If we know some of the bits of the value being switched on, we know that the maximum number of unique cases covers the unknown bits. This allows to eliminate switch defaults for large integers (i32) when most bits in the value are known. Note that I had to make the transform contingent on not having any dead cases. This is conservatively correct with the old code, but required for the new code since we might have a dead case which varies one of the known bits. Counting that towards our number of covering cases would be bad. If we do have dead cases, we'll eliminate them first, then revisit the possibly dead default. Differential Revision: http://reviews.llvm.org/D12497 llvm-svn: 247309
* 80-cols; NFCSanjay Patel2015-09-101-4/+4
| | | | llvm-svn: 247295
* use range-based for loop; NFCISanjay Patel2015-09-101-2/+2
| | | | llvm-svn: 247294
* use range-based for loop; NFCISanjay Patel2015-09-101-2/+2
| | | | llvm-svn: 247293
* fix typo; NFCSanjay Patel2015-09-101-1/+1
| | | | llvm-svn: 247287
* Fix build warning.Craig Topper2015-09-051-1/+1
| | | | llvm-svn: 246908
* Fix build warningAndrew Kaylor2015-09-051-2/+2
| | | | llvm-svn: 246903
* Fix build warningAndrew Kaylor2015-09-041-4/+0
| | | | llvm-svn: 246899
* [WinEH] Teach SimplfyCFG to eliminate empty cleanup pads.Andrew Kaylor2015-09-041-20/+201
| | | | | | Differential Revision: http://reviews.llvm.org/D12434 llvm-svn: 246896
* [SimplifyCFG] Prune code from a provably unreachable switch defaultPhilip Reames2015-08-261-0/+17
| | | | | | | | | | As Sanjoy pointed out over in http://reviews.llvm.org/D11819, a switch on an icmp should always be able to become a branch instruction. This patch generalizes that notion slightly to prove that the default case of a switch is unreachable if the cases completely cover all possible bit patterns in the condition. Once that's done, the switch to branch conversion kicks in just fine. Note: Duplicate case values are disallowed by the LangRef and verifier. Differential Revision: http://reviews.llvm.org/D11995 llvm-svn: 246125
* Rename Instruction::dropUnknownMetadata() to dropUnknownNonDebugMetadata()Adrian Prantl2015-08-201-2/+1
| | | | | | | | | | | and make it always preserve debug locations, since all callers wanted this behavior anyway. This is addressing a post-commit review feedback for r245589. NFC (inside the LLVM tree). llvm-svn: 245622
* Fix a bug that caused SimplifyCFG to drop DebugLocs.Adrian Prantl2015-08-201-0/+1
| | | | | | | | | | | Instruction::dropUnknownMetadata(KnownSet) is supposed to preserve all metadata in KnownSet, but the condition for DebugLocs was inverted. Most users of dropUnknownMetadata() actually worked around this by not adding LLVMContext::MD_dbg to their list of KnowIDs. This is now made explicit. llvm-svn: 245589
* Replace some calls to isa<LandingPadInst> with isEHPad()David Majnemer2015-08-191-1/+1
| | | | | | No functionality change is intended. llvm-svn: 245487
* Convert a bunch of loops to foreach. NFC.Pete Cooper2015-08-061-2/+1
| | | | | | | | After r244074, we now have a successors() method to iterate over all the successors of a TerminatorInst. This commit changes a bunch of eligible loops to use it. llvm-svn: 244260
* De-constify pointers to Type since they can't be modified. NFCCraig Topper2015-08-011-3/+3
| | | | | | This was already done in most places a while ago. This just fixes the ones that crept in over time. llvm-svn: 243842
* don't repeat function names in comments; NFCSanjay Patel2015-06-241-103/+88
| | | | llvm-svn: 240591
* fix typos; NFCSanjay Patel2015-06-241-2/+2
| | | | llvm-svn: 240585
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-3/+3
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-3/+3
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* Fix "the the" in comments.Eric Christopher2015-06-191-1/+1
| | | | llvm-svn: 240112
* SimplifyCFG: Correctly handle switch lookup tables which fully cover the ↵Hans Wennborg2015-04-241-4/+9
| | | | | | | | | | | | | input type and use bit tests to check for holes When using bit tests for hole checks, we call AddPredecessorToBlock to give the phi node a value from the bit test block. This would break if we've previously called removePredecessor on the default destination because the switch is fully covered. Test case by Mark Lacey. llvm-svn: 235771
* Fix typo.Mark Lacey2015-04-121-1/+1
| | | | llvm-svn: 234706
* [opaque pointer type] More GEP IRBuilder API migrations...David Blaikie2015-04-031-2/+2
| | | | llvm-svn: 234058
* Merge empty landing pads in SimplifyCFGPhilip Reames2015-03-241-0/+85
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch tries to merge duplicate landing pads when they branch to a common shared target. Given IR that looks like this: lpad1: %exn = landingpad {i8*, i32} personality i32 (...)* @__gxx_personality_v0 cleanup br label %shared_resume lpad2: %exn2 = landingpad {i8*, i32} personality i32 (...)* @__gxx_personality_v0 cleanup br label %shared_resume shared_resume: call void @fn() ret void } We can rewrite the users of both landing pad blocks to use one of them. This will generally allow the shared_resume block to be merged with the common landing pad as well. Without this change, tail duplication would likely kick in - creating N (2 in this case) copies of the shared_resume basic block. Differential Revision: http://reviews.llvm.org/D8297 llvm-svn: 233125
* [ConstantRange] Split makeICmpRegion in two.Sanjoy Das2015-03-181-2/+2
| | | | | | | | | | | | | | | | | | | | Summary: This change splits `makeICmpRegion` into `makeAllowedICmpRegion` and `makeSatisfyingICmpRegion` with slightly different contracts. The first one is useful for determining what values some expression //may// take, given that a certain `icmp` evaluates to true. The second one is useful for determining what values are guaranteed to //satisfy// a given `icmp`. Reviewers: nlewycky Reviewed By: nlewycky Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8345 llvm-svn: 232575
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-140/+124
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Now that the DataLayout is a mandatory part of the module, let's start cleaning the codebase. This patch is a first attempt at doing that. This patch is not exactly NFC as for instance some places were passing a nullptr instead of the DataLayout, possibly just because there was a default value on the DataLayout argument to many functions in the API. Even though it is not purely NFC, there is no change in the validation. I turned as many pointer to DataLayout to references, this helped figuring out all the places where a nullptr could come up. I had initially a local version of this patch broken into over 30 independant, commits but some later commit were cleaning the API and touching part of the code modified in the previous commits, so it seemed cleaner without the intermediate state. Test Plan: Reviewers: echristo Subscribers: llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231740
* Prevent hoisting fmul from THEN/ELSE to IF if there is fmsub/fmadd opportunity.Chad Rosier2015-02-231-2/+6
| | | | | | | | | | | This patch adds the isProfitableToHoist API. For AArch64, we want to prevent a fmul from being hoisted in cases where it is more profitable to form a fmsub/fmadd. Phabricator Review: http://reviews.llvm.org/D7299 Patch by Lawrence Hu <lawrence@codeaurora.org> llvm-svn: 230241
* Demote vectors to arrays. No functionality change.Benjamin Kramer2015-02-191-7/+5
| | | | llvm-svn: 229861
* Removing LLVM_DELETED_FUNCTION, as MSVC 2012 was the last reason for ↵Aaron Ballman2015-02-151-3/+2
| | | | | | requiring the macro. NFC; LLVM edition. llvm-svn: 229340
* [SimplifyCFG] Be more aggressiveJames Molloy2015-02-131-2/+6
| | | | | | | | Up the phi node folding threshold from a cheap "1" to a meagre "2". Update tests for extra added selects and slight code churn. llvm-svn: 229099
* [SimplifyCFG] Swap to using TargetTransformInfo for costJames Molloy2015-02-111-50/+28
| | | | | | | | | | | | | | | | | | analysis. We're already using TTI in SimplifyCFG, so remove the hard-baked "cheapness" heuristic and use TTI directly. Generally NFC intended, but we're using a slightly different heuristic now so there is a slight test churn. Test changes: * combine-comparisons-by-cse.ll: Removed unneeded branch check. * 2014-08-04-muls-it.ll: Test now doesn't branch but emits muleq. * coalesce-subregs.ll: Superfluous block check. * 2008-01-02-hoist-fp-add.ll: fadd is safe to speculate. Change to udiv. * PhiBlockMerge.ll: Superfluous CFG checking code. Main checks still present. * select-gep.ll: A variable GEP is not expensive, just TCC_Basic, according to the TTI. llvm-svn: 228826
* SimplifyCFG: Omit range checks for switch lookup tables when default is ↵Hans Wennborg2015-01-261-7/+8
| | | | | | | | | | | unreachable The range check would get optimized away later, but we might as well not emit them in the first place. http://reviews.llvm.org/D6471 llvm-svn: 227126
* SimplifyCFG: don't remove unreachable default switch destinationsHans Wennborg2015-01-261-89/+92
| | | | | | | | | | | | | | | An unreachable default destination can be exploited by other optimizations and allows for more efficient lowering. Both the SDag switch lowering and LowerSwitch can exploit unreachable defaults. Also make TurnSwitchRangeICmp handle switches with unreachable default. This is kind of separate change, but it cannot be tested without the change above, and I don't want to land the change above without this since that would regress other tests. Differential Revision: http://reviews.llvm.org/D6471 llvm-svn: 227125
* Revert "Don't remove a landing pad if the invoke requires a table entry."Reid Kleckner2015-01-221-17/+3
| | | | | | | | | | | | This reverts commit r176827. Björn Steinbrink pointed out that this didn't actually fix the bug (PR15555) it was attempting to fix. With this reverted, we can now remove landingpad cleanups that immediately resume unwinding, converting the invoke to a call. llvm-svn: 226850
* fix {typo, build failure} in r225760Ramkumar Ramachandra2015-01-131-1/+1
| | | | llvm-svn: 225762
* Standardize {pred,succ,use,user}_empty()Ramkumar Ramachandra2015-01-131-3/+3
| | | | | | | | | The functions {pred,succ,use,user}_{begin,end} exist, but many users have to check *_begin() with *_end() by hand to determine if the BasicBlock or User is empty. Fix this with a standard *_empty(), demonstrating a few usecases. llvm-svn: 225760
OpenPOWER on IntegriCloud