summaryrefslogtreecommitdiff
path: root/lib/Analysis/DataStructure/EquivClassGraphs.cpp
blob: b46564dd4f48335c3eab21faedf8fb8620ebd5a0 (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
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
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
//===- EquivClassGraphs.cpp - Merge equiv-class graphs & inline bottom-up -===//
// 
//                     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.
// 
//===----------------------------------------------------------------------===//
//
// This pass is the same as the complete bottom-up graphs, but
// with functions partitioned into equivalence classes and a single merged
// DS graph for all functions in an equivalence class.  After this merging,
// graphs are inlined bottom-up on the SCCs of the final (CBU) call graph.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "ECGraphs"
#include "llvm/Analysis/DataStructure/EquivClassGraphs.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/DataStructure/DSGraph.h"
#include "llvm/Analysis/DataStructure/DataStructure.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/STLExtras.h"
using namespace llvm;

namespace {
  RegisterAnalysis<EquivClassGraphs> X("eqdatastructure",
                    "Equivalence-class Bottom-up Data Structure Analysis");
  Statistic<> NumEquivBUInlines("equivdatastructures",
                                "Number of graphs inlined");
  Statistic<> NumFoldGraphInlines("Inline equiv-class graphs bottom up",
                                  "Number of graphs inlined");
}

#ifndef NDEBUG
template<typename GT>
static void CheckAllGraphs(Module *M, GT &ECGraphs) {
  DSGraph &GG = ECGraphs.getGlobalsGraph();

  for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
    if (!I->isExternal()) {
      DSGraph &G = ECGraphs.getDSGraph(*I);
      if (G.retnodes_begin()->first != I)
        continue;  // Only check a graph once.

      DSGraph::NodeMapTy GlobalsGraphNodeMapping;
      G.computeGToGGMapping(GlobalsGraphNodeMapping);
    } 
}
#endif

// getSomeCalleeForCallSite - Return any one callee function at a call site.
// 
Function *EquivClassGraphs::getSomeCalleeForCallSite(const CallSite &CS) const{
  Function *thisFunc = CS.getCaller();
  assert(thisFunc && "getSomeCalleeForCallSite(): Not a valid call site?");
  DSGraph &DSG = getDSGraph(*thisFunc);
  DSNode *calleeNode = DSG.getNodeForValue(CS.getCalledValue()).getNode();
  std::map<DSNode*, Function *>::const_iterator I =
    OneCalledFunction.find(calleeNode);
  return (I == OneCalledFunction.end())? NULL : I->second;
}

// runOnModule - Calculate the bottom up data structure graphs for each function
// in the program.
//
bool EquivClassGraphs::runOnModule(Module &M) {
  CBU = &getAnalysis<CompleteBUDataStructures>();
  GlobalECs = CBU->getGlobalECs();
  DEBUG(CheckAllGraphs(&M, *CBU));

  GlobalsGraph = new DSGraph(CBU->getGlobalsGraph(), GlobalECs);
  GlobalsGraph->setPrintAuxCalls();

  ActualCallees = CBU->getActualCallees();

  // Find equivalence classes of functions called from common call sites.
  // Fold the CBU graphs for all functions in an equivalence class.
  buildIndirectFunctionSets(M);

  // Stack of functions used for Tarjan's SCC-finding algorithm.
  std::vector<DSGraph*> Stack;
  std::map<DSGraph*, unsigned> ValMap;
  unsigned NextID = 1;

  Function *MainFunc = M.getMainFunction();
  if (MainFunc && !MainFunc->isExternal()) {
    processSCC(getOrCreateGraph(*MainFunc), Stack, NextID, ValMap);
  } else {
    std::cerr << "Fold Graphs: No 'main' function found!\n";
  }
  
  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
    if (!I->isExternal())
      processSCC(getOrCreateGraph(*I), Stack, NextID, ValMap);

  DEBUG(CheckAllGraphs(&M, *this));

  getGlobalsGraph().removeTriviallyDeadNodes();
  getGlobalsGraph().markIncompleteNodes(DSGraph::IgnoreGlobals);

  // Merge the globals variables (not the calls) from the globals graph back
  // into the main function's graph so that the main function contains all of
  // the information about global pools and GV usage in the program.
  if (MainFunc && !MainFunc->isExternal()) {
    DSGraph &MainGraph = getOrCreateGraph(*MainFunc);
    const DSGraph &GG = *MainGraph.getGlobalsGraph();
    ReachabilityCloner RC(MainGraph, GG, 
                          DSGraph::DontCloneCallNodes |
                          DSGraph::DontCloneAuxCallNodes);

    // Clone the global nodes into this graph.
    for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(),
           E = GG.getScalarMap().global_end(); I != E; ++I)
      if (isa<GlobalVariable>(*I))
        RC.getClonedNH(GG.getNodeForValue(*I));

    MainGraph.maskIncompleteMarkers();
    MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs | 
                                  DSGraph::IgnoreGlobals);
  }

  // Final processing.  Note that dead node elimination may actually remove
  // globals from a function graph that are immediately used.  If there are no
  // scalars pointing to the node (e.g. because the only use is a direct store
  // to a scalar global) we have to make sure to rematerialize the globals back
  // into the graphs here, or clients will break!
  for (Module::global_iterator GI = M.global_begin(), E = M.global_end();
       GI != E; ++GI)
    // This only happens to first class typed globals.
    if (GI->getType()->getElementType()->isFirstClassType())
      for (Value::use_iterator UI = GI->use_begin(), E = GI->use_end();
           UI != E; ++UI)
        // This only happens to direct uses by instructions.
        if (Instruction *User = dyn_cast<Instruction>(*UI)) {
          DSGraph &DSG = getOrCreateGraph(*User->getParent()->getParent());
          if (!DSG.getScalarMap().count(GI)) {
            // If this global does not exist in the graph, but it is immediately
            // used by an instruction in the graph, clone it over from the
            // globals graph.
            ReachabilityCloner RC(DSG, *GlobalsGraph, 0);
            RC.getClonedNH(GlobalsGraph->getNodeForValue(GI));
          }
        }

  return false;
}


