-
Notifications
You must be signed in to change notification settings - Fork 391
/
GlobalRegisterAllocator.hpp
275 lines (231 loc) · 13.6 KB
/
GlobalRegisterAllocator.hpp
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
/*******************************************************************************
* Copyright IBM Corp. and others 2000
*
* This program and the accompanying materials are made available under
* the terms of the Eclipse Public License 2.0 which accompanies this
* distribution and is available at https://www.eclipse.org/legal/epl-2.0/
* or the Apache License, Version 2.0 which accompanies this distribution
* and is available at https://www.apache.org/licenses/LICENSE-2.0.
*
* This Source Code may also be made available under the following Secondary
* Licenses when the conditions for such availability set forth in the
* Eclipse Public License, v. 2.0 are satisfied: GNU General Public License,
* version 2 with the GNU Classpath Exception [1] and GNU General Public
* License, version 2 with the OpenJDK Assembly Exception [2].
*
* [1] https://www.gnu.org/software/classpath/license.html
* [2] https://openjdk.org/legal/assembly-exception.html
*
* SPDX-License-Identifier: EPL-2.0 OR Apache-2.0 OR GPL-2.0-only WITH Classpath-exception-2.0 OR GPL-2.0-only WITH OpenJDK-assembly-exception-1.0
*******************************************************************************/
#ifndef GLOBAL_REGISTER_ALLOCATOR_INCL
#define GLOBAL_REGISTER_ALLOCATOR_INCL
#include <stddef.h>
#include <stdint.h>
#include "compile/Compilation.hpp"
#include "env/TRMemory.hpp"
#include "il/DataTypes.hpp"
#include "il/Node.hpp"
#include "infra/BitVector.hpp"
#include "infra/Link.hpp"
#include "infra/List.hpp"
#include "optimizer/Optimization.hpp"
#include "optimizer/OptimizationManager.hpp"
#include "optimizer/UseDefInfo.hpp"
namespace TR { class GlobalRegister; }
class TR_NodeMappings;
namespace TR { class RegisterCandidate; }
namespace TR { class RegisterCandidates; }
class TR_StructureSubGraphNode;
namespace TR { class Block; }
namespace TR { class Symbol; }
namespace TR { class SymbolReference; }
namespace TR { class TreeTop; }
template <class T> class TR_Array;
struct StoresInBlockInfo : public TR_Link<StoresInBlockInfo>
{
TR_ALLOC(TR_Memory::GlobalRegisterAllocator)
TR::GlobalRegister *_gr;
TR::TreeTop *_lastStore;
bool _origStoreExists;
};
struct TR_PairedSymbols
{
TR_ALLOC(TR_Memory::GlobalRegisterAllocator)
TR_PairedSymbols(TR::SymbolReference *symRef1, TR::SymbolReference *symRef2) : _symRef1(symRef1), _symRef2(symRef2) {}
TR::SymbolReference *_symRef1;
TR::SymbolReference *_symRef2;
};
struct TR_SymRefCandidatePair
{
TR_ALLOC(TR_Memory::GlobalRegisterAllocator)
TR_SymRefCandidatePair(TR::SymbolReference *symRef, TR::RegisterCandidate *rc) : _symRef(symRef), _rc(rc) {}
TR::SymbolReference *_symRef;
TR::RegisterCandidate *_rc;
};
class TR_LiveRangeSplitter : public TR::Optimization
{
public:
TR_LiveRangeSplitter(TR::OptimizationManager *manager);
static TR::Optimization *create(TR::OptimizationManager *manager)
{
return new (manager->allocator()) TR_LiveRangeSplitter(manager);
}
virtual int32_t perform();
virtual const char * optDetailString() const throw();
typedef TR::typed_allocator<std::pair<uint32_t const, TR::RegisterCandidate*>, TR::Region&> SymRefCandidateMapAllocator;
typedef std::less<uint32_t> SymRefCandidateMapComparator;
typedef std::map<uint32_t, TR::RegisterCandidate*, SymRefCandidateMapComparator, SymRefCandidateMapAllocator> SymRefCandidateMap;
virtual void splitLiveRanges();
void splitLiveRanges(TR_StructureSubGraphNode *structureNode);
virtual void replaceAutosUsedIn(TR::TreeTop *currentTree, TR::Node *node, TR::Node *parent, TR::Block * block, List<TR::Block> *blocksInLoop, List<TR::Block> *exitBlocks, vcount_t visitCount, int32_t executionFrequency, SymRefCandidateMap ®isterCandidates, TR_SymRefCandidatePair **correspondingSymRefs, TR_BitVector *replacedAutosInCurrentLoop, TR_BitVector *autosThatCannotBereplacedInCurrentLoop, TR_StructureSubGraphNode *loop, TR::Block *loopInvariantBlock);
void placeStoresInLoopExits(TR::Node *node, TR_StructureSubGraphNode *loop, List<TR::Block> *blocksInLoop, TR::SymbolReference *orig, TR::SymbolReference *replacement);
TR_SymRefCandidatePair *splitAndFixPreHeader(TR::SymbolReference *symRef, TR_SymRefCandidatePair **correspondingSymRefs, TR::Block *loopInvariantBlock, TR::Node *node);
void fixExitsAfterSplit(TR::SymbolReference *symRef, TR_SymRefCandidatePair *correspondingSymRefCandidate, TR_SymRefCandidatePair **correspondingSymRefs, TR::Block *loopInvariantBlock, List<TR::Block> *blocksInLoop, TR::Node *node, SymRefCandidateMap ®isterCandidates, TR_StructureSubGraphNode *loop, TR_BitVector *replacedAutosInCurrentLoop, TR::SymbolReference *origSymRef);
void appendStoreToBlock(TR::SymbolReference *storeSymRef, TR::SymbolReference *loadSymRef, TR::Block *block, TR::Node *node);
void prependStoreToBlock(TR::SymbolReference *storeSymRef, TR::SymbolReference *loadSymRef, TR::Block *block, TR::Node *node);
protected:
List<TR::Block> _splitBlocks;
int32_t _numberOfGPRs;
int32_t _numberOfFPRs;
TR_BitVector *_storedSymRefs;
bool _changedSomething;
TR::SymbolReference **_origSymRefs;
int32_t _origSymRefCount;
};
struct TR_ReplaceNode
{
TR_ALLOC(TR_Memory::GlobalRegisterAllocator)
TR_ReplaceNode() : _old(NULL), _new(NULL) {};
TR_ReplaceNode(TR::Node *o, TR::Node *n) : _old(o), _new(n) {};
TR::Node *_old;
TR::Node *_new;
};
class TR_GlobalRegisterAllocator : public TR::Optimization
{
public:
TR_GlobalRegisterAllocator(TR::OptimizationManager *manager);
static TR::Optimization *create(TR::OptimizationManager *manager)
{
return new (manager->allocator()) TR_GlobalRegisterAllocator(manager);
}
virtual int32_t perform();
virtual const char * optDetailString() const throw();
void walkTreesAndCollectSymbolDataTypes();
void visitNodeForDataType(TR::Node*);
bool candidateCouldNeedSignExtension(int32_t symRefNum)
{
return (_candidatesNeedingSignExtension &&
_candidatesNeedingSignExtension->get(symRefNum));
}
TR_BitVector *signExtensionRequired() { return _signExtAdjustmentReqd; }
void setSignExtensionRequired(bool b, int32_t regNum)
{
if (b)
_signExtAdjustmentReqd->set(regNum);
else
_signExtAdjustmentReqd->reset(regNum);
}
TR_BitVector *signExtensionNotRequired() { return _signExtAdjustmentNotReqd; }
void setSignExtensionNotRequired(bool b, int32_t regNum)
{
if (b)
_signExtAdjustmentNotReqd->set(regNum);
else
_signExtAdjustmentNotReqd->reset(regNum);
}
TR::Node * resolveTypeMismatch(TR::DataType oldType, TR::Node *newNode);
TR::Node * resolveTypeMismatch(TR::Node *oldNode, TR::Node *newNode);
TR::Node * resolveTypeMismatch(TR::DataType inputOldType, TR::Node *oldNode, TR::Node *newNode);
typedef TR::typed_allocator<std::pair<uint32_t const, TR::RegisterCandidate*>, TR::Region&> SymRefCandidateMapAllocator;
typedef std::less<uint32_t> SymRefCandidateMapComparator;
typedef std::map<uint32_t, TR::RegisterCandidate*, SymRefCandidateMapComparator, SymRefCandidateMapAllocator> SymRefCandidateMap;
private:
void findLoopsAndAutosNoStructureInfo(vcount_t visitCount, TR::RegisterCandidate **registerCandidates);
void initializeControlFlowInfo();
void signExtendAllDefNodes(TR::Node *, List<TR::Node> *);
void findSymsUsedInIndirectAccesses(TR::Node *, TR_BitVector *, TR_BitVector *, bool);
void offerAllAutosAndRegisterParmAsCandidates(TR::Block **, int32_t, bool onlySelectedCandidates = false);
bool allocateForSymRef(TR::SymbolReference *symRef);
bool allocateForType(TR::DataType dt);
void assignRegisters();
void assignRegisters(TR::Block *);
virtual void transformNode(TR::Node *, TR::Node *, int32_t, TR::TreeTop *, TR::Block * &, TR_Array<TR::GlobalRegister> &, TR_NodeMappings *);
void addGlRegDepToExit(TR_Array<TR::Node *> &, TR::Node *, TR_Array<TR::GlobalRegister> &, TR::Block *);
virtual void prepareForBlockExit(TR::TreeTop * &, TR::Node * &, TR::Block *, TR_Array<TR::GlobalRegister> &,
TR::Block *, TR_Array<TR::Node *> &);
bool markCandidateForReloadInSuccessors(int32_t, TR::GlobalRegister *, TR::GlobalRegister *, TR::Block *, bool);
void reloadNonRegStarVariables(TR::TreeTop *, TR::Node *, TR::Block *, bool);
virtual bool registerIsLiveAcrossEdge(TR::TreeTop *, TR::Node *, TR::Block *, TR::GlobalRegister *, TR::Block * &, int32_t);
TR::Block * extendBlock(TR::Block *, TR::Block *);
TR::Block * createBlock(TR::Block *, TR::Block *);
bool tagCandidates(TR::Block *, bool);
bool tagCandidates(TR::Block *, uint32_t, bool);
TR::Node * createStoreToRegister();
TR::Node * createStoreFromRegister();
TR::Node * createLoadFromRegister();
TR::Block *getAppendBlock(TR::Block *);
TR_ScratchList<TR_PairedSymbols> _pairedSymbols;
TR_PairedSymbols *findPairedSymbols(TR::SymbolReference *symRef1, TR::SymbolReference *symRef2);
TR_ScratchList<TR_PairedSymbols> *getPairedSymbols() { return &_pairedSymbols; }
bool isSplittingCopy(TR::Node *node);
void restoreOriginalSymbol(TR::Node *node, vcount_t visitCount);
void findLoopsAndCreateAutosForSignExt(TR_StructureSubGraphNode *structureNode, vcount_t visitCount);
void createStoresForSignExt(TR::Node *node, TR::Node *parent, TR::Node *grandParent, TR::TreeTop *treetop, TR::Node **currentArrayAccess, TR::Block * block, List<TR::Block> *blocksInLoop, vcount_t visitCount, bool hasCatchBlock);
void populateSymRefNodes(TR::Node *node, vcount_t visitCount);
/*
void splitLiveRanges();
void splitLiveRanges(TR_StructureSubGraphNode *structureNode, vcount_t visitCount, TR::RegisterCandidate **registerCandidates);
void replaceAutosUsedIn(TR::Node *node, TR::Node *parent, TR::Block * block, List<TR::Block> *blocksInLoop, vcount_t visitCount, int32_t executionFrequency, TR::RegisterCandidate **registerCandidates, TR_SymRefCandidatePair **correspondingSymRefs, TR_BitVector *replacedAutosInCurrentLoop, TR_StructureSubGraphNode *loop, TR::Block *loopInvariantBlock);
void placeStoresInPreHeaderAndInLoopExits(TR::Node *node, TR_StructureSubGraphNode *loop, TR::Block *loopInvariantBlock, List<TR::Block> *blocksInLoop, TR::SymbolReference *orig, TR::SymbolReference *replacement);
void appendStoreToBlock(TR::SymbolReference *storeSymRef, TR::SymbolReference *loadSymRef, TR::Block *block, TR::Node *node);
*/
protected:
TR::Block * createNewSuccessorBlock(TR::Block *, TR::Block *, TR::TreeTop *, TR::Node *, TR::RegisterCandidate * rc);
void appendGotoBlock(TR::Block *gotoBlock, TR::Block *curBlock);
void transformBlock(TR::TreeTop *);
bool isTypeAvailable(TR::SymbolReference *symref);
bool isSymRefAvailable(TR::SymbolReference *symRef);
bool isSymRefAvailable(TR::SymbolReference *symRef, List<TR::Block> *blocksInLoop);
void transformMultiWayBranch(TR::TreeTop *, TR::Node *, TR::Block *, TR_Array<TR::GlobalRegister> &, bool regStarTransformDone = false);
void transformBlockExit(TR::TreeTop *, TR::Node *, TR::Block *, TR_Array<TR::GlobalRegister> &, TR::Block *);
void addCandidateReloadsToEntry(TR::TreeTop *, TR_Array<TR::GlobalRegister> &, TR::Block *);
void addRegLoadsToEntry(TR::TreeTop *, TR_Array<TR::GlobalRegister> &, TR::Block *);
void addStoresForCatchBlockLoads(TR::TreeTop *appendPoint, TR_Array<TR::GlobalRegister> &extBlockRegisters, TR::Block *throwingBlock);
bool isNodeAvailable(TR::Node *node);
TR::GlobalRegister * getGlobalRegister(TR::Symbol *, TR_Array<TR::GlobalRegister> &, TR::Block *);
TR::GlobalRegister * getGlobalRegisterWithoutChangingCurrentCandidate(TR::Symbol *, TR_Array<TR::GlobalRegister> &, TR::Block *);
StoresInBlockInfo * findRegInStoreInfo(TR::GlobalRegister *);
int32_t numberOfRegistersLiveOnEntry(TR_Array<TR::GlobalRegister> &, bool);
TR_PairedSymbols *findOrCreatePairedSymbols(TR::SymbolReference *symRef1, TR::SymbolReference *symRef2);
bool isDependentStore(TR::Node *, const TR_UseDefInfo::BitVector &, TR::SymbolReference *, bool *);
TR::TreeTop * findPrevTreeTop(TR::TreeTop * &, TR::Node * &, TR::Block *, TR::Block *);
vcount_t _visitCount;
int32_t _firstGlobalRegisterNumber;
int32_t _lastGlobalRegisterNumber;
TR::Block *_appendBlock;
SymRefCandidateMap *_registerCandidates;
TR_ScratchList<TR::Block> _newBlocks;
TR_BitVector *_temp, *_temp2;
TR_BitVector *_candidatesNeedingSignExtension;
TR_BitVector *_candidatesSignExtendedInThisLoop;
TR_LinkHead<StoresInBlockInfo> _storesInBlockInfo;
TR_BitVector *_signExtAdjustmentReqd;
TR_BitVector *_signExtAdjustmentNotReqd;
TR_BitVector *_signExtDifference;
TR_BitVector *_valueModifiedSymRefs;
TR::RegisterCandidates * _candidates;
TR::Node **_nodesForSymRefs;
struct BlockInfo
{
TR_ALLOC(TR_Memory::GlobalRegisterAllocator)
BlockInfo() : _alwaysReached(false) { }
bool _inALoop;
bool _alwaysReached;
};
BlockInfo & blockInfo(int32_t);
BlockInfo * _blockInfo;
int32_t _origSymRefCount;
TR::Block *_osrCatchSucc;
};
#endif