1 /* 2 * Copyright (C) 2009 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 #ifndef DALVIK_VM_COMPILER_IR_H_ 18 #define DALVIK_VM_COMPILER_IR_H_ 19 20 #include "codegen/Optimizer.h" 21 22 typedef enum RegisterClass { 23 kCoreReg, 24 kFPReg, 25 kAnyReg, 26 } RegisterClass; 27 28 typedef enum RegLocationType { 29 kLocDalvikFrame = 0, 30 kLocPhysReg, 31 kLocRetval, // Return region in interpState 32 kLocSpill, 33 } RegLocationType; 34 35 typedef struct RegLocation { 36 RegLocationType location:2; 37 unsigned wide:1; 38 unsigned fp:1; // Hint for float/double 39 u1 lowReg:6; // First physical register 40 u1 highReg:6; // 2nd physical register (if wide) 41 s2 sRegLow; // SSA name for low Dalvik word 42 } RegLocation; 43 44 #define INVALID_SREG (-1) 45 #define INVALID_REG (0x3F) 46 47 typedef enum BBType { 48 /* For coding convenience reasons chaining cell types should appear first */ 49 kChainingCellNormal = 0, 50 kChainingCellHot, 51 kChainingCellInvokeSingleton, 52 kChainingCellInvokePredicted, 53 kChainingCellBackwardBranch, 54 kChainingCellGap, 55 /* Don't insert new fields between Gap and Last */ 56 kChainingCellLast = kChainingCellGap + 1, 57 kEntryBlock, 58 kDalvikByteCode, 59 kExitBlock, 60 kPCReconstruction, 61 kExceptionHandling, 62 kCatchEntry, 63 } BBType; 64 65 typedef enum JitMode { 66 kJitTrace = 0, // Acyclic - all instructions come from the trace descriptor 67 kJitLoop, // Cycle - trace descriptor is used as a hint 68 kJitMethod, // Whole method 69 } JitMode; 70 71 typedef struct ChainCellCounts { 72 union { 73 u1 count[kChainingCellLast]; /* include one more space for the gap # */ 74 u4 dummyForAlignment; 75 } u; 76 } ChainCellCounts; 77 78 typedef struct LIR { 79 int offset; 80 struct LIR *next; 81 struct LIR *prev; 82 struct LIR *target; 83 } LIR; 84 85 enum ExtendedMIROpcode { 86 kMirOpFirst = kNumPackedOpcodes, 87 kMirOpPhi = kMirOpFirst, 88 kMirOpNullNRangeUpCheck, 89 kMirOpNullNRangeDownCheck, 90 kMirOpLowerBound, 91 kMirOpPunt, 92 kMirOpCheckInlinePrediction, // Gen checks for predicted inlining 93 kMirOpLast, 94 }; 95 96 struct SSARepresentation; 97 98 typedef enum { 99 kMIRIgnoreNullCheck = 0, 100 kMIRNullCheckOnly, 101 kMIRIgnoreRangeCheck, 102 kMIRRangeCheckOnly, 103 kMIRInlined, // Invoke is inlined (ie dead) 104 kMIRInlinedPred, // Invoke is inlined via prediction 105 kMIRCallee, // Instruction is inlined from callee 106 kMIRInvokeMethodJIT, // Callee is JIT'ed as a whole method 107 } MIROptimizationFlagPositons; 108 109 #define MIR_IGNORE_NULL_CHECK (1 << kMIRIgnoreNullCheck) 110 #define MIR_NULL_CHECK_ONLY (1 << kMIRNullCheckOnly) 111 #define MIR_IGNORE_RANGE_CHECK (1 << kMIRIgnoreRangeCheck) 112 #define MIR_RANGE_CHECK_ONLY (1 << kMIRRangeCheckOnly) 113 #define MIR_INLINED (1 << kMIRInlined) 114 #define MIR_INLINED_PRED (1 << kMIRInlinedPred) 115 #define MIR_CALLEE (1 << kMIRCallee) 116 #define MIR_INVOKE_METHOD_JIT (1 << kMIRInvokeMethodJIT) 117 118 typedef struct CallsiteInfo { 119 const char *classDescriptor; 120 Object *classLoader; 121 const Method *method; 122 LIR *misPredBranchOver; 123 } CallsiteInfo; 124 125 typedef struct MIR { 126 DecodedInstruction dalvikInsn; 127 unsigned int width; 128 unsigned int offset; 129 struct MIR *prev; 130 struct MIR *next; 131 struct SSARepresentation *ssaRep; 132 int OptimizationFlags; 133 int seqNum; 134 union { 135 // Used by the inlined insn from the callee to find the mother method 136 const Method *calleeMethod; 137 // Used by the inlined invoke to find the class and method pointers 138 CallsiteInfo *callsiteInfo; 139 } meta; 140 } MIR; 141 142 struct BasicBlockDataFlow; 143 144 /* For successorBlockList */ 145 typedef enum BlockListType { 146 kNotUsed = 0, 147 kCatch, 148 kPackedSwitch, 149 kSparseSwitch, 150 } BlockListType; 151 152 typedef struct BasicBlock { 153 int id; 154 bool visited; 155 bool hidden; 156 unsigned int startOffset; 157 const Method *containingMethod; // For blocks from the callee 158 BBType blockType; 159 bool needFallThroughBranch; // For blocks ended due to length limit 160 bool isFallThroughFromInvoke; // True means the block needs alignment 161 MIR *firstMIRInsn; 162 MIR *lastMIRInsn; 163 struct BasicBlock *fallThrough; 164 struct BasicBlock *taken; 165 struct BasicBlock *iDom; // Immediate dominator 166 struct BasicBlockDataFlow *dataFlowInfo; 167 BitVector *predecessors; 168 BitVector *dominators; 169 BitVector *iDominated; // Set nodes being immediately dominated 170 BitVector *domFrontier; // Dominance frontier 171 struct { // For one-to-many successors like 172 BlockListType blockListType; // switch and exception handling 173 GrowableList blocks; 174 } successorBlockList; 175 } BasicBlock; 176 177 /* 178 * The "blocks" field in "successorBlockList" points to an array of 179 * elements with the type "SuccessorBlockInfo". 180 * For catch blocks, key is type index for the exception. 181 * For swtich blocks, key is the case value. 182 */ 183 typedef struct SuccessorBlockInfo { 184 BasicBlock *block; 185 int key; 186 } SuccessorBlockInfo; 187 188 struct LoopAnalysis; 189 struct RegisterPool; 190 191 typedef enum AssemblerStatus { 192 kSuccess, 193 kRetryAll, 194 kRetryHalve 195 } AssemblerStatus; 196 197 typedef struct CompilationUnit { 198 int numInsts; 199 int numBlocks; 200 GrowableList blockList; 201 const Method *method; 202 const JitTraceDescription *traceDesc; 203 LIR *firstLIRInsn; 204 LIR *lastLIRInsn; 205 LIR *literalList; // Constants 206 LIR *classPointerList; // Relocatable 207 int numClassPointers; 208 LIR *chainCellOffsetLIR; 209 GrowableList pcReconstructionList; 210 int headerSize; // bytes before the first code ptr 211 int dataOffset; // starting offset of literal pool 212 int totalSize; // header + code size 213 AssemblerStatus assemblerStatus; // Success or fix and retry 214 int assemblerRetries; // How many times tried to fix assembly 215 unsigned char *codeBuffer; 216 void *baseAddr; 217 bool printMe; 218 bool allSingleStep; 219 bool hasClassLiterals; // Contains class ptrs used as literals 220 bool hasLoop; // Contains a loop 221 bool hasInvoke; // Contains an invoke instruction 222 bool heapMemOp; // Mark mem ops for self verification 223 bool usesLinkRegister; // For self-verification only 224 int profileCodeSize; // Size of the profile prefix in bytes 225 int numChainingCells[kChainingCellGap]; 226 LIR *firstChainingLIR[kChainingCellGap]; 227 LIR *chainingCellBottom; 228 struct RegisterPool *regPool; 229 int optRound; // round number to tell an LIR's age 230 jmp_buf *bailPtr; 231 JitInstructionSetType instructionSet; 232 /* Number of total regs used in the whole cUnit after SSA transformation */ 233 int numSSARegs; 234 /* Map SSA reg i to the Dalvik[15..0]/Sub[31..16] pair. */ 235 GrowableList *ssaToDalvikMap; 236 237 /* The following are new data structures to support SSA representations */ 238 /* Map original Dalvik reg i to the SSA[15..0]/Sub[31..16] pair */ 239 int *dalvikToSSAMap; // length == method->registersSize 240 BitVector *isConstantV; // length == numSSAReg 241 int *constantValues; // length == numSSAReg 242 243 /* Data structure for loop analysis and optimizations */ 244 struct LoopAnalysis *loopAnalysis; 245 246 /* Map SSA names to location */ 247 RegLocation *regLocation; 248 int sequenceNumber; 249 250 /* 251 * Set to the Dalvik PC of the switch instruction if it has more than 252 * MAX_CHAINED_SWITCH_CASES cases. 253 */ 254 const u2 *switchOverflowPad; 255 256 JitMode jitMode; 257 int numReachableBlocks; 258 int numDalvikRegisters; // method->registersSize + inlined 259 BasicBlock *entryBlock; 260 BasicBlock *exitBlock; 261 BasicBlock *puntBlock; // punting to interp for exceptions 262 BasicBlock *backChainBlock; // for loop-trace 263 BasicBlock *curBlock; 264 BasicBlock *nextCodegenBlock; // for extended trace codegen 265 GrowableList dfsOrder; 266 GrowableList domPostOrderTraversal; 267 BitVector *tryBlockAddr; 268 BitVector **defBlockMatrix; // numDalvikRegister x numBlocks 269 BitVector *tempBlockV; 270 BitVector *tempDalvikRegisterV; 271 BitVector *tempSSARegisterV; // numSSARegs 272 bool printSSANames; 273 void *blockLabelList; 274 bool quitLoopMode; // cold path/complex bytecode 275 } CompilationUnit; 276 277 #if defined(WITH_SELF_VERIFICATION) 278 #define HEAP_ACCESS_SHADOW(_state) cUnit->heapMemOp = _state 279 #else 280 #define HEAP_ACCESS_SHADOW(_state) 281 #endif 282 283 BasicBlock *dvmCompilerNewBB(BBType blockType, int blockId); 284 285 void dvmCompilerAppendMIR(BasicBlock *bb, MIR *mir); 286 287 void dvmCompilerPrependMIR(BasicBlock *bb, MIR *mir); 288 289 void dvmCompilerInsertMIRAfter(BasicBlock *bb, MIR *currentMIR, MIR *newMIR); 290 291 void dvmCompilerAppendLIR(CompilationUnit *cUnit, LIR *lir); 292 293 void dvmCompilerInsertLIRBefore(LIR *currentLIR, LIR *newLIR); 294 295 void dvmCompilerInsertLIRAfter(LIR *currentLIR, LIR *newLIR); 296 297 void dvmCompilerAbort(CompilationUnit *cUnit); 298 299 /* Debug Utilities */ 300 void dvmCompilerDumpCompilationUnit(CompilationUnit *cUnit); 301 302 #endif // DALVIK_VM_COMPILER_IR_H_ 303