Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/Delinearization.cpp
Line
Count
Source (jump to first uncovered line)
1
//===---- Delinearization.cpp - MultiDimensional Index Delinearization ----===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This implements an analysis pass that tries to delinearize all GEP
10
// instructions in all loops using the SCEV analysis functionality. This pass is
11
// only used for testing purposes: if your pass needs delinearization, please
12
// use the on-demand SCEVAddRecExpr::delinearize() function.
13
//
14
//===----------------------------------------------------------------------===//
15
16
#include "llvm/Analysis/LoopInfo.h"
17
#include "llvm/Analysis/Passes.h"
18
#include "llvm/Analysis/ScalarEvolution.h"
19
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
20
#include "llvm/IR/Constants.h"
21
#include "llvm/IR/DerivedTypes.h"
22
#include "llvm/IR/Function.h"
23
#include "llvm/IR/InstIterator.h"
24
#include "llvm/IR/Instructions.h"
25
#include "llvm/IR/LLVMContext.h"
26
#include "llvm/IR/Type.h"
27
#include "llvm/Pass.h"
28
#include "llvm/Support/Debug.h"
29
#include "llvm/Support/raw_ostream.h"
30
31
using namespace llvm;
32
33
#define DL_NAME "delinearize"
34
#define DEBUG_TYPE DL_NAME
35
36
namespace {
37
38
class Delinearization : public FunctionPass {
39
  Delinearization(const Delinearization &); // do not implement
40
protected:
41
  Function *F;
42
  LoopInfo *LI;
43
  ScalarEvolution *SE;
44
45
public:
46
  static char ID; // Pass identification, replacement for typeid
47
48
16
  Delinearization() : FunctionPass(ID) {
49
16
    initializeDelinearizationPass(*PassRegistry::getPassRegistry());
50
16
  }
51
  bool runOnFunction(Function &F) override;
52
  void getAnalysisUsage(AnalysisUsage &AU) const override;
53
  void print(raw_ostream &O, const Module *M = nullptr) const override;
54
};
55
56
} // end anonymous namespace
57
58
16
void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
59
16
  AU.setPreservesAll();
60
16
  AU.addRequired<LoopInfoWrapperPass>();
61
16
  AU.addRequired<ScalarEvolutionWrapperPass>();
62
16
}
63
64
16
bool Delinearization::runOnFunction(Function &F) {
65
16
  this->F = &F;
66
16
  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
67
16
  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
68
16
  return false;
69
16
}
70
71
16
void Delinearization::print(raw_ostream &O, const Module *) const {
72
16
  O << "Delinearization on function " << F->getName() << ":\n";
73
533
  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; 
++I517
) {
74
517
    Instruction *Inst = &(*I);
75
517
76
517
    // Only analyze loads and stores.
77
517
    if (!isa<StoreInst>(Inst) && 
!isa<LoadInst>(Inst)484
&&
78
517
        
!isa<GetElementPtrInst>(Inst)451
)
79
412
      continue;
80
105
81
105
    const BasicBlock *BB = Inst->getParent();
82
105
    // Delinearize the memory access as analyzed in all the surrounding loops.
83
105
    // Do not analyze memory accesses outside loops.
84
270
    for (Loop *L = LI->getLoopFor(BB); L != nullptr; 
L = L->getParentLoop()165
) {
85
165
      const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(Inst), L);
86
165
87
165
      const SCEVUnknown *BasePointer =
88
165
          dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
89
165
      // Do not delinearize if we cannot find the base pointer.
90
165
      if (!BasePointer)
91
0
        break;
92
165
      AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
93
165
94
165
      O << "\n";
95
165
      O << "Inst:" << *Inst << "\n";
96
165
      O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
97
165
      O << "AccessFunction: " << *AccessFn << "\n";
98
165
99
165
      SmallVector<const SCEV *, 3> Subscripts, Sizes;
100
165
      SE->delinearize(AccessFn, Subscripts, Sizes, SE->getElementSize(Inst));
101
165
      if (Subscripts.size() == 0 || 
Sizes.size() == 041
||
102
165
          
Subscripts.size() != Sizes.size()41
) {
103
124
        O << "failed to delinearize\n";
104
124
        continue;
105
124
      }
106
41
107
41
      O << "Base offset: " << *BasePointer << "\n";
108
41
      O << "ArrayDecl[UnknownSize]";
109
41
      int Size = Subscripts.size();
110
98
      for (int i = 0; i < Size - 1; 
i++57
)
111
57
        O << "[" << *Sizes[i] << "]";
112
41
      O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
113
41
114
41
      O << "ArrayRef";
115
139
      for (int i = 0; i < Size; 
i++98
)
116
98
        O << "[" << *Subscripts[i] << "]";
117
41
      O << "\n";
118
41
    }
119
105
  }
120
16
}
121
122
char Delinearization::ID = 0;
123
static const char delinearization_name[] = "Delinearization";
124
11.0k
INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
125
11.0k
                      true)
126
11.0k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
127
11.0k
INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
128
129
0
FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }