Skip to content
  • Faith Ekstrand's avatar
    nir/search: Search for all combinations of commutative ops · 50f3535d
    Faith Ekstrand authored
    
    
    Consider the following search expression and NIR sequence:
    
        ('iadd', ('imul', a, b), b)
    
        ssa_2 = imul ssa_0, ssa_1
        ssa_3 = iadd ssa_2, ssa_0
    
    The current algorithm is greedy and, the moment the imul finds a match,
    it commits those variable names and returns success.  In the above
    example, it maps a -> ssa_0 and b -> ssa_1.  When we then try to match
    the iadd, it sees that ssa_0 is not b and fails to match.  The iadd
    match will attempt to flip itself and try again (which won't work) but
    it cannot ask the imul to try a flipped match.
    
    This commit instead counts the number of commutative ops in each
    expression and assigns an index to each.  It then does a loop and loops
    over the full combinatorial matrix of commutative operations.  In order
    to keep things sane, we limit it to at most 4 commutative operations (16
    combinations).  There is only one optimization in opt_algebraic that
    goes over this limit and it's the bitfieldReverse detection for some UE4
    demo.
    
    Shader-db results on Kaby Lake:
    
        total instructions in shared programs: 15310125 -> 15302469 (-0.05%)
        instructions in affected programs: 1797123 -> 1789467 (-0.43%)
        helped: 6751
        HURT: 2264
    
        total cycles in shared programs: 357346617 -> 357202526 (-0.04%)
        cycles in affected programs: 15931005 -> 15786914 (-0.90%)
        helped: 6024
        HURT: 3436
    
        total loops in shared programs: 4360 -> 4360 (0.00%)
        loops in affected programs: 0 -> 0
        helped: 0
        HURT: 0
    
        total spills in shared programs: 23675 -> 23666 (-0.04%)
        spills in affected programs: 235 -> 226 (-3.83%)
        helped: 5
        HURT: 1
    
        total fills in shared programs: 32040 -> 32032 (-0.02%)
        fills in affected programs: 190 -> 182 (-4.21%)
        helped: 6
        HURT: 2
    
        LOST:   18
        GAINED: 5
    
    Reviewed-by: default avatarThomas Helland <thomashelland90@gmail.com>
    50f3535d