[RFC] mir-canon: A new tool for canonicalizing MIR for cleaner diffing.

Hi,

My name is Puyan and I’ve been exploring ways to improve the state of instruction level diffing using llvm and MIR. Below is a proposal for a new llvm tool meant to address issues encountered when diffing at the machine level. I’m eager to hear the community’s feedback.

Thanks

PL

mir-canon: A new tool for canonicalizing MIR for cleaner diffing.

Problem Statement and Context:

Diff-tools are regularly used for comparing IR and assembly files. This often involves reasoning through differences that are semantically equivalent and it can be very time consuming for a person to do said reasoning.

Specifically in the context of GlobalISel development there are problems of correctness verification. There is a need to compare two programs, compiled from identical IR by two different instruction selectors in a way where the true differences stand out.

Proposal:

We propose a new tool that we have tentatively named ‘mir-canon’ that performs canonical transformations on MIR. The goal is for MIR pre-processed with mir-canon to show fewer differences than if it were not pre-processed.

At the time of this writing we have a prototype canonicalization tool. We’ve come up with some techniques that show promise and would like to open discussion with the community to get feedback and suggestions on refining said techniques. Currently we think of this as an open ended project.

Techniques:

Our prototype does the following for each basic block in a Reverse Post Ordering:

  • Canonical instruction ordering is done by moving a given instruction as close to the nearest use of its def as possible.

  • Next, canonical VReg renaming is done by building a collection of candidate instructions that can be thought of as sinks in the def-use graph: they are typically instructions that write to physical registers or store to memory. These candidates are used as the root of a breadth first walk over the vreg operand def-use graph that determines a canonical vreg ordering.

  • Using said canonical vreg ordering we rename monotonically, but before we do this we skip several vreg values in order to increase the chance that we land on the same vreg number for two different input MIR files. We also do this to reduce the chances that a difference in previously def-use walks will affect the vreg renaming for subsequent walks. This skipping step could be thought of as a kind of vreg number reckoning: we skip modulo n vregs so that we are likely to land on the same vreg for two different files.

This approach is completely agnostic of ISA specific semantics so it should work for any target.

Current status:

At the moment we have a standalone llvm tool that uses a single pass to do the above described transformations. We have test inputs that show promise but we still need a wider set of tests as well as hard metrics.

Our approach processes a single file at a time. The primary benefit to this approach is lower complexity in initial implementation and exploration of building such a tool. We are open to other approaches such as an llvm-diff like (two file at a time) approach, but we have not explored that avenue fully yet.

We’re eager to hear community feedback and will be ready to share patches for review soon.

Ping.

Still working on preparing code for review. Will have a patch for review ready in the coming days.

PL

Patch for review.

mir-canon.patch (26.9 KB)

Hi Puyan. Seeing as nobody else has expressed an opinion so far, I
thought I'd just say that this does sound like a useful tool. I don't
currently do any MIR-level testing, but this seems like it would be
helpful when that changes.

Best,

Alex

Puyan Lotfi via llvm-dev <llvm-dev@lists.llvm.org> writes:

mir-canon: A new tool for canonicalizing MIR for cleaner diffing.

Problem Statement and Context:

Diff-tools are regularly used for comparing IR and assembly files. This often
involves reasoning through differences that are semantically equivalent and it
can be very time consuming for a person to do said reasoning.

Specifically in the context of GlobalISel development there are problems of
correctness verification. There is a need to compare two programs, compiled
from identical IR by two different instruction selectors in a way where the
true differences stand out.

Proposal:

We propose a new tool that we have tentatively named 'mir-canon' that performs
canonical transformations on MIR. The goal is for MIR pre-processed with
mir-canon to show fewer differences than if it were not pre-processed.

This sounds great. One place I'm hoping to use this for is in ISel
fuzzing - we can currently catch crashes and machine verifier errors,
but comparing SDAG to GlobalISel is a space that I'd really like to
explore.

At the time of this writing we have a prototype canonicalization tool. We’ve
come up with some techniques that show promise and would like to open
discussion with the community to get feedback and suggestions on refining said
techniques. Currently we think of this as an open ended project.

Techniques:

