Chromium Code Reviews| OLD | NEW |
|---|---|
| 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 #include "vm/flow_graph_allocator.h" | 5 #include "vm/flow_graph_allocator.h" |
| 6 | 6 |
| 7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
| 8 #include "vm/intermediate_language.h" | 8 #include "vm/intermediate_language.h" |
| 9 #include "vm/il_printer.h" | 9 #include "vm/il_printer.h" |
| 10 #include "vm/flow_graph.h" | 10 #include "vm/flow_graph.h" |
| (...skipping 522 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 533 use = use->next(); | 533 use = use->next(); |
| 534 } | 534 } |
| 535 return true; | 535 return true; |
| 536 } | 536 } |
| 537 | 537 |
| 538 | 538 |
| 539 void FlowGraphAllocator::BuildLiveRanges() { | 539 void FlowGraphAllocator::BuildLiveRanges() { |
| 540 const intptr_t block_count = postorder_.length(); | 540 const intptr_t block_count = postorder_.length(); |
| 541 ASSERT(postorder_.Last()->IsGraphEntry()); | 541 ASSERT(postorder_.Last()->IsGraphEntry()); |
| 542 BitVector* current_interference_set = NULL; | 542 BitVector* current_interference_set = NULL; |
| 543 Isolate* isolate = flow_graph_.isolate(); | 543 Zone* zone = flow_graph_.zone(); |
| 544 for (intptr_t i = 0; i < (block_count - 1); i++) { | 544 for (intptr_t i = 0; i < (block_count - 1); i++) { |
| 545 BlockEntryInstr* block = postorder_[i]; | 545 BlockEntryInstr* block = postorder_[i]; |
| 546 | 546 |
| 547 BlockInfo* block_info = BlockInfoAt(block->start_pos()); | 547 BlockInfo* block_info = BlockInfoAt(block->start_pos()); |
| 548 | 548 |
| 549 // For every SSA value that is live out of this block, create an interval | 549 // For every SSA value that is live out of this block, create an interval |
| 550 // that covers the whole block. It will be shortened if we encounter a | 550 // that covers the whole block. It will be shortened if we encounter a |
| 551 // definition of this value in this block. | 551 // definition of this value in this block. |
| 552 for (BitVector::Iterator it(liveness_.GetLiveOutSetAt(i)); | 552 for (BitVector::Iterator it(liveness_.GetLiveOutSetAt(i)); |
| 553 !it.Done(); | 553 !it.Done(); |
| 554 it.Advance()) { | 554 it.Advance()) { |
| 555 LiveRange* range = GetLiveRange(it.Current()); | 555 LiveRange* range = GetLiveRange(it.Current()); |
| 556 range->AddUseInterval(block->start_pos(), block->end_pos()); | 556 range->AddUseInterval(block->start_pos(), block->end_pos()); |
| 557 } | 557 } |
| 558 | 558 |
| 559 BlockInfo* loop_header = block_info->loop_header(); | 559 BlockInfo* loop_header = block_info->loop_header(); |
| 560 if ((loop_header != NULL) && (loop_header->last_block() == block)) { | 560 if ((loop_header != NULL) && (loop_header->last_block() == block)) { |
| 561 current_interference_set = new(isolate) BitVector( | 561 current_interference_set = new(zone) BitVector( |
| 562 isolate, flow_graph_.max_virtual_register_number()); | 562 zone, flow_graph_.max_virtual_register_number()); |
| 563 ASSERT(loop_header->backedge_interference() == NULL); | 563 ASSERT(loop_header->backedge_interference() == NULL); |
| 564 // All values flowing into the loop header are live at the back-edge and | 564 // All values flowing into the loop header are live at the back-edge and |
| 565 // can interfere with phi moves. | 565 // can interfere with phi moves. |
| 566 current_interference_set->AddAll( | 566 current_interference_set->AddAll( |
| 567 liveness_.GetLiveInSet(loop_header->entry())); | 567 liveness_.GetLiveInSet(loop_header->entry())); |
| 568 loop_header->set_backedge_interference( | 568 loop_header->set_backedge_interference( |
| 569 current_interference_set); | 569 current_interference_set); |
| 570 } | 570 } |
| 571 | 571 |
| 572 // Connect outgoing phi-moves that were created in NumberInstructions | 572 // Connect outgoing phi-moves that were created in NumberInstructions |
| (...skipping 1445 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 2018 allocated_head); | 2018 allocated_head); |
| 2019 if (pos < intersection) intersection = pos; | 2019 if (pos < intersection) intersection = pos; |
| 2020 } | 2020 } |
| 2021 return intersection; | 2021 return intersection; |
| 2022 } | 2022 } |
| 2023 | 2023 |
| 2024 | 2024 |
| 2025 void ReachingDefs::AddPhi(PhiInstr* phi) { | 2025 void ReachingDefs::AddPhi(PhiInstr* phi) { |
| 2026 // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation. | 2026 // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation. |
| 2027 if (phi->reaching_defs() == NULL) { | 2027 if (phi->reaching_defs() == NULL) { |
| 2028 Isolate* isolate = Isolate::Current(); | 2028 Zone* zone = Thread::Current()->zone(); |
|
siva
2015/01/23 19:29:26
Zone* zone = flow_graph_.zone();
here?
koda
2015/01/23 21:09:42
Done.
| |
| 2029 phi->set_reaching_defs(new(isolate) BitVector( | 2029 phi->set_reaching_defs(new(zone) BitVector( |
| 2030 isolate, flow_graph_.max_virtual_register_number())); | 2030 zone, flow_graph_.max_virtual_register_number())); |
| 2031 | 2031 |
| 2032 // Compute initial set reaching defs set. | 2032 // Compute initial set reaching defs set. |
| 2033 bool depends_on_phi = false; | 2033 bool depends_on_phi = false; |
| 2034 for (intptr_t i = 0; i < phi->InputCount(); i++) { | 2034 for (intptr_t i = 0; i < phi->InputCount(); i++) { |
| 2035 Definition* input = phi->InputAt(i)->definition(); | 2035 Definition* input = phi->InputAt(i)->definition(); |
| 2036 if (input->IsPhi()) { | 2036 if (input->IsPhi()) { |
| 2037 depends_on_phi = true; | 2037 depends_on_phi = true; |
| 2038 } | 2038 } |
| 2039 phi->reaching_defs()->Add(input->ssa_temp_index()); | 2039 phi->reaching_defs()->Add(input->ssa_temp_index()); |
| 2040 } | 2040 } |
| 2041 | 2041 |
| 2042 // If this phi depends on another phi then we need fix point iteration. | 2042 // If this phi depends on another phi then we need fix point iteration. |
| 2043 if (depends_on_phi) phis_.Add(phi); | 2043 if (depends_on_phi) phis_.Add(phi); |
| 2044 } | 2044 } |
| 2045 } | 2045 } |
| 2046 | 2046 |
| 2047 | 2047 |
| 2048 void ReachingDefs::Compute() { | 2048 void ReachingDefs::Compute() { |
| 2049 // Transitively collect all phis that are used by the given phi. | 2049 // Transitively collect all phis that are used by the given phi. |
| 2050 for (intptr_t i = 0; i < phis_.length(); i++) { | 2050 for (intptr_t i = 0; i < phis_.length(); i++) { |
| 2051 // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation. | 2051 // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation. |
| 2052 PhiInstr* phi = phis_[i]; | 2052 PhiInstr* phi = phis_[i]; |
| 2053 | 2053 |
| 2054 // Add all phis that affect this phi to the list. | 2054 // Add all phis that affect this phi to the list. |
| 2055 for (intptr_t i = 0; i < phi->InputCount(); i++) { | 2055 for (intptr_t i = 0; i < phi->InputCount(); i++) { |
| 2056 PhiInstr* input_phi = phi->InputAt(i)->definition()->AsPhi(); | 2056 PhiInstr* input_phi = phi->InputAt(i)->definition()->AsPhi(); |
| 2057 if (input_phi != NULL) { | 2057 if (input_phi != NULL) { |
| 2058 AddPhi(input_phi); | 2058 AddPhi(input_phi); |
|
Ivan Posva
2015/01/23 04:53:04
We are calling Thread::Current() inside a doubly n
koda
2015/01/23 14:29:31
Done. Simply used the flow graph's zone.
Also got
| |
| 2059 } | 2059 } |
| 2060 } | 2060 } |
| 2061 } | 2061 } |
| 2062 | 2062 |
| 2063 // Propagate values until fix point is reached. | 2063 // Propagate values until fix point is reached. |
| 2064 bool changed; | 2064 bool changed; |
| 2065 do { | 2065 do { |
| 2066 changed = false; | 2066 changed = false; |
| 2067 for (intptr_t i = 0; i < phis_.length(); i++) { | 2067 for (intptr_t i = 0; i < phis_.length(); i++) { |
| 2068 PhiInstr* phi = phis_[i]; | 2068 PhiInstr* phi = phis_[i]; |
| (...skipping 85 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 2154 !it.Done(); | 2154 !it.Done(); |
| 2155 it.Advance()) { | 2155 it.Advance()) { |
| 2156 // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation. | 2156 // TODO(johnmccutchan): Fix handling of PhiInstr with PairLocation. |
| 2157 PhiInstr* phi = it.Current(); | 2157 PhiInstr* phi = it.Current(); |
| 2158 ASSERT(phi->is_alive()); | 2158 ASSERT(phi->is_alive()); |
| 2159 const intptr_t phi_vreg = phi->ssa_temp_index(); | 2159 const intptr_t phi_vreg = phi->ssa_temp_index(); |
| 2160 LiveRange* range = GetLiveRange(phi_vreg); | 2160 LiveRange* range = GetLiveRange(phi_vreg); |
| 2161 if (range->assigned_location().kind() == register_kind_) { | 2161 if (range->assigned_location().kind() == register_kind_) { |
| 2162 const intptr_t reg = range->assigned_location().register_code(); | 2162 const intptr_t reg = range->assigned_location().register_code(); |
| 2163 | 2163 |
| 2164 if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) { | 2164 if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) { |
|
Ivan Posva
2015/01/23 04:53:04
ditto for Get(phi)
koda
2015/01/23 14:29:31
Get doesn't need any zone.
| |
| 2165 used_on_backedge[reg] = true; | 2165 used_on_backedge[reg] = true; |
| 2166 } | 2166 } |
| 2167 } | 2167 } |
| 2168 } | 2168 } |
| 2169 | 2169 |
| 2170 if (used_on_backedge[candidate]) { | 2170 if (used_on_backedge[candidate]) { |
| 2171 TRACE_ALLOC(OS::Print( | 2171 TRACE_ALLOC(OS::Print( |
| 2172 "considering %s for v%" Pd ": has interference on the back edge" | 2172 "considering %s for v%" Pd ": has interference on the back edge" |
| 2173 " {loop [%" Pd ", %" Pd ")}\n", | 2173 " {loop [%" Pd ", %" Pd ")}\n", |
| 2174 MakeRegisterLocation(candidate).Name(), | 2174 MakeRegisterLocation(candidate).Name(), |
| (...skipping 797 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 2972 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", | 2972 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", |
| 2973 function.ToFullyQualifiedCString()); | 2973 function.ToFullyQualifiedCString()); |
| 2974 FlowGraphPrinter printer(flow_graph_, true); | 2974 FlowGraphPrinter printer(flow_graph_, true); |
| 2975 printer.PrintBlocks(); | 2975 printer.PrintBlocks(); |
| 2976 OS::Print("----------------------------------------------\n"); | 2976 OS::Print("----------------------------------------------\n"); |
| 2977 } | 2977 } |
| 2978 } | 2978 } |
| 2979 | 2979 |
| 2980 | 2980 |
| 2981 } // namespace dart | 2981 } // namespace dart |
| OLD | NEW |