summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/NewGVN.cpp
Commit message (Collapse)AuthorAgeFilesLines
* NewGVN: Remove useless test in addPhiOfOps.Daniel Berlin2017-06-291-2/+1
| | | | llvm-svn: 306702
* [NewGVN] Fix a bug that made the store verifier less effective.Davide Italiano2017-06-201-6/+4
| | | | | | | | | We weren't actually checking for duplicated stores, as the condition was always actually false. This was found by Coverity, and I have no clue how to trigger this in real-world code (although I tried for a bit). llvm-svn: 305867
* [NewGVN] Simplify findConditionEquivalence(). NFCI.Davide Italiano2017-06-191-3/+1
| | | | llvm-svn: 305707
* NewGVN: Fix PR 33461, caused by slightly overzealous verification.Daniel Berlin2017-06-191-18/+30
| | | | llvm-svn: 305657
* NewGVN: This is wrong by inspection, it will not cause an issue currently ↵Daniel Berlin2017-06-141-1/+1
| | | | | | due to other limitations, i believe. This also means i can't make a test for it. llvm-svn: 305415
* Fix signed/unsigned comparison warning; NFCGeorge Burgess IV2017-06-131-1/+1
| | | | llvm-svn: 305262
* NewGVN: Fix PR/33187. This is a bug caused by two things:Daniel Berlin2017-06-061-32/+48
| | | | | | | | | | | | | 1. When there is no perfect iteration order, we can't let phi nodes put themselves in terms of things that come later in the iteration order, or we will endlessly cycle (the normal RPO algorithm clears the hashtable to avoid this issue). 2. We are sometimes erasing the wrong expression (causing pessimism) because our equality says loads and stores are the same. We introduce an exact equality function and use it when erasing to make sure we erase only identical expressions, not equivalent ones. llvm-svn: 304807
* NewGVN: Fix PR 33185 by checking whether we need to recursivelyDaniel Berlin2017-05-311-23/+15
| | | | | | generate a phi of ops, which we don't currently support. llvm-svn: 304272
* NewGVN: Compute hash value of expression on demand and use it in inequality ↵Daniel Berlin2017-05-301-30/+12
| | | | | | testing. llvm-svn: 304195
* NewGVN: Fix PR33194, memory corruption by putting temporary instructions in ↵Daniel Berlin2017-05-301-5/+8
| | | | | | tables sometimes. llvm-svn: 304194
* Make helper functions static. NFC.Benjamin Kramer2017-05-261-0/+2
| | | | llvm-svn: 304029
* NewGVN: Fix PR 33119, PR 33129, due to regressed undef handlingDaniel Berlin2017-05-251-22/+42
| | | | | | Fix PR33120 and others by eliminating self-cycles a different way. llvm-svn: 303875
* [NewGVN] Update additionalUsers when we simplify to a value.Davide Italiano2017-05-241-0/+4
| | | | | | | | | | Otherwise we don't revisit an instruction that could be simplified, and when we verify, we discover there's something that changed, i.e. what we had wasn't a maximal fixpoint. Fixes PR32836. llvm-svn: 303715
* 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
* [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
* BitVector: add iterators for set bitsFrancis Visoiu Mistrih2017-05-171-2/+1
| | | | | | Differential revision: https://reviews.llvm.org/D32060 llvm-svn: 303227
* 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
* 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
* [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
* [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
* [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
* [NewGVN] Fix a consistent order for phi nodes operands.Davide Italiano2017-05-091-7/+19
| | | | | | | | | | | | | | | | | | | | | | | | | The way we currently define congruency for two PHIExpression(s) is: 1) The operands to the phi functions are congruent 2) The PHIs are defined in the same BasicBlock. NewGVN works under the assumption that phi operands are in predecessor order, or at least in some consistent order. OTOH, is valid IR: patatino: %meh = phi i16 [ %0, %winky ], [ %conv1, %tinky ] %banana = phi i16 [ %0, %tinky ], [ %conv1, %winky ] br label %end and the in-memory representations of the two SSA registers have an inconsistent order. This violation of NewGVN assumptions results into two PHIs found congruent when they're not. While we think it's useful to have always a consistent order enforced, let's fix this in NewGVN sorting uses in predecessor order before creating a PHI expression. Differential Revision: https://reviews.llvm.org/D32990 llvm-svn: 302552
* NewGVN: Make all of symbolic evaluation logically const.Daniel Berlin2017-05-091-64/+74
| | | | llvm-svn: 302550
* [NewGVN] Remove unneeded newline and format assertions. NFCI.Davide Italiano2017-05-041-5/+4
| | | | llvm-svn: 302173
* [NewGVN] Fix typo and format comment. NFCI.Davide Italiano2017-05-021-7/+4
| | | | llvm-svn: 301974
* [NewGVN] Don't derive incorrect implications.Davide Italiano2017-05-011-4/+4
| | | | | | | | | | | | | | In the testcase attached, we believe %tmp1 implies %tmp4. where: br i1 %tmp1, label %bb2, label %bb7 br i1 %tmp4, label %bb5, label %bb7 because Wwhile looking at PredicateInfo stuffs we end up calling isImpliedTrueByMatchingCmp() with the arguments backwards. Differential Revision: https://reviews.llvm.org/D32718 llvm-svn: 301849
* Kill off the old SimplifyInstruction API by converting remaining users.Daniel Berlin2017-04-281-3/+3
| | | | llvm-svn: 301673
* NewGVN: Use new SimplifyQuery based APIDaniel Berlin2017-04-261-11/+11
| | | | llvm-svn: 301466
* NewGVN: Fix memory congruence verification. The return true should be a ↵Daniel Berlin2017-04-181-8/+8
| | | | | | return false. Merge the appropriate if statements so it doesn't happen again. llvm-svn: 300584
* NewGVN: Don't waste time value numbering unreachable blocksDaniel Berlin2017-04-181-17/+6
| | | | llvm-svn: 300565
* NewGVN: Don't propagate over phi backedges where undef causes us toDaniel Berlin2017-04-141-8/+149
| | | | | | | | have >1 value, unless we can prove the phi node is cycle free. Fixes PR 32607. llvm-svn: 300299
* [IR] Redesign the case iterator in SwitchInst to actually be an iteratorChandler Carruth2017-04-121-3/+3
| | | | | | | | | | | | | | | | and to expose a handle to represent the actual case rather than having the iterator return a reference to itself. All of this allows the iterator to be used with common STL facilities, standard algorithms, etc. Doing this exposed some missing facilities in the iterator facade that I've fixed and required some work to the actual iterator to fully support the necessary API. Differential Revision: https://reviews.llvm.org/D31548 llvm-svn: 300032
OpenPOWER on IntegriCloud