| /* |
| * Copyright (C) 2019 Apple Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
| * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "config.h" |
| #include "B3OptimizeAssociativeExpressionTrees.h" |
| |
| #if ENABLE(B3_JIT) |
| |
| #include "B3BasicBlock.h" |
| #include "B3Const32Value.h" |
| #include "B3Const64Value.h" |
| #include "B3InsertionSetInlines.h" |
| #include "B3Opcode.h" |
| #include "B3PhaseScope.h" |
| #include "B3Procedure.h" |
| #include "B3Value.h" |
| #include "B3ValueInlines.h" |
| |
| namespace JSC { namespace B3 { |
| |
| class OptimizeAssociativeExpressionTrees { |
| public: |
| OptimizeAssociativeExpressionTrees(Procedure& proc) |
| : m_proc(proc) |
| { |
| } |
| |
| bool run(); |
| |
| private: |
| int64_t neutralElement(Opcode); |
| bool isAbsorbingElement(Opcode, int64_t); |
| void combineConstants(Opcode, int64_t&, int64_t); |
| void emitValue(Opcode, Value*, unsigned numSeen, InsertionSet&, size_t indexInBlock, Vector<Value*, 4>& results); |
| bool optimizeRootedTree(Value* root, InsertionSet&, size_t indexInBlock, const Vector<unsigned>& useCounts); |
| |
| Procedure& m_proc; |
| static constexpr bool verbose { false }; |
| }; |
| |
| int64_t OptimizeAssociativeExpressionTrees::neutralElement(Opcode op) |
| { |
| switch (op) { |
| case Add: |
| case BitOr: |
| case BitXor: |
| return 0; |
| case Mul: |
| return 1; |
| case BitAnd: |
| return -1; |
| default: |
| RELEASE_ASSERT_NOT_REACHED(); |
| } |
| } |
| |
| bool OptimizeAssociativeExpressionTrees::isAbsorbingElement(Opcode op, int64_t constant) |
| { |
| switch (op) { |
| case Add: |
| case BitXor: |
| return false; |
| case Mul: |
| case BitAnd: |
| return !constant; |
| case BitOr: |
| return constant == -1; |
| default: |
| RELEASE_ASSERT_NOT_REACHED(); |
| } |
| } |
| |
| void OptimizeAssociativeExpressionTrees::combineConstants(Opcode op, int64_t& const1, int64_t const2) |
| { |
| switch (op) { |
| case Add: |
| const1 += const2; |
| break; |
| case Mul: |
| const1 *= const2; |
| break; |
| case BitAnd: |
| const1 &= const2; |
| break; |
| case BitOr: |
| const1 |= const2; |
| break; |
| case BitXor: |
| const1 ^= const2; |
| break; |
| default: |
| RELEASE_ASSERT_NOT_REACHED(); |
| } |
| } |
| |
| void OptimizeAssociativeExpressionTrees::emitValue(Opcode op, Value* value, unsigned numSeen, InsertionSet& insertionSet, size_t indexInBlock, Vector<Value*, 4>& results) |
| { |
| switch (op) { |
| case Add: |
| if (numSeen > 1) { |
| Value* constNumSeen; |
| if (value->type() == Int32) |
| constNumSeen = insertionSet.insert<Const32Value>(indexInBlock, value->origin(), numSeen); |
| else |
| constNumSeen = insertionSet.insert<Const64Value>(indexInBlock, value->origin(), static_cast<int64_t>(numSeen)); |
| results.append(insertionSet.insert<Value>(indexInBlock, Mul, value->origin(), value, constNumSeen)); |
| } else |
| results.append(value); |
| break; |
| case Mul: |
| for (unsigned i = 0; i < numSeen; ++i) |
| results.append(value); |
| break; |
| case BitAnd: |
| case BitOr: |
| results.append(value); |
| break; |
| case BitXor: |
| if (numSeen % 2) |
| results.append(value); |
| break; |
| default: |
| RELEASE_ASSERT_NOT_REACHED(); |
| } |
| } |
| |
| bool OptimizeAssociativeExpressionTrees::optimizeRootedTree(Value* root, InsertionSet& insertionSet, size_t indexInBlock, const Vector<unsigned>& useCounts) |
| { |
| Opcode op = root->opcode(); |
| if ((root->child(0)->opcode() != op || useCounts[root->child(0)->index()] > 1) |
| && (root->child(1)->opcode() != op || useCounts[root->child(1)->index()] > 1)) { |
| // This is a trivial expression tree of size two, we have nothing to do here that B3ReduceStrength cannot do better than us. |
| return false; |
| } |
| |
| // We proceed in three steps: |
| // - gather all the leaves of the expression tree |
| // - sort them, and combine as many as possible |
| // - make a balanced binary tree of them |
| |
| Vector<Value*, 4> leaves; |
| Vector<Value*, 3> worklist = { root->child(0), root->child(1) }; |
| int64_t constant = neutralElement(op); |
| unsigned numVisited = 0; |
| while (!worklist.isEmpty()) { |
| Value* val = worklist.takeLast(); |
| if (val->opcode() == op && useCounts[val->index()] < 2) { |
| worklist.append(val->child(0)); |
| worklist.append(val->child(1)); |
| } else if (val->hasInt()) { |
| combineConstants(op, constant, val->asInt()); |
| numVisited++; |
| } else { |
| numVisited++; |
| leaves.append(val); |
| } |
| } |
| if (isAbsorbingElement(op, constant)) { |
| Value* newRoot; |
| if (root->type() == Int32) |
| newRoot = insertionSet.insert<Const32Value>(indexInBlock, root->origin(), static_cast<int32_t>(constant)); |
| else |
| newRoot = insertionSet.insert<Const64Value>(indexInBlock, root->origin(), constant); |
| root->replaceWithIdentity(newRoot); |
| return true; |
| } |
| if (numVisited < 4) { |
| // 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. |
| return false; |
| } |
| |
| std::sort(leaves.begin(), leaves.end(), [](Value* x, Value* y) { |
| return x->index() < y->index(); |
| }); |
| Vector<Value*, 4> optLeaves; |
| Value* lastValue = nullptr; |
| unsigned numSeen = 0; |
| for (Value* value : leaves) { |
| if (lastValue == value) |
| numSeen++; |
| else { |
| if (lastValue) |
| emitValue(op, lastValue, numSeen, insertionSet, indexInBlock, optLeaves); |
| lastValue = value; |
| numSeen = 1; |
| } |
| } |
| if (lastValue) |
| emitValue(op, lastValue, numSeen, insertionSet, indexInBlock, optLeaves); |
| |
| // optLeaves can be empty for trees of BitXor where all leaves happen an even number of times. |
| // In that case, we make the whole tree equivalent to the neutral element (which is 0 for BitXor). |
| if (constant != neutralElement(op) || optLeaves.isEmpty()) { |
| if (root->type() == Int32) |
| optLeaves.append(insertionSet.insert<Const32Value>(indexInBlock, root->origin(), static_cast<int32_t>(constant))); |
| else |
| optLeaves.append(insertionSet.insert<Const64Value>(indexInBlock, root->origin(), constant)); |
| } |
| |
| if (verbose) { |
| dataLog(" Expression tree rooted at ", *root, " (", root->opcode(), ") with leaves (numVisited = ", numVisited, ") "); |
| for (Value* leaf : leaves) |
| dataLog(" ", *leaf); |
| dataLog(" =>"); |
| for (Value* leaf : optLeaves) |
| dataLog(" ", *leaf); |
| dataLog("\n"); |
| } |
| |
| // Finally we can build the balanced binary tree |
| unsigned leafIndex = 0; |
| while (leafIndex + 1 < optLeaves.size()) { |
| optLeaves.append(insertionSet.insert<Value>(indexInBlock, op, root->origin(), optLeaves[leafIndex], optLeaves[leafIndex + 1])); |
| leafIndex += 2; |
| } |
| ASSERT(leafIndex == optLeaves.size() - 1); |
| root->replaceWithIdentity(optLeaves[leafIndex]); |
| return true; |
| } |
| |
| bool OptimizeAssociativeExpressionTrees::run() |
| { |
| bool changed = false; |
| |
| // We proceed in two phases. |
| // In the first one we compute the use counts of each value (of an interesting opcode), and find potential roots of interesting expression trees. |
| // In the second one we optimize each such expression tree in turn. |
| // We need the use counts to avoid duplicating code. |
| |
| m_proc.resetValueOwners(); |
| |
| Vector<unsigned> useCounts(m_proc.values().size(), 0); // Mapping from Value::m_index to use counts. |
| HashSet<Value*> expressionTreeRoots; |
| HashSet<BasicBlock*> rootOwners; |
| |
| for (BasicBlock* block : m_proc) { |
| for (Value* value : *block) { |
| for (Value* child : value->children()) { |
| if (!child->isInteger()) |
| continue; |
| switch (child->opcode()) { |
| case Mul: |
| case Add: |
| case BitAnd: |
| case BitOr: |
| case BitXor: |
| useCounts[child->index()]++; |
| if (child->opcode() != value->opcode() || useCounts[child->index()] > 1) { |
| expressionTreeRoots.add(child); |
| rootOwners.add(child->owner); |
| } |
| break; |
| default: |
| break; |
| } |
| } |
| } |
| } |
| |
| InsertionSet insertionSet = InsertionSet(m_proc); |
| for (BasicBlock* block : rootOwners) { |
| for (unsigned index = 0; index < block->size(); ++index) { |
| Value* value = block->at(index); |
| if (expressionTreeRoots.contains(value)) |
| changed |= optimizeRootedTree(value, insertionSet, index, useCounts); |
| } |
| insertionSet.execute(block); |
| } |
| |
| return changed; |
| } |
| |
| bool optimizeAssociativeExpressionTrees(Procedure& proc) |
| { |
| PhaseScope phaseScope(proc, "optimizeAssociativeExpressionTrees"); |
| OptimizeAssociativeExpressionTrees optimizeAssociativeExpressionTrees(proc); |
| return optimizeAssociativeExpressionTrees.run(); |
| } |
| |
| } } // namespace JSC::B3 |
| |
| #endif // ENABLE(B3_JIT) |
