From cefa3d6eb69ccc3f54c7502580cddca7ab7178c0 Mon Sep 17 00:00:00 2001 From: Alina Sbirlea Date: Fri, 12 Jul 2019 22:30:30 +0000 Subject: [PATCH] [MemorySSA] Use SetVector to avoid nondeterminism. Summary: Use a SetVector for DeadBlockSet. Resolves PR42574. Reviewers: george.burgess.iv, uabelho, dblaikie Subscribers: jlebar, Prazek, mgrang, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64601 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@365970 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/MemorySSAUpdater.h | 3 +- lib/Analysis/MemorySSAUpdater.cpp | 2 +- lib/Transforms/Scalar/LoopSimplifyCFG.cpp | 4 +- lib/Transforms/Scalar/SimpleLoopUnswitch.cpp | 6 +- lib/Transforms/Utils/Local.cpp | 2 +- lib/Transforms/Utils/LoopSimplify.cpp | 3 +- test/Analysis/MemorySSA/nondeterminism.ll | 122 +++++++++++++++++++ 7 files changed, 133 insertions(+), 9 deletions(-) create mode 100644 test/Analysis/MemorySSA/nondeterminism.ll diff --git a/include/llvm/Analysis/MemorySSAUpdater.h b/include/llvm/Analysis/MemorySSAUpdater.h index 6467d41cc0b..d4d8040c1ff 100644 --- a/include/llvm/Analysis/MemorySSAUpdater.h +++ b/include/llvm/Analysis/MemorySSAUpdater.h @@ -31,6 +31,7 @@ #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" @@ -243,7 +244,7 @@ public: /// Deleted blocks still have successor info, but their predecessor edges and /// Phi nodes may already be updated. Instructions in DeadBlocks should be /// deleted after this call. - void removeBlocks(const SmallPtrSetImpl &DeadBlocks); + void removeBlocks(const SmallSetVector &DeadBlocks); /// Instruction I will be changed to an unreachable. Remove all accesses in /// I's block that follow I (inclusive), and update the Phis in the blocks' diff --git a/lib/Analysis/MemorySSAUpdater.cpp b/lib/Analysis/MemorySSAUpdater.cpp index 19559a62eb9..4c1feee7fd9 100644 --- a/lib/Analysis/MemorySSAUpdater.cpp +++ b/lib/Analysis/MemorySSAUpdater.cpp @@ -1247,7 +1247,7 @@ void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA, bool OptimizePhis) { } void MemorySSAUpdater::removeBlocks( - const SmallPtrSetImpl &DeadBlocks) { + const SmallSetVector &DeadBlocks) { // First delete all uses of BB in MemoryPhis. for (BasicBlock *BB : DeadBlocks) { Instruction *TI = BB->getTerminator(); diff --git a/lib/Transforms/Scalar/LoopSimplifyCFG.cpp b/lib/Transforms/Scalar/LoopSimplifyCFG.cpp index c650abb412d..046f4c8af49 100644 --- a/lib/Transforms/Scalar/LoopSimplifyCFG.cpp +++ b/lib/Transforms/Scalar/LoopSimplifyCFG.cpp @@ -428,8 +428,8 @@ private: /// relevant updates to DT and LI. void deleteDeadLoopBlocks() { if (MSSAU) { - SmallPtrSet DeadLoopBlocksSet(DeadLoopBlocks.begin(), - DeadLoopBlocks.end()); + SmallSetVector DeadLoopBlocksSet(DeadLoopBlocks.begin(), + DeadLoopBlocks.end()); MSSAU->removeBlocks(DeadLoopBlocksSet); } diff --git a/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp b/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp index 97153292238..aeac6f548b3 100644 --- a/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp +++ b/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp @@ -1463,8 +1463,8 @@ deleteDeadClonedBlocks(Loop &L, ArrayRef ExitBlocks, // Remove all MemorySSA in the dead blocks if (MSSAU) { - SmallPtrSet DeadBlockSet(DeadBlocks.begin(), - DeadBlocks.end()); + SmallSetVector DeadBlockSet(DeadBlocks.begin(), + DeadBlocks.end()); MSSAU->removeBlocks(DeadBlockSet); } @@ -1482,7 +1482,7 @@ static void deleteDeadBlocksFromLoop(Loop &L, MemorySSAUpdater *MSSAU) { // Find all the dead blocks tied to this loop, and remove them from their // successors. - SmallPtrSet DeadBlockSet; + SmallSetVector DeadBlockSet; // Start with loop/exit blocks and get a transitive closure of reachable dead // blocks. diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index 91d33cb0f20..39b6b889f91 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -2238,7 +2238,7 @@ bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI, assert(Reachable.size() < F.size()); NumRemoved += F.size()-Reachable.size(); - SmallPtrSet DeadBlockSet; + SmallSetVector DeadBlockSet; for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) { auto *BB = &*I; if (Reachable.count(BB)) diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index 5ec12aafff0..7e6da02d570 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -681,7 +681,8 @@ ReprocessLoop: } DT->eraseNode(ExitingBlock); if (MSSAU) { - SmallPtrSet ExitBlockSet{ExitingBlock}; + SmallSetVector ExitBlockSet; + ExitBlockSet.insert(ExitingBlock); MSSAU->removeBlocks(ExitBlockSet); } diff --git a/test/Analysis/MemorySSA/nondeterminism.ll b/test/Analysis/MemorySSA/nondeterminism.ll new file mode 100644 index 00000000000..0bb3df30b58 --- /dev/null +++ b/test/Analysis/MemorySSA/nondeterminism.ll @@ -0,0 +1,122 @@ +; RUN: opt -simplifycfg -enable-mssa-loop-dependency -S --preserve-ll-uselistorder %s | FileCheck %s +; REQUIRES: x86-registered-target +; CHECK-LABEL: @n +; CHECK: uselistorder i16 0, { 3, 2, 4, 1, 5, 0, 6 } + +; Note: test was added in an effort to ensure determinism when updating memoryssa. See PR42574. +; If the uselistorder check becomes no longer relevant, the test can be disabled or removed. + +%rec9 = type { i16, i32, i32 } + +@a = global [1 x [1 x %rec9]] zeroinitializer + +define i16 @n() { + br label %..split_crit_edge + +..split_crit_edge: ; preds = %0 + br label %.split + +bb4.us4: ; preds = %bb2.split.us32, %bb6.us28 + %i.4.01.us5 = phi i16 [ %_tmp49.us30, %bb6.us28 ] + br label %g.exit4.us21 + +bb1.i.us14: ; preds = %bb4.us4 + br label %g.exit4.us21 + +g.exit4.us21: ; preds = %bb1.i.us14, %g.exit4.critedge.us9 + %i.4.02.us22 = phi i16 [ %i.4.01.us5, %bb4.us4 ], [ %i.4.01.us5, %bb1.i.us14 ] + br label %bb6.us28 + +bb5.us26: ; preds = %g.exit4.us21 + br label %bb6.us28 + +bb6.us28: ; preds = %bb5.us26, %g.exit4.us21 + %i.4.03.us29 = phi i16 [ %i.4.02.us22, %bb5.us26 ], [ %i.4.02.us22, %g.exit4.us21 ] + %_tmp49.us30 = add nuw nsw i16 %i.4.03.us29, 1 + br label %bb4.us4 + +bb4.us.us: ; preds = %bb2.split.us.us, %bb6.us.us + %i.4.01.us.us = phi i16 [ %_tmp49.us.us, %bb6.us.us ] + br label %bb1.i.us.us + +bb1.i.us.us: ; preds = %bb4.us.us + br label %g.exit4.us.us + +g.exit4.us.us: ; preds = %bb1.i.us.us, %g.exit4.critedge.us.us + %i.4.02.us.us = phi i16 [ %i.4.01.us.us, %bb1.i.us.us ] + br label %bb5.us.us + +bb5.us.us: ; preds = %g.exit4.us.us + br label %bb6.us.us + +bb6.us.us: ; preds = %bb5.us.us, %g.exit4.us.us + %i.4.03.us.us = phi i16 [ %i.4.02.us.us, %bb5.us.us ] + %_tmp49.us.us = add nuw nsw i16 %i.4.03.us.us, 1 + br label %bb4.us.us + + +.split: ; preds = %..split_crit_edge + br label %bb2 + +bb2: ; preds = %.split, %bb7 + %h.3.0 = phi i16 [ undef, %.split ], [ %_tmp53, %bb7 ] + br label %bb2.bb2.split_crit_edge + +bb2.bb2.split_crit_edge: ; preds = %bb2 + br label %bb2.split + +bb2.split.us: ; preds = %bb2 + br label %bb4.us + +bb4.us: ; preds = %bb6.us, %bb2.split.us + %i.4.01.us = phi i16 [ 0, %bb2.split.us ] + br label %bb1.i.us + +g.exit4.critedge.us: ; preds = %bb4.us + br label %g.exit4.us + +bb1.i.us: ; preds = %bb4.us + br label %g.exit4.us + +g.exit4.us: ; preds = %bb1.i.us, %g.exit4.critedge.us + %i.4.02.us = phi i16 [ %i.4.01.us, %g.exit4.critedge.us ], [ %i.4.01.us, %bb1.i.us ] + br label %bb5.us + +bb5.us: ; preds = %g.exit4.us + br label %bb7 + +bb2.split: ; preds = %bb2.bb2.split_crit_edge + br label %bb4 + +bb4: ; preds = %bb2.split, %bb6 + %i.4.01 = phi i16 [ 0, %bb2.split ] + %_tmp16 = getelementptr [1 x [1 x %rec9]], [1 x [1 x %rec9]]* @a, i16 0, i16 %h.3.0, i16 %i.4.01, i32 0 + %_tmp17 = load i16, i16* %_tmp16, align 1 + br label %g.exit4.critedge + +bb1.i: ; preds = %bb4 + br label %g.exit4 + +g.exit4.critedge: ; preds = %bb4 + %_tmp28.c = getelementptr [1 x [1 x %rec9]], [1 x [1 x %rec9]]* @a, i16 0, i16 %h.3.0, i16 %i.4.01, i32 1 + %_tmp29.c = load i32, i32* %_tmp28.c, align 1 + %_tmp30.c = trunc i32 %_tmp29.c to i16 + br label %g.exit4 + +g.exit4: ; preds = %g.exit4.critedge, %bb1.i + %i.4.02 = phi i16 [ %i.4.01, %g.exit4.critedge ], [ %i.4.01, %bb1.i ] + %_tmp41 = getelementptr [1 x [1 x %rec9]], [1 x [1 x %rec9]]* @a, i16 0, i16 %h.3.0, i16 %i.4.02, i32 2 + br label %bb6 + +bb5: ; preds = %g.exit4 + br label %bb6 + +bb6: ; preds = %bb5, %g.exit4 + %i.4.03 = phi i16 [ %i.4.02, %bb5 ], [ %i.4.02, %g.exit4 ] + %_tmp49 = add nuw nsw i16 %i.4.03, 1 + br label %bb7 + +bb7: ; preds = %bb7.us-lcssa.us, %bb7.us-lcssa + %_tmp53 = add nsw i16 %h.3.0, 1 + br label %bb2 +} -- 2.40.0