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