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