summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [IRCE] Fix how IRCE checks for no-sign-overflow.Sanjoy Das2015-03-241-14/+24
| | | | | | | | | IRCE requires the induction variables it handles to not sign-overflow. The current scheme of checking if sext({X,+,S}) == {sext(X),+,sext(S)} fails when SCEV simplifies sext(X) too. After this change we //also// check no-signed-wrap by looking at the flags set on the SCEVAddRecExpr. llvm-svn: 233102
* [IRCE] Fix a regression introduced in r232444.Sanjoy Das2015-03-241-9/+20
| | | | | | | IRCE should not try to eliminate range checks that check an induction variable against a loop-varying length. llvm-svn: 233101
* Re-sort includes with sort-includes.py and insert raw_ostream.h where it's used.Benjamin Kramer2015-03-231-8/+3
| | | | llvm-svn: 232998
* Fix GCC -Wparentheses warning (& reformat now that the precedence is fixed)David Blaikie2015-03-171-2/+2
| | | | | | | Benign warning (clang deliberately suppresses this case) but does regularly produce bad formatting, so it's nice to fix/reformat. llvm-svn: 232508
* Use an underlying enum type of unsigned to silence a -Wmicrosoft warning ↵Reid Kleckner2015-03-171-1/+1
| | | | | | about being unable to put (unsigned)-1 into the default underyling type of int llvm-svn: 232498
* [IRCE] Add a -irce-print-range-checks option.Sanjoy Das2015-03-171-6/+15
| | | | | | | -irce-print-range-checks prints out the set of range checks recognized by IRCE. llvm-svn: 232451
* [IRCE] Add comments, NFC.Sanjoy Das2015-03-171-4/+27
| | | | | | | This change adds some comments that justify why a potentially overflowing operation is safe. llvm-svn: 232445
* [IRCE] Support half-range checks.Sanjoy Das2015-03-171-128/+152
| | | | | | | | | | | | This change to IRCE gets it to recognize "half" range checks. Half range checks are range checks that only either check if the index is `slt` some positive integer ("length") or if the index is `sge` `0`. The range solver does not try to be clever / aggressive about solving half-range checks -- it transforms "I < L" to "0 <= I < L" and "0 <= I" to "0 <= I < INT_SMAX". This is safe, but not always optimal. llvm-svn: 232444
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-4/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* IRCE: only touch loops that have been shown to have a highSanjoy Das2015-02-261-4/+17
| | | | | | backedge-taken count in profiliing data. llvm-svn: 230619
* IRCE: generalize to handle loops with decreasing induction variables.Sanjoy Das2015-02-261-207/+358
| | | | | | | | | IRCE can now split the iteration space for loops like: for (i = n; i >= 0; i--) a[i + k] = 42; // bounds check on access llvm-svn: 230618
* IRCE: print newline after printing an InductiveRangeCheck.Sanjoy Das2015-02-261-0/+1
| | | | llvm-svn: 230607
* IRCE: generalize InductiveRangeCheck::computeSafeIterationSpace toSanjoy Das2015-02-211-32/+57
| | | | | | | | | | work with a non-canonical induction variable. This is currently a non-functional change because we only ever call computeSafeIterationSpace on a canonical induction variable; but the generalization will be useful in a later commit. llvm-svn: 230151
* IRCE: use SCEVs instead of llvm::Value's for intermediateSanjoy Das2015-02-211-46/+30
| | | | | | | | | calculations. Semantically non-functional change. This gets rid of some of the SCEV -> Value -> SCEV round tripping and the Construct(SMin|SMax)Of and MaybeSimplify helper routines. llvm-svn: 230150
* Make helper functions/classes/globals static. NFC.Benjamin Kramer2015-02-061-4/+4
| | | | llvm-svn: 228410
* IRCE: Demote template to ArrayRef and SmallVector to array.Benjamin Kramer2015-02-061-26/+15
| | | | | | NFC. llvm-svn: 228398
* Teach IRCE to look at branch weights when recognizing range checksSanjoy Das2015-01-271-3/+14
| | | | | | | | | | | Splitting a loop to make range checks redundant is profitable only if the range check "never" fails. Make this fact a part of recognizing a range check -- a branch is a range check only if it is expected to pass (via branch_weights metadata). Differential Revision: http://reviews.llvm.org/D7192 llvm-svn: 227249
* [NFC] Introduce a 'struct Range' for IRCESanjoy Das2015-01-221-17/+27
| | | | | | | | | Use the struct instead of a std::pair<Value *, Value *>. This makes a Range an obviously immutable object, and we can now assert that a range is well-typed (Begin->getType() == End->getType()) on its construction. llvm-svn: 226804
* Fix crashes in IRCE caused by mismatched typesSanjoy Das2015-01-221-7/+35
| | | | | | | | | | | | | | | There are places where the inductive range check elimination pass depends on two llvm::Values or llvm::SCEVs to be of the same llvm::Type when they do not need to be. This patch relaxes those restrictions (by bailing out of the optimization if the types mismatch), and adds test cases to trigger those paths. These issues were found by bootstrapping clang with IRCE running in the -O3 pass ordering. Differential Revision: http://reviews.llvm.org/D7082 llvm-svn: 226793
* [PM] Now that LoopInfo isn't in the Pass type hierarchy, it is muchChandler Carruth2015-01-181-2/+1
| | | | | | | | | | | | cleaner to derive from the generic base. Thise removes a ton of boiler plate code and somewhat strange and pointless indirections. It also remove a bunch of the previously needed friend declarations. To fully remove these, I also lifted the verify logic into the generic LoopInfoBase, which seems good anyways -- it is generic and useful logic even for the machine side. llvm-svn: 226385
* [PM] Split the LoopInfo object apart from the legacy pass, creatingChandler Carruth2015-01-171-2/+3
| | | | | | | | | | a LoopInfoWrapperPass to wire the object up to the legacy pass manager. This switches all the clients of LoopInfo over and paves the way to port LoopInfo to the new pass manager. No functionality change is intended with this iteration. llvm-svn: 226373
* Add a new pass "inductive range check elimination"Sanjoy Das2015-01-161-0/+1210
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | IRCE eliminates range checks of the form 0 <= A * I + B < Length by splitting a loop's iteration space into three segments in a way that the check is completely redundant in the middle segment. As an example, IRCE will convert len = < known positive > for (i = 0; i < n; i++) { if (0 <= i && i < len) { do_something(); } else { throw_out_of_bounds(); } } to len = < known positive > limit = smin(n, len) // no first segment for (i = 0; i < limit; i++) { if (0 <= i && i < len) { // this check is fully redundant do_something(); } else { throw_out_of_bounds(); } } for (i = limit; i < n; i++) { if (0 <= i && i < len) { do_something(); } else { throw_out_of_bounds(); } } IRCE can deal with multiple range checks in the same loop (it takes the intersection of the ranges that will make each of them redundant individually). Currently IRCE does not do any profitability analysis. That is a TODO. Please note that the status of this pass is *experimental*, and it is not part of any default pass pipeline. Having said that, I will love to get feedback and general input from people interested in trying this out. This pass was originally r226201. It was reverted because it used C++ features not supported by MSVC 2012. Differential Revision: http://reviews.llvm.org/D6693 llvm-svn: 226238
* Revert r226201 (Add a new pass "inductive range check elimination")Sanjoy Das2015-01-151-1189/+0
| | | | | | | The change used C++11 features not supported by MSVC 2012. I will fix the change to use things supported MSVC 2012 and recommit shortly. llvm-svn: 226216
* InductiveRangeCheckElimination: Remove extra ';'David Majnemer2015-01-151-3/+3
| | | | | | This silences a GCC warning. llvm-svn: 226215
* Add a new pass "inductive range check elimination"Sanjoy Das2015-01-151-0/+1189
IRCE eliminates range checks of the form 0 <= A * I + B < Length by splitting a loop's iteration space into three segments in a way that the check is completely redundant in the middle segment. As an example, IRCE will convert len = < known positive > for (i = 0; i < n; i++) { if (0 <= i && i < len) { do_something(); } else { throw_out_of_bounds(); } } to len = < known positive > limit = smin(n, len) // no first segment for (i = 0; i < limit; i++) { if (0 <= i && i < len) { // this check is fully redundant do_something(); } else { throw_out_of_bounds(); } } for (i = limit; i < n; i++) { if (0 <= i && i < len) { do_something(); } else { throw_out_of_bounds(); } } IRCE can deal with multiple range checks in the same loop (it takes the intersection of the ranges that will make each of them redundant individually). Currently IRCE does not do any profitability analysis. That is a TODO. Please note that the status of this pass is *experimental*, and it is not part of any default pass pipeline. Having said that, I will love to get feedback and general input from people interested in trying this out. Differential Revision: http://reviews.llvm.org/D6693 llvm-svn: 226201
OpenPOWER on IntegriCloud