Our prototype does the following for each basic block in a Reverse Post
Ordering:

  * Canonical instruction ordering is done by moving a given instruction as
    close to the nearest use of its def as possible.

  * Next, canonical VReg renaming is done by building a collection of
    candidate instructions that can be thought of as sinks in the def-use
    graph: they are typically instructions that write to physical registers or
    store to memory. These candidates are used as the root of a breadth first
    walk over the vreg operand def-use graph that determines a canonical vreg
    ordering.

  * Using said canonical vreg ordering we rename monotonically, but before we
    do this we skip several vreg values in order to increase the chance that
    we land on the same vreg number for two different input MIR files.

This is one place where handling multiple files at once would help, correct?

    We also do this to reduce the chances that a difference in
    previously def-use walks will affect the vreg renaming for
    subsequent walks. This skipping step could be thought of as a kind
    of vreg number reckoning: we skip modulo n vregs so that we are
    likely to land on the same vreg for two different files.

This approach is completely agnostic of ISA specific semantics so it should
work for any target.

Current status:

At the moment we have a standalone llvm tool that uses a single pass to do
the above described transformations. We have test inputs that show promise
but we still need a wider set of tests as well as hard metrics.

This sounds like a great start, but I feel like this design won't quite
scale to all the ways we want to use this.

Consider, if this was a pass in the LLVM library rather than only
accessible in a tool, you could potentially set it up to run at the end
of an `llc` run. Similarly, if I want to use this in a fuzzer it would
be nice to be able to do the canonicalization in memory.

Our approach processes a single file at a time. The primary benefit to this
approach is lower complexity in initial implementation and exploration of
building such a tool. We are open to other approaches such as an llvm-diff
like (two file at a time) approach, but we have not explored that avenue
fully yet.

We’re eager to hear community feedback and will be ready to share patches
for review soon.

...

Patch for review.

Please send the patch to llvm-commits (and refer back to this thread).
Patch review is too much traffic for llvm-dev.

It sounds quite useful. I wonder though why did you decide in favor of a stand-alone tool vs an LLVM pass that can be invoked under an option? It seems to me using the llvm infrastructure should provide the means for the transformations the tool is performing. Maybe there is the sense that it is faster to implement (assuming this is what you mean by lower complexity) an off-line tool but there are benefits to leveraging llvm also.

I’m also curious about ways to link back difference sightings to actions in the compiler. Does this come down to follow ups “by hand”? Or do you plan to sync this with opt-viewer remarks? Or something else like “I (hopefully) know what to do when I see a ‘canonical’ diff"? Perhaps you can share some thoughts about it.

Cheers
Gerolf

Hey Puyan,

Do you think that mir-canon could be used with, say, the MachineOutliner/other outlining/code size technologies?

If mir-canon is inter-procedural, I imagine that reducing the differences between semantically equivalent sequences of instructions might reveal more opportunities for outlining.

  • Jessica

Puyan Lotfi via llvm-dev <llvm-dev@lists.llvm.org> writes:
> mir-canon: A new tool for canonicalizing MIR for cleaner diffing.
>
> Problem Statement and Context:
>
> Diff-tools are regularly used for comparing IR and assembly files. This
often
> involves reasoning through differences that are semantically equivalent
and it
> can be very time consuming for a person to do said reasoning.
>
> Specifically in the context of GlobalISel development there are problems
of
> correctness verification. There is a need to compare two programs,
compiled
> from identical IR by two different instruction selectors in a way where
the
> true differences stand out.
>
> Proposal:
>
> We propose a new tool that we have tentatively named 'mir-canon' that
performs
> canonical transformations on MIR. The goal is for MIR pre-processed with
> mir-canon to show fewer differences than if it were not pre-processed.

This sounds great. One place I'm hoping to use this for is in ISel
fuzzing - we can currently catch crashes and machine verifier errors,
but comparing SDAG to GlobalISel is a space that I'd really like to
explore.

Thats exactly what I'm trying to do. I'm still trying to think of good ways
to narrow down the set of functions and basic blocks that get
canonicalized. I have some opt flags to control that but I think the
control could be better.

> At the time of this writing we have a prototype canonicalization tool.
We’ve
> come up with some techniques that show promise and would like to open
> discussion with the community to get feedback and suggestions on
refining said
> techniques. Currently we think of this as an open ended project.
>
> Techniques:
>
> Our prototype does the following for each basic block in a Reverse Post
> Ordering:
>
> * Canonical instruction ordering is done by moving a given instruction
as
> close to the nearest use of its def as possible.
>
> * Next, canonical VReg renaming is done by building a collection of
> candidate instructions that can be thought of as sinks in the def-use
> graph: they are typically instructions that write to physical
registers or
> store to memory. These candidates are used as the root of a breadth
first
> walk over the vreg operand def-use graph that determines a canonical
vreg
> ordering.
>
> * Using said canonical vreg ordering we rename monotonically, but
before we
> do this we skip several vreg values in order to increase the chance
that
> we land on the same vreg number for two different input MIR files.

