Closed Bug 1767966 Opened 4 years ago Closed 4 years ago

Improve codegen for test expressions

Categories

(Core :: JavaScript Engine: JIT, enhancement)

Product:
Core
Component:
JavaScript Engine: JIT
Type:
enhancement

Tracking

()

Status:
RESOLVED FIXED
Milestone:
102 Branch
Tracking Flags:
Tracking Status
firefox102 --- fixed

People

(Reporter: anba, Assigned: anba)

References

Details

Attachments

(13 files, 1 obsolete file)

Bug 1767966 - Part 1: Add MaybeFoldDiamondConditionBlock. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 2: Don't require diamond pattern. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 3: Support triangle pattern when folding test blocks. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 4: Handle '!!' idiom in BlockIsSingleTest. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 5: Handle '!!' idiom when comparing test input. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 7: Handle JumpTarget in EliminateTriviallyDeadResumePointOperands. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 8: Add spew pass after removing dead resume point operands. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 9: Remove trivially dead resume point operands before folding tests. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 10: Use post-order traversal when folding tests. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 11: Fold test pattern with more than two operands. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 12: Don't add extra split-edges when we don't fold tests. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 13: Remove defunkt constant test condition code. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
Bug 1767966 - Part 14: Merge both loops in FoldTests. r=jandem!
48 bytes, text/x-phabricator-request
Details | Review
No description provided.

Split MaybeFoldConditionBlock into two functions:

  1. IsDiamondPattern which is a predicate to test if the diamond pattern applies.
  2. MaybeFoldDiamondConditionBlock to fold the diamond pattern.

This is in preparation for part 3.

Doesn't result in any change of behaviour.

Stop creating the diamond structure when building JSOp::JumpTarget, which
leads to creating a triangle pattern for short-circuit operations. The next
part will add support for optimising this triangle pattern.

Depends on D145588

Support the triangle pattern in MaybeFoldConditionBlock. The code is based
on what we're already using in MaybeFoldDiamondConditionBlock.

This change has two benefits:

  1. We no longer have to create the diamond pattern in WarpBuilder (part 2).
  2. And we're no longer extending the liveness of the first operand of a
    short-circuit expression: The liveness was extended into the empty block
    of the diamond pattern, which prevents to emit the first operand at its
    uses during lowering.

Depends on D145589

BlockIsSingleTest doesn't handle the '!!' idiom which may have been added by
WarpCacheIRTranspiler::convertToBoolean().

This improves the codegen for if (a && b) { ... } where a and b are both
int32 values.

From:

# ebx = a
# edx = b

test %ebx, %ebx
jnz .L1

mov %ebx, %edx
set .L1
test %edx, %edx
jz .L2

To:

# ebx = a
# edx = b

test %ebx, %ebx
jz .L2

test %edx, %edx
jz .L2

Depends on D145590

This improves the codegen for if (a ? b : a) { ... } where a and b are
both int32 values.

From

# edx = a
# ebx = b

test %edx, %edx
jz .L1

test %ebx, %ebx
jz .L2
jmp .L3

set .L1
test %edx, %edx
jz .L2

To:

# edx = a
# ebx = b

test %edx, %edx
jz .L2

test %ebx, %ebx
jz .L2

Depends on D145591

Handle the cases from parts 4-5 when the inputs can be boxed.

Depends on D145592

This code no longer worked correctly when JSOp::JumpTarget was added.

This improves the codegen for if (a < 10 && b < 20) { ... } where a and b
are both int32 values.

From:

# ebx = a
# edx = b

cmp $0x0A, %ebx
setl %bpl
movzx %bpl, %ebp
test %ebp, %ebp
jz .L1

cmp $0x14, %edx
jnl .L1

To:

# ebx = a
# edx = b

cmp $0x0A, %ebx
jnl .L1

cmp $0x14, %edx
jnl .L1

Also see bug 1028580, bug 1045749, and bug 913935 for the initial work on this
issue.

Depends on D145593

This helps to verify the changes from the previous parts.

Depends on D145594

Removing trivially dead resume points adds optimised-out constants, which now
have to be handled in MBasicBlock::NewSplitEdge().

This allows more aggressive optimisations in the next part.

Depends on D145595

This improves the codegen for if ((a < 10 && b < 20) || c < 30) { ... } where
a, b, and c are all int32 values.

From:

# esi = a
# ebp = b
# edx = c

cmp $0x0A, %esi
setl %bl
movzx %bl, %ebx
test %ebx, %ebx
jz .L1

cmp $0x14, %ebp
setl %bl
movzx %bl, %ebx
set .L1
test %ebx, %ebx
jnz .L2

cmp $0x1E, %edx
jnl .L3

To:

# ebx = a
# ebp = b
# edx = c

cmp $0x0A, %ebx
jnl .L1

cmp $0x14, %ebp
jl .L2

set .L1
cmp $0x1E, %edx
jnl .L3

Depends on D145596

This is basically an extension of MaybeFoldTriangleConditionBlock to handle
more than two operands. It doesn't support all optimisations which are
performed in MaybeFoldTriangleConditionBlock, so we keep both functions for
now.

MaybeFoldTriangleConditionBlock also has a stricter requirement that there
are no intervening blocks, e.g. when phiBlock != falseBranch, then the
single predecessor of trueBranch has to be initialBlock. This requirement
isn't used here, because it doesn't seem to matter resp. without this
requirement we can optimise more cases.

This improves the codegen for if (a < 10 && b < 20 && c < 30) { ... } where
a, b, and c are all int32 values.

From:

# esi = a
# ebp = b
# ebx = c

