From 738fc4e15b38e4cacda9ddd9b8352d448587ea9c Mon Sep 17 00:00:00 2001 From: DeLesley Hutchins Date: Tue, 15 Apr 2014 23:23:19 +0000 Subject: [PATCH] Thread Safety Analysis: rewrite SSA pass to use the new SExpr and CFG traversal system. The new pass is still undergoing testing; no change in functionality. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@206338 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Analysis/Analyses/ThreadSafetyCommon.h | 202 ++++++--- .../clang/Analysis/Analyses/ThreadSafetyTIL.h | 47 ++- .../Analysis/Analyses/ThreadSafetyTraverse.h | 49 ++- .../Analysis/Analyses/ThreadSafetyUtil.h | 149 ++++++- lib/Analysis/ThreadSafetyCommon.cpp | 385 ++++++++++++++---- 5 files changed, 659 insertions(+), 173 deletions(-) diff --git a/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/include/clang/Analysis/Analyses/ThreadSafetyCommon.h index 5e0f40ea84..83a00d3806 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyCommon.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyCommon.h @@ -33,32 +33,53 @@ namespace clang { namespace threadSafety { -// CFG traversal uses templates instead of virtual function dispatch. Visitors -// must implement the following functions: -// -// Enter the CFG for Decl D, and perform any initial setup operations. -// void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {} -// -// Enter a CFGBlock. -// void enterCFGBlock(const CFGBlock *B) {} -// -// Process an ordinary statement. -// void handleStatement(const Stmt *S) {} -// -// Process a destructor call -// void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} -// -// Process a successor edge. -// void handleSuccessor(const CFGBlock *Succ) {} -// -// Process a successor back edge to a previously visited block. -// void handleSuccessorBackEdge(const CFGBlock *Succ) {} -// -// Leave a CFGBlock. -// void exitCFGBlock(const CFGBlock *B) {} -// -// Leave the CFG, and perform any final cleanup operations. -// void exitCFG(const CFGBlock *Last) {} +// This class defines the interface of a clang CFG Visitor. +// CFGWalker will invoke the following methods. +// Note that methods are not virtual; the visitor is templatized. +class CFGVisitor { + // Enter the CFG for Decl D, and perform any initial setup operations. + void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {} + + // Enter a CFGBlock. + void enterCFGBlock(const CFGBlock *B) {} + + // Returns true if this visitor implements handlePredecessor + bool visitPredecessors() { return true; } + + // Process a predecessor edge. + void handlePredecessor(const CFGBlock *Pred) {} + + // Process a successor back edge to a previously visited block. + void handlePredecessorBackEdge(const CFGBlock *Pred) {} + + // Called just before processing statements. + void enterCFGBlockBody(const CFGBlock *B) {} + + // Process an ordinary statement. + void handleStatement(const Stmt *S) {} + + // Process a destructor call + void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} + + // Called after all statements have been handled. + void exitCFGBlockBody(const CFGBlock *B) {} + + // Return true + bool visitSuccessors() { return true; } + + // Process a successor edge. + void handleSuccessor(const CFGBlock *Succ) {} + + // Process a successor back edge to a previously visited block. + void handleSuccessorBackEdge(const CFGBlock *Succ) {} + + // Leave a CFGBlock. + void exitCFGBlock(const CFGBlock *B) {} + + // Leave the CFG, and perform any final cleanup operations. + void exitCFG(const CFGBlock *Last) {} +}; + // Walks the clang CFG, and invokes methods on a given CFGVisitor. class CFGWalker { @@ -97,6 +118,25 @@ public: V.enterCFGBlock(CurrBlock); + // Process predecessors + if (V.visitPredecessors()) { + // Process successors + for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(), + SE = CurrBlock->pred_end(); + SI != SE; ++SI) { + if (*SI == nullptr) + continue; + + if (!VisitedBlocks.alreadySet(*SI)) { + V.handlePredecessorBackEdge(*SI); + continue; + } + V.handlePredecessor(*SI); + } + } + + V.enterCFGBlockBody(CurrBlock); + // Process statements for (const auto &BI : *CurrBlock) { switch (BI.getKind()) { @@ -117,18 +157,23 @@ public: } } + V.exitCFGBlockBody(CurrBlock); + // Process successors - for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), - SE = CurrBlock->succ_end(); - SI != SE; ++SI) { - if (*SI == nullptr) - continue; - - if (VisitedBlocks.alreadySet(*SI)) { - V.handleSuccessorBackEdge(*SI); - continue; + if (V.visitSuccessors()) { + // Process successors + for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), + SE = CurrBlock->succ_end(); + SI != SE; ++SI) { + if (*SI == nullptr) + continue; + + if (VisitedBlocks.alreadySet(*SI)) { + V.handleSuccessorBackEdge(*SI); + continue; + } + V.handleSuccessor(*SI); } - V.handleSuccessor(*SI); } V.exitCFGBlock(CurrBlock); @@ -174,15 +219,16 @@ public: {} }; - til::SExpr *lookupStmt(const Stmt *S); - void insertStmt(const Stmt *S, til::Variable *V); - // Translate a clang statement or expression to a TIL expression. // Also performs substitution of variables; Ctx provides the context. // Dispatches on the type of S. til::SExpr *translate(const Stmt *S, CallingContext *Ctx); + til::SCFG *buildCFG(CFGWalker &Walker); + + til::SExpr *lookupStmt(const Stmt *S); + til::SCFG *getCFG() const { return Scfg; } -protected: +private: til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE, CallingContext *Ctx) ; til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx); @@ -204,24 +250,86 @@ protected: til::SExpr *translateBinaryConditionalOperator( const BinaryConditionalOperator *C, CallingContext *Ctx); + til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); + +private: + // Used for looking the index of a name. + typedef llvm::DenseMap NameIndexMap; + + // Used for looking up the current SSA variable for a name, by index. + typedef CopyOnWriteVector > + NameVarMap; + + struct BlockInfo { + NameVarMap ExitMap; + bool HasBackEdges = false; + unsigned SuccessorsToProcess = 0; + }; + + // We implement the CFGVisitor API + friend class CFGWalker; + + void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First); + void enterCFGBlock(const CFGBlock *B); + bool visitPredecessors() { return true; } + void handlePredecessor(const CFGBlock *Pred); + void handlePredecessorBackEdge(const CFGBlock *Pred); + void enterCFGBlockBody(const CFGBlock *B); + void handleStatement(const Stmt *S); + void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD); + void exitCFGBlockBody(const CFGBlock *B); + bool visitSuccessors() { return true; } + void handleSuccessor(const CFGBlock *Succ); + void handleSuccessorBackEdge(const CFGBlock *Succ); + void exitCFGBlock(const CFGBlock *B); + void exitCFG(const CFGBlock *Last); + + void insertStmt(const Stmt *S, til::Variable *V); + til::SExpr *addStatement(til::SExpr *E, const Stmt *S, const ValueDecl *VD=0); + til::SExpr *lookupVarDecl(const ValueDecl *VD); + til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E); + til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E); + + void mergeEntryMap(NameVarMap Map); public: - SExprBuilder(til::MemRegionRef A, StatementMap *SM = nullptr) - : Arena(A), SMap(SM), SelfVar(nullptr), CurrentBlock(nullptr) { + SExprBuilder(til::MemRegionRef A) + : Arena(A), SelfVar(nullptr), Scfg(nullptr), CallCtx(nullptr), + CurrentBB(nullptr), CurrentBlockID(0), CurrentVarID(0), + CurrentArgIndex(0) + { // FIXME: we don't always have a self-variable. SelfVar = new (Arena) til::Variable(til::Variable::VK_SFun); } -protected: + ~SExprBuilder() { + if (CallCtx) + delete CallCtx; + } + +private: til::MemRegionRef Arena; - StatementMap *SMap; // Map from Stmt to TIL Variables - til::Variable *SelfVar; // Variable to use for 'this'. May be null. - til::BasicBlock* CurrentBlock; // Current basic block. May be null. + til::Variable *SelfVar; // Variable to use for 'this'. May be null. + til::SCFG *Scfg; + + StatementMap SMap; // Map from Stmt to TIL Variables + NameIndexMap IdxMap; // Indices of clang local vars. + std::vector BlockMap; // Map from clang to til BBs. + std::vector BBInfo; // Extra information per BB. + // Indexed by clang BlockID. + SExprBuilder::CallingContext *CallCtx; // Root calling context + + NameVarMap CurrentNameMap; + til::BasicBlock *CurrentBB; + BlockInfo *CurrentBlockInfo; + unsigned CurrentBlockID; + unsigned CurrentVarID; + unsigned CurrentArgIndex; }; // Dump an SCFG to llvm::errs(). -void printSCFG(CFGWalker &walker); +void printSCFG(CFGWalker &Walker); } // end namespace threadSafety diff --git a/include/clang/Analysis/Analyses/ThreadSafetyTIL.h b/include/clang/Analysis/Analyses/ThreadSafetyTIL.h index eaa779faa8..eaf9a0d3d2 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyTIL.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyTIL.h @@ -199,7 +199,7 @@ public: // These are defined after SExprRef contructor, below inline Variable(VariableKind K, SExpr *D = nullptr, const clang::ValueDecl *Cvd = nullptr); - inline Variable(const clang::ValueDecl *Cvd, SExpr *D = nullptr); + inline Variable(SExpr *D = nullptr, const clang::ValueDecl *Cvd = nullptr); inline Variable(const Variable &Vd, SExpr *D); VariableKind kind() const { return static_cast(Flags); } @@ -220,6 +220,7 @@ public: BlockID = static_cast(Bid); Id = static_cast(I); } + void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; } template typename V::R_SExpr traverse(V &Visitor) { // This routine is only called for variable references. @@ -353,7 +354,7 @@ Variable::Variable(VariableKind K, SExpr *D, const clang::ValueDecl *Cvd) Flags = K; } -Variable::Variable(const clang::ValueDecl *Cvd, SExpr *D) +Variable::Variable(SExpr *D, const clang::ValueDecl *Cvd) : SExpr(COP_Variable), Definition(D), Cvdecl(Cvd), BlockID(0), Id(0), NumUses(0) { Flags = VK_Let; @@ -935,6 +936,8 @@ private: SExprRef Expr0; }; + + class BasicBlock; // An SCFG is a control-flow graph. It consists of a set of basic blocks, each @@ -998,13 +1001,16 @@ public: BasicBlock(MemRegionRef A, unsigned Nargs, unsigned Nins, SExpr *Term = nullptr) - : BlockID(0), Parent(nullptr), Args(A, Nargs), Instrs(A, Nins), - Terminator(Term) {} + : BlockID(0), Parent(nullptr), NumPredecessors(0), + Args(A, Nargs), Instrs(A, Nins), Terminator(Term) {} BasicBlock(const BasicBlock &B, VarArray &&As, VarArray &&Is, SExpr *T) - : BlockID(0), Parent(nullptr), Args(std::move(As)), Instrs(std::move(Is)), - Terminator(T) {} + : BlockID(0), Parent(nullptr), NumPredecessors(B.NumPredecessors), + Args(std::move(As)), Instrs(std::move(Is)), Terminator(T) + {} unsigned blockID() const { return BlockID; } + unsigned numPredecessors() const { return NumPredecessors; } + const BasicBlock *parent() const { return Parent; } BasicBlock *parent() { return Parent; } @@ -1017,8 +1023,9 @@ public: const SExpr *terminator() const { return Terminator.get(); } SExpr *terminator() { return Terminator.get(); } - void setParent(BasicBlock *P) { Parent = P; } void setBlockID(unsigned i) { BlockID = i; } + void setParent(BasicBlock *P) { Parent = P; } + void setNumPredecessors(unsigned NP) { NumPredecessors = NP; } void setTerminator(SExpr *E) { Terminator.reset(E); } void addArgument(Variable *V) { Args.push_back(V); } void addInstr(Variable *V) { Args.push_back(V); } @@ -1057,9 +1064,10 @@ private: friend class SCFG; unsigned BlockID; - BasicBlock *Parent; // The parent block is the enclosing lexical scope. - // The parent dominates this block. - VarArray Args; // Phi nodes + BasicBlock *Parent; // The parent block is the enclosing lexical scope. + // The parent dominates this block. + unsigned NumPredecessors; // Number of blocks which jump to this one. + VarArray Args; // Phi nodes. One argument per predecessor. VarArray Instrs; SExprRef Terminator; }; @@ -1100,8 +1108,8 @@ public: return Visitor.reducePhi(*this, Nvs); } - template typename C::CType compare(Phi *E, C &Cmp) { - // TODO -- implement CFG comparisons + template typename C::CType compare(Phi* E, C &Cmp) { + // TODO: implement CFG comparisons return Cmp.comparePointers(this, E); } @@ -1146,17 +1154,26 @@ public: static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } Branch(SExpr *C, BasicBlock *T, BasicBlock *E) - : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E) {} + : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E), + ThenIndex(0), ElseIndex(0) + {} Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) - : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E) {} + : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E), + ThenIndex(0), ElseIndex(0) + {} const SExpr *condition() const { return Condition; } SExpr *condition() { return Condition; } + const BasicBlock *thenBlock() const { return ThenBlock; } BasicBlock *thenBlock() { return ThenBlock; } + const BasicBlock *elseBlock() const { return ElseBlock; } BasicBlock *elseBlock() { return ElseBlock; } + unsigned thenIndex() const { return ThenIndex; } + unsigned elseIndex() const { return ElseIndex; } + template typename V::R_SExpr traverse(V &Visitor) { typename V::R_SExpr Nc = Visitor.traverse(Condition); BasicBlock *Ntb = Visitor.reduceBasicBlockRef(ThenBlock); @@ -1173,6 +1190,8 @@ private: SExpr *Condition; BasicBlock *ThenBlock; BasicBlock *ElseBlock; + unsigned ThenIndex; + unsigned ElseIndex; }; diff --git a/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h b/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h index 8b13af75ef..603c5f556c 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h @@ -409,6 +409,15 @@ protected: SS << "\n"; } + void printBlockLabel(StreamType & SS, BasicBlock *BB, unsigned index) { + if (!BB) { + SS << "BB_null"; + return; + } + SS << "BB_"; + SS << BB->blockID(); + } + // TODO: further distinguish between binary operations. static const unsigned Prec_Atom = 0; static const unsigned Prec_Postfix = 1; @@ -560,9 +569,11 @@ protected: void printSApply(SApply *E, StreamType &SS) { self()->printSExpr(E->sfun(), SS, Prec_Postfix); - SS << "@("; - self()->printSExpr(E->arg(), SS, Prec_MAX); - SS << ")"; + if (E->isDelegation()) { + SS << "@("; + self()->printSExpr(E->arg(), SS, Prec_MAX); + SS << ")"; + } } void printProject(Project *E, StreamType &SS) { @@ -584,7 +595,7 @@ protected: } void printAlloc(Alloc *E, StreamType &SS) { - SS << "#alloc "; + SS << "new "; self()->printSExpr(E->dataType(), SS, Prec_Other-1); } @@ -595,7 +606,7 @@ protected: void printStore(Store *E, StreamType &SS) { self()->printSExpr(E->destination(), SS, Prec_Other-1); - SS << " = "; + SS << " := "; self()->printSExpr(E->source(), SS, Prec_Other-1); } @@ -628,9 +639,11 @@ protected: newline(SS); } for (auto I : BBI->instructions()) { - SS << "let "; - self()->printVariable(I, SS); - SS << " = "; + if (I->definition()->opcode() != COP_Store) { + SS << "let "; + self()->printVariable(I, SS); + SS << " = "; + } self()->printSExpr(I->definition(), SS, Prec_MAX); SS << ";"; newline(SS); @@ -648,31 +661,29 @@ protected: } void printPhi(Phi *E, StreamType &SS) { - SS << "#phi("; + SS << "phi("; unsigned i = 0; for (auto V : E->values()) { - ++i; if (i > 0) SS << ", "; self()->printSExpr(V, SS, Prec_MAX); + ++i; } SS << ")"; } void printGoto(Goto *E, StreamType &SS) { - SS << "#goto BB_"; - SS << E->targetBlock()->blockID(); - SS << ":"; - SS << E->index(); + SS << "goto "; + printBlockLabel(SS, E->targetBlock(), E->index()); } void printBranch(Branch *E, StreamType &SS) { - SS << "#branch ("; + SS << "branch ("; self()->printSExpr(E->condition(), SS, Prec_MAX); - SS << ") BB_"; - SS << E->thenBlock()->blockID(); - SS << " BB_"; - SS << E->elseBlock()->blockID(); + SS << ") "; + printBlockLabel(SS, E->thenBlock(), E->thenIndex()); + SS << " "; + printBlockLabel(SS, E->elseBlock(), E->elseIndex()); } }; diff --git a/include/clang/Analysis/Analyses/ThreadSafetyUtil.h b/include/clang/Analysis/Analyses/ThreadSafetyUtil.h index f565ece8d6..996e81d1b5 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyUtil.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyUtil.h @@ -78,7 +78,7 @@ template class SimpleArray { public: SimpleArray() : Data(nullptr), Size(0), Capacity(0) {} SimpleArray(T *Dat, size_t Cp, size_t Sz = 0) - : Data(Dat), Size(0), Capacity(Cp) {} + : Data(Dat), Size(Sz), Capacity(Cp) {} SimpleArray(MemRegionRef A, size_t Cp) : Data(A.allocateT(Cp)), Size(0), Capacity(Cp) {} SimpleArray(SimpleArray &&A) @@ -101,8 +101,14 @@ public: size_t size() const { return Size; } size_t capacity() const { return Capacity; } - T &operator[](unsigned I) { return Data[I]; } - const T &operator[](unsigned I) const { return Data[I]; } + T &operator[](unsigned i) { + assert(i < Sz && "Array index out of bounds."); + return Data[i]; + } + const T &operator[](unsigned i) const { + assert(i < Size && "Array index out of bounds."); + return Data[i]; + } iterator begin() { return Data; } iterator end() { return Data + Size; } @@ -115,6 +121,14 @@ public: Data[Size++] = Elem; } + void setValues(unsigned Sz, const T& C) { + assert(Sz < Capacity); + Size = Sz; + for (unsigned i = 0; i < Sz; ++i) { + Data[i] = C; + } + } + template unsigned append(Iter I, Iter E) { size_t Osz = Size; size_t J = Osz; @@ -132,8 +146,135 @@ private: size_t Capacity; }; - } // end namespace til + + +// A copy on write vector. +// The vector can be in one of three states: +// * invalid -- no operations are permitted. +// * read-only -- read operations are permitted. +// * writable -- read and write operations are permitted. +// The init(), destroy(), and makeWritable() methods will change state. +template +class CopyOnWriteVector { +private: + class VectorData { + public: + VectorData() : NumRefs(1) { } + VectorData(const VectorData &VD) : NumRefs(1), Vect(VD.Vect) { } + + unsigned NumRefs; + std::vector Vect; + }; + +public: + CopyOnWriteVector() : Data(0) { } + CopyOnWriteVector(const CopyOnWriteVector &V) = delete; + CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { + V.Data = 0; + } + ~CopyOnWriteVector() { + destroy(); + } + + // Returns true if this holds a valid vector. + bool valid() { return Data; } + + // Returns true if this vector is writable. + bool writable() { return Data && Data->NumRefs == 1; } + + // If this vector is not valid, initialize it to a valid vector. + void init() { + if (!Data) { + Data = new VectorData(); + } + } + + // Destroy this vector; thus making it invalid. + void destroy() { + if (!Data) + return; + if (Data->NumRefs <= 1) + delete Data; + else + --Data->NumRefs; + Data = 0; + } + + // Make this vector writable, creating a copy if needed. + void makeWritable() { + if (!Data) { + Data = new VectorData(); + return; + } + if (Data->NumRefs == 1) + return; // already writeable. + --Data->NumRefs; + Data = new VectorData(*Data); + } + + // Create a lazy copy of this vector. + CopyOnWriteVector clone() { return CopyOnWriteVector(Data); } + + // No copy constructor or copy assignment. Use clone() with move assignment. + void operator=(const CopyOnWriteVector &V) = delete; + + void operator=(CopyOnWriteVector &&V) { + destroy(); + Data = V.Data; + V.Data = 0; + } + + typedef typename std::vector::const_iterator iterator; + + const std::vector &elements() const { return Data->Vect; } + + iterator begin() const { return elements().cbegin(); } + iterator end() const { return elements().cend(); } + + const T& operator[](unsigned i) const { return elements()[i]; } + + unsigned size() const { return Data ? elements().size() : 0; } + + // Return true if V and this vector refer to the same data. + bool sameAs(const CopyOnWriteVector& V) { return Data == V.Data; } + + // Clear vector. The vector must be writable. + void clear() { + assert(writable() && "Vector is not writable!"); + Data->Vect.clear(); + } + + // Push a new element onto the end. The vector must be writable. + void push_back(const T& Elem) { + assert(writable() && "Vector is not writable!"); + Data->Vect.push_back(Elem); + } + + // Gets a mutable reference to the element at index(i). + // The vector must be writable. + T& elem(unsigned i) { + assert(writable() && "Vector is not writable!"); + return Data->Vect[i]; + } + + // Drops elements from the back until the vector has size i. + void downsize(unsigned i) { + assert(writable() && "Vector is not writable!"); + Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end()); + } + +private: + CopyOnWriteVector(VectorData *D) : Data(D) { + if (!Data) + return; + ++Data->NumRefs; + } + + VectorData *Data; +}; + + } // end namespace threadSafety } // end namespace clang diff --git a/lib/Analysis/ThreadSafetyCommon.cpp b/lib/Analysis/ThreadSafetyCommon.cpp index 7413a3373c..2c90b2a4be 100644 --- a/lib/Analysis/ThreadSafetyCommon.cpp +++ b/lib/Analysis/ThreadSafetyCommon.cpp @@ -28,6 +28,8 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" +#include +#include #include @@ -38,16 +40,20 @@ typedef SExprBuilder::CallingContext CallingContext; til::SExpr *SExprBuilder::lookupStmt(const Stmt *S) { - if (!SMap) - return nullptr; - auto It = SMap->find(S); - if (It != SMap->end()) + auto It = SMap.find(S); + if (It != SMap.end()) return It->second; return nullptr; } void SExprBuilder::insertStmt(const Stmt *S, til::Variable *V) { - SMap->insert(std::make_pair(S, V)); + SMap.insert(std::make_pair(S, V)); +} + + +til::SCFG *SExprBuilder::buildCFG(CFGWalker &Walker) { + Walker.walk(*this); + return Scfg; } @@ -55,6 +61,9 @@ void SExprBuilder::insertStmt(const Stmt *S, til::Variable *V) { // Also performs substitution of variables; Ctx provides the context. // Dispatches on the type of S. til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) { + if (!S) + return nullptr; + // Check if S has already been translated and cached. // This handles the lookup of SSA names for DeclRefExprs here. if (til::SExpr *E = lookupStmt(S)) @@ -105,6 +114,9 @@ til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) { case Stmt::StringLiteralClass: case Stmt::ObjCStringLiteralClass: return new (Arena) til::Literal(cast(S)); + + case Stmt::DeclStmtClass: + return translateDeclStmt(cast(S), Ctx); default: break; } @@ -209,6 +221,7 @@ til::SExpr *SExprBuilder::translateUnaryOperator(const UnaryOperator *UO, return new (Arena) til::Undefined(UO); } + til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO, CallingContext *Ctx) { switch (BO->getOpcode()) { @@ -238,10 +251,17 @@ til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO, til::BinaryOp(BO->getOpcode(), translate(BO->getLHS(), Ctx), translate(BO->getRHS(), Ctx)); - case BO_Assign: - return new (Arena) - til::Store(translate(BO->getLHS(), Ctx), translate(BO->getRHS(), Ctx)); - + case BO_Assign: { + const Expr *LHS = BO->getLHS(); + if (const DeclRefExpr *DRE = dyn_cast(LHS)) { + const Expr *RHS = BO->getRHS(); + til::SExpr *E1 = translate(RHS, Ctx); + return updateVarDecl(DRE->getDecl(), E1); + } + til::SExpr *E0 = translate(LHS, Ctx); + til::SExpr *E1 = translate(BO->getRHS(), Ctx); + return new (Arena) til::Store(E0, E1); + } case BO_MulAssign: case BO_DivAssign: case BO_RemAssign: @@ -265,145 +285,332 @@ til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO, til::SExpr *SExprBuilder::translateCastExpr(const CastExpr *CE, CallingContext *Ctx) { - til::SExpr *E0 = translate(CE->getSubExpr(), Ctx); - clang::CastKind K = CE->getCastKind(); switch (K) { - case CK_LValueToRValue: + case CK_LValueToRValue: { + if (const DeclRefExpr *DRE = dyn_cast(CE->getSubExpr())) { + til::SExpr *E0 = lookupVarDecl(DRE->getDecl()); + if (E0) + return E0; + } + til::SExpr *E0 = translate(CE->getSubExpr(), Ctx); return new (Arena) til::Load(E0); - + } case CK_NoOp: case CK_DerivedToBase: case CK_UncheckedDerivedToBase: case CK_ArrayToPointerDecay: - case CK_FunctionToPointerDecay: + case CK_FunctionToPointerDecay: { + til::SExpr *E0 = translate(CE->getSubExpr(), Ctx); return E0; - - default: + } + default: { + til::SExpr *E0 = translate(CE->getSubExpr(), Ctx); return new (Arena) til::Cast(K, E0); } + } } + til::SExpr * SExprBuilder::translateArraySubscriptExpr(const ArraySubscriptExpr *E, CallingContext *Ctx) { return new (Arena) til::Undefined(E); } + til::SExpr * SExprBuilder::translateConditionalOperator(const ConditionalOperator *C, CallingContext *Ctx) { return new (Arena) til::Undefined(C); } + til::SExpr *SExprBuilder::translateBinaryConditionalOperator( const BinaryConditionalOperator *C, CallingContext *Ctx) { return new (Arena) til::Undefined(C); } +til::SExpr * +SExprBuilder::translateDeclStmt(const DeclStmt *S, CallingContext *Ctx) { + DeclGroupRef DGrp = S->getDeclGroup(); + for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { + if (VarDecl *VD = dyn_cast_or_null(*I)) { + Expr *E = VD->getInit(); + til::SExpr* SE = translate(E, Ctx); + + // Add local variables with trivial type to the variable map + QualType T = VD->getType(); + if (T.isTrivialType(VD->getASTContext())) { + return addVarDecl(VD, SE); + } + else { + // TODO: add alloca + } + } + } + return nullptr; +} -// Build a complete SCFG from a clang CFG. -class SCFGBuilder { - class BBInfo { - }; +// If (E) is non-trivial, then add it to the current basic block, and +// update the statement map so that S refers to E. Returns a new variable +// that refers to E. +// If E is trivial returns E. +til::SExpr *SExprBuilder::addStatement(til::SExpr* E, const Stmt *S, + const ValueDecl *VD) { + if (!E) + return nullptr; + if (til::ThreadSafetyTIL::isTrivial(E)) + return E; - void addStatement(til::SExpr* E, const Stmt *S) { - if (!E) - return; - if (til::ThreadSafetyTIL::isTrivial(E)) - return; + til::Variable *V = new (Arena) til::Variable(E, VD); + V->setID(CurrentBlockID, CurrentVarID++); + CurrentBB->addInstr(V); + if (S) + insertStmt(S, V); + return V; +} - til::Variable *V = new (Arena) til::Variable(til::Variable::VK_Let, E); - V->setID(CurrentBlockID, CurrentVarID++); - CurrentBB->addInstr(V); - if (S) - BuildEx.insertStmt(S, V); - } -public: - // Enter the CFG for Decl D, and perform any initial setup operations. - void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) { - Scfg = new (Arena) til::SCFG(Arena, Cfg->getNumBlockIDs()); - CallCtx = new SExprBuilder::CallingContext(D); - } +// Returns the current value of VD, if known, and nullptr otherwise. +til::SExpr *SExprBuilder::lookupVarDecl(const ValueDecl *VD) { + auto It = IdxMap.find(VD); + if (It != IdxMap.end()) + return CurrentNameMap[It->second].second; + return nullptr; +} + - // Enter a CFGBlock. - void enterCFGBlock(const CFGBlock *B) { - CurrentBB = new (Arena) til::BasicBlock(Arena, 0, B->size()); - CurrentBB->setBlockID(CurrentBlockID); - CurrentVarID = 0; - Scfg->add(CurrentBB); +// if E is a til::Variable, update its clangDecl. +inline void maybeUpdateVD(til::SExpr *E, const ValueDecl *VD) { + if (!E) + return; + if (til::Variable *V = dyn_cast(E)) { + if (!V->clangDecl()) + V->setClangDecl(VD); } +} + +// Adds a new variable declaration. +til::SExpr *SExprBuilder::addVarDecl(const ValueDecl *VD, til::SExpr *E) { + maybeUpdateVD(E, VD); + IdxMap.insert(std::make_pair(VD, CurrentNameMap.size())); + CurrentNameMap.makeWritable(); + CurrentNameMap.push_back(std::make_pair(VD, E)); + return E; +} - // Process an ordinary statement. - void handleStatement(const Stmt *S) { - til::SExpr *E = BuildEx.translate(S, CallCtx); - addStatement(E, S); + +// Updates a current variable declaration. (E.g. by assignment) +til::SExpr *SExprBuilder::updateVarDecl(const ValueDecl *VD, til::SExpr *E) { + maybeUpdateVD(E, VD); + auto It = IdxMap.find(VD); + if (It == IdxMap.end()) { + til::SExpr *Ptr = new (Arena) til::LiteralPtr(VD); + til::SExpr *St = new (Arena) til::Store(Ptr, E); + return St; } + CurrentNameMap.makeWritable(); + CurrentNameMap.elem(It->second).second = E; + return E; +} + - // Process a destructor call - void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) { - til::SExpr *Sf = new (Arena) til::LiteralPtr(VD); - til::SExpr *Dr = new (Arena) til::LiteralPtr(DD); - til::SExpr *Ap = new (Arena) til::Apply(Dr, Sf); - til::SExpr *E = new (Arena) til::Call(Ap); - addStatement(E, nullptr); +// Merge values from Map into the current entry map. +void SExprBuilder::mergeEntryMap(NameVarMap Map) { + assert(CurrentBlockInfo && "Not processing a block!"); + + if (!CurrentNameMap.valid()) { + // Steal Map, using copy-on-write. + CurrentNameMap = std::move(Map); + return; } + if (CurrentNameMap.sameAs(Map)) + return; // Easy merge: maps from different predecessors are unchanged. + + unsigned ESz = CurrentNameMap.size(); + unsigned MSz = Map.size(); + unsigned Sz = std::max(ESz, MSz); + bool W = CurrentNameMap.writable(); + for (unsigned i=0; i(CurrentNameMap[i].second); + if (V && V->getBlockID() == CurrentBB->blockID()) { + // We already have a Phi node, so add the new variable. + til::Phi *Ph = dyn_cast(V->definition()); + assert(Ph && "Expecting Phi node."); + Ph->values()[CurrentArgIndex] = Map[i].second; + } + else { + if (!W) + CurrentNameMap.makeWritable(); + unsigned NPreds = CurrentBB->numPredecessors(); + assert(CurrentArgIndex > 0 && CurrentArgIndex < NPreds); + + // Make a new phi node. All phi args up to the current index must + // be the same, and equal to the current NameMap value. + auto *Ph = new (Arena) til::Phi(Arena, NPreds); + Ph->values().setValues(NPreds, nullptr); + for (unsigned PIdx = 0; PIdx < CurrentArgIndex; ++PIdx) + Ph->values()[PIdx] = CurrentNameMap[i].second; + Ph->values()[CurrentArgIndex] = Map[i].second; + + // Add phi node to current basic block. + auto *Var = new (Arena) til::Variable(Ph, CurrentNameMap[i].first); + Var->setID(CurrentBlockID, CurrentVarID++); + CurrentBB->addArgument(Var); + CurrentNameMap.elem(i).second = Var; + } + } + } + if (ESz > MSz) { + if (!W) + CurrentNameMap.makeWritable(); + CurrentNameMap.downsize(Map.size()); + } +} + - // Process a successor edge. - void handleSuccessor(const CFGBlock *Succ) {} - // Process a successor back edge to a previously visited block. - void handleSuccessorBackEdge(const CFGBlock *Succ) {} +void SExprBuilder::enterCFG(CFG *Cfg, const NamedDecl *D, + const CFGBlock *First) { + // Perform initial setup operations. + unsigned NBlocks = Cfg->getNumBlockIDs(); + Scfg = new (Arena) til::SCFG(Arena, NBlocks); - // Leave a CFGBlock. - void exitCFGBlock(const CFGBlock *B) { - CurrentBlockID++; - CurrentBB = 0; + // allocate all basic blocks immediately, to handle forward references. + BlockMap.reserve(NBlocks); + BBInfo.resize(NBlocks); + for (auto *B : *Cfg) { + auto *BB = new (Arena) til::BasicBlock(Arena, 0, B->size()); + BlockMap.push_back(BB); } + CallCtx = new SExprBuilder::CallingContext(D); +} + + + +void SExprBuilder::enterCFGBlock(const CFGBlock *B) { + // Intialize TIL basic block and add it to the CFG. + CurrentBB = BlockMap[B->getBlockID()]; + CurrentBB->setBlockID(CurrentBlockID); + CurrentBB->setNumPredecessors(B->pred_size()); + Scfg->add(CurrentBB); + + CurrentBlockInfo = &BBInfo[B->getBlockID()]; + CurrentVarID = 0; + CurrentArgIndex = 0; + + assert(!CurrentNameMap.valid() && "CurrentNameMap already initialized."); +} + + +void SExprBuilder::handlePredecessor(const CFGBlock *Pred) { + // Compute CurrentNameMap on entry from ExitMaps of predecessors + + BlockInfo *PredInfo = &BBInfo[Pred->getBlockID()]; + assert(PredInfo->SuccessorsToProcess > 0); + + if (--PredInfo->SuccessorsToProcess == 0) + mergeEntryMap(std::move(PredInfo->ExitMap)); + else + mergeEntryMap(PredInfo->ExitMap.clone()); + + ++CurrentArgIndex; +} + + +void SExprBuilder::handlePredecessorBackEdge(const CFGBlock *Pred) { + CurrentBlockInfo->HasBackEdges = true; +} + - // Leave the CFG, and perform any final cleanup operations. - void exitCFG(const CFGBlock *Last) { - delete CallCtx; - CallCtx = nullptr; +void SExprBuilder::enterCFGBlockBody(const CFGBlock *B) { } + + +void SExprBuilder::handleStatement(const Stmt *S) { + til::SExpr *E = translate(S, CallCtx); + addStatement(E, S); +} + + +void SExprBuilder::handleDestructorCall(const VarDecl *VD, + const CXXDestructorDecl *DD) { + til::SExpr *Sf = new (Arena) til::LiteralPtr(VD); + til::SExpr *Dr = new (Arena) til::LiteralPtr(DD); + til::SExpr *Ap = new (Arena) til::Apply(Dr, Sf); + til::SExpr *E = new (Arena) til::Call(Ap); + addStatement(E, nullptr); +} + + + +void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) { + unsigned N = B->succ_size(); + auto It = B->succ_begin(); + if (N == 1) { + til::BasicBlock *BB = *It ? BlockMap[(*It)->getBlockID()] : nullptr; + // TODO: set index + til::SExpr *Tm = new (Arena) til::Goto(BB, 0); + CurrentBB->setTerminator(Tm); } + else if (N == 2) { + til::SExpr *C = translate(B->getTerminatorCondition(true), CallCtx); + til::BasicBlock *BB1 = *It ? BlockMap[(*It)->getBlockID()] : nullptr; + ++It; + til::BasicBlock *BB2 = *It ? BlockMap[(*It)->getBlockID()] : nullptr; + // TODO: set conditional, set index + til::SExpr *Tm = new (Arena) til::Branch(C, BB1, BB2); + CurrentBB->setTerminator(Tm); + } +} - SCFGBuilder(til::MemRegionRef A) - : Arena(A), Scfg(nullptr), CurrentBB(nullptr), CurrentBlockID(0), - CurrentVarID(0), CallCtx(nullptr), - SMap(new SExprBuilder::StatementMap()), BuildEx(A, SMap) {} - ~SCFGBuilder() { delete SMap; } - til::SCFG *getCFG() const { return Scfg; } +void SExprBuilder::handleSuccessor(const CFGBlock *Succ) { + ++CurrentBlockInfo->SuccessorsToProcess; +} -private: - til::MemRegionRef Arena; - til::SCFG *Scfg; - til::BasicBlock *CurrentBB; - unsigned CurrentBlockID; - unsigned CurrentVarID; - SExprBuilder::CallingContext *CallCtx; - SExprBuilder::StatementMap *SMap; - SExprBuilder BuildEx; -}; +void SExprBuilder::handleSuccessorBackEdge(const CFGBlock *Succ) { + +} + + +void SExprBuilder::exitCFGBlock(const CFGBlock *B) { + CurrentBlockInfo->ExitMap = std::move(CurrentNameMap); + CurrentBlockID++; + CurrentBB = nullptr; + CurrentBlockInfo = nullptr; +} + + +void SExprBuilder::exitCFG(const CFGBlock *Last) { + CurrentBlockID = 0; + CurrentVarID = 0; + CurrentArgIndex = 0; +} -class LLVMPrinter : - public til::PrettyPrinter { +class LLVMPrinter : public til::PrettyPrinter { }; -void printSCFG(CFGWalker &walker) { +void printSCFG(CFGWalker &Walker) { llvm::BumpPtrAllocator Bpa; til::MemRegionRef Arena(&Bpa); - SCFGBuilder builder(Arena); - // CFGVisitor visitor; - walker.walk(builder); - LLVMPrinter::print(builder.getCFG(), llvm::errs()); + SExprBuilder builder(Arena); + til::SCFG *Cfg = builder.buildCFG(Walker); + LLVMPrinter::print(Cfg, llvm::errs()); } -- 2.40.0