// buildIndirectFunctionSets - Iterate over the module looking for indirect
// calls to functions.  If a call site can invoke any functions [F1, F2... FN],
// unify the N functions together in the FuncECs set.
//
void EquivClassGraphs::buildIndirectFunctionSets(Module &M) {
  const ActualCalleesTy& AC = CBU->getActualCallees();
  
  // Loop over all of the indirect calls in the program.  If a call site can
  // call multiple different functions, we need to unify all of the callees into
  // the same equivalence class.
  Instruction *LastInst = 0;
  Function *FirstFunc = 0;
  for (ActualCalleesTy::const_iterator I=AC.begin(), E=AC.end(); I != E; ++I) {
    if (I->second->isExternal())
      continue;                         // Ignore functions we cannot modify

    CallSite CS = CallSite::get(I->first);

    if (CS.getCalledFunction()) {       // Direct call:
      FuncECs.insert(I->second);        // -- Make sure function has equiv class
      FirstFunc = I->second;            // -- First callee at this site
    } else {                            // Else indirect call
      // DEBUG(std::cerr << "CALLEE: " << I->second->getName()
      //       << " from : " << I->first);
      if (I->first != LastInst) {
        // This is the first callee from this call site.
        LastInst = I->first;
        FirstFunc = I->second;
	// Instead of storing the lastInst For Indirection call Sites we store
	// the DSNode for the function ptr arguemnt
	Function *thisFunc = LastInst->getParent()->getParent();
        DSGraph &TFG = CBU->getDSGraph(*thisFunc);
	DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode();
        OneCalledFunction[calleeNode] = FirstFunc;
        FuncECs.insert(I->second);
      } else {
        // This is not the first possible callee from a particular call site.
        // Union the callee in with the other functions.
        FuncECs.unionSets(FirstFunc, I->second);
#ifndef NDEBUG
	Function *thisFunc = LastInst->getParent()->getParent();
        DSGraph &TFG = CBU->getDSGraph(*thisFunc);
	DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode();
        assert(OneCalledFunction.count(calleeNode) > 0 && "Missed a call?");
#endif
      }
    }

    // Now include all functions that share a graph with any function in the
    // equivalence class.  More precisely, if F is in the class, and G(F) is
    // its graph, then we include all other functions that are also in G(F).
    // Currently, that is just the functions in the same call-graph-SCC as F.
    // 
    DSGraph& funcDSGraph = CBU->getDSGraph(*I->second);
    for (DSGraph::retnodes_iterator RI = funcDSGraph.retnodes_begin(),
           RE = funcDSGraph.retnodes_end(); RI != RE; ++RI)
      FuncECs.unionSets(FirstFunc, RI->first);
  }

  // Now that all of the equivalences have been built, merge the graphs for
  // each equivalence class.
  //
  DEBUG(std::cerr << "\nIndirect Function Equivalence Sets:\n");
  for (EquivalenceClasses<Function*>::iterator EQSI = FuncECs.begin(), E =
         FuncECs.end(); EQSI != E; ++EQSI) {
    if (!EQSI->isLeader()) continue;

    EquivalenceClasses<Function*>::member_iterator SI =
      FuncECs.member_begin(EQSI);
    assert(SI != FuncECs.member_end() && "Empty equiv set??");
    EquivalenceClasses<Function*>::member_iterator SN = SI;
    ++SN;
    if (SN == FuncECs.member_end())
      continue;   // Single function equivalence set, no merging to do.

    Function* LF = *SI;

#ifndef NDEBUG
    DEBUG(std::cerr <<"  Equivalence set for leader " << LF->getName() <<" = ");
    for (SN = SI; SN != FuncECs.member_end(); ++SN)
      DEBUG(std::cerr << " " << (*SN)->getName() << "," );
    DEBUG(std::cerr << "\n");
#endif

    // This equiv class has multiple functions: merge their graphs.  First,
    // clone the CBU graph for the leader and make it the common graph for the
    // equivalence graph.
    DSGraph &MergedG = getOrCreateGraph(*LF);

    // Record the argument nodes for use in merging later below.
    std::vector<DSNodeHandle> ArgNodes;  

    for (Function::arg_iterator AI = LF->arg_begin(), E = LF->arg_end();
         AI != E; ++AI)
      if (DS::isPointerType(AI->getType()))
        ArgNodes.push_back(MergedG.getNodeForValue(AI));
      
    // Merge in the graphs of all other functions in this equiv. class.  Note
    // that two or more functions may have the same graph, and it only needs
    // to be merged in once.
    std::set<DSGraph*> GraphsMerged;
    GraphsMerged.insert(&CBU->getDSGraph(*LF));
    
    for (++SI; SI != FuncECs.member_end(); ++SI) {
      Function *F = *SI;
      DSGraph *&FG = DSInfo[F];
      
      DSGraph &CBUGraph = CBU->getDSGraph(*F); 
      if (GraphsMerged.insert(&CBUGraph).second) {
        // Record the "folded" graph for the function.
        for (DSGraph::retnodes_iterator I = CBUGraph.retnodes_begin(),
               E = CBUGraph.retnodes_end(); I != E; ++I) {
          assert(DSInfo[I->first] == 0 && "Graph already exists for Fn!");
          DSInfo[I->first] = &MergedG;
        }
        
        // Clone this member of the equivalence class into MergedG.
        MergedG.cloneInto(CBUGraph);
      }
      
      // Merge the return nodes of all functions together.
      MergedG.getReturnNodes()[LF].mergeWith(MergedG.getReturnNodes()[F]);
      
      // Merge the function arguments with all argument nodes found so far.
      // If there are extra function args, add them to the vector of argNodes
      Function::arg_iterator AI2 = F->arg_begin(), AI2end = F->arg_end();
      for (unsigned arg = 0, numArgs = ArgNodes.size();
           arg != numArgs && AI2 != AI2end; ++AI2, ++arg)
        if (DS::isPointerType(AI2->getType()))
          ArgNodes[arg].mergeWith(MergedG.getNodeForValue(AI2));
      
      for ( ; AI2 != AI2end; ++AI2)
        if (DS::isPointerType(AI2->getType()))
          ArgNodes.push_back(MergedG.getNodeForValue(AI2));
      DEBUG(MergedG.AssertGraphOK());
    }
  }
  DEBUG(std::cerr << "\n");
}


