summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
...
* [SCCP] Use the `hasAddressTaken()` version defined in `Function`.Davide Italiano2017-05-231-1/+2
| | | | | | | | | | Instead of using the SCCP homegrown one. We should eventually make the private SCCP version disappear, but that wont' be today. PR33143 tracks this issue. Add braces for consistency while here. No functional change intended. llvm-svn: 303706
* [LIR] Use the newly `getRecurrenceVar()` helper. NFCI.Davide Italiano2017-05-231-4/+4
| | | | llvm-svn: 303704
* [LIR] Strengthen the check for recurrence variable in popcnt/CTLZ.Davide Italiano2017-05-231-9/+16
| | | | | | | Fixes PR33114. Differential Revision: https://reviews.llvm.org/D33420 llvm-svn: 303700
* [JumpThreading] Safely replace uses of conditionAnna Thomas2017-05-231-2/+40
| | | | | | | | | | | | | | | | | | | | | | This patch builds over https://reviews.llvm.org/rL303349 and replaces the use of the condition only if it is safe to do so. We should not blindly RAUW the condition if experimental.guard or assume is a use of that condition. This is because LVI may have used the guard/assume to identify the value of the condition, and RUAWing will fold the guard/assume and uses before the guards/assumes. Reviewers: sanjoy, reames, trentxintong, mkazantsev Reviewed by: sanjoy, reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33257 llvm-svn: 303633
* [LoopPredication] NFC. Add extra debug output in case we fail to parse the ↵Artur Pilipenko2017-05-221-1/+3
| | | | | | range check llvm-svn: 303544
* [LoopPredication] NFC. Move a nested struct declaration before the fields, ↵Artur Pilipenko2017-05-221-7/+9
| | | | | | | | clang-format a bit This will simplify the diff for an upcoming review. llvm-svn: 303543
* NewGVN: Fix PR 33116, the memoryphi version of bug 32838.Daniel Berlin2017-05-211-6/+5
| | | | llvm-svn: 303521
* NewGVN: Cleanup some repeated code using some templated helpersDaniel Berlin2017-05-211-40/+40
| | | | llvm-svn: 303520
* NewGVN: Fix printing of simplified expressionDaniel Berlin2017-05-211-1/+1
| | | | llvm-svn: 303519
* [NewGVN] Create a StoreExpression instead of a VariableExpression.Davide Italiano2017-05-201-1/+1
| | | | | | | | | | | | | In the case where we have an operand defined by a lod of the same memory location. Historically this was a VariableExpression because we wanted to make sure they ended up in the same class, but if we create the right expression, they end up in the same class anyway. Fixes PR32897. Thanks to Dan for the detailed discussion and the fix suggestion. llvm-svn: 303475
* [NewGVN] Get rid of an assertion.Davide Italiano2017-05-201-1/+0
| | | | | | | | | | This was here because we don't want to switch leaders too much, in order to avoid fixpoint(ing) issue, but it's not sure if it matters in practice. A first step towards fixing PR32897. llvm-svn: 303473
* NewGVN: Fix PR32838.Daniel Berlin2017-05-191-22/+53
| | | | | | | | | | This is a complicated bug involving two issues: 1. What do we do with phi nodes when we prove all arguments are not live? 2. When is it safe to use value leaders to determine if we can ignore an argumnet? llvm-svn: 303453
* Last of the major pieces to NewGVN - yay!Daniel Berlin2017-05-191-117/+525
| | | | | | | | | | | | | | | | | | | | | | Summary: NewGVN: Handle equivalence between phi of ops and op of phis. This makes our GVN mostly-complete. It would be complete, modulo some deliberate choices we make. This means it detects roughly all herband equivalences in polynomial time, including cases notoriously hard for other GVN's to detect. It also detects a very large swath of the cases we currently rely on instcombine to detect that involve folding upwards through phis. Fixes PR 31125, 31463, PR 31868 Reviewers: davide Subscribers: Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D32151 llvm-svn: 303444
* NewGVN: Get rid of most dominating leader checkDaniel Berlin2017-05-191-24/+2
| | | | llvm-svn: 303443
* [NFC][loopIdiom] Clang format change rL303434Anna Thomas2017-05-191-3/+5
| | | | llvm-svn: 303439
* [LoopIdiom] Refactor return value of isLegalStore [NFC]Anna Thomas2017-05-191-31/+38
| | | | | | | | | | | | | | | | | | | | | | | Summary: This NFC simply refactors the return value of LoopIdiomRecognize::isLegalStore() from bool to an enumeration, and removes the return-through-parameter mechanism that the function was using. This function is constructed such that it will only ever recognize a single store idiom (memset, memset_pattern, or memcpy), and never a combination of these. As such it makes much more sense for the return value to be the single idiom that the store matches, rather than having a separate argument-return for each idiom -- it's cleaner, and makes it clearer that only a single idiom can be matched. Patch by Daniel Neilson! Reviewers: anna, sanjoy, davide, haicheng Reviewed By: anna, haicheng Subscribers: haicheng, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D33359 llvm-svn: 303434
* [LoopPredication] NFC. Extract LoopICmp struct and parseLoopICmp helperArtur Pilipenko2017-05-191-18/+44
| | | | llvm-svn: 303427
* [LoopPredication] NFC. Extract LoopPredication::expandCheck helperArtur Pilipenko2017-05-191-5/+16
| | | | llvm-svn: 303426
* [LoopPredication] NFC. Extract CanExpand helper lambdaArtur Pilipenko2017-05-191-2/+6
| | | | llvm-svn: 303425
* [LoopPredication] NFC. Add an early exit if there is no guards in the loopArtur Pilipenko2017-05-191-0/+3
| | | | llvm-svn: 303424
* [NewGVN] Delete the old store when we find congruent to a load.Davide Italiano2017-05-191-2/+2
| | | | | | | (or non-store, more in general). Fixes PR33086. Caught by the store verifier. llvm-svn: 303406
* [NewGVN] Break infinite recursion in singleReachablePHIPath().Davide Italiano2017-05-181-6/+20
| | | | | | | | | | | | We can have cycles between PHIs and this causes singleReachablePhi() to call itself indefintely (until we run out of stack). The proper solution would be that of computing SCCs, but it's not worth for now, so just keep a visited set and give up when we find a cycle. Thanks to Dan for the discussion/help with this. Fixes PR33014. llvm-svn: 303393
* [NewGVN] Replace predicate info leftovers.Davide Italiano2017-05-181-0/+6
| | | | | | | This time with an additional fix, i.e. we remove the dead @llvm.ssa.copy instruction. llvm-svn: 303385
* [IR] De-virtualize ~Value to save a vptrReid Kleckner2017-05-186-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Implements PR889 Removing the virtual table pointer from Value saves 1% of RSS when doing LTO of llc on Linux. The impact on time was positive, but too noisy to conclusively say that performance improved. Here is a link to the spreadsheet with the original data: https://docs.google.com/spreadsheets/d/1F4FHir0qYnV0MEp2sYYp_BuvnJgWlWPhWOwZ6LbW7W4/edit?usp=sharing This change makes it invalid to directly delete a Value, User, or Instruction pointer. Instead, such code can be rewritten to a null check and a call Value::deleteValue(). Value objects tend to have their lifetimes managed through iplist, so for the most part, this isn't a big deal. However, there are some places where LLVM deletes values, and those places had to be migrated to deleteValue. I have also created llvm::unique_value, which has a custom deleter, so it can be used in place of std::unique_ptr<Value>. I had to add the "DerivedUser" Deleter escape hatch for MemorySSA, which derives from User outside of lib/IR. Code in IR cannot include MemorySSA headers or call the MemoryAccess object destructors without introducing a circular dependency, so we need some level of indirection. Unfortunately, no class derived from User may have any virtual methods, because adding a virtual method would break User::getHungOffOperands(), which assumes that it can find the use list immediately prior to the User object. I've added a static_assert to the appropriate OperandTraits templates to help people avoid this trap. Reviewers: chandlerc, mehdi_amini, pete, dberlin, george.burgess.iv Reviewed By: chandlerc Subscribers: krytarowski, eraman, george.burgess.iv, mzolotukhin, Prazek, nlewycky, hans, inglorion, pcc, tejohnson, dberlin, llvm-commits Differential Revision: https://reviews.llvm.org/D31261 llvm-svn: 303362
* [LSR] Call canonicalize after we generate a new Formula in ↵Wei Mi2017-05-181-0/+1
| | | | | | | | | | | | | | GenerateTruncates. Fix PR33077. The testcase in PR33077 generates a LSR Use Formula with two SCEVAddRecExprs for the same loop. Such uncommon formula will become non-canonical after GenerateTruncates adds sign extension to the ScaledReg of the Formula, and it will break the assertion that every Formula to be inserted is canonical. The fix is to call canonicalize for the raw Formula generated by GenerateTruncates before inserting it. llvm-svn: 303361
* [JumpThreading] Dont RAUW condition incorrectlyAnna Thomas2017-05-181-17/+14
| | | | | | | | | | | | | | | | | | | Summary: We have a bug when RAUWing the condition if experimental.guard or assumes is a use of that condition. This is because LazyValueInfo may have used the guards/assumes to identify the value of the condition at the end of the block. RAUW replaces the uses at the guard/assume as well as uses before the guard/assume. Both of these are incorrect. For now, disable RAUW for conditions and fix the logic as a next step: https://reviews.llvm.org/D33257 Reviewers: sanjoy, reames, trentxintong Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33279 llvm-svn: 303349
* [Statistics] Add a method to atomically update a statistic that contains a ↵Craig Topper2017-05-181-4/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | maximum Summary: There are several places in the codebase that try to calculate a maximum value in a Statistic object. We currently do this in one of two ways: MaxNumFoo = std::max(MaxNumFoo, NumFoo); or MaxNumFoo = (MaxNumFoo > NumFoo) ? MaxNumFoo : NumFoo; The first version reads from MaxNumFoo one time and uncontionally rwrites to it. The second version possibly reads it twice depending on the result of the first compare. But we have no way of knowing if the value was changed by another thread between the reads and the writes. This patch adds a method to the Statistic object that can ensure that we only store if our value is the max and the previous max didn't change after we read it. If it changed we'll recheck if our value should still be the max or not and try again. This spawned from an audit I'm trying to do of all places we uses the implicit conversion to unsigned on the Statistics objects. See my previous thread on llvm-dev https://groups.google.com/forum/#!topic/llvm-dev/yfvxiorKrDQ Reviewers: dberlin, chandlerc, hfinkel, dblaikie Reviewed By: chandlerc Subscribers: llvm-commits, sanjoy Differential Revision: https://reviews.llvm.org/D33301 llvm-svn: 303318
* [Statistics] Use Statistic::operator+= instead of adding and assigning ↵Craig Topper2017-05-172-2/+2
| | | | | | | | separately. I believe this technically fixes a multithreaded race condition in this code. But my primary concern was as part of looking at removing the ability to treat Statistics like a plain unsigned. There are many weird operations on Statistics in the codebase. llvm-svn: 303314
* BitVector: add iterators for set bitsFrancis Visoiu Mistrih2017-05-172-4/+2
| | | | | | Differential revision: https://reviews.llvm.org/D32060 llvm-svn: 303227
* [ADT] Fix some Clang-tidy modernize-use-using warnings; other minor fixes (NFC).Eugene Zelenko2017-05-161-9/+28
| | | | llvm-svn: 303221
* [IR] Prefer use_empty() to !hasNUsesOrMore(1) for clarity.Davide Italiano2017-05-162-2/+2
| | | | llvm-svn: 303218
* The patch exclude a case from zero check skip inEvgeny Stupachenko2017-05-161-7/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | CTLZ idiom recognition (r303102). Summary: The following case: i = 1; if(n) while (n >>= 1) i++; use(i); Was converted to: i = 1; if(n) i += builtin_ctlz(n >> 1, false); use(i); Which is not correct. The patch make it: i = 1; if(n) i += builtin_ctlz(n >> 1, true); use(i); From: Evgeny Stupachenko <evstupac@gmail.com> llvm-svn: 303212
* NewGVN: Only do something in verifyStoreExpressions if assertions are ↵Daniel Berlin2017-05-161-0/+2
| | | | | | enabled, to avoid unused code warnings. llvm-svn: 303201
* NewGVN: Fix PR 33051 by making sure we remove old store expressionsDaniel Berlin2017-05-161-27/+36
| | | | | | from the ExpressionToClass mapping. llvm-svn: 303200
* [CorrelatedValuePropagation] Don't use -> to call a static method of ↵Craig Topper2017-05-161-6/+4
| | | | | | ConstantRange. NFC llvm-svn: 303147
* NewGVN: Use StoreExpression StoredValue instead of looking it up again, ↵Daniel Berlin2017-05-161-6/+5
| | | | | | since it was already looked up when it was created llvm-svn: 303144
* NewGVN: Formatting fixesDaniel Berlin2017-05-161-2/+3
| | | | llvm-svn: 303143
* Revert "[NewGVN] Replace predicate info leftovers."Davide Italiano2017-05-161-4/+0
| | | | | | It's breaking the bots. llvm-svn: 303142
* [NewGVN] Replace predicate info leftovers.Davide Italiano2017-05-161-0/+4
| | | | | | | | Fixes PR32945. Differential Revision: https://reviews.llvm.org/D33226 llvm-svn: 303141
* [NewGVN] Remove unused setDefiningExpr(). NFCI.Davide Italiano2017-05-151-1/+0
| | | | llvm-svn: 303107
* The patch adds CTLZ idiom recognition.Evgeny Stupachenko2017-05-151-1/+294
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The following loops should be recognized: i = 0; while (n) { n = n >> 1; i++; body(); } use(i); And replaced with builtin_ctlz(n) if body() is empty or for CPUs that have CTLZ instruction converted to countable: for (j = 0; j < builtin_ctlz(n); j++) { n = n >> 1; i++; body(); } use(builtin_ctlz(n)); Reviewers: rengolin, joerg Differential Revision: http://reviews.llvm.org/D32605 From: Evgeny Stupachenko <evstupac@gmail.com> llvm-svn: 303102
* [NewGVN] Fix verification of MemoryPhis in verifyMemoryCongruency().Davide Italiano2017-05-151-0/+13
| | | | | | | | | | | | verifyMemoryCongruency() filters out trivially dead MemoryDef(s), as we find them immediately dead, before moving from TOP to a new congruence class. This fixes the same problem for PHI(s) skipping MemoryPhis if all the operands are dead. Differential Revision: https://reviews.llvm.org/D33044 llvm-svn: 303100
* [NewGVN] Improve debug output a bit. NFCI.Davide Italiano2017-05-121-1/+1
| | | | | | | While debugging a predicate info problem, I noticed this was missing a newline, making the debug output slightly less readable. llvm-svn: 302908
* [NewGVN] Format an assertion and fix a typo. NFCI.Davide Italiano2017-05-121-3/+2
| | | | llvm-svn: 302906
* [NewGVN] Don't incorrectly reset the memory leader.Davide Italiano2017-05-121-1/+1
| | | | | | | | | | This code was missing a check for stores, so we were thinking the congruency class didn't have any memory members, and reset the memory leader. Differential Revision: https://reviews.llvm.org/D33056 llvm-svn: 302905
* [PM/Unswitch] Teach the new simple loop unswitch to handle loopChandler Carruth2017-05-121-23/+138
| | | | | | | | | | | | | | | | | | | | | | | | invariant PHI inputs and to rewrite PHI nodes during the actual unswitching. The checking is quite easy, but rewriting the PHI nodes is somewhat surprisingly challenging. This should handle both branches and switches. I think this is now a full featured trivial unswitcher, and more full featured than the trivial cases in the old pass while still being (IMO) somewhat simpler in how it works. Next up is to verify its correctness in more widespread testing, and then to add non-trivial unswitching. Thanks to Davide and Sanjoy for the excellent review. There is one remaining question that I may address in a follow-up patch (see the review thread for details) but it isn't related to the functionality specifically. Differential Revision: https://reviews.llvm.org/D32699 llvm-svn: 302867
* [NewGVN] Introduce a definesNoMemory() helper and use it.Davide Italiano2017-05-101-3/+5
| | | | | | | This is nice as is, but it will be used in my next patch to fix a bug. Suggested by Daniel Berlin. llvm-svn: 302714
* Revert r301950: SpeculativeExecution: Stop using whitelist for costsChandler Carruth2017-05-101-1/+42
| | | | | | | | | | This pass doesn't correctly handle testing for when it is legal to hoist arbitrary instructions. The whitelist happens to make it safe, so before it is removed the pass's legality checks will need to be enhanced. Details have been added to the code review thread for the patch. llvm-svn: 302640
* [NewGVN] Simplify a DEBUG() statement. NFCI.Davide Italiano2017-05-091-2/+1
| | | | llvm-svn: 302579
* [NewGVN] Explain why sorting by pointer values doesn't introduce ↵Davide Italiano2017-05-091-0/+4
| | | | | | | | non-determinism. Thanks to Eli for pointing out in a post-commit review comment. llvm-svn: 302566
OpenPOWER on IntegriCloud