buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2011 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 ART_SRC_COMPILER_COMPILER_IR_H_ |
| 18 | #define ART_SRC_COMPILER_COMPILER_IR_H_ |
| 19 | |
| 20 | #include "codegen/Optimizer.h" |
buzbee | c143c55 | 2011-08-20 17:38:58 -0700 | [diff] [blame] | 21 | #include <vector> |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 22 | |
| 23 | typedef enum RegisterClass { |
| 24 | kCoreReg, |
| 25 | kFPReg, |
| 26 | kAnyReg, |
| 27 | } RegisterClass; |
| 28 | |
| 29 | typedef enum RegLocationType { |
| 30 | kLocDalvikFrame = 0, // Normal Dalvik register |
| 31 | kLocPhysReg, |
| 32 | kLocSpill, |
| 33 | } RegLocationType; |
| 34 | |
buzbee | 67bc236 | 2011-10-11 18:08:40 -0700 | [diff] [blame^] | 35 | typedef struct PromotionMap { |
| 36 | RegLocationType coreLocation:3; |
| 37 | u1 coreReg; |
| 38 | RegLocationType fpLocation:3; |
| 39 | u1 fpReg; |
| 40 | bool firstInPair; |
| 41 | } PromotionMap; |
| 42 | |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 43 | typedef struct RegLocation { |
buzbee | 67bc236 | 2011-10-11 18:08:40 -0700 | [diff] [blame^] | 44 | RegLocationType location:3; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 45 | unsigned wide:1; |
buzbee | 67bc236 | 2011-10-11 18:08:40 -0700 | [diff] [blame^] | 46 | unsigned defined:1; // Do we know the type? |
| 47 | unsigned fp:1; // Floating point? |
| 48 | unsigned core:1; // Non-floating point? |
| 49 | unsigned highWord:1; // High word of pair? |
| 50 | unsigned home:1; // Does this represent the home location? |
| 51 | u1 lowReg; // First physical register |
| 52 | u1 highReg; // 2nd physical register (if wide) |
| 53 | s2 sRegLow; // SSA name for low Dalvik word |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 54 | } RegLocation; |
| 55 | |
| 56 | #define INVALID_SREG (-1) |
buzbee | 3ddc0d1 | 2011-10-05 10:36:21 -0700 | [diff] [blame] | 57 | #define INVALID_VREG (0xFFFFU) |
buzbee | 67bc236 | 2011-10-11 18:08:40 -0700 | [diff] [blame^] | 58 | #define INVALID_REG (0xFF) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 59 | #define INVALID_OFFSET (-1) |
| 60 | |
| 61 | typedef enum BBType { |
| 62 | kEntryBlock, |
| 63 | kDalvikByteCode, |
| 64 | kExitBlock, |
| 65 | kExceptionHandling, |
| 66 | kCatchEntry, |
| 67 | } BBType; |
| 68 | |
| 69 | typedef struct LIR { |
| 70 | int offset; // Offset of this instruction |
| 71 | int dalvikOffset; // Offset of Dalvik opcode |
| 72 | struct LIR* next; |
| 73 | struct LIR* prev; |
| 74 | struct LIR* target; |
| 75 | } LIR; |
| 76 | |
| 77 | enum ExtendedMIROpcode { |
| 78 | kMirOpFirst = kNumPackedOpcodes, |
| 79 | kMirOpPhi = kMirOpFirst, |
| 80 | kMirOpNullNRangeUpCheck, |
| 81 | kMirOpNullNRangeDownCheck, |
| 82 | kMirOpLowerBound, |
| 83 | kMirOpPunt, |
| 84 | kMirOpCheckInlinePrediction, // Gen checks for predicted inlining |
| 85 | kMirOpLast, |
| 86 | }; |
| 87 | |
| 88 | struct SSARepresentation; |
| 89 | |
| 90 | typedef enum { |
| 91 | kMIRIgnoreNullCheck = 0, |
| 92 | kMIRNullCheckOnly, |
| 93 | kMIRIgnoreRangeCheck, |
| 94 | kMIRRangeCheckOnly, |
| 95 | kMIRInlined, // Invoke is inlined (ie dead) |
| 96 | kMIRInlinedPred, // Invoke is inlined via prediction |
| 97 | kMIRCallee, // Instruction is inlined from callee |
buzbee | c1f4504 | 2011-09-21 16:03:19 -0700 | [diff] [blame] | 98 | kMIRIgnoreSuspendCheck, |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 99 | } MIROptimizationFlagPositons; |
| 100 | |
| 101 | #define MIR_IGNORE_NULL_CHECK (1 << kMIRIgnoreNullCheck) |
| 102 | #define MIR_NULL_CHECK_ONLY (1 << kMIRNullCheckOnly) |
| 103 | #define MIR_IGNORE_RANGE_CHECK (1 << kMIRIgnoreRangeCheck) |
| 104 | #define MIR_RANGE_CHECK_ONLY (1 << kMIRRangeCheckOnly) |
| 105 | #define MIR_INLINED (1 << kMIRInlined) |
| 106 | #define MIR_INLINED_PRED (1 << kMIRInlinedPred) |
| 107 | #define MIR_CALLEE (1 << kMIRCallee) |
buzbee | c1f4504 | 2011-09-21 16:03:19 -0700 | [diff] [blame] | 108 | #define MIR_IGNORE_SUSPEND_CHECK (1 << kMIRIgnoreSuspendCheck) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 109 | |
| 110 | typedef struct CallsiteInfo { |
| 111 | const char* classDescriptor; |
| 112 | Object* classLoader; |
| 113 | const Method* method; |
| 114 | LIR* misPredBranchOver; |
| 115 | } CallsiteInfo; |
| 116 | |
| 117 | typedef struct MIR { |
| 118 | DecodedInstruction dalvikInsn; |
| 119 | unsigned int width; |
| 120 | unsigned int offset; |
| 121 | struct MIR* prev; |
| 122 | struct MIR* next; |
| 123 | struct SSARepresentation* ssaRep; |
buzbee | 43a3642 | 2011-09-14 14:00:13 -0700 | [diff] [blame] | 124 | int optimizationFlags; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 125 | int seqNum; |
| 126 | union { |
| 127 | // Used by the inlined insn from the callee to find the mother method |
| 128 | const Method* calleeMethod; |
| 129 | // Used by the inlined invoke to find the class and method pointers |
| 130 | CallsiteInfo* callsiteInfo; |
buzbee | c0ecd65 | 2011-09-25 18:11:54 -0700 | [diff] [blame] | 131 | // Used to quickly locate all Phi opcodes |
| 132 | struct MIR* phiNext; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 133 | } meta; |
| 134 | } MIR; |
| 135 | |
| 136 | struct BasicBlockDataFlow; |
| 137 | |
| 138 | /* For successorBlockList */ |
| 139 | typedef enum BlockListType { |
| 140 | kNotUsed = 0, |
| 141 | kCatch, |
| 142 | kPackedSwitch, |
| 143 | kSparseSwitch, |
| 144 | } BlockListType; |
| 145 | |
| 146 | typedef struct BasicBlock { |
| 147 | int id; |
| 148 | bool visited; |
| 149 | bool hidden; |
buzbee | 43a3642 | 2011-09-14 14:00:13 -0700 | [diff] [blame] | 150 | bool catchEntry; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 151 | unsigned int startOffset; |
| 152 | const Method* containingMethod; // For blocks from the callee |
| 153 | BBType blockType; |
| 154 | bool needFallThroughBranch; // For blocks ended due to length limit |
| 155 | bool isFallThroughFromInvoke; // True means the block needs alignment |
| 156 | MIR* firstMIRInsn; |
| 157 | MIR* lastMIRInsn; |
| 158 | struct BasicBlock* fallThrough; |
| 159 | struct BasicBlock* taken; |
| 160 | struct BasicBlock* iDom; // Immediate dominator |
| 161 | struct BasicBlockDataFlow* dataFlowInfo; |
| 162 | ArenaBitVector* predecessors; |
| 163 | ArenaBitVector* dominators; |
| 164 | ArenaBitVector* iDominated; // Set nodes being immediately dominated |
| 165 | ArenaBitVector* domFrontier; // Dominance frontier |
| 166 | struct { // For one-to-many successors like |
| 167 | BlockListType blockListType; // switch and exception handling |
| 168 | GrowableList blocks; |
| 169 | } successorBlockList; |
| 170 | } BasicBlock; |
| 171 | |
| 172 | /* |
| 173 | * The "blocks" field in "successorBlockList" points to an array of |
| 174 | * elements with the type "SuccessorBlockInfo". |
| 175 | * For catch blocks, key is type index for the exception. |
| 176 | * For swtich blocks, key is the case value. |
| 177 | */ |
| 178 | typedef struct SuccessorBlockInfo { |
| 179 | BasicBlock* block; |
| 180 | int key; |
| 181 | } SuccessorBlockInfo; |
| 182 | |
| 183 | struct LoopAnalysis; |
| 184 | struct RegisterPool; |
| 185 | |
| 186 | typedef enum AssemblerStatus { |
| 187 | kSuccess, |
| 188 | kRetryAll, |
| 189 | kRetryHalve |
| 190 | } AssemblerStatus; |
| 191 | |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 192 | typedef struct CompilationUnit { |
| 193 | int numInsts; |
| 194 | int numBlocks; |
| 195 | GrowableList blockList; |
Brian Carlstrom | 928bf02 | 2011-10-11 02:48:14 -0700 | [diff] [blame] | 196 | const Compiler* compiler; |
| 197 | const Method* method; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 198 | LIR* firstLIRInsn; |
| 199 | LIR* lastLIRInsn; |
| 200 | LIR* literalList; // Constants |
| 201 | LIR* classPointerList; // Relocatable |
| 202 | int numClassPointers; |
| 203 | LIR* chainCellOffsetLIR; |
buzbee | ce30293 | 2011-10-04 14:32:18 -0700 | [diff] [blame] | 204 | uint32_t disableOpt; // optControlVector flags |
| 205 | uint32_t enableDebug; // debugControlVector flags |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 206 | int headerSize; // bytes before the first code ptr |
| 207 | int dataOffset; // starting offset of literal pool |
| 208 | int totalSize; // header + code size |
| 209 | AssemblerStatus assemblerStatus; // Success or fix and retry |
| 210 | int assemblerRetries; |
buzbee | 4ef7652 | 2011-09-08 10:00:32 -0700 | [diff] [blame] | 211 | std::vector<short> codeBuffer; |
| 212 | std::vector<uint32_t> mappingTable; |
buzbee | 3ddc0d1 | 2011-10-05 10:36:21 -0700 | [diff] [blame] | 213 | std::vector<uint16_t> coreVmapTable; |
| 214 | std::vector<uint16_t> fpVmapTable; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 215 | bool printMe; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 216 | bool hasClassLiterals; // Contains class ptrs used as literals |
| 217 | bool hasLoop; // Contains a loop |
| 218 | bool hasInvoke; // Contains an invoke instruction |
| 219 | bool heapMemOp; // Mark mem ops for self verification |
| 220 | bool usesLinkRegister; // For self-verification only |
| 221 | bool methodTraceSupport; // For TraceView profiling |
| 222 | struct RegisterPool* regPool; |
| 223 | int optRound; // round number to tell an LIR's age |
| 224 | OatInstructionSetType instructionSet; |
| 225 | /* Number of total regs used in the whole cUnit after SSA transformation */ |
| 226 | int numSSARegs; |
| 227 | /* Map SSA reg i to the Dalvik[15..0]/Sub[31..16] pair. */ |
| 228 | GrowableList* ssaToDalvikMap; |
| 229 | |
| 230 | /* The following are new data structures to support SSA representations */ |
| 231 | /* Map original Dalvik reg i to the SSA[15..0]/Sub[31..16] pair */ |
| 232 | int* dalvikToSSAMap; // length == method->registersSize |
buzbee | f0cde54 | 2011-09-13 14:55:02 -0700 | [diff] [blame] | 233 | int* SSALastDefs; // length == method->registersSize |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 234 | ArenaBitVector* isConstantV; // length == numSSAReg |
| 235 | int* constantValues; // length == numSSAReg |
buzbee | c0ecd65 | 2011-09-25 18:11:54 -0700 | [diff] [blame] | 236 | int* phiAliasMap; // length == numSSAReg |
| 237 | MIR* phiList; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 238 | |
| 239 | /* Map SSA names to location */ |
| 240 | RegLocation* regLocation; |
| 241 | int sequenceNumber; |
| 242 | |
buzbee | 67bc236 | 2011-10-11 18:08:40 -0700 | [diff] [blame^] | 243 | /* Keep track of Dalvik vReg to physical register mappings */ |
| 244 | PromotionMap* promotionMap; |
| 245 | |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 246 | /* |
| 247 | * Set to the Dalvik PC of the switch instruction if it has more than |
| 248 | * MAX_CHAINED_SWITCH_CASES cases. |
| 249 | */ |
| 250 | const u2* switchOverflowPad; |
| 251 | |
| 252 | int numReachableBlocks; |
| 253 | int numDalvikRegisters; // method->registersSize + inlined |
| 254 | BasicBlock* entryBlock; |
| 255 | BasicBlock* exitBlock; |
| 256 | BasicBlock* curBlock; |
| 257 | BasicBlock* nextCodegenBlock; // for extended trace codegen |
| 258 | GrowableList dfsOrder; |
| 259 | GrowableList domPostOrderTraversal; |
buzbee | 5ade1d2 | 2011-09-09 14:44:52 -0700 | [diff] [blame] | 260 | GrowableList throwLaunchpads; |
buzbee | c1f4504 | 2011-09-21 16:03:19 -0700 | [diff] [blame] | 261 | GrowableList suspendLaunchpads; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 262 | ArenaBitVector* tryBlockAddr; |
| 263 | ArenaBitVector** defBlockMatrix; // numDalvikRegister x numBlocks |
| 264 | ArenaBitVector* tempBlockV; |
| 265 | ArenaBitVector* tempDalvikRegisterV; |
| 266 | ArenaBitVector* tempSSARegisterV; // numSSARegs |
| 267 | bool printSSANames; |
| 268 | void* blockLabelList; |
| 269 | bool quitLoopMode; // cold path/complex bytecode |
| 270 | int preservedRegsUsed; // How many callee save regs used |
| 271 | /* |
buzbee | 5ade1d2 | 2011-09-09 14:44:52 -0700 | [diff] [blame] | 272 | * Frame layout details. |
| 273 | * NOTE: for debug support it will be necessary to add a structure |
| 274 | * to map the Dalvik virtual registers to the promoted registers. |
| 275 | * NOTE: "num" fields are in 4-byte words, "Size" and "Offset" in bytes. |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 276 | */ |
| 277 | int numIns; |
| 278 | int numOuts; |
| 279 | int numRegs; // Unlike struct Method, does not include ins |
buzbee | bbaf894 | 2011-10-02 13:08:29 -0700 | [diff] [blame] | 280 | int numCoreSpills; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 281 | int numFPSpills; |
| 282 | int numPadding; // # of 4-byte padding cells |
| 283 | int regsOffset; // sp-relative offset to beginning of Dalvik regs |
| 284 | int insOffset; // sp-relative offset to beginning of Dalvik ins |
| 285 | int frameSize; |
| 286 | unsigned int coreSpillMask; |
| 287 | unsigned int fpSpillMask; |
buzbee | cefd187 | 2011-09-09 09:59:52 -0700 | [diff] [blame] | 288 | unsigned int attrs; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 289 | /* |
| 290 | * CLEANUP/RESTRUCTURE: The code generation utilities don't have a built-in |
buzbee | 03fa263 | 2011-09-20 17:10:57 -0700 | [diff] [blame] | 291 | * mechanism to propagate the original Dalvik opcode address to the |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 292 | * associated generated instructions. For the trace compiler, this wasn't |
| 293 | * necessary because the interpreter handled all throws and debugging |
| 294 | * requests. For now we'll handle this by placing the Dalvik offset |
| 295 | * in the CompilationUnit struct before codegen for each instruction. |
| 296 | * The low-level LIR creation utilites will pull it from here. Should |
| 297 | * be rewritten. |
| 298 | */ |
| 299 | int currentDalvikOffset; |
| 300 | GrowableList switchTables; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 301 | GrowableList fillArrayData; |
| 302 | const u2* insns; |
| 303 | u4 insnsSize; |
| 304 | } CompilationUnit; |
| 305 | |
| 306 | BasicBlock* oatNewBB(BBType blockType, int blockId); |
| 307 | |
| 308 | void oatAppendMIR(BasicBlock* bb, MIR* mir); |
| 309 | |
| 310 | void oatPrependMIR(BasicBlock* bb, MIR* mir); |
| 311 | |
| 312 | void oatInsertMIRAfter(BasicBlock* bb, MIR* currentMIR, MIR* newMIR); |
| 313 | |
| 314 | void oatAppendLIR(CompilationUnit* cUnit, LIR* lir); |
| 315 | |
| 316 | void oatInsertLIRBefore(LIR* currentLIR, LIR* newLIR); |
| 317 | |
| 318 | void oatInsertLIRAfter(LIR* currentLIR, LIR* newLIR); |
| 319 | |
| 320 | /* Debug Utilities */ |
| 321 | void oatDumpCompilationUnit(CompilationUnit* cUnit); |
| 322 | |
| 323 | #endif // ART_SRC_COMPILER_COMPILER_IR_H_ |