Home | History | Annotate | Download | only in compiler 
      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 
     22 typedef enum RegisterClass {
     23     kCoreReg,
     24     kFPReg,
     25     kAnyReg,
     26 } RegisterClass;
     27 
     28 typedef enum RegLocationType {
     29     kLocDalvikFrame = 0,
     30     kLocPhysReg,
     31     kLocRetval,          // Return region in interpState
     32     kLocSpill,
     33 } RegLocationType;
     34 
     35 typedef 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 
     47 typedef 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 
     66 typedef struct ChainCellCounts {
     67     union {
     68         u1 count[kChainingCellLast]; /* include one more space for the gap # */
     69         u4 dummyForAlignment;
     70     } u;
     71 } ChainCellCounts;
     72 
     73 typedef struct LIR {
     74     int offset;
     75     struct LIR *next;
     76     struct LIR *prev;
     77     struct LIR *target;
     78 } LIR;
     79 
     80 enum 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 
     91 struct SSARepresentation;
     92 
     93 typedef 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 
    111 typedef struct CallsiteInfo {
    112     const ClassObject *clazz;
    113     const Method *method;
    114     LIR *misPredBranchOver;
    115 } CallsiteInfo;
    116 
    117 typedef 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 
    134 struct BasicBlockDataFlow;
    135 
    136 typedef 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 
    152 struct LoopAnalysis;
    153 struct RegisterPool;
    154 
    155 typedef enum AssemblerStatus {
    156     kSuccess,
    157     kRetryAll,
    158     kRetryHalve
    159 } AssemblerStatus;
    160 
    161 typedef 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 
    224 BasicBlock *dvmCompilerNewBB(BBType blockType);
    225 
    226 void dvmCompilerAppendMIR(BasicBlock *bb, MIR *mir);
    227 
    228 void dvmCompilerPrependMIR(BasicBlock *bb, MIR *mir);
    229 
    230 void dvmCompilerInsertMIRAfter(BasicBlock *bb, MIR *currentMIR, MIR *newMIR);
    231 
    232 void dvmCompilerAppendLIR(CompilationUnit *cUnit, LIR *lir);
    233 
    234 void dvmCompilerInsertLIRBefore(LIR *currentLIR, LIR *newLIR);
    235 
    236 void dvmCompilerInsertLIRAfter(LIR *currentLIR, LIR *newLIR);
    237 
    238 void dvmCompilerAbort(CompilationUnit *cUnit);
    239 
    240 /* Debug Utilities */
    241 void dvmCompilerDumpCompilationUnit(CompilationUnit *cUnit);
    242 
    243 #endif /* _DALVIK_VM_COMPILER_IR */
    244