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