| //===- ThreadSafetyTIL.cpp -------------------------------------*- C++ --*-===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT in the llvm repository for details. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" |
| #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" |
| using namespace clang; |
| using namespace threadSafety; |
| using namespace til; |
| |
| StringRef til::getUnaryOpcodeString(TIL_UnaryOpcode Op) { |
| switch (Op) { |
| case UOP_Minus: return "-"; |
| case UOP_BitNot: return "~"; |
| case UOP_LogicNot: return "!"; |
| } |
| return ""; |
| } |
| |
| StringRef til::getBinaryOpcodeString(TIL_BinaryOpcode Op) { |
| switch (Op) { |
| case BOP_Mul: return "*"; |
| case BOP_Div: return "/"; |
| case BOP_Rem: return "%"; |
| case BOP_Add: return "+"; |
| case BOP_Sub: return "-"; |
| case BOP_Shl: return "<<"; |
| case BOP_Shr: return ">>"; |
| case BOP_BitAnd: return "&"; |
| case BOP_BitXor: return "^"; |
| case BOP_BitOr: return "|"; |
| case BOP_Eq: return "=="; |
| case BOP_Neq: return "!="; |
| case BOP_Lt: return "<"; |
| case BOP_Leq: return "<="; |
| case BOP_Cmp: return "<=>"; |
| case BOP_LogicAnd: return "&&"; |
| case BOP_LogicOr: return "||"; |
| } |
| return ""; |
| } |
| |
| |
| 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 (SExpr *E : Args) { |
| if (Phi* Ph = dyn_cast<Phi>(E)) { |
| Ph->values().reserveCheck(1, Arena); |
| Ph->values().push_back(nullptr); |
| } |
| } |
| return Idx; |
| } |
| |
| |
| void BasicBlock::reservePredecessors(unsigned NumPreds) { |
| Predecessors.reserve(NumPreds, Arena); |
| for (SExpr *E : Args) { |
| if (Phi* Ph = dyn_cast<Phi>(E)) { |
| Ph->values().reserve(NumPreds, Arena); |
| } |
| } |
| } |
| |
| |
| // If E is a variable, then trace back through any aliases or redundant |
| // Phi nodes to find the canonical definition. |
| const SExpr *til::getCanonicalVal(const SExpr *E) { |
| 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; |
| } |
| } |
| 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 *til::simplifyToCanonicalVal(SExpr *E) { |
| while (true) { |
| if (auto *V = dyn_cast<Variable>(E)) { |
| if (V->kind() != Variable::VK_Let) |
| return V; |
| // 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(Ph); |
| // Eliminate redundant Phi nodes. |
| if (Ph->status() == Phi::PH_SingleVal) { |
| E = Ph->values()[0]; |
| continue; |
| } |
| } |
| 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 til::simplifyIncompleteArg(til::Phi *Ph) { |
| assert(Ph && Ph->status() == Phi::PH_Incomplete); |
| |
| // eliminate infinite recursion -- assume that this node is not redundant. |
| Ph->setStatus(Phi::PH_MultiVal); |
| |
| 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 == Ph) |
| continue; // Recursive reference to itself. Don't count. |
| if (Ei != E0) { |
| return; // Status is already set to MultiVal. |
| } |
| } |
| Ph->setStatus(Phi::PH_SingleVal); |
| } |
| |
| |
| // 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 = true; |
| 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 accessible via traversal of back-edges from the exit that |
| // weren't accessible 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 = false; |
| if (DominatorNode.Parent) |
| ID = DominatorNode.Parent->topologicalFinalSort(Blocks, ID); |
| for (auto *Pred : Predecessors) |
| ID = Pred->topologicalFinalSort(Blocks, ID); |
| assert(static_cast<size_t>(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(static_cast<size_t>(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); |
| } |
| } |