16bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines//===- ThreadSafetyTIL.cpp -------------------------------------*- C++ --*-===// 26bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 36bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// The LLVM Compiler Infrastructure 46bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 56bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// This file is distributed under the University of Illinois Open Source 66bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// License. See LICENSE.TXT in the llvm repository for details. 76bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 86bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines//===----------------------------------------------------------------------===// 96bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include "clang/Analysis/Analyses/ThreadSafetyTIL.h" 116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" 126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace clang { 146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace threadSafety { 156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace til { 166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen HinesStringRef getUnaryOpcodeString(TIL_UnaryOpcode Op) { 196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines switch (Op) { 206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case UOP_Minus: return "-"; 216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case UOP_BitNot: return "~"; 226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case UOP_LogicNot: return "!"; 236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ""; 256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen HinesStringRef getBinaryOpcodeString(TIL_BinaryOpcode Op) { 296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines switch (Op) { 306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_Mul: return "*"; 316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_Div: return "/"; 326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_Rem: return "%"; 336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_Add: return "+"; 346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_Sub: return "-"; 356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_Shl: return "<<"; 366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_Shr: return ">>"; 376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_BitAnd: return "&"; 386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_BitXor: return "^"; 396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_BitOr: return "|"; 406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_Eq: return "=="; 416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_Neq: return "!="; 426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_Lt: return "<"; 436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_Leq: return "<="; 446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_LogicAnd: return "&&"; 456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case BOP_LogicOr: return "||"; 466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ""; 486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 51ef8225444452a1486bd721f3285301fe84643b00Stephen Hinesunsigned BasicBlock::addPredecessor(BasicBlock *Pred) { 52ef8225444452a1486bd721f3285301fe84643b00Stephen Hines unsigned Idx = Predecessors.size(); 53ef8225444452a1486bd721f3285301fe84643b00Stephen Hines Predecessors.reserveCheck(1, Arena); 54ef8225444452a1486bd721f3285301fe84643b00Stephen Hines Predecessors.push_back(Pred); 55ef8225444452a1486bd721f3285301fe84643b00Stephen Hines for (Variable *V : Args) { 56ef8225444452a1486bd721f3285301fe84643b00Stephen Hines if (Phi* Ph = dyn_cast<Phi>(V->definition())) { 57ef8225444452a1486bd721f3285301fe84643b00Stephen Hines Ph->values().reserveCheck(1, Arena); 58ef8225444452a1486bd721f3285301fe84643b00Stephen Hines Ph->values().push_back(nullptr); 59ef8225444452a1486bd721f3285301fe84643b00Stephen Hines } 60ef8225444452a1486bd721f3285301fe84643b00Stephen Hines } 61ef8225444452a1486bd721f3285301fe84643b00Stephen Hines return Idx; 62ef8225444452a1486bd721f3285301fe84643b00Stephen Hines} 63ef8225444452a1486bd721f3285301fe84643b00Stephen Hines 64ef8225444452a1486bd721f3285301fe84643b00Stephen Hinesvoid BasicBlock::reservePredecessors(unsigned NumPreds) { 65ef8225444452a1486bd721f3285301fe84643b00Stephen Hines Predecessors.reserve(NumPreds, Arena); 66ef8225444452a1486bd721f3285301fe84643b00Stephen Hines for (Variable *V : Args) { 67ef8225444452a1486bd721f3285301fe84643b00Stephen Hines if (Phi* Ph = dyn_cast<Phi>(V->definition())) { 68ef8225444452a1486bd721f3285301fe84643b00Stephen Hines Ph->values().reserve(NumPreds, Arena); 69ef8225444452a1486bd721f3285301fe84643b00Stephen Hines } 70ef8225444452a1486bd721f3285301fe84643b00Stephen Hines } 71ef8225444452a1486bd721f3285301fe84643b00Stephen Hines} 72ef8225444452a1486bd721f3285301fe84643b00Stephen Hines 73ef8225444452a1486bd721f3285301fe84643b00Stephen Hinesvoid BasicBlock::renumberVars() { 74ef8225444452a1486bd721f3285301fe84643b00Stephen Hines unsigned VID = 0; 75ef8225444452a1486bd721f3285301fe84643b00Stephen Hines for (Variable *V : Args) { 76ef8225444452a1486bd721f3285301fe84643b00Stephen Hines V->setID(BlockID, VID++); 77ef8225444452a1486bd721f3285301fe84643b00Stephen Hines } 78ef8225444452a1486bd721f3285301fe84643b00Stephen Hines for (Variable *V : Instrs) { 79ef8225444452a1486bd721f3285301fe84643b00Stephen Hines V->setID(BlockID, VID++); 80ef8225444452a1486bd721f3285301fe84643b00Stephen Hines } 81ef8225444452a1486bd721f3285301fe84643b00Stephen Hines} 82ef8225444452a1486bd721f3285301fe84643b00Stephen Hines 83ef8225444452a1486bd721f3285301fe84643b00Stephen Hinesvoid SCFG::renumberVars() { 84ef8225444452a1486bd721f3285301fe84643b00Stephen Hines for (BasicBlock *B : Blocks) { 85ef8225444452a1486bd721f3285301fe84643b00Stephen Hines B->renumberVars(); 86ef8225444452a1486bd721f3285301fe84643b00Stephen Hines } 87ef8225444452a1486bd721f3285301fe84643b00Stephen Hines} 88ef8225444452a1486bd721f3285301fe84643b00Stephen Hines 89ef8225444452a1486bd721f3285301fe84643b00Stephen Hines 90ef8225444452a1486bd721f3285301fe84643b00Stephen Hines 916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// If E is a variable, then trace back through any aliases or redundant 936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// Phi nodes to find the canonical definition. 946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen HinesSExpr *getCanonicalVal(SExpr *E) { 956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines while (auto *V = dyn_cast<Variable>(E)) { 966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SExpr *D; 976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines do { 986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (V->kind() != Variable::VK_Let) 996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return V; 1006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines D = V->definition(); 1016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines auto *V2 = dyn_cast<Variable>(D); 1026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (V2) 1036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines V = V2; 1046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines else 1056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines break; 1066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } while (true); 1076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (ThreadSafetyTIL::isTrivial(D)) 1096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return D; 1106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Phi *Ph = dyn_cast<Phi>(D)) { 1126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Ph->status() == Phi::PH_Incomplete) 1136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines simplifyIncompleteArg(V, Ph); 1146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Ph->status() == Phi::PH_SingleVal) { 1166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines E = Ph->values()[0]; 1176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines continue; 1186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return V; 1216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return E; 1236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 1246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// Trace the arguments of an incomplete Phi node to see if they have the same 1276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// canonical definition. If so, mark the Phi node as redundant. 1286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// getCanonicalVal() will recursively call simplifyIncompletePhi(). 1296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesvoid simplifyIncompleteArg(Variable *V, til::Phi *Ph) { 1306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(Ph && Ph->status() == Phi::PH_Incomplete); 1316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // eliminate infinite recursion -- assume that this node is not redundant. 1336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Ph->setStatus(Phi::PH_MultiVal); 1346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SExpr *E0 = getCanonicalVal(Ph->values()[0]); 1366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines for (unsigned i=1, n=Ph->values().size(); i<n; ++i) { 1376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SExpr *Ei = getCanonicalVal(Ph->values()[i]); 1386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Ei == V) 1396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines continue; // Recursive reference to itself. Don't count. 1406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Ei != E0) { 1416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return; // Status is already set to MultiVal. 1426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Ph->setStatus(Phi::PH_SingleVal); 1456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Eliminate Redundant Phi node. 1466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines V->setDefinition(Ph->values()[0]); 1476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 1486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace til 1516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace threadSafety 1526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace clang 1536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 154