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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
|
//===- IPModRef.cpp - Compute IP Mod/Ref information ------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// See high-level comments in IPModRef.h
//
//===----------------------------------------------------------------------===//
#include "IPModRef.h"
#include "llvm/Analysis/DataStructure/DataStructure.h"
#include "llvm/Analysis/DataStructure/DSGraph.h"
#include "llvm/Module.h"
#include "llvm/Function.h"
#include "llvm/iMemory.h"
#include "llvm/iOther.h"
#include "Support/Statistic.h"
#include "Support/STLExtras.h"
#include "Support/StringExtras.h"
#include <vector>
namespace llvm {
//----------------------------------------------------------------------------
// Private constants and data
//----------------------------------------------------------------------------
static RegisterAnalysis<IPModRef>
Z("ipmodref", "Interprocedural mod/ref analysis");
//----------------------------------------------------------------------------
// class ModRefInfo
//----------------------------------------------------------------------------
void ModRefInfo::print(std::ostream &O,
const std::string& sprefix) const
{
O << sprefix << "Modified nodes = " << modNodeSet;
O << sprefix << "Referenced nodes = " << refNodeSet;
}
void ModRefInfo::dump() const
{
print(std::cerr);
}
//----------------------------------------------------------------------------
// class FunctionModRefInfo
//----------------------------------------------------------------------------
// This constructor computes a node numbering for the TD graph.
//
FunctionModRefInfo::FunctionModRefInfo(const Function& func,
IPModRef& ipmro,
DSGraph* tdgClone)
: F(func), IPModRefObj(ipmro),
funcTDGraph(tdgClone),
funcModRefInfo(tdgClone->getGraphSize())
{
unsigned i = 0;
for (DSGraph::node_iterator NI = funcTDGraph->node_begin(),
E = funcTDGraph->node_end(); NI != E; ++NI)
NodeIds[*NI] = i++;
}
FunctionModRefInfo::~FunctionModRefInfo()
{
for(std::map<const Instruction*, ModRefInfo*>::iterator
I=callSiteModRefInfo.begin(), E=callSiteModRefInfo.end(); I != E; ++I)
delete(I->second);
// Empty map just to make problems easier to track down
callSiteModRefInfo.clear();
delete funcTDGraph;
}
unsigned FunctionModRefInfo::getNodeId(const Value* value) const {
return getNodeId(funcTDGraph->getNodeForValue(const_cast<Value*>(value))
.getNode());
}
// Compute Mod/Ref bit vectors for the entire function.
// These are simply copies of the Read/Write flags from the nodes of
// the top-down DS graph.
//
void FunctionModRefInfo::computeModRef(const Function &func)
{
// Mark all nodes in the graph that are marked MOD as being mod
// and all those marked REF as being ref.
unsigned i = 0;
for (DSGraph::node_iterator NI = funcTDGraph->node_begin(),
E = funcTDGraph->node_end(); NI != E; ++NI, ++i) {
if ((*NI)->isModified()) funcModRefInfo.setNodeIsMod(i);
if ((*NI)->isRead()) funcModRefInfo.setNodeIsRef(i);
}
// Compute the Mod/Ref info for all call sites within the function.
// The call sites are recorded in the TD graph.
const std::vector<DSCallSite>& callSites = funcTDGraph->getFunctionCalls();
for (unsigned i = 0, N = callSites.size(); i < N; ++i)
computeModRef(callSites[i].getCallSite());
}
// ResolveCallSiteModRefInfo - This method performs the following actions:
//
// 1. It clones the top-down graph for the current function
// 2. It clears all of the mod/ref bits in the cloned graph
// 3. It then merges the bottom-up graph(s) for the specified call-site into
// the clone (bringing new mod/ref bits).
// 4. It returns the clone, and a mapping of nodes from the original TDGraph to
// the cloned graph with Mod/Ref info for the callsite.
//
// NOTE: Because this clones a dsgraph and returns it, the caller is responsible
// for deleting the returned graph!
// NOTE: This method may return a null pointer if it is unable to determine the
// requested information (because the call site calls an external
// function or we cannot determine the complete set of functions invoked).
//
DSGraph* FunctionModRefInfo::ResolveCallSiteModRefInfo(CallSite CS,
hash_map<const DSNode*, DSNodeHandle> &NodeMap)
{
// Step #0: Quick check if we are going to fail anyway: avoid
// all the graph cloning and map copying in steps #1 and #2.
//
if (const Function *F = CS.getCalledFunction()) {
if (F->isExternal())
return 0; // We cannot compute Mod/Ref info for this callsite...
} else {
// Eventually, should check here if any callee is external.
// For now we are not handling this case anyway.
std::cerr << "IP Mod/Ref indirect call not implemented yet: "
<< "Being conservative\n";
return 0; // We cannot compute Mod/Ref info for this callsite...
}
// Step #1: Clone the top-down graph...
DSGraph *Result = new DSGraph(*funcTDGraph, NodeMap);
// Step #2: Clear Mod/Ref information...
Result->maskNodeTypes(~(DSNode::Modified | DSNode::Read));
// Step #3: clone the bottom up graphs for the callees into the caller graph
if (Function *F = CS.getCalledFunction())
{
assert(!F->isExternal());
// Build up a DSCallSite for our invocation point here...
// If the call returns a value, make sure to merge the nodes...
DSNodeHandle RetVal;
if (DS::isPointerType(CS.getInstruction()->getType()))
RetVal = Result->getNodeForValue(CS.getInstruction());
// Populate the arguments list...
std::vector<DSNodeHandle> Args;
for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
I != E; ++I)
if (DS::isPointerType((*I)->getType()))
Args.push_back(Result->getNodeForValue(*I));
// Build the call site...
DSCallSite NCS(CS, RetVal, F, Args);
// Perform the merging now of the graph for the callee, which will
// come with mod/ref bits set...
Result->mergeInGraph(NCS, *F, IPModRefObj.getBUDSGraph(*F),
DSGraph::StripAllocaBit
| DSGraph::DontCloneCallNodes
| DSGraph::DontCloneAuxCallNodes);
}
else
assert(0 && "See error message");
// Remove dead nodes aggressively to match the caller's original graph.
Result->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
// Step #4: Return the clone + the mapping (by ref)
return Result;
}
// Compute Mod/Ref bit vectors for a single call site.
// These are copies of the Read/Write flags from the nodes of
// the graph produced by clearing all flags in the caller's TD graph
// and then inlining the callee's BU graph into the caller's TD graph.
//
void
FunctionModRefInfo::computeModRef(CallSite CS)
{
// Allocate the mod/ref info for the call site. Bits automatically cleared.
ModRefInfo* callModRefInfo = new ModRefInfo(funcTDGraph->getGraphSize());
callSiteModRefInfo[CS.getInstruction()] = callModRefInfo;
// Get a copy of the graph for the callee with the callee inlined
hash_map<const DSNode*, DSNodeHandle> NodeMap;
DSGraph* csgp = ResolveCallSiteModRefInfo(CS, NodeMap);
if (!csgp)
{ // Callee's side effects are unknown: mark all nodes Mod and Ref.
// Eventually this should only mark nodes visible to the callee, i.e.,
// exclude stack variables not reachable from any outgoing argument
// or any global.
callModRefInfo->getModSet().set();
callModRefInfo->getRefSet().set();
return;
}
// For all nodes in the graph, extract the mod/ref information
for (DSGraph::node_iterator NI = funcTDGraph->node_begin(),
E = funcTDGraph->node_end(); NI != E; ++NI) {
DSNode* csgNode = NodeMap[*NI].getNode();
assert(csgNode && "Inlined and original graphs do not correspond!");
if (csgNode->isModified())
callModRefInfo->setNodeIsMod(getNodeId(*NI));
if (csgNode->isRead())
callModRefInfo->setNodeIsRef(getNodeId(*NI));
}
// Drop nodemap before we delete the graph...
NodeMap.clear();
delete csgp;
}
class DSGraphPrintHelper {
const DSGraph& tdGraph;
std::vector<std::vector<const Value*> > knownValues; // identifiable objects
public:
/*ctor*/ DSGraphPrintHelper(const FunctionModRefInfo& fmrInfo)
: tdGraph(fmrInfo.getFuncGraph())
{
knownValues.resize(tdGraph.getGraphSize());
// For every identifiable value, save Value pointer in knownValues[i]
for (hash_map<Value*, DSNodeHandle>::const_iterator
I = tdGraph.getScalarMap().begin(),
E = tdGraph.getScalarMap().end(); I != E; ++I)
if (isa<GlobalValue>(I->first) ||
isa<Argument>(I->first) ||
isa<LoadInst>(I->first) ||
isa<AllocaInst>(I->first) ||
isa<MallocInst>(I->first))
{
unsigned nodeId = fmrInfo.getNodeId(I->second.getNode());
knownValues[nodeId].push_back(I->first);
}
}
void printValuesInBitVec(std::ostream &O, const BitSetVector& bv) const
{
assert(bv.size() == knownValues.size());
if (bv.none())
{ // No bits are set: just say so and return
O << "\tNONE.\n";
return;
}
if (bv.all())
{ // All bits are set: just say so and return
O << "\tALL GRAPH NODES.\n";
return;
}
for (unsigned i=0, N=bv.size(); i < N; ++i)
if (bv.test(i))
{
O << "\tNode# " << i << " : ";
if (! knownValues[i].empty())
for (unsigned j=0, NV=knownValues[i].size(); j < NV; j++)
{
const Value* V = knownValues[i][j];
if (isa<GlobalValue>(V)) O << "(Global) ";
else if (isa<Argument>(V)) O << "(Target of FormalParm) ";
else if (isa<LoadInst>(V)) O << "(Target of LoadInst ) ";
else if (isa<AllocaInst>(V)) O << "(Target of AllocaInst) ";
else if (isa<MallocInst>(V)) O << "(Target of MallocInst) ";
if (V->hasName()) O << V->getName();
else if (isa<Instruction>(V)) O << *V;
else O << "(Value*) 0x" << (void*) V;
O << std::string((j < NV-1)? "; " : "\n");
}
#if 0
else
tdGraph.getNodes()[i]->print(O, /*graph*/ NULL);
#endif
}
}
};
// Print the results of the pass.
// Currently this just prints bit-vectors and is not very readable.
//
void FunctionModRefInfo::print(std::ostream &O) const
{
DSGraphPrintHelper DPH(*this);
O << "========== Mod/ref information for function "
<< F.getName() << "========== \n\n";
// First: Print Globals and Locals modified anywhere in the function.
//
O << " -----Mod/Ref in the body of function " << F.getName()<< ":\n";
O << " --Objects modified in the function body:\n";
DPH.printValuesInBitVec(O, funcModRefInfo.getModSet());
O << " --Objects referenced in the function body:\n";
DPH.printValuesInBitVec(O, funcModRefInfo.getRefSet());
O << " --Mod and Ref vectors for the nodes listed above:\n";
funcModRefInfo.print(O, "\t");
O << "\n";
// Second: Print Globals and Locals modified at each call site in function
//
for (std::map<const Instruction *, ModRefInfo*>::const_iterator
CI = callSiteModRefInfo.begin(), CE = callSiteModRefInfo.end();
CI != CE; ++CI)
{
O << " ----Mod/Ref information for call site\n" << *CI->first;
O << " --Objects modified at call site:\n";
DPH.printValuesInBitVec(O, CI->second->getModSet());
O << " --Objects referenced at call site:\n";
DPH.printValuesInBitVec(O, CI->second->getRefSet());
O << " --Mod and Ref vectors for the nodes listed above:\n";
CI->second->print(O, "\t");
O << "\n";
}
O << "\n";
}
void FunctionModRefInfo::dump() const
{
print(std::cerr);
}
//----------------------------------------------------------------------------
// class IPModRef: An interprocedural pass that computes IP Mod/Ref info.
//----------------------------------------------------------------------------
// Free the FunctionModRefInfo objects cached in funcToModRefInfoMap.
//
void IPModRef::releaseMemory()
{
for(std::map<const Function*, FunctionModRefInfo*>::iterator
I=funcToModRefInfoMap.begin(), E=funcToModRefInfoMap.end(); I != E; ++I)
delete(I->second);
// Clear map so memory is not re-released if we are called again
funcToModRefInfoMap.clear();
}
// Run the "interprocedural" pass on each function. This needs to do
// NO real interprocedural work because all that has been done the
// data structure analysis.
//
bool IPModRef::run(Module &theModule)
{
M = &theModule;
for (Module::const_iterator FI = M->begin(), FE = M->end(); FI != FE; ++FI)
if (! FI->isExternal())
getFuncInfo(*FI, /*computeIfMissing*/ true);
return true;
}
FunctionModRefInfo& IPModRef::getFuncInfo(const Function& func,
bool computeIfMissing)
{
FunctionModRefInfo*& funcInfo = funcToModRefInfoMap[&func];
assert (funcInfo != NULL || computeIfMissing);
if (funcInfo == NULL)
{ // Create a new FunctionModRefInfo object.
// Clone the top-down graph and remove any dead nodes first, because
// otherwise original and merged graphs will not match.
// The memory for this graph clone will be freed by FunctionModRefInfo.
DSGraph* funcTDGraph =
new DSGraph(getAnalysis<TDDataStructures>().getDSGraph(func));
funcTDGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
funcInfo = new FunctionModRefInfo(func, *this, funcTDGraph); //auto-insert
funcInfo->computeModRef(func); // computes the mod/ref info
}
return *funcInfo;
}
/// getBUDSGraph - This method returns the BU data structure graph for F through
/// the use of the BUDataStructures object.
///
const DSGraph &IPModRef::getBUDSGraph(const Function &F) {
return getAnalysis<BUDataStructures>().getDSGraph(F);
}
// getAnalysisUsage - This pass requires top-down data structure graphs.
// It modifies nothing.
//
void IPModRef::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<LocalDataStructures>();
AU.addRequired<BUDataStructures>();
AU.addRequired<TDDataStructures>();
}
void IPModRef::print(std::ostream &O) const
{
O << "\nRESULTS OF INTERPROCEDURAL MOD/REF ANALYSIS:\n\n";
for (std::map<const Function*, FunctionModRefInfo*>::const_iterator
mapI = funcToModRefInfoMap.begin(), mapE = funcToModRefInfoMap.end();
mapI != mapE; ++mapI)
mapI->second->print(O);
O << "\n";
}
void IPModRef::dump() const
{
print(std::cerr);
}
} // End llvm namespace
|