This is one place where handling multiple files at once would help,
correct?

I think so. I think if I were processing two files at once I could
increment the vreg count by a more exact number between basic blocks
processed and between def-use walks.

> We also do this to reduce the chances that a difference in
> previously def-use walks will affect the vreg renaming for
> subsequent walks. This skipping step could be thought of as a kind
> of vreg number reckoning: we skip modulo n vregs so that we are
> likely to land on the same vreg for two different files.
>
> This approach is completely agnostic of ISA specific semantics so it
should
> work for any target.
>
> Current status:
>
> At the moment we have a standalone llvm tool that uses a single pass to
do
> the above described transformations. We have test inputs that show
promise
> but we still need a wider set of tests as well as hard metrics.

This sounds like a great start, but I feel like this design won't quite
scale to all the ways we want to use this.

Consider, if this was a pass in the LLVM library rather than only
accessible in a tool, you could potentially set it up to run at the end
of an `llc` run. Similarly, if I want to use this in a fuzzer it would
be nice to be able to do the canonicalization in memory.

I used to have it as an LLVM pass but a while ago I thought it could be
more prudent to have contained in a separate tool as it wasn't actually for
optimization or codegen. I can easily reintegrate it as an LLVM pass. I'll
send out another patch.

> Our approach processes a single file at a time. The primary benefit to
this
> approach is lower complexity in initial implementation and exploration of
> building such a tool. We are open to other approaches such as an
llvm-diff
> like (two file at a time) approach, but we have not explored that avenue
> fully yet.
>
> We’re eager to hear community feedback and will be ready to share patches
> for review soon.
...
> Patch for review.

Please send the patch to llvm-commits (and refer back to this thread).
Patch review is too much traffic for llvm-dev.

Great, thanks!

Right now the mir-cannon Canonicalization pass is limited within a basic block. I don’t know the full details of how the outliner works, but I suspect if outlining success rate is limited by factors like vreg names and/or instruction ordering then it could be helpful. Of course, I think if you used some canonicalization pass to reorder the schedule prior to outlining, then you’d definitely want to run the outlined code through the scheduler.

PL

This would be easier to discuss on llvm-commits and phabricator.

Patch for review.

Ping.

Still working on preparing code for review. Will have a patch for review ready in the coming days.

PL

Hi,

My name is Puyan and I’ve been exploring ways to improve the state of instruction level diffing using llvm and MIR. Below is a proposal for a new llvm tool meant to address issues encountered when diffing at the machine level. I’m eager to hear the community’s feedback.

Thanks

PL

mir-canon: A new tool for canonicalizing MIR for cleaner diffing.

Problem Statement and Context:

Diff-tools are regularly used for comparing IR and assembly files. This often involves reasoning through differences that are semantically equivalent and it can be very time consuming for a person to do said reasoning.

Specifically in the context of GlobalISel development there are problems of correctness verification. There is a need to compare two programs, compiled from identical IR by two different instruction selectors in a way where the true differences stand out.

Sounds interesting!
I hope some people involved in GlobalISel will chime in the discussion about the patch.

Proposal:

We propose a new tool that we have tentatively named ‘mir-canon’ that performs canonical transformations on MIR. The goal is for MIR pre-processed with mir-canon to show fewer differences than if it were not pre-processed.

At the time of this writing we have a prototype canonicalization tool. We’ve come up with some techniques that show promise and would like to open discussion with the community to get feedback and suggestions on refining said techniques. Currently we think of this as an open ended project.

Techniques:

Our prototype does the following for each basic block in a Reverse Post Ordering:

  • Canonical instruction ordering is done by moving a given instruction as close to the nearest use of its def as possible.

