KhronosGroup / KhronosGroup/SPIRV-Tools

[spirv-opt] Reassociation Pass

Open
#6,407 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
1.4k
Forks
709
Avg merge
1d 22h
Merged PRs (30d)
28

Description

Hey,

Currently folding rules act on a instruction-by-instruction basis, which works for a lot of cases, but struggles to deal with temporaries in the middle of an expression.

e.g:
```
10 + a + 10 => a + 20
10 + b + a + 10 => no fold

(3 * a) + (-3 *a) => 0
(3 * a) + 1 + (-3 *a) => no fold

(3 * a) + (3 * b) => 3 * (a + b)
(3 * a) + c + (3 * b) => no fold
```

Because each rule would need to account for every possibility and combination, it's not very practical to
make rules for these sorts of situations.

Locally I've been working on a reassociation pass (for FP arithmetic) and was wondering if it is something that you would want (since it's not simply adding extra folding rules).

The general premise is to reassociate independant chains of: `OpFAdd`, `OpFSub`, `OpFNegate`, `OpFMul`, `OpFDiv`, `OpVectorTimesScalar`.

Constants are moved closer together e.g:
```
(A + 5 + B - C - 7) => (5 - 7 + A + B - C) => (-2 + A + B - C)
(A * 5 * B * C * 7) => (5 * 7 * A * B * C) => (35 * A * B * C)
```

Variables far apart can cancel each other out e.g:
```
(A + B + C - A - B) => C
(A * B * C / (A * B)) => C
```

Variables can be factored e.g:
```
(A * x * x + B * x + C) => x * (A * x + B) + C
A * x + B * x + C * x => x * (A + B + C)
```

With a few extra folding rules that operate on the chains directly.

Many thanks,
Alister

Contributor guide

Open the contributing guide

Research direction

The issue names no source file or test; begin at the spirv-opt optimizer and trace handling of the listed floating-point operations. Done would require an agreed reassociation-pass scope, implementation, and coverage for the constant movement, cancellation, and factoring examples.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.