1 //===- ThreadSafetyTIL.cpp -------------------------------------*- C++ --*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT in the llvm repository for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" 11 #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" 12 13 namespace clang { 14 namespace threadSafety { 15 namespace til { 16 17 18 StringRef 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 27 28 StringRef 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_LogicAnd: return "&&"; 45 case BOP_LogicOr: return "||"; 46 } 47 return ""; 48 } 49 50 51 unsigned BasicBlock::addPredecessor(BasicBlock *Pred) { 52 unsigned Idx = Predecessors.size(); 53 Predecessors.reserveCheck(1, Arena); 54 Predecessors.push_back(Pred); 55 for (Variable *V : Args) { 56 if (Phi* Ph = dyn_cast<Phi>(V->definition())) { 57 Ph->values().reserveCheck(1, Arena); 58 Ph->values().push_back(nullptr); 59 } 60 } 61 return Idx; 62 } 63 64 void BasicBlock::reservePredecessors(unsigned NumPreds) { 65 Predecessors.reserve(NumPreds, Arena); 66 for (Variable *V : Args) { 67 if (Phi* Ph = dyn_cast<Phi>(V->definition())) { 68 Ph->values().reserve(NumPreds, Arena); 69 } 70 } 71 } 72 73 void BasicBlock::renumberVars() { 74 unsigned VID = 0; 75 for (Variable *V : Args) { 76 V->setID(BlockID, VID++); 77 } 78 for (Variable *V : Instrs) { 79 V->setID(BlockID, VID++); 80 } 81 } 82 83 void SCFG::renumberVars() { 84 for (BasicBlock *B : Blocks) { 85 B->renumberVars(); 86 } 87 } 88 89 90 91 92 // If E is a variable, then trace back through any aliases or redundant 93 // Phi nodes to find the canonical definition. 94 SExpr *getCanonicalVal(SExpr *E) { 95 while (auto *V = dyn_cast<Variable>(E)) { 96 SExpr *D; 97 do { 98 if (V->kind() != Variable::VK_Let) 99 return V; 100 D = V->definition(); 101 auto *V2 = dyn_cast<Variable>(D); 102 if (V2) 103 V = V2; 104 else 105 break; 106 } while (true); 107 108 if (ThreadSafetyTIL::isTrivial(D)) 109 return D; 110 111 if (Phi *Ph = dyn_cast<Phi>(D)) { 112 if (Ph->status() == Phi::PH_Incomplete) 113 simplifyIncompleteArg(V, Ph); 114 115 if (Ph->status() == Phi::PH_SingleVal) { 116 E = Ph->values()[0]; 117 continue; 118 } 119 } 120 return V; 121 } 122 return E; 123 } 124 125 126 // Trace the arguments of an incomplete Phi node to see if they have the same 127 // canonical definition. If so, mark the Phi node as redundant. 128 // getCanonicalVal() will recursively call simplifyIncompletePhi(). 129 void simplifyIncompleteArg(Variable *V, til::Phi *Ph) { 130 assert(Ph && Ph->status() == Phi::PH_Incomplete); 131 132 // eliminate infinite recursion -- assume that this node is not redundant. 133 Ph->setStatus(Phi::PH_MultiVal); 134 135 SExpr *E0 = getCanonicalVal(Ph->values()[0]); 136 for (unsigned i=1, n=Ph->values().size(); i<n; ++i) { 137 SExpr *Ei = getCanonicalVal(Ph->values()[i]); 138 if (Ei == V) 139 continue; // Recursive reference to itself. Don't count. 140 if (Ei != E0) { 141 return; // Status is already set to MultiVal. 142 } 143 } 144 Ph->setStatus(Phi::PH_SingleVal); 145 // Eliminate Redundant Phi node. 146 V->setDefinition(Ph->values()[0]); 147 } 148 149 150 } // end namespace til 151 } // end namespace threadSafety 152 } // end namespace clang 153 154