类SsaBuilder的作用： 将一个graph转变成SSA形式。该转化的liveness guarantees在下面列出。dex register被杀意味着代码中某个给定位置的值在其environment use中不再可用。下文中的merge被具化成HPhi。 (a)不需要merge的dex registers（即在一个join block，他们没有不同的值）在所有的environment use中都是可用的。注意：这不意味着在register allocation之后instruction将会有一个physical location。参见SsaLivenessAnalysis部分。 (b)需要merge且merge会带来不相容类型的dex registers将会被杀掉，为了该merge的environment use。 (c)当debuggable 标记被传到compiler后，需要merg且在merge后有一个proper type的dex registers，对所有的environment use都是可用的。如果debuggable 标记没有被设置，仅被environment使用的dex register的value会被杀掉。
class SsaLivenessAnalysis的作用： 计算instruction的liveness的分析。 (a)instruction的non-environment use会使得这个instruction live (b)类型是object(即非primitive类型)的instruction的environment use会使得instruction live。这是由于必须使得有finalizers（对象被删除时要调用的）来删除native objects的objects保持alive（因为对象的删除是由虚拟机的垃圾收集器完成的,时间不确定,所以调用finalizer的时间也是不确定的）。 (c)当一个graph有debuggable这个属性时，有primitive类型的instruction的environment use似的instruction live。如果graph没有debuggable属性，environment use没有任何作用，而且可能在register allocation后得到一个’none’ value。 (b)(c)是通过SsaLivenessAnalysis::ShouldBeLiveForEnvironment来实现的。
class LiveRange的作用： live range包含一个instruction或者一个temporary live的start和end。还含有LiveRange* next_;
class LiveInterval的作用： interval是一个instruction live的不重合的live range的链表。每个有use的instruction都有一个interval。
class UsePosition的作用： use position代表着在一个给定position的live interval use。
160 private: 161 HInstruction* const user_; 162 HEnvironment* const environment_; 163 const size_t input_index_; 164 const size_t position_; 165 UsePosition* next_; 231 void SsaBuilder::BuildSsa() { 232 // 1) Visit in reverse post order. We need to have all predecessors of a block visited 233 // (with the exception of loops) in order to create the right environment for that 234 // block. For loops, we create phis whose inputs will be set in 2). 235 for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { 236 VisitBasicBlock(it.Current()); 237 } 238 239 // 2) Set inputs of loop phis. 240 for (size_t i = 0; i < loop_headers_.Size(); i++) { 241 HBasicBlock* block = loop_headers_.Get(i); 242 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 243 HPhi* phi = it.Current()->AsPhi(); 244 for (size_t pred = 0; pred < block->GetPredecessors().Size(); pred++) { 245 HInstruction* input = ValueOfLocal(block->GetPredecessors().Get(pred), phi->GetRegNumber()); 246 phi->AddInput(input); 247 } 248 } 249 } 250 251 // 3) Mark dead phis. This will mark phis that are only used by environments: 252 // at the DEX level, the type of these phis does not need to be consistent, but 253 // our code generator will complain if the inputs of a phi do not have the same 254 // type. The marking allows the type propagation to know which phis it needs 255 // to handle. We mark but do not eliminate: the elimination will be done in 256 // step 9). 257 SsaDeadPhiElimination dead_phis_for_type_propagation(GetGraph()); 258 dead_phis_for_type_propagation.MarkDeadPhis(); 259 260 // 4) Propagate types of phis. At this point, phis are typed void in the general 261 // case, or float/double/reference when we created an equivalent phi. So we 262 // need to propagate the types across phis to give them a correct type. 263 PrimitiveTypePropagation type_propagation(GetGraph()); 264 type_propagation.Run(); 265 266 // 5) When creating equivalent phis we copy the inputs of the original phi which 267 // may be improperly typed. This was fixed during the type propagation in 4) but 268 // as a result we may end up with two equivalent phis with the same type for 269 // the same dex register. This pass cleans them up. 270 EquivalentPhisCleanup(); 271 272 // 6) Mark dead phis again. Step 4) may have introduced new phis. 273 // Step 5) might enable the death of new phis. 274 SsaDeadPhiElimination dead_phis(GetGraph()); 275 dead_phis.MarkDeadPhis(); 276 277 // 7) Now that the graph is correctly typed, we can get rid of redundant phis. 278 // Note that we cannot do this phase before type propagation, otherwise 279 // we could get rid of phi equivalents, whose presence is a requirement for the 280 // type propagation phase. Note that this is to satisfy statement (a) of the 281 // SsaBuilder (see ssa_builder.h). 282 SsaRedundantPhiElimination redundant_phi(GetGraph()); 283 redundant_phi.Run(); 284 285 // 8) Fix the type for null constants which are part of an equality comparison. 286 // We need to do this after redundant phi elimination, to ensure the only cases 287 // that we can see are reference comparison against 0. The redundant phi 288 // elimination ensures we do not see a phi taking two 0 constants in a HEqual 289 // or HNotEqual. 290 FixNullConstantType(); 291 292 // 9) Make sure environments use the right phi "equivalent": a phi marked dead 293 // can have a phi equivalent that is not dead. We must therefore update 294 // all environment uses of the dead phi to use its equivalent. Note that there 295 // can be multiple phis for the same Dex register that are live (for example 296 // when merging constants), in which case it is OK for the environments 297 // to just reference one. 298 for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { 299 HBasicBlock* block = it.Current(); 300 for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) { 301 HPhi* phi = it_phis.Current()->AsPhi(); 302 // If the phi is not dead, or has no environment uses, there is nothing to do. 303 if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue; 304 HInstruction* next = phi->GetNext(); 305 if (!IsPhiEquivalentOf(next, phi)) continue; 306 if (next->AsPhi()->IsDead()) { 307 // If the phi equivalent is dead, check if there is another one. 308 next = next->GetNext(); 309 if (!IsPhiEquivalentOf(next, phi)) continue; 310 // There can be at most two phi equivalents. 311 DCHECK(!IsPhiEquivalentOf(next->GetNext(), phi)); 312 if (next->AsPhi()->IsDead()) continue; 313 } 314 // We found a live phi equivalent. Update the environment uses of `phi` with it. 315 phi->ReplaceWith(next); 316 } 317 } 318 319 // 10) Deal with phis to guarantee liveness of phis in case of a debuggable 320 // application. This is for satisfying statement (c) of the SsaBuilder 321 // (see ssa_builder.h). 322 if (GetGraph()->IsDebuggable()) { 323 DeadPhiHandling dead_phi_handler(GetGraph()); 324 dead_phi_handler.Run(); 325 } 326 327 // 11) Now that the right phis are used for the environments, and we 328 // have potentially revive dead phis in case of a debuggable application, 329 // we can eliminate phis we do not need. Regardless of the debuggable status, 330 // this phase is necessary for statement (b) of the SsaBuilder (see ssa_builder.h), 331 // as well as for the code generation, which does not deal with phis of conflicting 332 // input types. 333 dead_phis.EliminateDeadPhis(); 334 335 // 12) Clear locals. 336 for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions()); 337 !it.Done(); 338 it.Advance()) { 339 HInstruction* current = it.Current(); 340 if (current->IsLocal()) { 341 current->GetBlock()->RemoveInstruction(current); 342 } 343 } 344 }待续