DSGraph &EquivClassGraphs::getOrCreateGraph(Function &F) {
  // Has the graph already been created?
  DSGraph *&Graph = DSInfo[&F];
  if (Graph) return *Graph;

  DSGraph &CBUGraph = CBU->getDSGraph(F);

  // Copy the CBU graph...
  Graph = new DSGraph(CBUGraph, GlobalECs);   // updates the map via reference
  Graph->setGlobalsGraph(&getGlobalsGraph());
  Graph->setPrintAuxCalls();

  // Make sure to update the DSInfo map for all functions in the graph!
  for (DSGraph::retnodes_iterator I = Graph->retnodes_begin();
       I != Graph->retnodes_end(); ++I)
    if (I->first != &F) {
      DSGraph *&FG = DSInfo[I->first];
      assert(FG == 0 && "Merging function in SCC twice?");
      FG = Graph;
    }

  return *Graph;
}


unsigned EquivClassGraphs::
processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, unsigned &NextID, 
           std::map<DSGraph*, unsigned> &ValMap) {
  std::map<DSGraph*, unsigned>::iterator It = ValMap.lower_bound(&FG);
  if (It != ValMap.end() && It->first == &FG)
    return It->second;

  DEBUG(std::cerr << "    ProcessSCC for function " << FG.getFunctionNames()
                  << "\n");

  unsigned Min = NextID++, MyID = Min;
  ValMap[&FG] = Min;
  Stack.push_back(&FG);

  // The edges out of the current node are the call site targets...
  for (DSGraph::fc_iterator CI = FG.fc_begin(), CE = FG.fc_end();
       CI != CE; ++CI) {
    Instruction *Call = CI->getCallSite().getInstruction();

    // Loop over all of the actually called functions...
    for (callee_iterator I = callee_begin(Call), E = callee_end(Call);
         I != E; ++I)
      if (!I->second->isExternal()) {
        // Process the callee as necessary.
        unsigned M = processSCC(getOrCreateGraph(*I->second),
                                Stack, NextID, ValMap);
        if (M < Min) Min = M;
      }
  }

  assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
  if (Min != MyID)
    return Min;         // This is part of a larger SCC!

  // If this is a new SCC, process it now.
  bool MergedGraphs = false;
  while (Stack.back() != &FG) {
    DSGraph *NG = Stack.back();
    ValMap[NG] = ~0U;

    // If the SCC found is not the same as those found in CBU, make sure to
    // merge the graphs as appropriate.
    FG.cloneInto(*NG);

    // Update the DSInfo map and delete the old graph...
    for (DSGraph::retnodes_iterator I = NG->retnodes_begin();
         I != NG->retnodes_end(); ++I)
      DSInfo[I->first] = &FG;
    
    // Remove NG from the ValMap since the pointer may get recycled.
    ValMap.erase(NG);
    delete NG;
    MergedGraphs = true;
    Stack.pop_back();
  }

  // Clean up the graph before we start inlining a bunch again.
  if (MergedGraphs)
    FG.removeTriviallyDeadNodes();

  Stack.pop_back();

  processGraph(FG);
  ValMap[&FG] = ~0U;
  return MyID;
}


