summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Make bitcast, extractelement, and insertelement considered cheap for ↵Matt Arsenault2014-05-301-0/+3
| | | | | | | | | | speculation. This helps more branches into selects. On R600, vectors are cheap and anything that helps remove branches is very good. llvm-svn: 209914
* Rename ComputeMaskedBits to computeKnownBits. "Masked" has beenJay Foad2014-05-141-1/+1
| | | | | | inappropriate since it lost its Mask parameter in r154011. llvm-svn: 208811
* Add ExtractValue instruction to SimplifyCFG's ComputeSpeculationCostLouis Gerbarg2014-05-091-0/+1
| | | | | | | | | | | | | Since ExtractValue is not included in ComputeSpeculationCost CFGs containing ExtractValueInsts cannot be simplified. In particular this interacts with InstCombineCompare's tendency to insert add.with.overflow intrinsics for certain idiomatic math operations, preventing optimization. This patch adds ExtractValue to the ComputeSpeculationCost. Test case included rdar://14853450 llvm-svn: 208434
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-73/+74
| | | | llvm-svn: 207196
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | | | | | | definition below all of the header #include lines, lib/Transforms/... edition. This one is tricky for two reasons. We again have a couple of passes that define something else before the includes as well. I've sunk their name macros with the DEBUG_TYPE. Also, InstCombine contains headers that need DEBUG_TYPE, so now those headers #define and #undef DEBUG_TYPE around their code, leaving them well formed modular headers. Fixing these headers was a large motivation for all of these changes, as "leaky" macros of this form are hard on the modules implementation. llvm-svn: 206844
* Allow switch-to-lookup table for tables with holes by adding bitmask checkHans Wennborg2014-03-121-5/+61
| | | | | | | | | | | | | | | | | | | | | | | | This allows us to generate table lookups for code such as: unsigned test(unsigned x) { switch (x) { case 100: return 0; case 101: return 1; case 103: return 2; case 105: return 3; case 107: return 4; case 109: return 5; case 110: return 6; default: return f(x); } } Since cases 102, 104, etc. are not constants, the lookup table has holes in those positions. We therefore guard the table lookup with a bitmask check. Patch by Jasper Neumann! llvm-svn: 203694
* SimplifyCFG: Simplify the weight scaling algorithm.Benjamin Kramer2014-03-091-15/+6
| | | | | | No change in functionality. llvm-svn: 203413
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-10/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* [Modules] Move the ConstantRange class into the IR library. This isChandler Carruth2014-03-041-1/+1
| | | | | | | | | | a bit surprising, as the class is almost entirely abstracted away from any particular IR, however it encodes the comparsion predicates which mutate ranges as ICmp predicate codes. This is reasonable as they're used for both instructions and constants. Thus, it belongs in the IR library with instructions and constants. llvm-svn: 202838
* [Modules] Move the NoFolder into the IR library as it createsChandler Carruth2014-03-041-1/+1
| | | | | | instructions. llvm-svn: 202834
* [Modules] Move CFG.h to the IR library as it defines graph traits overChandler Carruth2014-03-041-1/+1
| | | | | | IR types. llvm-svn: 202827
* [Modules] Move the LLVM IR pattern match header into the IR library, itChandler Carruth2014-03-041-1/+1
| | | | | | obviously is coupled to the IR. llvm-svn: 202818
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-2/+2
| | | | | | Remove the old functions. llvm-svn: 202636
* Rename many DataLayout variables from TD to DL.Rafael Espindola2014-02-211-70/+70
| | | | | | | | | I am really sorry for the noise, but the current state where some parts of the code use TD (from the old name: TargetData) and other parts use DL makes it hard to write a patch that changes where those variables come from and how they are passed along. llvm-svn: 201827
* Fix pr14893.Rafael Espindola2014-01-281-0/+8
| | | | | | | | | | | When simplifycfg moves an instruction, it must drop metadata it doesn't know is still valid with the preconditions changes. In particular, it must drop the range and tbaa metadata. The patch implements this with an utility function to drop all metadata not in a white list. llvm-svn: 200322
* PGO branch weight: keep halving the weights until they can fit intoManman Ren2014-01-271-12/+13
| | | | | | | | | | uint32. When folding branches to common destination, the updated branch weights can exceed uint32 by more than factor of 2. We should keep halving the weights until they can fit into uint32. llvm-svn: 200262
* Fix known typosAlp Toker2014-01-241-3/+3
| | | | | | | Sweep the codebase for common typos. Includes some changes to visible function names that were misspelt. llvm-svn: 200018
* Switch-to-lookup tables: set threshold to 3 casesHans Wennborg2014-01-151-5/+3
| | | | | | | | | | | | | | | There has been an old FIXME to find the right cut-off for when it's worth analyzing and potentially transforming a switch to a lookup table. The switches always have two or more cases. I could not measure any speed-up by transforming a switch with two cases. A switch with three cases gets a nice speed-up, and I couldn't measure any compile-time regression, so I think this is the right threshold. In a Clang self-host, this causes 480 new switches to be transformed, and reduces the final binary size with 8 KB. llvm-svn: 199294
* Switch-to-lookup tables: Don't require a result for the defaultHans Wennborg2014-01-121-12/+25
| | | | | | | | | | | | | | | | | | | | | | | case when the lookup table doesn't have any holes. This means we can build a lookup table for switches like this: switch (x) { case 0: return 1; case 1: return 2; case 2: return 3; case 3: return 4; default: exit(1); } The default case doesn't yield a constant result here, but that doesn't matter, since a default result is only necessary for filling holes in the lookup table, and this table doesn't have any holes. This makes us transform 505 more switches in a clang bootstrap, and shaves 164 KB off the resulting clang binary. llvm-svn: 199025
* Transforms: Don't create bad weights when eliminating dead casesJustin Bogner2013-12-201-1/+1
| | | | | | | | | If we happen to eliminate every case in a switch that has branch weights, we currently try to create metadata for the one remaining branch, triggering an assert. Instead, we need to check that the metadata we're trying to create is sensible. llvm-svn: 197791
* FoldBranchToCommonDest merges branches into a single branch with or/and of ↵Nadav Rotem2013-11-121-2/+7
| | | | | | the condition. It has a heuristics for estimating when some of the dependencies are processed by out-of-order processors. This patch adds another rule to the heuristics that says that if the "BonusInstruction" that we speculatively execute is used by the condition of the second branch then it is okay to hoist it. This change exposes more opportunities for other passes to transform the code. It does not matter that much that we if-convert the code because the selectiondag builder splits or/and branches into multiple branches when profitable. llvm-svn: 194524
* SimplifyCFG: Use existing constant folding logic when forming switch tables.Benjamin Kramer2013-11-121-31/+20
| | | | | | Both simpler and more powerful than the hand-rolled folding logic. llvm-svn: 194475
* SimplifyCFG has a heuristics for out-of-order processors that decides when ↵Nadav Rotem2013-11-101-1/+1
| | | | | | | | it is worthwhile to merge branches. It tries to estimate if the operands of the instruction that we want to hoist are ready. This commit marks function arguments as 'ready' because they require no calculation. This boosts libquantum and a few other workloads from the testsuite. llvm-svn: 194346
* SimplifyCFG: Don't duplicate calls to functions marked noduplicate v2Tom Stellard2013-10-211-0/+15
| | | | | | | v2: - Use CI->cannotDuplicate() llvm-svn: 193115
* Teach SimplifyCFG about address spacesMatt Arsenault2013-10-211-5/+9
| | | | llvm-svn: 193104
* Fix the predecessor removal logic in r193045.Michael Gottesman2013-10-211-11/+9
| | | | | | Additionally some small comment/stylistic fixes are included as well. llvm-svn: 193068
* Teach simplify-cfg how to correctly create covered lookup tables for ↵Michael Gottesman2013-10-201-6/+28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | switches on iN with N >= 3. One optimization simplify-cfg performs is the converting of switches to lookup tables if the switch has > 4 cases. This is done by: 1. Finding the max/min case value and calculating the switch case range. 2. Create a lookup table basic block. 3. Perform a check in the switch's BB to see if the input value is in the switch's case range. If the input value satisfies said predicate branch to the lookup table BB, otherwise branch to the switch's default destination BB using the default value as the result. The conditional check consists of subtracting the min case value of the table from any input iN value and then ensuring that said value is unsigned less than the size of the lookup table represented as an iN value. If the lookup table is a covered lookup table, the size of the table will be N which is 0 as an iN value. Thus the comparison will be an `icmp ult` of an iN value against 0 which is always false yielding the incorrect result. This patch fixes this problem by recognizing if we have a covered lookup table and if we do, unconditionally jumps to the lookup table BB since the covering property of the lookup table implies no input values could not be handled by said BB. rdar://15268442 llvm-svn: 193045
* Provide basic type safety for array_pod_sort comparators.Benjamin Kramer2013-09-221-3/+4
| | | | | | | | This makes using array_pod_sort significantly safer. The implementation relies on function pointer casting but that should be safe as we're dealing with void* here. llvm-svn: 191175
* Use type helper functions.Matt Arsenault2013-09-061-1/+1
| | | | llvm-svn: 190113
* Factor FlattenCFG out from SimplifyCFGTom Stellard2013-08-061-516/+4
| | | | | | Patch by: Mei Ye llvm-svn: 187764
* Fix dereferencing end iterator in SimplifyCFG. Patch by Ye Mei.Alexey Samsonov2013-08-021-5/+8
| | | | llvm-svn: 187646
* Fix -Wdocumentation warnings.Rafael Espindola2013-07-281-4/+4
| | | | llvm-svn: 187336
* SimplifyCFG: Use parallel-and and parallel-or mode to consolidate branch ↵Tom Stellard2013-07-271-11/+432
| | | | | | | | | | | | | | conditions Merge consecutive if-regions if they contain identical statements. Both transformations reduce number of branches. The transformation is guarded by a target-hook, and is currently enabled only for +R600, but the correctness has been tested on X86 target using a variety of CPU benchmarks. Patch by: Mei Ye llvm-svn: 187278
* Use SmallVectorImpl& instead of SmallVector to avoid repeating small vector ↵Craig Topper2013-07-141-8/+9
| | | | | | size. llvm-svn: 186274
* SimplifyCFG: Teach switch generation some patterns that instcombine forms.Benjamin Kramer2013-07-041-1/+27
| | | | | | | | This allows us to create switches even if instcombine has munged two of the incombing compares into one and some bit twiddling. This was motivated by enum compares that are common in clang. llvm-svn: 185632
* Second part of pr16069Rafael Espindola2013-06-041-4/+9
| | | | | | | | | | | | | | | | | The problem this time seems to be a thinko. We were assuming that in the CFG A | \ | B | / C speculating the basic block B would cause only the phi value for the B->C edge to be speculated. That is not true, the phi's are semantically in the edges, so if the A->B->C path is taken, any code needed for A->C is not executed and we have to consider it too when deciding to speculate B. llvm-svn: 183226
* Typo: s/caes/cases/ in SimplifyCFGHans Wennborg2013-06-041-1/+1
| | | | llvm-svn: 183219
* SimplifyCFG: Do not transform PHI to select if doing so would be unsafeDavid Majnemer2013-06-031-2/+19
| | | | | | | | | | | | | PR16069 is an interesting case where an incoming value to a PHI is a trap value while also being a 'ConstantExpr'. We do not consider this case when performing the 'HoistThenElseCodeToIf' optimization. Instead, make our modifications more conservative if we detect that we cannot transform the PHI to a select. llvm-svn: 183152
* SimplifyCFG: Small cleanup, use ICmpInst::isEquality()David Majnemer2013-06-031-3/+1
| | | | llvm-svn: 183151
* SimplifyCFG: Fix typo in comment for ComputeSpeculationCostDavid Majnemer2013-06-011-1/+1
| | | | llvm-svn: 183078
* More symbols that should be static.Benjamin Kramer2013-05-231-2/+2
| | | | llvm-svn: 182590
* SimplifyCFG: If convert single conditional storesArnold Schwaighofer2013-04-291-4/+90
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This resurrects r179957, but adds code that makes sure we don't touch atomic/volatile stores: This transformation will transform a conditional store with a preceeding uncondtional store to the same location: a[i] = may-alias with a[i] load if (cond) a[i] = Y into an unconditional store. a[i] = X may-alias with a[i] load tmp = cond ? Y : X; a[i] = tmp We assume that on average the cost of a mispredicted branch is going to be higher than the cost of a second store to the same location, and that the secondary benefits of creating a bigger basic block for other optimizations to work on outway the potential case where the branch would be correctly predicted and the cost of the executing the second store would be noticably reflected in performance. hmmer's execution time improves by 30% on an imac12,2 on ref data sets. With this change we are on par with gcc's performance (gcc also performs this transformation). There was a 1.2 % performance improvement on a ARM swift chip. Other tests in the test-suite+external seem to be mostly uninfluenced in my experiments: This optimization was triggered on 41 tests such that the executable was different before/after the patch. Only 1 out of the 40 tests (dealII) was reproducable below 100% (by about .4%). Given that hmmer benefits so much I believe this to be a fair trade off. llvm-svn: 180731
* Revert "SimplifyCFG: If convert single conditional stores"Arnold Schwaighofer2013-04-211-88/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | There is the temptation to make this tranform dependent on target information as it is not going to be beneficial on all (sub)targets. Therefore, we should probably do this in MI Early-Ifconversion. This reverts commit r179957. Original commit message: "SimplifyCFG: If convert single conditional stores This transformation will transform a conditional store with a preceeding uncondtional store to the same location: a[i] = may-alias with a[i] load if (cond) a[i] = Y into an unconditional store. a[i] = X may-alias with a[i] load tmp = cond ? Y : X; a[i] = tmp We assume that on average the cost of a mispredicted branch is going to be higher than the cost of a second store to the same location, and that the secondary benefits of creating a bigger basic block for other optimizations to work on outway the potential case were the branch would be correctly predicted and the cost of the executing the second store would be noticably reflected in performance. hmmer's execution time improves by 30% on an imac12,2 on ref data sets. With this change we are on par with gcc's performance (gcc also performs this transformation). There was a 1.2 % performance improvement on a ARM swift chip. Other tests in the test-suite+external seem to be mostly uninfluenced in my experiments: This optimization was triggered on 41 tests such that the executable was different before/after the patch. Only 1 out of the 40 tests (dealII) was reproducable below 100% (by about .4%). Given that hmmer benefits so much I believe this to be a fair trade off. I am going to watch performance numbers across the builtbots and will revert this if anything unexpected comes up." llvm-svn: 179980
* SimplifyCFG: If convert single conditional storesArnold Schwaighofer2013-04-201-4/+88
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This transformation will transform a conditional store with a preceeding uncondtional store to the same location: a[i] = may-alias with a[i] load if (cond) a[i] = Y into an unconditional store. a[i] = X may-alias with a[i] load tmp = cond ? Y : X; a[i] = tmp We assume that on average the cost of a mispredicted branch is going to be higher than the cost of a second store to the same location, and that the secondary benefits of creating a bigger basic block for other optimizations to work on outway the potential case were the branch would be correctly predicted and the cost of the executing the second store would be noticably reflected in performance. hmmer's execution time improves by 30% on an imac12,2 on ref data sets. With this change we are on par with gcc's performance (gcc also performs this transformation). There was a 1.2 % performance improvement on a ARM swift chip. Other tests in the test-suite+external seem to be mostly uninfluenced in my experiments: This optimization was triggered on 41 tests such that the executable was different before/after the patch. Only 1 out of the 40 tests (dealII) was reproducable below 100% (by about .4%). Given that hmmer benefits so much I believe this to be a fair trade off. I am going to watch performance numbers across the builtbots and will revert this if anything unexpected comes up. llvm-svn: 179957
* simplifycfg: Fix integer overflow converting switch into icmp.Hans Wennborg2013-04-161-1/+6
| | | | | | | | | | | If a switch instruction has a case for every possible value of its type, with the same successor, SimplifyCFG would replace it with an icmp ult, but the computation of the bound overflows in that case, which inverts the test. Patch by Jed Davis! llvm-svn: 179587
* Don't remove a landing pad if the invoke requires a table entry.Bill Wendling2013-03-111-3/+17
| | | | | | | | An invoke may require a table entry. For instance, when the function it calls is expected to throw. <rdar://problem/13360379> llvm-svn: 176827
* SimplifyCFG fix for volatile load/store.Andrew Trick2013-03-071-2/+4
| | | | | | | | | | | | | Fixes rdar:13349374. Volatile loads and stores need to be preserved even if the language standard says they are undefined. "volatile" in this context means "get out of the way compiler, let my platform handle it". Additionally, this is the only way I know of with llvm to write to the first page (when hardware allows) without dropping to assembly. llvm-svn: 176599
* Re-revert r173342, without losing the compile time improvements, flatChandler Carruth2013-01-271-27/+12
| | | | | | out bug fixes, or functionality preserving refactorings. llvm-svn: 173610
* Switch this code away from Value::isUsedInBasicBlock. That code eitherChandler Carruth2013-01-251-7/+29
| | | | | | | | | | | | | | | | | | | | | | | | | | | | loops over instructions in the basic block or the use-def list of the value, neither of which are really efficient when repeatedly querying about values in the same basic block. What's more, we already know that the CondBB is small, and so we can do a much more efficient test by counting the uses in CondBB, and seeing if those account for all of the uses. Finally, we shouldn't blanket fail on any such instruction, instead we should conservatively assume that those instructions are part of the cost. Note that this actually fixes a bug in the pass because isUsedInBasicBlock has a really terrible bug in it. I'll fix that in my next commit, but the fix for it would make this code suddenly take the compile time hit I thought it already was taking, so I wanted to go ahead and migrate this code to a faster & better pattern. The bug in isUsedInBasicBlock was also causing other tests to test the wrong thing entirely: for example we weren't actually disabling speculation for floating point operations as intended (and tested), but the test passed because we failed to speculate them due to the isUsedInBasicBlock failure. llvm-svn: 173417
* Reapply chandlerc's r173342 now that the miscompile it was triggering is fixed.Benjamin Kramer2013-01-241-9/+18
| | | | | | | | | | | | | | | | | | | | Original commit message: Plug TTI into the speculation logic, giving it a real cost interface that can be specialized by targets. The goal here is not to be more aggressive, but to just be more accurate with very obvious cases. There are instructions which are known to be truly free and which were not being modeled as such in this code -- see the regression test which is distilled from an inner loop of zlib. Everywhere the TTI cost model is insufficiently conservative I've added explicit checks with FIXME comments to go add proper modelling of these cost factors. If this causes regressions, the likely solution is to make TTI even more conservative in its cost estimates, but test cases will help here. llvm-svn: 173357
OpenPOWER on IntegriCloud