Skip to content

Commit 6048f75

Browse files
tebbiV8 LUCI CQ
tebbi
authored and
V8 LUCI CQ
committed
[compiler] make CanCover() transitive
In addition to checking that a node is owned, CanCover() also needs to check if there are any side-effects in between the current node and the merged node. When merging inputs of inputs, this check was done with the wrong side-effect level of the in-between node. We partially fixed this before with `CanCoverTransitively`. This CL addresses the issue by always comparing to the side-effect level of the node from which we started, making `CanCoverTransitively` superfluous. Bug: chromium:1336869 Change-Id: I78479b32461ede81138f8b5d48d60058cfb5fa0a Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3707277 Reviewed-by: Clemens Backes <[email protected]> Commit-Queue: Tobias Tebbi <[email protected]> Cr-Commit-Position: refs/heads/main@{#81217}
1 parent 5b9401d commit 6048f75

6 files changed

Lines changed: 14 additions & 29 deletions

File tree

‎src/compiler/backend/instruction-selector.cc‎

Lines changed: 4 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -284,15 +284,15 @@ Instruction* InstructionSelector::Emit(Instruction* instr) {
284284

285285
bool InstructionSelector::CanCover(Node* user, Node* node) const {
286286
// 1. Both {user} and {node} must be in the same basic block.
287-
if (schedule()->block(node) != schedule()->block(user)) {
287+
if (schedule()->block(node) != current_block_) {
288288
return false;
289289
}
290290
// 2. Pure {node}s must be owned by the {user}.
291291
if (node->op()->HasProperty(Operator::kPure)) {
292292
return node->OwnedBy(user);
293293
}
294294
// 3. Impure {node}s must match the effect level of {user}.
295-
if (GetEffectLevel(node) != GetEffectLevel(user)) {
295+
if (GetEffectLevel(node) != current_effect_level_) {
296296
return false;
297297
}
298298
// 4. Only {node} must have value edges pointing to {user}.
@@ -304,21 +304,6 @@ bool InstructionSelector::CanCover(Node* user, Node* node) const {
304304
return true;
305305
}
306306

307-
bool InstructionSelector::CanCoverTransitively(Node* user, Node* node,
308-
Node* node_input) const {
309-
if (CanCover(user, node) && CanCover(node, node_input)) {
310-
// If {node} is pure, transitivity might not hold.
311-
if (node->op()->HasProperty(Operator::kPure)) {
312-
// If {node_input} is pure, the effect levels do not matter.
313-
if (node_input->op()->HasProperty(Operator::kPure)) return true;
314-
// Otherwise, {user} and {node_input} must have the same effect level.
315-
return GetEffectLevel(user) == GetEffectLevel(node_input);
316-
}
317-
return true;
318-
}
319-
return false;
320-
}
321-
322307
bool InstructionSelector::IsOnlyUserOfNodeInSameBlock(Node* user,
323308
Node* node) const {
324309
BasicBlock* bb_user = schedule()->block(user);
@@ -1196,6 +1181,7 @@ void InstructionSelector::VisitBlock(BasicBlock* block) {
11961181
int effect_level = 0;
11971182
for (Node* const node : *block) {
11981183
SetEffectLevel(node, effect_level);
1184+
current_effect_level_ = effect_level;
11991185
if (node->opcode() == IrOpcode::kStore ||
12001186
node->opcode() == IrOpcode::kUnalignedStore ||
12011187
node->opcode() == IrOpcode::kCall ||
@@ -1213,6 +1199,7 @@ void InstructionSelector::VisitBlock(BasicBlock* block) {
12131199
// control input should be on the same effect level as the last node.
12141200
if (block->control_input() != nullptr) {
12151201
SetEffectLevel(block->control_input(), effect_level);
1202+
current_effect_level_ = effect_level;
12161203
}
12171204

12181205
auto FinishEmittedInstructions = [&](Node* node, int instruction_start) {

‎src/compiler/backend/instruction-selector.h‎

Lines changed: 6 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -407,15 +407,12 @@ class V8_EXPORT_PRIVATE InstructionSelector final {
407407
// Used in pattern matching during code generation.
408408
// Check if {node} can be covered while generating code for the current
409409
// instruction. A node can be covered if the {user} of the node has the only
410-
// edge and the two are in the same basic block.
411-
// Before fusing two instructions a and b, it is useful to check that
412-
// CanCover(a, b) holds. If this is not the case, code for b must still be
413-
// generated for other users, and fusing is unlikely to improve performance.
410+
// edge, the two are in the same basic block, and there are no side-effects
411+
// in-between. The last check is crucial for soundness.
412+
// For pure nodes, CanCover(a,b) is checked to avoid duplicated execution:
413+
// If this is not the case, code for b must still be generated for other
414+
// users, and fusing is unlikely to improve performance.
414415
bool CanCover(Node* user, Node* node) const;
415-
// CanCover is not transitive. The counter example are Nodes A,B,C such that
416-
// CanCover(A, B) and CanCover(B,C) and B is pure: The the effect level of A
417-
// and B might differ. CanCoverTransitively does the additional checks.
418-
bool CanCoverTransitively(Node* user, Node* node, Node* node_input) const;
419416

420417
// Used in pattern matching during code generation.
421418
// This function checks that {node} and {user} are in the same basic block,
@@ -749,6 +746,7 @@ class V8_EXPORT_PRIVATE InstructionSelector final {
749746
BoolVector defined_;
750747
BoolVector used_;
751748
IntVector effect_level_;
749+
int current_effect_level_;
752750
IntVector virtual_registers_;
753751
IntVector virtual_register_rename_;
754752
InstructionScheduler* scheduler_;

‎src/compiler/backend/loong64/instruction-selector-loong64.cc‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1448,7 +1448,7 @@ void InstructionSelector::VisitTruncateInt64ToInt32(Node* node) {
14481448
if (CanCover(node, value)) {
14491449
switch (value->opcode()) {
14501450
case IrOpcode::kWord64Sar: {
1451-
if (CanCoverTransitively(node, value, value->InputAt(0)) &&
1451+
if (CanCover(value, value->InputAt(0)) &&
14521452
TryEmitExtendingLoad(this, value, node)) {
14531453
return;
14541454
} else {

‎src/compiler/backend/mips64/instruction-selector-mips64.cc‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1534,7 +1534,7 @@ void InstructionSelector::VisitTruncateInt64ToInt32(Node* node) {
15341534
if (CanCover(node, value)) {
15351535
switch (value->opcode()) {
15361536
case IrOpcode::kWord64Sar: {
1537-
if (CanCoverTransitively(node, value, value->InputAt(0)) &&
1537+
if (CanCover(value, value->InputAt(0)) &&
15381538
TryEmitExtendingLoad(this, value, node)) {
15391539
return;
15401540
} else {

‎src/compiler/backend/riscv64/instruction-selector-riscv64.cc‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1481,7 +1481,7 @@ void InstructionSelector::VisitTruncateInt64ToInt32(Node* node) {
14811481
if (CanCover(node, value)) {
14821482
switch (value->opcode()) {
14831483
case IrOpcode::kWord64Sar: {
1484-
if (CanCoverTransitively(node, value, value->InputAt(0)) &&
1484+
if (CanCover(value, value->InputAt(0)) &&
14851485
TryEmitExtendingLoad(this, value, node)) {
14861486
return;
14871487
} else {

‎src/compiler/backend/x64/instruction-selector-x64.cc‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1824,7 +1824,7 @@ void InstructionSelector::VisitTruncateInt64ToInt32(Node* node) {
18241824
case IrOpcode::kWord64Shr: {
18251825
Int64BinopMatcher m(value);
18261826
if (m.right().Is(32)) {
1827-
if (CanCoverTransitively(node, value, value->InputAt(0)) &&
1827+
if (CanCover(value, value->InputAt(0)) &&
18281828
TryMatchLoadWord64AndShiftRight(this, value, kX64Movl)) {
18291829
return EmitIdentity(node);
18301830
}

0 commit comments

Comments
 (0)