From glancing at the patch this only seems to respect vreg dependencies but I couldn’t see memory / side effect tracking (ScheduleDAGInstrs may be the right tool for the job).

  • Next, canonical VReg renaming is done by building a collection of candidate instructions that can be thought of as sinks in the def-use graph: they are typically instructions that write to physical registers or store to memory. These candidates are used as the root of a breadth first walk over the vreg operand def-use graph that determines a canonical vreg ordering.

  • Using said canonical vreg ordering we rename monotonically, but before we do this we skip several vreg values in order to increase the chance that we land on the same vreg number for two different input MIR files. We also do this to reduce the chances that a difference in previously def-use walks will affect the vreg renaming for subsequent walks. This skipping step could be thought of as a kind of vreg number reckoning: we skip modulo n vregs so that we are likely to land on the same vreg for two different files.

It may be interesting to extend the .mir file format here to allow arbitrary names for vregs.

So instead of

block1:
%0 = foo
%1 = bar
use %1

block2:
%100 = baz

you could do something along the lines of:

block1:
%1_foo0 = foo
%1_bar1 = bar
use %1_bar1

block2:
%2_baz = baz

That way you could avoid the vreg numbering games and by encoding the instruction type you are even robust against insertion/removal of instructions of different types.

I’d certainly be open to some mir extension patches.

  • Matthias

This would be easier to discuss on llvm-commits and phabricator.

Patch for review.

Ping.

Still working on preparing code for review. Will have a patch for review
ready in the coming days.

PL

Hi,

My name is Puyan and I've been exploring ways to improve the state of
instruction level diffing using llvm and MIR. Below is a proposal for a new
llvm tool meant to address issues encountered when diffing at the machine
level. I'm eager to hear the community's feedback.

Thanks

PL

mir-canon: A new tool for canonicalizing MIR for cleaner diffing.

Problem Statement and Context:

Diff-tools are regularly used for comparing IR and assembly files. This
often involves reasoning through differences that are semantically
equivalent and it can be very time consuming for a person to do said
reasoning.

Specifically in the context of GlobalISel development there are problems
of correctness verification. There is a need to compare two programs,
compiled from identical IR by two different instruction selectors in a way
where the true differences stand out.

Sounds interesting!

I hope some people involved in GlobalISel will chime in the discussion
about the patch.

I'm hoping to get them using it once things get checked in and are
available in all our branches.

Proposal:

We propose a new tool that we have tentatively named 'mir-canon' that
performs canonical transformations on MIR. The goal is for MIR
pre-processed with mir-canon to show fewer differences than if it were not
pre-processed.

At the time of this writing we have a prototype canonicalization tool.
We’ve come up with some techniques that show promise and would like to open
discussion with the community to get feedback and suggestions on refining
said techniques. Currently we think of this as an open ended project.

Techniques:

Our prototype does the following for each basic block in a Reverse Post
Ordering:

   - Canonical instruction ordering is done by moving a given
   instruction as close to the nearest use of its def as possible.

From glancing at the patch this only seems to respect vreg dependencies

but I couldn't see memory / side effect tracking (ScheduleDAGInstrs may be
the right tool for the job).

I've currently not gotten to that. At the moment, I treat memory and
physical register side effects as canonicalization barriers. Doing a side
effect tracker sounds like a good next step.

   - Next, canonical VReg renaming is done by building a collection of
   candidate instructions that can be thought of as sinks in the def-use
   graph: they are typically instructions that write to physical registers or
   store to memory. These candidates are used as the root of a breadth first
   walk over the vreg operand def-use graph that determines a canonical vreg
   ordering.

   - Using said canonical vreg ordering we rename monotonically, but
   before we do this we skip several vreg values in order to increase the
   chance that we land on the same vreg number for two different input MIR
   files. We also do this to reduce the chances that a difference in
   previously def-use walks will affect the vreg renaming for subsequent
   walks. This skipping step could be thought of as a kind of vreg number
   reckoning: we skip modulo n vregs so that we are likely to land on the same
   vreg for two different files.

It may be interesting to extend the .mir file format here to allow

arbitrary names for vregs.

So instead of

block1:
%0 = foo
%1 = bar
   use %1

block2:
%100 = baz

you could do something along the lines of:

block1:
  %1_foo0 = foo
  %1_bar1 = bar
         use %1_bar1

block2:
  %2_baz = baz

That way you could avoid the vreg numbering games and by encoding the
instruction type you are even robust against insertion/removal of
instructions of different types.

I'd certainly be open to some mir extension patches.

That would actually be pretty great because currently the compile time
suffers a lot from generating all those skipped vregs.
I will certainly follow up with you as a second phase of this in order to
speed things up.

I will send a revised patch to the commits list as soon as I can.

PL