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