summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/JumpThreading.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* Revert "Clean up: Refactoring the hardcoded value of 6 for ↵Larisse Voufo2015-09-151-4/+3
| | | | | | FindAvailableLoadedValue()'s parameter MaxInstsToScan." for preliminary community discussion (See. D12886) llvm-svn: 247716
* Clean up: Refactoring the hardcoded value of 6 for ↵Larisse Voufo2015-09-121-3/+4
| | | | | | FindAvailableLoadedValue()'s parameter MaxInstsToScan. llvm-svn: 247497
* Add GlobalsAA as preserved to a bunch of transformsJames Molloy2015-09-101-0/+2
| | | | | | GlobalsAA must by definition be preserved in function passes, but the passmanager doesn't know that. Make each pass explicitly preserve GlobalsAA. llvm-svn: 247263
* [JumpThreading] make jump threading respect convergent annotation.Jingyue Wu2015-08-311-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: JumpThreading shouldn't duplicate a convergent call, because that would move a convergent call into a control-inequivalent location. For example, if (cond) { ... } else { ... } convergent_call(); if (cond) { ... } else { ... } should not be optimized to if (cond) { ... convergent_call(); ... } else { ... convergent_call(); ... } Test Plan: test/Transforms/JumpThreading/basic.ll Patch by Xuetian Weng. Reviewers: resistor, arsenm, jingyue Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12484 llvm-svn: 246415
* [IR] Add token typesDavid Majnemer2015-08-141-0/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This introduces the basic functionality to support "token types". The motivation stems from the need to perform operations on a Value whose provenance cannot be obscured. There are several applications for such a type but my immediate motivation stems from WinEH. Our personality routine enforces a single-entry - single-exit regime for cleanups. After several rounds of optimizations, we may be left with a terminator whose "cleanup-entry block" is not entirely clear because control flow has merged two cleanups together. We have experimented with using labels as operands inside of instructions which are not terminators to indicate where we came from but found that LLVM does not expect such exotic uses of BasicBlocks. Instead, we can use this new type to clearly associate the "entry point" and "exit point" of our cleanup. This is done by having the cleanuppad yield a Token and consuming it at the cleanupret. The token type makes it impossible to obscure or otherwise hide the Value, making it trivial to track the relationship between the two points. What is the burden to the optimizer? Well, it turns out we have already paid down this cost by accepting that there are certain calls that we are not permitted to duplicate, optimizations have to watch out for such instructions anyway. There are additional places in the optimizer that we will probably have to update but early examination has given me the impression that this will not be heroic. Differential Revision: http://reviews.llvm.org/D11861 llvm-svn: 245029
* Drive-by fixes for LandingPad -> EHPadDavid Majnemer2015-08-041-3/+3
| | | | | | | | This change was done as an audit and is by inspection. The new EH system is still very much a work in progress. NFC for the landingpad case. llvm-svn: 243965
* New EH representation for MSVC compatibilityDavid Majnemer2015-07-311-1/+2
| | | | | | | | | | This introduces new instructions neccessary to implement MSVC-compatible exception handling support. Most of the middle-end and none of the back-end haven't been audited or updated to take them into account. Differential Revision: http://reviews.llvm.org/D11097 llvm-svn: 243766
* Revert the new EH instructionsDavid Majnemer2015-07-101-2/+1
| | | | | | This reverts commits r241888-r241891, I didn't mean to commit them. llvm-svn: 241893
* New EH representation for MSVC compatibilityDavid Majnemer2015-07-101-1/+2
| | | | | | | | | | | | | | | Summary: This introduces new instructions neccessary to implement MSVC-compatible exception handling support. Most of the middle-end and none of the back-end haven't been audited or updated to take them into account. Reviewers: rnk, JosephTremoulet, reames, nlewycky, rjmccall Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11041 llvm-svn: 241888
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-1/+1
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* Fix "the the" in comments.Eric Christopher2015-06-191-1/+1
| | | | llvm-svn: 240112
* Move logic from JumpThreading into LazyValue info to simplify caller. Philip Reames2015-06-161-51/+17
| | | | | | | | This change is hopefully NFC. The only tricky part is that I changed the context instruction being used to the branch rather than the comparison. I believe both to be correct, but the branch is strictly more powerful. With the moved code, using the branch instruction is required for the basic block comparison test to return the same result. The previous code was able to directly access both the branch and the comparison where the revised code is not. Differential Revision: http://reviews.llvm.org/D9652 llvm-svn: 239797
* [JumpThreading] Simplify comparisons when simplifying branchesPhilip Reames2015-05-071-0/+11
| | | | | | | | | | If we have recognized that a conditional is constant at a particular location in the code (while trying to decide if we can simplify a conditional branch), we can eagerly replace that condition with a constant if it's definition is post dominated by the branch in question. In practice, this ends up being a compile time savings at most. JumpThreading would have visited each using branch anyways. CVP would have visited the cmp itself again. Unless LVI gives up early, we shouldn't gain any addition power by doing this transformation early. What we do gain is simplicity and compile time. Differential Revision: http://reviews.llvm.org/D9312 llvm-svn: 236684
* Re-sort includes with sort-includes.py and insert raw_ostream.h where it's used.Benjamin Kramer2015-03-231-1/+1
| | | | llvm-svn: 232998
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Now that the DataLayout is a mandatory part of the module, let's start cleaning the codebase. This patch is a first attempt at doing that. This patch is not exactly NFC as for instance some places were passing a nullptr instead of the DataLayout, possibly just because there was a default value on the DataLayout argument to many functions in the API. Even though it is not purely NFC, there is no change in the validation. I turned as many pointer to DataLayout to references, this helped figuring out all the places where a nullptr could come up. I had initially a local version of this patch broken into over 30 independant, commits but some later commit were cleaning the API and touching part of the code modified in the previous commits, so it seemed cleaner without the intermediate state. Test Plan: Reviewers: echristo Subscribers: llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231740
* Make DataLayout Non-Optional in the ModuleMehdi Amini2015-03-041-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: DataLayout keeps the string used for its creation. As a side effect it is no longer needed in the Module. This is "almost" NFC, the string is no longer canonicalized, you can't rely on two "equals" DataLayout having the same string returned by getStringRepresentation(). Get rid of DataLayoutPass: the DataLayout is in the Module The DataLayout is "per-module", let's enforce this by not duplicating it more than necessary. One more step toward non-optionality of the DataLayout in the module. Make DataLayout Non-Optional in the Module Module->getDataLayout() will never returns nullptr anymore. Reviewers: echristo Subscribers: resistor, llvm-commits, jholewinski Differential Revision: http://reviews.llvm.org/D7992 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231270
* [PM] Replace the Pass argument to SplitEdge with specific analyses usedChandler Carruth2015-01-191-1/+1
| | | | | | | | | | | | | | | and updated. This may appear to remove handling for things like alias analysis when splitting critical edges here, but in fact no callers of SplitEdge relied on this. Similarly, all of them wanted to preserve LCSSA if there was any update of the loop info. That makes the interface much simpler. With this, all of BasicBlockUtils.h is free of Pass arguments and prepared for the new pass manager. This is tho majority of utilities that relied on pass arguments. llvm-svn: 226459
OpenPOWER on IntegriCloud