Home | History | Annotate | Download | only in Analysis 
      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