blob: 0fc26dea4cf794157a87550c258adb1c3ea98a75 [file] [log] [blame]
buzbee67bf8852011-08-17 17:51:35 -07001/*
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"
Ian Rogers1bddec32012-02-04 12:27:34 -080021#include "CompilerUtility.h"
buzbeec143c552011-08-20 17:38:58 -070022#include <vector>
buzbee31a4a6f2012-02-28 15:36:15 -080023#include "oat_compilation_unit.h"
buzbee67bf8852011-08-17 17:51:35 -070024
Elliott Hughes11d1b0c2012-01-23 16:57:47 -080025namespace art {
26
buzbee31a4a6f2012-02-28 15:36:15 -080027#define SLOW_FIELD_PATH (cUnit->enableDebug & (1 << kDebugSlowFieldPath))
28#define SLOW_INVOKE_PATH (cUnit->enableDebug & (1 << kDebugSlowInvokePath))
29#define SLOW_STRING_PATH (cUnit->enableDebug & (1 << kDebugSlowStringPath))
30#define SLOW_TYPE_PATH (cUnit->enableDebug & (1 << kDebugSlowTypePath))
31#define EXERCISE_SLOWEST_FIELD_PATH (cUnit->enableDebug & \
32 (1 << kDebugSlowestFieldPath))
33#define EXERCISE_SLOWEST_STRING_PATH (cUnit->enableDebug & \
34 (1 << kDebugSlowestStringPath))
35#define EXERCISE_RESOLVE_METHOD (cUnit->enableDebug & \
36 (1 << kDebugExerciseResolveMethod))
37
Elliott Hughes719ace42012-03-09 18:06:03 -080038enum RegisterClass {
buzbee67bf8852011-08-17 17:51:35 -070039 kCoreReg,
40 kFPReg,
41 kAnyReg,
Elliott Hughes719ace42012-03-09 18:06:03 -080042};
buzbee67bf8852011-08-17 17:51:35 -070043
Elliott Hughes719ace42012-03-09 18:06:03 -080044enum RegLocationType {
buzbee67bf8852011-08-17 17:51:35 -070045 kLocDalvikFrame = 0, // Normal Dalvik register
46 kLocPhysReg,
buzbeee1965672012-03-11 18:39:19 -070047 kLocCompilerTemp,
buzbeee62076c2012-03-21 14:26:16 -070048 kLocInvalid
Elliott Hughes719ace42012-03-09 18:06:03 -080049};
buzbee67bf8852011-08-17 17:51:35 -070050
Elliott Hughes719ace42012-03-09 18:06:03 -080051struct PromotionMap {
buzbee67bc2362011-10-11 18:08:40 -070052 RegLocationType coreLocation:3;
53 u1 coreReg;
54 RegLocationType fpLocation:3;
55 u1 fpReg;
56 bool firstInPair;
Elliott Hughes719ace42012-03-09 18:06:03 -080057};
buzbee67bc2362011-10-11 18:08:40 -070058
Elliott Hughes719ace42012-03-09 18:06:03 -080059struct RegLocation {
buzbee67bc2362011-10-11 18:08:40 -070060 RegLocationType location:3;
buzbee67bf8852011-08-17 17:51:35 -070061 unsigned wide:1;
buzbee67bc2362011-10-11 18:08:40 -070062 unsigned defined:1; // Do we know the type?
63 unsigned fp:1; // Floating point?
64 unsigned core:1; // Non-floating point?
65 unsigned highWord:1; // High word of pair?
66 unsigned home:1; // Does this represent the home location?
67 u1 lowReg; // First physical register
68 u1 highReg; // 2nd physical register (if wide)
buzbeee1965672012-03-11 18:39:19 -070069 int32_t sRegLow; // SSA name for low Dalvik word
70};
71
72struct CompilerTemp {
73 int sReg;
74 ArenaBitVector* bv;
Elliott Hughes719ace42012-03-09 18:06:03 -080075};
buzbee67bf8852011-08-17 17:51:35 -070076
buzbeee3acd072012-02-25 17:03:10 -080077 /*
78 * Data structure tracking the mapping between a Dalvik register (pair) and a
79 * native register (pair). The idea is to reuse the previously loaded value
80 * if possible, otherwise to keep the value in a native register as long as
81 * possible.
82 */
Elliott Hughes719ace42012-03-09 18:06:03 -080083struct RegisterInfo {
buzbeee3acd072012-02-25 17:03:10 -080084 int reg; // Reg number
85 bool inUse; // Has it been allocated?
86 bool isTemp; // Can allocate as temp?
87 bool pair; // Part of a register pair?
88 int partner; // If pair, other reg of pair
89 bool live; // Is there an associated SSA name?
90 bool dirty; // If live, is it dirty?
91 int sReg; // Name of live value
92 struct LIR *defStart; // Starting inst in last def sequence
93 struct LIR *defEnd; // Ending inst in last def sequence
Elliott Hughes719ace42012-03-09 18:06:03 -080094};
buzbeee3acd072012-02-25 17:03:10 -080095
Elliott Hughes719ace42012-03-09 18:06:03 -080096struct RegisterPool {
buzbeee3acd072012-02-25 17:03:10 -080097 int numCoreRegs;
98 RegisterInfo *coreRegs;
99 int nextCoreReg;
100 int numFPRegs;
101 RegisterInfo *FPRegs;
102 int nextFPReg;
Elliott Hughes719ace42012-03-09 18:06:03 -0800103};
buzbeee3acd072012-02-25 17:03:10 -0800104
buzbee67bf8852011-08-17 17:51:35 -0700105#define INVALID_SREG (-1)
buzbee3ddc0d12011-10-05 10:36:21 -0700106#define INVALID_VREG (0xFFFFU)
buzbee67bc2362011-10-11 18:08:40 -0700107#define INVALID_REG (0xFF)
buzbee67bf8852011-08-17 17:51:35 -0700108#define INVALID_OFFSET (-1)
109
buzbeee1965672012-03-11 18:39:19 -0700110/* SSA encodings for special registers */
buzbee9c044ce2012-03-18 13:24:07 -0700111#define SSA_METHOD_BASEREG (-2)
buzbeee1965672012-03-11 18:39:19 -0700112/* First compiler temp basereg, grows smaller */
buzbee9c044ce2012-03-18 13:24:07 -0700113#define SSA_CTEMP_BASEREG (SSA_METHOD_BASEREG - 1)
buzbeee1965672012-03-11 18:39:19 -0700114
buzbee99ba9642012-01-25 14:23:14 -0800115/*
116 * Some code patterns cause the generation of excessively large
117 * methods - in particular initialization sequences. There isn't much
118 * benefit in optimizing these methods, and the cost can be very high.
119 * We attempt to identify these cases, and avoid performing most dataflow
120 * analysis. Two thresholds are used - one for known initializers and one
buzbee5abfa3e2012-01-31 17:01:43 -0800121 * for everything else.
buzbee99ba9642012-01-25 14:23:14 -0800122 */
buzbee5abfa3e2012-01-31 17:01:43 -0800123#define MANY_BLOCKS_INITIALIZER 1000 /* Threshold for switching dataflow off */
124#define MANY_BLOCKS 4000 /* Non-initializer threshold */
buzbee99ba9642012-01-25 14:23:14 -0800125
Elliott Hughes719ace42012-03-09 18:06:03 -0800126enum BBType {
buzbee67bf8852011-08-17 17:51:35 -0700127 kEntryBlock,
128 kDalvikByteCode,
129 kExitBlock,
130 kExceptionHandling,
131 kCatchEntry,
Elliott Hughes719ace42012-03-09 18:06:03 -0800132};
buzbee67bf8852011-08-17 17:51:35 -0700133
buzbee31a4a6f2012-02-28 15:36:15 -0800134/* Utility macros to traverse the LIR list */
135#define NEXT_LIR(lir) (lir->next)
136#define PREV_LIR(lir) (lir->prev)
137
138#define NEXT_LIR_LVALUE(lir) (lir)->next
139#define PREV_LIR_LVALUE(lir) (lir)->prev
140
Elliott Hughes719ace42012-03-09 18:06:03 -0800141struct LIR {
buzbee67bf8852011-08-17 17:51:35 -0700142 int offset; // Offset of this instruction
143 int dalvikOffset; // Offset of Dalvik opcode
144 struct LIR* next;
145 struct LIR* prev;
146 struct LIR* target;
buzbee31a4a6f2012-02-28 15:36:15 -0800147 int opcode;
Ian Rogersb5d09b22012-03-06 22:14:17 -0800148 int operands[5]; // [0..4] = [dest, src1, src2, extra, extra2]
buzbee31a4a6f2012-02-28 15:36:15 -0800149 struct {
150 bool isNop:1; // LIR is optimized away
151 bool pcRelFixup:1; // May need pc-relative fixup
152 unsigned int age:4; // default is 0, set lazily by the optimizer
buzbee71ac9942012-03-01 17:23:10 -0800153 unsigned int size:5; // in bytes
154 unsigned int unused:21;
buzbee31a4a6f2012-02-28 15:36:15 -0800155 } flags;
156 int aliasInfo; // For Dalvik register & litpool disambiguation
157 u8 useMask; // Resource mask for use
158 u8 defMask; // Resource mask for def
Elliott Hughes719ace42012-03-09 18:06:03 -0800159};
buzbee67bf8852011-08-17 17:51:35 -0700160
161enum ExtendedMIROpcode {
162 kMirOpFirst = kNumPackedOpcodes,
163 kMirOpPhi = kMirOpFirst,
buzbee84fd6932012-03-29 16:44:16 -0700164 kMirOpCopy,
165 kMirOpFusedCmplFloat,
166 kMirOpFusedCmpgFloat,
167 kMirOpFusedCmplDouble,
168 kMirOpFusedCmpgDouble,
169 kMirOpFusedCmpLong,
170 kMirOpNop,
buzbee67bf8852011-08-17 17:51:35 -0700171 kMirOpNullNRangeUpCheck,
172 kMirOpNullNRangeDownCheck,
173 kMirOpLowerBound,
buzbee67bf8852011-08-17 17:51:35 -0700174 kMirOpLast,
175};
176
177struct SSARepresentation;
178
Elliott Hughes719ace42012-03-09 18:06:03 -0800179enum MIROptimizationFlagPositons {
buzbee67bf8852011-08-17 17:51:35 -0700180 kMIRIgnoreNullCheck = 0,
181 kMIRNullCheckOnly,
182 kMIRIgnoreRangeCheck,
183 kMIRRangeCheckOnly,
184 kMIRInlined, // Invoke is inlined (ie dead)
185 kMIRInlinedPred, // Invoke is inlined via prediction
186 kMIRCallee, // Instruction is inlined from callee
buzbeec1f45042011-09-21 16:03:19 -0700187 kMIRIgnoreSuspendCheck,
buzbeee1965672012-03-11 18:39:19 -0700188 kMIRDup,
buzbee239c4e72012-03-16 08:42:29 -0700189 kMIRMark, // Temporary node mark
Elliott Hughes719ace42012-03-09 18:06:03 -0800190};
buzbee67bf8852011-08-17 17:51:35 -0700191
192#define MIR_IGNORE_NULL_CHECK (1 << kMIRIgnoreNullCheck)
193#define MIR_NULL_CHECK_ONLY (1 << kMIRNullCheckOnly)
194#define MIR_IGNORE_RANGE_CHECK (1 << kMIRIgnoreRangeCheck)
195#define MIR_RANGE_CHECK_ONLY (1 << kMIRRangeCheckOnly)
196#define MIR_INLINED (1 << kMIRInlined)
197#define MIR_INLINED_PRED (1 << kMIRInlinedPred)
198#define MIR_CALLEE (1 << kMIRCallee)
buzbeec1f45042011-09-21 16:03:19 -0700199#define MIR_IGNORE_SUSPEND_CHECK (1 << kMIRIgnoreSuspendCheck)
buzbeee1965672012-03-11 18:39:19 -0700200#define MIR_DUP (1 << kMIRDup)
buzbee239c4e72012-03-16 08:42:29 -0700201#define MIR_MARK (1 << kMIRMark)
buzbee67bf8852011-08-17 17:51:35 -0700202
Elliott Hughes719ace42012-03-09 18:06:03 -0800203struct CallsiteInfo {
buzbee67bf8852011-08-17 17:51:35 -0700204 const char* classDescriptor;
205 Object* classLoader;
206 const Method* method;
207 LIR* misPredBranchOver;
Elliott Hughes719ace42012-03-09 18:06:03 -0800208};
buzbee67bf8852011-08-17 17:51:35 -0700209
Elliott Hughes719ace42012-03-09 18:06:03 -0800210struct MIR {
buzbee67bf8852011-08-17 17:51:35 -0700211 DecodedInstruction dalvikInsn;
212 unsigned int width;
213 unsigned int offset;
214 struct MIR* prev;
215 struct MIR* next;
216 struct SSARepresentation* ssaRep;
buzbee43a36422011-09-14 14:00:13 -0700217 int optimizationFlags;
buzbee67bf8852011-08-17 17:51:35 -0700218 int seqNum;
219 union {
220 // Used by the inlined insn from the callee to find the mother method
221 const Method* calleeMethod;
222 // Used by the inlined invoke to find the class and method pointers
223 CallsiteInfo* callsiteInfo;
buzbeec0ecd652011-09-25 18:11:54 -0700224 // Used to quickly locate all Phi opcodes
225 struct MIR* phiNext;
buzbee67bf8852011-08-17 17:51:35 -0700226 } meta;
Elliott Hughes719ace42012-03-09 18:06:03 -0800227};
buzbee67bf8852011-08-17 17:51:35 -0700228
229struct BasicBlockDataFlow;
230
231/* For successorBlockList */
Elliott Hughes719ace42012-03-09 18:06:03 -0800232enum BlockListType {
buzbee67bf8852011-08-17 17:51:35 -0700233 kNotUsed = 0,
234 kCatch,
235 kPackedSwitch,
236 kSparseSwitch,
Elliott Hughes719ace42012-03-09 18:06:03 -0800237};
buzbee67bf8852011-08-17 17:51:35 -0700238
Elliott Hughes719ace42012-03-09 18:06:03 -0800239struct BasicBlock {
buzbee67bf8852011-08-17 17:51:35 -0700240 int id;
buzbee5b537102012-01-17 17:33:47 -0800241 int dfsId;
buzbee67bf8852011-08-17 17:51:35 -0700242 bool visited;
243 bool hidden;
buzbee43a36422011-09-14 14:00:13 -0700244 bool catchEntry;
buzbeee1965672012-03-11 18:39:19 -0700245 bool fallThroughTarget; // Reached via fallthrough
buzbee239c4e72012-03-16 08:42:29 -0700246 uint16_t startOffset;
247 uint16_t nestingDepth;
buzbee67bf8852011-08-17 17:51:35 -0700248 const Method* containingMethod; // For blocks from the callee
249 BBType blockType;
250 bool needFallThroughBranch; // For blocks ended due to length limit
251 bool isFallThroughFromInvoke; // True means the block needs alignment
252 MIR* firstMIRInsn;
253 MIR* lastMIRInsn;
254 struct BasicBlock* fallThrough;
255 struct BasicBlock* taken;
256 struct BasicBlock* iDom; // Immediate dominator
257 struct BasicBlockDataFlow* dataFlowInfo;
buzbee5abfa3e2012-01-31 17:01:43 -0800258 GrowableList* predecessors;
buzbee67bf8852011-08-17 17:51:35 -0700259 ArenaBitVector* dominators;
260 ArenaBitVector* iDominated; // Set nodes being immediately dominated
261 ArenaBitVector* domFrontier; // Dominance frontier
262 struct { // For one-to-many successors like
263 BlockListType blockListType; // switch and exception handling
264 GrowableList blocks;
265 } successorBlockList;
Elliott Hughes719ace42012-03-09 18:06:03 -0800266};
buzbee67bf8852011-08-17 17:51:35 -0700267
268/*
269 * The "blocks" field in "successorBlockList" points to an array of
270 * elements with the type "SuccessorBlockInfo".
271 * For catch blocks, key is type index for the exception.
272 * For swtich blocks, key is the case value.
273 */
Elliott Hughes719ace42012-03-09 18:06:03 -0800274struct SuccessorBlockInfo {
buzbee67bf8852011-08-17 17:51:35 -0700275 BasicBlock* block;
276 int key;
Elliott Hughes719ace42012-03-09 18:06:03 -0800277};
buzbee67bf8852011-08-17 17:51:35 -0700278
279struct LoopAnalysis;
280struct RegisterPool;
buzbeeba938cb2012-02-03 14:47:55 -0800281struct ArenaMemBlock;
282struct Memstats;
buzbee67bf8852011-08-17 17:51:35 -0700283
Elliott Hughes719ace42012-03-09 18:06:03 -0800284enum AssemblerStatus {
buzbee67bf8852011-08-17 17:51:35 -0700285 kSuccess,
286 kRetryAll,
287 kRetryHalve
Elliott Hughes719ace42012-03-09 18:06:03 -0800288};
buzbee67bf8852011-08-17 17:51:35 -0700289
buzbee5b537102012-01-17 17:33:47 -0800290#define NOTVISITED (-1)
291
Elliott Hughes719ace42012-03-09 18:06:03 -0800292struct CompilationUnit {
Elliott Hughese52e49b2012-04-02 16:05:44 -0700293 CompilationUnit()
294 : numBlocks(0),
295 compiler(NULL),
296 class_linker(NULL),
297 dex_file(NULL),
298 dex_cache(NULL),
299 class_loader(NULL),
300 method_idx(0),
301 code_item(NULL),
302 access_flags(0),
303 shorty(NULL),
304 firstLIRInsn(NULL),
305 lastLIRInsn(NULL),
306 literalList(NULL),
307 methodLiteralList(NULL),
308 codeLiteralList(NULL),
309 classPointerList(NULL),
310 numClassPointers(0),
311 chainCellOffsetLIR(NULL),
312 disableOpt(0),
313 enableDebug(0),
314 headerSize(0),
315 dataOffset(0),
316 totalSize(0),
317 assemblerStatus(kSuccess),
318 assemblerRetries(0),
319 genDebugger(false),
320 printMe(false),
321 hasClassLiterals(false),
322 hasLoop(false),
323 hasInvoke(false),
324 heapMemOp(false),
325 qdMode(false),
326 usesLinkRegister(false),
327 methodTraceSupport(false),
328 regPool(NULL),
329 optRound(0),
330 instructionSet(kNone),
331 numSSARegs(0),
332 ssaBaseVRegs(NULL),
333 ssaSubscripts(NULL),
334 vRegToSSAMap(NULL),
335 SSALastDefs(NULL),
336 isConstantV(NULL),
337 constantValues(NULL),
338 phiAliasMap(NULL),
339 phiList(NULL),
340 regLocation(NULL),
341 sequenceNumber(0),
342 promotionMap(NULL),
343 methodSReg(0),
344 switchOverflowPad(NULL),
345 numReachableBlocks(0),
346 numDalvikRegisters(0),
347 entryBlock(NULL),
348 exitBlock(NULL),
349 curBlock(NULL),
350 nextCodegenBlock(NULL),
351 iDomList(NULL),
352 tryBlockAddr(NULL),
353 defBlockMatrix(NULL),
354 tempBlockV(NULL),
355 tempDalvikRegisterV(NULL),
356 tempSSARegisterV(NULL),
357 printSSANames(false),
358 blockLabelList(NULL),
359 quitLoopMode(false),
360 preservedRegsUsed(0),
361 numIns(0),
362 numOuts(0),
363 numRegs(0),
364 numCoreSpills(0),
365 numFPSpills(0),
366 numCompilerTemps(0),
367 frameSize(0),
368 coreSpillMask(0U),
369 fpSpillMask(0U),
370 attrs(0U),
371 currentDalvikOffset(0),
372 insns(NULL),
373 insnsSize(0U),
374 disableDataflow(false),
375 defCount(0),
376 compilerFlipMatch(false),
377 arenaHead(NULL),
378 currentArena(NULL),
379 numArenaBlocks(0),
380 mstats(NULL),
381 opcodeCount(NULL) {
382#if !defined(NDEBUG)
383 liveSReg = 0;
384#endif
385 }
386
buzbee67bf8852011-08-17 17:51:35 -0700387 int numBlocks;
388 GrowableList blockList;
Ian Rogers996cc582012-02-14 22:23:29 -0800389 Compiler* compiler; // Compiler driving this compiler
Elliott Hughes11d1b0c2012-01-23 16:57:47 -0800390 ClassLinker* class_linker; // Linker to resolve fields and methods
391 const DexFile* dex_file; // DexFile containing the method being compiled
392 DexCache* dex_cache; // DexFile's corresponding cache
393 const ClassLoader* class_loader; // compiling method's class loader
Ian Rogersa3760aa2011-11-14 14:32:37 -0800394 uint32_t method_idx; // compiling method's index into method_ids of DexFile
Elliott Hughes11d1b0c2012-01-23 16:57:47 -0800395 const DexFile::CodeItem* code_item; // compiling method's DexFile code_item
Ian Rogersa3760aa2011-11-14 14:32:37 -0800396 uint32_t access_flags; // compiling method's access flags
397 const char* shorty; // compiling method's shorty
buzbee67bf8852011-08-17 17:51:35 -0700398 LIR* firstLIRInsn;
399 LIR* lastLIRInsn;
400 LIR* literalList; // Constants
Ian Rogers3fa13792012-03-18 15:53:45 -0700401 LIR* methodLiteralList; // Method literals requiring patching
402 LIR* codeLiteralList; // Code literals requiring patching
buzbee67bf8852011-08-17 17:51:35 -0700403 LIR* classPointerList; // Relocatable
404 int numClassPointers;
405 LIR* chainCellOffsetLIR;
buzbeece302932011-10-04 14:32:18 -0700406 uint32_t disableOpt; // optControlVector flags
407 uint32_t enableDebug; // debugControlVector flags
buzbee67bf8852011-08-17 17:51:35 -0700408 int headerSize; // bytes before the first code ptr
409 int dataOffset; // starting offset of literal pool
410 int totalSize; // header + code size
411 AssemblerStatus assemblerStatus; // Success or fix and retry
412 int assemblerRetries;
Ian Rogersab058bb2012-03-11 22:19:38 -0700413 std::vector<uint8_t> codeBuffer;
buzbee4ef76522011-09-08 10:00:32 -0700414 std::vector<uint32_t> mappingTable;
buzbee3ddc0d12011-10-05 10:36:21 -0700415 std::vector<uint16_t> coreVmapTable;
416 std::vector<uint16_t> fpVmapTable;
buzbee44b412b2012-02-04 08:50:53 -0800417 bool genDebugger; // Generate code for debugger
buzbee67bf8852011-08-17 17:51:35 -0700418 bool printMe;
buzbee67bf8852011-08-17 17:51:35 -0700419 bool hasClassLiterals; // Contains class ptrs used as literals
420 bool hasLoop; // Contains a loop
421 bool hasInvoke; // Contains an invoke instruction
422 bool heapMemOp; // Mark mem ops for self verification
buzbeea7c12682012-03-19 13:13:53 -0700423 bool qdMode; // Compile for code size/compile time
buzbee67bf8852011-08-17 17:51:35 -0700424 bool usesLinkRegister; // For self-verification only
425 bool methodTraceSupport; // For TraceView profiling
426 struct RegisterPool* regPool;
427 int optRound; // round number to tell an LIR's age
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800428 InstructionSet instructionSet;
buzbee67bf8852011-08-17 17:51:35 -0700429 /* Number of total regs used in the whole cUnit after SSA transformation */
430 int numSSARegs;
buzbeee1965672012-03-11 18:39:19 -0700431 /* Map SSA reg i to the base virtual register/subscript */
432 GrowableList* ssaBaseVRegs;
433 GrowableList* ssaSubscripts;
buzbee67bf8852011-08-17 17:51:35 -0700434
435 /* The following are new data structures to support SSA representations */
buzbeee1965672012-03-11 18:39:19 -0700436 /* Map original Dalvik virtual reg i to the current SSA name */
437 int* vRegToSSAMap; // length == method->registersSize
buzbeef0cde542011-09-13 14:55:02 -0700438 int* SSALastDefs; // length == method->registersSize
buzbee67bf8852011-08-17 17:51:35 -0700439 ArenaBitVector* isConstantV; // length == numSSAReg
440 int* constantValues; // length == numSSAReg
buzbeec0ecd652011-09-25 18:11:54 -0700441 int* phiAliasMap; // length == numSSAReg
442 MIR* phiList;
buzbee67bf8852011-08-17 17:51:35 -0700443
buzbee239c4e72012-03-16 08:42:29 -0700444 /* Use counts of ssa names */
buzbee84fd6932012-03-29 16:44:16 -0700445 GrowableList useCounts; // Weighted by nesting depth
446 GrowableList rawUseCounts; // Not weighted
buzbee239c4e72012-03-16 08:42:29 -0700447
448 /* Optimization support */
449 GrowableList loopHeaders;
450
buzbee67bf8852011-08-17 17:51:35 -0700451 /* Map SSA names to location */
452 RegLocation* regLocation;
453 int sequenceNumber;
454
buzbee67bc2362011-10-11 18:08:40 -0700455 /* Keep track of Dalvik vReg to physical register mappings */
456 PromotionMap* promotionMap;
457
buzbeee1965672012-03-11 18:39:19 -0700458 /* SSA name for Method* */
459 int methodSReg;
460
buzbee67bf8852011-08-17 17:51:35 -0700461 /*
462 * Set to the Dalvik PC of the switch instruction if it has more than
463 * MAX_CHAINED_SWITCH_CASES cases.
464 */
465 const u2* switchOverflowPad;
466
467 int numReachableBlocks;
buzbeee1965672012-03-11 18:39:19 -0700468 int numDalvikRegisters; // method->registersSize
buzbee67bf8852011-08-17 17:51:35 -0700469 BasicBlock* entryBlock;
470 BasicBlock* exitBlock;
471 BasicBlock* curBlock;
472 BasicBlock* nextCodegenBlock; // for extended trace codegen
473 GrowableList dfsOrder;
buzbee5b537102012-01-17 17:33:47 -0800474 GrowableList dfsPostOrder;
buzbee67bf8852011-08-17 17:51:35 -0700475 GrowableList domPostOrderTraversal;
buzbee5ade1d22011-09-09 14:44:52 -0700476 GrowableList throwLaunchpads;
buzbeec1f45042011-09-21 16:03:19 -0700477 GrowableList suspendLaunchpads;
buzbeefc9e6fa2012-03-23 15:14:29 -0700478 GrowableList intrinsicLaunchpads;
buzbeee1965672012-03-11 18:39:19 -0700479 GrowableList compilerTemps;
buzbee5b537102012-01-17 17:33:47 -0800480 int* iDomList;
buzbee67bf8852011-08-17 17:51:35 -0700481 ArenaBitVector* tryBlockAddr;
482 ArenaBitVector** defBlockMatrix; // numDalvikRegister x numBlocks
483 ArenaBitVector* tempBlockV;
484 ArenaBitVector* tempDalvikRegisterV;
485 ArenaBitVector* tempSSARegisterV; // numSSARegs
486 bool printSSANames;
487 void* blockLabelList;
488 bool quitLoopMode; // cold path/complex bytecode
489 int preservedRegsUsed; // How many callee save regs used
490 /*
buzbee5ade1d22011-09-09 14:44:52 -0700491 * Frame layout details.
492 * NOTE: for debug support it will be necessary to add a structure
493 * to map the Dalvik virtual registers to the promoted registers.
494 * NOTE: "num" fields are in 4-byte words, "Size" and "Offset" in bytes.
buzbee67bf8852011-08-17 17:51:35 -0700495 */
496 int numIns;
497 int numOuts;
Ian Rogersa3760aa2011-11-14 14:32:37 -0800498 int numRegs; // Unlike numDalvikRegisters, does not include ins
buzbeebbaf8942011-10-02 13:08:29 -0700499 int numCoreSpills;
buzbee67bf8852011-08-17 17:51:35 -0700500 int numFPSpills;
buzbeeefccc562012-03-11 11:19:28 -0700501 int numCompilerTemps;
buzbee67bf8852011-08-17 17:51:35 -0700502 int frameSize;
503 unsigned int coreSpillMask;
504 unsigned int fpSpillMask;
buzbeecefd1872011-09-09 09:59:52 -0700505 unsigned int attrs;
buzbee67bf8852011-08-17 17:51:35 -0700506 /*
507 * CLEANUP/RESTRUCTURE: The code generation utilities don't have a built-in
buzbee03fa2632011-09-20 17:10:57 -0700508 * mechanism to propagate the original Dalvik opcode address to the
buzbee67bf8852011-08-17 17:51:35 -0700509 * associated generated instructions. For the trace compiler, this wasn't
510 * necessary because the interpreter handled all throws and debugging
511 * requests. For now we'll handle this by placing the Dalvik offset
512 * in the CompilationUnit struct before codegen for each instruction.
513 * The low-level LIR creation utilites will pull it from here. Should
514 * be rewritten.
515 */
Elliott Hughese52e49b2012-04-02 16:05:44 -0700516 int currentDalvikOffset;
517 GrowableList switchTables;
518 GrowableList fillArrayData;
519 const u2* insns;
520 u4 insnsSize;
521 bool disableDataflow; // Skip dataflow analysis if possible
522 std::map<unsigned int, BasicBlock*> blockMap; // findBlock lookup cache
523 std::map<unsigned int, LIR*> boundaryMap; // boundary lookup cache
524 int defCount; // Used to estimate number of SSA names
525
526 // If non-empty, apply optimizer/debug flags only to matching methods.
527 std::string compilerMethodMatch;
528 // Flips sense of compilerMethodMatch - apply flags if doesn't match.
529 bool compilerFlipMatch;
530 struct ArenaMemBlock* arenaHead;
531 struct ArenaMemBlock* currentArena;
532 int numArenaBlocks;
533 struct Memstats* mstats;
534 int* opcodeCount; // Count Dalvik opcodes for tuning
buzbee3d661942012-03-14 17:37:27 -0700535#ifndef NDEBUG
536 /*
537 * Sanity checking for the register temp tracking. The same ssa
538 * name should never be associated with one temp register per
539 * instruction compilation.
540 */
541 int liveSReg;
542#endif
Elliott Hughes719ace42012-03-09 18:06:03 -0800543};
buzbee67bf8852011-08-17 17:51:35 -0700544
Elliott Hughes719ace42012-03-09 18:06:03 -0800545enum OpSize {
buzbeee3acd072012-02-25 17:03:10 -0800546 kWord,
547 kLong,
548 kSingle,
549 kDouble,
550 kUnsignedHalf,
551 kSignedHalf,
552 kUnsignedByte,
553 kSignedByte,
Elliott Hughes719ace42012-03-09 18:06:03 -0800554};
buzbeee3acd072012-02-25 17:03:10 -0800555
Elliott Hughes719ace42012-03-09 18:06:03 -0800556enum OpKind {
buzbee31a4a6f2012-02-28 15:36:15 -0800557 kOpMov,
558 kOpMvn,
559 kOpCmp,
560 kOpLsl,
561 kOpLsr,
562 kOpAsr,
563 kOpRor,
564 kOpNot,
565 kOpAnd,
566 kOpOr,
567 kOpXor,
568 kOpNeg,
569 kOpAdd,
570 kOpAdc,
571 kOpSub,
572 kOpSbc,
573 kOpRsub,
574 kOpMul,
575 kOpDiv,
576 kOpRem,
577 kOpBic,
578 kOpCmn,
579 kOpTst,
580 kOpBkpt,
581 kOpBlx,
582 kOpPush,
583 kOpPop,
584 kOp2Char,
585 kOp2Short,
586 kOp2Byte,
587 kOpCondBr,
588 kOpUncondBr,
buzbee5de34942012-03-01 14:51:57 -0800589 kOpBx,
buzbee31a4a6f2012-02-28 15:36:15 -0800590 kOpInvalid,
Elliott Hughes719ace42012-03-09 18:06:03 -0800591};
buzbee31a4a6f2012-02-28 15:36:15 -0800592
Ian Rogers680b1bd2012-03-07 20:18:49 -0800593std::ostream& operator<<(std::ostream& os, const OpKind& kind);
594
Elliott Hughes719ace42012-03-09 18:06:03 -0800595enum ConditionCode {
Ian Rogersb5d09b22012-03-06 22:14:17 -0800596 kCondEq, // equal
597 kCondNe, // not equal
598 kCondCs, // carry set (unsigned less than)
599 kCondUlt = kCondCs,
600 kCondCc, // carry clear (unsigned greater than or same)
601 kCondUge = kCondCc,
602 kCondMi, // minus
603 kCondPl, // plus, positive or zero
604 kCondVs, // overflow
605 kCondVc, // no overflow
606 kCondHi, // unsigned greater than
607 kCondLs, // unsigned lower or same
608 kCondGe, // signed greater than or equal
609 kCondLt, // signed less than
610 kCondGt, // signed greater than
611 kCondLe, // signed less than or equal
612 kCondAl, // always
613 kCondNv, // never
Elliott Hughes719ace42012-03-09 18:06:03 -0800614};
buzbee31a4a6f2012-02-28 15:36:15 -0800615
Elliott Hughes719ace42012-03-09 18:06:03 -0800616enum ThrowKind {
buzbee31a4a6f2012-02-28 15:36:15 -0800617 kThrowNullPointer,
618 kThrowDivZero,
619 kThrowArrayBounds,
620 kThrowVerificationError,
buzbee31a4a6f2012-02-28 15:36:15 -0800621 kThrowNoSuchMethod,
622 kThrowStackOverflow,
Elliott Hughes719ace42012-03-09 18:06:03 -0800623};
buzbee31a4a6f2012-02-28 15:36:15 -0800624
Elliott Hughes719ace42012-03-09 18:06:03 -0800625struct SwitchTable {
buzbee5de34942012-03-01 14:51:57 -0800626 int offset;
627 const u2* table; // Original dex table
628 int vaddr; // Dalvik offset of switch opcode
buzbeec5159d52012-03-03 11:48:39 -0800629 LIR* anchor; // Reference instruction for relative offsets
buzbee5de34942012-03-01 14:51:57 -0800630 LIR** targets; // Array of case targets
Elliott Hughes719ace42012-03-09 18:06:03 -0800631};
buzbee5de34942012-03-01 14:51:57 -0800632
Elliott Hughes719ace42012-03-09 18:06:03 -0800633struct FillArrayData {
buzbee5de34942012-03-01 14:51:57 -0800634 int offset;
635 const u2* table; // Original dex table
636 int size;
Elliott Hughesadb8c672012-03-06 16:49:32 -0800637 int vaddr; // Dalvik offset of FILL_ARRAY_DATA opcode
Elliott Hughes719ace42012-03-09 18:06:03 -0800638};
buzbee5de34942012-03-01 14:51:57 -0800639
buzbee16da88c2012-03-20 10:38:17 -0700640#define MAX_PATTERN_LEN 5
641
642enum SpecialCaseHandler {
643 kNoHandler,
644 kNullMethod,
645 kConstFunction,
646 kIGet,
647 kIGetBoolean,
648 kIGetObject,
649 kIGetByte,
650 kIGetChar,
651 kIGetShort,
652 kIGetWide,
653 kIPut,
654 kIPutBoolean,
655 kIPutObject,
656 kIPutByte,
657 kIPutChar,
658 kIPutShort,
659 kIPutWide,
buzbeee62076c2012-03-21 14:26:16 -0700660 kIdentity,
buzbee16da88c2012-03-20 10:38:17 -0700661};
662
663struct CodePattern {
664 const Instruction::Code opcodes[MAX_PATTERN_LEN];
665 const SpecialCaseHandler handlerCode;
666};
667
668static const CodePattern specialPatterns[] = {
669 {{Instruction::RETURN_VOID}, kNullMethod},
670 {{Instruction::CONST, Instruction::RETURN}, kConstFunction},
671 {{Instruction::CONST_4, Instruction::RETURN}, kConstFunction},
Ian Rogersf24132c2012-03-21 01:34:31 -0700672 {{Instruction::CONST_4, Instruction::RETURN_OBJECT}, kConstFunction},
buzbee16da88c2012-03-20 10:38:17 -0700673 {{Instruction::CONST_16, Instruction::RETURN}, kConstFunction},
674 {{Instruction::IGET, Instruction:: RETURN}, kIGet},
Ian Rogersf24132c2012-03-21 01:34:31 -0700675 {{Instruction::IGET_BOOLEAN, Instruction::RETURN}, kIGetBoolean},
676 {{Instruction::IGET_OBJECT, Instruction::RETURN_OBJECT}, kIGetObject},
677 {{Instruction::IGET_BYTE, Instruction::RETURN}, kIGetByte},
678 {{Instruction::IGET_CHAR, Instruction::RETURN}, kIGetChar},
679 {{Instruction::IGET_SHORT, Instruction::RETURN}, kIGetShort},
680 {{Instruction::IGET_WIDE, Instruction::RETURN_WIDE}, kIGetWide},
681 {{Instruction::IPUT, Instruction::RETURN_VOID}, kIPut},
682 {{Instruction::IPUT_BOOLEAN, Instruction::RETURN_VOID}, kIPutBoolean},
683 {{Instruction::IPUT_OBJECT, Instruction::RETURN_VOID}, kIPutObject},
684 {{Instruction::IPUT_BYTE, Instruction::RETURN_VOID}, kIPutByte},
685 {{Instruction::IPUT_CHAR, Instruction::RETURN_VOID}, kIPutChar},
686 {{Instruction::IPUT_SHORT, Instruction::RETURN_VOID}, kIPutShort},
687 {{Instruction::IPUT_WIDE, Instruction::RETURN_VOID}, kIPutWide},
buzbeee62076c2012-03-21 14:26:16 -0700688 {{Instruction::RETURN}, kIdentity},
689 {{Instruction::RETURN_OBJECT}, kIdentity},
690 {{Instruction::RETURN_WIDE}, kIdentity},
buzbee16da88c2012-03-20 10:38:17 -0700691};
buzbee5de34942012-03-01 14:51:57 -0800692
buzbee5abfa3e2012-01-31 17:01:43 -0800693BasicBlock* oatNewBB(CompilationUnit* cUnit, BBType blockType, int blockId);
buzbee67bf8852011-08-17 17:51:35 -0700694
695void oatAppendMIR(BasicBlock* bb, MIR* mir);
696
697void oatPrependMIR(BasicBlock* bb, MIR* mir);
698
699void oatInsertMIRAfter(BasicBlock* bb, MIR* currentMIR, MIR* newMIR);
700
701void oatAppendLIR(CompilationUnit* cUnit, LIR* lir);
702
703void oatInsertLIRBefore(LIR* currentLIR, LIR* newLIR);
704
705void oatInsertLIRAfter(LIR* currentLIR, LIR* newLIR);
706
buzbeefc9e6fa2012-03-23 15:14:29 -0700707MIR* oatFindMoveResult(CompilationUnit* cUnit, BasicBlock* bb, MIR* mir,
708 bool wide);
buzbee67bf8852011-08-17 17:51:35 -0700709/* Debug Utilities */
710void oatDumpCompilationUnit(CompilationUnit* cUnit);
711
Elliott Hughes11d1b0c2012-01-23 16:57:47 -0800712} // namespace art
713
buzbee67bf8852011-08-17 17:51:35 -0700714#endif // ART_SRC_COMPILER_COMPILER_IR_H_