1/*
2 * Copyright (C) 2019 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "B3OptimizeAssociativeExpressionTrees.h"
28
29#if ENABLE(B3_JIT)
30
31#include "B3BasicBlock.h"
32#include "B3Const32Value.h"
33#include "B3Const64Value.h"
34#include "B3InsertionSetInlines.h"
35#include "B3Opcode.h"
36#include "B3PhaseScope.h"
37#include "B3Procedure.h"
38#include "B3Value.h"
39#include "B3ValueInlines.h"
40
41namespace JSC { namespace B3 {
42
43class OptimizeAssociativeExpressionTrees {
44public:
45 OptimizeAssociativeExpressionTrees(Procedure& proc)
46 : m_proc(proc)
47 {
48 }
49
50 bool run();
51
52private:
53 int64_t neutralElement(Opcode);
54 bool isAbsorbingElement(Opcode, int64_t);
55 void combineConstants(Opcode, int64_t&, int64_t);
56 void emitValue(Opcode, Value*, unsigned numSeen, InsertionSet&, size_t indexInBlock, Vector<Value*, 4>& results);
57 bool optimizeRootedTree(Value* root, InsertionSet&, size_t indexInBlock, const Vector<unsigned>& useCounts);
58
59 Procedure& m_proc;
60 bool verbose { false };
61};
62
63int64_t OptimizeAssociativeExpressionTrees::neutralElement(Opcode op)
64{
65 switch (op) {
66 case Add:
67 case BitOr:
68 case BitXor:
69 return 0;
70 case Mul:
71 return 1;
72 case BitAnd:
73 return -1;
74 default:
75 RELEASE_ASSERT_NOT_REACHED();
76 }
77}
78
79bool OptimizeAssociativeExpressionTrees::isAbsorbingElement(Opcode op, int64_t constant)
80{
81 switch (op) {
82 case Add:
83 case BitXor:
84 return false;
85 case Mul:
86 case BitAnd:
87 return !constant;
88 case BitOr:
89 return constant == -1;
90 default:
91 RELEASE_ASSERT_NOT_REACHED();
92 }
93}
94
95void OptimizeAssociativeExpressionTrees::combineConstants(Opcode op, int64_t& const1, int64_t const2)
96{
97 switch (op) {
98 case Add:
99 const1 += const2;
100 break;
101 case Mul:
102 const1 *= const2;
103 break;
104 case BitAnd:
105 const1 &= const2;
106 break;
107 case BitOr:
108 const1 |= const2;
109 break;
110 case BitXor:
111 const1 ^= const2;
112 break;
113 default:
114 RELEASE_ASSERT_NOT_REACHED();
115 }
116}
117
118void OptimizeAssociativeExpressionTrees::emitValue(Opcode op, Value* value, unsigned numSeen, InsertionSet& insertionSet, size_t indexInBlock, Vector<Value*, 4>& results)
119{
120 switch (op) {
121 case Add:
122 if (numSeen > 1) {
123 Value* constNumSeen;
124 if (value->type() == Int32)
125 constNumSeen = insertionSet.insert<Const32Value>(indexInBlock, value->origin(), numSeen);
126 else
127 constNumSeen = insertionSet.insert<Const64Value>(indexInBlock, value->origin(), static_cast<int64_t>(numSeen));
128 results.append(insertionSet.insert<Value>(indexInBlock, Mul, value->origin(), value, constNumSeen));
129 } else
130 results.append(value);
131 break;
132 case Mul:
133 for (unsigned i = 0; i < numSeen; ++i)
134 results.append(value);
135 break;
136 case BitAnd:
137 case BitOr:
138 results.append(value);
139 break;
140 case BitXor:
141 if (numSeen % 2)
142 results.append(value);
143 break;
144 default:
145 RELEASE_ASSERT_NOT_REACHED();
146 }
147}
148
149bool OptimizeAssociativeExpressionTrees::optimizeRootedTree(Value* root, InsertionSet& insertionSet, size_t indexInBlock, const Vector<unsigned>& useCounts)
150{
151 Opcode op = root->opcode();
152 if ((root->child(0)->opcode() != op || useCounts[root->child(0)->index()] > 1)
153 && (root->child(1)->opcode() != op || useCounts[root->child(1)->index()] > 1)) {
154 // This is a trivial expression tree of size two, we have nothing to do here that B3ReduceStrength cannot do better than us.
155 return false;
156 }
157
158 // We proceed in three steps:
159 // - gather all the leaves of the expression tree
160 // - sort them, and combine as many as possible
161 // - make a balanced binary tree of them
162
163 Vector<Value*, 4> leaves;
164 Vector<Value*, 3> worklist = { root->child(0), root->child(1) };
165 int64_t constant = neutralElement(op);
166 unsigned numVisited = 0;
167 while (!worklist.isEmpty()) {
168 Value* val = worklist.takeLast();
169 if (val->opcode() == op && useCounts[val->index()] < 2) {
170 worklist.append(val->child(0));
171 worklist.append(val->child(1));
172 } else if (val->hasInt()) {
173 combineConstants(op, constant, val->asInt());
174 numVisited++;
175 } else {
176 numVisited++;
177 leaves.append(val);
178 }
179 }
180 if (isAbsorbingElement(op, constant)) {
181 Value* newRoot;
182 if (root->type() == Int32)
183 newRoot = insertionSet.insert<Const32Value>(indexInBlock, root->origin(), static_cast<int32_t>(constant));
184 else
185 newRoot = insertionSet.insert<Const64Value>(indexInBlock, root->origin(), constant);
186 root->replaceWithIdentity(newRoot);
187 return true;
188 }
189 if (numVisited < 4) {
190 // This is a nearly-trivial expression of size 3. B3ReduceStrength is still able to deal with such expressions competently, and there is no possible win from balancing them.
191 return false;
192 }
193
194 std::sort(leaves.begin(), leaves.end(), [](Value* x, Value* y) {
195 return x->index() < y->index();
196 });
197 Vector<Value*, 4> optLeaves;
198 Value* lastValue = nullptr;
199 unsigned numSeen = 0;
200 for (Value* value : leaves) {
201 if (lastValue == value)
202 numSeen++;
203 else {
204 if (lastValue)
205 emitValue(op, lastValue, numSeen, insertionSet, indexInBlock, optLeaves);
206 lastValue = value;
207 numSeen = 1;
208 }
209 }
210 if (lastValue)
211 emitValue(op, lastValue, numSeen, insertionSet, indexInBlock, optLeaves);
212
213 // optLeaves can be empty for trees of BitXor where all leaves happen an even number of times.
214 // In that case, we make the whole tree equivalent to the neutral element (which is 0 for BitXor).
215 if (constant != neutralElement(op) || optLeaves.isEmpty()) {
216 if (root->type() == Int32)
217 optLeaves.append(insertionSet.insert<Const32Value>(indexInBlock, root->origin(), static_cast<int32_t>(constant)));
218 else
219 optLeaves.append(insertionSet.insert<Const64Value>(indexInBlock, root->origin(), constant));
220 }
221
222 if (verbose) {
223 dataLog(" Expression tree rooted at ", *root, " (", root->opcode(), ") with leaves (numVisited = ", numVisited, ") ");
224 for (Value* leaf : leaves)
225 dataLog(" ", *leaf);
226 dataLog(" =>");
227 for (Value* leaf : optLeaves)
228 dataLog(" ", *leaf);
229 dataLog("\n");
230 }
231
232 // Finally we can build the balanced binary tree
233 unsigned leafIndex = 0;
234 while (leafIndex + 1 < optLeaves.size()) {
235 optLeaves.append(insertionSet.insert<Value>(indexInBlock, op, root->origin(), optLeaves[leafIndex], optLeaves[leafIndex + 1]));
236 leafIndex += 2;
237 }
238 ASSERT(leafIndex == optLeaves.size() - 1);
239 root->replaceWithIdentity(optLeaves[leafIndex]);
240 return true;
241}
242
243bool OptimizeAssociativeExpressionTrees::run()
244{
245 bool changed = false;
246
247 // We proceed in two phases.
248 // In the first one we compute the use counts of each value (of an interesting opcode), and find potential roots of interesting expression trees.
249 // In the second one we optimize each such expression tree in turn.
250 // We need the use counts to avoid duplicating code.
251
252 Vector<unsigned> useCounts(m_proc.values().size(), 0); // Mapping from Value::m_index to use counts.
253 HashSet<Value*> expressionTreeRoots;
254 HashSet<BasicBlock*> rootOwners;
255
256 for (BasicBlock* block : m_proc) {
257 for (Value* value : *block) {
258 for (Value* child : value->children()) {
259 if (!child->isInteger())
260 continue;
261 switch (child->opcode()) {
262 case Mul:
263 case Add:
264 case BitAnd:
265 case BitOr:
266 case BitXor:
267 useCounts[child->index()]++;
268 if (child->opcode() != value->opcode() || useCounts[child->index()] > 1) {
269 expressionTreeRoots.add(child);
270 rootOwners.add(child->owner);
271 }
272 break;
273 default:
274 break;
275 }
276 }
277 }
278 }
279
280 InsertionSet insertionSet = InsertionSet(m_proc);
281 for (BasicBlock* block : rootOwners) {
282 for (unsigned index = 0; index < block->size(); ++index) {
283 Value* value = block->at(index);
284 if (expressionTreeRoots.contains(value))
285 changed |= optimizeRootedTree(value, insertionSet, index, useCounts);
286 }
287 insertionSet.execute(block);
288 }
289
290 return changed;
291}
292
293bool optimizeAssociativeExpressionTrees(Procedure& proc)
294{
295 PhaseScope phaseScope(proc, "optimizeAssociativeExpressionTrees");
296 OptimizeAssociativeExpressionTrees optimizeAssociativeExpressionTrees(proc);
297 return optimizeAssociativeExpressionTrees.run();
298}
299
300} } // namespace JSC::B3
301
302#endif // ENABLE(B3_JIT)
303