Index: include/llvm/Transforms/Utils/SSAUpdaterNew.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Utils/SSAUpdaterNew.h @@ -0,0 +1,118 @@ +//===-- SSAUpdaterNew.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 SSAUpdaterNew class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERNEW_H +#define LLVM_TRANSFORMS_UTILS_SSAUPDATERNEW_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include + +namespace llvm { + +class BasicBlock; +class Instruction; +class LoadInst; +template class ArrayRef; +template class SmallVectorImpl; +class PHINode; +class Type; +class Use; +class Value; + +/// \brief 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. +/// First, choose an unsigned int to represent your "variable". As long as you +/// are consistent, it doesn not matter which you choose. +/// Set the name and type of the "variable" using setName and setType. +/// Now, for each definition of the "variable" that already exists or you've +/// inserted, call writeVariable(Var, BB, Value). +/// For each place you want to know the variable to use (for example, to replace +/// a use), call readVariableBeforeDef(Var, BB) or readVariableAfterDef(Var, +/// BB), it will place phi nodes if necessary. +/// If you have multiple definitions in the same block, call the read/write +/// routines in program order. +/// For example, if before i have: +/// if (foo) +/// a = b + c +/// d = b + c +/// and i place a new copy in the else block to do PRE: +/// if (foo) +/// ifbb: +/// a = b + c +/// else +/// elsebb: +/// temp = b + c +/// mergebb: +/// d = b + c +/// I would call: +/// setType(0, a->getType()) +/// setName(0, "pretemp") +/// writeVariable(0, ifbb, a) +/// writeVariable(0, elsebb, temp) +/// and now to update d, i would call readVariableBeforeDef(0, mergebb), and it will +/// create a phi node and return it to me. +/// if i have a loop with a use as so: +// pred: +// def (A) +// loop: +// use(A) +// def(A) +// branch to either pred, loop +// i would call writevariable(0, pred, A) +// readvariablebeforedef(0, loop, A) to replace the use +// writevariable(0, pred, A) + + + + +class SSAUpdaterNew { + +private: + SmallVectorImpl *InsertedPHIs; + DenseMap, Value *> CurrentDef; + DenseSet> VisitedBlocks; + DenseMap CurrentType; + DenseMap CurrentName; + +public: + /// If InsertedPHIs is specified, it will be filled + /// in with all PHI Nodes created by rewriting. + explicit SSAUpdaterNew(SmallVectorImpl *InsertedPHIs = nullptr); + SSAUpdaterNew(const SSAUpdaterNew &) = delete; + SSAUpdaterNew &operator=(const SSAUpdaterNew &) = delete; + ~SSAUpdaterNew(); + + // Mark a definition point of variable Var, occuring in BasicBlock BB, with + // Value V. + void writeVariable(unsigned Var, BasicBlock *BB, Value *V); + // Get the definition of Var in BB, creating any phi nodes necessary to give a + // singular answer. + Value *readVariableAfterDef(unsigned Var, BasicBlock *); + // Set the type to be used for variable Var + void setType(unsigned Var, Type *Ty); + void setName(unsigned Var, StringRef Name); + Value *readVariableBeforeDef(unsigned Var, BasicBlock *); + +private: + Value *addPhiOperands(unsigned Var, PHINode *); +}; +} + +#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATER_H Index: lib/Transforms/Utils/CMakeLists.txt =================================================================== --- lib/Transforms/Utils/CMakeLists.txt +++ lib/Transforms/Utils/CMakeLists.txt @@ -40,6 +40,7 @@ PromoteMemoryToRegister.cpp StripGCRelocates.cpp SSAUpdater.cpp + SSAUpdaterNew.cpp SanitizerStats.cpp SimplifyCFG.cpp SimplifyIndVar.cpp Index: lib/Transforms/Utils/SSAUpdaterNew.cpp =================================================================== --- /dev/null +++ lib/Transforms/Utils/SSAUpdaterNew.cpp @@ -0,0 +1,123 @@ +//===- SSAUpdaterNew.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 SSAUpdaterNew class. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/SSAUpdaterNew.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/TinyPtrVector.h" +#include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DebugLoc.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/Use.h" +#include "llvm/IR/Value.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include +#include + +using namespace llvm; + +#define DEBUG_TYPE "SSAUpdaterNew" + +SSAUpdaterNew::SSAUpdaterNew(SmallVectorImpl *NewPHI) + : InsertedPHIs(NewPHI) {} + +SSAUpdaterNew::~SSAUpdaterNew() {} +void SSAUpdaterNew::setType(unsigned Var, Type *Ty) { CurrentType[Var] = Ty; } +void SSAUpdaterNew::setName(unsigned Var, StringRef Name) { + CurrentName[Var] = Name; +} + +void SSAUpdaterNew::writeVariable(unsigned Var, BasicBlock *BB, Value *V) { + CurrentDef[{Var, BB}] = V; +} + +Value *SSAUpdaterNew :: readVariableAfterDef(unsigned Var, BasicBlock *BB) { + auto CDI = CurrentDef.find({Var, BB}); + if (CDI != CurrentDef.end()) + return CDI->second; + return readVariableAfterDef(Var, BB); +} + +Value *SSAUpdaterNew::readVariableBeforeDef(unsigned Var, BasicBlock *BB) { + Value *Result; + + // Single predecessor case, just recurse + if (BasicBlock *Pred = BB->getSinglePredecessor()) { + Result = readVariableAfterDef(Var, Pred); + } else if (VisitedBlocks.count({Var, BB})) { + // We hit our node again, meaning we had a cycle, we must insert a phi + // node + Result = PHINode::Create(CurrentType.lookup(Var), 0, + CurrentName.lookup(Var), &BB->front()); + } else { + // Mark us visited so we can detect a cycle + VisitedBlocks.insert({Var, BB}); + Value *Same = nullptr; + bool AllSame = true; + + // Detect equal arguments or no arguments + for (auto *Pred : predecessors(BB)) { + Value *PredVal = readVariableAfterDef(Var, Pred); + if (PredVal == Same) + continue; + // See if we see ourselves, due to a self-cycle + if (CurrentDef.lookup({Var, BB}) == PredVal) + continue; + + // If we haven't set Same,set it out. Otherwise, the args are not all the + // same. + if (!Same) { + Same = PredVal; + } else { + Same = nullptr; + AllSame = false; + } + } + PHINode *Phi = dyn_cast_or_null(CurrentDef.lookup({Var, BB})); + // We never went through the loop, our phi is undefined + if (!Same && AllSame) { + Result = UndefValue::get(CurrentType.lookup(Var)); + Phi->replaceAllUsesWith(Result); + Phi->eraseFromParent(); + } else if (!AllSame) { + if (!Phi) + Phi = PHINode::Create(CurrentType.lookup(Var), 0, + CurrentName.lookup(Var), &BB->front()); + // This must be filled in by the recursive read + for (auto *Pred : predecessors(BB)) + Phi->addIncoming(CurrentDef.lookup({Var, Pred}), Pred); + Result = Phi; + } else { + assert(Same && AllSame && "Should have set both!"); + Result = Same; + Phi->replaceAllUsesWith(Same); + Phi->eraseFromParent(); + } + if (isa(Result)) + InsertedPHIs->push_back(Result); + VisitedBlocks.erase({Var, BB}); + } + writeVariable(Var, BB, Result); + return Result; +}