External code optimizer (eventually with AI) for MPLAB X generated code

[microvia]

Hi,

Is there a specific code optimizer that can work on the code generated by MPLAB X, even with an AI and showing before/after results for those who want to understand or verify the optimizations, or even allow/remove parts of those optimizations in critical areas ?

[JPortici]

what?
you mean a "developer"?

[radiolistener]

Oh, I wish that optimizer too! Just imagine - I feed it some messy code, lean back with a glass of wine and it shows me a beautiful "before/after" diff like a makeover show. Then I just press a big shiny and beautiful button: "Yes, I like it!" or "Nah, try again" - and it keeps refining until I will be satisfied. 

[radiolistener]

 

[microvia]

I meant something equivalent to the -o options under MPLABX, but performed by a separate tool which takes the asm generated by MPLABX to try optimizing when possible.
The before/after is an idea, which can't work with multi-level optimizations unless you record every optimization step.

What would be really interesting is a tool which improves your C source to save program memory and/or speed up, like the tricks seen at https://www.embedded.com/10-simple-tricks-to-optimize-your-c-code-in-small-embedded-systems/. I think this differs from post-compilation optimizations.

[JPortici]

you mean taking the output of an optimizing compiler and optimizing it even further?
again, that's going to take a human, probably.

Because the human can actually understand context, the big picture, and apply tricks the compiler can't guarantee for (or it would use them).

The problem is, the output of an optimizing compiler, at higher levels, can create partterns that are difficult to analyze, and further optimize. And a human capable of doing that would probably not bother, he would rewrite the thing in assembly directly.

In any case, it usually doesn't matter. A program can be divided in logic and stuff that doesn't need to happen at microsecond rate and time critical code that can be optimized, but usually the compiler already does a good job, or the time critical code is rewritten in assembly.

However, if you mean to take an autogenerated mess (such as the clusterfuck generated by MCC, or crap from "AI") and convert it to efficient code... automated tools will never make it. Just hire/become a competent developer.

[hans]

I'm trying to understand what the compiler in MPLAB won't do which this tool must then take over.
Or is this to work around Microchip's paid optimization levels?

All but 8-bit PICs C compilers from microchip are based on GCC. If you enable LTO and set them to level O2 or O3 of optimization, you will see very remarkable optimizations that are almost (not quite) impossible to do by hand, and frankly I think this is exactly the tool you're asking for. Even without LTO its hard to recognize the original program when its compiled and linked together.
 
When I'm looking at assembly output in my own programs, and see which instruction corresponds to which line of code in C(++), then its incredibly dense. Basically it can execute code from 5 different functions within a dozen instructions.

But, "bad code" it cannot optimize as much. In fact, in order to do that effectively, its probably better to architect this at the higher abstraction level (which is your program code). High level design choices, such as how your program structures and uses memory, tends to have a much bigger impact than (manually) shaving off a few ALU or load instructions here and there.

[jfiresto]

I meant something equivalent to the -o options under MPLABX, but performed by a separate tool which takes the asm generated by MPLABX to try optimizing when possible.
The before/after is an idea, which can't work with multi-level optimizations unless you record every optimization step.
...

I did something like that for avr-gcc. I wrote a Python package that fixed avr-gcc's missed optimizations. It optimized the code within each assembly language function, and used a simple DSL to identify and express the individual, function-level transformations. Here is an example that I wrote over a couple days that fixed all but one missed optimization in a program, leaving one wasted word:

Code: [Select]

#!/usr/bin/env python
"""Perform various, post-compile .S code optimizations.

Read the source lines from an assembly file on stdin, call each of the
functions, let them edit the lines, then output the lines to stdout.

BUG: The changed lines lose their trailing spaces and tabs.
"""
# This program was prompted by avr-gcc 3.4.6 which doesn't use 'lpm rn, z[+]'
# or 'movw' instructions when targeting an ATtiny24; avr-gcc 4.2+ apparently
# does.

from fleo.target.avr import *


@rolling_optimizer
@disabled
def _dump_initial_needed(lines):
    lines.dump_needed()
    log('')
    return -lines.end


@rolling_optimizer(on_code_error=-1, start='and | or')
def delete_needless_tst(lines, match):
    """Delete a needless TST instruction after an AND / OR.

    An example:
                or r18,r19                  or r18,r19
        .L7:                 ---\   .L7:
                tst r18      ---/
                brne .L7                    brne .L7
    """
    # Upon finding an AND/OR instruction, search the next 10 lines for a TST.
    # If there is none or if it does not test the AND/OR's result, return,
    # discard the AND/OR line, and try again.
    #
    i_tst = lines.find_lines('tst', start=1, end=11).start
    if i_tst < 0 or lines[0].xR != lines[i_tst].xR:
        return -1

    # Collect the indices of the lines that reference any labels between the
    # AND/OR and the TST.  If any instructions come between the two, return,
    # discard the lines before the first instruction, and try again.
    #
    references = []
    for line in lines[1:i_tst]:
        if line.M:
            return -1
        references += line.from_indices

    # If the line after the TST references a label between the AND/OR and TST,
    # ignore the branch instruction's one reference. If there are no other
    # references or there were none at all, white out the test instruction.
    # Return and report the lines through the TST instruction are done.
    #
    if len(references) <= (i_tst + 1) in references:
        lines[i_tst] = ''
    return i_tst + 1


