summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* SimplifyCFG: check uses of constant-foldable instrs in switch destinations ↵Hans Wennborg2015-01-091-6/+15
| | | | | | | | | | | (PR20210) The previous code assumed that such instructions could not have any uses outside CaseDest, with the motivation that the instruction could not dominate CommonDest because CommonDest has phi nodes in it. That simply isn't true; e.g., CommonDest could have an edge back to itself. llvm-svn: 225552
* [PM] Split the AssumptionTracker immutable pass into two separate APIs:Chandler Carruth2015-01-041-34/+34
| | | | | | | | | | | | | | | | | | | | | | | | | | | | a cache of assumptions for a single function, and an immutable pass that manages those caches. The motivation for this change is two fold. Immutable analyses are really hacks around the current pass manager design and don't exist in the new design. This is usually OK, but it requires that the core logic of an immutable pass be reasonably partitioned off from the pass logic. This change does precisely that. As a consequence it also paves the way for the *many* utility functions that deal in the assumptions to live in both pass manager worlds by creating an separate non-pass object with its own independent API that they all rely on. Now, the only bits of the system that deal with the actual pass mechanics are those that actually need to deal with the pass mechanics. Once this separation is made, several simplifications become pretty obvious in the assumption cache itself. Rather than using a set and callback value handles, it can just be a vector of weak value handles. The callers can easily skip the handles that are null, and eventually we can wrap all of this up behind a filter iterator. For now, this adds boiler plate to the various passes, but this kind of boiler plate will end up making it possible to port these passes to the new pass manager, and so it will end up factored away pretty reasonably. llvm-svn: 225131
* [SimplifyCFG] Revise common code sinkingMichael Liao2014-12-231-30/+30
| | | | | | | | | | - Fix the case where more than 1 common instructions derived from the same operand cannot be sunk. When a pair of value has more than 1 derived values in both branches, only 1 derived value could be sunk. - Replace BB1 -> (BB2, PN) map with joint value map, i.e. map of (BB1, BB2) -> PN, which is more accurate to track common ops. llvm-svn: 224757
* IR: Split Metadata from ValueDuncan P. N. Exon Smith2014-12-091-5/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Split `Metadata` away from the `Value` class hierarchy, as part of PR21532. Assembly and bitcode changes are in the wings, but this is the bulk of the change for the IR C++ API. I have a follow-up patch prepared for `clang`. If this breaks other sub-projects, I apologize in advance :(. Help me compile it on Darwin I'll try to fix it. FWIW, the errors should be easy to fix, so it may be simpler to just fix it yourself. This breaks the build for all metadata-related code that's out-of-tree. Rest assured the transition is mechanical and the compiler should catch almost all of the problems. Here's a quick guide for updating your code: - `Metadata` is the root of a class hierarchy with three main classes: `MDNode`, `MDString`, and `ValueAsMetadata`. It is distinct from the `Value` class hierarchy. It is typeless -- i.e., instances do *not* have a `Type`. - `MDNode`'s operands are all `Metadata *` (instead of `Value *`). - `TrackingVH<MDNode>` and `WeakVH` referring to metadata can be replaced with `TrackingMDNodeRef` and `TrackingMDRef`, respectively. If you're referring solely to resolved `MDNode`s -- post graph construction -- just use `MDNode*`. - `MDNode` (and the rest of `Metadata`) have only limited support for `replaceAllUsesWith()`. As long as an `MDNode` is pointing at a forward declaration -- the result of `MDNode::getTemporary()` -- it maintains a side map of its uses and can RAUW itself. Once the forward declarations are fully resolved RAUW support is dropped on the ground. This means that uniquing collisions on changing operands cause nodes to become "distinct". (This already happened fairly commonly, whenever an operand went to null.) If you're constructing complex (non self-reference) `MDNode` cycles, you need to call `MDNode::resolveCycles()` on each node (or on a top-level node that somehow references all of the nodes). Also, don't do that. Metadata cycles (and the RAUW machinery needed to construct them) are expensive. - An `MDNode` can only refer to a `Constant` through a bridge called `ConstantAsMetadata` (one of the subclasses of `ValueAsMetadata`). As a side effect, accessing an operand of an `MDNode` that is known to be, e.g., `ConstantInt`, takes three steps: first, cast from `Metadata` to `ConstantAsMetadata`; second, extract the `Constant`; third, cast down to `ConstantInt`. The eventual goal is to introduce `MDInt`/`MDFloat`/etc. and have metadata schema owners transition away from using `Constant`s when the type isn't important (and they don't care about referring to `GlobalValue`s). In the meantime, I've added transitional API to the `mdconst` namespace that matches semantics with the old code, in order to avoid adding the error-prone three-step equivalent to every call site. If your old code was: MDNode *N = foo(); bar(isa <ConstantInt>(N->getOperand(0))); baz(cast <ConstantInt>(N->getOperand(1))); bak(cast_or_null <ConstantInt>(N->getOperand(2))); bat(dyn_cast <ConstantInt>(N->getOperand(3))); bay(dyn_cast_or_null<ConstantInt>(N->getOperand(4))); you can trivially match its semantics with: MDNode *N = foo(); bar(mdconst::hasa <ConstantInt>(N->getOperand(0))); baz(mdconst::extract <ConstantInt>(N->getOperand(1))); bak(mdconst::extract_or_null <ConstantInt>(N->getOperand(2))); bat(mdconst::dyn_extract <ConstantInt>(N->getOperand(3))); bay(mdconst::dyn_extract_or_null<ConstantInt>(N->getOperand(4))); and when you transition your metadata schema to `MDInt`: MDNode *N = foo(); bar(isa <MDInt>(N->getOperand(0))); baz(cast <MDInt>(N->getOperand(1))); bak(cast_or_null <MDInt>(N->getOperand(2))); bat(dyn_cast <MDInt>(N->getOperand(3))); bay(dyn_cast_or_null<MDInt>(N->getOperand(4))); - A `CallInst` -- specifically, intrinsic instructions -- can refer to metadata through a bridge called `MetadataAsValue`. This is a subclass of `Value` where `getType()->isMetadataTy()`. `MetadataAsValue` is the *only* class that can legally refer to a `LocalAsMetadata`, which is a bridged form of non-`Constant` values like `Argument` and `Instruction`. It can also refer to any other `Metadata` subclass. (I'll break all your testcases in a follow-up commit, when I propagate this change to assembly.) llvm-svn: 223802
* Revert "Move function to obtain branch weights into the BranchInst class. NFC."Juergen Ributzka2014-12-091-6/+26
| | | | | | This reverts commit r223784 and copies the 'ExtractBranchMetadata' to CodeGenPrepare. llvm-svn: 223795
* Move function to obtain branch weights into the BranchInst class. NFC.Juergen Ributzka2014-12-091-26/+6
| | | | | | Make this function available to other parts of LLVM. llvm-svn: 223784
* Revert r223049, r223050 and r223051 while investigating test failures.Hans Wennborg2014-12-011-8/+56
| | | | | | I didn't foresee affecting the Clang test suite :/ llvm-svn: 223054
* SimplifyCFG: Omit range checks for switch lookup tables when default is ↵Hans Wennborg2014-12-011-7/+8
| | | | | | | | unreachable They would get optimized away later, but we might as well not emit them. llvm-svn: 223051
* SimplifyCFG: don't remove unreachable default switch destinationsHans Wennborg2014-12-011-49/+0
| | | | | | | | | | | | | An unreachable default destination can be exploited by other optimizations, and SDag lowering is now prepared to handle them efficiently. For example, branches to the unreachable destination will be optimized away, such as in the case of range checks for switch lookup tables. On 64-bit Linux, this reduces the size of a clang bootstrap by 80 kB (and Chromium by 30 kB). llvm-svn: 223050
* reinstate r222872: Peephole optimization in switch table lookup: reuse the ↵Erik Eckstein2014-11-271-7/+100
| | | | | | | | | | | | | | | | | | | | | | | | | | | guarding table comparison if possible. Fixed missing dominance check. Original commit message: This optimization tries to reuse the generated compare instruction, if there is a comparison against the default value after the switch. Example: if (idx < tablesize) r = table[idx]; // table does not contain default_value else r = default_value; if (r != default_value) ... Is optimized to: cond = idx < tablesize; if (cond) r = table[idx]; else r = default_value; if (cond) ... Jump threading will then eliminate the second if(cond). llvm-svn: 222891
* Revert "Peephole optimization in switch table lookup: reuse the guarding ↵Erik Eckstein2014-11-271-89/+7
| | | | | | | | table comparison if possible." It is breaking the clang bootstrag. llvm-svn: 222877
OpenPOWER on IntegriCloud