summaryrefslogtreecommitdiff
path: root/clang/lib/Analysis/ThreadSafetyTIL.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'clang/lib/Analysis/ThreadSafetyTIL.cpp')
-rw-r--r--clang/lib/Analysis/ThreadSafetyTIL.cpp332
1 files changed, 332 insertions, 0 deletions
diff --git a/clang/lib/Analysis/ThreadSafetyTIL.cpp b/clang/lib/Analysis/ThreadSafetyTIL.cpp
new file mode 100644
index 000000000000..652f953d2a6d
--- /dev/null
+++ b/clang/lib/Analysis/ThreadSafetyTIL.cpp
@@ -0,0 +1,332 @@
+//===- 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 "llvm/Support/Casting.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);
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 01:15:23 +0000