summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
* [InstrSimplify,NewGVN] Add option to ignore additional instr info when ↵Florian Hahn2018-08-171-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | simplifying. NewGVN uses InstructionSimplify for simplifications of leaders of congruence classes. It is not guaranteed that the metadata or other flags/keywords (like nsw or exact) of the leader is available for all members in a congruence class, so we cannot use it for simplification. This patch adds a InstrInfoQuery struct with a boolean field UseInstrInfo (which defaults to true to keep the current behavior as default) and a set of helper methods to get metadata/keywords for a given instruction, if UseInstrInfo is true. The whole thing might need a better name, to avoid confusion with TargetInstrInfo but I am not sure what a better name would be. The current patch threads through InstrInfoQuery to the required places, which is messier then it would need to be, if InstructionSimplify and ValueTracking would share the same Query struct. The reason I added it as a separate struct is that it can be shared between InstructionSimplify and ValueTracking's query objects. Also, some places do not need a full query object, just the InstrInfoQuery. It also updates some interfaces that do not take a Query object, but a set of optional parameters to take an additional boolean UseInstrInfo. See https://bugs.llvm.org/show_bug.cgi?id=37540. Reviewers: dberlin, davide, efriedma, sebpop, hiraditya Reviewed By: hiraditya Differential Revision: https://reviews.llvm.org/D47143 llvm-svn: 340031
* [LICM] Add a diagnostic analysis for identifying alias informationAnna Thomas2018-08-171-14/+69
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Currently, in LICM, we use the alias set tracker to identify if the instruction (we're interested in hoisting) aliases with instruction that modifies that memory location. This patch adds an LICM alias analysis diagnostic tool that checks the mod ref info of the instruction we are interested in hoisting/sinking, with every instruction in the loop. Because of O(N^2) complexity this is now only a diagnostic tool to show the limitation we have with the alias set tracker and is OFF by default. Test cases show the difference with the diagnostic analysis tool, where we're able to hoist out loads and readonly + argmemonly calls from the loop, where the alias set tracker analysis is not able to hoist these instructions out. Reviewers: reames, mkazantsev, fedor.sergeev, hfinkel Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D50854 llvm-svn: 340026
* [MISC]Fix wrong usage of std::equal()Chen Zheng2018-08-171-6/+2
| | | | | | Differential Revision: https://reviews.llvm.org/D49958 llvm-svn: 340000
* [LICM][NFC] Restructure pointer invalidation API in terms of MemoryLocationPhilip Reames2018-08-161-19/+10
| | | | | | | | Main value is just simplifying code. I'll further simply the argument handling case in a bit, but that involved a slightly orthogonal change so I went with the mildy ugly intermediate for this patch. Note that the isSized check in the old LICM code was not carried across. It turns out that check was dead. a) no test exercised it, and b) langref and verifier had been updated to disallow unsized types used in loads. llvm-svn: 339930
* [NFC] Remove const modifier to allow further development in LICMMax Kazantsev2018-08-161-3/+2
| | | | llvm-svn: 339846
* [GVN] Fix typo in IsValueFullyAvailableInBlock. NFC.Marcello Maggioni2018-08-151-1/+1
| | | | | | | | DenseMap insert() method return a pair<iterator, bool> not pair<iterator, char> Noticed it and thought I might just fix it ... llvm-svn: 339777
* [NFC] Refactoring of LoopSafetyInfo, step 1Max Kazantsev2018-08-153-5/+5
| | | | | | | | | Turn structure into class, encapsulate methods, add clarifying comments. Differential Revision: https://reviews.llvm.org/D50693 Reviewed By: reames llvm-svn: 339752
* [NFC][LICM] Make hoist method voidMax Kazantsev2018-08-151-4/+4
| | | | | | | | | Method hoist always returns true. This patch makes it void. Differential Revision: https://reviews.llvm.org/D50696 Reviewed By: hiraditya llvm-svn: 339750
* [GuardWidening] Widen very likely non-taken br instructionsMax Kazantsev2018-08-131-24/+47
| | | | | | | | | | This is a second part of D49974 that handles widening of conditional branches that have very likely `false` branch. Differential Revision: https://reviews.llvm.org/D50040 Reviewed By: reames llvm-svn: 339537
* [UnJ] Improve explicit loop count checksDavid Green2018-08-111-52/+67
| | | | | | | | | | | | | Try to improve the computed counts when it has been explicitly set by a pragma or command line option. This moves the code around, so that first call to computeUnrollCount to get a sensible count and override that if explicit unroll and jam counts are specified. Also added some extra debug messages for when unroll and jamming is disabled. Differential Revision: https://reviews.llvm.org/D50075 llvm-svn: 339501
* [LICM] Hoist assumes out of loopsPhilip Reames2018-08-101-0/+9
| | | | | | | | If we have an assume which is known to execute and whose operand is invariant, we can lift that into the pre-header. So long as we don't change which paths the assume executes on, this is a legal transformation. It's likely to be a useful canonicalization as other transforms only look for dominating assumes. Differential Revision: https://reviews.llvm.org/D50364 llvm-svn: 339481
* [LICM] Suppress a compiler warning noticed by one of the botsPhilip Reames2018-08-091-0/+1
| | | | llvm-svn: 339388
* [LICM] hoist fences out of loops w/o memory operationsPhilip Reames2018-08-091-0/+15
| | | | | | | | | | The motivating case is an otherwise dead loop with a fence in it. At the moment, this goes all the way through the optimizer and we end up emitting an entirely pointless loop on x86. This case may seem a bit contrived, but we've seen it in real code as the result of otherwise reasonable lowering strategies combined w/thread local memory optimizations (such as escape analysis). To handle this simple case, we can teach LICM to hoist must execute fences when there is no other memory operation within the loop. Differential Revision: https://reviews.llvm.org/D50489 llvm-svn: 339378
* SCEV should forget all loops containing a deleted block.Alina Sbirlea2018-08-091-1/+2
| | | | | | | | | | | | | | Summary: LoopSimplifyCFG should update ScEv for all loops after a block is deleted. If the deleted block "Succ" is part of L, then it is part of all parent loops, so forget topmost loop. Reviewers: greened, mkazantsev, sanjoy Subscribers: jlebar, javed.absar, uabelho, llvm-commits Differential Revision: https://reviews.llvm.org/D50422 llvm-svn: 339363
* [LICM] Add an assert to ensure all instruction types needing aliasing are ↵Philip Reames2018-08-091-0/+2
| | | | | | handled [NFC] llvm-svn: 339308
* [GVN,NewGVN] Move patchReplacementInstruction to Utils/Local.hFlorian Hahn2018-08-072-62/+0
| | | | | | | | | | | | | This function is shared between both implementations. I am not sure if Utils/Local.h is the best place though. Reviewers: davide, dberlin, efriedma, xbolva00 Reviewed By: efriedma, xbolva00 Differential Revision: https://reviews.llvm.org/D47337 llvm-svn: 339138
* [NFC] Factor out implicit control flow logic from GVNMax Kazantsev2018-08-071-75/+11
| | | | | | | | | | | | | | Logic for tracking implicit control flow instructions was added to GVN to perform PRE optimizations correctly. It appears that GVN is not the only optimization that sometimes does PRE, so this logic is required in other places (such as Jump Threading). This is an NFC patch that encapsulates all ICF-related logic in a dedicated utility class separated from GVN. Differential Revision: https://reviews.llvm.org/D40293 llvm-svn: 339086
* [LICM] Extract a helper function for readability [NFC]Philip Reames2018-08-061-8/+12
| | | | llvm-svn: 339069
* Try to fix buildbotMax Kazantsev2018-08-061-1/+1
| | | | llvm-svn: 338991
* [GuardWidening] Widen guards with conditions of frequently taken dominated ↵Max Kazantsev2018-08-061-34/+98
| | | | | | | | | | | | | | | | | | | | | | | | | | branches If there is a frequently taken branch dominated by a guard, and its condition is available at the point of the guard, we can widen guard with condition of this branch and convert the branch into unconditional: guard(cond1) if (cond2) { // taken in 99.9% cases // do something } else { // do something else } Converts to guard(cond1 && cond2) // do something Differential Revision: https://reviews.llvm.org/D49974 Reviewed By: reames llvm-svn: 338988
* [DebugInfo] Refactor DbgInfoIntrinsic class hierarchy.Hsiangkai Wang2018-08-063-5/+5
| | | | | | | | | | | | | | | | In the past, DbgInfoIntrinsic has a strong assumption that these intrinsics all have variables and expressions attached to them. However, it is too strong to derive the class for other debug entities. Now, it has problems for debug labels. In order to make DbgInfoIntrinsic as a base class for 'debug info', I create a class for 'variable debug info', DbgVariableIntrinsic. DbgDeclareInst, DbgAddrIntrinsic, and DbgValueInst will be derived from it. Differential Revision: https://reviews.llvm.org/D50220 llvm-svn: 338984
* [TailCallElim] Preserve DT and PDTChijun Sima2018-08-041-26/+49
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Previously, in the NewPM pipeline, TailCallElim recalculates the DomTree when it modifies any instruction in the Function. For example, ``` CallInst *CI = dyn_cast<CallInst>(&I); ... CI->setTailCall(); Modified = true; ... if (!Modified || ...) return PreservedAnalyses::all(); ``` After applying this patch, the DomTree only recalculates if needed (plus an extra insertEdge() + an extra deleteEdge() call). When optimizing SQLite with `-passes="default<O3>"` pipeline of the newPM, the number of DomTree recalculation decreases by 6.2%, the number of nodes visited by DFS decreases by 2.9%. The time used by DomTree will decrease approximately 1%~2.5% after applying the patch. Statistics: ``` Before the patch: 23010 dom-tree-stats - Number of DomTree recalculations 489264 dom-tree-stats - Number of nodes visited by DFS -- DomTree After the patch: 21581 dom-tree-stats - Number of DomTree recalculations 475088 dom-tree-stats - Number of nodes visited by DFS -- DomTree ``` Reviewers: kuhar, dmgreen, brzycki, grosser, davide Reviewed By: kuhar, brzycki Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D49982 llvm-svn: 338954
* [ADCE] Remove the need of DomTreeChijun Sima2018-08-041-8/+10
| | | | | | | | | | | | | | Summary: ADCE doesn't need to query domtree. Reviewers: kuhar, brzycki, dmgreen, davide, grosser Reviewed By: kuhar Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D49988 llvm-svn: 338950
* [TRE][DebugInfo] Preserve Debug Location in new branch instructionAnastasis Grammenos2018-08-031-1/+2
| | | | | | | | | There are two branch instructions created so the new test covers them both. Differential Revision: https://reviews.llvm.org/D50263 llvm-svn: 338917
* [NFC] Add missing commentMax Kazantsev2018-08-031-0/+1
| | | | llvm-svn: 338848
* [NFC] Move some methods into static functionsMax Kazantsev2018-08-031-37/+27
| | | | llvm-svn: 338843
* [Dominators] Convert existing passes and utils to use the DomTreeUpdater classChijun Sima2018-08-036-55/+64
| | | | | | | | | | | | | | | | | | Summary: This patch is the second in a series of patches related to the [[ http://lists.llvm.org/pipermail/llvm-dev/2018-June/123883.html | RFC - A new dominator tree updater for LLVM ]]. It converts passes (e.g. adce/jump-threading) and various functions which currently accept DDT in local.cpp and BasicBlockUtils.cpp to use the new DomTreeUpdater class. These converted functions in utils can accept DomTreeUpdater with either UpdateStrategy and can deal with both DT and PDT held by the DomTreeUpdater. Reviewers: brzycki, kuhar, dmgreen, grosser, davide Reviewed By: brzycki Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D48967 llvm-svn: 338814
* [LICM] Remove unneccessary safety check to increase sinking effectivenessPhilip Reames2018-08-031-8/+1
| | | | | | | | | | | | This one requires a bit of explaination. It's not every day you simply delete code to implement an optimization. :) The transform in question is sinking an instruction from a loop to the uses in loop exiting blocks. We know (from LCSSA) that all of the uses outside the loop must be phi nodes, and after predecessor splitting, we know all phi users must have a single operand. Since the use must be strictly dominated by the def, we know from the definition of dominance/ssa that the exit block must execute along a (non-strict) subset of paths which reach the def. As a result, duplicating a potentially faulting instruction can not *introduce* a fault that didn't previously exist in the program. The full story is that this patch builds on "rL338671: [LICM] Factor out fault legality from canHoistOrSinkInst [NFC]" which pulled this logic out of a common helper routine. As best I can tell, this check was originally added to the helper function for hoisting legality, later an incorrect fastpath for loads/calls was added, and then the bug was fixed by duplicating the fault safety check in the hoist path. This left the redundant check in the common code to pessimize sinking for no reason. I split it out in an NFC, and am not removing the unneccessary check. I wanted there to be something easy to revert in case I missed something. Reviewed by: Anna Thomas (in person) llvm-svn: 338794
* [LICM] Factor out fault legality from canHoistOrSinkInst [NFC]Philip Reames2018-08-022-18/+16
| | | | | | | | | This method has three callers, each of which wanted distinct handling: 1) Sinking into a loop is moving an instruction known to execute before a loop into the loop. We don't need to worry about introducing a fault at all in this case. 2) Hoisting from a loop into a preheader already duplicated the check in the caller. 3) Sinking from the loop into an exit block was the only true user of the code within the routine. For the moment, this has just been lifted into the caller, but up next is examining the logic more carefully. Whitelisting of loads and calls - while consistent with the previous code - is rather suspicious. Either way, a behavior change is worthy of it's own patch. llvm-svn: 338671
* [LICM] hoisting/sinking legality - bail early for unsupported instructionsPhilip Reames2018-08-021-8/+19
| | | | | | Originally, this was part of a larger refactoring I'd planned, but had to abandoned. I figured the minor improvement in readability was worthwhile. llvm-svn: 338663
* Reland r338431: "Add DebugCounters to DivRemPairs"George Burgess IV2018-08-011-0/+6
| | | | | | | | | | | | | | | | | | | | | | | | | (Previously reverted in r338442) I'm told that the breakage came from us using an x86 triple on configs that didn't have x86 enabled. This is remedied by moving the debugcounter test to an x86 directory (where there's also a opt-bisect-isel.ll test for similar reasons). I can't repro the reverse-iteration failure mentioned in the revert with this patch, so I assume that a misconfiguration on my end is what caused that. Original commit message: Add DebugCounters to DivRemPairs For people who don't use DebugCounters, NFCI. Patch by Zhizhou Yang! Differential Revision: https://reviews.llvm.org/D50033 llvm-svn: 338653
* Revert r338431: "Add DebugCounters to DivRemPairs"George Burgess IV2018-07-311-6/+0
| | | | | | | This reverts r338431; the test it added is making buildbots unhappy. Locally, I can repro the failure on reverse-iteration builds. llvm-svn: 338442
* Add DebugCounters to DivRemPairsGeorge Burgess IV2018-07-311-0/+6
| | | | | | | | | | For people who don't use DebugCounters, NFCI. Patch by Zhizhou Yang! Differential Revision: https://reviews.llvm.org/D50033 llvm-svn: 338431
* [NFC] Collect statistics in GuardWideningMax Kazantsev2018-07-311-0/+4
| | | | llvm-svn: 338348
* Remove trailing spaceFangrui Song2018-07-3017-52/+52
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* [NFC] Prepare GuardWidening for widening of cond branchesMax Kazantsev2018-07-301-27/+61
| | | | llvm-svn: 338229
* [SimpleLoopUnswitch] Fix DT updates for trivial branch unswitching.Alina Sbirlea2018-07-281-2/+4
| | | | | | | | | | | | | | | Summary: Fixing 2 issues with the DT update in trivial branch switching, though I don't have a case where DT update fails. 1. After splitting ParentBB->UnswitchedBB edge, new edges become: ParentBB->LoopExitBB->UnswitchedBB, so remove ParentBB->LoopExitBB edge. 2. AFAIU, for multiple CFG changes, DT should be updated using batch updates, vs consecutive addEdge and removeEdge calls. Reviewers: chandlerc, kuhar Subscribers: sanjoy, jlebar, llvm-commits Differential Revision: https://reviews.llvm.org/D49925 llvm-svn: 338180
* Revert r337904: [IPSCCP] Use PredicateInfo to propagate facts from cmp ↵Florian Hahn2018-07-251-118/+8
| | | | | | | | instructions. I suspect it is causing the clang-stage2-Rthinlto failures. llvm-svn: 337956
* Recommit r333268: [IPSCCP] Use PredicateInfo to propagate facts from cmp ↵Florian Hahn2018-07-251-8/+118
| | | | | | | | | | | | | | | | | | | | instructions. r337828 resolves a PredicateInfo issue with unnamed types. Original message: This patch updates IPSCCP to use PredicateInfo to propagate facts to true branches predicated by EQ and to false branches predicated by NE. As a follow up, we should be able to extend it to also propagate additional facts about nonnull. Reviewers: davide, mssimpso, dberlin, efriedma Reviewed By: davide, dberlin llvm-svn: 337904
* [DebugCounters] Keep track of total countsGeorge Burgess IV2018-07-231-1/+1
| | | | | | | | | | | | | | This patch makes debug counters keep track of the total number of times we've called `shouldExecute` for each counter, so it's easier to build automated tooling on top of these. A patch to print these counts is coming soon. Patch by Zhizhou Yang! Differential Revision: https://reviews.llvm.org/D49560 llvm-svn: 337748
* [GVN] Don't use the eliminated load as an available value in phi constructionJohn Brawn2018-07-231-0/+9
| | | | | | | | | | | In ConstructSSAForLoadSet if an available value is actually the load that we're doing SSA construction to eliminate, then we can omit it as SSAUpdate will add in the value for the phi that will be replacing it anyway. This can result in simpler IR which can allow further optimisation. Differential Revision: https://reviews.llvm.org/D44160 llvm-svn: 337686
* [GVNHoist] safeToHoistLdSt allows illegal hoistingAlexandros Lamprineas2018-07-231-1/+1
| | | | | | | | | | | | | Bug fix for PR36787. When reasoning if it's safe to hoist a load we want to make sure that the defining memory access dominates the new insertion point of the hoisted instruction. safeToHoistLdSt calls firstInBB(InsertionPoint,DefiningAccess) which returns false if InsertionPoint == DefiningAccess, and therefore it falsely thinks it's safe to hoist. Differential Revision: https://reviews.llvm.org/D49555 llvm-svn: 337674
* Early exit with cheaper checksAditya Kumar2018-07-211-13/+12
| | | | | | | Reviewers: sebpop,davide,fhahn,trentxintong Differential Revision: https://reviews.llvm.org/D49617 llvm-svn: 337643
* [IPSCCP] Fix for bot failure caused by r337548Florian Hahn2018-07-201-1/+1
| | | | llvm-svn: 337554
* Recommit r328307: [IPSCCP] Use constant range information for comparisons of ↵Florian Hahn2018-07-201-110/+80
| | | | | | | | | | | | | | | | | | | | | | | | | | | parameters. This version contains a fix to add values for which the state in ParamState change to the worklist if the state in ValueState did not change. To avoid adding the same value multiple times, mergeInValue returns true, if it added the value to the worklist. The value is added to the worklist depending on its state in ValueState. Original message: For comparisons with parameters, we can use the ParamState lattice elements which also provide constant range information. This improves the code for PR33253 further and gets us closer to use ValueLatticeElement for all values. Also, as we are using the range information in the solver directly, we do not need tryToReplaceWithConstantRange afterwards anymore. Reviewers: dberlin, mssimpso, davide, efriedma Reviewed By: mssimpso Differential Revision: https://reviews.llvm.org/D43762 llvm-svn: 337548
* [SCCP] Don't use markForcedConstant on branch conditions.Eli Friedman2018-07-191-73/+62
| | | | | | | | | | | | It's more aggressive than we need to be, and leads to strange workarounds in other places like call return value inference. Instead, just directly mark an edge viable. Tests by Florian Hahn. Differential Revision: https://reviews.llvm.org/D49408 llvm-svn: 337507
* [IPSCCP] Run Solve each time we resolved an undef in a function.Florian Hahn2018-07-171-3/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Once we resolved an undef in a function we can run Solve, which could lead to finding a constant return value for the function, which in turn could turn undefs into constants in other functions that call it, before resolving undefs there. Computationally the amount of work we are doing stays the same, just the order we process things is slightly different and potentially there are a few less undefs to resolve. We are still relying on the order of functions in the IR, which means depending on the order, we are able to resolve the optimal undef first or not. For example, if @test1 comes before @testf, we find the constant return value of @testf too late and we cannot use it while solving @test1. This on its own does not lead to more constants removed in the test-suite, probably because currently we have to be very lucky to visit applicable functions in the right order. Maybe we manage to come up with a better way of resolving undefs in more 'profitable' functions first. Reviewers: efriedma, mssimpso, davide Reviewed By: efriedma, davide Differential Revision: https://reviews.llvm.org/D49385 llvm-svn: 337283
* [LSR] If no Use is interesting, early return.Tim Shen2018-07-131-1/+3
| | | | | | | | | | | | | | | Summary: By looking at the callers of getUse(), we can see that even though IVUsers may offer uses, but they may not be interesting to LSR. It's possible that none of them is interesting. Reviewers: sanjoy Subscribers: jlebar, hiraditya, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D49049 llvm-svn: 337072
* Temporarily revert "Recommit r328307: [IPSCCP] Use constant range ↵Eric Christopher2018-07-121-81/+111
| | | | | | | | | | information for comparisons of parameters." as it's causing miscompiles. A testcase was provided in the original review thread. This reverts commit r336098. llvm-svn: 336877
* [LoopIdiomRecognize] Don't convert a do while loop to ctlz.Craig Topper2018-07-111-10/+15
| | | | | | | | | | | | | | | | | | | This commit suppresses turning loops like this into "(bitwidth - ctlz(input))". unsigned foo(unsigned input) { unsigned num = 0; do { ++num; input >>= 1; } while (input != 0); return num; } The loop version returns a value of 1 for both an input of 0 and an input of 1. Converting to a naive ctlz does not preserve that. Theoretically we could do better if we checked isKnownNonZero or we could insert a select to handle the divergence. But until we have motivating cases for that, this is the easiest solution. llvm-svn: 336864
OpenPOWER on IntegriCloud