Index: llvm/trunk/include/llvm/Transforms/Utils/SSAUpdaterBulk.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/SSAUpdaterBulk.h +++ llvm/trunk/include/llvm/Transforms/Utils/SSAUpdaterBulk.h @@ -0,0 +1,91 @@ +//===- SSAUpdaterBulk.h - Unstructured SSA Update Tool ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares the SSAUpdaterBulk class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H +#define LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/IR/PredIteratorCache.h" + +namespace llvm { + +class BasicBlock; +class PHINode; +template class SmallVectorImpl; +class Type; +class Use; +class Value; +class DominatorTree; + +/// Helper class for SSA formation on a set of values defined in multiple +/// blocks. +/// +/// This is used when code duplication or another unstructured transformation +/// wants to rewrite a set of uses of one value with uses of a set of values. +/// The update is done only when RewriteAllUses is called, all other methods are +/// used for book-keeping. That helps to share some common computations between +/// updates of different uses (which is not the case when traditional SSAUpdater +/// is used). +class SSAUpdaterBulk { + struct RewriteInfo { + DenseMap Defines; + SmallPtrSet Uses; + StringRef Name; + Type *Ty; + RewriteInfo(){}; + RewriteInfo(StringRef &N, Type *T) : Name(N), Ty(T){}; + }; + DenseMap Rewrites; + + PredIteratorCache PredCache; + + Value *computeValueAt(BasicBlock *BB, RewriteInfo &R, DominatorTree *DT); + +public: + explicit SSAUpdaterBulk(){}; + SSAUpdaterBulk(const SSAUpdaterBulk &) = delete; + SSAUpdaterBulk &operator=(const SSAUpdaterBulk &) = delete; + ~SSAUpdaterBulk(){}; + + /// Add a new variable to the SSA rewriter. This needs to be called before + /// AddAvailableValue or AddUse calls. + void AddVariable(unsigned Var, StringRef Name, Type *Ty); + + /// Indicate that a rewritten value is available in the specified block with + /// the specified value. + void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V); + + /// Record a use of the symbolic value. This use will be updated with a + /// rewritten value when RewriteAllUses is called. + void AddUse(unsigned Var, Use *U); + + /// Return true if the SSAUpdater already has a value for the specified + /// variable in the specified block. + bool HasValueForBlock(unsigned Var, BasicBlock *BB); + + /// Perform all the necessary updates, including new PHI-nodes insertion and + /// the requested uses update. + /// + /// The function requires dominator tree DT, which is used for computing + /// locations for new phi-nodes insertions. If a nonnull pointer to a vector + /// InsertedPHIs is passed, all the new phi-nodes will be added to this + /// vector. + void RewriteAllUses(DominatorTree *DT, + SmallVectorImpl *InsertedPHIs = nullptr); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H Index: llvm/trunk/lib/Transforms/Utils/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Transforms/Utils/CMakeLists.txt +++ llvm/trunk/lib/Transforms/Utils/CMakeLists.txt @@ -44,6 +44,7 @@ PromoteMemoryToRegister.cpp StripGCRelocates.cpp SSAUpdater.cpp + SSAUpdaterBulk.cpp SanitizerStats.cpp SimplifyCFG.cpp SimplifyIndVar.cpp Index: llvm/trunk/lib/Transforms/Utils/SSAUpdaterBulk.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/SSAUpdaterBulk.cpp +++ llvm/trunk/lib/Transforms/Utils/SSAUpdaterBulk.cpp @@ -0,0 +1,173 @@ +//===- SSAUpdaterBulk.cpp - Unstructured SSA Update Tool ------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the SSAUpdaterBulk class. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/SSAUpdaterBulk.h" +#include "llvm/Analysis/IteratedDominanceFrontier.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Use.h" +#include "llvm/IR/Value.h" + +using namespace llvm; + +#define DEBUG_TYPE "ssaupdaterbulk" + +/// Add a new variable to the SSA rewriter. This needs to be called before +/// AddAvailableValue or AddUse calls. +void SSAUpdaterBulk::AddVariable(unsigned Var, StringRef Name, Type *Ty) { + assert(Rewrites.find(Var) == Rewrites.end() && "Variable added twice!"); + RewriteInfo RI(Name, Ty); + Rewrites[Var] = RI; +} + +/// Indicate that a rewritten value is available in the specified block with the +/// specified value. +void SSAUpdaterBulk::AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V) { + assert(Rewrites.find(Var) != Rewrites.end() && "Should add variable first!"); + Rewrites[Var].Defines[BB] = V; +} + +/// Record a use of the symbolic value. This use will be updated with a +/// rewritten value when RewriteAllUses is called. +void SSAUpdaterBulk::AddUse(unsigned Var, Use *U) { + assert(Rewrites.find(Var) != Rewrites.end() && "Should add variable first!"); + Rewrites[Var].Uses.insert(U); +} + +/// Return true if the SSAUpdater already has a value for the specified variable +/// in the specified block. +bool SSAUpdaterBulk::HasValueForBlock(unsigned Var, BasicBlock *BB) { + return Rewrites.count(Var) ? Rewrites[Var].Defines.count(BB) : false; +} + +// Compute value at the given block BB. We either should already know it, or we +// should be able to recursively reach it going up dominator tree. +Value *SSAUpdaterBulk::computeValueAt(BasicBlock *BB, RewriteInfo &R, + DominatorTree *DT) { + if (!R.Defines.count(BB)) { + if (PredCache.get(BB).size()) { + BasicBlock *IDom = DT->getNode(BB)->getIDom()->getBlock(); + R.Defines[BB] = computeValueAt(IDom, R, DT); + } else + R.Defines[BB] = UndefValue::get(R.Ty); + } + return R.Defines[BB]; +} + +/// Given sets of UsingBlocks and DefBlocks, compute the set of LiveInBlocks. +/// This is basically a subgraph limited by DefBlocks and UsingBlocks. +static void +ComputeLiveInBlocks(const SmallPtrSetImpl &UsingBlocks, + const SmallPtrSetImpl &DefBlocks, + SmallPtrSetImpl &LiveInBlocks) { + // To determine liveness, we must iterate through the predecessors of blocks + // where the def is live. Blocks are added to the worklist if we need to + // check their predecessors. Start with all the using blocks. + SmallVector LiveInBlockWorklist(UsingBlocks.begin(), + UsingBlocks.end()); + + // Now that we have a set of blocks where the phi is live-in, recursively add + // their 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. Add the preds to the worklist unless they are a + // defining block. + for (BasicBlock *P : predecessors(BB)) { + // The value is not live into a predecessor if it defines the value. + if (DefBlocks.count(P)) + continue; + + // Otherwise it is, add to the worklist. + LiveInBlockWorklist.push_back(P); + } + } +} + +/// Helper function for finding a block which should have a value for the given +/// user. For PHI-nodes this block is the corresponding predecessor, for other +/// instructions it's their parent block. +static BasicBlock *getUserBB(Use *U) { + auto *User = cast(U->getUser()); + + if (auto *UserPN = dyn_cast(User)) + return UserPN->getIncomingBlock(*U); + else + return User->getParent(); +} + +/// Perform all the necessary updates, including new PHI-nodes insertion and the +/// requested uses update. +void SSAUpdaterBulk::RewriteAllUses(DominatorTree *DT, + SmallVectorImpl *InsertedPHIs) { + for (auto P : Rewrites) { + // Compute locations for new phi-nodes. + // For that we need to initialize DefBlocks from definitions in R.Defines, + // UsingBlocks from uses in R.Uses, then compute LiveInBlocks, and then use + // this set for computing iterated dominance frontier (IDF). + // The IDF blocks are the blocks where we need to insert new phi-nodes. + ForwardIDFCalculator IDF(*DT); + RewriteInfo &R = P.second; + SmallPtrSet DefBlocks; + for (auto Def : R.Defines) + DefBlocks.insert(Def.first); + IDF.setDefiningBlocks(DefBlocks); + + SmallPtrSet UsingBlocks; + for (auto U : R.Uses) + UsingBlocks.insert(getUserBB(U)); + + SmallVector IDFBlocks; + SmallPtrSet LiveInBlocks; + ComputeLiveInBlocks(UsingBlocks, DefBlocks, LiveInBlocks); + IDF.resetLiveInBlocks(); + IDF.setLiveInBlocks(LiveInBlocks); + IDF.calculate(IDFBlocks); + + // We've computed IDF, now insert new phi-nodes there. + SmallVector InsertedPHIsForVar; + for (auto FrontierBB : IDFBlocks) { + IRBuilder<> B(FrontierBB, FrontierBB->begin()); + PHINode *PN = B.CreatePHI(R.Ty, 0, R.Name); + R.Defines[FrontierBB] = PN; + InsertedPHIsForVar.push_back(PN); + if (InsertedPHIs) + InsertedPHIs->push_back(PN); + } + + // Fill in arguments of the inserted PHIs. + for (auto PN : InsertedPHIsForVar) { + BasicBlock *PBB = PN->getParent(); + for (BasicBlock *Pred : PredCache.get(PBB)) + PN->addIncoming(computeValueAt(Pred, R, DT), Pred); + } + + // Rewrite actual uses with the inserted definitions. + for (auto U : R.Uses) { + Value *V = computeValueAt(getUserBB(U), R, DT); + Value *OldVal = U->get(); + // Notify that users of the existing value that it is being replaced. + if (OldVal != V && OldVal->hasValueHandle()) + ValueHandleBase::ValueIsRAUWd(OldVal, V); + U->set(V); + } + } +} Index: llvm/trunk/unittests/Transforms/Utils/CMakeLists.txt =================================================================== --- llvm/trunk/unittests/Transforms/Utils/CMakeLists.txt +++ llvm/trunk/unittests/Transforms/Utils/CMakeLists.txt @@ -15,5 +15,6 @@ IntegerDivision.cpp Local.cpp OrderedInstructions.cpp + SSAUpdaterBulk.cpp ValueMapperTest.cpp ) Index: llvm/trunk/unittests/Transforms/Utils/SSAUpdaterBulk.cpp =================================================================== --- llvm/trunk/unittests/Transforms/Utils/SSAUpdaterBulk.cpp +++ llvm/trunk/unittests/Transforms/Utils/SSAUpdaterBulk.cpp @@ -0,0 +1,195 @@ +//===- SSAUpdaterBulk.cpp - Unit tests for SSAUpdaterBulk -----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/SSAUpdaterBulk.h" +#include "llvm/AsmParser/Parser.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Module.h" +#include "gtest/gtest.h" + +using namespace llvm; + +TEST(SSAUpdaterBulk, SimpleMerge) { + SSAUpdaterBulk Updater; + LLVMContext C; + Module M("SSAUpdaterTest", C); + IRBuilder<> B(C); + Type *I32Ty = B.getInt32Ty(); + auto *F = Function::Create(FunctionType::get(B.getVoidTy(), {I32Ty}, false), + GlobalValue::ExternalLinkage, "F", &M); + + // Generate a simple program: + // if: + // br i1 true, label %true, label %false + // true: + // %1 = add i32 %0, 1 + // %2 = sub i32 %0, 2 + // br label %merge + // false: + // %3 = add i32 %0, 3 + // %4 = sub i32 %0, 4 + // br label %merge + // merge: + // %5 = add i32 %1, 5 + // %6 = add i32 %3, 6 + // %7 = add i32 %2, %4 + // %8 = sub i32 %2, %4 + Argument *FirstArg = &*(F->arg_begin()); + BasicBlock *IfBB = BasicBlock::Create(C, "if", F); + BasicBlock *TrueBB = BasicBlock::Create(C, "true", F); + BasicBlock *FalseBB = BasicBlock::Create(C, "false", F); + BasicBlock *MergeBB = BasicBlock::Create(C, "merge", F); + + B.SetInsertPoint(IfBB); + B.CreateCondBr(B.getTrue(), TrueBB, FalseBB); + + B.SetInsertPoint(TrueBB); + Value *AddOp1 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 1)); + Value *SubOp1 = B.CreateSub(FirstArg, ConstantInt::get(I32Ty, 2)); + B.CreateBr(MergeBB); + + B.SetInsertPoint(FalseBB); + Value *AddOp2 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 3)); + Value *SubOp2 = B.CreateSub(FirstArg, ConstantInt::get(I32Ty, 4)); + B.CreateBr(MergeBB); + + B.SetInsertPoint(MergeBB, MergeBB->begin()); + auto *I1 = cast(B.CreateAdd(AddOp1, ConstantInt::get(I32Ty, 5))); + auto *I2 = cast(B.CreateAdd(AddOp2, ConstantInt::get(I32Ty, 6))); + auto *I3 = cast(B.CreateAdd(SubOp1, SubOp2)); + auto *I4 = cast(B.CreateSub(SubOp1, SubOp2)); + + // Now rewrite uses in instructions %5, %6, %7. They need to use a phi, which + // SSAUpdater should insert into %merge. + // Intentionally don't touch %8 to see that SSAUpdater only changes + // instructions that were explicitly specified. + Updater.AddVariable(0, "a", I32Ty); + Updater.AddAvailableValue(0, TrueBB, AddOp1); + Updater.AddAvailableValue(0, FalseBB, AddOp2); + Updater.AddUse(0, &I1->getOperandUse(0)); + Updater.AddUse(0, &I2->getOperandUse(0)); + + Updater.AddVariable(1, "b", I32Ty); + Updater.AddAvailableValue(1, TrueBB, SubOp1); + Updater.AddAvailableValue(1, FalseBB, SubOp2); + Updater.AddUse(1, &I3->getOperandUse(0)); + Updater.AddUse(1, &I3->getOperandUse(1)); + + DominatorTree DT(*F); + Updater.RewriteAllUses(&DT); + + // Check how %5 and %6 were rewritten. + PHINode *UpdatePhiA = dyn_cast_or_null(I1->getOperand(0)); + EXPECT_NE(UpdatePhiA, nullptr); + EXPECT_EQ(UpdatePhiA->getIncomingValueForBlock(TrueBB), AddOp1); + EXPECT_EQ(UpdatePhiA->getIncomingValueForBlock(FalseBB), AddOp2); + EXPECT_EQ(UpdatePhiA, dyn_cast_or_null(I1->getOperand(0))); + + // Check how %7 was rewritten. + PHINode *UpdatePhiB = dyn_cast_or_null(I3->getOperand(0)); + EXPECT_EQ(UpdatePhiB->getIncomingValueForBlock(TrueBB), SubOp1); + EXPECT_EQ(UpdatePhiB->getIncomingValueForBlock(FalseBB), SubOp2); + EXPECT_EQ(UpdatePhiB, dyn_cast_or_null(I3->getOperand(1))); + + // Check that %8 was kept untouched. + EXPECT_EQ(I4->getOperand(0), SubOp1); + EXPECT_EQ(I4->getOperand(1), SubOp2); +} + +TEST(SSAUpdaterBulk, Irreducible) { + SSAUpdaterBulk Updater; + LLVMContext C; + Module M("SSAUpdaterTest", C); + IRBuilder<> B(C); + Type *I32Ty = B.getInt32Ty(); + auto *F = Function::Create(FunctionType::get(B.getVoidTy(), {I32Ty}, false), + GlobalValue::ExternalLinkage, "F", &M); + + // Generate a small program with a multi-entry loop: + // if: + // %1 = add i32 %0, 1 + // br i1 true, label %loopmain, label %loopstart + // + // loopstart: + // %2 = add i32 %0, 2 + // br label %loopmain + // + // loopmain: + // %3 = add i32 %1, 3 + // br i1 true, label %loopstart, label %afterloop + // + // afterloop: + // %4 = add i32 %2, 4 + // ret i32 %0 + Argument *FirstArg = &*F->arg_begin(); + BasicBlock *IfBB = BasicBlock::Create(C, "if", F); + BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F); + BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F); + BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F); + + B.SetInsertPoint(IfBB); + Value *AddOp1 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 1)); + B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB); + + B.SetInsertPoint(LoopStartBB); + Value *AddOp2 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 2)); + B.CreateBr(LoopMainBB); + + B.SetInsertPoint(LoopMainBB); + auto *I1 = cast(B.CreateAdd(AddOp1, ConstantInt::get(I32Ty, 3))); + B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB); + + B.SetInsertPoint(AfterLoopBB); + auto *I2 = cast(B.CreateAdd(AddOp2, ConstantInt::get(I32Ty, 4))); + ReturnInst *Return = B.CreateRet(FirstArg); + + // Now rewrite uses in instructions %3, %4, and 'ret i32 %0'. Only %4 needs a + // new phi, others should be able to work with existing values. + // The phi for %4 should be inserted into LoopMainBB and should look like + // this: + // %b = phi i32 [ %2, %loopstart ], [ undef, %if ] + // No other rewrites should be made. + + // Add use in %3. + Updater.AddVariable(0, "c", I32Ty); + Updater.AddAvailableValue(0, IfBB, AddOp1); + Updater.AddUse(0, &I1->getOperandUse(0)); + + // Add use in %4. + Updater.AddVariable(1, "b", I32Ty); + Updater.AddAvailableValue(1, LoopStartBB, AddOp2); + Updater.AddUse(1, &I2->getOperandUse(0)); + + // Add use in the return instruction. + Updater.AddVariable(2, "a", I32Ty); + Updater.AddAvailableValue(2, &F->getEntryBlock(), FirstArg); + Updater.AddUse(2, &Return->getOperandUse(0)); + + // Save all inserted phis into a vector. + SmallVector Inserted; + DominatorTree DT(*F); + Updater.RewriteAllUses(&DT, &Inserted); + + // Only one phi should have been inserted. + EXPECT_EQ(Inserted.size(), 1u); + + // I1 and Return should use the same values as they used before. + EXPECT_EQ(I1->getOperand(0), AddOp1); + EXPECT_EQ(Return->getOperand(0), FirstArg); + + // I2 should use the new phi. + PHINode *UpdatePhi = dyn_cast_or_null(I2->getOperand(0)); + EXPECT_NE(UpdatePhi, nullptr); + EXPECT_EQ(UpdatePhi->getIncomingValueForBlock(LoopStartBB), AddOp2); + EXPECT_EQ(UpdatePhi->getIncomingValueForBlock(IfBB), UndefValue::get(I32Ty)); +}