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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
// Copyright 2023 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/compiler/wasm-address-reassociation.h"
#include "src/compiler/common-operator.h"
#include "src/compiler/graph.h"
#include "src/compiler/js-graph.h"
#include "src/compiler/machine-graph.h"
#include "src/compiler/machine-operator.h"
#include "src/compiler/node-matchers.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/node.h"
#include "src/compiler/opcodes.h"
#include "src/compiler/operator.h"
#include "src/zone/zone.h"
namespace v8 {
namespace internal {
namespace compiler {
// Wasm address reassociation.
//
// wasm32 load and store operations use a 32-bit dynamic offset along with a
// 32-bit static index to create a 33-bit effective address. This means that
// to use a static index, greater than zero, the producer needs to prove that
// the addition of the index won't overflow. However, if we're performing
// address computations with 64-bits, we should be able to more readily use
// immediate indexes.
//
// So, the purpose of this transform is to pattern match certain address
// computations and reorganize the operands for more efficient code generation.
//
// Many addresses will be computed in the form like this:
// - ProtectedLoad (IntPtrAdd (base_reg, immediate_offset), register_offset)
// - ProtectedStore (IntPtrAdd (base_reg, immediate_offset), register_offset)
// And this pass aims to transform this into:
// - ProtectedLoad (IntPtrAdd (base_reg, register_offset), immediate_offset)
// - ProtectedStore (IntPtrAdd (base_reg, register_offset), immediate_offset)
//
// This allows the reuse of a base pointer across multiple instructions, each of
// which then has the opportunity to use an immediate offset.
WasmAddressReassociation::WasmAddressReassociation(JSGraph* jsgraph, Zone* zone)
: graph_(jsgraph->graph()),
common_(jsgraph->common()),
machine_(jsgraph->machine()),
candidate_base_addrs_(zone),
candidates_(zone),
zone_(zone) {}
void WasmAddressReassociation::Optimize() {
for (auto& candidate : candidates_) {
const CandidateAddressKey& key = candidate.first;
if (!ShouldTryOptimize(key)) continue;
// We've found multiple instances of addresses in the form
// object(base + imm_offset), reg_offset
// So, create a new object for these operations to share and then use an
// immediate offset:
// object(base, reg_offset), imm_offset
Node* new_object = CreateNewBase(key);
CandidateMemOps& mem_ops = candidate.second;
size_t num_nodes = mem_ops.GetNumNodes();
for (size_t i = 0; i < num_nodes; ++i) {
Node* mem_op = mem_ops.mem_op(i);
Node* imm_offset =
graph_->NewNode(common_->Int64Constant(mem_ops.imm_offset(i)));
ReplaceInputs(mem_op, new_object, imm_offset);
}
}
}
bool WasmAddressReassociation::ShouldTryOptimize(
const CandidateAddressKey& key) const {
// We already process the graph in terms of effect chains in an attempt to
// reduce the risk of creating large live-ranges, but also set a lower
// bound for the number of required users so that the benefits are more
// likely to outweigh any detrimental affects, such as additions being shared
// and so the number of operations is increased. Benchmarking showed two or
// more was a good heuristic.
return candidates_.at(key).GetNumNodes() > 1;
}
Node* WasmAddressReassociation::CreateNewBase(const CandidateAddressKey& key) {
CandidateBaseAddr& candidate_base_addr = candidate_base_addrs_.at(key);
Node* base = candidate_base_addr.base();
Node* reg_offset = candidate_base_addr.offset();
return graph_->NewNode(machine_->Int64Add(), base, reg_offset);
}
void WasmAddressReassociation::ReplaceInputs(Node* mem_op, Node* base,
Node* offset) {
DCHECK_GT(mem_op->InputCount(), 1);
DCHECK(NodeProperties::IsConstant(offset));
mem_op->ReplaceInput(0, base);
mem_op->ReplaceInput(1, offset);
}
void WasmAddressReassociation::VisitProtectedMemOp(Node* node,
NodeId effect_chain) {
DCHECK(node->opcode() == IrOpcode::kProtectedLoad ||
node->opcode() == IrOpcode::kProtectedStore);
Node* base(node->InputAt(0));
Node* offset(node->InputAt(1));
if (base->opcode() == IrOpcode::kInt64Add &&
offset->opcode() == IrOpcode::kInt64Add) {
Int64BinopMatcher base_add(base);
Int64BinopMatcher offset_add(offset);
if (base_add.right().HasResolvedValue() &&
!base_add.left().HasResolvedValue() &&
offset_add.right().HasResolvedValue() &&
!offset_add.left().HasResolvedValue()) {
Node* base_reg = base_add.left().node();
Node* reg_offset = offset_add.left().node();
int64_t imm_offset =
base_add.right().ResolvedValue() + offset_add.right().ResolvedValue();
return AddCandidate(node, base_reg, reg_offset, imm_offset, effect_chain);
}
}
if (base->opcode() == IrOpcode::kInt64Add) {
Int64BinopMatcher base_add(base);
if (base_add.right().HasResolvedValue() &&
!base_add.left().HasResolvedValue()) {
Node* base_reg = base_add.left().node();
Node* reg_offset = node->InputAt(1);
int64_t imm_offset = base_add.right().ResolvedValue();
return AddCandidate(node, base_reg, reg_offset, imm_offset, effect_chain);
}
}
if (offset->opcode() == IrOpcode::kInt64Add) {
Int64BinopMatcher offset_add(offset);
if (offset_add.right().HasResolvedValue() &&
!offset_add.left().HasResolvedValue()) {
Node* base_reg = node->InputAt(0);
Node* reg_offset = offset_add.left().node();
int64_t imm_offset = offset_add.right().ResolvedValue();
return AddCandidate(node, base_reg, reg_offset, imm_offset, effect_chain);
}
}
}
void WasmAddressReassociation::AddCandidate(Node* mem_op, Node* base,
Node* reg_offset,
int64_t imm_offset,
NodeId effect_chain) {
// Sort base and offset so that the key is the same for either permutation.
if (base->id() > reg_offset->id()) {
std::swap(base, reg_offset);
}
CandidateAddressKey key =
std::make_tuple(base->id(), reg_offset->id(), effect_chain);
bool is_new =
candidate_base_addrs_.emplace(key, CandidateBaseAddr(base, reg_offset))
.second;
auto it = is_new ? candidates_.emplace(key, CandidateMemOps(zone_)).first
: candidates_.find(key);
it->second.AddCandidate(mem_op, imm_offset);
}
bool WasmAddressReassociation::HasCandidateBaseAddr(
const CandidateAddressKey& key) const {
return candidate_base_addrs_.count(key);
}
void WasmAddressReassociation::CandidateMemOps::AddCandidate(
Node* mem_op, int64_t imm_offset) {
DCHECK(mem_op->opcode() == IrOpcode::kProtectedLoad ||
mem_op->opcode() == IrOpcode::kProtectedStore);
mem_ops_.push_back(mem_op);
imm_offsets_.push_back(imm_offset);
}
size_t WasmAddressReassociation::CandidateMemOps::GetNumNodes() const {
DCHECK_EQ(mem_ops_.size(), imm_offsets_.size());
return mem_ops_.size();
}
Node* WasmAddressReassociation::CandidateMemOps::mem_op(size_t i) const {
return mem_ops_[i];
}
int64_t WasmAddressReassociation::CandidateMemOps::imm_offset(size_t i) const {
return imm_offsets_[i];
}
} // namespace compiler
} // namespace internal
} // namespace v8
|
