1 /*
2  * Copyright (C) 2016 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 ART_COMPILER_OPTIMIZING_BLOCK_BUILDER_H_
18 #define ART_COMPILER_OPTIMIZING_BLOCK_BUILDER_H_
19 
20 #include "base/scoped_arena_allocator.h"
21 #include "base/scoped_arena_containers.h"
22 #include "dex/code_item_accessors.h"
23 #include "dex/dex_file.h"
24 #include "nodes.h"
25 
26 namespace art {
27 
28 class HBasicBlockBuilder : public ValueObject {
29  public:
30   HBasicBlockBuilder(HGraph* graph,
31                      const DexFile* const dex_file,
32                      const CodeItemDebugInfoAccessor& accessor,
33                      ScopedArenaAllocator* local_allocator);
34 
35   // Creates basic blocks in `graph_` at branch target dex_pc positions of the
36   // `code_item_`. Blocks are connected but left unpopulated with instructions.
37   // TryBoundary blocks are inserted at positions where control-flow enters/
38   // exits a try block.
39   bool Build();
40 
41   // Creates basic blocks in `graph_` for compiling an intrinsic.
42   void BuildIntrinsic();
43 
GetNumberOfBranches()44   size_t GetNumberOfBranches() const { return number_of_branches_; }
GetBlockAt(uint32_t dex_pc)45   HBasicBlock* GetBlockAt(uint32_t dex_pc) const { return branch_targets_[dex_pc]; }
46 
47   size_t GetQuickenIndex(uint32_t dex_pc) const;
48 
49  private:
50   // Creates a basic block starting at given `dex_pc`.
51   HBasicBlock* MaybeCreateBlockAt(uint32_t dex_pc);
52 
53   // Creates a basic block for bytecode instructions at `semantic_dex_pc` and
54   // stores it under the `store_dex_pc` key. This is used when multiple blocks
55   // share the same semantic dex_pc, e.g. when building switch decision trees.
56   HBasicBlock* MaybeCreateBlockAt(uint32_t semantic_dex_pc, uint32_t store_dex_pc);
57 
58   bool CreateBranchTargets();
59   void ConnectBasicBlocks();
60   void InsertTryBoundaryBlocks();
61 
62   // To ensure branches with negative offsets can always OSR jump to compiled
63   // code, we insert synthesized loops before each block that is the target of a
64   // negative branch.
65   void InsertSynthesizedLoopsForOsr();
66 
67   // Helper method which decides whether `catch_block` may have live normal
68   // predecessors and thus whether a synthetic catch block needs to be created
69   // to avoid mixing normal and exceptional predecessors.
70   // Should only be called during InsertTryBoundaryBlocks on blocks at catch
71   // handler dex_pcs.
72   bool MightHaveLiveNormalPredecessors(HBasicBlock* catch_block);
73 
74   ArenaAllocator* const allocator_;
75   HGraph* const graph_;
76 
77   const DexFile* const dex_file_;
78   CodeItemDataAccessor code_item_accessor_;  // null code item for intrinsic graph.
79 
80   ScopedArenaAllocator* const local_allocator_;
81   ScopedArenaVector<HBasicBlock*> branch_targets_;
82   ScopedArenaVector<HBasicBlock*> throwing_blocks_;
83   size_t number_of_branches_;
84 
85   // A table to quickly find the quicken index for the first instruction of a basic block.
86   ScopedArenaSafeMap<uint32_t, uint32_t> quicken_index_for_dex_pc_;
87 
88   static constexpr size_t kDefaultNumberOfThrowingBlocks = 2u;
89 
90   DISALLOW_COPY_AND_ASSIGN(HBasicBlockBuilder);
91 };
92 
93 }  // namespace art
94 
95 #endif  // ART_COMPILER_OPTIMIZING_BLOCK_BUILDER_H_
96