blob: 58f6147b767b34b9558293dc029c982d72b7a17f [file] [log] [blame]
// Copyright 2016 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/load-elimination.h"
#include "src/compiler/access-builder.h"
#include "src/compiler/js-graph.h"
#include "src/compiler/node.h"
#include "src/compiler/simplified-operator.h"
#include "test/unittests/compiler/graph-reducer-unittest.h"
#include "test/unittests/compiler/graph-unittest.h"
#include "test/unittests/compiler/node-test-utils.h"
#include "testing/gmock-support.h"
using testing::_;
using testing::StrictMock;
namespace v8 {
namespace internal {
namespace compiler {
class LoadEliminationTest : public TypedGraphTest {
public:
LoadEliminationTest()
: TypedGraphTest(3),
simplified_(zone()),
jsgraph_(isolate(), graph(), common(), nullptr, simplified(), nullptr) {
}
~LoadEliminationTest() override = default;
protected:
JSGraph* jsgraph() { return &jsgraph_; }
SimplifiedOperatorBuilder* simplified() { return &simplified_; }
private:
SimplifiedOperatorBuilder simplified_;
JSGraph jsgraph_;
};
TEST_F(LoadEliminationTest, LoadElementAndLoadElement) {
Node* object = Parameter(Type::Any(), 0);
Node* effect = graph()->start();
Node* control = graph()->start();
Node* index = Parameter(Type::UnsignedSmall(), 1);
ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Any(),
MachineType::AnyTagged(), kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
Node* load1 = effect = graph()->NewNode(simplified()->LoadElement(access),
object, index, effect, control);
load_elimination.Reduce(load1);
Node* load2 = effect = graph()->NewNode(simplified()->LoadElement(access),
object, index, effect, control);
EXPECT_CALL(editor, ReplaceWithValue(load2, load1, load1, _));
Reduction r = load_elimination.Reduce(load2);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(load1, r.replacement());
}
TEST_F(LoadEliminationTest, StoreElementAndLoadElement) {
Node* object = Parameter(Type::Any(), 0);
Node* effect = graph()->start();
Node* control = graph()->start();
Node* index = Parameter(Type::UnsignedSmall(), 1);
Node* value = Parameter(Type::Any(), 2);
ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Any(),
MachineType::AnyTagged(), kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
Node* store = effect =
graph()->NewNode(simplified()->StoreElement(access), object, index, value,
effect, control);
load_elimination.Reduce(store);
Node* load = effect = graph()->NewNode(simplified()->LoadElement(access),
object, index, effect, control);
EXPECT_CALL(editor, ReplaceWithValue(load, value, store, _));
Reduction r = load_elimination.Reduce(load);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(value, r.replacement());
}
TEST_F(LoadEliminationTest, StoreElementAndStoreFieldAndLoadElement) {
Node* object = Parameter(Type::Any(), 0);
Node* effect = graph()->start();
Node* control = graph()->start();
Node* index = Parameter(Type::UnsignedSmall(), 1);
Node* value = Parameter(Type::Any(), 2);
ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Any(),
MachineType::AnyTagged(), kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
Node* store1 = effect =
graph()->NewNode(simplified()->StoreElement(access), object, index, value,
effect, control);
load_elimination.Reduce(store1);
Node* store2 = effect =
graph()->NewNode(simplified()->StoreField(AccessBuilder::ForMap()),
object, value, effect, control);
load_elimination.Reduce(store2);
Node* load = effect = graph()->NewNode(simplified()->LoadElement(access),
object, index, effect, control);
EXPECT_CALL(editor, ReplaceWithValue(load, value, store2, _));
Reduction r = load_elimination.Reduce(load);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(value, r.replacement());
}
TEST_F(LoadEliminationTest, LoadFieldAndLoadField) {
Node* object = Parameter(Type::Any(), 0);
Node* effect = graph()->start();
Node* control = graph()->start();
FieldAccess const access = {kTaggedBase, kTaggedSize,
MaybeHandle<Name>(), MaybeHandle<Map>(),
Type::Any(), MachineType::AnyTagged(),
kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
Node* load1 = effect = graph()->NewNode(simplified()->LoadField(access),
object, effect, control);
load_elimination.Reduce(load1);
Node* load2 = effect = graph()->NewNode(simplified()->LoadField(access),
object, effect, control);
EXPECT_CALL(editor, ReplaceWithValue(load2, load1, load1, _));
Reduction r = load_elimination.Reduce(load2);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(load1, r.replacement());
}
TEST_F(LoadEliminationTest, StoreFieldAndLoadField) {
Node* object = Parameter(Type::Any(), 0);
Node* value = Parameter(Type::Any(), 1);
Node* effect = graph()->start();
Node* control = graph()->start();
FieldAccess access = {kTaggedBase, kTaggedSize,
MaybeHandle<Name>(), MaybeHandle<Map>(),
Type::Any(), MachineType::AnyTagged(),
kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
Node* store = effect = graph()->NewNode(simplified()->StoreField(access),
object, value, effect, control);
load_elimination.Reduce(store);
Node* load = effect = graph()->NewNode(simplified()->LoadField(access),
object, effect, control);
EXPECT_CALL(editor, ReplaceWithValue(load, value, store, _));
Reduction r = load_elimination.Reduce(load);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(value, r.replacement());
}
TEST_F(LoadEliminationTest, StoreFieldAndKillFields) {
Node* object = Parameter(Type::Any(), 0);
Node* value = Parameter(Type::Any(), 1);
Node* effect = graph()->start();
Node* control = graph()->start();
FieldAccess access1 = {kTaggedBase, kTaggedSize,
MaybeHandle<Name>(), MaybeHandle<Map>(),
Type::Any(), MachineType::AnyTagged(),
kNoWriteBarrier};
// Offset that out of field cache size.
FieldAccess access2 = {kTaggedBase, 2048 * kTaggedSize,
MaybeHandle<Name>(), MaybeHandle<Map>(),
Type::Any(), MachineType::AnyTagged(),
kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
Node* store1 = effect = graph()->NewNode(simplified()->StoreField(access1),
object, value, effect, control);
load_elimination.Reduce(store1);
// Invalidate caches of object.
Node* store2 = effect = graph()->NewNode(simplified()->StoreField(access2),
object, value, effect, control);
load_elimination.Reduce(store2);
Node* store3 = graph()->NewNode(simplified()->StoreField(access1),
object, value, effect, control);
Reduction r = load_elimination.Reduce(store3);
// store3 shall not be replaced, since caches were invalidated.
EXPECT_EQ(store3, r.replacement());
}
TEST_F(LoadEliminationTest, StoreFieldAndStoreElementAndLoadField) {
Node* object = Parameter(Type::Any(), 0);
Node* value = Parameter(Type::Any(), 1);
Node* index = Parameter(Type::UnsignedSmall(), 2);
Node* effect = graph()->start();
Node* control = graph()->start();
FieldAccess access = {kTaggedBase, kTaggedSize,
MaybeHandle<Name>(), MaybeHandle<Map>(),
Type::Any(), MachineType::AnyTagged(),
kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
Node* store1 = effect = graph()->NewNode(simplified()->StoreField(access),
object, value, effect, control);
load_elimination.Reduce(store1);
Node* store2 = effect = graph()->NewNode(
simplified()->StoreElement(AccessBuilder::ForFixedArrayElement()), object,
index, object, effect, control);
load_elimination.Reduce(store2);
Node* load = effect = graph()->NewNode(simplified()->LoadField(access),
object, effect, control);
EXPECT_CALL(editor, ReplaceWithValue(load, value, store2, _));
Reduction r = load_elimination.Reduce(load);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(value, r.replacement());
}
TEST_F(LoadEliminationTest, LoadElementOnTrueBranchOfDiamond) {
Node* object = Parameter(Type::Any(), 0);
Node* index = Parameter(Type::UnsignedSmall(), 1);
Node* check = Parameter(Type::Boolean(), 2);
Node* effect = graph()->start();
Node* control = graph()->start();
ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Any(),
MachineType::AnyTagged(), kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
Node* branch = graph()->NewNode(common()->Branch(), check, control);
Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
Node* etrue = graph()->NewNode(simplified()->LoadElement(access), object,
index, effect, if_true);
load_elimination.Reduce(etrue);
Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
Node* efalse = effect;
control = graph()->NewNode(common()->Merge(2), if_true, if_false);
effect = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, control);
load_elimination.Reduce(effect);
Node* load = graph()->NewNode(simplified()->LoadElement(access), object,
index, effect, control);
Reduction r = load_elimination.Reduce(load);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(load, r.replacement());
}
TEST_F(LoadEliminationTest, LoadElementOnFalseBranchOfDiamond) {
Node* object = Parameter(Type::Any(), 0);
Node* index = Parameter(Type::UnsignedSmall(), 1);
Node* check = Parameter(Type::Boolean(), 2);
Node* effect = graph()->start();
Node* control = graph()->start();
ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Any(),
MachineType::AnyTagged(), kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
Node* branch = graph()->NewNode(common()->Branch(), check, control);
Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
Node* etrue = effect;
Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
Node* efalse = graph()->NewNode(simplified()->LoadElement(access), object,
index, effect, if_false);
load_elimination.Reduce(efalse);
control = graph()->NewNode(common()->Merge(2), if_true, if_false);
effect = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, control);
load_elimination.Reduce(effect);
Node* load = graph()->NewNode(simplified()->LoadElement(access), object,
index, effect, control);
Reduction r = load_elimination.Reduce(load);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(load, r.replacement());
}
TEST_F(LoadEliminationTest, LoadFieldOnFalseBranchOfDiamond) {
Node* object = Parameter(Type::Any(), 0);
Node* check = Parameter(Type::Boolean(), 1);
Node* effect = graph()->start();
Node* control = graph()->start();
FieldAccess const access = {kTaggedBase, kTaggedSize,
MaybeHandle<Name>(), MaybeHandle<Map>(),
Type::Any(), MachineType::AnyTagged(),
kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
Node* branch = graph()->NewNode(common()->Branch(), check, control);
Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
Node* etrue = effect;
Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
Node* efalse = graph()->NewNode(simplified()->LoadField(access), object,
effect, if_false);
load_elimination.Reduce(efalse);
control = graph()->NewNode(common()->Merge(2), if_true, if_false);
effect = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, control);
load_elimination.Reduce(effect);
Node* load = graph()->NewNode(simplified()->LoadField(access), object, effect,
control);
Reduction r = load_elimination.Reduce(load);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(load, r.replacement());
}
TEST_F(LoadEliminationTest, LoadFieldOnTrueBranchOfDiamond) {
Node* object = Parameter(Type::Any(), 0);
Node* check = Parameter(Type::Boolean(), 1);
Node* effect = graph()->start();
Node* control = graph()->start();
FieldAccess const access = {kTaggedBase, kTaggedSize,
MaybeHandle<Name>(), MaybeHandle<Map>(),
Type::Any(), MachineType::AnyTagged(),
kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
Node* branch = graph()->NewNode(common()->Branch(), check, control);
Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
Node* etrue = graph()->NewNode(simplified()->LoadField(access), object,
effect, if_true);
load_elimination.Reduce(etrue);
Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
Node* efalse = effect;
control = graph()->NewNode(common()->Merge(2), if_true, if_false);
effect = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, control);
load_elimination.Reduce(effect);
Node* load = graph()->NewNode(simplified()->LoadField(access), object, effect,
control);
Reduction r = load_elimination.Reduce(load);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(load, r.replacement());
}
TEST_F(LoadEliminationTest, LoadFieldWithTypeMismatch) {
Node* object = Parameter(Type::Any(), 0);
Node* value = Parameter(Type::Signed32(), 1);
Node* effect = graph()->start();
Node* control = graph()->start();
FieldAccess const access = {kTaggedBase, kTaggedSize,
MaybeHandle<Name>(), MaybeHandle<Map>(),
Type::Unsigned31(), MachineType::AnyTagged(),
kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
effect = graph()->NewNode(simplified()->StoreField(access), object, value,
effect, control);
load_elimination.Reduce(effect);
Node* load = graph()->NewNode(simplified()->LoadField(access), object, effect,
control);
EXPECT_CALL(editor, ReplaceWithValue(load, IsTypeGuard(value, _), _, _));
Reduction r = load_elimination.Reduce(load);
ASSERT_TRUE(r.Changed());
EXPECT_THAT(r.replacement(), IsTypeGuard(value, _));
}
TEST_F(LoadEliminationTest, LoadElementWithTypeMismatch) {
Node* object = Parameter(Type::Any(), 0);
Node* index = Parameter(Type::UnsignedSmall(), 1);
Node* value = Parameter(Type::Signed32(), 2);
Node* effect = graph()->start();
Node* control = graph()->start();
ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Unsigned31(),
MachineType::AnyTagged(), kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(graph()->start());
effect = graph()->NewNode(simplified()->StoreElement(access), object, index,
value, effect, control);
load_elimination.Reduce(effect);
Node* load = graph()->NewNode(simplified()->LoadElement(access), object,
index, effect, control);
Reduction r = load_elimination.Reduce(load);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(load, r.replacement());
}
TEST_F(LoadEliminationTest, AliasAnalysisForFinishRegion) {
Node* value0 = Parameter(Type::Signed32(), 0);
Node* value1 = Parameter(Type::Signed32(), 1);
Node* effect = graph()->start();
Node* control = graph()->start();
FieldAccess const access = {kTaggedBase, kTaggedSize,
MaybeHandle<Name>(), MaybeHandle<Map>(),
Type::Signed32(), MachineType::AnyTagged(),
kNoWriteBarrier};
StrictMock<MockAdvancedReducerEditor> editor;
LoadElimination load_elimination(&editor, jsgraph(), zone());
load_elimination.Reduce(effect);
effect = graph()->NewNode(
common()->BeginRegion(RegionObservability::kNotObservable), effect);
load_elimination.Reduce(effect);
Node* object0 = effect = graph()->NewNode(
simplified()->Allocate(Type::Any(), AllocationType::kYoung),
jsgraph()->Constant(16), effect, control);
load_elimination.Reduce(effect);
Node* region0 = effect =
graph()->NewNode(common()->FinishRegion(), object0, effect);
load_elimination.Reduce(effect);
effect = graph()->NewNode(
common()->BeginRegion(RegionObservability::kNotObservable), effect);
load_elimination.Reduce(effect);
Node* object1 = effect = graph()->NewNode(
simplified()->Allocate(Type::Any(), AllocationType::kYoung),
jsgraph()->Constant(16), effect, control);
load_elimination.Reduce(effect);
Node* region1 = effect =
graph()->NewNode(common()->FinishRegion(), object1, effect);
load_elimination.Reduce(effect);
effect = graph()->NewNode(simplified()->StoreField(access), region0, value0,
effect, control);
load_elimination.Reduce(effect);
effect = graph()->NewNode(simplified()->StoreField(access), region1, value1,
effect, control);
load_elimination.Reduce(effect);
Node* load = graph()->NewNode(simplified()->LoadField(access), region0,
effect, control);
EXPECT_CALL(editor, ReplaceWithValue(load, value0, effect, _));
Reduction r = load_elimination.Reduce(load);
ASSERT_TRUE(r.Changed());
EXPECT_EQ(value0, r.replacement());
}
} // namespace compiler
} // namespace internal
} // namespace v8