ssa_builder.cc revision 421e9f9088b51e9680a3dfcae6965fc1854d3ee4
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#include "ssa_builder.h" 18 19#include "nodes.h" 20#include "ssa_type_propagation.h" 21 22namespace art { 23 24void SsaBuilder::BuildSsa() { 25 // 1) Visit in reverse post order. We need to have all predecessors of a block visited 26 // (with the exception of loops) in order to create the right environment for that 27 // block. For loops, we create phis whose inputs will be set in 2). 28 for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { 29 VisitBasicBlock(it.Current()); 30 } 31 32 // 2) Set inputs of loop phis. 33 for (size_t i = 0; i < loop_headers_.Size(); i++) { 34 HBasicBlock* block = loop_headers_.Get(i); 35 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 36 HPhi* phi = it.Current()->AsPhi(); 37 for (size_t pred = 0; pred < block->GetPredecessors().Size(); pred++) { 38 HInstruction* input = ValueOfLocal(block->GetPredecessors().Get(pred), phi->GetRegNumber()); 39 phi->AddInput(input); 40 } 41 } 42 } 43 44 // 3) Propagate types of phis. 45 SsaTypePropagation type_propagation(GetGraph()); 46 type_propagation.Run(); 47 48 // 4) Clear locals. 49 // TODO: Move this to a dead code eliminator phase. 50 for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions()); 51 !it.Done(); 52 it.Advance()) { 53 HInstruction* current = it.Current(); 54 if (current->IsLocal()) { 55 current->GetBlock()->RemoveInstruction(current); 56 } 57 } 58} 59 60HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) { 61 return GetLocalsFor(block)->Get(local); 62} 63 64void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { 65 current_locals_ = GetLocalsFor(block); 66 67 if (block->IsLoopHeader()) { 68 // If the block is a loop header, we know we only have visited the pre header 69 // because we are visiting in reverse post order. We create phis for all initialized 70 // locals from the pre header. Their inputs will be populated at the end of 71 // the analysis. 72 for (size_t local = 0; local < current_locals_->Size(); local++) { 73 HInstruction* incoming = ValueOfLocal(block->GetLoopInformation()->GetPreHeader(), local); 74 if (incoming != nullptr) { 75 HPhi* phi = new (GetGraph()->GetArena()) HPhi( 76 GetGraph()->GetArena(), local, 0, Primitive::kPrimVoid); 77 block->AddPhi(phi); 78 current_locals_->Put(local, phi); 79 } 80 } 81 // Save the loop header so that the last phase of the analysis knows which 82 // blocks need to be updated. 83 loop_headers_.Add(block); 84 } else if (block->GetPredecessors().Size() > 0) { 85 // All predecessors have already been visited because we are visiting in reverse post order. 86 // We merge the values of all locals, creating phis if those values differ. 87 for (size_t local = 0; local < current_locals_->Size(); local++) { 88 bool one_predecessor_has_no_value = false; 89 bool is_different = false; 90 HInstruction* value = ValueOfLocal(block->GetPredecessors().Get(0), local); 91 92 for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 93 HInstruction* current = ValueOfLocal(block->GetPredecessors().Get(i), local); 94 if (current == nullptr) { 95 one_predecessor_has_no_value = true; 96 break; 97 } else if (current != value) { 98 is_different = true; 99 } 100 } 101 102 if (one_predecessor_has_no_value) { 103 // If one predecessor has no value for this local, we trust the verifier has 104 // successfully checked that there is a store dominating any read after this block. 105 continue; 106 } 107 108 if (is_different) { 109 HPhi* phi = new (GetGraph()->GetArena()) HPhi( 110 GetGraph()->GetArena(), local, block->GetPredecessors().Size(), Primitive::kPrimVoid); 111 for (size_t i = 0; i < block->GetPredecessors().Size(); i++) { 112 HInstruction* pred_value = ValueOfLocal(block->GetPredecessors().Get(i), local); 113 phi->SetRawInputAt(i, pred_value); 114 } 115 block->AddPhi(phi); 116 value = phi; 117 } 118 current_locals_->Put(local, value); 119 } 120 } 121 122 // Visit all instructions. The instructions of interest are: 123 // - HLoadLocal: replace them with the current value of the local. 124 // - HStoreLocal: update current value of the local and remove the instruction. 125 // - Instructions that require an environment: populate their environment 126 // with the current values of the locals. 127 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 128 it.Current()->Accept(this); 129 } 130} 131 132/** 133 * Constants in the Dex format are not typed. So the builder types them as 134 * integers, but when doing the SSA form, we might realize the constant 135 * is used for floating point operations. We create a floating-point equivalent 136 * constant to make the operations correctly typed. 137 */ 138static HFloatConstant* GetFloatEquivalent(HIntConstant* constant) { 139 // We place the floating point constant next to this constant. 140 HFloatConstant* result = constant->GetNext()->AsFloatConstant(); 141 if (result == nullptr) { 142 HGraph* graph = constant->GetBlock()->GetGraph(); 143 ArenaAllocator* allocator = graph->GetArena(); 144 result = new (allocator) HFloatConstant(bit_cast<int32_t, float>(constant->GetValue())); 145 constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); 146 } else { 147 // If there is already a constant with the expected type, we know it is 148 // the floating point equivalent of this constant. 149 DCHECK_EQ((bit_cast<float, int32_t>(result->GetValue())), constant->GetValue()); 150 } 151 return result; 152} 153 154/** 155 * Wide constants in the Dex format are not typed. So the builder types them as 156 * longs, but when doing the SSA form, we might realize the constant 157 * is used for floating point operations. We create a floating-point equivalent 158 * constant to make the operations correctly typed. 159 */ 160static HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant) { 161 // We place the floating point constant next to this constant. 162 HDoubleConstant* result = constant->GetNext()->AsDoubleConstant(); 163 if (result == nullptr) { 164 HGraph* graph = constant->GetBlock()->GetGraph(); 165 ArenaAllocator* allocator = graph->GetArena(); 166 result = new (allocator) HDoubleConstant(bit_cast<int64_t, double>(constant->GetValue())); 167 constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); 168 } else { 169 // If there is already a constant with the expected type, we know it is 170 // the floating point equivalent of this constant. 171 DCHECK_EQ((bit_cast<double, int64_t>(result->GetValue())), constant->GetValue()); 172 } 173 return result; 174} 175 176/** 177 * Because of Dex format, we might end up having the same phi being 178 * used for non floating point operations and floating point operations. Because 179 * we want the graph to be correctly typed (and thereafter avoid moves between 180 * floating point registers and core registers), we need to create a copy of the 181 * phi with a floating point type. 182 */ 183static HPhi* GetFloatOrDoubleEquivalentOfPhi(HPhi* phi, Primitive::Type type) { 184 // We place the floating point phi next to this phi. 185 HInstruction* next = phi->GetNext(); 186 if (next == nullptr 187 || (next->GetType() != Primitive::kPrimDouble && next->GetType() != Primitive::kPrimFloat)) { 188 ArenaAllocator* allocator = phi->GetBlock()->GetGraph()->GetArena(); 189 HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type); 190 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 191 // Copy the inputs. Note that the graph may not be correctly typed by doing this copy, 192 // but the type propagation phase will fix it. 193 new_phi->SetRawInputAt(i, phi->InputAt(i)); 194 } 195 phi->GetBlock()->InsertPhiAfter(new_phi, phi); 196 return new_phi; 197 } else { 198 // If there is already a phi with the expected type, we know it is the floating 199 // point equivalent of this phi. 200 DCHECK_EQ(next->AsPhi()->GetRegNumber(), phi->GetRegNumber()); 201 return next->AsPhi(); 202 } 203} 204 205HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user, 206 HInstruction* value, 207 Primitive::Type type) { 208 if (value->IsArrayGet()) { 209 // The verifier has checked that values in arrays cannot be used for both 210 // floating point and non-floating point operations. It is therefore safe to just 211 // change the type of the operation. 212 value->AsArrayGet()->SetType(type); 213 return value; 214 } else if (value->IsLongConstant()) { 215 return GetDoubleEquivalent(value->AsLongConstant()); 216 } else if (value->IsIntConstant()) { 217 return GetFloatEquivalent(value->AsIntConstant()); 218 } else if (value->IsPhi()) { 219 return GetFloatOrDoubleEquivalentOfPhi(value->AsPhi(), type); 220 } else { 221 // For other instructions, we assume the verifier has checked that the dex format is correctly 222 // typed and the value in a dex register will not be used for both floating point and 223 // non-floating point operations. So the only reason an instruction would want a floating 224 // point equivalent is for an unused phi that will be removed by the dead phi elimination phase. 225 DCHECK(user->IsPhi()); 226 return value; 227 } 228} 229 230void SsaBuilder::VisitLoadLocal(HLoadLocal* load) { 231 HInstruction* value = current_locals_->Get(load->GetLocal()->GetRegNumber()); 232 if (load->GetType() != value->GetType() 233 && (load->GetType() == Primitive::kPrimFloat || load->GetType() == Primitive::kPrimDouble)) { 234 // If the operation requests a specific type, we make sure its input is of that type. 235 value = GetFloatOrDoubleEquivalent(load, value, load->GetType()); 236 } 237 load->ReplaceWith(value); 238 load->GetBlock()->RemoveInstruction(load); 239} 240 241void SsaBuilder::VisitStoreLocal(HStoreLocal* store) { 242 current_locals_->Put(store->GetLocal()->GetRegNumber(), store->InputAt(1)); 243 store->GetBlock()->RemoveInstruction(store); 244} 245 246void SsaBuilder::VisitInstruction(HInstruction* instruction) { 247 if (!instruction->NeedsEnvironment()) { 248 return; 249 } 250 HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment( 251 GetGraph()->GetArena(), current_locals_->Size()); 252 environment->Populate(*current_locals_); 253 instruction->SetEnvironment(environment); 254} 255 256void SsaBuilder::VisitTemporary(HTemporary* temp) { 257 // Temporaries are only used by the baseline register allocator. 258 temp->GetBlock()->RemoveInstruction(temp); 259} 260 261} // namespace art 262