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
|
/*========================== begin_copyright_notice ============================
Copyright (C) 2022 Intel Corporation
SPDX-License-Identifier: MIT
============================= end_copyright_notice ===========================*/
#ifndef _POINTSTOANALYSIS_H_
#define _POINTSTOANALYSIS_H_
#include <memory>
#include <unordered_map>
#include <vector>
#include "Assertions.h"
//#include "common.h"
#include "FlowGraph.h"
//#include "G4_BB.hpp"
//#include "G4_IR.hpp"
//#include "G4_Opcode.h"
namespace vISA {
struct pointInfo {
G4_RegVar *var;
unsigned char off;
};
struct addrExpInfo {
G4_AddrExp *exp;
unsigned char off;
};
typedef std::vector<pointInfo> REGVAR_VECTOR;
typedef std::vector<addrExpInfo> ADDREXP_VECTOR;
typedef std::vector<G4_RegVar *> ORG_REGVAR_VECTOR;
typedef std::map<const G4_RegVar *, unsigned> REGVAR_ID_MAP;
/*
* Performs flow-insensitive points-to analysis.
* Points-to analysis is performed once at the beginning of RA,
* and is used to compute the indirect uses of GRF variables for liveness
* analysis. Each address variable in the declare list is associated with a
* points-to set, which is a list of GRF RegVars.
*/
class PointsToAnalysis {
private:
G4_Kernel *kernel = nullptr;
const unsigned int numBBs;
unsigned int numAddrs;
// keeps track of the indirect variables used in each BB
const std::unique_ptr<REGVAR_VECTOR[]> indirectUses;
// vector of points-to set for each address variable
std::vector<REGVAR_VECTOR> pointsToSets;
// vector of address expression for each address variable
std::vector<ADDREXP_VECTOR> addrExpSets;
// index of an address's points-to set in the pointsToSets vector
std::vector<unsigned> addrPointsToSetIndex;
// original regvar ptrs
REGVAR_ID_MAP regVars;
void resizePointsToSet(unsigned int newsize);
void addPointsToSetToBB(int bbId, const G4_RegVar *addr);
bool isVar(G4_RegVar *var, pointInfo &pt) { return pt.var == var; }
void addIndirectUseToBB(unsigned int bbId, pointInfo pt);
void addToPointsToSet(const G4_RegVar *addr, G4_AddrExp *opnd,
unsigned char offset);
// Merge addr2's points-to set into addr1's
// basically we copy the content of addr2's points-to to addr1,
// and have addr2 point to addr1's points-to set
void mergePointsToSet(const G4_RegVar *addr1, const G4_RegVar *addr2);
unsigned int getIndexOfRegVar(const G4_RegVar *r) const;
public:
PointsToAnalysis(const DECLARE_LIST &declares, unsigned numBBs);
void dump(std::ostream &os = std::cerr) const;
// addr reg -> pointee regs
void
getPointsToMap(std::unordered_map<const G4_Declare *, std::vector<G4_Declare *>> &) const;
// pointee -> addr reg
void getRevPointsToMap(
std::unordered_map<G4_Declare *, std::vector<const G4_Declare *>> &);
void doPointsToAnalysis(FlowGraph &fg);
const REGVAR_VECTOR &getIndrUseVectorForBB(unsigned int bbId) const {
vISA_ASSERT(bbId < numBBs, "invalid basic block id");
return indirectUses[bbId];
}
G4_RegVar* getRootRegVar(G4_RegVar *a) const {
G4_RegVar *addr = a->getDeclare()->getAliasDeclare()
? a->getDeclare()->getRootDeclare()->getRegVar()
: a;
return addr;
}
const G4_RegVar* getRootRegVar(const G4_RegVar *a) const {
const G4_RegVar *addr = a->getDeclare()->getAliasDeclare()
? a->getDeclare()->getRootDeclare()->getRegVar()
: a;
return addr;
}
// Following methods were added to support address taken spill/fill
// Since ids of addr regvars will be reset, we fall back to using
// the regvar ptr
void insertAndMergeFilledAddr(const G4_RegVar *addr1, G4_RegVar *addr2);
const REGVAR_VECTOR *getAllInPointsTo(const G4_RegVar *addr) const;
ADDREXP_VECTOR *getAllInPointsToAddrExps(G4_RegVar *addr);
const REGVAR_VECTOR &getAllInPointsToOrIndrUse(const G4_Operand *opnd,
const G4_BB *bb) const;
G4_RegVar *getPointsTo(const G4_RegVar *addr, int idx) const;
G4_RegVar *getPointsTo(const G4_RegVar *addr, int idx,
unsigned char &offset) const;
bool isPresentInPointsTo(const G4_RegVar *addr, const G4_RegVar *var) const;
void addFillToPointsTo(unsigned int bbid, G4_RegVar *addr, G4_RegVar *newvar);
void patchPointsToSet(const G4_RegVar *addr, G4_AddrExp *opnd,
unsigned char offset);
void removeFromPointsTo(G4_RegVar *addr, G4_RegVar *vartoremove);
void fixupUnresolvedAddrVars();
};
} // namespace vISA
#endif
|
