summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/JumpThreading.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Use the range variant of find instead of unpacking begin/endDavid Majnemer2016-08-111-2/+1
| | | | | | | | | If the result of the find is only used to compare against end(), just use is_contained instead. No functionality change is intended. llvm-svn: 278433
* Consistently use FunctionAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278077
* [JumpThreading] Fix handling of aliasing metadata.Eli Friedman2016-08-081-6/+16
| | | | | | | | | | | | | | | | | | Summary: The correctness fix here is that when we CSE a load with another load, we need to combine the metadata on the two loads. This matches the behavior of other passes, like instcombine and GVN. There's also a minor optimization improvement here: for load PRE, the aliasing metadata on the inserted load should be the same as the metadata on the original load. Not sure why the old code was throwing it away. Issue found by inspection. Differential Revision: http://reviews.llvm.org/D21460 llvm-svn: 277977
* Don't remove side effecting instructions due to ConstantFoldInstructionDavid Majnemer2016-07-221-1/+2
| | | | | | | | | Just because we can constant fold the result of an instruction does not imply that we can delete the instruction. It may have side effects. This fixes PR28655. llvm-svn: 276389
* [JumpThreading] PRE unordered loadsSanjoy Das2016-07-141-5/+6
| | | | | | | | | | | | Summary: Extend JumpThreading's PRE to unordered atomic loads. Reviewers: hfinkel, reames Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D22326 llvm-svn: 275456
* [JumpThreading] Delete commented out debug code; NFCSanjoy Das2016-07-131-3/+0
| | | | llvm-svn: 275346
* Work around PR28400 a bit harder.Sean Silva2016-07-061-2/+5
| | | | | | | | | | We were still crashing in the "no change" case because LVI was not getting invalidated. See the thread "Should analyses be able to hold AssertingVH to IR? (related to PR28400)" for more discussion. llvm-svn: 274656
* PR28400: Partly undo r274440 to bring test-suite back to life with the new PMSean Silva2016-07-031-1/+2
| | | | | | | | | PR28400 seems to be not an isolated issue, but a general problem related to caching analyses. We will need to discuss on llvm-dev. A test case is in the PR. llvm-svn: 274457
* [PM] Fix a small typo from when I ported JumpThreadingSean Silva2016-07-021-1/+1
| | | | llvm-svn: 274440
* Reinstate r273711David Majnemer2016-06-251-2/+7
| | | | | | | | | | r273711 was reverted by r273743. The inliner needs to know about any call sites in the inlined function. These were obscured if we replaced a call to undef with an undef but kept the call around. This fixes PR28298. llvm-svn: 273753
* Revert r273711, it caused PR28298.Nico Weber2016-06-241-7/+2
| | | | llvm-svn: 273743
* SimplifyInstruction does not imply DCEDavid Majnemer2016-06-241-2/+7
| | | | | | | We cannot remove an instruction with no uses just because SimplifyInstruction succeeds. It may have side effects. llvm-svn: 273711
* Revert r272891 "[JumpThreading] Prevent dangling pointer problems in ↵Igor Laevsky2016-06-161-12/+4
| | | | | | | | BranchProbabilityInfo" It was causing failures in Profile-i386 and Profile-x86_64 tests. llvm-svn: 272912
* [JumpThreading] Prevent dangling pointer problems in BranchProbabilityInfoIgor Laevsky2016-06-161-4/+12
| | | | | | | | | We should update results of the BranchProbabilityInfo after removing block in JumpThreading. Otherwise we will get dangling pointer inside BranchProbabilityInfo cache. Differential Revision: http://reviews.llvm.org/D20957 llvm-svn: 272891
* Bring back "[PM] Port JumpThreading to the new PM" with a fixSean Silva2016-06-141-113/+82
| | | | | | | | | | | This reverts commit r272603 and adds a fix. Big thanks to Davide for pointing me at r216244 which gives some insight into how to fix this VS2013 issue. VS2013 can't synthesize a move constructor. So the fix here is to add one explicitly to the JumpThreadingPass class. llvm-svn: 272607
* Revert "[PM] Port JumpThreading to the new PM"Sean Silva2016-06-141-82/+113
| | | | | | | | This reverts commit r272597. Will investigate issue with VS2013 compilation and then recommit. llvm-svn: 272603
* [PM] Port JumpThreading to the new PMSean Silva2016-06-131-113/+82
| | | | | | | | | | | | This follows the approach in r263208 (for GVN) pretty closely: - move the bulk of the body of the function to the new PM class. - expose a runImpl method on the new-PM class that takes the IRUnitT and pointers/references to any analyses and use that to implement the old-PM class. - use a private namespace in the header for stuff that used to be file scope llvm-svn: 272597
* [PM] Port LVI to the new PM.Sean Silva2016-06-131-4/+4
| | | | | | | | | | | | | | | | | | | This is a bit gnarly since LVI is maintaining its own cache. I think this port could be somewhat cleaner, but I'd rather not spend too much time on it while we still have the old pass hanging around and limiting how much we can clean things up. Once the old pass is gone it will be easier (less time spent) to clean it up anyway. This is the last dependency needed for porting JumpThreading which I'll do in a follow-up commit (there's no printer pass for LVI or anything to test it, so porting a pass that depends on it seems best). I've been mostly following: r269370 / D18834 which ported Dependence Analysis r268601 / D19839 which ported BPI llvm-svn: 272593
* [ValueTracking] Improve isImpliedCondition when the dominating cond is false.Chad Rosier2016-04-251-2/+5
| | | | llvm-svn: 267430
* Re-commit optimization bisect support (r267022) without new pass manager ↵Andrew Kaylor2016-04-221-1/+1
| | | | | | | | | | support. The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the OptBisect handling). Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267231
* Revert "Initial implementation of optimization bisect support."Vedant Kumar2016-04-221-1/+1
| | | | | | | | This reverts commit r267022, due to an ASan failure: http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549 llvm-svn: 267115
* Initial implementation of optimization bisect support.Andrew Kaylor2016-04-211-1/+1
| | | | | | | | | | | | This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations. The bisection is enabled using a new command line option (-opt-bisect-limit). Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit. A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used. The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check. Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute. A new function call has been added for module and SCC passes that behaves in a similar way. Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267022
* [ValueTracking] Make isImpliedCondition return an Optional<bool>. NFC.Chad Rosier2016-04-201-4/+5
| | | | | | Phabricator Revision: http://reviews.llvm.org/D19277 llvm-svn: 266904
* [ValueTracking] Improve isImpliedCondition for conditions with matching ↵Chad Rosier2016-04-191-3/+4
| | | | | | | | | | | | | | | operands. This patch improves SimplifyCFG to catch cases like: if (a < b) { if (a > b) <- known to be false unreachable; } Phabricator Revision: http://reviews.llvm.org/D18905 llvm-svn: 266767
* [SimlifyCFG] Prevent passes from destroying canonical loop structure, ↵Hyojin Sung2016-03-291-1/+4
| | | | | | | | | | | | | | | | | especially for nested loops When eliminating or merging almost empty basic blocks, the existence of non-trivial PHI nodes is currently used to recognize potential loops of which the block is the header and keep the block. However, the current algorithm fails if the loops' exit condition is evaluated only with volatile values hence no PHI nodes in the header. Especially when such a loop is an outer loop of a nested loop, the loop is collapsed into a single loop which prevent later optimizations from being applied (e.g., transforming nested loops into simplified forms and loop vectorization). The patch augments the existing PHI node-based check by adding a pre-test if the BB actually belongs to a set of loop headers and not eliminating it if yes. llvm-svn: 264697
* Revert "[SimlifyCFG] Prevent passes from destroying canonical loop ↵Reid Kleckner2016-03-281-4/+1
| | | | | | | | | | structure, especially for nested loops" This reverts commit r264596. It does not compile. llvm-svn: 264604
* [SimlifyCFG] Prevent passes from destroying canonical loop structure, ↵Hyojin Sung2016-03-281-1/+4
| | | | | | | | | | | | | | | | especially for nested loops When eliminating or merging almost empty basic blocks, the existence of non-trivial PHI nodes is currently used to recognize potential loops of which the block is the header and keep the block. However, the current algorithm fails if the loops' exit condition is evaluated only with volatile values hence no PHI nodes in the header. Especially when such a loop is an outer loop of a nested loop, the loop is collapsed into a single loop which prevent later optimizations from being applied (e.g., transforming nested loops into simplified forms and loop vectorization). The patch augments the existing PHI node-based check by adding a pre-test if the BB actually belongs to a set of loop headers and not eliminating it if yes. llvm-svn: 264596
* [JumpThreading] See through Cast InstructionsHaicheng Wu2016-03-161-0/+19
| | | | | | To capture more jump-thread opportunity. llvm-svn: 263618
* Revert "[JumpThreading] Simplify Instructions first in ↵Haicheng Wu2016-03-151-35/+20
| | | | | | | | ComputeValueKnownInPredecessors()" Not sure it handles undef properly. llvm-svn: 263605
* [JumpThreading] Simplify Instructions first in ComputeValueKnownInPredecessors()Haicheng Wu2016-02-261-20/+35
| | | | | | This change tries to find more opportunities to thread over basic blocks. llvm-svn: 261981
* [JumpThreading] Change a return of ComputeValueKnownInPredecessors()Haicheng Wu2016-02-081-1/+1
| | | | | | | | | Change a return statement of ComputeValueKnownInPredecessors() to be the same as the rest return statements of the function. Otherwise, it might return true with an empty Result when the current basic block has no predecessors and trigger the first assert of JumpThreading::ProcessThreadableEdges(). llvm-svn: 260110
* [opaque pointer types] [NFC] FindAvailableLoadedValue: take LoadInst instead ↵Eduard Burtescu2016-01-221-2/+2
| | | | | | | | | | | | of just the pointer. Reviewers: mjacob, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D16422 llvm-svn: 258477
* [JumpThreading] Don't forget to report that the IR changedDavid Majnemer2016-01-101-2/+3
| | | | | | | | | | | | | | JumpThreading's runOnFunction is supposed to return true if it made any changes. JumpThreading has a call to removeUnreachableBlocks which may result in changes to the IR but runOnFunction didn't appropriate account for this possibility, leading to badness. While we are here, make sure to call LazyValueInfo::eraseBlock in removeUnreachableBlocks; JumpThreading preserves LVI. This fixes PR26096. llvm-svn: 257279
* [JumpThreading] Use range-based for loops.Benjamin Kramer2016-01-091-82/+68
| | | | | | No functionality change intended. llvm-svn: 257262
* [JumpThreading] Split select that has constant conditions coming from the ↵Haicheng Wu2016-01-081-0/+63
| | | | | | | | | | | | | | | | | | | | PHI node Look for PHI/Select in the same BB of the form bb: %p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ... %s = select p, trueval, falseval And expand the select into a branch structure. This later enables jump-threading over bb in this pass. Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold select if the associated PHI has at least one constant. If the unfolded select is not jump-threaded, it will be folded again in the later optimizations. llvm-svn: 257198
* [JumpThreading] Fix opcode bonus in getJumpThreadDuplicationCost()Geoff Berry2015-12-291-10/+16
| | | | | | | | | | | | The code that was meant to adjust the duplication cost based on the terminator opcode was not being executed in cases where the initial threshold was hit inside the loop. Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D15536 llvm-svn: 256568
* [BPI] Fix two potential divide-by-zero operations that are introduced in ↵Cong Hou2015-12-221-7/+12
| | | | | | r256263. llvm-svn: 256303
* [BPI] Replace weights by probabilities in BPI.Cong Hou2015-12-221-10/+18
| | | | | | | | | | | | This patch removes all weight-related interfaces from BPI and replace them by probability versions. With this patch, we won't use edge weight anymore in either IR or MC passes. Edge probabilitiy is a better representation in terms of CFG update and validation. Differential revision: http://reviews.llvm.org/D15519 llvm-svn: 256263
* [ValueTracking] Add parameters to isImpliedCondition; NFCSanjoy Das2015-11-061-1/+3
| | | | | | | | | | | | | | | | Summary: This change makes the `isImpliedCondition` interface similar to the rest of the functions in ValueTracking (in that it takes a DataLayout, AssumptionCache etc.). This is an NFC, intended to make a later diff less noisy. Depends on D14369 Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14391 llvm-svn: 252333
* [JumpThreading] Use dominating conditions to prove implicationsSanjoy Das2015-10-281-2/+40
| | | | | | | | | | | | | | | Summary: If P branches to Q conditional on C and Q branches to R conditional on C' and C => C' then the branch conditional on C' can be folded to an unconditional branch. Reviewers: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13972 llvm-svn: 251557
* Recommit r250345, it was reverted in r250366 to investigate a bot failure.Manman Ren2015-10-151-5/+116
| | | | | | Our internal bot is still red after r250366. llvm-svn: 250415
* Temporarily revert r250345 to sort out bot failure.Manman Ren2015-10-151-116/+5
| | | | | | | | | | | | | | With r250345 and r250343, we start to observe the following failure when bootstrap clang with lto and pgo: PHI node entries do not match predecessors! %.sroa.029.3.i = phi %"class.llvm::SDNode.13298"* [ null, %30953 ], [ null, %31017 ], [ null, %30998 ], [ null, %_ZN4llvm8dyn_castINS_14ConstantSDNodeENS_7SDValueEEENS_10cast_rettyIT_T0_E8ret_typeERS5_.exit.i.1804 ], [ null, %30975 ], [ null, %30991 ], [ null, %_ZNK4llvm3EVT13getScalarTypeEv.exit.i.1812 ], [ %..sroa.029.0.i, %_ZN4llvm11SmallVectorIiLj8EED1Ev.exit.i.1826 ], !dbg !451895 label %30998 label %_ZNK4llvm3EVTeqES0_.exit19.thread.i LLVM ERROR: Broken function found, compilation aborted! I will re-commit this if the bot does not recover. llvm-svn: 250366
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-141-5/+116
| | | | | | | | | | Currently in JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB). This is the third attempt to submit this patch, while the first two led to failures in some FDO tests. After investigation, it is the edge weight normalization that caused those failures. In this patch the edge weight normalization is fixed so that there is no zero weight in the output and the sum of all weights can fit in 32-bit integer. Several unit tests are added. Differential revision: http://reviews.llvm.org/D10979 llvm-svn: 250345
* Revert r250204 and r250240 due to bot failure. We failed to build PGO-ed clang.Manman Ren2015-10-141-118/+5
| | | | llvm-svn: 250264
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-131-5/+118
| | | | | | | | Currently in JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB). Differential revision: http://reviews.llvm.org/D10979 llvm-svn: 250204
* Scalar: Remove some implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-10-131-12/+12
| | | | | | | Remove some of the implicit ilist iterator conversions in LLVMScalarOpts. More to go. llvm-svn: 250197
* Revert 250089 due to bot failure. It failed when building clang itself with PGO.Manman Ren2015-10-131-118/+5
| | | | llvm-svn: 250145
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-121-5/+118
| | | | | | | | In JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB). Differential revision: http://reviews.llvm.org/D10979 llvm-svn: 250089
* Clean up: Refactoring the hardcoded value of 6 for ↵Larisse Voufo2015-09-181-3/+4
| | | | | | FindAvailableLoadedValue()'s parameter MaxInstsToScan. (Complete version of r247497. See D12886) llvm-svn: 248022
* Test commit: Fixed a few typos in the comments.David L Kreitzer2015-09-161-6/+6
| | | | llvm-svn: 247793
OpenPOWER on IntegriCloud