summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
* Revert "Revert r330403 and r330413."Michael Zolotukhin2018-04-201-26/+30
| | | | | | | | | | | Reapply the patches with a fix. Thanks Ilya and Hans for the reproducer! This reverts commit r330416. The issue was that removing predecessors invalidated uses that we stored for rewrite. The fix is to finish manipulating with CFG before we select uses for rewrite. llvm-svn: 330431
* Revert r330403 and r330413.Ilya Biryukov2018-04-201-20/+16
| | | | | | | | | | | | | | | | Revert r330413: "[SSAUpdaterBulk] Use SmallVector instead of DenseMap for storing rewrites." Revert r330403 "Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." one more time." r330403 commit seems to crash clang during our integrate while doing PGO build with the following stacktrace: #2 llvm::SSAUpdaterBulk::RewriteAllUses(llvm::DominatorTree*, llvm::SmallVectorImpl<llvm::PHINode*>*) #3 llvm::JumpThreadingPass::ThreadEdge(llvm::BasicBlock*, llvm::SmallVectorImpl<llvm::BasicBlock*> const&, llvm::BasicBlock*) #4 llvm::JumpThreadingPass::ProcessThreadableEdges(llvm::Value*, llvm::BasicBlock*, llvm::jumpthreading::ConstantPreference, llvm::Instruction*) #5 llvm::JumpThreadingPass::ProcessBlock(llvm::BasicBlock*) The crash happens while compiling 'lib/Analysis/CallGraph.cpp'. r3340413 is reverted due to conflicting changes. llvm-svn: 330416
* [SSAUpdaterBulk] Use SmallVector instead of DenseMap for storing rewrites.Michael Zolotukhin2018-04-201-3/+1
| | | | llvm-svn: 330413
* Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." one more time.Michael Zolotukhin2018-04-201-16/+22
| | | | | | | | | Hopefully, changing set to vector removes nondeterminism detected by some bots, or the new assert will catch something. This reverts commit r330180. llvm-svn: 330403
* Refine the loop rotation's APIJin Lin2018-04-191-3/+4
| | | | | | | | | | | | | | | | Summary: The following changes addresses the following two issues. 1) The existing loop rotation pass contains both loop latch simplification and loop rotation. So one flag RotationOnly is added to be passed to the loop rotation pass. 2) The threshold value is initialized with MAX_UINT since the loop rotation utility should not have threshold limit. Reviewers: dmgreen, efriedma Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D45582 llvm-svn: 330362
* [PM/LoopUnswitch] Detect irreducible control flow within loops and skip ↵Chandler Carruth2018-04-191-0/+13
| | | | | | | | | | | | | | | | | | | | unswitching non-trivial edges. Summary: This fixes the bug pointed out in review with non-trivial unswitching. This also provides a basis that should make it pretty easy to finish fleshing out a routine to scan an entire function body for irreducible control flow, but this patch remains minimal for disabling loop unswitch. Reviewers: sanjoy, fedor.sergeev Subscribers: mcrosier, hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D45754 llvm-svn: 330357
* [Reassociate] fix formatting; NFCSanjay Patel2018-04-191-4/+3
| | | | llvm-svn: 330348
* [NewGVN] Add ops as dependency if we cannot find a leader for ValueOp.Florian Hahn2018-04-191-2/+11
| | | | | | | | | | | | | | | | | If those operands change, we might find a leader for ValueOp, which could enable new phi-of-op creation. This fixes a case where we missed creating a phi-of-ops node. With D43865 and this patch, bootstrapping clang/llvm works with -enable-newgvn, whereas without it, the "value changed after iteration" assertion is triggered. Reviewers: dberlin, davide Reviewed By: dberlin Differential Revision: https://reviews.llvm.org/D42180 llvm-svn: 330334
* [IRCE] Only check for NSW on equality predicatesSam Parker2018-04-181-29/+14
| | | | | | | | | | | After investigation discussed in D45439, it would seem that the nsw flag restriction is unnecessary in most cases. So the IsInductionVar lambda has been removed, the functionality extracted, and now only require nsw when using eq/ne predicates. Differential Revision: https://reviews.llvm.org/D45617 llvm-svn: 330256
* Revert "Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." again."Michael Zolotukhin2018-04-171-22/+15
| | | | | | This reverts r330175. There are still stage3/stage4 miscompares. llvm-svn: 330180
* Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." again.Michael Zolotukhin2018-04-171-15/+22
| | | | | | | | | One more, hopefully the last, bug is fixed: when forming UsesToRewrite we should ignore phi operands coming from edges that we want to delete. This reverts r329910. llvm-svn: 330175
* [NFC] ConstantOffsetExtractor::CanTraceInto(): add FIXME: no testsRoman Lebedev2018-04-151-0/+2
| | | | | | | | As suggested in https://reviews.llvm.org/D45631#1068338, looking at haveNoCommonBitsSet() users, and *trying* to show the change effect elsewhere. llvm-svn: 330100
* [NFC] fix trivial typos in document and commentsHiroshi Inoue2018-04-141-1/+1
| | | | | | "not not" -> "not" etc llvm-svn: 330083
* [Transforms] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang2018-04-1312-42/+44
| | | | | | | | | | | | | | | | | | | | | | Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer the comments section in D44363 for a list of all the required patches. Reviewers: kcc, pcc, danielcdh, jmolloy, sanjoy, dberlin, ruiu Reviewed By: ruiu Subscribers: ruiu, llvm-commits Differential Revision: https://reviews.llvm.org/D45142 llvm-svn: 330059
* [CallSiteSplit] Fix comment. NFCXin Tong2018-04-131-1/+1
| | | | llvm-svn: 329987
* Revert "Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." one more time."Benjamin Kramer2018-04-121-18/+13
| | | | | | This reverts commit r329865. Causes stage2/stage3 miscompare. llvm-svn: 329910
* [IRCE] isKnownNonNegative helper functionSam Parker2018-04-121-2/+9
| | | | | | | | | | Created a helper function to query for non negative SCEVs. Uses the SGE predicate to catch constants that could be interpreted as negative. Differential Revision: https://reviews.llvm.org/D45481 llvm-svn: 329907
* [NFC] fix trivial typos in documents and commentsHiroshi Inoue2018-04-121-1/+1
| | | | | | "is is" -> "is", "if if" -> "if", "or or" -> "or" llvm-svn: 329878
* Reapply "[PR16756] Use SSAUpdaterBulk in JumpThreading." one more time.Michael Zolotukhin2018-04-111-13/+18
| | | | | | This reapplies commit r329644. llvm-svn: 329865
* [CVP] simplify phi with constant incoming values that match common variable ↵Sanjay Patel2018-04-101-0/+60
| | | | | | | | | | | | | | | | | | | | | | | edge values This is based on an example that was recently posted on llvm-dev: void *propagate_null(void* b, int* g) { if (!b) { return 0; } (*g)++; return b; } https://godbolt.org/g/xYk3qG The original code or constant propagation in other passes has obscured the fact that the phi can be removed completely. Differential Revision: https://reviews.llvm.org/D45448 llvm-svn: 329755
* Revert "[PR16756] Use SSAUpdaterBulk in JumpThreading." one more time.Michael Zolotukhin2018-04-101-18/+13
| | | | | | This reverts r329661. Bots are still unhappy. llvm-svn: 329666
* Revert "Revert "[PR16756] Use SSAUpdaterBulk in JumpThreading.""Michael Zolotukhin2018-04-101-13/+18
| | | | | | This reapplies commit r329644. llvm-svn: 329661
* Revert "[PR16756] Use SSAUpdaterBulk in JumpThreading."Michael Zolotukhin2018-04-101-18/+13
| | | | | | This reverts commit r329644. llvm-svn: 329650
* [PR16756] Use SSAUpdaterBulk in JumpThreading.Michael Zolotukhin2018-04-091-13/+18
| | | | | | | | | | | | | | | | | Summary: SSAUpdater is a bottleneck in JumpThreading, and this patch improves the situation by using SSAUpdaterBulk instead. Compile time impact: no noticable changes on CTMark, a big improvement on the test from PR16756. Reviewers: dberlin, davide, MatzeB Subscribers: llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D44282 llvm-svn: 329644
* [MergeICmp] Update debug msg.NFCXin Tong2018-04-091-1/+1
| | | | llvm-svn: 329572
* [MergeICmp] Split blocks that do other work.Xin Tong2018-04-091-19/+118
| | | | | | | | | | | | | | | Summary: We do not try to move the instructions and split the block till we know the blocks can be split, i.e. BCE-cmp-insts can be separated from non-BCE-cmp-insts. Reviewers: davide, courbet Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D44443 llvm-svn: 329564
* [IRCE] Relax restriction on collected range checksMax Kazantsev2018-04-091-9/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In IRCE, we have a very old legacy check that works when we collect comparisons that we treat as range checks. It ensures that the value against which the indvar is compared is loop invariant and is also positive. This latter condition remained there since the times when IRCE was only able to handle signed latch comparison. As the optimization evolved, it now learned how to intersect signed or unsigned ranges, and this logic has no reliance on the fact that the right border of each range should be positive. The old implementation of this non-negativity check was also naive enough and just looked into ranges (while most of other IRCE logic tries to use power of SCEV implications), so this check did not allow to deal with the most simple case that looks like follows: int size; // not known non-negative int length; //known non-negative; i = 0; if (size != 0) { do { range_check(i < size); range_check(i < length); ++i; } while (i < size) } In this case, even if from some dominating conditions IRCE could parse loop structure, it could only remove the range check against `length` and simply ignored the check against `size`. In this patch we remove this obsolete check. It will allow IRCE to pick comparison against `size` as a potential range check and then let Range Intersection logic decide whether it is OK to eliminate it or not. Differential Revision: https://reviews.llvm.org/D45362 Reviewed By: samparker llvm-svn: 329547
* [NFC] fix trivial typos in comments and error messageHiroshi Inoue2018-04-091-1/+1
| | | | | | "is is" -> "is", "are are" -> "are" llvm-svn: 329546
* [LIR] Reorder header. NFCXin Tong2018-04-081-1/+1
| | | | llvm-svn: 329530
* [EarlyCSE] Add debug counter for debugging mis-optimizations. NFC.Geoff Berry2018-04-061-24/+60
| | | | | | | | | | Reviewers: reames, spatel, davide, dberlin Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D45162 llvm-svn: 329443
* [NFC] Add missing end of line symbolsMax Kazantsev2018-04-061-3/+3
| | | | llvm-svn: 329383
* [LoopInterchange] Add stats counter for number of interchanged loops.Florian Hahn2018-04-051-0/+4
| | | | | | | | | | Reviewers: samparker, karthikthecool, blitz.opensource Reviewed By: samparker Differential Revision: https://reviews.llvm.org/D45209 llvm-svn: 329269
* [LoopInterchange] Preserve LoopInfo after interchanging.Florian Hahn2018-04-051-13/+72
| | | | | | | | | | | | | | LoopInterchange relies on LoopInfo being up-to-date, so we should preserve it after interchanging. This patch updates restructureLoops to move the BBs of the interchanged loops to the right place. Reviewers: davide, efriedma, karthikthecool, mcrosier Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D45278 llvm-svn: 329264
* [CallSiteSplitting] Do not perform callsite splitting inside landing padTaewook Oh2018-04-051-0/+6
| | | | | | | | | | | | | | | | | | | Summary: If the callsite is inside landing pad, do not perform callsite splitting. Callsite splitting uses utility function llvm::DuplicateInstructionsInSplitBetween, which eventually calls llvm::SplitEdge. llvm::SplitEdge calls llvm::SplitCriticalEdge with an assumption that the function returns nullptr only when the target edge is not a critical edge (and further assumes that if the return value was not nullptr, the predecessor of the original target edge always has a single successor because critical edge splitting was successful). However, this assumtion is not true because SplitCriticalEdge returns nullptr if the destination block is a landing pad. This invalid assumption results assertion failure. Fundamental solution might be fixing llvm::SplitEdge to not to rely on the invalid assumption. However, it'll involve a lot of work because current API assumes that llvm::SplitEdge never fails. Instead, this patch makes callsite splitting to not to attempt splitting if the callsite is in a landing pad. Attached test case will crash with assertion failure without the fix. Reviewers: fhahn, junbuml, dberlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D45130 llvm-svn: 329250
* StructurizeCFG: Test for branch divergence correctlyNicolai Haehnle2018-04-041-13/+54
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Fixes cases like the new test @nonuniform. In that test, %cc itself is a uniform value; however, when reading it after the end of the loop in basic block %if, its value is effectively non-uniform, so the branch is non-uniform. This problem was encountered in https://bugs.freedesktop.org/show_bug.cgi?id=103743; however, this change in itself is not sufficient to fix that bug, as there is another issue in the AMDGPU backend. As discovered after committing an earlier version of this change, this exposes a subtle interaction between this pass and DivergenceAnalysis: since we remove and re-create branch instructions, we can no longer rely on DivergenceAnalysis for branches in subregions that were already processed by the pass. Explicitly remove branch instructions from DivergenceAnalysis to avoid dangling pointers as a matter of defensive programming, and change how we detect non-uniform subregions. Change-Id: I32bbffece4a32f686fab54964dae1a5dd72949d4 Differential Revision: https://reviews.llvm.org/D43743 llvm-svn: 329165
* [Hexagon] peel loops with runtime small trip countsIkhlas Ajbar2018-04-031-3/+0
| | | | | | | | Move the check canPeel() to Hexagon Target before setting PeelCount. Differential Revision: https://reviews.llvm.org/D44880 llvm-svn: 329129
* [LoopInterchange] Add remark for calls preventing interchanging.Florian Hahn2018-04-031-0/+7
| | | | | | | | | | | | | | It also updates test/Transforms/LoopInterchange/call-instructions.ll to use accesses where we can prove dependence after D35430. Reviewers: sebpop, karthikthecool, blitz.opensource Reviewed By: sebpop Differential Revision: https://reviews.llvm.org/D45206 llvm-svn: 329111
* peel loops with runtime small trip countsIkhlas Ajbar2018-04-031-0/+3
| | | | | | | | | | For Hexagon, peeling loops with small runtime trip count is beneficial for our benchmarks. We set PeelCount in HexagonTargetInfo.cpp and we use PeelCount set by the target for computing the desired peel count. Differential Revision: https://reviews.llvm.org/D44880 llvm-svn: 329042
* Fix a bunch of typoes. NFCFangrui Song2018-03-302-3/+3
| | | | llvm-svn: 328907
* [NFC][LICM] Rearrange checks to have the cheap bail out firstPhilip Reames2018-03-291-6/+6
| | | | llvm-svn: 328822
* [JumpThreading] Don't select an edge that we know we can't threadHaicheng Wu2018-03-291-1/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In r312664 (D36404), JumpThreading stopped threading edges into loop headers. Unfortunately, I observed a significant performance regression as a result of this change. Upon further investigation, the problematic pattern looked something like this (after many high level optimizations): while (true) { bool cond = ...; if (!cond) { <body> } if (cond) break; } Now, naturally we want jump threading to essentially eliminate the second if check and hook up the edges appropriately. However, the above mentioned change, prevented it from doing this because it would have to thread an edge into the loop header. Upon further investigation, what is happening is that since both branches are threadable, JumpThreading picks one of them at arbitrarily. In my case, because of the way that the IR ended up, it tended to pick the one to the loop header, bailing out immediately after. However, if it had picked the one to the exit block, everything would have worked out fine (because the only remaining branch would then be folded, not thraded which is acceptable). Thus, to fix this problem, we can simply eliminate loop headers from consideration as possible threading targets earlier, to make sure that if there are multiple eligible branches, we can still thread one of the ones that don't target a loop header. Patch by Keno Fischer! Differential Revision: https://reviews.llvm.org/D42260 llvm-svn: 328798
* [LoopRotate] Restructuring LoopRotation.cpp to create Loop Rotation Pass ↵David Green2018-03-291-581/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | with Loop Rotation Utility Interface The existing LoopRotation.cpp is implemented as one of loop passes instead of being a utility. The user cannot easily perform the loop rotation selectively (or on demand) under different optimization level. For example, the loop rotation is needed as part of the logic to convert a loop into a loop with bottom test for a transformation. If the loop rotation is simply added as a loop pass before the transformation, the pass is skipped if it is compiled at –O0 or if it is explicitly disabled by the user, causing the compiler to generate incorrect code. Furthermore, as a loop pass it will rotate all loops instead of just the relevant loops. We provide a utility interface for the loop rotation so that the loop rotation can be called on demand. The changeset is as follows: - Create a new file lib/Transforms/Utils/LoopRotationUtils.cpp and move the main implementation of class LoopRotate into this file. - Create a new file llvm/include/Transform/Utils/LoopRotationUtils.h with the interface LoopRotation(...). - Original LoopRotation.cpp is changed to use the utility function LoopRotation in LoopRotationUtils.cpp. This is done in the same way community did for mem-to-reg implementation. Patch by Jin Lin! Differential Revision: https://reviews.llvm.org/D44595 llvm-svn: 328766
* Plumb useAA through TargetTransformInfo to remove Transforms->CodeGen header ↵David Blaikie2018-03-281-13/+9
| | | | | | | | dependency Thanks to echristo for the pointers on direction. llvm-svn: 328737
* Oops - moved slightly too many things from Scalar to Utils. Move ↵David Blaikie2018-03-281-0/+4
| | | | | | LoopSimplifyCFG things back llvm-svn: 328720
* Transforms: Introduce Transforms/Utils.h rather than spreading the ↵David Blaikie2018-03-2810-12/+9
| | | | | | | | | declarations amongst Scalar.h and IPO.h Fixes layering - Transforms/Utils shouldn't depend on including a Scalar or IPO header, because Scalar and IPO depend on Utils. llvm-svn: 328717
* 80-line wrap. NFCXin Tong2018-03-271-1/+2
| | | | llvm-svn: 328660
* [IRCE] Enable decreasing loops of non-const boundSam Parker2018-03-271-52/+74
| | | | | | | | | | | | | | As a follow-up to r328480, this updates the logic for the decreasing safety checks in a similar manner: - CanBeMax is replaced by CannotBeMaxInLoop which queries isLoopEntryGuardedByCond on the maximum value. - SumCanReachMin is replaced by isSafeDecreasingBound which includes some logic from parseLoopStructure and, again, has been updated to use isLoopEntryGuardedByCond on the given bounds. Differential Revision: https://reviews.llvm.org/D44776 llvm-svn: 328613
* [LSR] Allow giving priority to post-incrementing addressing modesKrzysztof Parzyszek2018-03-261-9/+66
| | | | | | | | | | | Implement TTI interface for targets to indicate that the LSR should give priority to post-incrementing addressing modes. Combination of patches by Sebastian Pop and Brendon Cahoon. Differential Revision: https://reviews.llvm.org/D44758 llvm-svn: 328490
* [IRCE] Enable increasing loops of variable boundsSam Parker2018-03-261-58/+78
| | | | | | | | | | | | | | | | | | | | | CanBeMin is currently used which will report true for any unknown values, but often a check is performed outside the loop which covers this situation: for (int i = 0; i < N; ++i) ... if (N > 0) for (int i = 0; i < N; ++i) ... So I've add 'LoopGuardedAgainstMin' which reports whether N is greater than the minimum value which then allows loop with a variable loop count to be optimised. I've also moved the increasing bound checking into its own function and replaced SumCanReachMax is another isLoopEntryGuardedByCond function. llvm-svn: 328480
* [GuardWidening] Group code by class [NFC]Philip Reames2018-03-231-39/+40
| | | | llvm-svn: 328387
OpenPOWER on IntegriCloud