Class: Optimize::Passes::ArithReassocPass

Inherits:
Optimize::Pass show all
Defined in:
lib/optimize/passes/arith_reassoc_pass.rb

Overview

Arithmetic reassociation within a basic block, driven by REASSOC_GROUPS. See docs/superpowers/specs/2026-04-21-pass-arith-reassoc-v3-design.md.

Constant Summary collapse

REASSOC_GROUPS =

Each entry describes one commutative-associative group of operators:

ops:        opcode => Symbol method used to combine that op's RHS
            literal into the running accumulator. Insertion-ordered.
identity:   neutral element for the group (0 for +, 1 for *).
primary_op: opcode used to emit the single literal-carrying trailing
            op after a rewrite. Must be a key in `ops`.
kind:       selects the rewrite algorithm. :abelian uses v3's
            partition-by-combiner + inject-reduce (valid when all
            ops in the group commute and associate, e.g. +/-).
            :ordered walks the chain left-to-right with a single
            literal accumulator, used when the group contains a
            non-commutative op like opt_div.
associative:
            true:  same-op literal runs fold anywhere in the chain.
                   Sound when `(a op b) op c = a op (b op c)` — e.g.
                   `*` on Integer, and `/` on positive Integer (via
                   the `a/b/c = a/(b*c)` identity using the primary
                   op's combiner `:*`).
            false: same-op literal runs fold ONLY in the pure-literal
                   prefix, before any non-literal has been emitted.
                   Required for `%`: `(y%b)%c ≠ y%b` in general, so
                   `x % 7 % 3` must NOT fold, only `7 % 3 % x → 1%x`.
commutative:
            true:  the walker can keep accumulating literals past a
                   same-op non-literal (`2*3*x*4 → x*24`). Sound for
                   `*` (commutative) and `/` on positive Integer
                   (`(a/b)/c = (a/c)/b`).
            false: commit the pending literal accumulator before
                   emitting any non-literal. Required for `%`, which
                   neither commutes nor satisfies a cross-non-literal
                   identity.

[
  { ops: { opt_plus: :+, opt_minus: :- }, identity: 0, primary_op: :opt_plus, kind: :abelian },
  { ops: { opt_mult: :*, opt_div: :/    }, identity: 1, primary_op: :opt_mult, kind: :ordered,
    associative: true,  commutative: true },
  { ops: { opt_mod:  :% },                identity: nil, primary_op: :opt_mod,  kind: :ordered,
    associative: false, commutative: false },
].freeze
INTERN_BIT_LENGTH_LIMIT =

ObjectTable#intern accepts integers with bit_length < 62 (i.e. values in -(2^61)..(2^61)-1). Results outside this range cannot be interned and must be skipped.

62
SINGLE_PUSH_OPERAND_OPCODES =

Opcodes that each push exactly one value, pop zero, and have no side effects relevant to reordering literals past them. Shared across all REASSOC_GROUPS entries. Widening this list without re-examining the “all entries are side-effect-free w.r.t. each other” invariant would break the non-literal reordering rule used by the additive group.

(
  LiteralValue::LITERAL_OPCODES + %i[
    getlocal
    getlocal_WC_0
    getlocal_WC_1
    getinstancevariable
    getclassvariable
    getglobal
    putself
  ]
).freeze

Instance Method Summary collapse

Methods inherited from Optimize::Pass

#one_shot?

Instance Method Details

#apply(function, type_env:, log:, object_table: nil, **_extras) ⇒ Object 



76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# File 'lib/optimize/passes/arith_reassoc_pass.rb', line 76

def apply(function, type_env:, log:, object_table: nil, **_extras)
  _ = type_env
  return unless object_table
  insts = function.instructions
  return unless insts

  # Outer any-rewrite fixpoint: a rewrite in one group can expose chains
  # in another group (e.g. mult folding `2 * 3 → 6` exposes a + chain
  # that plus missed on its first visit). See spec "Two-level fixpoint".
  loop do
    any_outer = false
    REASSOC_GROUPS.each do |group|
      loop do
        break unless rewrite_once(insts, function, log, object_table, group: group)
        any_outer = true
      end
    end
    break unless any_outer
  end
end

#name ⇒ Object 



74
 
# File 'lib/optimize/passes/arith_reassoc_pass.rb', line 74

def name = :arith_reassoc