Home | History | Annotate | Download | only in optimizing 
      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_type_propagation.h"
     18 
     19 #include "nodes.h"
     20 
     21 namespace art {
     22 
     23 static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_type) {
     24   // We trust the verifier has already done the necessary checking.
     25   switch (existing) {
     26     case Primitive::kPrimFloat:
     27     case Primitive::kPrimDouble:
     28     case Primitive::kPrimNot:
     29       return existing;
     30     default:
     31       return new_type;
     32   }
     33 }
     34 
     35 // Re-compute and update the type of the instruction. Returns
     36 // whether or not the type was changed.
     37 static bool UpdateType(HPhi* phi) {
     38   Primitive::Type existing = phi->GetType();
     39 
     40   Primitive::Type new_type = Primitive::kPrimVoid;
     41   for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
     42     Primitive::Type input_type = phi->InputAt(i)->GetType();
     43     new_type = MergeTypes(new_type, input_type);
     44   }
     45   phi->SetType(new_type);
     46   return existing != new_type;
     47 }
     48 
     49 void SsaTypePropagation::Run() {
     50   for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
     51     VisitBasicBlock(it.Current());
     52   }
     53   ProcessWorklist();
     54 }
     55 
     56 void SsaTypePropagation::VisitBasicBlock(HBasicBlock* block) {
     57   if (block->IsLoopHeader()) {
     58     for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
     59       HPhi* phi = it.Current()->AsPhi();
     60       // Set the initial type for the phi. Use the non back edge input for reaching
     61       // a fixed point faster.
     62       phi->SetType(phi->InputAt(0)->GetType());
     63       AddToWorklist(phi);
     64     }
     65   } else {
     66     for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
     67       HPhi* phi = it.Current()->AsPhi();
     68       if (UpdateType(phi)) {
     69         AddDependentInstructionsToWorklist(phi);
     70       }
     71     }
     72   }
     73 }
     74 
     75 void SsaTypePropagation::ProcessWorklist() {
     76   while (!worklist_.IsEmpty()) {
     77     HPhi* instruction = worklist_.Pop();
     78     if (UpdateType(instruction)) {
     79       AddDependentInstructionsToWorklist(instruction);
     80     }
     81   }
     82 }
     83 
     84 void SsaTypePropagation::AddToWorklist(HPhi* instruction) {
     85   worklist_.Add(instruction);
     86 }
     87 
     88 void SsaTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) {
     89   for (HUseIterator<HInstruction> it(instruction->GetUses()); !it.Done(); it.Advance()) {
     90     HPhi* phi = it.Current()->GetUser()->AsPhi();
     91     if (phi != nullptr) {
     92       AddToWorklist(phi);
     93     }
     94   }
     95 }
     96 
     97 }  // namespace art
     98