From 44be81b5a918b75c7fd88bc71f2b62a16e55e7e7 Mon Sep 17 00:00:00 2001 From: DeLesley Hutchins Date: Wed, 28 May 2014 21:28:13 +0000 Subject: [PATCH] Thread Safety Analysis: update TIL traversal mechanism to allow arbitrary local contexts. Also includes some minor refactoring. llvm-svn: 209774 --- .../clang/Analysis/Analyses/ThreadSafetyCommon.h | 2 +- .../clang/Analysis/Analyses/ThreadSafetyOps.def | 3 +- .../clang/Analysis/Analyses/ThreadSafetyTIL.h | 608 +++++++++++++-------- .../clang/Analysis/Analyses/ThreadSafetyTraverse.h | 269 +++++---- .../clang/Analysis/Analyses/ThreadSafetyUtil.h | 13 +- clang/lib/Analysis/ThreadSafetyCommon.cpp | 17 +- clang/lib/Analysis/ThreadSafetyTIL.cpp | 40 ++ 7 files changed, 594 insertions(+), 358 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h index a83cbc5..09c614c 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h +++ b/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h @@ -238,7 +238,7 @@ public: : Arena(A), SelfVar(nullptr), Scfg(nullptr), CurrentBB(nullptr), CurrentBlockInfo(nullptr) { // FIXME: we don't always have a self-variable. - SelfVar = new (Arena) til::Variable(); + SelfVar = new (Arena) til::Variable(nullptr); SelfVar->setKind(til::Variable::VK_SFun); } diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafetyOps.def b/clang/include/clang/Analysis/Analyses/ThreadSafetyOps.def index c8784b6..6ebc95d 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafetyOps.def +++ b/clang/include/clang/Analysis/Analyses/ThreadSafetyOps.def @@ -34,7 +34,7 @@ TIL_OPCODE_DEF(Call) TIL_OPCODE_DEF(Alloc) TIL_OPCODE_DEF(Load) TIL_OPCODE_DEF(Store) -TIL_OPCODE_DEF(ArrayFirst) +TIL_OPCODE_DEF(ArrayIndex) TIL_OPCODE_DEF(ArrayAdd) TIL_OPCODE_DEF(UnaryOp) @@ -42,6 +42,7 @@ TIL_OPCODE_DEF(BinaryOp) TIL_OPCODE_DEF(Cast) TIL_OPCODE_DEF(SCFG) +TIL_OPCODE_DEF(BasicBlock) TIL_OPCODE_DEF(Phi) TIL_OPCODE_DEF(Goto) TIL_OPCODE_DEF(Branch) diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h b/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h index dcb196f..a9e58c3 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h +++ b/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h @@ -246,13 +246,6 @@ inline ValueType ValueType::getValueType() { -enum TraversalKind { - TRV_Normal, - TRV_Lazy, // subexpression may need to be traversed lazily - TRV_Tail // subexpression occurs in a tail position -}; - - // Base class for AST nodes in the typed intermediate language. class SExpr { public: @@ -264,8 +257,9 @@ public: // copy constructor: construct copy of E, with some additional arguments. // } // - // template typename V::R_SExpr traverse(V &Visitor) { - // traverse all subexpressions, following the traversal/rewriter interface + // template + // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + // traverse all subexpressions, following the traversal/rewriter interface. // } // // template typename C::CType compare(CType* E, C& Cmp) { @@ -375,8 +369,8 @@ public: }; // These are defined after SExprRef contructor, below + inline Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr); inline Variable(StringRef s, 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); } @@ -402,9 +396,10 @@ public: void setDefinition(SExpr *E); void setKind(VariableKind K) { Flags = K; } - template typename V::R_SExpr traverse(V &Visitor) { + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { // This routine is only called for variable references. - return Visitor.reduceVariableRef(this); + return Vs.reduceVariableRef(this); } template typename C::CType compare(Variable* E, C& Cmp) { @@ -474,9 +469,10 @@ public: } } - template typename V::R_SExpr traverse(V &Visitor) { + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { assert(Result && "Cannot traverse Future that has not been forced."); - return Visitor.traverse(Result); + return Vs.traverse(Result, Ctx); } template typename C::CType compare(Future* E, C& Cmp) { @@ -568,8 +564,9 @@ public: Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {} Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {} - template typename V::R_SExpr traverse(V &Visitor) { - return Visitor.reduceUndefined(*this); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + return Vs.reduceUndefined(*this); } template typename C::CType compare(Undefined* E, C& Cmp) { @@ -589,8 +586,8 @@ public: Wildcard() : SExpr(COP_Wildcard) {} Wildcard(const Wildcard &W) : SExpr(W) {} - template typename V::R_SExpr traverse(V &Visitor) { - return Visitor.reduceWildcard(*this); + template typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + return Vs.reduceWildcard(*this); } template typename C::CType compare(Wildcard* E, C& Cmp) { @@ -615,16 +612,14 @@ public: ValueType valueType() const { return ValType; } - template typename V::R_SExpr traverse(V &Visitor) { - return Visitor.reduceLiteral(*this); - } + template typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx); template typename C::CType compare(Literal* E, C& Cmp) { // TODO -- use value, not pointer equality return Cmp.comparePointers(Cexpr, E->Cexpr); } -private: +protected: const ValueType ValType; const clang::Expr *Cexpr; }; @@ -645,6 +640,63 @@ private: }; +template +typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { + if (Cexpr) + return Vs.reduceLiteral(*this); + + switch (ValType.Base) { + case ValueType::BT_Void: + break; + case ValueType::BT_Bool: + return Vs.reduceLiteralT(*static_cast*>(this)); + case ValueType::BT_Int: { + switch (ValType.Size) { + case ValueType::ST_8: + if (ValType.Signed) + return Vs.reduceLiteralT(*static_cast*>(this)); + else + return Vs.reduceLiteralT(*static_cast*>(this)); + case ValueType::ST_16: + if (ValType.Signed) + return Vs.reduceLiteralT(*static_cast*>(this)); + else + return Vs.reduceLiteralT(*static_cast*>(this)); + case ValueType::ST_32: + if (ValType.Signed) + return Vs.reduceLiteralT(*static_cast*>(this)); + else + return Vs.reduceLiteralT(*static_cast*>(this)); + case ValueType::ST_64: + if (ValType.Signed) + return Vs.reduceLiteralT(*static_cast*>(this)); + else + return Vs.reduceLiteralT(*static_cast*>(this)); + default: + break; + } + } + case ValueType::BT_Float: { + switch (ValType.Size) { + case ValueType::ST_32: + return Vs.reduceLiteralT(*static_cast*>(this)); + case ValueType::ST_64: + return Vs.reduceLiteralT(*static_cast*>(this)); + default: + break; + } + } + case ValueType::BT_String: + return Vs.reduceLiteralT(*static_cast*>(this)); + case ValueType::BT_Pointer: + return Vs.reduceLiteralT(*static_cast*>(this)); + case ValueType::BT_ValueRef: + break; + } + return Vs.reduceLiteral(*this); +} + + // Literal pointer to an object allocated in memory. // At compile time, pointer literals are represented by symbolic names. class LiteralPtr : public SExpr { @@ -657,8 +709,9 @@ public: // The clang declaration for the value that this pointer points to. const clang::ValueDecl *clangDecl() const { return Cvdecl; } - template typename V::R_SExpr traverse(V &Visitor) { - return Visitor.reduceLiteralPtr(*this); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + return Vs.reduceLiteralPtr(*this); } template typename C::CType compare(LiteralPtr* E, C& Cmp) { @@ -692,14 +745,15 @@ public: SExpr *body() { return Body.get(); } const SExpr *body() const { return Body.get(); } - template typename V::R_SExpr traverse(V &Visitor) { + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { // This is a variable declaration, so traverse the definition. - typename V::R_SExpr E0 = Visitor.traverse(VarDecl->Definition, TRV_Lazy); + auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx)); // Tell the rewriter to enter the scope of the function. - Variable *Nvd = Visitor.enterScope(*VarDecl, E0); - typename V::R_SExpr E1 = Visitor.traverse(Body); - Visitor.exitScope(*VarDecl); - return Visitor.reduceFunction(*this, Nvd, E1); + Variable *Nvd = Vs.enterScope(*VarDecl, E0); + auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); + Vs.exitScope(*VarDecl); + return Vs.reduceFunction(*this, Nvd, E1); } template typename C::CType compare(Function* E, C& Cmp) { @@ -745,15 +799,16 @@ public: SExpr *body() { return Body.get(); } const SExpr *body() const { return Body.get(); } - template typename V::R_SExpr traverse(V &Visitor) { + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { // A self-variable points to the SFunction itself. // A rewrite must introduce the variable with a null definition, and update // it after 'this' has been rewritten. - Variable *Nvd = Visitor.enterScope(*VarDecl, nullptr /* def */); - typename V::R_SExpr E1 = Visitor.traverse(Body); - Visitor.exitScope(*VarDecl); + Variable *Nvd = Vs.enterScope(*VarDecl, nullptr); + auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); + Vs.exitScope(*VarDecl); // A rewrite operation will call SFun constructor to set Vvd->Definition. - return Visitor.reduceSFunction(*this, Nvd, E1); + return Vs.reduceSFunction(*this, Nvd, E1); } template typename C::CType compare(SFunction* E, C& Cmp) { @@ -784,10 +839,11 @@ public: SExpr *body() { return Body.get(); } const SExpr *body() const { return Body.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Nt = Visitor.traverse(ReturnType, TRV_Lazy); - typename V::R_SExpr Nb = Visitor.traverse(Body, TRV_Lazy); - return Visitor.reduceCode(*this, Nt, Nb); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx)); + auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); + return Vs.reduceCode(*this, Nt, Nb); } template typename C::CType compare(Code* E, C& Cmp) { @@ -818,10 +874,11 @@ public: SExpr *body() { return Body.get(); } const SExpr *body() const { return Body.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Nr = Visitor.traverse(Range, TRV_Lazy); - typename V::R_SExpr Nb = Visitor.traverse(Body, TRV_Lazy); - return Visitor.reduceField(*this, Nr, Nb); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx)); + auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); + return Vs.reduceField(*this, Nr, Nb); } template typename C::CType compare(Field* E, C& Cmp) { @@ -853,10 +910,11 @@ public: SExpr *arg() { return Arg.get(); } const SExpr *arg() const { return Arg.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Nf = Visitor.traverse(Fun); - typename V::R_SExpr Na = Visitor.traverse(Arg); - return Visitor.reduceApply(*this, Nf, Na); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx)); + auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx)); + return Vs.reduceApply(*this, Nf, Na); } template typename C::CType compare(Apply* E, C& Cmp) { @@ -889,10 +947,12 @@ public: bool isDelegation() const { return Arg == nullptr; } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Nf = Visitor.traverse(Sfun); - typename V::R_SExpr Na = Arg.get() ? Visitor.traverse(Arg) : nullptr; - return Visitor.reduceSApply(*this, Nf, Na); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx)); + typename V::R_SExpr Na = Arg.get() ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) + : nullptr; + return Vs.reduceSApply(*this, Nf, Na); } template typename C::CType compare(SApply* E, C& Cmp) { @@ -935,9 +995,10 @@ public: return SlotName; } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Nr = Visitor.traverse(Rec); - return Visitor.reduceProject(*this, Nr); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx)); + return Vs.reduceProject(*this, Nr); } template typename C::CType compare(Project* E, C& Cmp) { @@ -968,9 +1029,10 @@ public: const clang::CallExpr *clangCallExpr() const { return Cexpr; } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Nt = Visitor.traverse(Target); - return Visitor.reduceCall(*this, Nt); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx)); + return Vs.reduceCall(*this, Nt); } template typename C::CType compare(Call* E, C& Cmp) { @@ -1001,9 +1063,10 @@ public: SExpr *dataType() { return Dtype.get(); } const SExpr *dataType() const { return Dtype.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Nd = Visitor.traverse(Dtype); - return Visitor.reduceAlloc(*this, Nd); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx)); + return Vs.reduceAlloc(*this, Nd); } template typename C::CType compare(Alloc* E, C& Cmp) { @@ -1029,9 +1092,10 @@ public: SExpr *pointer() { return Ptr.get(); } const SExpr *pointer() const { return Ptr.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Np = Visitor.traverse(Ptr); - return Visitor.reduceLoad(*this, Np); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx)); + return Vs.reduceLoad(*this, Np); } template typename C::CType compare(Load* E, C& Cmp) { @@ -1058,10 +1122,11 @@ public: SExpr *source() { return Source.get(); } // Value to store const SExpr *source() const { return Source.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Np = Visitor.traverse(Dest); - typename V::R_SExpr Nv = Visitor.traverse(Source); - return Visitor.reduceStore(*this, Np, Nv); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx)); + auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx)); + return Vs.reduceStore(*this, Np, Nv); } template typename C::CType compare(Store* E, C& Cmp) { @@ -1079,27 +1144,37 @@ private: // If p is a reference to an array, then first(p) is a reference to the first // element. The usual array notation p[i] becomes first(p + i). -class ArrayFirst : public SExpr { +class ArrayIndex : public SExpr { public: - static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayFirst; } + static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; } - ArrayFirst(SExpr *A) : SExpr(COP_ArrayFirst), Array(A) {} - ArrayFirst(const ArrayFirst &E, SExpr *A) : SExpr(E), Array(A) {} + ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {} + ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N) + : SExpr(E), Array(A), Index(N) {} SExpr *array() { return Array.get(); } const SExpr *array() const { return Array.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Na = Visitor.traverse(Array); - return Visitor.reduceArrayFirst(*this, Na); + SExpr *index() { return Index.get(); } + const SExpr *index() const { return Index.get(); } + + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); + auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); + return Vs.reduceArrayIndex(*this, Na, Ni); } - template typename C::CType compare(ArrayFirst* E, C& Cmp) { - return Cmp.compare(array(), E->array()); + template typename C::CType compare(ArrayIndex* E, C& Cmp) { + typename C::CType Ct = Cmp.compare(array(), E->array()); + if (Cmp.notTrue(Ct)) + return Ct; + return Cmp.compare(index(), E->index()); } private: SExprRef Array; + SExprRef Index; }; @@ -1120,10 +1195,11 @@ public: SExpr *index() { return Index.get(); } const SExpr *index() const { return Index.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Na = Visitor.traverse(Array); - typename V::R_SExpr Ni = Visitor.traverse(Index); - return Visitor.reduceArrayAdd(*this, Na, Ni); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); + auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); + return Vs.reduceArrayAdd(*this, Na, Ni); } template typename C::CType compare(ArrayAdd* E, C& Cmp) { @@ -1156,9 +1232,10 @@ public: SExpr *expr() { return Expr0.get(); } const SExpr *expr() const { return Expr0.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Ne = Visitor.traverse(Expr0); - return Visitor.reduceUnaryOp(*this, Ne); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); + return Vs.reduceUnaryOp(*this, Ne); } template typename C::CType compare(UnaryOp* E, C& Cmp) { @@ -1198,10 +1275,11 @@ public: SExpr *expr1() { return Expr1.get(); } const SExpr *expr1() const { return Expr1.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Ne0 = Visitor.traverse(Expr0); - typename V::R_SExpr Ne1 = Visitor.traverse(Expr1); - return Visitor.reduceBinaryOp(*this, Ne0, Ne1); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); + auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx)); + return Vs.reduceBinaryOp(*this, Ne0, Ne1); } template typename C::CType compare(BinaryOp* E, C& Cmp) { @@ -1236,9 +1314,10 @@ public: SExpr *expr() { return Expr0.get(); } const SExpr *expr() const { return Expr0.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Ne = Visitor.traverse(Expr0); - return Visitor.reduceCast(*this, Ne); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); + return Vs.reduceCast(*this, Ne); } template typename C::CType compare(Cast* E, C& Cmp) { @@ -1254,57 +1333,53 @@ private: }; +class SCFG; -class BasicBlock; -// An SCFG is a control-flow graph. It consists of a set of basic blocks, each -// of which terminates in a branch to another basic block. There is one -// entry point, and one exit point. -class SCFG : public SExpr { +class Phi : public SExpr { public: - typedef SimpleArray BlockArray; - typedef BlockArray::iterator iterator; - typedef BlockArray::const_iterator const_iterator; - - static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } + // TODO: change to SExprRef + typedef SimpleArray ValArray; - SCFG(MemRegionRef A, unsigned Nblocks) - : 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! - } + // In minimal SSA form, all Phi nodes are MultiVal. + // During conversion to SSA, incomplete Phi nodes may be introduced, which + // are later determined to be SingleVal, and are thus redundant. + enum Status { + PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal) + PH_SingleVal, // Phi node has one distinct value, and can be eliminated + PH_Incomplete // Phi node is incomplete + }; - iterator begin() { return Blocks.begin(); } - iterator end() { return Blocks.end(); } + static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } - const_iterator begin() const { return cbegin(); } - const_iterator end() const { return cend(); } + Phi() : SExpr(COP_Phi) {} + Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {} + Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {} - const_iterator cbegin() const { return Blocks.cbegin(); } - const_iterator cend() const { return Blocks.cend(); } + const ValArray &values() const { return Values; } + ValArray &values() { return Values; } - const BasicBlock *entry() const { return Entry; } - BasicBlock *entry() { return Entry; } - const BasicBlock *exit() const { return Exit; } - BasicBlock *exit() { return Exit; } + Status status() const { return static_cast(Flags); } + void setStatus(Status s) { Flags = s; } - void add(BasicBlock *BB); - void setEntry(BasicBlock *BB) { Entry = BB; } - void setExit(BasicBlock *BB) { Exit = BB; } + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + typename V::template Container + Nvs(Vs, Values.size()); - template typename V::R_SExpr traverse(V &Visitor); + for (auto *Val : Values) { + Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) ); + } + return Vs.reducePhi(*this, Nvs); + } - template typename C::CType compare(SCFG *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); } private: - BlockArray Blocks; - BasicBlock *Entry; - BasicBlock *Exit; + ValArray Values; }; @@ -1313,21 +1388,28 @@ private: // are "arguments" to the function, followed by a sequence of instructions. // Both arguments and instructions define new variables. It ends with a // branch or goto to another basic block in the same SCFG. -class BasicBlock { +class BasicBlock : public SExpr { public: - typedef SimpleArray VarArray; - - BasicBlock(MemRegionRef A, unsigned Nargs, unsigned Nins, - SExpr *Term = nullptr) - : 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), NumVars(B.NumVars), NumPredecessors(B.NumPredecessors), + typedef SimpleArray VarArray; + typedef SimpleArray BlockArray; + + static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; } + + explicit BasicBlock(MemRegionRef A, BasicBlock* P = nullptr) + : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0), + Parent(P), Terminator(nullptr) + { } + BasicBlock(BasicBlock &B, VarArray &&As, VarArray &&Is, SExpr *T) + : SExpr(COP_BasicBlock), Arena(B.Arena), CFGPtr(nullptr), BlockID(0), Parent(nullptr), Args(std::move(As)), Instrs(std::move(Is)), - Terminator(T) {} + Terminator(T) + { } unsigned blockID() const { return BlockID; } - unsigned numPredecessors() const { return NumPredecessors; } + unsigned numPredecessors() const { return Predecessors.size(); } + + const SCFG* cfg() const { return CFGPtr; } + SCFG* cfg() { return CFGPtr; } const BasicBlock *parent() const { return Parent; } BasicBlock *parent() { return Parent; } @@ -1338,46 +1420,76 @@ public: const VarArray &instructions() const { return Instrs; } VarArray &instructions() { return Instrs; } + const BlockArray &predecessors() const { return Predecessors; } + BlockArray &predecessors() { return Predecessors; } + const SExpr *terminator() const { return Terminator.get(); } SExpr *terminator() { return Terminator.get(); } - 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 setBlockID(unsigned i) { BlockID = i; } + void setParent(BasicBlock *P) { Parent = P; } + void setTerminator(SExpr *E) { Terminator.reset(E); } + // Add a new argument. V must define a phi-node. void addArgument(Variable *V) { - V->setID(BlockID, NumVars++); + Args.reserveCheck(1, Arena); Args.push_back(V); } + // Add a new instruction. void addInstruction(Variable *V) { - V->setID(BlockID, NumVars++); + Instrs.reserveCheck(1, Arena); Instrs.push_back(V); } + // Add a new predecessor, and return the phi-node index for it. + // Will add an argument to all phi-nodes, initialized to nullptr. + unsigned addPredecessor(BasicBlock *Pred); - template BasicBlock *traverse(V &Visitor) { - typename V::template Container Nas(Visitor, Args.size()); - typename V::template Container Nis(Visitor, Instrs.size()); + // Reserve space for Nargs arguments. + void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); } + + // Reserve space for Nins instructions. + void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); } + + // Reserve space for NumPreds predecessors, including space in phi nodes. + void reservePredecessors(unsigned NumPreds); + + // Return the index of BB, or Predecessors.size if BB is not a predecessor. + unsigned findPredecessorIndex(BasicBlock *BB) { + unsigned I = 0; + for (BasicBlock *B : Predecessors) { + if (B == BB) return I; + ++I; + } + return Predecessors.size(); + } + + // Set id numbers for variables. + void renumberVars(); + + template + typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) { + typename V::template Container Nas(Vs, Args.size()); + typename V::template Container Nis(Vs, Instrs.size()); + + // Entering the basic block should do any scope initialization. + Vs.enterBasicBlock(*this); for (auto *A : Args) { - typename V::R_SExpr Ne = Visitor.traverse(A->Definition); - Variable *Nvd = Visitor.enterScope(*A, Ne); + auto Ne = Vs.traverse(A->Definition, Vs.subExprCtx(Ctx)); + Variable *Nvd = Vs.enterScope(*A, Ne); Nas.push_back(Nvd); } for (auto *I : Instrs) { - typename V::R_SExpr Ne = Visitor.traverse(I->Definition); - Variable *Nvd = Visitor.enterScope(*I, Ne); + auto Ne = Vs.traverse(I->Definition, Vs.subExprCtx(Ctx)); + Variable *Nvd = Vs.enterScope(*I, Ne); Nis.push_back(Nvd); } - typename V::R_SExpr Nt = Visitor.traverse(Terminator); + auto Nt = Vs.traverse(Terminator, Ctx); - // TODO: use reverse iterator - for (unsigned J = 0, JN = Instrs.size(); J < JN; ++J) - Visitor.exitScope(*Instrs[JN-J]); - for (unsigned I = 0, IN = Instrs.size(); I < IN; ++I) - Visitor.exitScope(*Args[IN-I]); + // Exiting the basic block should handle any scope cleanup. + Vs.exitBasicBlock(*this); - return Visitor.reduceBasicBlock(*this, Nas, Nis, Nt); + return Vs.reduceBasicBlock(*this, Nas, Nis, Nt); } template typename C::CType compare(BasicBlock *E, C &Cmp) { @@ -1388,80 +1500,95 @@ public: private: friend class SCFG; - unsigned BlockID; - unsigned NumVars; - unsigned NumPredecessors; // Number of blocks which jump to this one. + MemRegionRef Arena; + SCFG *CFGPtr; // The CFG that contains this block. + unsigned BlockID; // unique id for this BB in the containing CFG BasicBlock *Parent; // The parent block is the enclosing lexical scope. // The parent dominates this block. - VarArray Args; // Phi nodes. One argument per predecessor. - VarArray Instrs; - SExprRef Terminator; + BlockArray Predecessors; // Predecessor blocks in the CFG. + VarArray Args; // Phi nodes. One argument per predecessor. + VarArray Instrs; // Instructions. + SExprRef Terminator; // Branch or Goto }; -inline void SCFG::add(BasicBlock *BB) { - BB->setBlockID(Blocks.size()); - Blocks.push_back(BB); -} +// An SCFG is a control-flow graph. It consists of a set of basic blocks, each +// of which terminates in a branch to another basic block. There is one +// entry point, and one exit point. +class SCFG : public SExpr { +public: + typedef SimpleArray BlockArray; + typedef BlockArray::iterator iterator; + typedef BlockArray::const_iterator const_iterator; + static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } -template -typename V::R_SExpr SCFG::traverse(V &Visitor) { - Visitor.enterCFG(*this); - typename V::template Container Bbs(Visitor, Blocks.size()); - for (auto *B : Blocks) { - BasicBlock *Nbb = B->traverse(Visitor); - Bbs.push_back(Nbb); - } - Visitor.exitCFG(*this); - return Visitor.reduceSCFG(*this, Bbs); -} + SCFG(MemRegionRef A, unsigned Nblocks) + : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks), + Entry(nullptr), Exit(nullptr) { + Entry = new (A) BasicBlock(A, nullptr); + Exit = new (A) BasicBlock(A, Entry); + auto *V = new (A) Variable(new (A) Phi()); + Exit->addArgument(V); + add(Entry); + add(Exit); + } + SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba + : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)), + Entry(nullptr), Exit(nullptr) { + // TODO: set entry and exit! + } + iterator begin() { return Blocks.begin(); } + iterator end() { return Blocks.end(); } -class Phi : public SExpr { -public: - // TODO: change to SExprRef - typedef SimpleArray ValArray; + const_iterator begin() const { return cbegin(); } + const_iterator end() const { return cend(); } - // In minimal SSA form, all Phi nodes are MultiVal. - // During conversion to SSA, incomplete Phi nodes may be introduced, which - // are later determined to be SingleVal. - enum Status { - PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal) - PH_SingleVal, // Phi node has one distinct value, and can be eliminated - PH_Incomplete // Phi node is incomplete - }; + const_iterator cbegin() const { return Blocks.cbegin(); } + const_iterator cend() const { return Blocks.cend(); } - static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } + const BasicBlock *entry() const { return Entry; } + BasicBlock *entry() { return Entry; } + const BasicBlock *exit() const { return Exit; } + BasicBlock *exit() { return Exit; } - Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {} - Phi(const Phi &P, ValArray &&Vs) // steals memory of Vs - : SExpr(COP_Phi), Values(std::move(Vs)) {} + inline void add(BasicBlock *BB) { + assert(BB->CFGPtr == nullptr || BB->CFGPtr == this); + BB->setBlockID(Blocks.size()); + BB->CFGPtr = this; + Blocks.reserveCheck(1, Arena); + Blocks.push_back(BB); + } - const ValArray &values() const { return Values; } - ValArray &values() { return Values; } + void setEntry(BasicBlock *BB) { Entry = BB; } + void setExit(BasicBlock *BB) { Exit = BB; } - Status status() const { return static_cast(Flags); } - void setStatus(Status s) { Flags = s; } + // Set varable ids in all blocks. + void renumberVars(); - template typename V::R_SExpr traverse(V &Visitor) { - typename V::template Container Nvs(Visitor, - Values.size()); - for (auto *Val : Values) { - typename V::R_SExpr Nv = Visitor.traverse(Val); - Nvs.push_back(Nv); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + Vs.enterCFG(*this); + typename V::template Container Bbs(Vs, Blocks.size()); + for (auto *B : Blocks) { + Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) ); } - return Visitor.reducePhi(*this, Nvs); + Vs.exitCFG(*this); + return Vs.reduceSCFG(*this, Bbs); } - template typename C::CType compare(Phi *E, C &Cmp) { - // TODO: implement CFG comparisons + template typename C::CType compare(SCFG *E, C &Cmp) { + // TODO -- implement CFG comparisons return Cmp.comparePointers(this, E); } private: - ValArray Values; + MemRegionRef Arena; + BlockArray Blocks; + BasicBlock *Entry; + BasicBlock *Exit; }; @@ -1469,8 +1596,8 @@ class Goto : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } - Goto(BasicBlock *B, unsigned Index) - : SExpr(COP_Goto), TargetBlock(B), Index(0) {} + Goto(BasicBlock *B, unsigned I) + : SExpr(COP_Goto), TargetBlock(B), Index(I) {} Goto(const Goto &G, BasicBlock *B, unsigned I) : SExpr(COP_Goto), TargetBlock(B), Index(I) {} @@ -1479,10 +1606,10 @@ public: unsigned index() const { return Index; } - template typename V::R_SExpr traverse(V &Visitor) { - // TODO -- rewrite indices properly - BasicBlock *Ntb = Visitor.reduceBasicBlockRef(TargetBlock); - return Visitor.reduceGoto(*this, Ntb, Index); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock); + return Vs.reduceGoto(*this, Ntb); } template typename C::CType compare(Goto *E, C &Cmp) { @@ -1500,13 +1627,14 @@ class Branch : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } - Branch(SExpr *C, BasicBlock *T, BasicBlock *E) + Branch(SExpr *C, BasicBlock *T, BasicBlock *E, unsigned TI, unsigned EI) : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E), - ThenIndex(0), ElseIndex(0) + ThenIndex(TI), ElseIndex(EI) {} - Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) + Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E, + unsigned TI, unsigned EI) : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E), - ThenIndex(0), ElseIndex(0) + ThenIndex(TI), ElseIndex(EI) {} const SExpr *condition() const { return Condition; } @@ -1521,11 +1649,12 @@ public: 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); - BasicBlock *Nte = Visitor.reduceBasicBlockRef(ElseBlock); - return Visitor.reduceBranch(*this, Nc, Ntb, Nte); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); + BasicBlock *Ntb = Vs.reduceBasicBlockRef(ThenBlock); + BasicBlock *Nte = Vs.reduceBasicBlockRef(ElseBlock); + return Vs.reduceBranch(*this, Nc, Ntb, Nte); } template typename C::CType compare(Branch *E, C &Cmp) { @@ -1553,8 +1682,9 @@ public: StringRef name() const { return Name; } - template typename V::R_SExpr traverse(V &Visitor) { - return Visitor.reduceIdentifier(*this); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + return Vs.reduceIdentifier(*this); } template typename C::CType compare(Identifier* E, C& Cmp) { @@ -1567,7 +1697,7 @@ private: // An if-then-else expression. -// This is a pseduo-term; it will be lowered to a CFG. +// This is a pseduo-term; it will be lowered to a branch in a CFG. class IfThenElse : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; } @@ -1588,11 +1718,12 @@ public: SExpr *elseExpr() { return ElseExpr.get(); } // Value to store const SExpr *elseExpr() const { return ElseExpr.get(); } - template typename V::R_SExpr traverse(V &Visitor) { - typename V::R_SExpr Nc = Visitor.traverse(Condition); - typename V::R_SExpr Nt = Visitor.traverse(ThenExpr); - typename V::R_SExpr Ne = Visitor.traverse(ElseExpr); - return Visitor.reduceIfThenElse(*this, Nc, Nt, Ne); + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); + auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx)); + auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx)); + return Vs.reduceIfThenElse(*this, Nc, Nt, Ne); } template typename C::CType compare(IfThenElse* E, C& Cmp) { @@ -1613,7 +1744,7 @@ private: // A let-expression, e.g. let x=t; u. -// This is a pseduo-term; it will be lowered to a CFG. +// This is a pseduo-term; it will be lowered to instructions in a CFG. class Let : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Let; } @@ -1631,14 +1762,15 @@ public: SExpr *body() { return Body.get(); } const SExpr *body() const { return Body.get(); } - template typename V::R_SExpr traverse(V &Visitor) { + template + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { // This is a variable declaration, so traverse the definition. - typename V::R_SExpr E0 = Visitor.traverse(VarDecl->Definition, TRV_Lazy); + auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx)); // Tell the rewriter to enter the scope of the let variable. - Variable *Nvd = Visitor.enterScope(*VarDecl, E0); - typename V::R_SExpr E1 = Visitor.traverse(Body); - Visitor.exitScope(*VarDecl); - return Visitor.reduceLet(*this, Nvd, E1); + Variable *Nvd = Vs.enterScope(*VarDecl, E0); + auto E1 = Vs.traverse(Body, Ctx); + Vs.exitScope(*VarDecl); + return Vs.reduceLet(*this, Nvd, E1); } template typename C::CType compare(Let* E, C& Cmp) { diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h b/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h index b28085b..47c08a0 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h +++ b/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h @@ -45,33 +45,31 @@ namespace til { // compute a result for a node of type X // // The reduceX methods control the kind of traversal (visitor, copy, etc.). -// These are separated into a separate class R for the purpose of code reuse. -// The full reducer interface also has methods to handle scopes -template class Traversal : public R { +// They are defined in derived classes. +// +// Class R defines the basic interface types (R_SExpr). +template +class Traversal { public: - Self *self() { return reinterpret_cast(this); } + Self *self() { return static_cast(this); } // Traverse an expression -- returning a result of type R_SExpr. // Override this method to do something for every expression, regardless - // of which kind it is. TraversalKind indicates the context in which - // the expression occurs, and can be: - // TRV_Normal - // TRV_Lazy -- e may need to be traversed lazily, using a Future. - // TRV_Tail -- e occurs in a tail position - typename R::R_SExpr traverse(SExprRef &E, TraversalKind K = TRV_Normal) { - return traverse(E.get(), K); + // of which kind it is. + typename R::R_SExpr traverse(SExprRef &E, typename R::R_Ctx Ctx) { + return traverse(E.get(), Ctx); } - typename R::R_SExpr traverse(SExpr *E, TraversalKind K = TRV_Normal) { - return traverseByCase(E); + typename R::R_SExpr traverse(SExpr *E, typename R::R_Ctx Ctx) { + return traverseByCase(E, Ctx); } // Helper method to call traverseX(e) on the appropriate type. - typename R::R_SExpr traverseByCase(SExpr *E) { + typename R::R_SExpr traverseByCase(SExpr *E, typename R::R_Ctx Ctx) { switch (E->opcode()) { #define TIL_OPCODE_DEF(X) \ case COP_##X: \ - return self()->traverse##X(cast(E)); + return self()->traverse##X(cast(E), Ctx); #include "ThreadSafetyOps.def" #undef TIL_OPCODE_DEF } @@ -80,41 +78,83 @@ public: // Traverse e, by static dispatch on the type "X" of e. // Override these methods to do something for a particular kind of term. #define TIL_OPCODE_DEF(X) \ - typename R::R_SExpr traverse##X(X *e) { return e->traverse(*self()); } + typename R::R_SExpr traverse##X(X *e, typename R::R_Ctx Ctx) { \ + return e->traverse(*self(), Ctx); \ + } #include "ThreadSafetyOps.def" #undef TIL_OPCODE_DEF }; -// Implements a Reducer that makes a deep copy of an SExpr. -// The default behavior of reduce##X(...) is to create a copy of the original. -// Subclasses can override reduce##X to implement non-destructive rewriting -// passes. -class CopyReducer { +// Base class for simple reducers that don't much care about the context. +class SimpleReducerBase { public: - CopyReducer() {} + enum TraversalKind { + TRV_Normal, + TRV_Decl, + TRV_Lazy, + TRV_Type + }; + + // R_Ctx defines a "context" for the traversal, which encodes information + // about where a term appears. This can be used to encoding the + // "current continuation" for CPS transforms, or other information. + typedef TraversalKind R_Ctx; + + // Create context for an ordinary subexpression. + R_Ctx subExprCtx(R_Ctx Ctx) { return TRV_Normal; } + + // Create context for a subexpression that occurs in a declaration position + // (e.g. function body). + R_Ctx declCtx(R_Ctx Ctx) { return TRV_Decl; } - void setArena(MemRegionRef A) { Arena = A; } + // Create context for a subexpression that occurs in a position that + // should be reduced lazily. (e.g. code body). + R_Ctx lazyCtx(R_Ctx Ctx) { return TRV_Lazy; } + // Create context for a subexpression that occurs in a type position. + R_Ctx typeCtx(R_Ctx Ctx) { return TRV_Type; } +}; + + +// Base class for traversals that rewrite an SExpr to another SExpr. +class CopyReducerBase : public SimpleReducerBase { +public: // R_SExpr is the result type for a traversal. // A copy or non-destructive rewrite returns a newly allocated term. typedef SExpr *R_SExpr; + typedef BasicBlock *R_BasicBlock; // Container is a minimal interface used to store results when traversing // SExprs of variable arity, such as Phi, Goto, and SCFG. template class Container { public: // Allocate a new container with a capacity for n elements. - Container(CopyReducer &R, unsigned N) : Elems(R.Arena, N) {} + Container(CopyReducerBase &S, unsigned N) : Elems(S.Arena, N) {} // Push a new element onto the container. void push_back(T E) { Elems.push_back(E); } - private: - friend class CopyReducer; SimpleArray Elems; }; + CopyReducerBase(MemRegionRef A) : Arena(A) {} + +protected: + MemRegionRef Arena; +}; + + +// Implements a traversal that makes a deep copy of an SExpr. +// The default behavior of reduce##X(...) is to create a copy of the original. +// Subclasses can override reduce##X to implement non-destructive rewriting +// passes. +template +class CopyReducer : public Traversal, + public CopyReducerBase { +public: + CopyReducer(MemRegionRef A) : CopyReducerBase(A) {} + public: R_SExpr reduceNull() { return nullptr; @@ -131,6 +171,10 @@ public: R_SExpr reduceLiteral(Literal &Orig) { return new (Arena) Literal(Orig); } + template + R_SExpr reduceLiteralT(LiteralT &Orig) { + return new (Arena) LiteralT(Orig); + } R_SExpr reduceLiteralPtr(LiteralPtr &Orig) { return new (Arena) LiteralPtr(Orig); } @@ -170,8 +214,8 @@ public: R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { return new (Arena) Store(Orig, E0, E1); } - R_SExpr reduceArrayFirst(ArrayFirst &Orig, R_SExpr E0) { - return new (Arena) ArrayFirst(Orig, E0); + R_SExpr reduceArrayIndex(ArrayIndex &Orig, R_SExpr E0, R_SExpr E1) { + return new (Arena) ArrayIndex(Orig, E0, E1); } R_SExpr reduceArrayAdd(ArrayAdd &Orig, R_SExpr E0, R_SExpr E1) { return new (Arena) ArrayAdd(Orig, E0, E1); @@ -187,16 +231,20 @@ public: } R_SExpr reduceSCFG(SCFG &Orig, Container &Bbs) { - return new (Arena) SCFG(Orig, std::move(Bbs.Elems)); + return nullptr; // FIXME: implement CFG rewriting + } + R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container &As, + Container &Is, R_SExpr T) { + return nullptr; // FIXME: implement CFG rewriting } R_SExpr reducePhi(Phi &Orig, Container &As) { return new (Arena) Phi(Orig, std::move(As.Elems)); } - R_SExpr reduceGoto(Goto &Orig, BasicBlock *B, unsigned Index) { - return new (Arena) Goto(Orig, B, Index); + R_SExpr reduceGoto(Goto &Orig, BasicBlock *B) { + return new (Arena) Goto(Orig, B, 0); // FIXME: set index } R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) { - return new (Arena) Branch(O, C, B0, B1); + return new (Arena) Branch(O, C, B0, B1, 0, 0); // FIXME: set indices } R_SExpr reduceIdentifier(Identifier &Orig) { @@ -209,12 +257,6 @@ public: return new (Arena) Let(Orig, Nvd, B); } - BasicBlock *reduceBasicBlock(BasicBlock &Orig, Container &As, - Container &Is, R_SExpr T) { - return new (Arena) BasicBlock(Orig, std::move(As.Elems), - std::move(Is.Elems), T); - } - // Create a new variable from orig, and push it onto the lexical scope. Variable *enterScope(Variable &Orig, R_SExpr E0) { return new (Arena) Variable(Orig, E0); @@ -224,49 +266,57 @@ public: void enterCFG(SCFG &Cfg) {} void exitCFG(SCFG &Cfg) {} + void enterBasicBlock(BasicBlock &BB) {} + void exitBasicBlock(BasicBlock &BB) {} // Map Variable references to their rewritten definitions. Variable *reduceVariableRef(Variable *Ovd) { return Ovd; } - // Map BasicBlock references to their rewritten defs. + // Map BasicBlock references to their rewritten definitions. BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; } - -private: - MemRegionRef Arena; }; -class SExprCopier : public Traversal { +class SExprCopier : public CopyReducer { public: - SExprCopier(MemRegionRef A) { setArena(A); } + typedef SExpr *R_SExpr; + + SExprCopier(MemRegionRef A) : CopyReducer(A) { } // Create a copy of e in region a. static SExpr *copy(SExpr *E, MemRegionRef A) { SExprCopier Copier(A); - return Copier.traverse(E); + return Copier.traverse(E, TRV_Normal); } }; -// Implements a Reducer that visits each subexpression, and returns either -// true or false. -class VisitReducer { -public: - VisitReducer() {} +// Base class for visit traversals. +class VisitReducerBase : public SimpleReducerBase { +public: // A visitor returns a bool, representing success or failure. typedef bool R_SExpr; + typedef bool R_BasicBlock; // A visitor "container" is a single bool, which accumulates success. template class Container { public: - Container(VisitReducer &R, unsigned N) : Success(true) {} + Container(VisitReducerBase &S, unsigned N) : Success(true) {} void push_back(bool E) { Success = Success && E; } - private: - friend class VisitReducer; bool Success; }; +}; + + +// Implements a traversal that visits each subexpression, and returns either +// true or false. +template +class VisitReducer : public Traversal, + public VisitReducerBase { +public: + VisitReducer() {} public: R_SExpr reduceNull() { return true; } @@ -274,6 +324,8 @@ public: R_SExpr reduceWildcard(Wildcard &Orig) { return true; } R_SExpr reduceLiteral(Literal &Orig) { return true; } + template + R_SExpr reduceLiteralT(LiteralT &Orig) { return true; } R_SExpr reduceLiteralPtr(Literal &Orig) { return true; } R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) { @@ -299,7 +351,9 @@ public: R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) { return E0; } R_SExpr reduceLoad(Load &Orig, R_SExpr E0) { return E0; } R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } - R_SExpr reduceArrayFirst(Store &Orig, R_SExpr E0) { return E0; } + R_SExpr reduceArrayIndex(Store &Orig, R_SExpr E0, R_SExpr E1) { + return E0 && E1; + } R_SExpr reduceArrayAdd(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } @@ -312,10 +366,14 @@ public: R_SExpr reduceSCFG(SCFG &Orig, Container Bbs) { return Bbs.Success; } - R_SExpr reducePhi(Phi &Orig, Container &As) { + R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container &As, + Container &Is, R_SExpr T) { + return (As.Success && Is.Success && T); + } + R_SExpr reducePhi(Phi &Orig, Container &As) { return As.Success; } - R_SExpr reduceGoto(Goto &Orig, BasicBlock *B, unsigned Index) { + R_SExpr reduceGoto(Goto &Orig, BasicBlock *B) { return true; } R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) { @@ -332,39 +390,25 @@ public: return Nvd && B; } - BasicBlock *reduceBasicBlock(BasicBlock &Orig, Container &As, - Container &Is, R_SExpr T) { - return (As.Success && Is.Success && T) ? &Orig : nullptr; - } - - Variable *enterScope(Variable &Orig, R_SExpr E0) { - return E0 ? &Orig : nullptr; - } + Variable *enterScope(Variable &Orig, R_SExpr E0) { return &Orig; } void exitScope(const Variable &Orig) {} - void enterCFG(SCFG &Cfg) {} void exitCFG(SCFG &Cfg) {} + void enterBasicBlock(BasicBlock &BB) {} + void exitBasicBlock(BasicBlock &BB) {} - Variable *reduceVariableRef(Variable *Ovd) { return Ovd; } - + Variable *reduceVariableRef (Variable *Ovd) { return Ovd; } BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; } -}; - -// A visitor will visit each node, and halt if any reducer returns false. -template -class SExprVisitor : public Traversal { public: - SExprVisitor() : Success(true) {} - bool traverse(SExpr *E, TraversalKind K = TRV_Normal) { Success = Success && this->traverseByCase(E); return Success; } static bool visit(SExpr *E) { - SExprVisitor Visitor; - return Visitor.traverse(E); + Self Visitor; + return Visitor.traverse(E, TRV_Normal); } private: @@ -454,6 +498,8 @@ protected: } SS << "BB_"; SS << BB->blockID(); + SS << ":"; + SS << index; } // TODO: further distinguish between binary operations. @@ -488,7 +534,7 @@ protected: case COP_Alloc: return Prec_Other; case COP_Load: return Prec_Postfix; case COP_Store: return Prec_Other; - case COP_ArrayFirst: return Prec_Postfix; + case COP_ArrayIndex: return Prec_Postfix; case COP_ArrayAdd: return Prec_Postfix; case COP_UnaryOp: return Prec_Unary; @@ -496,6 +542,7 @@ protected: case COP_Cast: return Prec_Unary; case COP_SCFG: return Prec_Decl; + case COP_BasicBlock: return Prec_MAX; case COP_Phi: return Prec_Atom; case COP_Goto: return Prec_Atom; case COP_Branch: return Prec_Atom; @@ -614,7 +661,7 @@ protected: } case ValueType::BT_String: { SS << "\""; - printLiteralT(reinterpret_cast*>(E), SS); + printLiteralT(reinterpret_cast*>(E), SS); SS << "\""; return; } @@ -755,15 +802,11 @@ protected: self()->printSExpr(E->source(), SS, Prec_Other-1); } - void printArrayFirst(ArrayFirst *E, StreamType &SS) { + void printArrayIndex(ArrayIndex *E, StreamType &SS) { self()->printSExpr(E->array(), SS, Prec_Postfix); - if (ArrayAdd *A = dyn_cast_or_null(E->array())) { - SS << "["; - printSExpr(A->index(), SS, Prec_MAX); - SS << "]"; - return; - } - SS << "[0]"; + SS << "["; + self()->printSExpr(E->index(), SS, Prec_MAX); + SS << "]"; } void printArrayAdd(ArrayAdd *E, StreamType &SS) { @@ -789,37 +832,43 @@ protected: } void printSCFG(SCFG *E, StreamType &SS) { - SS << "#CFG {\n"; + SS << "CFG {\n"; for (auto BBI : *E) { - SS << "BB_" << BBI->blockID() << ":"; + printBasicBlock(BBI, SS); + } + SS << "}"; + newline(SS); + } + + void printBasicBlock(BasicBlock *E, StreamType &SS) { + SS << "BB_" << E->blockID() << ":"; + if (E->parent()) + SS << " BB_" << E->parent()->blockID(); + newline(SS); + for (auto A : E->arguments()) { + SS << "let "; + self()->printVariable(A, SS, true); + SS << " = "; + self()->printSExpr(A->definition(), SS, Prec_MAX); + SS << ";"; newline(SS); - for (auto A : BBI->arguments()) { + } + for (auto I : E->instructions()) { + if (I->definition()->opcode() != COP_Store) { SS << "let "; - self()->printVariable(A, SS, true); + self()->printVariable(I, SS, true); SS << " = "; - self()->printSExpr(A->definition(), SS, Prec_MAX); - SS << ";"; - newline(SS); - } - for (auto I : BBI->instructions()) { - if (I->definition()->opcode() != COP_Store) { - SS << "let "; - self()->printVariable(I, SS, true); - SS << " = "; - } - self()->printSExpr(I->definition(), SS, Prec_MAX); - SS << ";"; - newline(SS); - } - SExpr *T = BBI->terminator(); - if (T) { - self()->printSExpr(T, SS, Prec_MAX); - SS << ";"; - newline(SS); } + self()->printSExpr(I->definition(), SS, Prec_MAX); + SS << ";"; + newline(SS); + } + SExpr *T = E->terminator(); + if (T) { + self()->printSExpr(T, SS, Prec_MAX); + SS << ";"; newline(SS); } - SS << "}"; newline(SS); } diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h b/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h index 986103d..3c25426 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h +++ b/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h @@ -109,8 +109,9 @@ public: return *this; } + // Reserve space for at least Ncp items, reallocating if necessary. void reserve(size_t Ncp, MemRegionRef A) { - if (Ncp < Capacity) + if (Ncp <= Capacity) return; T *Odata = Data; Data = A.allocateT(Ncp); @@ -119,6 +120,14 @@ public: return; } + // Reserve space for at least N more items. + void reserveCheck(size_t N, MemRegionRef A) { + if (Capacity == 0) + reserve(InitialCapacity, A); + else if (Size + N < Capacity) + reserve(Capacity*2, A); + } + typedef T *iterator; typedef const T *const_iterator; @@ -163,6 +172,8 @@ public: } private: + static const unsigned InitialCapacity = 4; + SimpleArray(const SimpleArray &A) LLVM_DELETED_FUNCTION; T *Data; diff --git a/clang/lib/Analysis/ThreadSafetyCommon.cpp b/clang/lib/Analysis/ThreadSafetyCommon.cpp index 91cf849..deb9ba9 100644 --- a/clang/lib/Analysis/ThreadSafetyCommon.cpp +++ b/clang/lib/Analysis/ThreadSafetyCommon.cpp @@ -384,8 +384,7 @@ SExprBuilder::translateArraySubscriptExpr(const ArraySubscriptExpr *E, CallingContext *Ctx) { til::SExpr *E0 = translate(E->getBase(), Ctx); til::SExpr *E1 = translate(E->getIdx(), Ctx); - auto *AA = new (Arena) til::ArrayAdd(E0, E1); - return new (Arena) til::ArrayFirst(AA); + return new (Arena) til::ArrayIndex(E0, E1); } @@ -628,7 +627,8 @@ void SExprBuilder::enterCFG(CFG *Cfg, const NamedDecl *D, BlockMap.resize(NBlocks, nullptr); // create map from clang blockID to til::BasicBlocks for (auto *B : *Cfg) { - auto *BB = new (Arena) til::BasicBlock(Arena, 0, B->size()); + auto *BB = new (Arena) til::BasicBlock(Arena); + BB->reserveInstructions(B->size()); BlockMap[B->getBlockID()] = BB; } CallCtx.reset(new SExprBuilder::CallingContext(D)); @@ -654,7 +654,7 @@ void SExprBuilder::enterCFG(CFG *Cfg, const NamedDecl *D, void SExprBuilder::enterCFGBlock(const CFGBlock *B) { // Intialize TIL basic block and add it to the CFG. CurrentBB = lookupBlock(B); - CurrentBB->setNumPredecessors(B->pred_size()); + CurrentBB->reservePredecessors(B->pred_size()); Scfg->add(CurrentBB); CurrentBlockInfo = &BBInfo[B->getBlockID()]; @@ -668,6 +668,7 @@ void SExprBuilder::enterCFGBlock(const CFGBlock *B) { void SExprBuilder::handlePredecessor(const CFGBlock *Pred) { // Compute CurrentLVarMap on entry from ExitMaps of predecessors + CurrentBB->addPredecessor(BlockMap[Pred->getBlockID()]); BlockInfo *PredInfo = &BBInfo[Pred->getBlockID()]; assert(PredInfo->UnprocessedSuccessors > 0); @@ -724,7 +725,8 @@ void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) { if (N == 1) { til::BasicBlock *BB = *It ? lookupBlock(*It) : nullptr; // TODO: set index - til::SExpr *Tm = new (Arena) til::Goto(BB, 0); + unsigned Idx = BB->findPredecessorIndex(CurrentBB); + til::SExpr *Tm = new (Arena) til::Goto(BB, Idx); CurrentBB->setTerminator(Tm); } else if (N == 2) { @@ -732,8 +734,9 @@ void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) { til::BasicBlock *BB1 = *It ? lookupBlock(*It) : nullptr; ++It; til::BasicBlock *BB2 = *It ? lookupBlock(*It) : nullptr; - // TODO: set conditional, set index - til::SExpr *Tm = new (Arena) til::Branch(C, BB1, BB2); + unsigned Idx1 = BB1 ? BB1->findPredecessorIndex(CurrentBB) : 0; + unsigned Idx2 = BB2 ? BB2->findPredecessorIndex(CurrentBB) : 0; + til::SExpr *Tm = new (Arena) til::Branch(C, BB1, BB2, Idx1, Idx2); CurrentBB->setTerminator(Tm); } } diff --git a/clang/lib/Analysis/ThreadSafetyTIL.cpp b/clang/lib/Analysis/ThreadSafetyTIL.cpp index f4da8d4..f67cbb9 100644 --- a/clang/lib/Analysis/ThreadSafetyTIL.cpp +++ b/clang/lib/Analysis/ThreadSafetyTIL.cpp @@ -48,6 +48,46 @@ StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op) { } +unsigned BasicBlock::addPredecessor(BasicBlock *Pred) { + unsigned Idx = Predecessors.size(); + Predecessors.reserveCheck(1, Arena); + Predecessors.push_back(Pred); + for (Variable *V : Args) { + if (Phi* Ph = dyn_cast(V->definition())) { + Ph->values().reserveCheck(1, Arena); + Ph->values().push_back(nullptr); + } + } + return Idx; +} + +void BasicBlock::reservePredecessors(unsigned NumPreds) { + Predecessors.reserve(NumPreds, Arena); + for (Variable *V : Args) { + if (Phi* Ph = dyn_cast(V->definition())) { + Ph->values().reserve(NumPreds, Arena); + } + } +} + +void BasicBlock::renumberVars() { + unsigned VID = 0; + for (Variable *V : Args) { + V->setID(BlockID, VID++); + } + for (Variable *V : Instrs) { + V->setID(BlockID, VID++); + } +} + +void SCFG::renumberVars() { + for (BasicBlock *B : Blocks) { + B->renumberVars(); + } +} + + + // If E is a variable, then trace back through any aliases or redundant // Phi nodes to find the canonical definition. -- 2.7.4