Skip to content

Additional missing known bits info for x * x #151043

@ZERICO2005

Description

@ZERICO2005

#48027 outlines that x * x will always have bit 1 cleared. I have also discovered three additional tricks that can resolve additional unknown bits:

A: If bit 0 of the input is set, then bit 2 of the output must be cleared.
B: If bit 0 of the input is cleared, then bit 3 of the output must be cleared.
C: If the input % 4 == 2, then bits 3 and 4 of the output must be cleared.

Alternatively, A and C can be rephrased as:

A: If bit 0 of the output is set, then bit 2 of the output must be cleared.
C: If bit 2 of the output is set, then bits 3 and 4 of the output must be cleared.

This is because these are the only possible results for (x * x) % 32:

00: 00000
01: 00001
04: 00100
09: 01001
10: 10000
11: 10001
19: 11001

The transformations appear to be valid in alive2:
A: https://alive2.llvm.org/ce/z/wip7Ue
B: https://alive2.llvm.org/ce/z/5etB7b
C: https://alive2.llvm.org/ce/z/BNzk7L

Clang 20.1.0 doesn't optimize these patterns out currently https://godbolt.org/z/M6rj4cG3T.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions