src/compiler/dex/mir_graph.h

/*
 * Copyright (C) 2013 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef ART_SRC_COMPILER_DEX_MIRGRAPH_H_
#define ART_SRC_COMPILER_DEX_MIRGRAPH_H_

#include "dex_file.h"
#include "dex_instruction.h"
#include "compiler_ir.h"

namespace art {

enum DataFlowAttributePos {
  kUA = 0,
  kUB,
  kUC,
  kAWide,
  kBWide,
  kCWide,
  kDA,
  kIsMove,
  kSetsConst,
  kFormat35c,
  kFormat3rc,
  kNullCheckSrc0,        // Null check of uses[0].
  kNullCheckSrc1,        // Null check of uses[1].
  kNullCheckSrc2,        // Null check of uses[2].
  kNullCheckOut0,        // Null check out outgoing arg0.
  kDstNonNull,           // May assume dst is non-null.
  kRetNonNull,           // May assume retval is non-null.
  kNullTransferSrc0,     // Object copy src[0] -> dst.
  kNullTransferSrcN,     // Phi null check state transfer.
  kRangeCheckSrc1,       // Range check of uses[1].
  kRangeCheckSrc2,       // Range check of uses[2].
  kRangeCheckSrc3,       // Range check of uses[3].
  kFPA,
  kFPB,
  kFPC,
  kCoreA,
  kCoreB,
  kCoreC,
  kRefA,
  kRefB,
  kRefC,
  kUsesMethodStar,       // Implicit use of Method*.
};

#define DF_NOP                  0
#define DF_UA                   (1 << kUA)
#define DF_UB                   (1 << kUB)
#define DF_UC                   (1 << kUC)
#define DF_A_WIDE               (1 << kAWide)
#define DF_B_WIDE               (1 << kBWide)
#define DF_C_WIDE               (1 << kCWide)
#define DF_DA                   (1 << kDA)
#define DF_IS_MOVE              (1 << kIsMove)
#define DF_SETS_CONST           (1 << kSetsConst)
#define DF_FORMAT_35C           (1 << kFormat35c)
#define DF_FORMAT_3RC           (1 << kFormat3rc)
#define DF_NULL_CHK_0           (1 << kNullCheckSrc0)
#define DF_NULL_CHK_1           (1 << kNullCheckSrc1)
#define DF_NULL_CHK_2           (1 << kNullCheckSrc2)
#define DF_NULL_CHK_OUT0        (1 << kNullCheckOut0)
#define DF_NON_NULL_DST         (1 << kDstNonNull)
#define DF_NON_NULL_RET         (1 << kRetNonNull)
#define DF_NULL_TRANSFER_0      (1 << kNullTransferSrc0)
#define DF_NULL_TRANSFER_N      (1 << kNullTransferSrcN)
#define DF_RANGE_CHK_1          (1 << kRangeCheckSrc1)
#define DF_RANGE_CHK_2          (1 << kRangeCheckSrc2)
#define DF_RANGE_CHK_3          (1 << kRangeCheckSrc3)
#define DF_FP_A                 (1 << kFPA)
#define DF_FP_B                 (1 << kFPB)
#define DF_FP_C                 (1 << kFPC)
#define DF_CORE_A               (1 << kCoreA)
#define DF_CORE_B               (1 << kCoreB)
#define DF_CORE_C               (1 << kCoreC)
#define DF_REF_A                (1 << kRefA)
#define DF_REF_B                (1 << kRefB)
#define DF_REF_C                (1 << kRefC)
#define DF_UMS                  (1 << kUsesMethodStar)

#define DF_HAS_USES             (DF_UA | DF_UB | DF_UC)

#define DF_HAS_DEFS             (DF_DA)

#define DF_HAS_NULL_CHKS        (DF_NULL_CHK_0 | \
                                 DF_NULL_CHK_1 | \
                                 DF_NULL_CHK_2 | \
                                 DF_NULL_CHK_OUT0)

#define DF_HAS_RANGE_CHKS       (DF_RANGE_CHK_1 | \
                                 DF_RANGE_CHK_2 | \
                                 DF_RANGE_CHK_3)

#define DF_HAS_NR_CHKS          (DF_HAS_NULL_CHKS | \
                                 DF_HAS_RANGE_CHKS)

#define DF_A_IS_REG             (DF_UA | DF_DA)
#define DF_B_IS_REG             (DF_UB)
#define DF_C_IS_REG             (DF_UC)
#define DF_IS_GETTER_OR_SETTER  (DF_IS_GETTER | DF_IS_SETTER)
#define DF_USES_FP              (DF_FP_A | DF_FP_B | DF_FP_C)

extern const int oat_data_flow_attributes[kMirOpLast];

class MIRGraph {
  public:
    MIRGraph(CompilationUnit* cu);
    ~MIRGraph() {}

    /*
     * Parse dex method and add MIR at current insert point.  Returns id (which is
     * actually the index of the method in the m_units_ array).
     */
    void InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags,
                      InvokeType invoke_type, uint32_t class_def_idx,
                      uint32_t method_idx, jobject class_loader, const DexFile& dex_file);

    /* Find existing block */
    BasicBlock* FindBlock(unsigned int code_offset)
    {
      return FindBlock(code_offset, false, false, NULL);
    }

    const uint16_t* GetCurrentInsns()
    {
      return current_code_item_->insns_;
    }

    const uint16_t* GetInsns(int m_unit_index)
    {
      return m_units_[m_unit_index]->GetCodeItem()->insns_;
    }

    int GetNumBlocks()
    {
      return num_blocks_;
    }

    ArenaBitVector* GetTryBlockAddr()
    {
      return try_block_addr_;
    }

    BasicBlock* GetEntryBlock()
    {
      return entry_block_;
    }

    BasicBlock* GetExitBlock()
    {
      return exit_block_;
    }

    GrowableListIterator GetBasicBlockIterator()
    {
      GrowableListIterator iterator;
      GrowableListIteratorInit(&block_list_, &iterator);
      return iterator;
    }

    BasicBlock* GetBasicBlock(int block_id)
    {
      return reinterpret_cast<BasicBlock*>(GrowableListGetElement(&block_list_, block_id));
    }

    size_t GetBasicBlockListCount()
    {
      return block_list_.num_used;
    }

    GrowableList* GetBlockList()
    {
      return &block_list_;
    }

    GrowableList* GetDfsOrder()
    {
      return &dfs_order_;
    }

    GrowableList* GetDfsPostOrder()
    {
      return &dfs_post_order_;
    }

    GrowableList* GetDomPostOrder()
    {
      return &dom_post_order_traversal_;
    }

    GrowableList* GetSSASubscripts()
    {
      return ssa_subscripts_;
    }

    int GetDefCount()
    {
      return def_count_;
    }

    void EnableOpcodeCounting()
    {
      opcode_count_ = static_cast<int*>(NewMem(cu_, kNumPackedOpcodes * sizeof(int), true,
                                        kAllocMisc));
    }

    void ShowOpcodeStats();

    DexCompilationUnit* GetCurrentDexCompilationUnit()
    {
      return m_units_[current_method_];
    }

    void DumpCFG(const char* dir_prefix, bool all_blocks);

    void BuildRegLocations();

    void DumpRegLocTable(RegLocation* table, int count);

    int ComputeFrameSize();

    void BasicBlockOptimization();

    bool IsConst(int32_t s_reg)
    {
      return (IsBitSet(is_constant_v_, s_reg));
    }

    bool IsConst(RegLocation loc)
    {
      return (IsConst(loc.orig_sreg));
    }

    int32_t ConstantValue(RegLocation loc)
    {
      DCHECK(IsConst(loc));
      return constant_values_[loc.orig_sreg];
    }

    int32_t ConstantValue(int32_t s_reg)
    {
      DCHECK(IsConst(s_reg));
      return constant_values_[s_reg];
    }

    int64_t ConstantValueWide(RegLocation loc)
    {
      DCHECK(IsConst(loc));
      return (static_cast<int64_t>(constant_values_[loc.orig_sreg + 1]) << 32) |
          Low32Bits(static_cast<int64_t>(constant_values_[loc.orig_sreg]));
    }

    bool IsConstantNullRef(RegLocation loc)
    {
      return loc.ref && loc.is_const && (ConstantValue(loc) == 0);
    }

    int GetNumSSARegs()
    {
      return num_ssa_regs_;
    }

    void SetNumSSARegs(int new_num)
    {
      num_ssa_regs_ = new_num;
    }

    int GetNumReachableBlocks()
    {
      return num_reachable_blocks_;
    }

    int GetUseCount(int vreg)
    {
      return GrowableListGetElement(&use_counts_, vreg);
    }

    int GetRawUseCount(int vreg)
    {
      return GrowableListGetElement(&raw_use_counts_, vreg);
    }

    int GetSSASubscript(int ssa_reg)
    {
      return GrowableListGetElement(ssa_subscripts_, ssa_reg);
    }

    const char* GetSSAString(int ssa_reg)
    {
      return GET_ELEM_N(ssa_strings_, char*, ssa_reg);
    }

    void BasicBlockCombine();
    void CodeLayout();
    void DumpCheckStats();
    void PropagateConstants();
    MIR* FindMoveResult(BasicBlock* bb, MIR* mir);
    int SRegToVReg(int ssa_reg);
    void VerifyDataflow();
    void MethodUseCount();
    void SSATransformation();
    void CheckForDominanceFrontier(BasicBlock* dom_bb, const BasicBlock* succ_bb);
    void NullCheckElimination();

    /*
     * IsDebugBuild sanity check: keep track of the Dex PCs for catch entries so that later on
     * we can verify that all catch entries have native PC entries.
     */
    std::set<uint32_t> catches_;

  private:

    int FindCommonParent(int block1, int block2);
    void ComputeSuccLineIn(ArenaBitVector* dest, const ArenaBitVector* src1,
                           const ArenaBitVector* src2);
    void HandleLiveInUse(ArenaBitVector* use_v, ArenaBitVector* def_v,
                                ArenaBitVector* live_in_v, int dalvik_reg_id);
    void HandleDef(ArenaBitVector* def_v, int dalvik_reg_id);
    void CompilerInitializeSSAConversion();
    bool DoSSAConversion(BasicBlock* bb);
    bool InvokeUsesMethodStar(MIR* mir);
    int ParseInsn(const uint16_t* code_ptr, DecodedInstruction* decoded_instruction);
    bool ContentIsInsn(const uint16_t* code_ptr);
    BasicBlock* SplitBlock(unsigned int code_offset, BasicBlock* orig_block,
                           BasicBlock** immed_pred_block_p);
    BasicBlock* FindBlock(unsigned int code_offset, bool split, bool create,
                          BasicBlock** immed_pred_block_p);
    void ProcessTryCatchBlocks();
    BasicBlock* ProcessCanBranch(BasicBlock* cur_block, MIR* insn, int cur_offset, int width,
                                 int flags, const uint16_t* code_ptr, const uint16_t* code_end);
    void ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, int cur_offset, int width, int flags);
    BasicBlock* ProcessCanThrow(BasicBlock* cur_block, MIR* insn, int cur_offset, int width,
                                int flags, ArenaBitVector* try_block_addr, const uint16_t* code_ptr,
                                const uint16_t* code_end);
    int AddNewSReg(int v_reg);
    void HandleSSAUse(int* uses, int dalvik_reg, int reg_index);
    void HandleSSADef(int* defs, int dalvik_reg, int reg_index);
    void DataFlowSSAFormat35C(MIR* mir);
    void DataFlowSSAFormat3RC(MIR* mir);
    bool FindLocalLiveIn(BasicBlock* bb);
    bool ClearVisitedFlag(struct BasicBlock* bb);
    bool CountUses(struct BasicBlock* bb);
    bool InferTypeAndSize(BasicBlock* bb);
    bool VerifyPredInfo(BasicBlock* bb);
    BasicBlock* NeedsVisit(BasicBlock* bb);
    BasicBlock* NextUnvisitedSuccessor(BasicBlock* bb);
    void MarkPreOrder(BasicBlock* bb);
    void RecordDFSOrders(BasicBlock* bb);
    void ComputeDFSOrders();
    void ComputeDefBlockMatrix();
    void ComputeDomPostOrderTraversal(BasicBlock* bb);
    void ComputeDominators();
    void InsertPhiNodes();
    void DoDFSPreOrderSSARename(BasicBlock* block);
    void SetConstant(int32_t ssa_reg, int value);
    void SetConstantWide(int ssa_reg, int64_t value);
    int GetSSAUseCount(int s_reg);
    bool BasicBlockOpt(BasicBlock* bb);
    bool EliminateNullChecks(BasicBlock* bb);
    bool NullCheckEliminationInit(BasicBlock* bb);
    bool BuildExtendedBBList(struct BasicBlock* bb);
    bool FillDefBlockMatrix(BasicBlock* bb);
    bool InitializeDominationInfo(BasicBlock* bb);
    bool ComputeblockIDom(BasicBlock* bb);
    bool ComputeBlockDominators(BasicBlock* bb);
    bool SetDominators(BasicBlock* bb);
    bool ComputeBlockLiveIns(BasicBlock* bb);
    bool InsertPhiNodeOperands(BasicBlock* bb);
    bool ComputeDominanceFrontier(BasicBlock* bb);
    bool DoConstantPropogation(BasicBlock* bb);
    bool CountChecks(BasicBlock* bb);
    bool CombineBlocks(BasicBlock* bb);

    CompilationUnit* cu_;
    GrowableList* ssa_base_vregs_;
    GrowableList* ssa_subscripts_;
    GrowableList* ssa_strings_;
    // Map original Dalvik virtual reg i to the current SSA name.
    int* vreg_to_ssa_map_;            // length == method->registers_size
    int* ssa_last_defs_;              // length == method->registers_size
    ArenaBitVector* is_constant_v_;   // length == num_ssa_reg
    int* constant_values_;            // length == num_ssa_reg
    // Use counts of ssa names.
    GrowableList use_counts_;         // Weighted by nesting depth
    GrowableList raw_use_counts_;     // Not weighted
    int num_reachable_blocks_;
    GrowableList dfs_order_;
    GrowableList dfs_post_order_;
    GrowableList dom_post_order_traversal_;
    int* i_dom_list_;
    ArenaBitVector** def_block_matrix_;    // num_dalvik_register x num_blocks.
    ArenaBitVector* temp_block_v_;
    ArenaBitVector* temp_dalvik_register_v_;
    ArenaBitVector* temp_ssa_register_v_;  // num_ssa_regs.
    static const int kInvalidEntry = -1;
    GrowableList block_list_;
    ArenaBitVector* try_block_addr_;
    BasicBlock* entry_block_;
    BasicBlock* exit_block_;
    BasicBlock* cur_block_;
    int num_blocks_;
    const DexFile::CodeItem* current_code_item_;
    SafeMap<unsigned int, BasicBlock*> block_map_; // FindBlock lookup cache.
    std::vector<DexCompilationUnit*> m_units_;     // List of methods included in this graph
    typedef std::pair<int, int> MIRLocation;       // Insert point, (m_unit_ index, offset)
    std::vector<MIRLocation> method_stack_;        // Include stack
    int current_method_;
    int current_offset_;
    int def_count_;                                // Used to estimate size of ssa name storage.
    int* opcode_count_;                            // Dex opcode coverage stats.
    int num_ssa_regs_;                             // Number of names following SSA transformation.
    std::vector<BasicBlock*> extended_basic_blocks_; // Heads of block "traces".
};

}  // namespace art

#endif // ART_SRC_COMPILER_DEX_MIRGRAPH_H_