/// processGraph - Process the CBU graphs for the program in bottom-up order on
/// the SCC of the __ACTUAL__ call graph.  This builds final folded CBU graphs.
void EquivClassGraphs::processGraph(DSGraph &G) {
  DEBUG(std::cerr << "    ProcessGraph for function "
                  << G.getFunctionNames() << "\n");

  hash_set<Instruction*> calls;

  // Else we need to inline some callee graph.  Visit all call sites.
  // The edges out of the current node are the call site targets...
  unsigned i = 0;
  for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE;
       ++CI, ++i) {
    const DSCallSite &CS = *CI;
    Instruction *TheCall = CS.getCallSite().getInstruction();

    assert(calls.insert(TheCall).second &&
           "Call instruction occurs multiple times in graph??");
    
    if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0)
      continue;

    // Inline the common callee graph into the current graph, if the callee
    // graph has not changed.  Note that all callees should have the same
    // graph so we only need to do this once.
    // 
    DSGraph* CalleeGraph = NULL;
    callee_iterator I = callee_begin(TheCall), E = callee_end(TheCall);
    unsigned TNum, Num;

    // Loop over all potential callees to find the first non-external callee.
    for (TNum = 0, Num = std::distance(I, E); I != E; ++I, ++TNum)
      if (!I->second->isExternal())
        break;

    // Now check if the graph has changed and if so, clone and inline it.
    if (I != E) {
      Function *CalleeFunc = I->second;
      
      // Merge the callee's graph into this graph, if not already the same.
      // Callees in the same equivalence class (which subsumes those
      // in the same SCCs) have the same graph.  Note that all recursion
      // including self-recursion have been folded in the equiv classes.
      // 
      CalleeGraph = &getOrCreateGraph(*CalleeFunc);
      if (CalleeGraph != &G) {
        ++NumFoldGraphInlines;
        G.mergeInGraph(CS, *CalleeFunc, *CalleeGraph,
                       DSGraph::StripAllocaBit |
                       DSGraph::DontCloneCallNodes |
                       DSGraph::DontCloneAuxCallNodes);
        DEBUG(std::cerr << "    Inlining graph [" << i << "/"
              << G.getFunctionCalls().size()-1
              << ":" << TNum << "/" << Num-1 << "] for "
              << CalleeFunc->getName() << "["
              << CalleeGraph->getGraphSize() << "+"
              << CalleeGraph->getAuxFunctionCalls().size()
              << "] into '" /*<< G.getFunctionNames()*/ << "' ["
              << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
              << "]\n");
      }
    }

