contrib/llvm/tools/clang/lib/Analysis/ThreadSafetyTIL.cpp

   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