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
18#define _DALVIK_VM_COMPILER_IR
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 (-1)
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    kMethodEntryBlock,
58    kTraceEntryBlock,
59    kDalvikByteCode,
60    kTraceExitBlock,
61    kMethodExitBlock,
62    kPCReconstruction,
63    kExceptionHandling,
64} BBType;
65
66typedef struct ChainCellCounts {
67    union {
68        u1 count[kChainingCellLast]; /* include one more space for the gap # */
69        u4 dummyForAlignment;
70    } u;
71} ChainCellCounts;
72
73typedef struct LIR {
74    int offset;
75    struct LIR *next;
76    struct LIR *prev;
77    struct LIR *target;
78} LIR;
79
80enum ExtendedMIROpcode {
81    kMirOpFirst = 256,
82    kMirOpPhi = kMirOpFirst,
83    kMirOpNullNRangeUpCheck,
84    kMirOpNullNRangeDownCheck,
85    kMirOpLowerBound,
86    kMirOpPunt,
87    kMirOpCheckInlinePrediction,        // Gen checks for predicted inlining
88    kMirOpLast,
89};
90
91struct SSARepresentation;
92
93typedef enum {
94    kMIRIgnoreNullCheck = 0,
95    kMIRNullCheckOnly,
96    kMIRIgnoreRangeCheck,
97    kMIRRangeCheckOnly,
98    kMIRInlined,                        // Invoke is inlined (ie dead)
99    kMIRInlinedPred,                    // Invoke is inlined via prediction
100    kMIRCallee,                         // Instruction is inlined from callee
101} MIROptimizationFlagPositons;
102
103#define MIR_IGNORE_NULL_CHECK           (1 << kMIRIgnoreNullCheck)
104#define MIR_NULL_CHECK_ONLY             (1 << kMIRNullCheckOnly)
105#define MIR_IGNORE_RANGE_CHECK          (1 << kMIRIgnoreRangeCheck)
106#define MIR_RANGE_CHECK_ONLY            (1 << kMIRRangeCheckOnly)
107#define MIR_INLINED                     (1 << kMIRInlined)
108#define MIR_INLINED_PRED                (1 << kMIRInlinedPred)
109#define MIR_CALLEE                      (1 << kMIRCallee)
110
111typedef struct CallsiteInfo {
112    const ClassObject *clazz;
113    const Method *method;
114    LIR *misPredBranchOver;
115} CallsiteInfo;
116
117typedef struct MIR {
118    DecodedInstruction dalvikInsn;
119    unsigned int width;
120    unsigned int offset;
121    struct MIR *prev;
122    struct MIR *next;
123    struct SSARepresentation *ssaRep;
124    int OptimizationFlags;
125    int seqNum;
126    union {
127        // Used by the inlined insn from the callee to find the mother method
128        const Method *calleeMethod;
129        // Used by the inlined invoke to find the class and method pointers
130        CallsiteInfo *callsiteInfo;
131    } meta;
132} MIR;
133
134struct BasicBlockDataFlow;
135
136typedef struct BasicBlock {
137    int id;
138    int visited;
139    unsigned int startOffset;
140    const Method *containingMethod;     // For blocks from the callee
141    BBType blockType;
142    bool needFallThroughBranch;         // For blocks ended due to length limit
143    bool isFallThroughFromInvoke;       // True means the block needs alignment
144    MIR *firstMIRInsn;
145    MIR *lastMIRInsn;
146    struct BasicBlock *fallThrough;
147    struct BasicBlock *taken;
148    struct BasicBlock *next;            // Serial link for book keeping purposes
149    struct BasicBlockDataFlow *dataFlowInfo;
150} BasicBlock;
151
152struct LoopAnalysis;
153struct RegisterPool;
154
155typedef enum AssemblerStatus {
156    kSuccess,
157    kRetryAll,
158    kRetryHalve
159} AssemblerStatus;
160
161typedef struct CompilationUnit {
162    int numInsts;
163    int numBlocks;
164    BasicBlock **blockList;
165    const Method *method;
166    const JitTraceDescription *traceDesc;
167    LIR *firstLIRInsn;
168    LIR *lastLIRInsn;
169    LIR *wordList;
170    LIR *chainCellOffsetLIR;
171    GrowableList pcReconstructionList;
172    int headerSize;                     // bytes before the first code ptr
173    int dataOffset;                     // starting offset of literal pool
174    int totalSize;                      // header + code size
175    AssemblerStatus assemblerStatus;    // Success or fix and retry
176    int assemblerRetries;               // How many times tried to fix assembly
177    unsigned char *codeBuffer;
178    void *baseAddr;
179    bool printMe;
180    bool allSingleStep;
181    bool executionCount;                // Add code to count trace executions
182    bool hasLoop;                       // Contains a loop
183    bool hasInvoke;                     // Contains an invoke instruction
184    bool heapMemOp;                     // Mark mem ops for self verification
185    bool wholeMethod;
186    int numChainingCells[kChainingCellGap];
187    LIR *firstChainingLIR[kChainingCellGap];
188    LIR *chainingCellBottom;
189    struct RegisterPool *regPool;
190    int optRound;                       // round number to tell an LIR's age
191    jmp_buf *bailPtr;
192    JitInstructionSetType instructionSet;
193    /* Number of total regs used in the whole cUnit after SSA transformation */
194    int numSSARegs;
195    /* Map SSA reg i to the Dalvik[15..0]/Sub[31..16] pair. */
196    GrowableList *ssaToDalvikMap;
197
198    /* The following are new data structures to support SSA representations */
199    /* Map original Dalvik reg i to the SSA[15..0]/Sub[31..16] pair */
200    int *dalvikToSSAMap;                // length == method->registersSize
201    BitVector *isConstantV;             // length == numSSAReg
202    int *constantValues;                // length == numSSAReg
203
204    /* Data structure for loop analysis and optimizations */
205    struct LoopAnalysis *loopAnalysis;
206
207    /* Map SSA names to location */
208    RegLocation *regLocation;
209    int sequenceNumber;
210
211    /*
212     * Set to the Dalvik PC of the switch instruction if it has more than
213     * MAX_CHAINED_SWITCH_CASES cases.
214     */
215    const u2 *switchOverflowPad;
216} CompilationUnit;
217
218#if defined(WITH_SELF_VERIFICATION)
219#define HEAP_ACCESS_SHADOW(_state) cUnit->heapMemOp = _state
220#else
221#define HEAP_ACCESS_SHADOW(_state)
222#endif
223
224BasicBlock *dvmCompilerNewBB(BBType blockType);
225
226void dvmCompilerAppendMIR(BasicBlock *bb, MIR *mir);
227
228void dvmCompilerPrependMIR(BasicBlock *bb, MIR *mir);
229
230void dvmCompilerInsertMIRAfter(BasicBlock *bb, MIR *currentMIR, MIR *newMIR);
231
232void dvmCompilerAppendLIR(CompilationUnit *cUnit, LIR *lir);
233
234void dvmCompilerInsertLIRBefore(LIR *currentLIR, LIR *newLIR);
235
236void dvmCompilerInsertLIRAfter(LIR *currentLIR, LIR *newLIR);
237
238void dvmCompilerAbort(CompilationUnit *cUnit);
239
240/* Debug Utilities */
241void dvmCompilerDumpCompilationUnit(CompilationUnit *cUnit);
242
243#endif /* _DALVIK_VM_COMPILER_IR */
244