232 lines
9.6 KiB
C++
232 lines
9.6 KiB
C++
/*
|
|
* Copyright (C) 2021 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 "B3CanonicalizePrePostIncrements.h"
|
|
|
|
#include "B3BackwardsDominators.h"
|
|
#include "B3BasicBlockInlines.h"
|
|
#include "B3BlockInsertionSet.h"
|
|
#include "B3Dominators.h"
|
|
#include "B3InsertionSetInlines.h"
|
|
#include "B3PhaseScope.h"
|
|
#include "B3ProcedureInlines.h"
|
|
#include "B3ValueInlines.h"
|
|
#include "B3ValueKeyInlines.h"
|
|
#include <wtf/HashMap.h>
|
|
#include <wtf/IndexSet.h>
|
|
#include <wtf/StdLibExtras.h>
|
|
|
|
#if ENABLE(B3_JIT)
|
|
|
|
namespace JSC { namespace B3 {
|
|
|
|
bool canonicalizePrePostIncrements(Procedure& proc)
|
|
{
|
|
if (!isARM64())
|
|
return false;
|
|
PhaseScope phaseScope(proc, "canonicalizePrePostIncrements");
|
|
using Arg = Air::Arg;
|
|
|
|
unsigned index { 0 };
|
|
InsertionSet insertionSet { proc };
|
|
BlockInsertionSet blockInsertionSet { proc };
|
|
|
|
Dominators& dominators = proc.dominators();
|
|
BackwardsDominators& backwardsDominators = proc.backwardsDominators();
|
|
|
|
IndexSet<Value*> ignoredValues;
|
|
HashMap<Value*, Vector<MemoryValue*>> baseToLoads;
|
|
HashMap<MemoryValue*, Value*> preIndexLoadCandidates;
|
|
HashMap<MemoryValue*, Value*> postIndexLoadCandidates;
|
|
HashMap<ValueKey, Vector<Value*>> baseOffsetToAddresses;
|
|
|
|
HashMap<Value*, Vector<MemoryValue*>> baseToStores;
|
|
HashMap<MemoryValue*, Value*> postIndexStoreCandidates;
|
|
|
|
auto tryAddPrePostIndexCandidate = [&] (Value* value) {
|
|
switch (value->opcode()) {
|
|
case Load: {
|
|
// Pre-Index Pattern:
|
|
// address = Add(base, offset)
|
|
// ...
|
|
// memory = Load(base, offset)
|
|
// Post-Index Pattern:
|
|
// memory = Load(base, 0)
|
|
// ...
|
|
// address = Add(base, offset)
|
|
auto tryAddpreIndexLoadCandidates = [&] () {
|
|
MemoryValue* memory = value->as<MemoryValue>();
|
|
if (memory->type() != Int32 && memory->type() != Int64)
|
|
return;
|
|
if (memory->offset()) {
|
|
if (!Arg::isValidIncrementIndexForm(memory->offset()))
|
|
return;
|
|
ValueKey baseOffsetkey = ValueKey(memory->child(0), static_cast<int64_t>(memory->offset()));
|
|
if (!baseOffsetToAddresses.contains(baseOffsetkey))
|
|
return;
|
|
for (Value* address : baseOffsetToAddresses.get(baseOffsetkey))
|
|
preIndexLoadCandidates.add(memory, address);
|
|
} else
|
|
baseToLoads.add(memory->child(0), Vector<MemoryValue*>()).iterator->value.append(memory);
|
|
};
|
|
|
|
tryAddpreIndexLoadCandidates();
|
|
break;
|
|
}
|
|
|
|
case Store: {
|
|
// Pre-Index Pattern:
|
|
// address = Add(base, offset)
|
|
// memory = Store(value, base, offset)
|
|
// Post-Index Pattern:
|
|
// memory = Store(value, base, 0)
|
|
// ...
|
|
// address = Add(base, offset)
|
|
auto tryUpdateBaseToStores = [&] () {
|
|
MemoryValue* memory = value->as<MemoryValue>();
|
|
if (memory->child(0)->type() != Int32 && memory->child(0)->type() != Int64)
|
|
return;
|
|
if (memory->child(0)->hasInt() || memory->offset())
|
|
return;
|
|
baseToStores.add(memory->child(1), Vector<MemoryValue*>()).iterator->value.append(memory);
|
|
};
|
|
|
|
tryUpdateBaseToStores();
|
|
break;
|
|
}
|
|
|
|
case Add: {
|
|
Value* left = value->child(0);
|
|
Value* right = value->child(1);
|
|
|
|
auto tryAddpostIndexCandidates = [&] () {
|
|
if (!right->hasIntPtr() || value->type() != Int64)
|
|
return;
|
|
intptr_t offset = right->asIntPtr();
|
|
Value::OffsetType smallOffset = static_cast<Value::OffsetType>(offset);
|
|
if (smallOffset != offset || !Arg::isValidIncrementIndexForm(smallOffset))
|
|
return;
|
|
// so far this Add value is a valid address candidate for both prefix and postfix pattern
|
|
ValueKey baseOffsetkey = ValueKey(left, static_cast<int64_t>(smallOffset));
|
|
baseOffsetToAddresses.add(baseOffsetkey, Vector<Value*>()).iterator->value.append(value);
|
|
if (baseToLoads.contains(left)) {
|
|
for (MemoryValue* memory : baseToLoads.get(left))
|
|
postIndexLoadCandidates.add(memory, value);
|
|
}
|
|
if (baseToStores.contains(left)) {
|
|
for (MemoryValue* memory : baseToStores.get(left))
|
|
postIndexStoreCandidates.add(memory, value);
|
|
}
|
|
};
|
|
|
|
tryAddpostIndexCandidates();
|
|
break;
|
|
}
|
|
|
|
default:
|
|
break;
|
|
}
|
|
};
|
|
|
|
for (BasicBlock* basicBlock : proc.blocksInPreOrder()) {
|
|
for (index = 0; index < basicBlock->size(); ++index)
|
|
tryAddPrePostIndexCandidate(basicBlock->at(index));
|
|
}
|
|
|
|
auto controlEquivalent = [&] (Value* v1, Value* v2) -> bool {
|
|
return (dominators.dominates(v1->owner, v2->owner) && backwardsDominators.dominates(v2->owner, v1->owner))
|
|
|| (dominators.dominates(v2->owner, v1->owner) && backwardsDominators.dominates(v1->owner, v2->owner));
|
|
};
|
|
|
|
// This search is expensive. However, due to the greedy pattern
|
|
// matching, no better method can be proposed at present.
|
|
auto valueIndexInBasicBlock = [&] (Value* value) -> unsigned {
|
|
unsigned index = 0;
|
|
BasicBlock* block = value->owner;
|
|
for (index = 0; index < block->size(); ++index) {
|
|
if (block->at(index) == value)
|
|
return index;
|
|
}
|
|
return index;
|
|
};
|
|
|
|
for (auto pair : preIndexLoadCandidates) {
|
|
MemoryValue* memory = pair.key;
|
|
Value* address = pair.value;
|
|
if (ignoredValues.contains(memory) || ignoredValues.contains(address) || !controlEquivalent(memory, address))
|
|
continue;
|
|
// address = Add(base, offset) address = Add(base, offset)
|
|
// ... --> newMemory = Load(base, offset)
|
|
// ... ...
|
|
// memory = Load(base, offset) memory = Identity(newMemory)
|
|
unsigned insertionIndex = valueIndexInBasicBlock(address) + 1;
|
|
MemoryValue* newMemory = insertionSet.insert<MemoryValue>(insertionIndex, Load, memory->type(), address->origin(), memory->lastChild());
|
|
newMemory->setOffset(memory->offset());
|
|
memory->replaceWithIdentity(newMemory);
|
|
insertionSet.execute(address->owner);
|
|
|
|
ignoredValues.add(memory);
|
|
ignoredValues.add(address);
|
|
}
|
|
|
|
auto detectPostIndex = [&] (const HashMap<MemoryValue*, Value*>& candidates) {
|
|
for (auto pair : candidates) {
|
|
MemoryValue* memory = pair.key;
|
|
Value* address = pair.value;
|
|
if (ignoredValues.contains(memory) || ignoredValues.contains(address) || !controlEquivalent(memory, address))
|
|
continue;
|
|
|
|
unsigned insertionIndex = valueIndexInBasicBlock(memory);
|
|
Value* newOffset = insertionSet.insert<Const64Value>(insertionIndex, memory->origin(), address->child(1)->asInt());
|
|
Value* newAddress = insertionSet.insert<Value>(insertionIndex, Add, memory->origin(), address->child(0), newOffset);
|
|
address->replaceWithIdentity(newAddress);
|
|
insertionSet.execute(memory->owner);
|
|
|
|
ignoredValues.add(memory);
|
|
ignoredValues.add(address);
|
|
}
|
|
};
|
|
|
|
// ... newOffset = Constant
|
|
// ... newAddress = Add(base, newOffset)
|
|
// memory = Load(base, 0) memory = Load(base, 0)
|
|
// ... --> ...
|
|
// address = Add(base, offset) address = Identity(newAddress)
|
|
detectPostIndex(postIndexLoadCandidates);
|
|
|
|
// ... newOffset = Constant
|
|
// ... newAddress = Add(base, newOffset)
|
|
// memory = Store(value, base, 0) memory = Store(value, base, 0)
|
|
// ... --> ...
|
|
// address = Add(base, offset) address = Identity(newAddress)
|
|
detectPostIndex(postIndexStoreCandidates);
|
|
return true;
|
|
}
|
|
|
|
} } // namespace JSC::B3
|
|
|
|
#endif // ENABLE(B3_JIT)
|