Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2014 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_SSA_BUILDER_H_ |
| 18 | #define ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_ |
| 19 | |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame^] | 20 | #include "base/arena_containers.h" |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 21 | #include "nodes.h" |
Nicolas Geoffray | 3159674 | 2014-11-24 15:28:45 +0000 | [diff] [blame] | 22 | #include "optimization.h" |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 23 | |
| 24 | namespace art { |
| 25 | |
| 26 | static constexpr int kDefaultNumberOfLoops = 2; |
| 27 | |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 28 | /** |
| 29 | * Transforms a graph into SSA form. The liveness guarantees of |
| 30 | * this transformation are listed below. A DEX register |
| 31 | * being killed means its value at a given position in the code |
| 32 | * will not be available to its environment uses. A merge in the |
| 33 | * following text is materialized as a `HPhi`. |
| 34 | * |
| 35 | * (a) Dex registers that do not require merging (that is, they do not |
| 36 | * have different values at a join block) are available to all their |
Nicolas Geoffray | 915b9d0 | 2015-03-11 15:11:19 +0000 | [diff] [blame] | 37 | * environment uses. Note that it does not imply the instruction will |
| 38 | * have a physical location after register allocation. See the |
| 39 | * SsaLivenessAnalysis phase. |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 40 | * |
| 41 | * (b) Dex registers that require merging, and the merging gives |
| 42 | * incompatible types, will be killed for environment uses of that merge. |
| 43 | * |
| 44 | * (c) When the `debuggable` flag is passed to the compiler, Dex registers |
| 45 | * that require merging and have a proper type after the merge, are |
| 46 | * available to all their environment uses. If the `debuggable` flag |
| 47 | * is not set, values of Dex registers only used by environments |
| 48 | * are killed. |
| 49 | */ |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 50 | class SsaBuilder : public HGraphVisitor { |
| 51 | public: |
| 52 | explicit SsaBuilder(HGraph* graph) |
| 53 | : HGraphVisitor(graph), |
| 54 | current_locals_(nullptr), |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame^] | 55 | loop_headers_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), |
| 56 | locals_for_(graph->GetBlocks().size(), |
| 57 | ArenaVector<HInstruction*>(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), |
| 58 | graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) { |
| 59 | loop_headers_.reserve(kDefaultNumberOfLoops); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 60 | } |
| 61 | |
| 62 | void BuildSsa(); |
| 63 | |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame^] | 64 | ArenaVector<HInstruction*>* GetLocalsFor(HBasicBlock* block) { |
| 65 | DCHECK_LT(block->GetBlockId(), locals_for_.size()); |
| 66 | ArenaVector<HInstruction*>* locals = &locals_for_[block->GetBlockId()]; |
| 67 | if (locals->empty() && GetGraph()->GetNumberOfVRegs() != 0u) { |
David Brazdil | ffee3d3 | 2015-07-06 11:48:53 +0100 | [diff] [blame] | 68 | const size_t vregs = GetGraph()->GetNumberOfVRegs(); |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame^] | 69 | locals->resize(vregs, nullptr); |
David Brazdil | ffee3d3 | 2015-07-06 11:48:53 +0100 | [diff] [blame] | 70 | |
| 71 | if (block->IsCatchBlock()) { |
| 72 | // We record incoming inputs of catch phis at throwing instructions and |
| 73 | // must therefore eagerly create the phis. Unused phis will be removed |
| 74 | // in the dead phi analysis. |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame^] | 75 | ArenaAllocator* arena = GetGraph()->GetArena(); |
David Brazdil | ffee3d3 | 2015-07-06 11:48:53 +0100 | [diff] [blame] | 76 | for (size_t i = 0; i < vregs; ++i) { |
| 77 | HPhi* phi = new (arena) HPhi(arena, i, 0, Primitive::kPrimVoid); |
| 78 | block->AddPhi(phi); |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame^] | 79 | (*locals)[i] = phi; |
David Brazdil | ffee3d3 | 2015-07-06 11:48:53 +0100 | [diff] [blame] | 80 | } |
| 81 | } |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 82 | } |
Nicolas Geoffray | 8c0c91a | 2015-05-07 11:46:05 +0100 | [diff] [blame] | 83 | return locals; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 84 | } |
| 85 | |
| 86 | HInstruction* ValueOfLocal(HBasicBlock* block, size_t local); |
| 87 | |
| 88 | void VisitBasicBlock(HBasicBlock* block); |
| 89 | void VisitLoadLocal(HLoadLocal* load); |
| 90 | void VisitStoreLocal(HStoreLocal* store); |
| 91 | void VisitInstruction(HInstruction* instruction); |
Nicolas Geoffray | 421e9f9 | 2014-11-11 18:21:53 +0000 | [diff] [blame] | 92 | void VisitTemporary(HTemporary* instruction); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 93 | |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 94 | static HInstruction* GetFloatOrDoubleEquivalent(HInstruction* user, |
| 95 | HInstruction* instruction, |
| 96 | Primitive::Type type); |
| 97 | |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 98 | static HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction); |
| 99 | |
Andreas Gampe | 7c3952f | 2015-02-19 18:21:24 -0800 | [diff] [blame] | 100 | static constexpr const char* kSsaBuilderPassName = "ssa_builder"; |
| 101 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 102 | private: |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 103 | void FixNullConstantType(); |
| 104 | void EquivalentPhisCleanup(); |
| 105 | |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 106 | static HFloatConstant* GetFloatEquivalent(HIntConstant* constant); |
| 107 | static HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant); |
| 108 | static HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type); |
| 109 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 110 | // Locals for the current block being visited. |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame^] | 111 | ArenaVector<HInstruction*>* current_locals_; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 112 | |
| 113 | // Keep track of loop headers found. The last phase of the analysis iterates |
| 114 | // over these blocks to set the inputs of their phis. |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame^] | 115 | ArenaVector<HBasicBlock*> loop_headers_; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 116 | |
| 117 | // HEnvironment for each block. |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame^] | 118 | ArenaVector<ArenaVector<HInstruction*>> locals_for_; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 119 | |
| 120 | DISALLOW_COPY_AND_ASSIGN(SsaBuilder); |
| 121 | }; |
| 122 | |
| 123 | } // namespace art |
| 124 | |
| 125 | #endif // ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_ |