From 0d362a25a4451812b6ce70f6a97d504075f20fb9 Mon Sep 17 00:00:00 2001 From: Davide Italiano Date: Thu, 3 Aug 2017 21:17:49 +0000 Subject: [PATCH] [NewGVN] Fix the case where we have a phi-of-ops which goes away. Patch by Daniel Berlin, fixes PR33196 (and probably something else). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@309988 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/NewGVN.cpp | 33 +++++++++++--- test/Transforms/NewGVN/pr33196.ll | 72 +++++++++++++++++++++++++++++++ 2 files changed, 99 insertions(+), 6 deletions(-) create mode 100644 test/Transforms/NewGVN/pr33196.ll diff --git a/lib/Transforms/Scalar/NewGVN.cpp b/lib/Transforms/Scalar/NewGVN.cpp index 096bbcf1116..d6e34666112 100644 --- a/lib/Transforms/Scalar/NewGVN.cpp +++ b/lib/Transforms/Scalar/NewGVN.cpp @@ -471,8 +471,8 @@ class NewGVN { DenseSet PHINodeUses; // Map a temporary instruction we created to a parent block. DenseMap TempToBlock; - // Map between the temporary phis we created and the real instructions they - // are known equivalent to. + // Map between the already in-program instructions and the temporary phis we + // created that they are known equivalent to. DenseMap RealToTemp; // In order to know when we should re-process instructions that have // phi-of-ops, we track the set of expressions that they needed as @@ -486,10 +486,14 @@ class NewGVN { DenseMap> ExpressionToPhiOfOps; // Map from basic block to the temporary operations we created - DenseMap> PHIOfOpsPHIs; + DenseMap> PHIOfOpsPHIs; // Map from temporary operation to MemoryAccess. DenseMap TempToMemory; // Set of all temporary instructions we created. + // Note: This will include instructions that were just created during value + // numbering. The way to test if something is using them is to check + // RealToTemp. + DenseSet AllTempInstructions; // Mapping from predicate info we used to the instructions we used it with. @@ -634,6 +638,7 @@ private: const Expression *makePossiblePhiOfOps(Instruction *, SmallPtrSetImpl &); void addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue); + void removePhiOfOps(Instruction *I, PHINode *PHITemp); // Value number an Instruction or MemoryPhi. void valueNumberMemoryPhi(MemoryPhi *); @@ -2414,11 +2419,22 @@ void NewGVN::processOutgoingEdges(TerminatorInst *TI, BasicBlock *B) { } } +// Remove the PHI of Ops PHI for I +void NewGVN::removePhiOfOps(Instruction *I, PHINode *PHITemp) { + InstrDFS.erase(PHITemp); + // It's still a temp instruction. We keep it in the array so it gets erased. + // However, it's no longer used by I, or in the block/ + PHIOfOpsPHIs[getBlockForValue(PHITemp)].erase(PHITemp); + TempToBlock.erase(PHITemp); + RealToTemp.erase(I); +} + +// Add PHI Op in BB as a PHI of operations version of ExistingValue. void NewGVN::addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue) { InstrDFS[Op] = InstrToDFSNum(ExistingValue); AllTempInstructions.insert(Op); - PHIOfOpsPHIs[BB].push_back(Op); + PHIOfOpsPHIs[BB].insert(Op); TempToBlock[Op] = BB; RealToTemp[ExistingValue] = Op; } @@ -2783,8 +2799,13 @@ void NewGVN::valueNumberInstruction(Instruction *I) { if (Symbolized && !isa(Symbolized) && !isa(Symbolized) && PHINodeUses.count(I)) { auto *PHIE = makePossiblePhiOfOps(I, Visited); - if (PHIE) + // If we created a phi of ops, use it. + // If we couldn't create one, make sure we don't leave one lying around + if (PHIE) { Symbolized = PHIE; + } else if (auto *Op = RealToTemp.lookup(I)) { + removePhiOfOps(I, Op); + } } } else { @@ -3626,7 +3647,7 @@ bool NewGVN::eliminateInstructions(Function &F) { CC->swap(MembersLeft); } else { // If this is a singleton, we can skip it. - if (CC->size() != 1 || RealToTemp.lookup(Leader)) { + if (CC->size() != 1 || RealToTemp.count(Leader)) { // This is a stack because equality replacement/etc may place // constants in the middle of the member list, and we want to use // those constant values in preference to the current leader, over diff --git a/test/Transforms/NewGVN/pr33196.ll b/test/Transforms/NewGVN/pr33196.ll new file mode 100644 index 00000000000..140965ae005 --- /dev/null +++ b/test/Transforms/NewGVN/pr33196.ll @@ -0,0 +1,72 @@ +; RUN: opt -S -newgvn %s | FileCheck %s + +; CHECK: define i32 @main() { +; CHECK-NEXT: entry: +; CHECK-NEXT: %tmp = load i32, i32* @d, align 4 +; CHECK-NEXT: %tmp1 = load i32, i32* @c, align 4 +; CHECK-NEXT: %tobool = icmp eq i32 %tmp1, -1 +; CHECK-NEXT: br i1 %tobool, label %if.end, label %if.then +; CHECK: if.then: +; CHECK-NEXT: br label %L +; CHECK: L: +; CHECK-NEXT: %e.0 = phi i32 [ 0, %if.then ], [ %e.1, %if.then4 ] +; CHECK-NEXT: br label %if.end +; CHECK: if.end: +; CHECK-NEXT: %e.1 = phi i32 [ %e.0, %L ], [ %tmp, %entry ] +; CHECK-NEXT: store i32 %e.1, i32* @a, align 4 +; CHECK-NEXT: %tmp2 = load i32, i32* @b, align 4 +; CHECK-NEXT: store i32 0, i32* @b, align 4 +; CHECK-NEXT: %sext = shl i32 %tmp2, 16 +; CHECK-NEXT: %conv1 = ashr exact i32 %sext, 16 +; CHECK-NEXT: %add = add nsw i32 %conv1, %tmp1 +; CHECK-NEXT: %add2 = add nsw i32 %add, %e.1 +; CHECK-NEXT: store i32 %add2, i32* @a, align 4 +; CHECK-NEXT: %tobool3 = icmp eq i32 %add2, 0 +; CHECK-NEXT: br i1 %tobool3, label %if.end5, label %if.then4 +; CHECK: if.then4: +; CHECK-NEXT: br label %L +; CHECK: if.end5: +; CHECK-NEXT: ret i32 0 +; CHECK-NEXT: } + +@d = global i32 1, align 4 +@c = common global i32 0, align 4 +@a = common global i32 0, align 4 +@b = common global i32 0, align 4 + +define i32 @main() { +entry: + %tmp = load i32, i32* @d, align 4 + %tmp1 = load i32, i32* @c, align 4 + %tobool = icmp eq i32 %tmp1, -1 + br i1 %tobool, label %if.end, label %if.then + +if.then: ; preds = %entry + br label %L + +L: ; preds = %if.then4, %if.then + %e.0 = phi i32 [ 0, %if.then ], [ %e.1, %if.then4 ] + br label %if.end + +if.end: ; preds = %L, %entry + %e.1 = phi i32 [ %e.0, %L ], [ %tmp, %entry ] + store i32 %e.1, i32* @a, align 4 + %tmp2 = load i32, i32* @b, align 4 + store i32 0, i32* @b, align 4 + %sext = shl i32 %tmp2, 16 + %conv1 = ashr exact i32 %sext, 16 + %tmp3 = load i32, i32* @c, align 4 + %add = add nsw i32 %conv1, %tmp3 + %tmp4 = load i32, i32* @a, align 4 + %and = and i32 %tmp4, %e.1 + %add2 = add nsw i32 %add, %and + store i32 %add2, i32* @a, align 4 + %tobool3 = icmp eq i32 %add2, 0 + br i1 %tobool3, label %if.end5, label %if.then4 + +if.then4: ; preds = %if.end + br label %L + +if.end5: ; preds = %if.end + ret i32 0 +} -- 2.50.1