From 1e98c0422640cfe512c0ef529ed2e3f2ecec3f67 Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Mon, 26 Sep 2016 17:22:54 +0000 Subject: [PATCH] Remove pruning of phi nodes in MemorySSA - it makes updating harder Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24923 llvm-svn: 282419 --- llvm/include/llvm/Transforms/Utils/MemorySSA.h | 3 +- llvm/lib/Transforms/Utils/MemorySSA.cpp | 45 +++------------------- llvm/test/Transforms/Util/MemorySSA/livein.ll | 53 -------------------------- 3 files changed, 6 insertions(+), 95 deletions(-) delete mode 100644 llvm/test/Transforms/Util/MemorySSA/livein.ll diff --git a/llvm/include/llvm/Transforms/Utils/MemorySSA.h b/llvm/include/llvm/Transforms/Utils/MemorySSA.h index 4f5a64d..fc10a17 100644 --- a/llvm/include/llvm/Transforms/Utils/MemorySSA.h +++ b/llvm/include/llvm/Transforms/Utils/MemorySSA.h @@ -612,8 +612,7 @@ private: MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace); void removeFromLookups(MemoryAccess *); - void placePHINodes(const SmallPtrSetImpl &, - const SmallPtrSetImpl &); + void placePHINodes(const SmallPtrSetImpl &); MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *); void renamePass(DomTreeNode *, MemoryAccess *IncomingVal, SmallPtrSet &Visited); diff --git a/llvm/lib/Transforms/Utils/MemorySSA.cpp b/llvm/lib/Transforms/Utils/MemorySSA.cpp index 151e606..e06b604 100644 --- a/llvm/lib/Transforms/Utils/MemorySSA.cpp +++ b/llvm/lib/Transforms/Utils/MemorySSA.cpp @@ -1348,7 +1348,7 @@ void MemorySSA::OptimizeUses::optimizeUsesInBlock( // branch of the dominator tree first. This will guarantee this resets on // the smallest set of blocks. if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock != BB && - !DT->dominates(LocInfo.LowerBoundBlock, BB)){ + !DT->dominates(LocInfo.LowerBoundBlock, BB)) { // Reset the lower bound of things to check. // TODO: Some day we should be able to reset to last kill, rather than // 0. @@ -1455,12 +1455,10 @@ void MemorySSA::OptimizeUses::optimizeUses() { } void MemorySSA::placePHINodes( - const SmallPtrSetImpl &DefiningBlocks, - const SmallPtrSetImpl &LiveInBlocks) { + const SmallPtrSetImpl &DefiningBlocks) { // Determine where our MemoryPhi's should go ForwardIDFCalculator IDFs(*DT); IDFs.setDefiningBlocks(DefiningBlocks); - IDFs.setLiveInBlocks(LiveInBlocks); SmallVector IDFBlocks; IDFs.calculate(IDFBlocks); @@ -1511,40 +1509,7 @@ void MemorySSA::buildMemorySSA() { if (Accesses) DefUseBlocks.insert(&B); } - - // Compute live-in. - // Live in is normally defined as "all the blocks on the path from each def to - // each of it's uses". - // MemoryDef's are implicit uses of previous state, so they are also uses. - // This means we don't really have def-only instructions. The only - // MemoryDef's that are not really uses are those that are of the LiveOnEntry - // variable (because LiveOnEntry can reach anywhere, and every def is a - // must-kill of LiveOnEntry). - // In theory, you could precisely compute live-in by using alias-analysis to - // disambiguate defs and uses to see which really pair up with which. - // In practice, this would be really expensive and difficult. So we simply - // assume all defs are also uses that need to be kept live. - // Because of this, the end result of this live-in computation will be "the - // entire set of basic blocks that reach any use". - - SmallPtrSet LiveInBlocks; - SmallVector LiveInBlockWorklist(DefUseBlocks.begin(), - DefUseBlocks.end()); - // Now that we have a set of blocks where a value is live-in, recursively add - // predecessors until we find the full region the value is live. - while (!LiveInBlockWorklist.empty()) { - BasicBlock *BB = LiveInBlockWorklist.pop_back_val(); - - // The block really is live in here, insert it into the set. If already in - // the set, then it has already been processed. - if (!LiveInBlocks.insert(BB).second) - continue; - - // Since the value is live into BB, it is either defined in a predecessor or - // live into it to. - LiveInBlockWorklist.append(pred_begin(BB), pred_end(BB)); - } - placePHINodes(DefiningBlocks, LiveInBlocks); + placePHINodes(DefiningBlocks); // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get // filled in with all blocks. @@ -2069,8 +2034,8 @@ bool MemorySSAPrinterLegacyPass::runOnFunction(Function &F) { char MemorySSAAnalysis::PassID; -MemorySSAAnalysis::Result -MemorySSAAnalysis::run(Function &F, FunctionAnalysisManager &AM) { +MemorySSAAnalysis::Result MemorySSAAnalysis::run(Function &F, + FunctionAnalysisManager &AM) { auto &DT = AM.getResult(F); auto &AA = AM.getResult(F); return MemorySSAAnalysis::Result(make_unique(F, &AA, &DT)); diff --git a/llvm/test/Transforms/Util/MemorySSA/livein.ll b/llvm/test/Transforms/Util/MemorySSA/livein.ll deleted file mode 100644 index 93072ea..0000000 --- a/llvm/test/Transforms/Util/MemorySSA/livein.ll +++ /dev/null @@ -1,53 +0,0 @@ -; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s -; RUN: opt -aa-pipeline=basic-aa -passes='print,verify' -disable-output < %s 2>&1 | FileCheck %s -define void @F(i8*) { - br i1 true, label %left, label %right -left: -; CHECK: 1 = MemoryDef(liveOnEntry) - store i8 16, i8* %0 - br label %merge -right: - br label %merge - -merge: -; CHECK-NOT: 2 = MemoryPhi -ret void -} - -define void @F2(i8*) { - br i1 true, label %left, label %right -left: -; CHECK: 1 = MemoryDef(liveOnEntry) - store i8 16, i8* %0 - br label %merge -right: - br label %merge - -merge: -; CHECK: 2 = MemoryPhi({left,1},{right,liveOnEntry}) -%c = load i8, i8* %0 -ret void -} - -; Ensure we treat def-only blocks as though they have uses for phi placement. -; CHECK-LABEL: define void @F3 -define void @F3() { - %a = alloca i8 -; CHECK: 1 = MemoryDef(liveOnEntry) -; CHECK-NEXT: store i8 0, i8* %a - store i8 0, i8* %a - br i1 undef, label %if.then, label %if.end - -if.then: -; CHECK: 2 = MemoryDef(1) -; CHECK-NEXT: store i8 1, i8* %a - store i8 1, i8* %a - br label %if.end - -if.end: -; CHECK: 4 = MemoryPhi({%0,1},{if.then,2}) -; CHECK: 3 = MemoryDef(4) -; CHECK-NEXT: store i8 2, i8* %a - store i8 2, i8* %a - ret void -} -- 2.7.4