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
13namespace clang {
14namespace threadSafety {
15namespace til {
16
17
18StringRef 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
28StringRef 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
51unsigned 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
64void 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
73void 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
83void 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.
94SExpr *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().
129void 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