@rolling_optimizer(requires='movw', start="""
    mov
    mov
""")
def movw_for_2x_mov(lines, match):
    """Try to replace MOV instruction pairs with single MOVW instructions.

    Replace pairs of the form

        mov r<n+1>,r<m+1>
        mov r<n>,r<m>

    and its three variants, with

        movw r<n>,r<m>
    """
    # If only the first MOV matched, return, discard it and the following
    # non-MOV instruction, and try again.
    #
    if len(match) < 2:
        return -2

    # Confirm the two MOV instructions move a consecutive, (2n, 2n+1), word
    # register pair to another. If they do not, return, discard the first MOV
    # and try again.
    #
    (d1, s1) = lines[0].xRR
    (d2, s2) = lines[1].xRR
    if not (d1 - d2 == s1 - s2 and abs(d1 - d2) == 1 and
            min(d1, d2) % 2 == min(s1, s2) % 2 == 0):
        return -1

    # White out the first MOV and replace the second with a MOVW.  Return that
    # the two move lines are done.
    #
    lines[:2] = ['',
                 'movw r%d,r%d' % (d1 & ~1, s1 & ~1)]
    return 2


@rolling_optimizer(start="""
    subi
    sbci
    out
    out
    subi
    sbci
""")
def movw_for_sub_out_sub(lines, match):
    """Use a 'movw' and 2 registers to shrink a subtract-out-subtract sequence.

    An example:
        subi r20,lo8(-(924))
        sbci r21,hi8(-(924))          movw r24,r20
        out (74)+1-0x20,r21     --\   subi r24,100
        out 74-0x20,r20         --/   sbci r25,252
        subi r20,lo8(-(-924))         out 43,r25
        sbci r21,hi8(-(-924))         out 42,r24
    """
    # Return and discard a partial match, but to just shy of the second word
    # subtraction (discard no more than the first four lines).
    #
    if len(match) < 6:
        return -min(4, match.end)

    # Return and discard the first four lines if the six lines do not subtract
    # and output a word register pair.
    #
    port = lines[3].xE
    word_reg = lines[0].xR
    if not (port == lines[2].xE - 1 and port % 2 == word_reg % 2 == 0 and
            word_reg == lines[1].xR - 1 == lines[2].xxR - 1 ==
                lines[3].xxR == lines[4].xR == lines[5].xR - 1):
        return -4

    # Return and discard the first four lines if the second subtract does not
    # undo the first one.
    #
    c0 = lines[0].xxE
    c1 = lines[1].xxE
    if not (c0 + lines[4].xxE == c1 + lines[5].xxE + 1 == 256):
        return -4

    # Find a free scratch register pair. Return and discard the first four
    # lines if no pair is available.
    #
    scratch_reg = lines.find_unneeded_reg_pair(end=6)
    if scratch_reg is None:
        return -4

    # White out the first line and add lines to: move the word value to the
    # scratch registers, do the first subtract and output the result. Return
    # that all six lines are done and the scratch registers have been
    # clobbered.
    #
    lines[:2] = ['',
                 'movw r%d,r%d' % (scratch_reg, word_reg)]
    lines[2:6] = remapped(lines[:4], {word_reg: scratch_reg,
                                      word_reg+1: scratch_reg+1})
    return 6


@optimizer(on_code_error=-2, start="""
    rcall
    mov
""")
def shed_returned_byte_move(lines, i, match):
    """Eliminate a needless move of a function's returned byte value register.

    Where possible, use the register instead until an instruction changes
    it. Then swap the register and the one it was moved to: until they are
    no longer needed.

    BUG: An IJMP instruction anywhere in a source extract, for example, in
         a jump-table switch statement, may disable this optimzation.
    """
    # Return, discard the RCALL line and try again if it alone matched.
    # Otherwise, white out the first MOV line.
    #
    if len(match) < 2:
        return 1
    (dst, src) = lines[i+1].xRR       # MOV's destination and source registers
    lines[i+1] = ''

    # Starting from after the MOV, progress through the source lines that need
    # the virgin source register, and record the walk. If a line writes the
    # source and/or destination register, or imports one or both, return and
    # try again. Return likewise if there was no code to walk.
    #
    @lines.progress_with(follow={src}, start=i+2, embargo={dst, src})
    def virgin_src(line, i):
        if line.writes & {dst, src}:
            code_error('line writes dst or src')

    # Wander the lines, after the whited-out MOV, that need the source and/or
    # destination registers. Replace each virgin destination register operand
    # with the virgin source register; swap the two registers, everywhere else.
    # If there were not errors, return that the two match lines are done
    # and commit the changes.
    #
    @lines.wander_with(start=i+2, avoid={i+1}, follow=[dst, src])
    def dst_or_src(line, i):
        lines[i] = (line.remap({dst: src}) if (i in virgin_src) else
                    line.swap({dst:src}))

    return 2


