summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/NewGVN
Commit message (Collapse)AuthorAgeFilesLines
...
* [NewGVN] Fix the case where we have a phi-of-ops which goes away.Davide Italiano2017-08-031-0/+72
| | | | | | Patch by Daniel Berlin, fixes PR33196 (and probably something else). llvm-svn: 309988
* [NewGVN] Now that load coercion is enable, we pass this test.Davide Italiano2017-08-021-1/+0
| | | | llvm-svn: 309872
* [NewGVN] Check for congruency of memory accesses.Davide Italiano2017-07-111-0/+91
| | | | | | | | | | This is fine as nothing in the code relies on leader and memory leader being the same for a given congruency class. Ack'ed by Dan. Fixes PR33720. llvm-svn: 307699
* NewGVN: Fix PR 33461, caused by slightly overzealous verification.Daniel Berlin2017-06-191-0/+36
| | | | llvm-svn: 305657
* NewGVN: Fix PR/33187. This is a bug caused by two things:Daniel Berlin2017-06-064-4/+150
| | | | | | | | | | | | | 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
* [InstSimplify] Constant fold the new GEP in SimplifyGEPInst.Joey Gouly2017-06-062-3/+3
| | | | llvm-svn: 304784
* NewGVN: Fix PR 33185 by checking whether we need to recursivelyDaniel Berlin2017-05-311-0/+59
| | | | | | generate a phi of ops, which we don't currently support. llvm-svn: 304272
* Fix test that wasn't update_test_check'dDaniel Berlin2017-05-311-0/+17
| | | | llvm-svn: 304271
* NewGVN: Fix PR 33119, PR 33129, due to regressed undef handlingDaniel Berlin2017-05-251-1/+2
| | | | | | 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/+45
| | | | | | | | | | 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-0/+39
| | | | llvm-svn: 303521
* [NewGVN] Actually check the NewGVN output.Davide Italiano2017-05-211-0/+30
| | | | | | Apparently I messed up squashing two consecutive commits. llvm-svn: 303516
* [NewGVN] Add a test for non most dominating leader.Davide Italiano2017-05-211-0/+34
| | | | | | | | Taken from PR32845. Dan removed the most dominating leader check in r303443, but we check this test anyway to make sure things don't regress. llvm-svn: 303515
* [NewGVN] Create a StoreExpression instead of a VariableExpression.Davide Italiano2017-05-201-0/+26
| | | | | | | | | | | | | 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: Fix PR32838.Daniel Berlin2017-05-191-0/+157
| | | | | | | | | | 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-192-10/+425
| | | | | | | | | | | | | | | | | | | | | | 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] Delete the old store when we find congruent to a load.Davide Italiano2017-05-191-0/+59
| | | | | | | (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-0/+54
| | | | | | | | | | | | 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/+24
| | | | | | | This time with an additional fix, i.e. we remove the dead @llvm.ssa.copy instruction. llvm-svn: 303385
* [NewGVN] Re-enable test now that the nondeterminism has been fixed.Davide Italiano2017-05-161-1/+0
| | | | llvm-svn: 303217
* Revert "[NewGVN] Replace predicate info leftovers."Davide Italiano2017-05-161-24/+0
| | | | | | It's breaking the bots. llvm-svn: 303142
* [NewGVN] Replace predicate info leftovers.Davide Italiano2017-05-161-0/+24
| | | | | | | | Fixes PR32945. Differential Revision: https://reviews.llvm.org/D33226 llvm-svn: 303141
* [NewGVN] Fix verification of MemoryPhis in verifyMemoryCongruency().Davide Italiano2017-05-151-0/+29
| | | | | | | | | | | | 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
* Disable llvm/test/Transforms/NewGVN/pr32934.ll while Davide is investigating.NAKAMURA Takumi2017-05-131-1/+1
| | | | llvm-svn: 302977
* [NewGVN] XFAIL a flaky test until I find out what's going on.Davide Italiano2017-05-131-0/+1
| | | | | | | | | | I bet the change is correct but this test seems to expose some underlying problem that manifest only on some buildbots, and I'm not able to reproduce locally. Unfortunately I can't debug right now but I don't want to annoy people with spurious failures, so I'll XFAIL until I can take a look (over the weekend). llvm-svn: 302976
* [NewGVN] Don't incorrectly reset the memory leader.Davide Italiano2017-05-121-0/+68
| | | | | | | | | | 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] Fix a consistent order for phi nodes operands.Davide Italiano2017-05-091-0/+42
| | | | | | | | | | | | | | | | | | | | | | | | | 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
* Support arbitrary address space pointers in masked gather/scatter intrinsics.Elad Cohen2017-05-031-8/+8
| | | | | | | | | | | | Fixes PR31789 - When loop-vectorize tries to use these intrinsics for a non-default address space pointer we fail with a "Calling a function with a bad singature!" assertion. This patch solves this by adding the 'vector of pointers' argument as an overloaded type which will determine the address space. Differential revision: https://reviews.llvm.org/D31490 llvm-svn: 302018
* [NewGVN] Don't derive incorrect implications.Davide Italiano2017-05-011-0/+24
| | | | | | | | | | | | | | 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
* [GVN] Don't coerce non-integral pointers to integers or vice versaSanjoy Das2017-04-191-0/+39
| | | | | | | | | | | | | | | | | Summary: See http://llvm.org/docs/LangRef.html#non-integral-pointer-type The NewGVN test does not fail without these changes (perhaps it does try to coerce pointers <-> integers to begin with?), but I added the test case anyway. Reviewers: dberlin Subscribers: mcrosier, llvm-commits, Prazek Differential Revision: https://reviews.llvm.org/D32208 llvm-svn: 300730
* NewGVN: Don't propagate over phi backedges where undef causes us toDaniel Berlin2017-04-141-0/+33
| | | | | | | | have >1 value, unless we can prove the phi node is cycle free. Fixes PR 32607. llvm-svn: 300299
* Add address space mangling to lifetime intrinsicsMatt Arsenault2017-04-102-8/+8
| | | | | | In preparation for allowing allocas to have non-0 addrspace. llvm-svn: 299876
* AliasAnalysis: Be less conservative about volatile than atomic.Daniel Berlin2017-04-071-1/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: getModRefInfo is meant to answer the question "what impact does this instruction have on a given memory location" (not even another instruction). Long debate on this on IRC comes to the conclusion the answer should be "nothing special". That is, a noalias volatile store does not affect a memory location just by being volatile. Note: DSE and GVN and memdep currently believe this, because memdep just goes behind AA's back after it says "modref" right now. see line 635 of memdep. Prior to this patch we would get modref there, then check aliasing, and if it said noalias, we would continue. getModRefInfo *already* has this same AA check, it just wasn't being used because volatile was lumped in with ordering. (I am separately testing whether this code in memdep is now dead except for the invariant load case) Reviewers: jyknight, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D31726 llvm-svn: 299741
* NewGVN: This patch makes memory congruence work for all types ofDaniel Berlin2017-04-062-5/+193
| | | | | | | | memorydefs, not just stores. Along the way, we audit and fixup issues about how we were tracking memory leaders, and improve the verifier to notice more memory congruency issues. llvm-svn: 299682
* NewGVN: Handle coercion of constant stores, loads, memory insts.Daniel Berlin2017-04-025-5/+59
| | | | | | | | | | | | | | | | | Summary: Depends on D30928. This adds support for coercion of stores and memory instructions that do not require insertion to process. Another few tests down. I added the relevant tests from rle.ll Reviewers: davide Subscribers: llvm-commits, Prazek Differential Revision: https://reviews.llvm.org/D30929 llvm-svn: 299330
* NewGVN: Fix PR32403 - Handling of undef in phis was not quite correctDaniel Berlin2017-03-241-0/+65
| | | | | | | due to LLVM's view of phi nodes. It would cause NewGVN not to fixpoint in some interesting edge cases. llvm-svn: 298687
* NewGVN: Fix PHI evaluation bug exposed by new verifier. We were checking ↵Daniel Berlin2017-03-181-0/+60
| | | | | | whether the incoming block was reachable instead of whether the specific edge was reachable llvm-svn: 298187
* Add missing condprop-xfail.ll that contains the remaining xfail'd testsDaniel Berlin2017-03-141-0/+123
| | | | llvm-svn: 297699
* NewGVN: We pass rle-nonlocal, we just perform the replacement in a way that ↵Daniel Berlin2017-03-131-8/+22
| | | | | | keeps the old name instead of the new one llvm-svn: 297683
* NewGVN: Rewrite DCE during elimination so we do it as well as old GVN did.Daniel Berlin2017-03-105-24/+15
| | | | llvm-svn: 297428
* NewGVN: We were not really failing this testcase, because the instructions ↵Daniel Berlin2017-03-061-7/+12
| | | | | | it was looking for are unused. GVN value numbers unused instructions, NewGVN does not. Fix the instructions to be used, so we eliminate the redundancies it's checking for, and un-XFAIL it llvm-svn: 297058
* [BasicAA] Take attributes into account when requesting modref info for a ↵Igor Laevsky2017-03-011-1/+0
| | | | | | | | call site Differential Revision: https://reviews.llvm.org/D29989 llvm-svn: 296617
* PredicateInfo: Support switch statementsDaniel Berlin2017-02-222-27/+128
| | | | | | | | | | | | | | | | | | | Summary: Depends on D29606 and D29682 Makes us pass GVN's edge.ll (we also will pass a few other testcases they just need cleaning up). Thoughts on the Predicate* hiearchy of classes especially welcome :) (it's not clear to me how best to organize it, and currently, the getBlock* seems ... uglier than maybe wasting a field somewhere or something). Reviewers: davide Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29747 llvm-svn: 295889
* NewGVN: Start making use of predicateinfo pass.Daniel Berlin2017-02-183-166/+137
| | | | | | | | | | | | Summary: This begins using the predicateinfo pass in NewGVN. Reviewers: davide Subscribers: llvm-commits, Prazek Differential Revision: https://reviews.llvm.org/D29682 llvm-svn: 295583
* NewGVN: Update a number of xfailed tests to either be correct or noteDaniel Berlin2017-02-127-33/+39
| | | | | | why they fail. llvm-svn: 294928
* NewGVN: We really pass TBAA if we enable DCE and fix the test. Note that GVN ↵Daniel Berlin2017-02-121-3/+5
| | | | | | eliminates no-use readonly/readnone calls, even if they are not marked nounwind. NewGVN only eliminates them if they are marked nounwind, and thus, trivially dead. llvm-svn: 294927
* NewGVN: Apply the fast math flags fix in r267113 to NewGVN as well.Daniel Berlin2017-02-121-1/+0
| | | | llvm-svn: 294922
* NewGVN: Clean up how we handle the INITIAL class so that everything inDaniel Berlin2017-02-111-4/+38
| | | | | | | | | | | | | | | | | | it is dead or unreachable, as it should be. This also makes the leader of INITIAL undef, enabling us to handle irreducibility properly. Summary: This lets us verify, more than we do now, that we didn't screw up value numbering. Reviewers: davide Subscribers: Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D29842 llvm-svn: 294844
* [NewGVN] Fix test so that it doesn't rely on InstCombine anymore.Davide Italiano2017-02-091-3/+5
| | | | llvm-svn: 294668
* Do not propagate DebugLoc across basic blocksTaewook Oh2017-01-311-0/+78
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: DebugLoc shouldn't be propagated across basic blocks to prevent incorrect stepping and imprecise sample profile result. rL288903 addressed the wrong DebugLoc propagation issue by limiting the copy of DebugLoc when GVN removes a fully redundant load that is dominated by some other load. However, DebugLoc is still incorrectly propagated in the following example: ``` 1: extern int g; 2: 3: void foo(int x, int y, int z) { 4: if (x) 5: g = 0; 6: else 7: g = 1; 8: 9: int i = 0; 10: for ( ; i < y ; i++) 11: if (i > z) 12: g++; 13: } ``` Below is LLVM IR representation of the program before GVN: ``` @g = external local_unnamed_addr global i32, align 4 ; Function Attrs: nounwind uwtable define void @foo(i32 %x, i32 %y, i32 %z) local_unnamed_addr #0 !dbg !4 { entry: %not.tobool = icmp eq i32 %x, 0, !dbg !8 %.sink = zext i1 %not.tobool to i32, !dbg !8 store i32 %.sink, i32* @g, align 4, !tbaa !9 %cmp8 = icmp sgt i32 %y, 0, !dbg !13 br i1 %cmp8, label %for.body.preheader, label %for.end, !dbg !17 for.body.preheader: ; preds = %entry br label %for.body, !dbg !19 for.body: ; preds = %for.body.preheader, %for.inc %i.09 = phi i32 [ %inc4, %for.inc ], [ 0, %for.body.preheader ] %cmp1 = icmp sgt i32 %i.09, %z, !dbg !19 br i1 %cmp1, label %if.then2, label %for.inc, !dbg !21 if.then2: ; preds = %for.body %0 = load i32, i32* @g, align 4, !dbg !22, !tbaa !9 %inc = add nsw i32 %0, 1, !dbg !22 store i32 %inc, i32* @g, align 4, !dbg !22, !tbaa !9 br label %for.inc, !dbg !23 for.inc: ; preds = %for.body, %if.then2 %inc4 = add nuw nsw i32 %i.09, 1, !dbg !24 %exitcond = icmp ne i32 %inc4, %y, !dbg !13 br i1 %exitcond, label %for.body, label %for.end.loopexit, !dbg !17 for.end.loopexit: ; preds = %for.inc br label %for.end, !dbg !26 for.end: ; preds = %for.end.loopexit, %entry ret void, !dbg !26 } ``` where ``` !21 = !DILocation(line: 11, column: 9, scope: !15) !22 = !DILocation(line: 12, column: 8, scope: !20) !23 = !DILocation(line: 12, column: 7, scope: !20) !24 = !DILocation(line: 10, column: 20, scope: !25) ``` And below is after GVN: ``` @g = external local_unnamed_addr global i32, align 4 define void @foo(i32 %x, i32 %y, i32 %z) local_unnamed_addr !dbg !4 { entry: %not.tobool = icmp eq i32 %x, 0, !dbg !8 %.sink = zext i1 %not.tobool to i32, !dbg !8 store i32 %.sink, i32* @g, align 4, !tbaa !9 %cmp8 = icmp sgt i32 %y, 0, !dbg !13 br i1 %cmp8, label %for.body.preheader, label %for.end, !dbg !17 for.body.preheader: ; preds = %entry br label %for.body, !dbg !19 for.body: ; preds = %for.inc, %for.body.preheader %0 = phi i32 [ %1, %for.inc ], [ %.sink, %for.body.preheader ], !dbg !21 %i.09 = phi i32 [ %inc4, %for.inc ], [ 0, %for.body.preheader ] %cmp1 = icmp sgt i32 %i.09, %z, !dbg !19 br i1 %cmp1, label %if.then2, label %for.inc, !dbg !22 if.then2: ; preds = %for.body %inc = add nsw i32 %0, 1, !dbg !21 store i32 %inc, i32* @g, align 4, !dbg !21, !tbaa !9 br label %for.inc, !dbg !23 for.inc: ; preds = %if.then2, %for.body %1 = phi i32 [ %inc, %if.then2 ], [ %0, %for.body ] %inc4 = add nuw nsw i32 %i.09, 1, !dbg !24 %exitcond = icmp ne i32 %inc4, %y, !dbg !13 br i1 %exitcond, label %for.body, label %for.end.loopexit, !dbg !17 for.end.loopexit: ; preds = %for.inc br label %for.end, !dbg !26 for.end: ; preds = %for.end.loopexit, %entry ret void, !dbg !26 } ``` As you see, GVN removes the load in if.then2 block and creates a phi instruction in for.body for it. The problem is that DebugLoc of remove load instruction is propagated to the newly created phi instruction, which is wrong. rL288903 cannot handle this case because ValuesPerBlock.size() is not 1 in this example when the load is removed. Reviewers: aprantl, andreadb, wolfgangp Reviewed By: andreadb Subscribers: davide, llvm-commits Differential Revision: https://reviews.llvm.org/D29254 llvm-svn: 293688
OpenPOWER on IntegriCloud