1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
/*
* 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 "gvn.h"
namespace art {
void GlobalValueNumberer::Run() {
ComputeSideEffects();
sets_.Put(graph_->GetEntryBlock()->GetBlockId(), new (allocator_) ValueSet(allocator_));
// Do reverse post order to ensure the non back-edge predecessors of a block are
// visited before the block itself.
for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
VisitBasicBlock(it.Current());
}
}
void GlobalValueNumberer::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) {
int id = info->GetHeader()->GetBlockId();
loop_effects_.Put(id, loop_effects_.Get(id).Union(effects));
}
void GlobalValueNumberer::ComputeSideEffects() {
if (kIsDebugBuild) {
for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
SideEffects effects = GetBlockEffects(block);
DCHECK(!effects.HasSideEffects() && !effects.HasDependencies());
if (block->IsLoopHeader()) {
effects = GetLoopEffects(block);
DCHECK(!effects.HasSideEffects() && !effects.HasDependencies());
}
}
}
// Do a post order visit to ensure we visit a loop header after its loop body.
for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
SideEffects effects = SideEffects::None();
// Update `effects` with the side effects of all instructions in this block.
for (HInstructionIterator inst_it(block->GetInstructions()); !inst_it.Done();
inst_it.Advance()) {
HInstruction* instruction = inst_it.Current();
effects = effects.Union(instruction->GetSideEffects());
if (effects.HasAllSideEffects()) {
break;
}
}
block_effects_.Put(block->GetBlockId(), effects);
if (block->IsLoopHeader()) {
// The side effects of the loop header are part of the loop.
UpdateLoopEffects(block->GetLoopInformation(), effects);
HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader();
if (pre_header->IsInLoop()) {
// Update the side effects of the outer loop with the side effects of the inner loop.
// Note that this works because we know all the blocks of the inner loop are visited
// before the loop header of the outer loop.
UpdateLoopEffects(pre_header->GetLoopInformation(), GetLoopEffects(block));
}
} else if (block->IsInLoop()) {
// Update the side effects of the loop with the side effects of this block.
UpdateLoopEffects(block->GetLoopInformation(), effects);
}
}
}
SideEffects GlobalValueNumberer::GetLoopEffects(HBasicBlock* block) const {
DCHECK(block->IsLoopHeader());
return loop_effects_.Get(block->GetBlockId());
}
SideEffects GlobalValueNumberer::GetBlockEffects(HBasicBlock* block) const {
return block_effects_.Get(block->GetBlockId());
}
void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
ValueSet* set = nullptr;
const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors();
if (predecessors.Size() == 0 || predecessors.Get(0)->IsEntryBlock()) {
// The entry block should only accumulate constant instructions, and
// the builder puts constants only in the entry block.
// Therefore, there is no need to propagate the value set to the next block.
set = new (allocator_) ValueSet(allocator_);
} else {
HBasicBlock* dominator = block->GetDominator();
set = sets_.Get(dominator->GetBlockId())->Copy();
if (dominator->GetSuccessors().Size() != 1 || dominator->GetSuccessors().Get(0) != block) {
// We have to copy if the dominator has other successors, or `block` is not a successor
// of the dominator.
set = set->Copy();
}
if (!set->IsEmpty()) {
if (block->IsLoopHeader()) {
DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader());
set->Kill(GetLoopEffects(block));
} else if (predecessors.Size() > 1) {
for (size_t i = 0, e = predecessors.Size(); i < e; ++i) {
set->IntersectionWith(sets_.Get(predecessors.Get(i)->GetBlockId()));
if (set->IsEmpty()) {
break;
}
}
}
}
}
sets_.Put(block->GetBlockId(), set);
HInstruction* current = block->GetFirstInstruction();
while (current != nullptr) {
set->Kill(current->GetSideEffects());
// Save the next instruction in case `current` is removed from the graph.
HInstruction* next = current->GetNext();
if (current->CanBeMoved()) {
HInstruction* existing = set->Lookup(current);
if (existing != nullptr) {
current->ReplaceWith(existing);
current->GetBlock()->RemoveInstruction(current);
} else {
set->Add(current);
}
}
current = next;
}
}
} // namespace art
|
