blob: 67d741a095e0d5bfaaad1706a4752da46bc4a2cb [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
Elliott Hughesa0e18062012-04-13 15:59:59 -070020#include <vector>
21
buzbee67bf8852011-08-17 17:51:35 -070022#include "codegen/Optimizer.h"
Ian Rogers1bddec32012-02-04 12:27:34 -080023#include "CompilerUtility.h"
buzbee31a4a6f2012-02-28 15:36:15 -080024#include "oat_compilation_unit.h"
Elliott Hughesa0e18062012-04-13 15:59:59 -070025#include "safe_map.h"
buzbee67bf8852011-08-17 17:51:35 -070026
Elliott Hughes11d1b0c2012-01-23 16:57:47 -080027namespace art {
28
buzbee31a4a6f2012-02-28 15:36:15 -080029#define SLOW_FIELD_PATH (cUnit->enableDebug & (1 << kDebugSlowFieldPath))
30#define SLOW_INVOKE_PATH (cUnit->enableDebug & (1 << kDebugSlowInvokePath))
31#define SLOW_STRING_PATH (cUnit->enableDebug & (1 << kDebugSlowStringPath))
32#define SLOW_TYPE_PATH (cUnit->enableDebug & (1 << kDebugSlowTypePath))
33#define EXERCISE_SLOWEST_FIELD_PATH (cUnit->enableDebug & \
34 (1 << kDebugSlowestFieldPath))
35#define EXERCISE_SLOWEST_STRING_PATH (cUnit->enableDebug & \
36 (1 << kDebugSlowestStringPath))
37#define EXERCISE_RESOLVE_METHOD (cUnit->enableDebug & \
38 (1 << kDebugExerciseResolveMethod))
39
Elliott Hughes719ace42012-03-09 18:06:03 -080040enum RegisterClass {
buzbee67bf8852011-08-17 17:51:35 -070041 kCoreReg,
42 kFPReg,
43 kAnyReg,
Elliott Hughes719ace42012-03-09 18:06:03 -080044};
buzbee67bf8852011-08-17 17:51:35 -070045
Elliott Hughes719ace42012-03-09 18:06:03 -080046enum RegLocationType {
buzbee67bf8852011-08-17 17:51:35 -070047 kLocDalvikFrame = 0, // Normal Dalvik register
48 kLocPhysReg,
buzbeee1965672012-03-11 18:39:19 -070049 kLocCompilerTemp,
buzbeee62076c2012-03-21 14:26:16 -070050 kLocInvalid
Elliott Hughes719ace42012-03-09 18:06:03 -080051};
buzbee67bf8852011-08-17 17:51:35 -070052
Elliott Hughes719ace42012-03-09 18:06:03 -080053struct PromotionMap {
buzbee67bc2362011-10-11 18:08:40 -070054 RegLocationType coreLocation:3;
55 u1 coreReg;
56 RegLocationType fpLocation:3;
57 u1 fpReg;
58 bool firstInPair;
Elliott Hughes719ace42012-03-09 18:06:03 -080059};
buzbee67bc2362011-10-11 18:08:40 -070060
Elliott Hughes719ace42012-03-09 18:06:03 -080061struct RegLocation {
buzbee67bc2362011-10-11 18:08:40 -070062 RegLocationType location:3;
buzbee67bf8852011-08-17 17:51:35 -070063 unsigned wide:1;
buzbee67bc2362011-10-11 18:08:40 -070064 unsigned defined:1; // Do we know the type?
65 unsigned fp:1; // Floating point?
66 unsigned core:1; // Non-floating point?
67 unsigned highWord:1; // High word of pair?
68 unsigned home:1; // Does this represent the home location?
69 u1 lowReg; // First physical register
70 u1 highReg; // 2nd physical register (if wide)
buzbeee1965672012-03-11 18:39:19 -070071 int32_t sRegLow; // SSA name for low Dalvik word
72};
73
74struct CompilerTemp {
75 int sReg;
76 ArenaBitVector* bv;
Elliott Hughes719ace42012-03-09 18:06:03 -080077};
buzbee67bf8852011-08-17 17:51:35 -070078
buzbeee3acd072012-02-25 17:03:10 -080079 /*
80 * Data structure tracking the mapping between a Dalvik register (pair) and a
81 * native register (pair). The idea is to reuse the previously loaded value
82 * if possible, otherwise to keep the value in a native register as long as
83 * possible.
84 */
Elliott Hughes719ace42012-03-09 18:06:03 -080085struct RegisterInfo {
buzbeee3acd072012-02-25 17:03:10 -080086 int reg; // Reg number
87 bool inUse; // Has it been allocated?
88 bool isTemp; // Can allocate as temp?
89 bool pair; // Part of a register pair?
90 int partner; // If pair, other reg of pair
91 bool live; // Is there an associated SSA name?
92 bool dirty; // If live, is it dirty?
93 int sReg; // Name of live value
Elliott Hughes7b9d9962012-04-20 18:48:18 -070094 LIR *defStart; // Starting inst in last def sequence
95 LIR *defEnd; // Ending inst in last def sequence
Elliott Hughes719ace42012-03-09 18:06:03 -080096};
buzbeee3acd072012-02-25 17:03:10 -080097
Elliott Hughes719ace42012-03-09 18:06:03 -080098struct RegisterPool {
buzbeee3acd072012-02-25 17:03:10 -080099 int numCoreRegs;
100 RegisterInfo *coreRegs;
101 int nextCoreReg;
102 int numFPRegs;
103 RegisterInfo *FPRegs;
104 int nextFPReg;
Elliott Hughes719ace42012-03-09 18:06:03 -0800105};
buzbeee3acd072012-02-25 17:03:10 -0800106
buzbee67bf8852011-08-17 17:51:35 -0700107#define INVALID_SREG (-1)
buzbee3ddc0d12011-10-05 10:36:21 -0700108#define INVALID_VREG (0xFFFFU)
buzbee67bc2362011-10-11 18:08:40 -0700109#define INVALID_REG (0xFF)
buzbee67bf8852011-08-17 17:51:35 -0700110#define INVALID_OFFSET (-1)
111
buzbeee1965672012-03-11 18:39:19 -0700112/* SSA encodings for special registers */
buzbee9c044ce2012-03-18 13:24:07 -0700113#define SSA_METHOD_BASEREG (-2)
buzbeee1965672012-03-11 18:39:19 -0700114/* First compiler temp basereg, grows smaller */
buzbee9c044ce2012-03-18 13:24:07 -0700115#define SSA_CTEMP_BASEREG (SSA_METHOD_BASEREG - 1)
buzbeee1965672012-03-11 18:39:19 -0700116
buzbee99ba9642012-01-25 14:23:14 -0800117/*
118 * Some code patterns cause the generation of excessively large
119 * methods - in particular initialization sequences. There isn't much
120 * benefit in optimizing these methods, and the cost can be very high.
121 * We attempt to identify these cases, and avoid performing most dataflow
122 * analysis. Two thresholds are used - one for known initializers and one
buzbee5abfa3e2012-01-31 17:01:43 -0800123 * for everything else.
buzbee99ba9642012-01-25 14:23:14 -0800124 */
buzbee5abfa3e2012-01-31 17:01:43 -0800125#define MANY_BLOCKS_INITIALIZER 1000 /* Threshold for switching dataflow off */
126#define MANY_BLOCKS 4000 /* Non-initializer threshold */
buzbee99ba9642012-01-25 14:23:14 -0800127
Elliott Hughes719ace42012-03-09 18:06:03 -0800128enum BBType {
buzbee67bf8852011-08-17 17:51:35 -0700129 kEntryBlock,
130 kDalvikByteCode,
131 kExitBlock,
132 kExceptionHandling,
133 kCatchEntry,
Elliott Hughes719ace42012-03-09 18:06:03 -0800134};
buzbee67bf8852011-08-17 17:51:35 -0700135
buzbee31a4a6f2012-02-28 15:36:15 -0800136/* Utility macros to traverse the LIR list */
137#define NEXT_LIR(lir) (lir->next)
138#define PREV_LIR(lir) (lir->prev)
139
140#define NEXT_LIR_LVALUE(lir) (lir)->next
141#define PREV_LIR_LVALUE(lir) (lir)->prev
142
Elliott Hughes719ace42012-03-09 18:06:03 -0800143struct LIR {
buzbee67bf8852011-08-17 17:51:35 -0700144 int offset; // Offset of this instruction
145 int dalvikOffset; // Offset of Dalvik opcode
Elliott Hughes7b9d9962012-04-20 18:48:18 -0700146 LIR* next;
147 LIR* prev;
148 LIR* target;
buzbee31a4a6f2012-02-28 15:36:15 -0800149 int opcode;
Ian Rogersb5d09b22012-03-06 22:14:17 -0800150 int operands[5]; // [0..4] = [dest, src1, src2, extra, extra2]
buzbee31a4a6f2012-02-28 15:36:15 -0800151 struct {
152 bool isNop:1; // LIR is optimized away
153 bool pcRelFixup:1; // May need pc-relative fixup
154 unsigned int age:4; // default is 0, set lazily by the optimizer
buzbee71ac9942012-03-01 17:23:10 -0800155 unsigned int size:5; // in bytes
156 unsigned int unused:21;
buzbee31a4a6f2012-02-28 15:36:15 -0800157 } flags;
158 int aliasInfo; // For Dalvik register & litpool disambiguation
159 u8 useMask; // Resource mask for use
160 u8 defMask; // Resource mask for def
Elliott Hughes719ace42012-03-09 18:06:03 -0800161};
buzbee67bf8852011-08-17 17:51:35 -0700162
163enum ExtendedMIROpcode {
164 kMirOpFirst = kNumPackedOpcodes,
165 kMirOpPhi = kMirOpFirst,
buzbee84fd6932012-03-29 16:44:16 -0700166 kMirOpCopy,
167 kMirOpFusedCmplFloat,
168 kMirOpFusedCmpgFloat,
169 kMirOpFusedCmplDouble,
170 kMirOpFusedCmpgDouble,
171 kMirOpFusedCmpLong,
172 kMirOpNop,
buzbee67bf8852011-08-17 17:51:35 -0700173 kMirOpNullNRangeUpCheck,
174 kMirOpNullNRangeDownCheck,
175 kMirOpLowerBound,
buzbee67bf8852011-08-17 17:51:35 -0700176 kMirOpLast,
177};
178
179struct SSARepresentation;
180
Elliott Hughes719ace42012-03-09 18:06:03 -0800181enum MIROptimizationFlagPositons {
buzbee67bf8852011-08-17 17:51:35 -0700182 kMIRIgnoreNullCheck = 0,
183 kMIRNullCheckOnly,
184 kMIRIgnoreRangeCheck,
185 kMIRRangeCheckOnly,
186 kMIRInlined, // Invoke is inlined (ie dead)
187 kMIRInlinedPred, // Invoke is inlined via prediction
188 kMIRCallee, // Instruction is inlined from callee
buzbeec1f45042011-09-21 16:03:19 -0700189 kMIRIgnoreSuspendCheck,
buzbeee1965672012-03-11 18:39:19 -0700190 kMIRDup,
buzbee239c4e72012-03-16 08:42:29 -0700191 kMIRMark, // Temporary node mark
Elliott Hughes719ace42012-03-09 18:06:03 -0800192};
buzbee67bf8852011-08-17 17:51:35 -0700193
194#define MIR_IGNORE_NULL_CHECK (1 << kMIRIgnoreNullCheck)
195#define MIR_NULL_CHECK_ONLY (1 << kMIRNullCheckOnly)
196#define MIR_IGNORE_RANGE_CHECK (1 << kMIRIgnoreRangeCheck)
197#define MIR_RANGE_CHECK_ONLY (1 << kMIRRangeCheckOnly)
198#define MIR_INLINED (1 << kMIRInlined)
199#define MIR_INLINED_PRED (1 << kMIRInlinedPred)
200#define MIR_CALLEE (1 << kMIRCallee)
buzbeec1f45042011-09-21 16:03:19 -0700201#define MIR_IGNORE_SUSPEND_CHECK (1 << kMIRIgnoreSuspendCheck)
buzbeee1965672012-03-11 18:39:19 -0700202#define MIR_DUP (1 << kMIRDup)
buzbee239c4e72012-03-16 08:42:29 -0700203#define MIR_MARK (1 << kMIRMark)
buzbee67bf8852011-08-17 17:51:35 -0700204
Elliott Hughes719ace42012-03-09 18:06:03 -0800205struct CallsiteInfo {
buzbee67bf8852011-08-17 17:51:35 -0700206 const char* classDescriptor;
207 Object* classLoader;
208 const Method* method;
209 LIR* misPredBranchOver;
Elliott Hughes719ace42012-03-09 18:06:03 -0800210};
buzbee67bf8852011-08-17 17:51:35 -0700211
Elliott Hughes719ace42012-03-09 18:06:03 -0800212struct MIR {
buzbee67bf8852011-08-17 17:51:35 -0700213 DecodedInstruction dalvikInsn;
214 unsigned int width;
215 unsigned int offset;
Elliott Hughes7b9d9962012-04-20 18:48:18 -0700216 MIR* prev;
217 MIR* next;
218 SSARepresentation* ssaRep;
buzbee43a36422011-09-14 14:00:13 -0700219 int optimizationFlags;
buzbee67bf8852011-08-17 17:51:35 -0700220 int seqNum;
221 union {
222 // Used by the inlined insn from the callee to find the mother method
223 const Method* calleeMethod;
224 // Used by the inlined invoke to find the class and method pointers
225 CallsiteInfo* callsiteInfo;
buzbeec0ecd652011-09-25 18:11:54 -0700226 // Used to quickly locate all Phi opcodes
Elliott Hughes7b9d9962012-04-20 18:48:18 -0700227 MIR* phiNext;
buzbee67bf8852011-08-17 17:51:35 -0700228 } meta;
Elliott Hughes719ace42012-03-09 18:06:03 -0800229};
buzbee67bf8852011-08-17 17:51:35 -0700230
231struct BasicBlockDataFlow;
232
233/* For successorBlockList */
Elliott Hughes719ace42012-03-09 18:06:03 -0800234enum BlockListType {
buzbee67bf8852011-08-17 17:51:35 -0700235 kNotUsed = 0,
236 kCatch,
237 kPackedSwitch,
238 kSparseSwitch,
Elliott Hughes719ace42012-03-09 18:06:03 -0800239};
buzbee67bf8852011-08-17 17:51:35 -0700240
Elliott Hughes719ace42012-03-09 18:06:03 -0800241struct BasicBlock {
buzbee67bf8852011-08-17 17:51:35 -0700242 int id;
buzbee5b537102012-01-17 17:33:47 -0800243 int dfsId;
buzbee67bf8852011-08-17 17:51:35 -0700244 bool visited;
245 bool hidden;
buzbee43a36422011-09-14 14:00:13 -0700246 bool catchEntry;
buzbeee1965672012-03-11 18:39:19 -0700247 bool fallThroughTarget; // Reached via fallthrough
buzbee239c4e72012-03-16 08:42:29 -0700248 uint16_t startOffset;
249 uint16_t nestingDepth;
buzbee67bf8852011-08-17 17:51:35 -0700250 const Method* containingMethod; // For blocks from the callee
251 BBType blockType;
252 bool needFallThroughBranch; // For blocks ended due to length limit
253 bool isFallThroughFromInvoke; // True means the block needs alignment
254 MIR* firstMIRInsn;
255 MIR* lastMIRInsn;
Elliott Hughes7b9d9962012-04-20 18:48:18 -0700256 BasicBlock* fallThrough;
257 BasicBlock* taken;
258 BasicBlock* iDom; // Immediate dominator
259 BasicBlockDataFlow* dataFlowInfo;
buzbee5abfa3e2012-01-31 17:01:43 -0800260 GrowableList* predecessors;
buzbee67bf8852011-08-17 17:51:35 -0700261 ArenaBitVector* dominators;
262 ArenaBitVector* iDominated; // Set nodes being immediately dominated
263 ArenaBitVector* domFrontier; // Dominance frontier
264 struct { // For one-to-many successors like
265 BlockListType blockListType; // switch and exception handling
266 GrowableList blocks;
267 } successorBlockList;
Elliott Hughes719ace42012-03-09 18:06:03 -0800268};
buzbee67bf8852011-08-17 17:51:35 -0700269
270/*
271 * The "blocks" field in "successorBlockList" points to an array of
272 * elements with the type "SuccessorBlockInfo".
273 * For catch blocks, key is type index for the exception.
274 * For swtich blocks, key is the case value.
275 */
Elliott Hughes719ace42012-03-09 18:06:03 -0800276struct SuccessorBlockInfo {
buzbee67bf8852011-08-17 17:51:35 -0700277 BasicBlock* block;
278 int key;
Elliott Hughes719ace42012-03-09 18:06:03 -0800279};
buzbee67bf8852011-08-17 17:51:35 -0700280
281struct LoopAnalysis;
282struct RegisterPool;
buzbeeba938cb2012-02-03 14:47:55 -0800283struct ArenaMemBlock;
284struct Memstats;
buzbee67bf8852011-08-17 17:51:35 -0700285
Elliott Hughes719ace42012-03-09 18:06:03 -0800286enum AssemblerStatus {
buzbee67bf8852011-08-17 17:51:35 -0700287 kSuccess,
288 kRetryAll,
289 kRetryHalve
Elliott Hughes719ace42012-03-09 18:06:03 -0800290};
buzbee67bf8852011-08-17 17:51:35 -0700291
buzbee5b537102012-01-17 17:33:47 -0800292#define NOTVISITED (-1)
293
Elliott Hughes719ace42012-03-09 18:06:03 -0800294struct CompilationUnit {
Elliott Hughese52e49b2012-04-02 16:05:44 -0700295 CompilationUnit()
296 : numBlocks(0),
297 compiler(NULL),
298 class_linker(NULL),
299 dex_file(NULL),
300 dex_cache(NULL),
301 class_loader(NULL),
302 method_idx(0),
303 code_item(NULL),
304 access_flags(0),
305 shorty(NULL),
306 firstLIRInsn(NULL),
307 lastLIRInsn(NULL),
308 literalList(NULL),
309 methodLiteralList(NULL),
310 codeLiteralList(NULL),
311 classPointerList(NULL),
312 numClassPointers(0),
313 chainCellOffsetLIR(NULL),
314 disableOpt(0),
315 enableDebug(0),
316 headerSize(0),
317 dataOffset(0),
318 totalSize(0),
319 assemblerStatus(kSuccess),
320 assemblerRetries(0),
321 genDebugger(false),
322 printMe(false),
323 hasClassLiterals(false),
324 hasLoop(false),
325 hasInvoke(false),
326 heapMemOp(false),
327 qdMode(false),
328 usesLinkRegister(false),
329 methodTraceSupport(false),
330 regPool(NULL),
331 optRound(0),
332 instructionSet(kNone),
333 numSSARegs(0),
334 ssaBaseVRegs(NULL),
335 ssaSubscripts(NULL),
336 vRegToSSAMap(NULL),
337 SSALastDefs(NULL),
338 isConstantV(NULL),
339 constantValues(NULL),
340 phiAliasMap(NULL),
341 phiList(NULL),
342 regLocation(NULL),
343 sequenceNumber(0),
344 promotionMap(NULL),
345 methodSReg(0),
346 switchOverflowPad(NULL),
347 numReachableBlocks(0),
348 numDalvikRegisters(0),
349 entryBlock(NULL),
350 exitBlock(NULL),
351 curBlock(NULL),
352 nextCodegenBlock(NULL),
353 iDomList(NULL),
354 tryBlockAddr(NULL),
355 defBlockMatrix(NULL),
356 tempBlockV(NULL),
357 tempDalvikRegisterV(NULL),
358 tempSSARegisterV(NULL),
359 printSSANames(false),
360 blockLabelList(NULL),
361 quitLoopMode(false),
362 preservedRegsUsed(0),
363 numIns(0),
364 numOuts(0),
365 numRegs(0),
366 numCoreSpills(0),
367 numFPSpills(0),
368 numCompilerTemps(0),
369 frameSize(0),
370 coreSpillMask(0U),
371 fpSpillMask(0U),
372 attrs(0U),
373 currentDalvikOffset(0),
374 insns(NULL),
375 insnsSize(0U),
376 disableDataflow(false),
377 defCount(0),
378 compilerFlipMatch(false),
379 arenaHead(NULL),
380 currentArena(NULL),
381 numArenaBlocks(0),
382 mstats(NULL),
383 opcodeCount(NULL) {
384#if !defined(NDEBUG)
385 liveSReg = 0;
386#endif
387 }
388
buzbee67bf8852011-08-17 17:51:35 -0700389 int numBlocks;
390 GrowableList blockList;
Ian Rogers996cc582012-02-14 22:23:29 -0800391 Compiler* compiler; // Compiler driving this compiler
Elliott Hughes11d1b0c2012-01-23 16:57:47 -0800392 ClassLinker* class_linker; // Linker to resolve fields and methods
393 const DexFile* dex_file; // DexFile containing the method being compiled
394 DexCache* dex_cache; // DexFile's corresponding cache
395 const ClassLoader* class_loader; // compiling method's class loader
Ian Rogersa3760aa2011-11-14 14:32:37 -0800396 uint32_t method_idx; // compiling method's index into method_ids of DexFile
Elliott Hughes11d1b0c2012-01-23 16:57:47 -0800397 const DexFile::CodeItem* code_item; // compiling method's DexFile code_item
Ian Rogersa3760aa2011-11-14 14:32:37 -0800398 uint32_t access_flags; // compiling method's access flags
399 const char* shorty; // compiling method's shorty
buzbee67bf8852011-08-17 17:51:35 -0700400 LIR* firstLIRInsn;
401 LIR* lastLIRInsn;
402 LIR* literalList; // Constants
Ian Rogers3fa13792012-03-18 15:53:45 -0700403 LIR* methodLiteralList; // Method literals requiring patching
404 LIR* codeLiteralList; // Code literals requiring patching
buzbee67bf8852011-08-17 17:51:35 -0700405 LIR* classPointerList; // Relocatable
406 int numClassPointers;
407 LIR* chainCellOffsetLIR;
buzbeece302932011-10-04 14:32:18 -0700408 uint32_t disableOpt; // optControlVector flags
409 uint32_t enableDebug; // debugControlVector flags
buzbee67bf8852011-08-17 17:51:35 -0700410 int headerSize; // bytes before the first code ptr
411 int dataOffset; // starting offset of literal pool
412 int totalSize; // header + code size
413 AssemblerStatus assemblerStatus; // Success or fix and retry
414 int assemblerRetries;
Ian Rogersab058bb2012-03-11 22:19:38 -0700415 std::vector<uint8_t> codeBuffer;
buzbee4ef76522011-09-08 10:00:32 -0700416 std::vector<uint32_t> mappingTable;
buzbee3ddc0d12011-10-05 10:36:21 -0700417 std::vector<uint16_t> coreVmapTable;
418 std::vector<uint16_t> fpVmapTable;
buzbee44b412b2012-02-04 08:50:53 -0800419 bool genDebugger; // Generate code for debugger
buzbee67bf8852011-08-17 17:51:35 -0700420 bool printMe;
buzbee67bf8852011-08-17 17:51:35 -0700421 bool hasClassLiterals; // Contains class ptrs used as literals
422 bool hasLoop; // Contains a loop
423 bool hasInvoke; // Contains an invoke instruction
424 bool heapMemOp; // Mark mem ops for self verification
buzbeea7c12682012-03-19 13:13:53 -0700425 bool qdMode; // Compile for code size/compile time
buzbee67bf8852011-08-17 17:51:35 -0700426 bool usesLinkRegister; // For self-verification only
427 bool methodTraceSupport; // For TraceView profiling
Elliott Hughes7b9d9962012-04-20 18:48:18 -0700428 RegisterPool* regPool;
buzbee67bf8852011-08-17 17:51:35 -0700429 int optRound; // round number to tell an LIR's age
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800430 InstructionSet instructionSet;
buzbee67bf8852011-08-17 17:51:35 -0700431 /* Number of total regs used in the whole cUnit after SSA transformation */
432 int numSSARegs;
buzbeee1965672012-03-11 18:39:19 -0700433 /* Map SSA reg i to the base virtual register/subscript */
434 GrowableList* ssaBaseVRegs;
435 GrowableList* ssaSubscripts;
buzbee67bf8852011-08-17 17:51:35 -0700436
437 /* The following are new data structures to support SSA representations */
buzbeee1965672012-03-11 18:39:19 -0700438 /* Map original Dalvik virtual reg i to the current SSA name */
439 int* vRegToSSAMap; // length == method->registersSize
buzbeef0cde542011-09-13 14:55:02 -0700440 int* SSALastDefs; // length == method->registersSize
buzbee67bf8852011-08-17 17:51:35 -0700441 ArenaBitVector* isConstantV; // length == numSSAReg
442 int* constantValues; // length == numSSAReg
buzbeec0ecd652011-09-25 18:11:54 -0700443 int* phiAliasMap; // length == numSSAReg
444 MIR* phiList;
buzbee67bf8852011-08-17 17:51:35 -0700445
buzbee239c4e72012-03-16 08:42:29 -0700446 /* Use counts of ssa names */
buzbee84fd6932012-03-29 16:44:16 -0700447 GrowableList useCounts; // Weighted by nesting depth
448 GrowableList rawUseCounts; // Not weighted
buzbee239c4e72012-03-16 08:42:29 -0700449
450 /* Optimization support */
451 GrowableList loopHeaders;
452
buzbee67bf8852011-08-17 17:51:35 -0700453 /* Map SSA names to location */
454 RegLocation* regLocation;
455 int sequenceNumber;
456
buzbee67bc2362011-10-11 18:08:40 -0700457 /* Keep track of Dalvik vReg to physical register mappings */
458 PromotionMap* promotionMap;
459
buzbeee1965672012-03-11 18:39:19 -0700460 /* SSA name for Method* */
461 int methodSReg;
462
buzbee67bf8852011-08-17 17:51:35 -0700463 /*
464 * Set to the Dalvik PC of the switch instruction if it has more than
465 * MAX_CHAINED_SWITCH_CASES cases.
466 */
467 const u2* switchOverflowPad;
468
469 int numReachableBlocks;
buzbeee1965672012-03-11 18:39:19 -0700470 int numDalvikRegisters; // method->registersSize
buzbee67bf8852011-08-17 17:51:35 -0700471 BasicBlock* entryBlock;
472 BasicBlock* exitBlock;
473 BasicBlock* curBlock;
474 BasicBlock* nextCodegenBlock; // for extended trace codegen
475 GrowableList dfsOrder;
buzbee5b537102012-01-17 17:33:47 -0800476 GrowableList dfsPostOrder;
buzbee67bf8852011-08-17 17:51:35 -0700477 GrowableList domPostOrderTraversal;
buzbee5ade1d22011-09-09 14:44:52 -0700478 GrowableList throwLaunchpads;
buzbeec1f45042011-09-21 16:03:19 -0700479 GrowableList suspendLaunchpads;
buzbeefc9e6fa2012-03-23 15:14:29 -0700480 GrowableList intrinsicLaunchpads;
buzbeee1965672012-03-11 18:39:19 -0700481 GrowableList compilerTemps;
buzbee5b537102012-01-17 17:33:47 -0800482 int* iDomList;
buzbee67bf8852011-08-17 17:51:35 -0700483 ArenaBitVector* tryBlockAddr;
484 ArenaBitVector** defBlockMatrix; // numDalvikRegister x numBlocks
485 ArenaBitVector* tempBlockV;
486 ArenaBitVector* tempDalvikRegisterV;
487 ArenaBitVector* tempSSARegisterV; // numSSARegs
488 bool printSSANames;
489 void* blockLabelList;
490 bool quitLoopMode; // cold path/complex bytecode
491 int preservedRegsUsed; // How many callee save regs used
492 /*
buzbee5ade1d22011-09-09 14:44:52 -0700493 * Frame layout details.
494 * NOTE: for debug support it will be necessary to add a structure
495 * to map the Dalvik virtual registers to the promoted registers.
496 * NOTE: "num" fields are in 4-byte words, "Size" and "Offset" in bytes.
buzbee67bf8852011-08-17 17:51:35 -0700497 */
498 int numIns;
499 int numOuts;
Ian Rogersa3760aa2011-11-14 14:32:37 -0800500 int numRegs; // Unlike numDalvikRegisters, does not include ins
buzbeebbaf8942011-10-02 13:08:29 -0700501 int numCoreSpills;
buzbee67bf8852011-08-17 17:51:35 -0700502 int numFPSpills;
buzbeeefccc562012-03-11 11:19:28 -0700503 int numCompilerTemps;
buzbee67bf8852011-08-17 17:51:35 -0700504 int frameSize;
505 unsigned int coreSpillMask;
506 unsigned int fpSpillMask;
buzbeecefd1872011-09-09 09:59:52 -0700507 unsigned int attrs;
buzbee67bf8852011-08-17 17:51:35 -0700508 /*
509 * CLEANUP/RESTRUCTURE: The code generation utilities don't have a built-in
buzbee03fa2632011-09-20 17:10:57 -0700510 * mechanism to propagate the original Dalvik opcode address to the
buzbee67bf8852011-08-17 17:51:35 -0700511 * associated generated instructions. For the trace compiler, this wasn't
512 * necessary because the interpreter handled all throws and debugging
513 * requests. For now we'll handle this by placing the Dalvik offset
514 * in the CompilationUnit struct before codegen for each instruction.
515 * The low-level LIR creation utilites will pull it from here. Should
516 * be rewritten.
517 */
Elliott Hughese52e49b2012-04-02 16:05:44 -0700518 int currentDalvikOffset;
519 GrowableList switchTables;
520 GrowableList fillArrayData;
521 const u2* insns;
522 u4 insnsSize;
523 bool disableDataflow; // Skip dataflow analysis if possible
Elliott Hughesa0e18062012-04-13 15:59:59 -0700524 SafeMap<unsigned int, BasicBlock*> blockMap; // findBlock lookup cache
525 SafeMap<unsigned int, LIR*> boundaryMap; // boundary lookup cache
Elliott Hughese52e49b2012-04-02 16:05:44 -0700526 int defCount; // Used to estimate number of SSA names
527
528 // If non-empty, apply optimizer/debug flags only to matching methods.
529 std::string compilerMethodMatch;
530 // Flips sense of compilerMethodMatch - apply flags if doesn't match.
531 bool compilerFlipMatch;
Elliott Hughes7b9d9962012-04-20 18:48:18 -0700532 ArenaMemBlock* arenaHead;
533 ArenaMemBlock* currentArena;
Elliott Hughese52e49b2012-04-02 16:05:44 -0700534 int numArenaBlocks;
Elliott Hughes7b9d9962012-04-20 18:48:18 -0700535 Memstats* mstats;
Elliott Hughese52e49b2012-04-02 16:05:44 -0700536 int* opcodeCount; // Count Dalvik opcodes for tuning
buzbee3d661942012-03-14 17:37:27 -0700537#ifndef NDEBUG
538 /*
539 * Sanity checking for the register temp tracking. The same ssa
540 * name should never be associated with one temp register per
541 * instruction compilation.
542 */
543 int liveSReg;
544#endif
Elliott Hughes719ace42012-03-09 18:06:03 -0800545};
buzbee67bf8852011-08-17 17:51:35 -0700546
Elliott Hughes719ace42012-03-09 18:06:03 -0800547enum OpSize {
buzbeee3acd072012-02-25 17:03:10 -0800548 kWord,
549 kLong,
550 kSingle,
551 kDouble,
552 kUnsignedHalf,
553 kSignedHalf,
554 kUnsignedByte,
555 kSignedByte,
Elliott Hughes719ace42012-03-09 18:06:03 -0800556};
buzbeee3acd072012-02-25 17:03:10 -0800557
Elliott Hughes719ace42012-03-09 18:06:03 -0800558enum OpKind {
buzbee31a4a6f2012-02-28 15:36:15 -0800559 kOpMov,
560 kOpMvn,
561 kOpCmp,
562 kOpLsl,
563 kOpLsr,
564 kOpAsr,
565 kOpRor,
566 kOpNot,
567 kOpAnd,
568 kOpOr,
569 kOpXor,
570 kOpNeg,
571 kOpAdd,
572 kOpAdc,
573 kOpSub,
574 kOpSbc,
575 kOpRsub,
576 kOpMul,
577 kOpDiv,
578 kOpRem,
579 kOpBic,
580 kOpCmn,
581 kOpTst,
582 kOpBkpt,
583 kOpBlx,
584 kOpPush,
585 kOpPop,
586 kOp2Char,
587 kOp2Short,
588 kOp2Byte,
589 kOpCondBr,
590 kOpUncondBr,
buzbee5de34942012-03-01 14:51:57 -0800591 kOpBx,
buzbee31a4a6f2012-02-28 15:36:15 -0800592 kOpInvalid,
Elliott Hughes719ace42012-03-09 18:06:03 -0800593};
buzbee31a4a6f2012-02-28 15:36:15 -0800594
Ian Rogers680b1bd2012-03-07 20:18:49 -0800595std::ostream& operator<<(std::ostream& os, const OpKind& kind);
596
Elliott Hughes719ace42012-03-09 18:06:03 -0800597enum ConditionCode {
Ian Rogersb5d09b22012-03-06 22:14:17 -0800598 kCondEq, // equal
599 kCondNe, // not equal
600 kCondCs, // carry set (unsigned less than)
601 kCondUlt = kCondCs,
602 kCondCc, // carry clear (unsigned greater than or same)
603 kCondUge = kCondCc,
604 kCondMi, // minus
605 kCondPl, // plus, positive or zero
606 kCondVs, // overflow
607 kCondVc, // no overflow
608 kCondHi, // unsigned greater than
609 kCondLs, // unsigned lower or same
610 kCondGe, // signed greater than or equal
611 kCondLt, // signed less than
612 kCondGt, // signed greater than
613 kCondLe, // signed less than or equal
614 kCondAl, // always
615 kCondNv, // never
Elliott Hughes719ace42012-03-09 18:06:03 -0800616};
buzbee31a4a6f2012-02-28 15:36:15 -0800617
Elliott Hughes719ace42012-03-09 18:06:03 -0800618enum ThrowKind {
buzbee31a4a6f2012-02-28 15:36:15 -0800619 kThrowNullPointer,
620 kThrowDivZero,
621 kThrowArrayBounds,
622 kThrowVerificationError,
buzbee31a4a6f2012-02-28 15:36:15 -0800623 kThrowNoSuchMethod,
624 kThrowStackOverflow,
Elliott Hughes719ace42012-03-09 18:06:03 -0800625};
buzbee31a4a6f2012-02-28 15:36:15 -0800626
Elliott Hughes719ace42012-03-09 18:06:03 -0800627struct SwitchTable {
buzbee5de34942012-03-01 14:51:57 -0800628 int offset;
629 const u2* table; // Original dex table
630 int vaddr; // Dalvik offset of switch opcode
buzbeec5159d52012-03-03 11:48:39 -0800631 LIR* anchor; // Reference instruction for relative offsets
buzbee5de34942012-03-01 14:51:57 -0800632 LIR** targets; // Array of case targets
Elliott Hughes719ace42012-03-09 18:06:03 -0800633};
buzbee5de34942012-03-01 14:51:57 -0800634
Elliott Hughes719ace42012-03-09 18:06:03 -0800635struct FillArrayData {
buzbee5de34942012-03-01 14:51:57 -0800636 int offset;
637 const u2* table; // Original dex table
638 int size;
Elliott Hughesadb8c672012-03-06 16:49:32 -0800639 int vaddr; // Dalvik offset of FILL_ARRAY_DATA opcode
Elliott Hughes719ace42012-03-09 18:06:03 -0800640};
buzbee5de34942012-03-01 14:51:57 -0800641
buzbee16da88c2012-03-20 10:38:17 -0700642#define MAX_PATTERN_LEN 5
643
644enum SpecialCaseHandler {
645 kNoHandler,
646 kNullMethod,
647 kConstFunction,
648 kIGet,
649 kIGetBoolean,
650 kIGetObject,
651 kIGetByte,
652 kIGetChar,
653 kIGetShort,
654 kIGetWide,
655 kIPut,
656 kIPutBoolean,
657 kIPutObject,
658 kIPutByte,
659 kIPutChar,
660 kIPutShort,
661 kIPutWide,
buzbeee62076c2012-03-21 14:26:16 -0700662 kIdentity,
buzbee16da88c2012-03-20 10:38:17 -0700663};
664
665struct CodePattern {
666 const Instruction::Code opcodes[MAX_PATTERN_LEN];
667 const SpecialCaseHandler handlerCode;
668};
669
670static const CodePattern specialPatterns[] = {
671 {{Instruction::RETURN_VOID}, kNullMethod},
672 {{Instruction::CONST, Instruction::RETURN}, kConstFunction},
673 {{Instruction::CONST_4, Instruction::RETURN}, kConstFunction},
Ian Rogersf24132c2012-03-21 01:34:31 -0700674 {{Instruction::CONST_4, Instruction::RETURN_OBJECT}, kConstFunction},
buzbee16da88c2012-03-20 10:38:17 -0700675 {{Instruction::CONST_16, Instruction::RETURN}, kConstFunction},
676 {{Instruction::IGET, Instruction:: RETURN}, kIGet},
Ian Rogersf24132c2012-03-21 01:34:31 -0700677 {{Instruction::IGET_BOOLEAN, Instruction::RETURN}, kIGetBoolean},
678 {{Instruction::IGET_OBJECT, Instruction::RETURN_OBJECT}, kIGetObject},
679 {{Instruction::IGET_BYTE, Instruction::RETURN}, kIGetByte},
680 {{Instruction::IGET_CHAR, Instruction::RETURN}, kIGetChar},
681 {{Instruction::IGET_SHORT, Instruction::RETURN}, kIGetShort},
682 {{Instruction::IGET_WIDE, Instruction::RETURN_WIDE}, kIGetWide},
683 {{Instruction::IPUT, Instruction::RETURN_VOID}, kIPut},
684 {{Instruction::IPUT_BOOLEAN, Instruction::RETURN_VOID}, kIPutBoolean},
685 {{Instruction::IPUT_OBJECT, Instruction::RETURN_VOID}, kIPutObject},
686 {{Instruction::IPUT_BYTE, Instruction::RETURN_VOID}, kIPutByte},
687 {{Instruction::IPUT_CHAR, Instruction::RETURN_VOID}, kIPutChar},
688 {{Instruction::IPUT_SHORT, Instruction::RETURN_VOID}, kIPutShort},
689 {{Instruction::IPUT_WIDE, Instruction::RETURN_VOID}, kIPutWide},
buzbeee62076c2012-03-21 14:26:16 -0700690 {{Instruction::RETURN}, kIdentity},
691 {{Instruction::RETURN_OBJECT}, kIdentity},
692 {{Instruction::RETURN_WIDE}, kIdentity},
buzbee16da88c2012-03-20 10:38:17 -0700693};
buzbee5de34942012-03-01 14:51:57 -0800694
buzbee5abfa3e2012-01-31 17:01:43 -0800695BasicBlock* oatNewBB(CompilationUnit* cUnit, BBType blockType, int blockId);
buzbee67bf8852011-08-17 17:51:35 -0700696
697void oatAppendMIR(BasicBlock* bb, MIR* mir);
698
699void oatPrependMIR(BasicBlock* bb, MIR* mir);
700
701void oatInsertMIRAfter(BasicBlock* bb, MIR* currentMIR, MIR* newMIR);
702
703void oatAppendLIR(CompilationUnit* cUnit, LIR* lir);
704
705void oatInsertLIRBefore(LIR* currentLIR, LIR* newLIR);
706
707void oatInsertLIRAfter(LIR* currentLIR, LIR* newLIR);
708
buzbeefc9e6fa2012-03-23 15:14:29 -0700709MIR* oatFindMoveResult(CompilationUnit* cUnit, BasicBlock* bb, MIR* mir,
710 bool wide);
buzbee67bf8852011-08-17 17:51:35 -0700711/* Debug Utilities */
712void oatDumpCompilationUnit(CompilationUnit* cUnit);
713
Elliott Hughes11d1b0c2012-01-23 16:57:47 -0800714} // namespace art
715
buzbee67bf8852011-08-17 17:51:35 -0700716#endif // ART_SRC_COMPILER_COMPILER_IR_H_