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