#ifndef NDEBUG
    // Now loop over the rest of the callees and make sure they have the
    // same graph as the one inlined above.
    if (CalleeGraph)
      for (++I, ++TNum; I != E; ++I, ++TNum)
        if (!I->second->isExternal())
          assert(CalleeGraph == &getOrCreateGraph(*I->second) &&
                 "Callees at a call site have different graphs?");
#endif
  }

  // Recompute the Incomplete markers.
  G.maskIncompleteMarkers();
  G.markIncompleteNodes(DSGraph::MarkFormalArgs);
  
  // Delete dead nodes.  Treat globals that are unreachable but that can
  // reach live nodes as live.
  G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);

  // When this graph is finalized, clone the globals in the graph into the
  // globals graph to make sure it has everything, from all graphs.
  ReachabilityCloner RC(*G.getGlobalsGraph(), G, DSGraph::StripAllocaBit);

  // Clone everything reachable from globals in the function graph into the
  // globals graph.
  DSScalarMap &MainSM = G.getScalarMap();
  for (DSScalarMap::global_iterator I = MainSM.global_begin(),
         E = MainSM.global_end(); I != E; ++I) 
    RC.getClonedNH(MainSM[*I]);

  DEBUG(std::cerr << "  -- DONE ProcessGraph for function "
                  << G.getFunctionNames() << "\n");
}