Coverage Report

Created: 2023-10-30 17:15

/builds/2mk6rsew/0/parcoach/parcoach/src/aSSA/ModRefAnalysis.cpp
Line
Count
Source (jump to first uncovered line)
1
#include "PTACallGraph.h"
2
#include "Utils.h"
3
4
#include "parcoach/Collectives.h"
5
#include "parcoach/ModRefAnalysis.h"
6
#include "parcoach/Options.h"
7
8
#include "llvm/ADT/SCCIterator.h"
9
10
using namespace llvm;
11
12
namespace parcoach {
13
namespace {
14
#ifndef NDEBUG
15
cl::opt<bool> OptDumpModRef("dump-modref",
16
                            cl::desc("Dump the mod/ref analysis"),
17
                            cl::cat(ParcoachCategory));
18
#endif
19
20
} // namespace
21
ModRefAnalysisResult::ModRefAnalysisResult(PTACallGraph const &CG,
22
                                           Andersen const &PTA,
23
                                           ExtInfo const &ExtInfo,
24
                                           MemReg const &Regions, Module &M)
25
1.76k
    : CG(CG), PTA(PTA), extInfo(ExtInfo), Regions(Regions) {
26
1.76k
  analyze(M);
27
1.76k
}
28
29
1.76k
ModRefAnalysisResult::~ModRefAnalysisResult() {}
30
31
28.0k
void ModRefAnalysisResult::visitAllocaInst(AllocaInst &I) {
32
28.0k
  auto *R = Regions.getValueRegion(&I);
33
28.0k
  assert(R);
34
28.0k
  funcLocalMap[curFunc].insert(R);
35
28.0k
}
36
37
43.9k
void ModRefAnalysisResult::visitLoadInst(LoadInst &I) {
38
43.9k
  std::vector<Value const *> PtsSet;
39
43.9k
  bool Found = PTA.getPointsToSet(I.getPointerOperand(), PtsSet);
40
  // FIXME: should this be an actual error?
41
43.9k
  assert(Found && "Load not found");
42
43.9k
  if (!Found) {
43
0
    return;
44
0
  }
45
43.9k
  MemRegVector Regs;
46
43.9k
  Regions.getValuesRegion(PtsSet, Regs);
47
48
43.9k
  for (auto *R : Regs) {
49
43.9k
    if (globalKillSet.find(R) != globalKillSet.end()) {
50
0
      continue;
51
0
    }
52
43.9k
    funcRefMap[curFunc].insert(R);
53
43.9k
  }
54
43.9k
}
55
56
26.4k
void ModRefAnalysisResult::visitStoreInst(StoreInst &I) {
57
26.4k
  std::vector<Value const *> PtsSet;
58
26.4k
  bool Found = PTA.getPointsToSet(I.getPointerOperand(), PtsSet);
59
  // FIXME: should this be an actual error?
60
26.4k
  assert(Found && "Store not found");
61
26.4k
  if (!Found) {
62
0
    return;
63
0
  }
64
26.4k
  MemRegVector Regs;
65
26.4k
  Regions.getValuesRegion(PtsSet, Regs);
66
67
26.4k
  for (auto *R : Regs) {
68
26.4k
    if (globalKillSet.find(R) != globalKillSet.end()) {
69
0
      continue;
70
0
    }
71
26.4k
    funcModMap[curFunc].insert(R);
72
26.4k
  }
73
26.4k
}
74
75
53.8k
void ModRefAnalysisResult::visitCallBase(CallBase &CB) {
76
  // For each external function called, add the region of each pointer
77
  // parameters passed to the function to the ref set of the called
78
  // function. Regions are added to the Mod set only if the parameter is
79
  // modified in the callee.
80
81
53.8k
  CallInst *CI = cast<CallInst>(&CB);
82
53.8k
  Function const *Callee = CI->getCalledFunction();
83
53.8k
#if defined(PARCOACH_ENABLE_CUDA) || defined(PARCOACH_ENABLE_OPENMP)
84
53.8k
  Collective const *Coll = Callee ? Collective::find(*Callee) : nullptr;
85
53.8k
#endif
86
87
#ifdef PARCOACH_ENABLE_CUDA
88
  // In CUDA after a synchronization, all region in shared memory are written.
89
  if (Coll && isa<CudaCollective>(Coll) && Coll->Name == "llvm.nvvm.barrier0") {
90
    for (auto *r : Regions.getCudaSharedRegions()) {
91
      if (globalKillSet.find(r) != globalKillSet.end()) {
92
        continue;
93
      }
94
      funcModMap[curFunc].insert(r);
95
    }
96
  }
97
#endif
98
99
53.8k
#ifdef PARCOACH_ENABLE_OPENMP
100
  // In OpenMP after a synchronization, all region in shared memory are written.
101
53.8k
  if (Coll && isa<OMPCollective>(Coll) && Coll->Name == "__kmpc_barrier") {
102
21
    for (auto *R : getRange(Regions.getOmpSharedRegions(), CI->getFunction())) {
103
1
      if (globalKillSet.find(R) != globalKillSet.end()) {
104
0
        continue;
105
0
      }
106
1
      funcModMap[curFunc].insert(R);
107
1
    }
108
21
  }
109
53.8k
#endif
110
111
  // indirect call
112
53.8k
  if (!Callee) {
113
3
    bool MayCallExternalFunction = false;
114
5
    for (Function const *MayCallee : CG.getIndirectCallMap().lookup(CI)) {
115
5
      if (MayCallee->isDeclaration() && !isIntrinsicDbgFunction(MayCallee)) {
116
1
        MayCallExternalFunction = true;
117
1
        break;
118
1
      }
119
5
    }
120
3
    if (!MayCallExternalFunction) {
121
2
      return;
122
2
    }
123
3
  }
124
125
  // direct call
126
53.8k
  else {
127
53.8k
    if (!Callee->isDeclaration()) {
128
60
      return;
129
60
    }
130
131
53.8k
    if (isIntrinsicDbgFunction(Callee)) {
132
26.2k
      return;
133
26.2k
    }
134
53.8k
  }
135
136
98.5k
  for (unsigned I = 0; I < CI->arg_size(); ++I) {
137
70.9k
    Value *Arg = CI->getArgOperand(I);
138
70.9k
    if (!Arg->getType()->isPointerTy()) {
139
15.9k
      continue;
140
15.9k
    }
141
142
    // Case where argument is a inttoptr cast (e.g. MPI_IN_PLACE)
143
55.0k
    ConstantExpr *Ce = dyn_cast<ConstantExpr>(Arg);
144
55.0k
    if (Ce) {
145
0
      Instruction *Inst = Ce->getAsInstruction();
146
0
      assert(Inst);
147
0
      bool IsAIntToPtr = isa<IntToPtrInst>(Inst);
148
0
      Inst->deleteValue();
149
0
      if (IsAIntToPtr) {
150
0
        continue;
151
0
      }
152
0
    }
153
154
55.0k
    std::vector<Value const *> ArgPtsSet;
155
156
55.0k
    bool Found = PTA.getPointsToSet(Arg, ArgPtsSet);
157
55.0k
    assert(Found && "arg not found in ModRefAnalysisResult");
158
55.0k
    if (!Found) {
159
0
      continue;
160
0
    }
161
55.0k
    MemRegVector Regs;
162
55.0k
    Regions.getValuesRegion(ArgPtsSet, Regs);
163
164
55.0k
    for (auto *R : Regs) {
165
54.7k
      if (globalKillSet.find(R) != globalKillSet.end()) {
166
0
        continue;
167
0
      }
168
54.7k
      funcRefMap[curFunc].insert(R);
169
54.7k
    }
170
171
    // direct call
172
55.0k
    if (Callee) {
173
55.0k
      auto const *Info = extInfo.getExtModInfo(Callee);
174
175
55.0k
      if (Info) {
176
        // Variadic argument
177
55.0k
        if (I >= Info->NbArgs) {
178
          // errs() << "Function: " << callee->getName() << " in " <<
179
          // callee->getParent()->getName() << "\n";
180
1
          assert(Callee->isVarArg());
181
182
1
          if (Info->ArgIsMod[Info->NbArgs - 1]) {
183
1
            for (auto *R : Regs) {
184
1
              if (globalKillSet.find(R) != globalKillSet.end()) {
185
0
                continue;
186
0
              }
187
1
              funcModMap[curFunc].insert(R);
188
1
            }
189
1
          }
190
55.0k
        } else {
191
          // Normal argument
192
55.0k
          if (Info->ArgIsMod[I]) {
193
17.2k
            for (auto *R : Regs) {
194
16.9k
              if (globalKillSet.find(R) != globalKillSet.end()) {
195
0
                continue;
196
0
              }
197
16.9k
              funcModMap[curFunc].insert(R);
198
16.9k
            }
199
17.2k
          }
200
55.0k
        }
201
55.0k
      }
202
55.0k
    } else { // indirect call
203
6
      for (Function const *MayCallee : CG.getIndirectCallMap().lookup(CI)) {
204
6
        if (!MayCallee->isDeclaration() || isIntrinsicDbgFunction(MayCallee)) {
205
0
          continue;
206
0
        }
207
208
6
        auto const *Info = extInfo.getExtModInfo(MayCallee);
209
6
        if (!Info) {
210
0
          continue;
211
0
        }
212
213
        // Variadic argument
214
6
        if (I >= Info->NbArgs) {
215
2
          assert(MayCallee->isVarArg());
216
217
2
          if (Info->ArgIsMod[Info->NbArgs - 1]) {
218
1
            for (auto *R : Regs) {
219
1
              if (globalKillSet.find(R) != globalKillSet.end()) {
220
0
                continue;
221
0
              }
222
1
              funcModMap[curFunc].insert(R);
223
1
            }
224
1
          }
225
2
        }
226
227
        // Normal argument
228
4
        else {
229
4
          if (Info->ArgIsMod[I]) {
230
1
            for (auto *R : Regs) {
231
1
              if (globalKillSet.find(R) != globalKillSet.end()) {
232
0
                continue;
233
0
              }
234
1
              funcModMap[curFunc].insert(R);
235
1
            }
236
1
          }
237
4
        }
238
6
      }
239
3
    }
240
55.0k
  }
241
242
  // Compute mof/ref for return value if it is a pointer.
243
27.5k
  if (Callee) {
244
27.5k
    auto const *Info = extInfo.getExtModInfo(Callee);
245
246
27.5k
    if (Callee->getReturnType()->isPointerTy()) {
247
2.60k
      std::vector<Value const *> RetPtsSet;
248
2.60k
      bool Found = PTA.getPointsToSet(CI, RetPtsSet);
249
2.60k
      assert(Found && "callee not found in ModRefAnalysisResult");
250
2.60k
      if (!Found) {
251
0
        return;
252
0
      }
253
254
2.60k
      MemRegVector Regs;
255
2.60k
      Regions.getValuesRegion(RetPtsSet, Regs);
256
2.60k
      for (auto *R : Regs) {
257
2.54k
        if (globalKillSet.find(R) != globalKillSet.end()) {
258
0
          continue;
259
0
        }
260
2.54k
        funcRefMap[curFunc].insert(R);
261
2.54k
      }
262
263
2.60k
      if (Info && Info->RetIsMod) {
264
2.60k
        for (auto *R : Regs) {
265
2.54k
          if (globalKillSet.find(R) != globalKillSet.end()) {
266
0
            continue;
267
0
          }
268
2.54k
          funcModMap[curFunc].insert(R);
269
2.54k
        }
270
2.60k
      }
271
2.60k
    }
272
27.5k
  }
273
274
1
  else {
275
2
    for (Function const *MayCallee : CG.getIndirectCallMap().lookup(CI)) {
276
2
      if (!MayCallee->isDeclaration() || isIntrinsicDbgFunction(MayCallee)) {
277
0
        continue;
278
0
      }
279
280
2
      auto const *Info = extInfo.getExtModInfo(MayCallee);
281
282
2
      if (MayCallee->getReturnType()->isPointerTy()) {
283
1
        std::vector<Value const *> RetPtsSet;
284
1
        bool Found = PTA.getPointsToSet(CI, RetPtsSet);
285
1
        assert(Found && "CI not found in ModRefAnalysisResult");
286
1
        if (!Found) {
287
0
          continue;
288
0
        }
289
1
        MemRegVector Regs;
290
1
        Regions.getValuesRegion(RetPtsSet, Regs);
291
1
        for (auto *R : Regs) {
292
0
          if (globalKillSet.find(R) != globalKillSet.end()) {
293
0
            continue;
294
0
          }
295
0
          funcRefMap[curFunc].insert(R);
296
0
        }
297
298
1
        if (Info && Info->RetIsMod) {
299
0
          for (auto *R : Regs) {
300
0
            if (globalKillSet.find(R) != globalKillSet.end()) {
301
0
              continue;
302
0
            }
303
0
            funcModMap[curFunc].insert(R);
304
0
          }
305
0
        }
306
1
      }
307
2
    }
308
1
  }
309
27.5k
}
310
311
1.76k
void ModRefAnalysisResult::analyze(Module &M) {
312
1.76k
  TimeTraceScope TTS("ModRefAnalysis");
313
  // Compute global kill set containing regions whose allocation sites are
314
  // in functions not reachable from prog entry.
315
1.76k
  std::vector<Value const *> AllocSites;
316
1.76k
  PTA.getAllAllocationSites(AllocSites);
317
42.3k
  for (Value const *V : AllocSites) {
318
42.3k
    Instruction const *Inst = dyn_cast<Instruction>(V);
319
42.3k
    if (!Inst) {
320
11.6k
      continue;
321
11.6k
    }
322
30.7k
    if (CG.isReachableFromEntry(*Inst->getParent()->getParent())) {
323
30.5k
      continue;
324
30.5k
    }
325
153
    globalKillSet.insert(Regions.getValueRegion(V));
326
153
  }
327
328
  // First compute the mod/ref sets of each function from its load/store
329
  // instructions and calls to external functions.
330
331
19.8k
  for (Function &F : M) {
332
19.8k
    if (!CG.isReachableFromEntry(F)) {
333
1.91k
      continue;
334
1.91k
    }
335
336
17.9k
    curFunc = &F;
337
17.9k
    visit(&F);
338
17.9k
  }
339
340
  // Then iterate through the PTACallGraph with an SCC iterator
341
  // and add mod/ref sets from callee to caller.
342
1.76k
  scc_iterator<PTACallGraph const *> CgSccIter = scc_begin(&CG);
343
25.1k
  while (!CgSccIter.isAtEnd()) {
344
345
23.3k
    auto const &NodeVec = *CgSccIter;
346
347
    // For each function in the SCC compute kill sets
348
    // from callee not in the SCC and update mod/ref sets accordingly.
349
23.3k
    for (PTACallGraphNode const *Node : NodeVec) {
350
23.3k
      Function const *F = Node->getFunction();
351
23.3k
      if (F == NULL) {
352
3.51k
        continue;
353
3.51k
      }
354
355
43.6k
      for (auto It : *Node) {
356
43.6k
        Function const *Callee = It.second->getFunction();
357
43.6k
        if (Callee == NULL || F == Callee) {
358
16.1k
          continue;
359
16.1k
        }
360
361
        // If callee is not in the scc
362
        // kill(F) = kill(F) U kill(callee) U local(callee)
363
27.4k
        if (find(NodeVec.begin(), NodeVec.end(), It.second) == NodeVec.end()) {
364
27.4k
          for (auto *R : funcLocalMap[Callee]) {
365
181
            funcKillMap[F].insert(R);
366
181
          }
367
368
          // Here we have to use a vector to store regions we want to add into
369
          // the funcKillMap because iterators in a DenseMap are invalidated
370
          // whenever an insertion occurs unlike map.
371
27.4k
          MemRegVector KillToAdd;
372
27.4k
          for (auto *R : funcKillMap[Callee]) {
373
112
            KillToAdd.push_back(R);
374
112
          }
375
27.4k
          for (auto *R : KillToAdd) {
376
112
            funcKillMap[F].insert(R);
377
112
          }
378
27.4k
        }
379
27.4k
      }
380
381
      // Mod(F) = Mod(F) \ kill(F)
382
      // Ref(F) = Ref(F) \ kill(F)
383
19.8k
      MemRegVector ToRemove;
384
30.1k
      for (auto *R : funcModMap[F]) {
385
30.1k
        if (funcKillMap[F].find(R) != funcKillMap[F].end()) {
386
0
          ToRemove.push_back(R);
387
0
        }
388
30.1k
      }
389
19.8k
      for (auto *R : ToRemove) {
390
0
        funcModMap[F].erase(R);
391
0
      }
392
19.8k
      ToRemove.clear();
393
35.8k
      for (auto *R : funcRefMap[F]) {
394
35.8k
        if (funcKillMap[F].find(R) != funcKillMap[F].end()) {
395
0
          ToRemove.push_back(R);
396
0
        }
397
35.8k
      }
398
19.8k
      for (auto *R : ToRemove) {
399
0
        funcRefMap[F].erase(R);
400
0
      }
401
19.8k
    }
402
403
    // For each function in the SCC, update mod/ref sets until reaching a fixed
404
    // point.
405
23.3k
    bool Changed = true;
406
407
46.8k
    while (Changed) {
408
23.4k
      Changed = false;
409
410
23.4k
      for (PTACallGraphNode const *Node : NodeVec) {
411
23.4k
        Function const *F = Node->getFunction();
412
23.4k
        if (F == NULL) {
413
3.51k
          continue;
414
3.51k
        }
415
416
19.9k
        unsigned ModSize = funcModMap[F].size();
417
19.9k
        unsigned RefSize = funcRefMap[F].size();
418
419
43.7k
        for (auto It : *Node) {
420
43.7k
          Function const *Callee = It.second->getFunction();
421
43.7k
          if (Callee == NULL || F == Callee) {
422
16.1k
            continue;
423
16.1k
          }
424
425
          // Mod(caller) = Mod(caller) U (Mod(callee) \ Kill(caller)
426
          // Ref(caller) = Ref(caller) U (Ref(callee) \ Kill(caller)
427
27.5k
          MemRegSet ModToAdd;
428
27.5k
          MemRegSet RefToAdd;
429
27.5k
          ModToAdd.insert(funcModMap[Callee].begin(), funcModMap[Callee].end());
430
27.5k
          RefToAdd.insert(funcRefMap[Callee].begin(), funcRefMap[Callee].end());
431
27.5k
          for (auto *R : ModToAdd) {
432
402
            if (funcKillMap[F].find(R) == funcKillMap[F].end()) {
433
58
              funcModMap[F].insert(R);
434
58
            }
435
402
          }
436
27.5k
          for (auto *R : RefToAdd) {
437
715
            if (funcKillMap[F].find(R) == funcKillMap[F].end()) {
438
416
              funcRefMap[F].insert(R);
439
416
            }
440
715
          }
441
27.5k
        }
442
443
19.9k
        if (funcModMap[F].size() > ModSize || funcRefMap[F].size() > RefSize) {
444
52
          Changed = true;
445
52
        }
446
19.9k
      }
447
23.4k
    }
448
449
23.3k
    ++CgSccIter;
450
23.3k
  }
451
1.76k
}
452
453
64
MemRegSet ModRefAnalysisResult::getFuncMod(Function const *F) const {
454
64
  return funcModMap.lookup(F);
455
64
}
456
457
64
MemRegSet ModRefAnalysisResult::getFuncRef(Function const *F) const {
458
64
  return funcRefMap.lookup(F);
459
64
}
460
461
64
MemRegSet ModRefAnalysisResult::getFuncKill(Function const *F) const {
462
64
  return funcKillMap.lookup(F);
463
64
}
464
465
144k
bool ModRefAnalysisResult::inGlobalKillSet(MemRegEntry *R) const {
466
144k
  return globalKillSet.count(R) > 0;
467
144k
}
468
469
#ifndef NDEBUG
470
void ModRefAnalysisResult::dump() const {
471
  scc_iterator<PTACallGraph const *> CgSccIter = scc_begin(&CG);
472
  while (!CgSccIter.isAtEnd()) {
473
    auto const &NodeVec = *CgSccIter;
474
475
    for (PTACallGraphNode const *Node : NodeVec) {
476
      Function *F = Node->getFunction();
477
      if (F == NULL || isIntrinsicDbgFunction(F)) {
478
        continue;
479
      }
480
481
      errs() << "Mod/Ref for function " << F->getName() << ":\n";
482
      errs() << "Mod(";
483
      for (auto *R : getFuncMod(F)) {
484
        errs() << R->getName() << ", ";
485
      }
486
      errs() << ")\n";
487
      errs() << "Ref(";
488
      for (auto *R : getFuncRef(F)) {
489
        errs() << R->getName() << ", ";
490
      }
491
      errs() << ")\n";
492
      errs() << "Local(";
493
      for (auto *R : funcLocalMap.lookup(F)) {
494
        errs() << R->getName() << ", ";
495
      }
496
      errs() << ")\n";
497
      errs() << "Kill(";
498
      for (auto *R : getFuncKill(F)) {
499
        errs() << R->getName() << ", ";
500
      }
501
      errs() << ")\n";
502
    }
503
504
    ++CgSccIter;
505
  }
506
  errs() << "GlobalKill(";
507
  for (auto *R : globalKillSet) {
508
    errs() << R->getName() << ", ";
509
  }
510
  errs() << ")\n";
511
}
512
#endif
513
514
AnalysisKey ModRefAnalysis::Key;
515
ModRefAnalysis::Result ModRefAnalysis::run(Module &M,
516
1.76k
                                           ModuleAnalysisManager &AM) {
517
1.76k
  TimeTraceScope TTS("ModRefAnalysisPass");
518
1.76k
  auto &AA = AM.getResult<AndersenAA>(M);
519
1.76k
  auto &PTA = AM.getResult<PTACallGraphAnalysis>(M);
520
1.76k
  auto &ExtInfo = AM.getResult<ExtInfoAnalysis>(M);
521
1.76k
  auto &Regions = AM.getResult<MemRegAnalysis>(M);
522
1.76k
  auto MRA =
523
1.76k
      std::make_unique<ModRefAnalysisResult>(*PTA, AA, *ExtInfo, *Regions, M);
524
#ifndef NDEBUG
525
  // FIXME: migrating this anywhere should work, we should make
526
  // the omp thingy an analysis pass.
527
  if (OptDumpModRef) {
528
    MRA->dump();
529
  }
530
#endif
531
1.76k
  return MRA;
532
1.76k
}
533
534
} // namespace parcoach