diff options
author | Nicolas Geoffray <ngeoffray@google.com> | 2014-06-09 14:06:02 +0100 |
---|---|---|
committer | Nicolas Geoffray <ngeoffray@google.com> | 2014-06-09 14:06:02 +0100 |
commit | 184d640d2a3ac86d871dab58386a50cc9bb973f9 (patch) | |
tree | 4880a8790937e57de955b38cda06404f7a105a0f /compiler/optimizing/ssa_type_propagation.cc | |
parent | fbc2b1747e7e3d06f214f801f53218a1d4bf2dbe (diff) | |
download | art-184d640d2a3ac86d871dab58386a50cc9bb973f9.zip art-184d640d2a3ac86d871dab58386a50cc9bb973f9.tar.gz art-184d640d2a3ac86d871dab58386a50cc9bb973f9.tar.bz2 |
Add a type propagation phase after building SSA.
This ensures all phis have a type.
Change-Id: I7e4f9a16d1efb5f64c493c1351749b352c870cbd
Diffstat (limited to 'compiler/optimizing/ssa_type_propagation.cc')
-rw-r--r-- | compiler/optimizing/ssa_type_propagation.cc | 97 |
1 files changed, 97 insertions, 0 deletions
diff --git a/compiler/optimizing/ssa_type_propagation.cc b/compiler/optimizing/ssa_type_propagation.cc new file mode 100644 index 0000000..53fa74e --- /dev/null +++ b/compiler/optimizing/ssa_type_propagation.cc @@ -0,0 +1,97 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "ssa_type_propagation.h" + +#include "nodes.h" + +namespace art { + +static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_type) { + // We trust the verifier has already done the necessary checking. + switch (existing) { + case Primitive::kPrimFloat: + case Primitive::kPrimDouble: + case Primitive::kPrimNot: + return existing; + default: + return new_type; + } +} + +// Re-compute and update the type of the instruction. Returns +// whether or not the type was changed. +static bool UpdateType(HPhi* phi) { + Primitive::Type existing = phi->GetType(); + + Primitive::Type new_type = Primitive::kPrimVoid; + for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { + Primitive::Type input_type = phi->InputAt(i)->GetType(); + new_type = MergeTypes(new_type, input_type); + } + phi->SetType(new_type); + return existing != new_type; +} + +void SsaTypePropagation::Run() { + for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { + VisitBasicBlock(it.Current()); + } + ProcessWorklist(); +} + +void SsaTypePropagation::VisitBasicBlock(HBasicBlock* block) { + if (block->IsLoopHeader()) { + for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + HPhi* phi = it.Current()->AsPhi(); + // Set the initial type for the phi. Use the non back edge input for reaching + // a fixed point faster. + phi->SetType(phi->InputAt(0)->GetType()); + AddToWorklist(phi); + } + } else { + for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + HPhi* phi = it.Current()->AsPhi(); + if (UpdateType(phi)) { + AddDependentInstructionsToWorklist(phi); + } + } + } +} + +void SsaTypePropagation::ProcessWorklist() { + while (!worklist_.IsEmpty()) { + HPhi* instruction = worklist_.Pop(); + if (UpdateType(instruction)) { + AddDependentInstructionsToWorklist(instruction); + } + } +} + +void SsaTypePropagation::AddToWorklist(HPhi* instruction) { + worklist_.Add(instruction); +} + +void SsaTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) { + for (HUseIterator<HInstruction> it(instruction->GetUses()); !it.Done(); it.Advance()) { + HPhi* phi = it.Current()->GetUser()->AsPhi(); + if (phi != nullptr) { + AddToWorklist(phi); + } + } +} + +} // namespace art |