cmp $0x0A, %esi
setl %dl
movzx %dl, %edx
test %edx, %edx
jz .L1

cmp $0x14, %ebp
setl %dl
movzx %dl, %edx
test %edx, %edx
jz .L1

cmp $0x1E, %ebx
setl %dl
movzx %dl, %edx
set .L1
test %edx, %edx
jz .L2

To:

# edx = a
# ebp = b
# ebx = c

cmp $0x0A, %edx
jnl .L2

cmp $0x14, %ebp
jnl .L2

cmp $0x1E, %ebx
jnl .L2

Depends on D145597

Only call SplitCriticalEdgesForBlock when we actually modify the graph.

This improves the codegen for if ((a < 10 && b < 20) || (c < 30 && d < 40)) { ... },
where all inputs are int32 values.

From:

cmp $0x0A, %edi
setl %dl
movzx %dl, %edx
test %edx, %edx
jz .L1

cmp $0x14, %esi
setl %dl
movzx %dl, %edx
set .L1
test %edx, %edx
jnz .L2

cmp $0x1E, %ebp
setl %dl
movzx %dl, %edx
test %edx, %edx
jz .L2

cmp $0x28, %ebx
setl %dl
movzx %dl, %edx
set .L2
test %edx, %edx
jz .L3

To:

cmp $0x0A, %edi
setl %sil
movzx %sil, %esi
test %esi, %esi
jz .L1

cmp $0x14, %ebp
setl %sil
movzx %sil, %esi
set .L1
test %esi, %esi
jnz .L2

cmp $0x1E, %edx
jnl .L3

cmp $0x28, %ebx
jnl .L3

Depends on D145598

The two tests !value->isConstant() and value->block() != block in
BlockComputesConstant have established these conditions:

  1. value is a MConstant
  2. value is part of block

So when iterating over all iterations in block, the test
*iter != value || !iter->isGoto() is always true. The code can be rewritten as:

if (*iter != value) {
  return false;
}
if (!iter->isGoto()) {
  return false;
}

When *iter is equal to value, it can't be a MGoto instruction, because
value is a MConstant.

Instead the loop should watch out for any instructions which are neither value
nor a MGoto, that means || should have been &&.

Fixing this typo revealed two bugs, which were never noticed because the code
was never actually run:

  1. When we remove blocks which compute a constant, we may end up with unreachable
    blocks. This leads to errors in later passes.
  2. When both arms of a test compute the same constant, the initial test will have
    a single predecessor. In that case we would need to replace the test instruction
    with a goto instruction.

Because this optimisation never really worked and because GVN handles a similar
case, let's just remove this code.

Depends on D145599

This improves the codegen for if ((a < 10 && b < 20) || (c < 30 && d < 40)) { ... },
where all inputs are int32 values.

From:

cmp $0x0A, %edi
setl %sil
movzx %sil, %esi
test %esi, %esi
jz .L1

cmp $0x14, %ebp
setl %sil
movzx %sil, %esi
set .L1
test %esi, %esi
jnz .L2

cmp $0x1E, %edx
jnl .L3

cmp $0x28, %ebx
jnl .L3

To:

cmp $0x0A, %ebp
jnl .L1

cmp $0x14, %esi
jl .L2

set .L1
cmp $0x1E, %edx
jnl .L3

cmp $0x28, %ebx
jnl .L3

Depends on D145600

Pushed by andre.bargull@gmail.com: https://hg.mozilla.org/integration/autoland/rev/70707e53a9ee Part 1: Add MaybeFoldDiamondConditionBlock. r=jandem https://hg.mozilla.org/integration/autoland/rev/99af6775b319 Part 2: Don't require diamond pattern. r=jandem https://hg.mozilla.org/integration/autoland/rev/67090396b390 Part 3: Support triangle pattern when folding test blocks. r=jandem https://hg.mozilla.org/integration/autoland/rev/59366e1dc540 Part 4: Handle '!!' idiom in BlockIsSingleTest. r=jandem https://hg.mozilla.org/integration/autoland/rev/7a0169499381 Part 5: Handle '!!' idiom when comparing test input. r=jandem https://hg.mozilla.org/integration/autoland/rev/b3b4b19b2fec Part 6: Handle boxed values in single-test blocks. r=jandem https://hg.mozilla.org/integration/autoland/rev/ced617b7e00b Part 7: Handle JumpTarget in EliminateTriviallyDeadResumePointOperands. r=jandem https://hg.mozilla.org/integration/autoland/rev/a1613ea8230a Part 8: Add spew pass after removing dead resume point operands. r=jandem https://hg.mozilla.org/integration/autoland/rev/1674c53f5c94 Part 9: Remove trivially dead resume point operands before folding tests. r=jandem https://hg.mozilla.org/integration/autoland/rev/ce5d1b1d8dc5 Part 10: Use post-order traversal when folding tests. r=jandem https://hg.mozilla.org/integration/autoland/rev/7f4338c9d68d Part 11: Fold test pattern with more than two operands. r=jandem https://hg.mozilla.org/integration/autoland/rev/6e18e578d998 Part 12: Don't add extra split-edges when we don't fold tests. r=jandem https://hg.mozilla.org/integration/autoland/rev/f87376dd2418 Part 13: Remove defunkt constant test condition code. r=jandem https://hg.mozilla.org/integration/autoland/rev/e59acdccc25b Part 14: Merge both loops in FoldTests. r=jandem
Regressions: 1768346
Blocks: 1768790
Regressions: 1769220
Regressions: 1769209
Attachment #9275209 - Attachment is obsolete: true
Regressions: CVE-2026-4698
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: