diff options
Diffstat (limited to 'clang/include')
4 files changed, 102 insertions, 43 deletions
diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h index 2b693cf0e46..6adef3471f6 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h +++ b/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h @@ -117,8 +117,9 @@ public: V.enterCFGBlock(CurrBlock); - // Process predecessors + // Process predecessors, handling back edges last if (V.visitPredecessors()) { + SmallVector<CFGBlock*, 4> BackEdges; // Process successors for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(), SE = CurrBlock->pred_end(); @@ -127,11 +128,14 @@ public: continue; if (!VisitedBlocks.alreadySet(*SI)) { - V.handlePredecessorBackEdge(*SI); + BackEdges.push_back(*SI); continue; } V.handlePredecessor(*SI); } + + for (auto *Blk : BackEdges) + V.handlePredecessorBackEdge(Blk); } V.enterCFGBlockBody(CurrBlock); @@ -158,8 +162,10 @@ public: V.exitCFGBlockBody(CurrBlock); - // Process successors + // Process successors, handling back edges first. if (V.visitSuccessors()) { + SmallVector<CFGBlock*, 8> ForwardEdges; + // Process successors for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), SE = CurrBlock->succ_end(); @@ -167,12 +173,15 @@ public: if (*SI == nullptr) continue; - if (VisitedBlocks.alreadySet(*SI)) { - V.handleSuccessorBackEdge(*SI); + if (!VisitedBlocks.alreadySet(*SI)) { + ForwardEdges.push_back(*SI); continue; } - V.handleSuccessor(*SI); + V.handleSuccessorBackEdge(*SI); } + + for (auto *Blk : ForwardEdges) + V.handleSuccessor(Blk); } V.exitCFGBlock(CurrBlock); @@ -197,8 +206,6 @@ private: // Translate clang::Expr to til::SExpr. class SExprBuilder { public: - typedef llvm::DenseMap<const Stmt*, til::Variable*> StatementMap; - /// \brief Encapsulates the lexical context of a function call. The lexical /// context includes the arguments to the call, including the implicit object /// argument. When an attribute containing a mutex expression is attached to @@ -226,10 +233,9 @@ public: SExprBuilder(til::MemRegionRef A) : Arena(A), SelfVar(nullptr), Scfg(nullptr), CallCtx(nullptr), - CurrentBB(nullptr), CurrentBlockID(0), CurrentVarID(0), - CurrentArgIndex(0) { + CurrentBB(nullptr), CurrentBlockInfo(nullptr) { // FIXME: we don't always have a self-variable. - SelfVar = new (Arena)til::Variable(til::Variable::VK_SFun); + SelfVar = new (Arena) til::Variable(til::Variable::VK_SFun); } // Translate a clang statement or expression to a TIL expression. @@ -239,6 +245,11 @@ public: til::SCFG *buildCFG(CFGWalker &Walker); til::SExpr *lookupStmt(const Stmt *S); + + til::BasicBlock *lookupBlock(const CFGBlock *B) { + return BlockMap[B->getBlockID()]; + } + const til::SCFG *getCFG() const { return Scfg; } til::SCFG *getCFF() { return Scfg; } @@ -266,30 +277,41 @@ private: til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); - // Used for looking the index of a name. - typedef llvm::DenseMap<const ValueDecl *, unsigned> NameIndexMap; + // Map from statements in the clang CFG to SExprs in the til::SCFG. + typedef llvm::DenseMap<const Stmt*, til::SExpr*> StatementMap; + + // Map from clang local variables to indices in a LVarDefinitionMap. + typedef llvm::DenseMap<const ValueDecl *, unsigned> LVarIndexMap; - // Used for looking up the current SSA variable for a name, by index. - typedef CopyOnWriteVector<std::pair<const ValueDecl *, til::SExpr *>> - NameVarMap; + // Map from local variable indices to SSA variables (or constants). + typedef std::pair<const ValueDecl *, til::SExpr *> NameVarPair; + typedef CopyOnWriteVector<NameVarPair> LVarDefinitionMap; struct BlockInfo { - NameVarMap ExitMap; + LVarDefinitionMap ExitMap; bool HasBackEdges; - unsigned SuccessorsToProcess; - BlockInfo() : HasBackEdges(false), SuccessorsToProcess(0) {} + unsigned UnprocessedSuccessors; // Successors yet to be processed + unsigned ProcessedPredecessors; // Predecessors already processed + + BlockInfo() + : HasBackEdges(false), UnprocessedSuccessors(0), + ProcessedPredecessors(0) {} BlockInfo(BlockInfo &&RHS) - : ExitMap(std::move(RHS.ExitMap)), HasBackEdges(RHS.HasBackEdges), - SuccessorsToProcess(RHS.SuccessorsToProcess) {} + : ExitMap(std::move(RHS.ExitMap)), + HasBackEdges(RHS.HasBackEdges), + UnprocessedSuccessors(RHS.UnprocessedSuccessors), + ProcessedPredecessors(RHS.ProcessedPredecessors) {} BlockInfo &operator=(BlockInfo &&RHS) { if (this != &RHS) { ExitMap = std::move(RHS.ExitMap); HasBackEdges = RHS.HasBackEdges; - SuccessorsToProcess = RHS.SuccessorsToProcess; + UnprocessedSuccessors = RHS.UnprocessedSuccessors; + ProcessedPredecessors = RHS.ProcessedPredecessors; } return *this; } + private: BlockInfo(const BlockInfo &) LLVM_DELETED_FUNCTION; void operator=(const BlockInfo &) LLVM_DELETED_FUNCTION; @@ -313,31 +335,38 @@ private: void exitCFGBlock(const CFGBlock *B); void exitCFG(const CFGBlock *Last); - void insertStmt(const Stmt *S, til::Variable *V); + void insertStmt(const Stmt *S, til::SExpr *E) { + SMap.insert(std::make_pair(S, E)); + } + til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD); + 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); + void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E); + void mergeEntryMap(LVarDefinitionMap Map); + void mergeEntryMapBackEdge(); + void mergePhiNodesBackEdge(const CFGBlock *Blk); +private: til::MemRegionRef Arena; 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. + LVarIndexMap LVarIdxMap; // Indices of clang local vars. std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs. std::vector<BlockInfo> BBInfo; // Extra information per BB. // Indexed by clang BlockID. SExprBuilder::CallingContext *CallCtx; // Root calling context - NameVarMap CurrentNameMap; + LVarDefinitionMap CurrentLVarMap; + std::vector<til::Variable*> CurrentArguments; + std::vector<til::Variable*> CurrentInstructions; til::BasicBlock *CurrentBB; BlockInfo *CurrentBlockInfo; - unsigned CurrentBlockID; - unsigned CurrentVarID; - unsigned CurrentArgIndex; }; diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h b/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h index 331e885178e..94ef9b3951b 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h +++ b/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h @@ -952,7 +952,8 @@ public: static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } SCFG(MemRegionRef A, unsigned Nblocks) - : SExpr(COP_SCFG), Blocks(A, Nblocks), Entry(nullptr), Exit(nullptr) {} + : SExpr(COP_SCFG), Blocks(A, Nblocks), + Entry(nullptr), Exit(nullptr) {} SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba : SExpr(COP_SCFG), Blocks(std::move(Ba)), Entry(nullptr), Exit(nullptr) { // TODO: set entry and exit! @@ -972,7 +973,7 @@ public: const BasicBlock *exit() const { return Exit; } BasicBlock *exit() { return Exit; } - void add(BasicBlock *BB) { Blocks.push_back(BB); } + void add(BasicBlock *BB); void setEntry(BasicBlock *BB) { Entry = BB; } void setExit(BasicBlock *BB) { Exit = BB; } @@ -1001,12 +1002,12 @@ public: BasicBlock(MemRegionRef A, unsigned Nargs, unsigned Nins, SExpr *Term = nullptr) - : BlockID(0), Parent(nullptr), NumPredecessors(0), + : BlockID(0), NumVars(0), NumPredecessors(0), Parent(nullptr), Args(A, Nargs), Instrs(A, Nins), Terminator(Term) {} BasicBlock(const BasicBlock &B, VarArray &&As, VarArray &&Is, SExpr *T) - : BlockID(0), Parent(nullptr), NumPredecessors(B.NumPredecessors), - Args(std::move(As)), Instrs(std::move(Is)), Terminator(T) - {} + : BlockID(0), NumVars(B.NumVars), NumPredecessors(B.NumPredecessors), + Parent(nullptr), Args(std::move(As)), Instrs(std::move(Is)), + Terminator(T) {} unsigned blockID() const { return BlockID; } unsigned numPredecessors() const { return NumPredecessors; } @@ -1027,8 +1028,15 @@ public: 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); } + + void addArgument(Variable *V) { + V->setID(BlockID, NumVars++); + Args.push_back(V); + } + void addInstruction(Variable *V) { + V->setID(BlockID, NumVars++); + Instrs.push_back(V); + } template <class V> BasicBlock *traverse(V &Visitor) { typename V::template Container<Variable*> Nas(Visitor, Args.size()); @@ -1064,14 +1072,23 @@ private: friend class SCFG; unsigned BlockID; + unsigned NumVars; + unsigned NumPredecessors; // Number of blocks which jump to this one. + 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; }; + +inline void SCFG::add(BasicBlock *BB) { + BB->setBlockID(Blocks.size()); + Blocks.push_back(BB); +} + + template <class V> typename V::R_SExpr SCFG::traverse(V &Visitor) { Visitor.enterCFG(*this); @@ -1084,6 +1101,7 @@ typename V::R_SExpr SCFG::traverse(V &Visitor) { return Visitor.reduceSCFG(*this, Bbs); } + class Phi : public SExpr { public: // TODO: change to SExprRef @@ -1098,6 +1116,15 @@ public: const ValArray &values() const { return Values; } ValArray &values() { return Values; } + // Incomplete phi nodes are constructed during SSA conversion, and + // may not be necessary. + bool incomplete() const { return Flags == 1; } + + void setIncomplete(bool b) { + if (b) Flags = 1; + else Flags = 0; + } + template <class V> typename V::R_SExpr traverse(V &Visitor) { typename V::template Container<typename V::R_SExpr> Nvs(Visitor, Values.size()); diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h b/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h index 603c5f556c0..dd10a34531a 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h +++ b/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h @@ -510,7 +510,7 @@ protected: } void printLiteralPtr(LiteralPtr *E, StreamType &SS) { - SS << E->clangDecl()->getName(); + SS << E->clangDecl()->getNameAsString(); } void printVariable(Variable *E, StreamType &SS) { diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h b/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h index 4ca49dfbd99..3b768c5a692 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h +++ b/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h @@ -80,7 +80,7 @@ public: SimpleArray(T *Dat, size_t Cp, size_t Sz = 0) : Data(Dat), Size(Sz), Capacity(Cp) {} SimpleArray(MemRegionRef A, size_t Cp) - : Data(A.allocateT<T>(Cp)), Size(0), Capacity(Cp) {} + : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Size(0), Capacity(Cp) {} SimpleArray(SimpleArray<T> &&A) : Data(A.Data), Size(A.Size), Capacity(A.Capacity) { A.Data = nullptr; @@ -100,11 +100,14 @@ public: return *this; } - T *resize(size_t Ncp, MemRegionRef A) { + void reserve(size_t Ncp, MemRegionRef A) { + if (Ncp < Capacity) + return; T *Odata = Data; Data = A.allocateT<T>(Ncp); + Capacity = Ncp; memcpy(Data, Odata, sizeof(T) * Size); - return Odata; + return; } typedef T *iterator; @@ -134,7 +137,7 @@ public: } void setValues(unsigned Sz, const T& C) { - assert(Sz < Capacity); + assert(Sz <= Capacity); Size = Sz; for (unsigned i = 0; i < Sz; ++i) { Data[i] = C; |
