| //===- ThreadSafetyTIL.cpp ------------------------------------------------===// | |
| // | |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |
| // See https://llvm.org/LICENSE.txt for license information. | |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |
| // | |
| //===----------------------------------------------------------------------===// | |
| #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" | |
| #include "clang/Basic/LLVM.h" | |
| #include <cassert> | |
| #include <cstddef> | |
| 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 (auto *E : Args) { | |
| if (auto *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 (auto *E : Args) { | |
| if (auto *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 (const auto *V = dyn_cast<Variable>(E)) { | |
| if (V->kind() == Variable::VK_Let) { | |
| E = V->definition(); | |
| continue; | |
| } | |
| } | |
| if (const auto *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. | |
| unsigned BasicBlock::renumberInstrs(unsigned 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. | |
| unsigned BasicBlock::topologicalSort(SimpleArray<BasicBlock *> &Blocks, | |
| unsigned 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. | |
| unsigned BasicBlock::topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks, | |
| unsigned 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() { | |
| unsigned 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. | |
| unsigned NumUnreachableBlocks = Entry->topologicalSort(Blocks, Blocks.size()); | |
| if (NumUnreachableBlocks > 0) { | |
| // If there were unreachable blocks shift everything down, and delete them. | |
| for (unsigned I = NumUnreachableBlocks, E = Blocks.size(); I < E; ++I) { | |
| unsigned 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. | |
| unsigned 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); | |
| } | |
| } |