Home | History | Annotate | Download | only in x86 
      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