From 42f1f6e771df5a450033067fcbff2ddb57f70c14 Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Wed, 11 Jan 2017 20:22:36 +0000 Subject: [PATCH] NewGVN: Fix PR31594, by tracking the store count of congruence classes, and updating checking to allow for equivalence through reachability. (Sadly, the checking here is not perfect, and can't be made perfect, so we'll have to disable it after we are satisfied with correctness. Right now it is just "very unlikely" to happen.) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@291698 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/NewGVN.cpp | 61 ++++++++++++--- test/Transforms/NewGVN/pr31594.ll | 119 ++++++++++++++++++++++++++++++ 2 files changed, 169 insertions(+), 11 deletions(-) create mode 100644 test/Transforms/NewGVN/pr31594.ll diff --git a/lib/Transforms/Scalar/NewGVN.cpp b/lib/Transforms/Scalar/NewGVN.cpp index 33b3e9ad6e0..1c1e04a6992 100644 --- a/lib/Transforms/Scalar/NewGVN.cpp +++ b/lib/Transforms/Scalar/NewGVN.cpp @@ -135,6 +135,10 @@ struct CongruenceClass { // purposes, and for skipping empty classes. bool Dead = false; + // Number of stores in this congruence class. + // This is used so we can detect store equivalence changes properly. + unsigned StoreCount = 0; + explicit CongruenceClass(unsigned ID) : ID(ID) {} CongruenceClass(unsigned ID, Value *Leader, const Expression *E) : ID(ID), RepLeader(Leader), DefiningExpr(E) {} @@ -348,7 +352,8 @@ private: void cleanupTables(); std::pair assignDFSNumbers(BasicBlock *, unsigned); void updateProcessedCount(Value *V); - void verifyMemoryCongruency(); + void verifyMemoryCongruency() const; + bool singleReachablePHIPath(const MemoryAccess *, const MemoryAccess *) const; }; char NewGVN::ID = 0; @@ -718,10 +723,10 @@ const StoreExpression *NewGVN::createStoreExpression(StoreInst *SI, // Utility function to check whether the congruence class has a member other // than the given instruction. bool hasMemberOtherThanUs(const CongruenceClass *CC, Instruction *I) { - // Either it has more than one member, in which case it must contain something - // other than us (because it's indexed by value), or if it only has one member + // Either it has more than one store, in which case it must contain something + // other than us (because it's indexed by value), or if it only has one store // right now, that member should not be us. - return CC->Members.size() > 1 || CC->Members.count(I) == 0; + return CC->StoreCount > 1 || CC->Members.count(I) == 0; } const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I, @@ -1145,6 +1150,7 @@ void NewGVN::performCongruenceFinding(Value *V, const Expression *E) { moveValueToNewCongruenceClass(V, VClass, EClass); + markUsersTouched(V); if (auto *I = dyn_cast(V)) { if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) { @@ -1470,9 +1476,40 @@ void NewGVN::valueNumberInstruction(Instruction *I) { } } +// Check if there is a path, using single or equal argument phi nodes, from +// First to Second. +bool NewGVN::singleReachablePHIPath(const MemoryAccess *First, + const MemoryAccess *Second) const { + if (First == Second) + return true; + + if (auto *FirstDef = dyn_cast(First)) { + auto *DefAccess = FirstDef->getDefiningAccess(); + return singleReachablePHIPath(DefAccess, Second); + } else { + auto *MP = cast(First); + auto ReachableOperandPred = [&](const Use &U) { + return ReachableBlocks.count(MP->getIncomingBlock(U)); + }; + auto FilteredPhiArgs = + make_filter_range(MP->operands(), ReachableOperandPred); + SmallVector OperandList; + std::copy(FilteredPhiArgs.begin(), FilteredPhiArgs.end(), + std::back_inserter(OperandList)); + bool Okay = OperandList.size() == 1; + if (!Okay) + Okay = std::equal(OperandList.begin(), OperandList.end(), + OperandList.begin()); + if (Okay) + return singleReachablePHIPath(cast(OperandList[0]), Second); + return false; + } +} + // Verify the that the memory equivalence table makes sense relative to the -// congruence classes. -void NewGVN::verifyMemoryCongruency() { +// congruence classes. Note that this checking is not perfect, and is currently +// subject to very rare false negatives. It is only useful for testing/debugging. +void NewGVN::verifyMemoryCongruency() const { // Anything equivalent in the memory access table should be in the same // congruence class. @@ -1499,11 +1536,13 @@ void NewGVN::verifyMemoryCongruency() { if (auto *FirstMUD = dyn_cast(KV.first)) { auto *SecondMUD = dyn_cast(KV.second); if (FirstMUD && SecondMUD) - assert( - ValueToClass.lookup(FirstMUD->getMemoryInst()) == - ValueToClass.lookup(SecondMUD->getMemoryInst()) && - "The instructions for these memory operations should have been in " - "the same congruence class"); + assert(singleReachablePHIPath(FirstMUD, SecondMUD) || + ValueToClass.lookup(FirstMUD->getMemoryInst()) == + ValueToClass.lookup(SecondMUD->getMemoryInst()) && + "The instructions for these memory operations should have " + "been in " + "the same congruence class or reachable through a single " + "argument phi"); } else if (auto *FirstMP = dyn_cast(KV.first)) { // We can only sanely verify that MemoryDefs in the operand list all have diff --git a/test/Transforms/NewGVN/pr31594.ll b/test/Transforms/NewGVN/pr31594.ll new file mode 100644 index 00000000000..0cdac1a7fff --- /dev/null +++ b/test/Transforms/NewGVN/pr31594.ll @@ -0,0 +1,119 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -basicaa -newgvn -S | FileCheck %s + +target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" + +define void @patatino(i8* %blah, i32 %choice) { +; CHECK-LABEL: @patatino( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[WHILE_COND:%.*]] +; CHECK: while.cond: +; CHECK-NEXT: [[FOO:%.*]] = phi i8* [ [[BLAH:%.*]], [[ENTRY:%.*]] ], [ null, [[WHILE_BODY:%.*]] ] +; CHECK-NEXT: switch i32 [[CHOICE:%.*]], label [[WHILE_BODY]] [ +; CHECK-NEXT: i32 -1, label [[WHILE_END:%.*]] +; CHECK-NEXT: i32 40, label [[LAND_END:%.*]] +; CHECK-NEXT: ] +; CHECK: land.end: +; CHECK-NEXT: br label [[WHILE_END]] +; CHECK: while.body: +; CHECK-NEXT: br label [[WHILE_COND]] +; CHECK: while.end: +; CHECK-NEXT: store i8 0, i8* [[FOO]], align 1 +; CHECK-NEXT: store i8 0, i8* [[BLAH]], align 1 +; CHECK-NEXT: ret void +; +entry: + br label %while.cond + +while.cond: + %foo = phi i8* [ %blah, %entry ], [ null, %while.body ] + switch i32 %choice, label %while.body [ + i32 -1, label %while.end + i32 40, label %land.end + ] + +land.end: + br label %while.end + +while.body: + br label %while.cond + +while.end: + %foo.lcssa = phi i8* [ %foo, %land.end ], [ %foo, %while.cond ] +;; These two stores will initially be considered equivalent, but then proven not. +;; the second store would previously end up deciding it's equivalent to a previous +;; store, but it was really just finding an optimistic version of itself +;; in the congruence class. + store i8 0, i8* %foo.lcssa, align 1 + %0 = load i8, i8* %blah, align 1 + %loaded = icmp eq i8 %0, 0 + store i8 0, i8* %blah, align 1 + ret void +} + + +;; This is an example of a case where the memory states are equivalent solely due to unreachability, +;; but the stores are not equal. +define void @foo(i8* %arg) { +; CHECK-LABEL: @foo( +; CHECK-NEXT: bb: +; CHECK-NEXT: br label [[BB1:%.*]] +; CHECK: bb1: +; CHECK-NEXT: [[TMP:%.*]] = phi i8* [ [[ARG:%.*]], [[BB:%.*]] ], [ null, [[BB2:%.*]] ] +; CHECK-NEXT: br i1 undef, label [[BB3:%.*]], label [[BB2]] +; CHECK: bb2: +; CHECK-NEXT: br label [[BB1]] +; CHECK: bb3: +; CHECK-NEXT: store i8 0, i8* [[TMP]], !g !0 +; CHECK-NEXT: br label [[BB4:%.*]] +; CHECK: bb4: +; CHECK-NEXT: br label [[BB6:%.*]] +; CHECK: bb6: +; CHECK-NEXT: br i1 undef, label [[BB9:%.*]], label [[BB7:%.*]] +; CHECK: bb7: +; CHECK-NEXT: switch i8 0, label [[BB6]] [ +; CHECK-NEXT: i8 6, label [[BB8:%.*]] +; CHECK-NEXT: ] +; CHECK: bb8: +; CHECK-NEXT: br label [[BB4]] +; CHECK: bb9: +; CHECK-NEXT: store i8 0, i8* [[ARG]], !g !0 +; CHECK-NEXT: unreachable +; +bb: + br label %bb1 + +bb1: ; preds = %bb2, %bb + %tmp = phi i8* [ %arg, %bb ], [ null, %bb2 ] + br i1 undef, label %bb3, label %bb2 + +bb2: ; preds = %bb1 + br label %bb1 + +bb3: ; preds = %bb1 + store i8 0, i8* %tmp, !g !0 + br label %bb4 + +bb4: ; preds = %bb8, %bb3 + %tmp5 = phi i8* [ null, %bb8 ], [ %arg, %bb3 ] + br label %bb6 + +bb6: ; preds = %bb7, %bb4 + br i1 undef, label %bb9, label %bb7 + +bb7: ; preds = %bb6 + switch i8 0, label %bb6 [ + i8 6, label %bb8 + ] + +bb8: ; preds = %bb7 + store i8 undef, i8* %tmp5, !g !0 + br label %bb4 + +bb9: ; preds = %bb6 + %tmp10 = phi i8* [ %tmp5, %bb6 ] + store i8 0, i8* %tmp10, !g !0 + unreachable +} + +!0 = !{} -- 2.40.0