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