summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
* Add const qualifiers to appease bots; NFCSanjoy Das2016-05-191-3/+3
| | | | llvm-svn: 270155
* [GuardWidening] Introduce range check mergingSanjoy Das2016-05-191-0/+244
| | | | | | | | | | | | | | | | | | | | | | Sequences of range checks expressed using guards, like guard((I - 2) u< L) guard((I - 1) u< L) guard((I + 0) u< L) guard((I + 1) u< L) guard((I + 2) u< L) can sometimes be combined into a smaller sequence: guard((I - 2) u< L AND (I + 2) u< L) if we can prove that (I - 2) u< L AND (I + 2) u< L implies all of checks expressed in the previous sequence. This change teaches GuardWidening to do this kind of merging when feasible. llvm-svn: 270151
* [SCCP] Prefer class to struct.Davide Italiano2016-05-191-2/+4
| | | | llvm-svn: 270074
* [GuardWidening] Use getEquivalentICmp to fold constant comparesSanjoy Das2016-05-191-13/+23
| | | | | | | `ConstantRange::getEquivalentICmp` is more general, and better factored. llvm-svn: 270019
* [LowerGuards] Rename variable; NFCSanjoy Das2016-05-181-3/+3
| | | | | | | PredicatePassProbability is a better name for what LikelyBranchWeight was trying to express. llvm-svn: 269999
* New pass: guard wideningSanjoy Das2016-05-183-0/+430
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Implement guard widening in LLVM. Description from GuardWidening.cpp: The semantics of the `@llvm.experimental.guard` intrinsic lets LLVM transform it so that it fails more often that it did before the transform. This optimization is called "widening" and can be used hoist and common runtime checks in situations like these: ``` %cmp0 = 7 u< Length call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ] call @unknown_side_effects() %cmp1 = 9 u< Length call @llvm.experimental.guard(i1 %cmp1) [ "deopt"(...) ] ... ``` to ``` %cmp0 = 9 u< Length call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ] call @unknown_side_effects() ... ``` If `%cmp0` is false, `@llvm.experimental.guard` will "deoptimize" back to a generic implementation of the same function, which will have the correct semantics from that point onward. It is always _legal_ to deoptimize (so replacing `%cmp0` with false is "correct"), though it may not always be profitable to do so. NB! This pass is a work in progress. It hasn't been tuned to be "production ready" yet. It is known to have quadriatic running time and will not scale to large numbers of guards Reviewers: reames, atrick, bogner, apilipenko, nlewycky Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20143 llvm-svn: 269997
* [LoopUnrollAnalyzer] Take into account cost of instructions controlling ↵Michael Zolotukhin2016-05-181-0/+1
| | | | | | | | | branches, along with their operands. Previously, we didn't add their and their operands cost, which could've resulted in unrolling loops for no actual benefit. llvm-svn: 269985
* [PM] Port per-function SCCP to the new pass manager.Davide Italiano2016-05-182-45/+53
| | | | llvm-svn: 269937
* [PM] Port DSE to the new pass managerJustin Bogner2016-05-172-322/+340
| | | | | | Patch by JakeVanAdrighem. Thanks! llvm-svn: 269847
* [Guards] Add branch metadata when loweringSanjoy Das2016-05-171-0/+10
| | | | | | | Guards are expected to basically never fail. Reflect this in the branch probabilities in their lowered form. llvm-svn: 269791
* [RewriteStatepointsForGC] Remove obsolete assertionIgor Laevsky2016-05-171-8/+0
| | | | | | | | | | This is assertion is no longer necessary since we never record constants in the live set anyway. (They are never recorded in the initial live set, and constant bases are removed near line 2119) Differential Revision: http://reviews.llvm.org/D20293 llvm-svn: 269764
* [PM] RewriterStatepointForGC: add missing dependency.Davide Italiano2016-05-161-0/+1
| | | | llvm-svn: 269624
* Move helper classes into anonymous namespaces. NFC.Benjamin Kramer2016-05-151-1/+1
| | | | llvm-svn: 269591
* [PM/SCCP] Fix pass dependencies.Davide Italiano2016-05-151-1/+4
| | | | | | | | | | | | TargetLibraryInfoWrapperPass is a dependency of SCCP but it's not listed as such. Chandler pointed out this is an easy mistake to make which only surfaces in weird crashes with some flag combinations. This code will go away anyway at some point in the future, but as long as it's (still) exercised, try to make it correct. llvm-svn: 269589
* [SCCP] Use range-based for loops. NFC.Davide Italiano2016-05-141-10/+10
| | | | llvm-svn: 269578
* [PM] Port LowerAtomic to the new pass manager.Davide Italiano2016-05-132-42/+56
| | | | llvm-svn: 269511
* Revert "Revert "[Unroll] Implement a conservative and monotonically ↵Michael Zolotukhin2016-05-131-13/+178
| | | | | | | | | | increasing cost tracking system during the full unroll heuristic analysis that avoids counting any instruction cost until that instruction becomes "live" through a side-effect or use outside the..."" This reverts commit r269395. Try to reapply with a fix from chapuni. llvm-svn: 269486
* Rename getLargestLegalIntTypeSize to getLargestLegalIntTypeSizeInBits(). NFC.Jun Bum Lim2016-05-131-1/+1
| | | | | | | | | | | | Summary: Rename DataLayout::getLargestLegalIntTypeSize to DataLayout::getLargestLegalIntTypeSizeInBits() to prevent similar mistakes fixed in r269433. Reviewers: joker.eph, mcrosier Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20248 llvm-svn: 269456
* [EarlyCSE] Change key type of AvailableCalls to Instruction*. NFCI.Geoff Berry2016-05-131-3/+4
| | | | llvm-svn: 269445
* [MemCpyOpt] Use MaxIntSize in byte instead of bitJun Bum Lim2016-05-131-1/+1
| | | | | | | | | | | | Summary: This change fix the bug in isProfitableToUseMemset() where MaxIntSize shoule be in byte, not bit. Reviewers: arsenm, joker.eph, mcrosier Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20176 llvm-svn: 269433
* Revert "[Unroll] Implement a conservative and monotonically increasing cost ↵Michael Zolotukhin2016-05-131-178/+13
| | | | | | | | | | | tracking system during the full unroll heuristic analysis that avoids counting any instruction cost until that instruction becomes "live" through a side-effect or use outside the..." This reverts commit r269388. It caused some bots to fail, I'm reverting it until I investigate the issue. llvm-svn: 269395
* [LoopDist] Only run LAA for loops with the pragmaAdam Nemet2016-05-131-17/+17
| | | | | | | This should fix some compile-time regressions after r267672. Thanks to Chris Matthews for bisecting it. llvm-svn: 269392
* [Unroll] Implement a conservative and monotonically increasing cost tracking ↵Michael Zolotukhin2016-05-131-13/+178
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | system during the full unroll heuristic analysis that avoids counting any instruction cost until that instruction becomes "live" through a side-effect or use outside the... Summary: ...loop after the last iteration. This is really hard to do correctly. The core problem is that we need to model liveness through the induction PHIs from iteration to iteration in order to get the correct results, and we need to correctly de-duplicate the common subgraphs of instructions feeding some subset of the induction PHIs. All of this can be driven either from a side effect at some iteration or from the loop values used after the loop finishes. This patch implements this by storing the forward-propagating analysis of each instruction in a cache to recall whether it was free and whether it has become live and thus counted toward the total unroll cost. Then, at each sink for a value in the loop, we recursively walk back through every value that feeds the sink, including looping back through the iterations as needed, until we have marked the entire input graph as live. Because we cache this, we never visit instructions more than twice -- once when we analyze them and put them into the cache, and once when we count their cost towards the unrolled loop. Also, because the cache is only two bits and because we are dealing with relatively small iteration counts, we can store all of this very densely in memory to avoid this from becoming an excessively slow analysis. The code here is still pretty gross. I would appreciate suggestions about better ways to factor or split this up, I've stared too long at the algorithmic side to really have a good sense of what the design should probably look at. Also, it might seem like we should do all of this bottom-up, but I think that is a red herring. Specifically, the simplification power is *much* greater working top-down. We can forward propagate very effectively, even across strange and interesting recurrances around the backedge. Because we use data to propagate, this doesn't cause a state space explosion. Doing this level of constant folding, etc, would be very expensive to do bottom-up because it wouldn't be until the last moment that you could collapse everything. The current solution is essentially a top-down simplification with a bottom-up cost accounting which seems to get the best of both worlds. It makes the simplification incremental and powerful while leaving everything dead until we *know* it is needed. Finally, a core property of this approach is its *monotonicity*. At all times, the current UnrolledCost is a conservatively low estimate. This ensures that we will never early-exit from the analysis due to exceeding a threshold when if we had continued, the cost would have gone back below the threshold. These kinds of bugs can cause incredibly hard to track down random changes to behavior. We could use a techinque similar (but much simpler) within the inliner as well to avoid considering speculated code in the inline cost. Reviewers: chandlerc Subscribers: sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D11758 llvm-svn: 269388
* [PM] Port of the DepndenceAnalysis to the new PM.Chandler Carruth2016-05-122-9/+9
| | | | | | | | | | | | | Ported DA to the new PM by splitting the former DependenceAnalysis Pass into a DependenceInfo result type and DependenceAnalysisWrapperPass type and adding a new PM-style DependenceAnalysis analysis pass returning the DependenceInfo. Patch by Philip Pfaffe, most of the review by Justin. Differential Revision: http://reviews.llvm.org/D18834 llvm-svn: 269370
* [PM] Make LowerAtomic a FunctionPass.Davide Italiano2016-05-121-5/+16
| | | | | | Differential Revision: http://reviews.llvm.org/D20025 llvm-svn: 269322
* [SCCP] Resolve shifts beyond the bitwidth to undefDavid Majnemer2016-05-121-0/+16
| | | | | | | | | Shifts beyond the bitwidth are undef but SCCP resolved them to zero. Instead, DTRT and resolve them to undef. This reimplements the transform which caused PR27712. llvm-svn: 269269
* Revert "[SCCP] Partially propagate informations when the input is not fully ↵Davide Italiano2016-05-111-3/+0
| | | | | | | | defined." This reverts commit r269105 as it caused PR27712. llvm-svn: 269252
* Revert "MemCpyOpt: combine local load/store sequences into memcpy."Tim Northover2016-05-101-222/+48
| | | | | | | This reverts commit r269125. It was in my tree when I ran "git svn dcommit". It's really still under review. llvm-svn: 269127
* MemCpyOpt: combine local load/store sequences into memcpy.Tim Northover2016-05-101-48/+222
| | | | | | | | Sort of the BB-local equivalent to idiom-recognizer: if we have a basic-block that really implements a memcpy operation, backends can benefit from seeing this. llvm-svn: 269125
* Loop unroller: set thresholds for optsize and minsize functions to zeroHans Wennborg2016-05-101-2/+2
| | | | | | | | | | | | | | | Before r268509, Clang would disable the loop unroll pass when optimizing for size. That commit enabled it to be able to support unroll pragmas in -Os builds. However, this regressed binary size in one of Chromium's DLLs with ~100 KB. This restores the original behaviour of no unrolling at -Os, but doing it in LLVM instead of Clang makes more sense, and also allows the pragmas to keep working. Differential revision: http://reviews.llvm.org/D20115 llvm-svn: 269124
* Enable loopreroll for sext of loop control only IVLawrence Hu2016-05-101-12/+33
| | | | | | | | | This patch extend loopreroll to allow the instruction chain of loop control only IV has sext. Differential Revision: http://reviews.llvm.org/D19820 llvm-svn: 269121
* Revert r26084: Enable loopreroll for sext of loop control only IVLawrence Hu2016-05-101-33/+12
| | | | llvm-svn: 269119
* [SCCP] Partially propagate informations when the input is not fully defined.Davide Italiano2016-05-101-0/+3
| | | | | | | | | | With this patch: %r1 = lshr i64 -1, 4294967296 -> undef Before this patch: %r1 = lshr i64 -1, 4294967296 -> 0 llvm-svn: 269105
* Enable loopreroll for sext of loop control only IVLawrence Hu2016-05-101-12/+33
| | | | | | | This patch extend loopreroll to allow the instruction chain of loop control only IV has sext. llvm-svn: 269084
* Update Debug Intrinsics in RewriteUsesOfClonedInstructions in LoopRotationChuang-Yu Cheng2016-05-101-0/+34
| | | | | | | | | | | | | | | | | | | | | | Loop rotation clones instruction from the old header into the preheader. If there were uses of values produced by these instructions that were outside the loop, we have to insert PHI nodes to merge the two values. If the values are used by DbgIntrinsics they will be used as a MetadataAsValue of a ValueAsMetadata of the original values, and iterating all of the uses of the original value will not update the DbgIntrinsics. The new code checks if the values are used by DbgIntrinsics and if so, updates them using essentially the same logic as the original code. The attached testcase demonstrates the issue. Without the fix, the DbgIntrinic outside the loop uses values computed inside the loop, even though these values do not dominate the DbgIntrinsic. Author: Thomas Jablin (tjablin) Reviewers: dblaikie aprantl kbarton hfinkel cycheng http://reviews.llvm.org/D19564 llvm-svn: 269034
* [LAA] Rename "isStridedPtr" with "getPtrStride". NFC.Denis Zobnin2016-05-101-2/+2
| | | | | | | Changing misleading function name was approved in http://reviews.llvm.org/D17268. Patch by Roman Shirokiy. llvm-svn: 269021
* [GVN] PRE of unordered loadsPhilip Reames2016-05-061-8/+4
| | | | | | Again, fairly simple. Only change is ensuring that we actually copy the property of the load correctly. The aliasing legality constraints were already handled by the FRE patches. There's nothing special about unorder atomics from the perspective of the PRE algorithm itself. llvm-svn: 268804
* [RS4GC] Fix typo in commentSanjoy Das2016-05-061-1/+1
| | | | llvm-svn: 268790
* [GVN] Handle unordered atomics in cross block FREPhilip Reames2016-05-061-5/+5
| | | | | | You'll note there are essentially no code changes here. Cross block FRE heavily reuses code from the block local FRE. All of the tricky parts were done as part of the previous patch and the refactoring that removed the original code duplication. llvm-svn: 268775
* [GVN] Do local FRE for unordered atomic loadsPhilip Reames2016-05-061-4/+21
| | | | | | | | | | This patch is the first in a small series teaching GVN to optimize unordered loads aggressively. This change just handles block local FRE because that's the simplest thing which lets me test MDA, and the AvailableValue pieces. Somewhat suprisingly, MDA appears fine and only a couple of small changes are needed in GVN. Once this is in, I'll tackle non-local FRE and PRE. The former looks like a natural extension of this, the later will require a couple of minor changes. Differential Revision: http://reviews.llvm.org/D19440 llvm-svn: 268770
* [EarlyCSE] Rename a variable for clarity [NFC]Philip Reames2016-05-061-8/+8
| | | | llvm-svn: 268701
* [PM] Port Interprocedural SCCP to the new pass manager.Davide Italiano2016-05-052-43/+54
| | | | llvm-svn: 268684
* Revert http://reviews.llvm.org/D19926 as it breaks tests.Dehao Chen2016-05-051-24/+28
| | | | llvm-svn: 268681
* Simplify CFG before assigning discriminator.Dehao Chen2016-05-051-28/+24
| | | | | | | | | | | | Summary: We need to clean up CFG before assigning discriminator to minimize the impact of optimization on debug info. Reviewers: davidxl, dblaikie, dnovillo Subscribers: dnovillo, danielcdh, llvm-commits Differential Revision: http://reviews.llvm.org/D19926 llvm-svn: 268675
* Remove dead include. NFC.Chad Rosier2016-05-051-1/+0
| | | | llvm-svn: 268654
* clang-format some files in preparation of coming patch reviews.Dehao Chen2016-05-052-233/+228
| | | | llvm-svn: 268583
* [LoopDataPrefetch] Add optimization remarkAdam Nemet2016-05-051-1/+6
| | | | | | | With -Rpass=loop-data-prefetch, show the memory access that got prefetched. llvm-svn: 268578
* Revert "[SCCP] Throw away dead code. NFC."Davide Italiano2016-05-041-0/+3
| | | | | | This reverts commit r268568, as it broke the bots. llvm-svn: 268570
* [SCCP] Throw away dead code. NFC.Davide Italiano2016-05-041-3/+0
| | | | llvm-svn: 268568
* Use a uniform name for the load combine pass. NFC.Chad Rosier2016-05-041-6/+5
| | | | llvm-svn: 268507
OpenPOWER on IntegriCloud