• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2012 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 
18 /*! \file ncg_o1_data.h
19     \brief A header file to define data structures used by register allocator & const folding
20 */
21 #ifndef _DALVIK_NCG_ANALYSISO1_H
22 #define _DALVIK_NCG_ANALYSISO1_H
23 
24 #include "Dalvik.h"
25 #include "enc_wrapper.h"
26 #include "Lower.h"
27 #ifdef WITH_JIT
28 #include "compiler/CompilerIR.h"
29 #endif
30 
31 //! maximal number of edges per basic block
32 #define MAX_NUM_EDGE_PER_BB 300
33 //! maximal number of basic blocks per method
34 #define MAX_NUM_BBS_PER_METHOD 1000
35 //! maximal number of virtual registers per basic block
36 #define MAX_REG_PER_BASICBLOCK 140
37 //! maximal number of virtual registers per bytecode
38 #define MAX_REG_PER_BYTECODE 40
39 //! maximal number of virtual registers per method
40 #define MAX_REG_PER_METHOD 200
41 //! maximal number of temporaries per bytecode
42 #define MAX_TEMP_REG_PER_BYTECODE 30
43 //! maximal number of GG GPR VRs in a method
44 #define MAX_GLOBAL_VR      2
45 //! maximal number of GG XMM VRs in a method
46 #define MAX_GLOBAL_VR_XMM  4
47 #define MAX_CONST_REG 150
48 
49 #define MASK_FOR_TYPE 7 //last 3 bits 111
50 
51 #define LOOP_COUNT 10
52 //! maximal number of entries in compileTable
53 #define COMPILE_TABLE_SIZE 200
54 //! maximal number of transfer points per basic block
55 #define MAX_XFER_PER_BB 1000  //on Jan 4
56 #define PC_FOR_END_OF_BB -999
57 #define PC_FOR_START_OF_BB -998
58 
59 //! various cases of overlapping between 2 variables
60 typedef enum OverlapCase {
61   OVERLAP_ALIGN = 0,
62   OVERLAP_B_IS_LOW_OF_A,
63   OVERLAP_B_IS_HIGH_OF_A,
64   OVERLAP_LOW_OF_A_IS_HIGH_OF_B,
65   OVERLAP_HIGH_OF_A_IS_LOW_OF_B,
66   OVERLAP_A_IS_LOW_OF_B,
67   OVERLAP_A_IS_HIGH_OF_B,
68   OVERLAP_B_COVER_A,
69   OVERLAP_B_COVER_LOW_OF_A,
70   OVERLAP_B_COVER_HIGH_OF_A,
71   OVERLAP_NO
72 } OverlapCase;
73 
74 //!access type of a variable
75 typedef enum RegAccessType {
76   REGACCESS_D = 0,
77   REGACCESS_U,
78   REGACCESS_DU,
79   REGACCESS_UD,
80   REGACCESS_L,
81   REGACCESS_H,
82   REGACCESS_UL,
83   REGACCESS_UH,
84   REGACCESS_LU,
85   REGACCESS_HU,
86   REGACCESS_N, //no access
87   REGACCESS_UNKNOWN
88 } RegAccessType;
89 //! a variable can be local (L), globally local (GL) or global (GG)
90 typedef enum GlobalType {
91   GLOBALTYPE_GG,
92   GLOBALTYPE_GL,
93   GLOBALTYPE_L
94 } GlobalType;
95 typedef enum VRState {
96   VRSTATE_SPILLED,
97   VRSTATE_UPDATED,
98   VRSTATE_CLEAN
99 } VRState;
100 //! helper state to determine if freeing VRs needs to be delayed
101 enum VRDelayFreeFlags {
102   VRDELAY_NONE = 0, // used when VR can be freed from using physical register if needed
103   VRDELAY_NULLCHECK = 1 << 0, // used when VR is used for null check and freeing must be delayed
104   VRDELAY_BOUNDCHECK = 1 << 1 // used when VR is used for bound check and freeing must be delayed
105 };
106 typedef enum TRState { //state of temporary registers
107   TRSTATE_SPILLED,
108   TRSTATE_UNSPILLED,
109   TRSTATE_CLEAN
110 } TRState;
111 //!information about a physical register
112 typedef struct RegisterInfo {
113   PhysicalReg physicalReg;
114   bool isUsed;
115   bool isCalleeSaved;
116   int freeTimeStamp;
117 } RegisterInfo;
118 typedef struct UniqueRegister {
119   LowOpndRegType physicalType;
120   int regNum;
121   int numExposedUsage;
122   PhysicalReg physicalReg;
123 } UniqueRegister;
124 //!specifies the weight of a VR allocated to a specific physical register
125 //!it is used for GPR VR only
126 typedef struct RegAllocConstraint {
127   PhysicalReg physicalReg;
128   int count;
129 } RegAllocConstraint;
130 
131 typedef enum XferType {
132   XFER_MEM_TO_XMM, //for usage
133   XFER_DEF_TO_MEM, //def is gp
134   XFER_DEF_TO_GP_MEM,
135   XFER_DEF_TO_GP,
136   XFER_DEF_IS_XMM //def is xmm
137 } XferType;
138 typedef struct XferPoint {
139   int tableIndex; //generated from a def-use pair
140   XferType xtype;
141   int offsetPC;
142   int regNum; //get or set VR at offsetPC
143   LowOpndRegType physicalType;
144 
145   //if XFER_DEF_IS_XMM
146   int vr_gpl; //a gp VR that uses the lower half of the def
147   int vr_gph;
148   bool dumpToXmm;
149   bool dumpToMem;
150 } XferPoint;
151 
152 //!for def: accessType means which part of the VR defined at offestPC is live now
153 //!for use: accessType means which part of the usage comes from the reachingDef
154 typedef struct DefOrUse {
155   int offsetPC; //!the program point
156   int regNum; //!access the virtual reg
157   LowOpndRegType physicalType; //!xmm or gp or ss
158   RegAccessType accessType; //!D, L, H, N
159 } DefOrUse;
160 //!a link list of DefOrUse
161 typedef struct DefOrUseLink {
162   int offsetPC;
163   int regNum; //access the virtual reg
164   LowOpndRegType physicalType; //xmm or gp
165   RegAccessType accessType; //D, L, H, N
166   struct DefOrUseLink* next;
167 } DefOrUseLink;
168 //!pair of def and uses
169 typedef struct DefUsePair {
170   DefOrUseLink* uses;
171   DefOrUseLink* useTail;
172   int num_uses;
173   DefOrUse def;
174   struct DefUsePair* next;
175 } DefUsePair;
176 
177 //!information associated with a virtual register
178 //!the pair <regNum, physicalType> uniquely determines a variable
179 typedef struct VirtualRegInfo {
180   int regNum;
181   LowOpndRegType physicalType;
182   int refCount;
183   RegAccessType accessType;
184   GlobalType gType;
185   int physicalReg_GG;
186   RegAllocConstraint allocConstraints[8];
187   RegAllocConstraint allocConstraintsSorted[8];
188 
189   DefOrUse reachingDefs[3]; //!reaching defs to the virtual register
190   int num_reaching_defs;
191 } VirtualRegInfo;
192 //!information of whether a VR is constant and its value
193 typedef struct ConstVRInfo {
194   int regNum;
195   int value;
196   bool isConst;
197 } ConstVRInfo;
198 #define NUM_ACCESS_IN_LIVERANGE 10
199 //!specifies one live range
200 typedef struct LiveRange {
201   int start;
202   int end; //inclusive
203   //all accesses in the live range
204   int num_access;
205   int num_alloc;
206   int* accessPC;
207   struct LiveRange* next;
208 } LiveRange;
209 typedef struct BoundCheckIndex {
210   int indexVR;
211   bool checkDone;
212 } BoundCheckIndex;
213 //!information for a virtual register such as live ranges, in memory
214 typedef struct MemoryVRInfo {
215   int regNum;
216   bool inMemory;
217   bool nullCheckDone;
218   BoundCheckIndex boundCheck;
219   int num_ranges;
220   LiveRange* ranges;
221   u4 delayFreeFlags; //! for use with flags defined by VRDelayFreeFlags enum
222 } MemoryVRInfo;
223 //!information of a temporary
224 //!the pair <regNum, physicalType> uniquely determines a variable
225 typedef struct TempRegInfo {
226   int regNum;
227   int physicalType;
228   int refCount;
229   int linkageToVR;
230   int versionNum;
231   bool shareWithVR; //for temp. regs updated by get_virtual_reg
232   bool is8Bit;
233 } TempRegInfo;
234 struct BasicBlock_O1;
235 //!all variables accessed
236 //!the pair <regNum, physicalType> uniquely determines a variable
237 typedef struct compileTableEntry {
238   int regNum;
239   int physicalType; //gp, xmm or scratch, virtual
240   int physicalReg;
241   int physicalReg_prev; //for spilled GG VR
242   RegAccessType accessType;
243 
244   bool isConst;
245   int value[2]; //[0]: lower [1]: higher
246   int refCount;
247 
248   int linkageToVR; //for temporary registers only
249   GlobalType gType;
250   struct BasicBlock_O1* bb; //bb VR belongs to
251   int indexToInfoBB;
252 
253   VRState regState;
254   TRState trState; //for temporary registers only
255   int spill_loc_index; //for temporary registers only
256 } compileTableEntry;
257 //!to save the state of register allocator
258 typedef struct regAllocStateEntry1 {
259   int spill_loc_index;
260   int physicalReg;
261 } regAllocStateEntry1;
262 typedef struct regAllocStateEntry2 {
263   int regNum; //
264   bool inMemory; //whether 4-byte virtual reg is in memory
265 } regAllocStateEntry2;
266 //!edge in control flow graph
267 typedef struct Edge_O1 {
268   struct BasicBlock_O1* src;
269   struct BasicBlock_O1* dst;
270 } Edge_O1;
271 //!information associated with a basic block
272 typedef struct BasicBlock_O1 {
273   int bb_index;
274   int bb_index2;
275   int pc_start;       //!inclusive
276 #ifndef WITH_JIT
277   int pc_end;         //!exclusive
278   Edge_O1* in_edges[MAX_NUM_EDGE_PER_BB]; //array of Edge*
279   int num_in_edges;
280   Edge_O1* out_edges[MAX_NUM_EDGE_PER_BB];
281   int num_out_edges;
282 #else
283   int pc_end;
284   BasicBlock* jitBasicBlock;
285 #endif
286   VirtualRegInfo infoBasicBlock[MAX_REG_PER_BASICBLOCK];
287   int num_regs;
288 
289   RegAllocConstraint allocConstraints[8]; //# of times a hardcoded register is used in this basic block
290   //a physical register that is used many times has a lower priority to get picked in getFreeReg
291   RegAllocConstraint allocConstraintsSorted[8]; //count from low to high
292 
293   DefUsePair* defUseTable;
294   DefUsePair* defUseTail;
295   int num_defs;
296   XferPoint xferPoints[MAX_XFER_PER_BB]; //program points where the transfer is required
297   int num_xfer_points;
298 
299   bool endsWithReturn;
300   bool hasAccessToGlue;
301 } BasicBlock_O1;
302 typedef struct CFG_O1 {
303   BasicBlock_O1* head;
304 } CFG_O1;
305 //!worklist to create a control flow graph
306 typedef struct CFGWork {
307   BasicBlock_O1* bb_prev;
308   int targetOff;
309   struct CFGWork* nextItem;
310 } CFGWork;
311 
312 /////////////////////////////////////////
313 extern compileTableEntry compileTable[COMPILE_TABLE_SIZE];
314 extern int num_compile_entries;
315 extern VirtualRegInfo infoByteCode[MAX_REG_PER_BYTECODE];
316 extern int num_regs_per_bytecode;
317 extern TempRegInfo infoByteCodeTemp[MAX_TEMP_REG_PER_BYTECODE];
318 extern int num_temp_regs_per_bytecode;
319 extern VirtualRegInfo infoMethod[MAX_REG_PER_METHOD];
320 extern int num_regs_per_method;
321 extern BasicBlock_O1* currentBB;
322 
323 extern BasicBlock_O1* method_bbs[MAX_NUM_BBS_PER_METHOD];
324 extern int num_bbs_for_method;
325 extern BasicBlock_O1* method_bbs_sorted[MAX_NUM_BBS_PER_METHOD];
326 extern BasicBlock_O1* bb_entry;
327 extern int pc_start;
328 extern int pc_end;
329 extern int current_bc_size;
330 extern int num_exception_handlers;
331 extern int exceptionHandlers[10];
332 
333 extern int num_const_vr;
334 extern ConstVRInfo constVRTable[MAX_CONST_REG];
335 
336 extern int genSet[MAX_REG_PER_BYTECODE];
337 extern int killSet[MAX_REG_PER_BYTECODE];
338 extern int num_regs_gen; //per bytecode
339 extern int num_regs_kill; //per bytecode
340 
341 extern int genSetBB[MAX_NUM_BBS_PER_METHOD][40];
342 extern int killSetBB[MAX_NUM_BBS_PER_METHOD][40]; //same as size of memVRTable
343 extern int num_gen_bb[MAX_NUM_BBS_PER_METHOD];
344 extern int num_kill_bb[MAX_NUM_BBS_PER_METHOD];
345 
346 extern int nullCheck_inB[MAX_NUM_BBS_PER_METHOD][40];
347 extern int nullCheck_inSize[MAX_NUM_BBS_PER_METHOD];
348 extern int nullCheck_outB[MAX_NUM_BBS_PER_METHOD][40];
349 extern int nullCheck_outSize[MAX_NUM_BBS_PER_METHOD];
350 
351 typedef enum GlueVarType {
352   RES_CLASS = 0,
353   RES_METHOD,
354   RES_FIELD,
355   RES_STRING,
356   GLUE_DVMDEX,
357   GLUE_METHOD_CLASS,
358   GLUE_METHOD
359 } GlueVarType;
360 
361 void forwardAnalysis(int type);
362 
363 //functions in bc_visitor.c
364 int getByteCodeSize();
365 bool getConstInfo(BasicBlock_O1* bb);
366 int getVirtualRegInfo(VirtualRegInfo* infoArray);
367 int getTempRegInfo(TempRegInfo* infoArray);
368 int createCFGHandler(Method* method);
369 
370 int findVirtualRegInTable(u2 vA, LowOpndRegType type, bool printError);
371 int searchCompileTable(int type, int regNum);
372 BasicBlock_O1* createBasicBlock(int src_pc, int end_pc);
373 void handleJump(BasicBlock_O1* bb_prev, int relOff);
374 void connectBasicBlock(BasicBlock_O1* src, BasicBlock_O1* dst);
375 int insertWorklist(BasicBlock_O1* bb_prev, int targetOff);
376 
377 int collectInfoOfBasicBlock(Method* method, BasicBlock_O1* bb); //update bb->infoBasicBlock
378 
379 void updateCurrentBBWithConstraints(PhysicalReg reg);
380 void updateConstInfo(BasicBlock_O1*);
381 OpndSize getRegSize(int type);
382 void invalidateVRDueToConst(int reg, OpndSize size);
383 #endif
384 
385