Index: llvm/include/llvm/Transforms/Utils/SSAUpdaterBulk.h =================================================================== --- /dev/null +++ llvm/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/lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -66,6 +66,7 @@ #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/SSAUpdater.h" +#include "llvm/Transforms/Utils/SSAUpdaterBulk.h" #include "llvm/Transforms/Utils/ValueMapper.h" #include #include @@ -1984,9 +1985,13 @@ // now have to update all uses of the value to use either the original value, // the cloned value, or some PHI derived value. This can require arbitrary // PHI insertion, of which we are prepared to do, clean these up now. - SSAUpdater SSAUpdate; + SSAUpdaterBulk SSAUpdate; SmallVector UsesToRename; + + unsigned VarNum = 0; for (Instruction &I : *BB) { + UsesToRename.clear(); + // Scan all uses of this instruction to see if it is used outside of its // block, and if so, record them in UsesToRename. for (Use &U : I.uses()) { @@ -2003,19 +2008,15 @@ // If there are no uses outside the block, we're done with this instruction. if (UsesToRename.empty()) continue; - - DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n"); - - // We found a use of I outside of BB. Rename all uses of I that are outside - // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks - // with the two values we know. - SSAUpdate.Initialize(I.getType(), I.getName()); - SSAUpdate.AddAvailableValue(BB, &I); - SSAUpdate.AddAvailableValue(NewBB, ValueMapping[&I]); - - while (!UsesToRename.empty()) - SSAUpdate.RewriteUse(*UsesToRename.pop_back_val()); - DEBUG(dbgs() << "\n"); + SSAUpdate.AddVariable(VarNum, I.getName(), I.getType()); + + // We found a use of I outside of BB - ee need to rename all uses of I that + // are outside its block to be uses of the appropriate PHI node etc. + SSAUpdate.AddAvailableValue(VarNum, BB, &I); + SSAUpdate.AddAvailableValue(VarNum, NewBB, ValueMapping[&I]); + for (auto U : UsesToRename) + SSAUpdate.AddUse(VarNum, U); + VarNum++; } // Ok, NewBB is good to go. Update the terminator of PredBB to jump to @@ -2032,6 +2033,9 @@ {DominatorTree::Insert, PredBB, NewBB}, {DominatorTree::Delete, PredBB, BB}}); + DominatorTree *DT = &DDT->flush(); + SSAUpdate.RewriteAllUses(DT); + // At this point, the IR is fully up to date and consistent. Do a quick scan // over the new instructions and zap any that are constants or dead. This // frequently happens because of phi translation. Index: llvm/lib/Transforms/Utils/CMakeLists.txt =================================================================== --- llvm/lib/Transforms/Utils/CMakeLists.txt +++ llvm/lib/Transforms/Utils/CMakeLists.txt @@ -43,6 +43,7 @@ PromoteMemoryToRegister.cpp StripGCRelocates.cpp SSAUpdater.cpp + SSAUpdaterBulk.cpp SanitizerStats.cpp SimplifyCFG.cpp SimplifyIndVar.cpp Index: llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp =================================================================== --- /dev/null +++ llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp @@ -0,0 +1,175 @@ +//===- 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 "ssaupdater" + +/// 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) { + if (!Rewrites.count(Var)) + return false; + return Rewrites[Var].Defines.count(BB); +} + +// 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) { + Instruction *User = cast(U->getUser()); + + if (PHINode *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); + } + } +}