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