332 lines · cpp
1//===- ThreadSafetyTIL.cpp ------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"10#include "clang/Basic/LLVM.h"11#include <cassert>12#include <cstddef>13 14using namespace clang;15using namespace threadSafety;16using namespace til;17 18StringRef til::getUnaryOpcodeString(TIL_UnaryOpcode Op) {19 switch (Op) {20 case UOP_Minus: return "-";21 case UOP_BitNot: return "~";22 case UOP_LogicNot: return "!";23 }24 return {};25}26 27StringRef til::getBinaryOpcodeString(TIL_BinaryOpcode Op) {28 switch (Op) {29 case BOP_Mul: return "*";30 case BOP_Div: return "/";31 case BOP_Rem: return "%";32 case BOP_Add: return "+";33 case BOP_Sub: return "-";34 case BOP_Shl: return "<<";35 case BOP_Shr: return ">>";36 case BOP_BitAnd: return "&";37 case BOP_BitXor: return "^";38 case BOP_BitOr: return "|";39 case BOP_Eq: return "==";40 case BOP_Neq: return "!=";41 case BOP_Lt: return "<";42 case BOP_Leq: return "<=";43 case BOP_Cmp: return "<=>";44 case BOP_LogicAnd: return "&&";45 case BOP_LogicOr: return "||";46 }47 return {};48}49 50SExpr* Future::force() {51 Status = FS_evaluating;52 Result = compute();53 Status = FS_done;54 return Result;55}56 57unsigned BasicBlock::addPredecessor(BasicBlock *Pred) {58 unsigned Idx = Predecessors.size();59 Predecessors.reserveCheck(1, Arena);60 Predecessors.push_back(Pred);61 for (auto *E : Args) {62 if (auto *Ph = dyn_cast<Phi>(E)) {63 Ph->values().reserveCheck(1, Arena);64 Ph->values().push_back(nullptr);65 }66 }67 return Idx;68}69 70void BasicBlock::reservePredecessors(unsigned NumPreds) {71 Predecessors.reserve(NumPreds, Arena);72 for (auto *E : Args) {73 if (auto *Ph = dyn_cast<Phi>(E)) {74 Ph->values().reserve(NumPreds, Arena);75 }76 }77}78 79// If E is a variable, then trace back through any aliases or redundant80// Phi nodes to find the canonical definition.81const SExpr *til::getCanonicalVal(const SExpr *E) {82 while (true) {83 if (const auto *V = dyn_cast<Variable>(E)) {84 if (V->kind() == Variable::VK_Let) {85 E = V->definition();86 continue;87 }88 }89 if (const auto *Ph = dyn_cast<Phi>(E)) {90 if (Ph->status() == Phi::PH_SingleVal) {91 E = Ph->values()[0];92 continue;93 }94 }95 break;96 }97 return E;98}99 100// If E is a variable, then trace back through any aliases or redundant101// Phi nodes to find the canonical definition.102// The non-const version will simplify incomplete Phi nodes.103SExpr *til::simplifyToCanonicalVal(SExpr *E) {104 while (true) {105 if (auto *V = dyn_cast<Variable>(E)) {106 if (V->kind() != Variable::VK_Let)107 return V;108 // Eliminate redundant variables, e.g. x = y, or x = 5,109 // but keep anything more complicated.110 if (til::ThreadSafetyTIL::isTrivial(V->definition())) {111 E = V->definition();112 continue;113 }114 return V;115 }116 if (auto *Ph = dyn_cast<Phi>(E)) {117 if (Ph->status() == Phi::PH_Incomplete)118 simplifyIncompleteArg(Ph);119 // Eliminate redundant Phi nodes.120 if (Ph->status() == Phi::PH_SingleVal) {121 E = Ph->values()[0];122 continue;123 }124 }125 return E;126 }127}128 129// Trace the arguments of an incomplete Phi node to see if they have the same130// canonical definition. If so, mark the Phi node as redundant.131// getCanonicalVal() will recursively call simplifyIncompletePhi().132void til::simplifyIncompleteArg(til::Phi *Ph) {133 assert(Ph && Ph->status() == Phi::PH_Incomplete);134 135 // eliminate infinite recursion -- assume that this node is not redundant.136 Ph->setStatus(Phi::PH_MultiVal);137 138 SExpr *E0 = simplifyToCanonicalVal(Ph->values()[0]);139 for (unsigned i = 1, n = Ph->values().size(); i < n; ++i) {140 SExpr *Ei = simplifyToCanonicalVal(Ph->values()[i]);141 if (Ei == Ph)142 continue; // Recursive reference to itself. Don't count.143 if (Ei != E0) {144 return; // Status is already set to MultiVal.145 }146 }147 Ph->setStatus(Phi::PH_SingleVal);148}149 150// Renumbers the arguments and instructions to have unique, sequential IDs.151unsigned BasicBlock::renumberInstrs(unsigned ID) {152 for (auto *Arg : Args)153 Arg->setID(this, ID++);154 for (auto *Instr : Instrs)155 Instr->setID(this, ID++);156 TermInstr->setID(this, ID++);157 return ID;158}159 160// Sorts the CFGs blocks using a reverse post-order depth-first traversal.161// Each block will be written into the Blocks array in order, and its BlockID162// will be set to the index in the array. Sorting should start from the entry163// block, and ID should be the total number of blocks.164unsigned BasicBlock::topologicalSort(SimpleArray<BasicBlock *> &Blocks,165 unsigned ID) {166 if (Visited) return ID;167 Visited = true;168 for (auto *Block : successors())169 ID = Block->topologicalSort(Blocks, ID);170 // set ID and update block array in place.171 // We may lose pointers to unreachable blocks.172 assert(ID > 0);173 BlockID = --ID;174 Blocks[BlockID] = this;175 return ID;176}177 178// Performs a reverse topological traversal, starting from the exit block and179// following back-edges. The dominator is serialized before any predecessors,180// which guarantees that all blocks are serialized after their dominator and181// before their post-dominator (because it's a reverse topological traversal).182// ID should be initially set to 0.183//184// This sort assumes that (1) dominators have been computed, (2) there are no185// critical edges, and (3) the entry block is reachable from the exit block186// and no blocks are accessible via traversal of back-edges from the exit that187// weren't accessible via forward edges from the entry.188unsigned BasicBlock::topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks,189 unsigned ID) {190 // Visited is assumed to have been set by the topologicalSort. This pass191 // assumes !Visited means that we've visited this node before.192 if (!Visited) return ID;193 Visited = false;194 if (DominatorNode.Parent)195 ID = DominatorNode.Parent->topologicalFinalSort(Blocks, ID);196 for (auto *Pred : Predecessors)197 ID = Pred->topologicalFinalSort(Blocks, ID);198 assert(static_cast<size_t>(ID) < Blocks.size());199 BlockID = ID++;200 Blocks[BlockID] = this;201 return ID;202}203 204// Computes the immediate dominator of the current block. Assumes that all of205// its predecessors have already computed their dominators. This is achieved206// by visiting the nodes in topological order.207void BasicBlock::computeDominator() {208 BasicBlock *Candidate = nullptr;209 // Walk backwards from each predecessor to find the common dominator node.210 for (auto *Pred : Predecessors) {211 // Skip back-edges212 if (Pred->BlockID >= BlockID) continue;213 // If we don't yet have a candidate for dominator yet, take this one.214 if (Candidate == nullptr) {215 Candidate = Pred;216 continue;217 }218 // Walk the alternate and current candidate back to find a common ancestor.219 auto *Alternate = Pred;220 while (Alternate != Candidate) {221 if (Candidate->BlockID > Alternate->BlockID)222 Candidate = Candidate->DominatorNode.Parent;223 else224 Alternate = Alternate->DominatorNode.Parent;225 }226 }227 DominatorNode.Parent = Candidate;228 DominatorNode.SizeOfSubTree = 1;229}230 231// Computes the immediate post-dominator of the current block. Assumes that all232// of its successors have already computed their post-dominators. This is233// achieved visiting the nodes in reverse topological order.234void BasicBlock::computePostDominator() {235 BasicBlock *Candidate = nullptr;236 // Walk back from each predecessor to find the common post-dominator node.237 for (auto *Succ : successors()) {238 // Skip back-edges239 if (Succ->BlockID <= BlockID) continue;240 // If we don't yet have a candidate for post-dominator yet, take this one.241 if (Candidate == nullptr) {242 Candidate = Succ;243 continue;244 }245 // Walk the alternate and current candidate back to find a common ancestor.246 auto *Alternate = Succ;247 while (Alternate != Candidate) {248 if (Candidate->BlockID < Alternate->BlockID)249 Candidate = Candidate->PostDominatorNode.Parent;250 else251 Alternate = Alternate->PostDominatorNode.Parent;252 }253 }254 PostDominatorNode.Parent = Candidate;255 PostDominatorNode.SizeOfSubTree = 1;256}257 258// Renumber instructions in all blocks259void SCFG::renumberInstrs() {260 unsigned InstrID = 0;261 for (auto *Block : Blocks)262 InstrID = Block->renumberInstrs(InstrID);263}264 265static inline void computeNodeSize(BasicBlock *B,266 BasicBlock::TopologyNode BasicBlock::*TN) {267 BasicBlock::TopologyNode *N = &(B->*TN);268 if (N->Parent) {269 BasicBlock::TopologyNode *P = &(N->Parent->*TN);270 // Initially set ID relative to the (as yet uncomputed) parent ID271 N->NodeID = P->SizeOfSubTree;272 P->SizeOfSubTree += N->SizeOfSubTree;273 }274}275 276static inline void computeNodeID(BasicBlock *B,277 BasicBlock::TopologyNode BasicBlock::*TN) {278 BasicBlock::TopologyNode *N = &(B->*TN);279 if (N->Parent) {280 BasicBlock::TopologyNode *P = &(N->Parent->*TN);281 N->NodeID += P->NodeID; // Fix NodeIDs relative to starting node.282 }283}284 285// Normalizes a CFG. Normalization has a few major components:286// 1) Removing unreachable blocks.287// 2) Computing dominators and post-dominators288// 3) Topologically sorting the blocks into the "Blocks" array.289void SCFG::computeNormalForm() {290 // Topologically sort the blocks starting from the entry block.291 unsigned NumUnreachableBlocks = Entry->topologicalSort(Blocks, Blocks.size());292 if (NumUnreachableBlocks > 0) {293 // If there were unreachable blocks shift everything down, and delete them.294 for (unsigned I = NumUnreachableBlocks, E = Blocks.size(); I < E; ++I) {295 unsigned NI = I - NumUnreachableBlocks;296 Blocks[NI] = Blocks[I];297 Blocks[NI]->BlockID = NI;298 // FIXME: clean up predecessor pointers to unreachable blocks?299 }300 Blocks.drop(NumUnreachableBlocks);301 }302 303 // Compute dominators.304 for (auto *Block : Blocks)305 Block->computeDominator();306 307 // Once dominators have been computed, the final sort may be performed.308 unsigned NumBlocks = Exit->topologicalFinalSort(Blocks, 0);309 assert(static_cast<size_t>(NumBlocks) == Blocks.size());310 (void) NumBlocks;311 312 // Renumber the instructions now that we have a final sort.313 renumberInstrs();314 315 // Compute post-dominators and compute the sizes of each node in the316 // dominator tree.317 for (auto *Block : Blocks.reverse()) {318 Block->computePostDominator();319 computeNodeSize(Block, &BasicBlock::DominatorNode);320 }321 // Compute the sizes of each node in the post-dominator tree and assign IDs in322 // the dominator tree.323 for (auto *Block : Blocks) {324 computeNodeID(Block, &BasicBlock::DominatorNode);325 computeNodeSize(Block, &BasicBlock::PostDominatorNode);326 }327 // Assign IDs in the post-dominator tree.328 for (auto *Block : Blocks.reverse()) {329 computeNodeID(Block, &BasicBlock::PostDominatorNode);330 }331}332