@rolling_optimizer(requires='lpm+', start='lpm')
def use_fancier_lpm(lines, match):
    """Use fancier LPM instructions to shrink LPM code blocks.

        lpm
        mov rn,r0  -->  lpm rn,z

        lpm
        mov rn,r0
        adiw z,1   -->  lpm rn,z+

        lpm rn,z
        adiw z,1   -->  lpm rn,z+

    where 'rn' is any register.
    """
    # If we can't improve the LPM because it is already 'LPM Rn, Z+', return,
    # discard the line and try again. Otherwise, count the first match.
    #
    if lines[0].xxS.endswith('+'):
        return -1
    regnum = lines[0].xR or 0
    n = 1

    # If a 'MOV Rn', R0 follows an LPM or 'LPM R0, Z', white out the LPM line,
    # change the MOV to 'LPM RN,Z' and count the match.
    #
    if regnum == 0 and lines.get(1).MxR == ('mov', 0):
        regnum = lines[1].xR
        lines[:2] = ['',
                     'lpm r%d,z' % regnum]
        n += 1

    # If the second or third line is an 'ADIW R30, 1' and the next line does
    # not need a status flag the second or third line sets, white out the
    # previous LPM line, replace the ADIW with 'LPM Rn, Z+' and count the
    # match. Return that the 1 to 3 matched lines are done.
    #
    if lines.get(n).MRE == ('adiw', 30, 1):
        if not lines[n].exports_at_end('svnzc'):
            lines[n-1:n+1] = ['',
                              'lpm r%d,z+' % regnum]
            n += 1
    return n


@optimizer(on_code_error=-3, start="""
    mov
    clr
    ret
""")
def shed_return_byte_move(lines, i, match):
    """Eliminate a needless move to r24 in a function returning a byte value.

    White out the MOV, use R24 as the register with the function's return
    value, and a free register pair for R24 and R25.
    """
    # Return and discard a partial match, or a full match if: there is nothing
    # before the MOV, the MOV maybe skipped or the function does not return a
    # byte value. Otherwise, white out the MOV line.
    #
    if len(match) < 3:
        return -match.end
    (dst, src) = lines[i].xRR
    if not i or lines[i].maybe_skipped or dst != 24 or lines[i+1].xR != 25:
        return -3
    lines[i] = ''

    # Wander the lines before the whited-out MOV that are connected with the
    # return that uses r24, r25 and with the register that sources the
    # function's return value (src). Try to get a word register pair the lines
    # do not use. If there is no free pair, return and try again.
    #
    dst_or_src = lines.wander_with(None, start=i-1, avoid=[i],
                                   follow=[24, 25, src])
    temp = lines(dst_or_src).find_unneeded_reg_pair()
    if temp is None:
        return -3

    # White out the 'mov r24, <src>' line and remap the registers used over the
    # wandered lines. Remap R24 and R25 to the free register pair, and the
    # return value source register to R24. Return that the lines through the
    # three matched lines are done, and commit the changes if all the
    # instructions allowed the register remapping.
    #
    lines(dst_or_src).remap({dst & ~1: temp, dst | 1: temp + 1, src: dst})
    return 3


# ------------------------------------------------------------------------
# NOTE: Do the following optimization, last, so that earlier functions can
#       recognize a function returning a byte value.
# ------------------------------------------------------------------------

@rolling_optimizer(start='clr r25')
def eliminate_needless_int_promotion(lines, match):
    """Delete a 'clr r25' line if the result is not needed.
    """
    if lines[0].writes & lines.get(1).needed:
        return -1
    lines[0] = ''
    return 1

It worked well through avr-gcc 3.4.6, but then avr-gcc's backend got dementia and made writing the transformations too tedious.

EDIT: Removed a couple more spurious [ m e m b e r ] tags the forum editor added to the code section.

[westfw]

something equivalent to the -o options under MPLABX, but performed by a separate tool which takes the asm generated by MPLABX to try optimizing when possible.

Most optimization is very dependent on information that the compiler keeps internally and doesn't output to the asm files.  Even if you were to output the "intermediate" compiler files, I don't think they'd have enough info.

Are you looking for a tool that goes beyond what is done by the optimizing ("Pro" $$$) versions of the Microchip compilers, or are you looking for a way to avoid spending those $$$?

Here is an example that I wrote over a couple days that fixed all but one missed optimization in a program

Very nice!

It worked well through avr-gcc 3.4.6, but then avr-gcc's backend got dementia and made writing the transformations too tedious.

Oh.  Ouch!Also, avr-gcc optimization seems to keep getting worse (having peaked at somewhere around v4 or v5); I think the compiler optimizes the "intermediate" code without having an accurate idea of how some of it translates into "real" code on an 8bit chip.  :-(

[jfiresto]

Yes, it was sad what happened to avr-gcc, but I am still happy to have written and used the optimizer as it answered a personal what-if I had been wondering about for about 30 years.