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
|
/*========================== begin_copyright_notice ============================
Copyright (C) 2017-2021 Intel Corporation
SPDX-License-Identifier: MIT
============================= end_copyright_notice ===========================*/
#pragma once
#include "Compiler/CISACodeGen/CISACodeGen.h"
#include "common/LLVMWarningsPush.hpp"
#include "llvm/Support/Allocator.h"
#include "common/LLVMWarningsPop.hpp"
namespace llvm
{
class FunctionPass;
class raw_ostream;
}
namespace IGC
{
/// Generic Polynomial Symbolic Expression (PSE)
/// PSE = C0*T0 + C1*T1 + C2*T2 + ... + Cn; (n = #terms)
/// where each Ti = Vi0 * Vi1 * Vi2 * ... * Vim (m = #Values)
//
// class SymTerm : symbolic term for denoting Ci * Ti
//
// class SymProd : symbolic product for Ti.
// Right now, no SymProd will be shared among different expressions.
// (we could use FoldingSet to make SymProd unique & shared among all
// symbolic expressions in the way that the same product will always
// use the same object of SymProd. In doing so, comparison of two
// products are simply carried out by comparing their pointer value.)
//
class SymProd {
public:
llvm::SmallVector<const llvm::Value*, 2> Prod;
SymProd() {}
SymProd(const SymProd& P) : Prod(P.Prod) {}
SymProd& operator=(const SymProd& P) = delete;
#if 0
{
Prod.append(P.Prod.begin(), P.Prod.end());
}
#endif
};
class SymTerm {
public:
SymProd* Term;
int64_t Coeff;
SymTerm() : Term(nullptr), Coeff(1) {}
SymTerm(const SymTerm& T) = delete;
SymTerm& operator=(const SymTerm& T) = delete;
};
// class SymExpr : representation of Symbolic expression.
// SymTerms[0] + SymTerms[1] + ... + SymTerms[n] + ConstTerm
// where n = SymTerms.size().
class SymExpr {
public:
llvm::SmallVector<SymTerm*, 4> SymTerms;
int64_t ConstTerm;
SymExpr() : ConstTerm(0) {}
};
/*
* This is an integer symbolic evaluation, intended for address calculation
* of straight-line code.
*
* The storage of symbolic expression is owned by this class. Once this
* class is destructed, so is its storage for the expression (including
* storage for SymTerm).
*/
class SymbolicEvaluation
{
public:
SymbolicEvaluation() : m_DL(nullptr), m_nextValueID(0) {}
void setDataLayout(const llvm::DataLayout* aDL) { m_DL = aDL; }
// Return a Canonicalized Polynomial Expression.
SymExpr* getSymExpr(const llvm::Value* V);
// If S1 - S0 = constant, return true and set "COff" to that constant
bool isOffByConstant(SymExpr* S0, SymExpr* S1, int64_t& COff);
// Return the lexical order of two products. It is used to sort
// an expression in canonical form:
// -1: P0 precedes P1
// 0: P0 has the same order as P1 ( P0 must be equal to P1)
// 1: P1 precedes P0
int cmp(const SymProd* T0, const SymProd* T1);
SymExpr* add(SymExpr* S0, SymExpr* S1, bool negateS1);
SymExpr* add(SymExpr* S, int64_t C);
SymExpr* mul(SymExpr* S, int64_t C);
// If N is a factor of S's symbolic part, that is, N
// can divide all coeffs of S's symbolic terms.
bool isFactor(SymExpr* S, int N)
{
for (int i = 0, e = S->SymTerms.size(); i < e; ++i)
{
if ((S->SymTerms[i]->Coeff % N) != 0) {
return false;
}
}
return true;
}
void copy(SymTerm* D, SymTerm* S)
{
D->Term = new (m_symEvaAllocator) SymProd(*S->Term);
D->Coeff = S->Coeff;
}
void copy(SymExpr* D, const SymExpr* S)
{
for (int i = 0, e = S->SymTerms.size(); i < e; ++i)
{
SymTerm* newT = new (m_symEvaAllocator) SymTerm();
copy(newT, S->SymTerms[i]);
D->SymTerms.push_back(newT);
}
D->ConstTerm = S->ConstTerm;
}
void clear() {
m_nextValueID = 0;
m_DL = nullptr;
m_symInfos.clear();
m_symEvaAllocator.Reset();
}
#if defined(_DEBUG)
void print(llvm::raw_ostream& OS, SymProd* P);
void print(llvm::raw_ostream& OS, SymTerm* T);
void print(llvm::raw_ostream& OS, SymExpr* SE);
void print(llvm::raw_ostream& OS, const llvm::Value* V);
void print_varMapping(llvm::raw_ostream& OS, SymProd* P);
void print_varMapping(llvm::raw_ostream& OS, SymTerm* T);
void print_varMapping(llvm::raw_ostream& OS, SymExpr* SE);
void print_varMapping(llvm::raw_ostream& OS, const llvm::Value* V);
void dump_symbols();
void dump(SymProd* P);
void dump(SymTerm* T);
void dump(SymExpr* SE);
void dump(const llvm::Value* V);
#endif
private:
const llvm::DataLayout* m_DL;
// This struct is to hold info about symbol (Value), such as its ID,
// and its equivalent symbolic expression.
typedef struct {
int ID;
SymExpr* symExpr;
} ValueSymInfo;
typedef llvm::DenseMap<const llvm::Value*, ValueSymInfo*> SymInfoMap;
// Used to assign a unique ID to ValueSymInfo
int m_nextValueID;
SymInfoMap m_symInfos;
llvm::BumpPtrAllocator m_symEvaAllocator;
// A varaint of getSymExpr. This one does not create SymExpr if
// V is an integer constant. Instead, return constant as 'C'.
void getSymExprOrConstant(const llvm::Value* V, SymExpr*& S, int64_t& C);
ValueSymInfo* getSymInfo(const llvm::Value* V)
{
auto SIIter = m_symInfos.find(V);
if (SIIter != m_symInfos.end())
{
ValueSymInfo* VSI = SIIter->second;
return VSI;
}
return nullptr;
}
void setSymInfo(const llvm::Value* V, SymExpr* E)
{
ValueSymInfo* VSI = new (m_symEvaAllocator) ValueSymInfo();
VSI->ID = m_nextValueID++;
VSI->symExpr = E;
m_symInfos.insert(std::make_pair(V, VSI));
}
};
llvm::FunctionPass* createSLMConstPropPass();
} // namespace IGC
|
