Compiler.h revision 18fba346582c08d81aa96d9508c0e935bad5f36f 
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#include <Thread.h>
18#include <setjmp.h>
19
20#ifndef _DALVIK_VM_COMPILER
21#define _DALVIK_VM_COMPILER
22
23/*
24 * Uncomment the following to enable JIT signature breakpoint
25 * #define SIGNATURE_BREAKPOINT
26 */
27
28#define MAX_JIT_RUN_LEN                 64
29#define COMPILER_WORK_QUEUE_SIZE        100
30#define COMPILER_IC_PATCH_QUEUE_SIZE    64
31
32/* Architectural-independent parameters for predicted chains */
33#define PREDICTED_CHAIN_CLAZZ_INIT       0
34#define PREDICTED_CHAIN_METHOD_INIT      0
35#define PREDICTED_CHAIN_COUNTER_INIT     0
36/* A fake value which will avoid initialization and won't match any class */
37#define PREDICTED_CHAIN_FAKE_CLAZZ       0xdeadc001
38/* Has to be positive */
39#define PREDICTED_CHAIN_COUNTER_AVOID    0x7fffffff
40/* Rechain after this many misses - shared globally and has to be positive */
41#define PREDICTED_CHAIN_COUNTER_RECHAIN  8192
42
43#define COMPILER_TRACED(X)
44#define COMPILER_TRACEE(X)
45#define COMPILER_TRACE_CHAINING(X)
46
47/* Macro to change the permissions applied to a chunk of the code cache */
48#define PROTECT_CODE_CACHE_ATTRS       (PROT_READ | PROT_EXEC)
49#define UNPROTECT_CODE_CACHE_ATTRS     (PROT_READ | PROT_EXEC | PROT_WRITE)
50
51/* Acquire the lock before removing PROT_WRITE from the specified mem region */
52#define UNPROTECT_CODE_CACHE(addr, size)                                       \
53    {                                                                          \
54        dvmLockMutex(&gDvmJit.codeCacheProtectionLock);                        \
55        mprotect((void *) (((intptr_t) (addr)) & ~gDvmJit.pageSizeMask),       \
56                 (size) + (((intptr_t) (addr)) & gDvmJit.pageSizeMask),        \
57                 (UNPROTECT_CODE_CACHE_ATTRS));                                \
58    }
59
60/* Add the PROT_WRITE to the specified memory region then release the lock */
61#define PROTECT_CODE_CACHE(addr, size)                                         \
62    {                                                                          \
63        mprotect((void *) (((intptr_t) (addr)) & ~gDvmJit.pageSizeMask),       \
64                 (size) + (((intptr_t) (addr)) & gDvmJit.pageSizeMask),        \
65                 (PROTECT_CODE_CACHE_ATTRS));                                  \
66        dvmUnlockMutex(&gDvmJit.codeCacheProtectionLock);                      \
67    }
68
69#define SINGLE_STEP_OP(opcode)                                                 \
70    (gDvmJit.includeSelectedOp !=                                              \
71     ((gDvmJit.opList[opcode >> 3] & (1 << (opcode & 0x7))) != 0))
72
73typedef enum JitInstructionSetType {
74    DALVIK_JIT_NONE = 0,
75    DALVIK_JIT_ARM,
76    DALVIK_JIT_THUMB,
77    DALVIK_JIT_THUMB2,
78    DALVIK_JIT_THUMB2EE,
79    DALVIK_JIT_IA32
80} JitInstructionSetType;
81
82/* Description of a compiled trace. */
83typedef struct JitTranslationInfo {
84    void *codeAddress;
85    JitInstructionSetType instructionSet;
86    int profileCodeSize;
87    bool discardResult;         // Used for debugging divergence and IC patching
88    bool methodCompilationAborted;  // Cannot compile the whole method
89    Thread *requestingThread;   // For debugging purpose
90    int cacheVersion;           // Used to identify stale trace requests
91} JitTranslationInfo;
92
93typedef enum WorkOrderKind {
94    kWorkOrderInvalid = 0,      // Should never see by the backend
95    kWorkOrderMethod = 1,       // Work is to compile a whole method
96    kWorkOrderTrace = 2,        // Work is to compile code fragment(s)
97    kWorkOrderTraceDebug = 3,   // Work is to compile/debug code fragment(s)
98    kWorkOrderProfileMode = 4,  // Change profiling mode
99} WorkOrderKind;
100
101typedef struct CompilerWorkOrder {
102    const u2* pc;
103    WorkOrderKind kind;
104    void* info;
105    JitTranslationInfo result;
106    jmp_buf *bailPtr;
107} CompilerWorkOrder;
108
109/* Chain cell for predicted method invocation */
110typedef struct PredictedChainingCell {
111    u4 branch;                  /* Branch to chained destination */
112    const ClassObject *clazz;   /* key for prediction */
113    const Method *method;       /* to lookup native PC from dalvik PC */
114    const ClassObject *stagedClazz;   /* possible next key for prediction */
115} PredictedChainingCell;
116
117/* Work order for inline cache patching */
118typedef struct ICPatchWorkOrder {
119    PredictedChainingCell *cellAddr;    /* Address to be patched */
120    PredictedChainingCell cellContent;  /* content of the new cell */
121} ICPatchWorkOrder;
122
123/* States of the dbg interpreter when serving a JIT-related request */
124typedef enum JitState {
125    /* Entering states in the debug interpreter */
126    kJitNot = 0,               // Non-JIT related reasons */
127    kJitTSelectRequest = 1,    // Request a trace (subject to filtering)
128    kJitTSelectRequestHot = 2, // Request a hot trace (bypass the filter)
129    kJitSelfVerification = 3,  // Self Verification Mode
130
131    /* Operational states in the debug interpreter */
132    kJitTSelect = 4,           // Actively selecting a trace
133    kJitTSelectEnd = 5,        // Done with the trace - wrap it up
134    kJitSingleStep = 6,        // Single step interpretation
135    kJitSingleStepEnd = 7,     // Done with single step, ready return to mterp
136    kJitDone = 8,              // Ready to leave the debug interpreter
137} JitState;
138
139#if defined(WITH_SELF_VERIFICATION)
140typedef enum SelfVerificationState {
141    kSVSIdle = 0,           // Idle
142    kSVSStart = 1,          // Shadow space set up, running compiled code
143    kSVSPunt = 2,           // Exiting compiled code by punting
144    kSVSSingleStep = 3,     // Exiting compiled code by single stepping
145    kSVSNoProfile = 4,      // Exiting compiled code and don't collect profiles
146    kSVSTraceSelect = 5,    // Exiting compiled code and compile the next pc
147    kSVSNormal = 6,         // Exiting compiled code normally
148    kSVSNoChain = 7,        // Exiting compiled code by no chain
149    kSVSBackwardBranch = 8, // Exiting compiled code with backward branch trace
150    kSVSDebugInterp = 9,    // Normal state restored, running debug interpreter
151} SelfVerificationState;
152#endif
153
154typedef enum JitHint {
155   kJitHintNone = 0,
156   kJitHintTaken = 1,         // Last inst in run was taken branch
157   kJitHintNotTaken = 2,      // Last inst in run was not taken branch
158   kJitHintNoBias = 3,        // Last inst in run was unbiased branch
159} jitHint;
160
161/*
162 * Element of a Jit trace description. If the isCode bit is set, it describes
163 * a contiguous sequence of Dalvik byte codes.
164 */
165typedef struct {
166    unsigned isCode:1;       // If set denotes code fragments
167    unsigned numInsts:8;     // Number of Byte codes in run
168    unsigned runEnd:1;       // Run ends with last byte code
169    jitHint  hint:6;         // Hint to apply to final code of run
170    u2    startOffset;       // Starting offset for trace run
171} JitCodeDesc;
172
173/*
174 * A complete list of trace runs passed to the compiler looks like the
175 * following:
176 *   frag1
177 *   frag2
178 *   frag3
179 *   meta1
180 *   meta2
181 *   frag4
182 *
183 * frags 1-4 have the "isCode" field set, and metas 1-2 are plain pointers or
184 * pointers to auxiliary data structures as long as the LSB is null.
185 * The meaning of the meta content is loosely defined. It is usually the code
186 * fragment right before the first meta field (frag3 in this case) to
187 * understand and parse them. Frag4 could be a dummy one with 0 "numInsts" but
188 * the "runEnd" field set.
189 *
190 * For example, if a trace run contains a method inlining target, the class
191 * type of "this" and the currently resolved method pointer are two instances
192 * of meta information stored there.
193 */
194typedef union {
195    JitCodeDesc frag;
196    void*       meta;
197} JitTraceRun;
198
199/*
200 * Trace description as will appear in the translation cache.  Note
201 * flexible array at end, as these will be of variable size.  To
202 * conserve space in the translation cache, total length of JitTraceRun
203 * array must be recomputed via seqential scan if needed.
204 */
205typedef struct {
206    const Method* method;
207    JitTraceRun trace[0];       // Variable-length trace descriptors
208} JitTraceDescription;
209
210typedef enum JitMethodAttributes {
211    kIsCallee = 0,      /* Code is part of a callee (invoked by a hot trace) */
212    kIsHot,             /* Code is part of a hot trace */
213    kIsLeaf,            /* Method is leaf */
214    kIsEmpty,           /* Method is empty */
215    kIsThrowFree,       /* Method doesn't throw */
216    kIsGetter,          /* Method fits the getter pattern */
217    kIsSetter,          /* Method fits the setter pattern */
218} JitMethodAttributes;
219
220#define METHOD_IS_CALLEE        (1 << kIsCallee)
221#define METHOD_IS_HOT           (1 << kIsHot)
222#define METHOD_IS_LEAF          (1 << kIsLeaf)
223#define METHOD_IS_EMPTY         (1 << kIsEmpty)
224#define METHOD_IS_THROW_FREE    (1 << kIsThrowFree)
225#define METHOD_IS_GETTER        (1 << kIsGetter)
226#define METHOD_IS_SETTER        (1 << kIsSetter)
227
228/* Vectors to provide optimization hints */
229typedef enum JitOptimizationHints {
230    kJitOptNoLoop = 0,          // Disable loop formation/optimization
231} JitOptimizationHints;
232
233#define JIT_OPT_NO_LOOP         (1 << kJitOptNoLoop)
234
235/* Customized node traversal orders for different needs */
236typedef enum DataFlowAnalysisMode {
237    kAllNodes = 0,              // All nodes
238    kReachableNodes,            // All reachable nodes
239    kPreOrderDFSTraversal,      // Depth-First-Search / Pre-Order
240    kPostOrderDFSTraversal,     // Depth-First-Search / Post-Order
241    kPostOrderDOMTraversal,     // Dominator tree / Post-Order
242} DataFlowAnalysisMode;
243
244typedef struct CompilerMethodStats {
245    const Method *method;       // Used as hash entry signature
246    int dalvikSize;             // # of bytes for dalvik bytecodes
247    int compiledDalvikSize;     // # of compiled dalvik bytecodes
248    int nativeSize;             // # of bytes for produced native code
249    int attributes;             // attribute vector
250} CompilerMethodStats;
251
252struct CompilationUnit;
253struct BasicBlock;
254struct SSARepresentation;
255struct GrowableList;
256struct JitEntry;
257struct MIR;
258
259bool dvmCompilerSetupCodeCache(void);
260bool dvmCompilerArchInit(void);
261void dvmCompilerArchDump(void);
262bool dvmCompilerStartup(void);
263void dvmCompilerShutdown(void);
264bool dvmCompilerWorkEnqueue(const u2* pc, WorkOrderKind kind, void* info);
265void *dvmCheckCodeCache(void *method);
266CompilerMethodStats *dvmCompilerAnalyzeMethodBody(const Method *method,
267                                                  bool isCallee);
268bool dvmCompilerCanIncludeThisInstruction(const Method *method,
269                                          const DecodedInstruction *insn);
270bool dvmCompileMethod(const Method *method);
271bool dvmCompileTrace(JitTraceDescription *trace, int numMaxInsts,
272                     JitTranslationInfo *info, jmp_buf *bailPtr, int optHints);
273void dvmCompilerDumpStats(void);
274void dvmCompilerDrainQueue(void);
275void dvmJitUnchainAll(void);
276void dvmCompilerSortAndPrintTraceProfiles(void);
277void dvmCompilerPerformSafePointChecks(void);
278void dvmCompilerInlineMIR(struct CompilationUnit *cUnit);
279void dvmInitializeSSAConversion(struct CompilationUnit *cUnit);
280int dvmConvertSSARegToDalvik(const struct CompilationUnit *cUnit, int ssaReg);
281bool dvmCompilerLoopOpt(struct CompilationUnit *cUnit);
282void dvmCompilerNonLoopAnalysis(struct CompilationUnit *cUnit);
283bool dvmCompilerFindLocalLiveIn(struct CompilationUnit *cUnit,
284                                struct BasicBlock *bb);
285bool dvmCompilerDoSSAConversion(struct CompilationUnit *cUnit,
286                                struct BasicBlock *bb);
287bool dvmCompilerDoConstantPropagation(struct CompilationUnit *cUnit,
288                                      struct BasicBlock *bb);
289bool dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit,
290                                       struct BasicBlock *bb);
291/* Clear the visited flag for each BB */
292bool dvmCompilerClearVisitedFlag(struct CompilationUnit *cUnit,
293                                 struct BasicBlock *bb);
294char *dvmCompilerGetDalvikDisassembly(const DecodedInstruction *insn,
295                                      char *note);
296char *dvmCompilerFullDisassembler(const struct CompilationUnit *cUnit,
297                                  const struct MIR *mir);
298char *dvmCompilerGetSSAString(struct CompilationUnit *cUnit,
299                              struct SSARepresentation *ssaRep);
300void dvmCompilerDataFlowAnalysisDispatcher(struct CompilationUnit *cUnit,
301                bool (*func)(struct CompilationUnit *, struct BasicBlock *),
302                DataFlowAnalysisMode dfaMode,
303                bool isIterative);
304void dvmCompilerMethodSSATransformation(struct CompilationUnit *cUnit);
305void dvmCompilerStateRefresh(void);
306JitTraceDescription *dvmCopyTraceDescriptor(const u2 *pc,
307                                            const struct JitEntry *desc);
308void *dvmCompilerGetInterpretTemplate();
309#endif /* _DALVIK_VM_COMPILER */
310