diff options
Diffstat (limited to 'clang/lib')
| -rw-r--r-- | clang/lib/Analysis/ThreadSafetyCommon.cpp | 65 | ||||
| -rw-r--r-- | clang/lib/Analysis/ThreadSafetyTIL.cpp | 286 |
2 files changed, 252 insertions, 99 deletions
diff --git a/clang/lib/Analysis/ThreadSafetyCommon.cpp b/clang/lib/Analysis/ThreadSafetyCommon.cpp index e9b1f64..88a1cbf 100644 --- a/clang/lib/Analysis/ThreadSafetyCommon.cpp +++ b/clang/lib/Analysis/ThreadSafetyCommon.cpp @@ -63,11 +63,9 @@ std::string getSourceLiteralString(const clang::Expr *CE) { namespace til { // Return true if E is a variable that points to an incomplete Phi node. -static bool isIncompleteVar(const SExpr *E) { - if (const auto *V = dyn_cast<Variable>(E)) { - if (const auto *Ph = dyn_cast<Phi>(V->definition())) - return Ph->status() == Phi::PH_Incomplete; - } +static bool isIncompletePhi(const SExpr *E) { + if (const auto *Ph = dyn_cast<Phi>(E)) + return Ph->status() == Phi::PH_Incomplete; return false; } @@ -320,6 +318,8 @@ til::SExpr *SExprBuilder::translateCXXThisExpr(const CXXThisExpr *TE, const ValueDecl *getValueDeclFromSExpr(const til::SExpr *E) { if (auto *V = dyn_cast<til::Variable>(E)) return V->clangDecl(); + if (auto *Ph = dyn_cast<til::Phi>(E)) + return Ph->clangDecl(); if (auto *P = dyn_cast<til::Project>(E)) return P->clangDecl(); if (auto *L = dyn_cast<til::LiteralPtr>(E)) @@ -641,14 +641,14 @@ SExprBuilder::translateDeclStmt(const DeclStmt *S, CallingContext *Ctx) { // If E is trivial returns E. til::SExpr *SExprBuilder::addStatement(til::SExpr* E, const Stmt *S, const ValueDecl *VD) { - if (!E || !CurrentBB || til::ThreadSafetyTIL::isTrivial(E)) + if (!E || !CurrentBB || E->block() || til::ThreadSafetyTIL::isTrivial(E)) return E; - - til::Variable *V = new (Arena) til::Variable(E, VD); - CurrentInstructions.push_back(V); + if (VD) + E = new (Arena) til::Variable(E, VD); + CurrentInstructions.push_back(E); if (S) - insertStmt(S, V); - return V; + insertStmt(S, E); + return E; } @@ -705,11 +705,11 @@ void SExprBuilder::makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E) { unsigned ArgIndex = CurrentBlockInfo->ProcessedPredecessors; assert(ArgIndex > 0 && ArgIndex < NPreds); - til::Variable *V = dyn_cast<til::Variable>(CurrentLVarMap[i].second); - if (V && V->getBlockID() == CurrentBB->blockID()) { + til::SExpr *CurrE = CurrentLVarMap[i].second; + if (CurrE->block() == CurrentBB) { // We already have a Phi node in the current block, // so just add the new variable to the Phi node. - til::Phi *Ph = dyn_cast<til::Phi>(V->definition()); + til::Phi *Ph = dyn_cast<til::Phi>(CurrE); assert(Ph && "Expecting Phi node."); if (E) Ph->values()[ArgIndex] = E; @@ -718,27 +718,26 @@ void SExprBuilder::makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E) { // Make a new phi node: phi(..., E) // All phi args up to the current index are set to the current value. - til::SExpr *CurrE = CurrentLVarMap[i].second; til::Phi *Ph = new (Arena) til::Phi(Arena, NPreds); Ph->values().setValues(NPreds, nullptr); for (unsigned PIdx = 0; PIdx < ArgIndex; ++PIdx) Ph->values()[PIdx] = CurrE; if (E) Ph->values()[ArgIndex] = E; + Ph->setClangDecl(CurrentLVarMap[i].first); // If E is from a back-edge, or either E or CurrE are incomplete, then // mark this node as incomplete; we may need to remove it later. - if (!E || isIncompleteVar(E) || isIncompleteVar(CurrE)) { + if (!E || isIncompletePhi(E) || isIncompletePhi(CurrE)) { Ph->setStatus(til::Phi::PH_Incomplete); } // Add Phi node to current block, and update CurrentLVarMap[i] - auto *Var = new (Arena) til::Variable(Ph, CurrentLVarMap[i].first); - CurrentArguments.push_back(Var); + CurrentArguments.push_back(Ph); if (Ph->status() == til::Phi::PH_Incomplete) - IncompleteArgs.push_back(Var); + IncompleteArgs.push_back(Ph); CurrentLVarMap.makeWritable(); - CurrentLVarMap.elem(i).second = Var; + CurrentLVarMap.elem(i).second = Ph; } @@ -812,15 +811,13 @@ void SExprBuilder::mergePhiNodesBackEdge(const CFGBlock *Blk) { unsigned ArgIndex = BBInfo[Blk->getBlockID()].ProcessedPredecessors; assert(ArgIndex > 0 && ArgIndex < BB->numPredecessors()); - for (til::Variable *V : BB->arguments()) { - til::Phi *Ph = dyn_cast_or_null<til::Phi>(V->definition()); + for (til::SExpr *PE : BB->arguments()) { + til::Phi *Ph = dyn_cast_or_null<til::Phi>(PE); assert(Ph && "Expecting Phi Node."); assert(Ph->values()[ArgIndex] == nullptr && "Wrong index for back edge."); - assert(V->clangDecl() && "No local variable for Phi node."); - til::SExpr *E = lookupVarDecl(V->clangDecl()); + til::SExpr *E = lookupVarDecl(Ph->clangDecl()); assert(E && "Couldn't find local variable for Phi node."); - Ph->values()[ArgIndex] = E; } } @@ -899,8 +896,8 @@ void SExprBuilder::enterCFGBlockBody(const CFGBlock *B) { // Push those arguments onto the basic block. CurrentBB->arguments().reserve( static_cast<unsigned>(CurrentArguments.size()), Arena); - for (auto *V : CurrentArguments) - CurrentBB->addArgument(V); + for (auto *A : CurrentArguments) + CurrentBB->addArgument(A); } @@ -934,7 +931,7 @@ void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) { til::BasicBlock *BB = *It ? lookupBlock(*It) : nullptr; // TODO: set index unsigned Idx = BB ? BB->findPredecessorIndex(CurrentBB) : 0; - til::SExpr *Tm = new (Arena) til::Goto(BB, Idx); + auto *Tm = new (Arena) til::Goto(BB, Idx); CurrentBB->setTerminator(Tm); } else if (N == 2) { @@ -942,9 +939,8 @@ void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) { til::BasicBlock *BB1 = *It ? lookupBlock(*It) : nullptr; ++It; til::BasicBlock *BB2 = *It ? lookupBlock(*It) : nullptr; - 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); + // FIXME: make sure these arent' critical edges. + auto *Tm = new (Arena) til::Branch(C, BB1, BB2); CurrentBB->setTerminator(Tm); } } @@ -971,10 +967,9 @@ void SExprBuilder::exitCFGBlock(const CFGBlock *B) { void SExprBuilder::exitCFG(const CFGBlock *Last) { - for (auto *V : IncompleteArgs) { - til::Phi *Ph = dyn_cast<til::Phi>(V->definition()); - if (Ph && Ph->status() == til::Phi::PH_Incomplete) - simplifyIncompleteArg(V, Ph); + for (auto *Ph : IncompleteArgs) { + if (Ph->status() == til::Phi::PH_Incomplete) + simplifyIncompleteArg(Ph); } CurrentArguments.clear(); diff --git a/clang/lib/Analysis/ThreadSafetyTIL.cpp b/clang/lib/Analysis/ThreadSafetyTIL.cpp index 0bb7d4c..a150636 100644 --- a/clang/lib/Analysis/ThreadSafetyTIL.cpp +++ b/clang/lib/Analysis/ThreadSafetyTIL.cpp @@ -48,12 +48,20 @@ StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op) { } +SExpr* Future::force() { + Status = FS_evaluating; + Result = compute(); + Status = FS_done; + return Result; +} + + 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<Phi>(V->definition())) { + for (SExpr *E : Args) { + if (Phi* Ph = dyn_cast<Phi>(E)) { Ph->values().reserveCheck(1, Arena); Ph->values().push_back(nullptr); } @@ -61,105 +69,73 @@ unsigned BasicBlock::addPredecessor(BasicBlock *Pred) { return Idx; } + void BasicBlock::reservePredecessors(unsigned NumPreds) { Predecessors.reserve(NumPreds, Arena); - for (Variable *V : Args) { - if (Phi* Ph = dyn_cast<Phi>(V->definition())) { + for (SExpr *E : Args) { + if (Phi* Ph = dyn_cast<Phi>(E)) { 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. const SExpr *getCanonicalVal(const SExpr *E) { - while (auto *V = dyn_cast<Variable>(E)) { - const SExpr *D; - do { - if (V->kind() != Variable::VK_Let) - return V; - D = V->definition(); - auto *V2 = dyn_cast<Variable>(D); - if (V2) - V = V2; - else - break; - } while (true); - - if (ThreadSafetyTIL::isTrivial(D)) - return D; - - if (const Phi *Ph = dyn_cast<Phi>(D)) { + while (true) { + if (auto *V = dyn_cast<Variable>(E)) { + if (V->kind() == Variable::VK_Let) { + E = V->definition(); + continue; + } + } + if (const Phi *Ph = dyn_cast<Phi>(E)) { if (Ph->status() == Phi::PH_SingleVal) { E = Ph->values()[0]; continue; } } - return V; + break; } return E; } - // If E is a variable, then trace back through any aliases or redundant // Phi nodes to find the canonical definition. // The non-const version will simplify incomplete Phi nodes. SExpr *simplifyToCanonicalVal(SExpr *E) { - while (auto *V = dyn_cast<Variable>(E)) { - SExpr *D; - do { + while (true) { + if (auto *V = dyn_cast<Variable>(E)) { if (V->kind() != Variable::VK_Let) return V; - D = V->definition(); - auto *V2 = dyn_cast<Variable>(D); - if (V2) - V = V2; - else - break; - } while (true); - - if (ThreadSafetyTIL::isTrivial(D)) - return D; - - if (Phi *Ph = dyn_cast<Phi>(D)) { + // Eliminate redundant variables, e.g. x = y, or x = 5, + // but keep anything more complicated. + if (til::ThreadSafetyTIL::isTrivial(V->definition())) { + E = V->definition(); + continue; + } + return V; + } + if (auto *Ph = dyn_cast<Phi>(E)) { if (Ph->status() == Phi::PH_Incomplete) - simplifyIncompleteArg(V, Ph); - + simplifyIncompleteArg(Ph); + // Eliminate redundant Phi nodes. if (Ph->status() == Phi::PH_SingleVal) { E = Ph->values()[0]; continue; } } - return V; + return E; } - return E; } - // Trace the arguments of an incomplete Phi node to see if they have the same // canonical definition. If so, mark the Phi node as redundant. // getCanonicalVal() will recursively call simplifyIncompletePhi(). -void simplifyIncompleteArg(Variable *V, til::Phi *Ph) { +void simplifyIncompleteArg(til::Phi *Ph) { assert(Ph && Ph->status() == Phi::PH_Incomplete); // eliminate infinite recursion -- assume that this node is not redundant. @@ -168,18 +144,200 @@ void simplifyIncompleteArg(Variable *V, til::Phi *Ph) { SExpr *E0 = simplifyToCanonicalVal(Ph->values()[0]); for (unsigned i=1, n=Ph->values().size(); i<n; ++i) { SExpr *Ei = simplifyToCanonicalVal(Ph->values()[i]); - if (Ei == V) + if (Ei == Ph) continue; // Recursive reference to itself. Don't count. if (Ei != E0) { return; // Status is already set to MultiVal. } } Ph->setStatus(Phi::PH_SingleVal); - // Eliminate Redundant Phi node. - V->setDefinition(Ph->values()[0]); } +// Renumbers the arguments and instructions to have unique, sequential IDs. +int BasicBlock::renumberInstrs(int ID) { + for (auto *Arg : Args) + Arg->setID(this, ID++); + for (auto *Instr : Instrs) + Instr->setID(this, ID++); + TermInstr->setID(this, ID++); + return ID; +} + +// Sorts the CFGs blocks using a reverse post-order depth-first traversal. +// Each block will be written into the Blocks array in order, and its BlockID +// will be set to the index in the array. Sorting should start from the entry +// block, and ID should be the total number of blocks. +int BasicBlock::topologicalSort(SimpleArray<BasicBlock*>& Blocks, int ID) { + if (Visited) return ID; + Visited = 1; + for (auto *Block : successors()) + ID = Block->topologicalSort(Blocks, ID); + // set ID and update block array in place. + // We may lose pointers to unreachable blocks. + assert(ID > 0); + BlockID = --ID; + Blocks[BlockID] = this; + return ID; +} + +// Performs a reverse topological traversal, starting from the exit block and +// following back-edges. The dominator is serialized before any predecessors, +// which guarantees that all blocks are serialized after their dominator and +// before their post-dominator (because it's a reverse topological traversal). +// ID should be initially set to 0. +// +// This sort assumes that (1) dominators have been computed, (2) there are no +// critical edges, and (3) the entry block is reachable from the exit block +// and no blocks are accessable via traversal of back-edges from the exit that +// weren't accessable via forward edges from the entry. +int BasicBlock::topologicalFinalSort(SimpleArray<BasicBlock*>& Blocks, int ID) { + // Visited is assumed to have been set by the topologicalSort. This pass + // assumes !Visited means that we've visited this node before. + if (!Visited) return ID; + Visited = 0; + if (DominatorNode.Parent) + ID = DominatorNode.Parent->topologicalFinalSort(Blocks, ID); + for (auto *Pred : Predecessors) + ID = Pred->topologicalFinalSort(Blocks, ID); + assert(ID < Blocks.size()); + BlockID = ID++; + Blocks[BlockID] = this; + return ID; +} + +// Computes the immediate dominator of the current block. Assumes that all of +// its predecessors have already computed their dominators. This is achieved +// by visiting the nodes in topological order. +void BasicBlock::computeDominator() { + BasicBlock *Candidate = nullptr; + // Walk backwards from each predecessor to find the common dominator node. + for (auto *Pred : Predecessors) { + // Skip back-edges + if (Pred->BlockID >= BlockID) continue; + // If we don't yet have a candidate for dominator yet, take this one. + if (Candidate == nullptr) { + Candidate = Pred; + continue; + } + // Walk the alternate and current candidate back to find a common ancestor. + auto *Alternate = Pred; + while (Alternate != Candidate) { + if (Candidate->BlockID > Alternate->BlockID) + Candidate = Candidate->DominatorNode.Parent; + else + Alternate = Alternate->DominatorNode.Parent; + } + } + DominatorNode.Parent = Candidate; + DominatorNode.SizeOfSubTree = 1; +} + +// Computes the immediate post-dominator of the current block. Assumes that all +// of its successors have already computed their post-dominators. This is +// achieved visiting the nodes in reverse topological order. +void BasicBlock::computePostDominator() { + BasicBlock *Candidate = nullptr; + // Walk back from each predecessor to find the common post-dominator node. + for (auto *Succ : successors()) { + // Skip back-edges + if (Succ->BlockID <= BlockID) continue; + // If we don't yet have a candidate for post-dominator yet, take this one. + if (Candidate == nullptr) { + Candidate = Succ; + continue; + } + // Walk the alternate and current candidate back to find a common ancestor. + auto *Alternate = Succ; + while (Alternate != Candidate) { + if (Candidate->BlockID < Alternate->BlockID) + Candidate = Candidate->PostDominatorNode.Parent; + else + Alternate = Alternate->PostDominatorNode.Parent; + } + } + PostDominatorNode.Parent = Candidate; + PostDominatorNode.SizeOfSubTree = 1; +} + + +// Renumber instructions in all blocks +void SCFG::renumberInstrs() { + int InstrID = 0; + for (auto *Block : Blocks) + InstrID = Block->renumberInstrs(InstrID); +} + + +static inline void computeNodeSize(BasicBlock *B, + BasicBlock::TopologyNode BasicBlock::*TN) { + BasicBlock::TopologyNode *N = &(B->*TN); + if (N->Parent) { + BasicBlock::TopologyNode *P = &(N->Parent->*TN); + // Initially set ID relative to the (as yet uncomputed) parent ID + N->NodeID = P->SizeOfSubTree; + P->SizeOfSubTree += N->SizeOfSubTree; + } +} + +static inline void computeNodeID(BasicBlock *B, + BasicBlock::TopologyNode BasicBlock::*TN) { + BasicBlock::TopologyNode *N = &(B->*TN); + if (N->Parent) { + BasicBlock::TopologyNode *P = &(N->Parent->*TN); + N->NodeID += P->NodeID; // Fix NodeIDs relative to starting node. + } +} + + +// Normalizes a CFG. Normalization has a few major components: +// 1) Removing unreachable blocks. +// 2) Computing dominators and post-dominators +// 3) Topologically sorting the blocks into the "Blocks" array. +void SCFG::computeNormalForm() { + // Topologically sort the blocks starting from the entry block. + int NumUnreachableBlocks = Entry->topologicalSort(Blocks, Blocks.size()); + if (NumUnreachableBlocks > 0) { + // If there were unreachable blocks shift everything down, and delete them. + for (size_t I = NumUnreachableBlocks, E = Blocks.size(); I < E; ++I) { + size_t NI = I - NumUnreachableBlocks; + Blocks[NI] = Blocks[I]; + Blocks[NI]->BlockID = NI; + // FIXME: clean up predecessor pointers to unreachable blocks? + } + Blocks.drop(NumUnreachableBlocks); + } + + // Compute dominators. + for (auto *Block : Blocks) + Block->computeDominator(); + + // Once dominators have been computed, the final sort may be performed. + int NumBlocks = Exit->topologicalFinalSort(Blocks, 0); + assert(NumBlocks == Blocks.size()); + (void) NumBlocks; + + // Renumber the instructions now that we have a final sort. + renumberInstrs(); + + // Compute post-dominators and compute the sizes of each node in the + // dominator tree. + for (auto *Block : Blocks.reverse()) { + Block->computePostDominator(); + computeNodeSize(Block, &BasicBlock::DominatorNode); + } + // Compute the sizes of each node in the post-dominator tree and assign IDs in + // the dominator tree. + for (auto *Block : Blocks) { + computeNodeID(Block, &BasicBlock::DominatorNode); + computeNodeSize(Block, &BasicBlock::PostDominatorNode); + } + // Assign IDs in the post-dominator tree. + for (auto *Block : Blocks.reverse()) { + computeNodeID(Block, &BasicBlock::PostDominatorNode); + } +} + } // end namespace til } // end namespace threadSafety } // end namespace clang |