Fusion opportunities for `not` instructions

[Jonathan Brandmeyer]

First off, thank you for volunteering to keep the Xbitmanip extension alive.

I read through the instruction prevalence statistics[0] used to justify only the inclusion of andc, but not any of the other complementing bitwise instructions (nand, xnor, nor, orn, and so on).  One thing that has me confused is why `mv' followed by `not' appears as an eligible fusion pattern in the generated code.  The only way to emit a `not` instruction isn't destructive, so why would it be fusible with `mv`?

I read the python script that generates the statistics, and it looks to me like its properly accounting for live ranges within each basic block.  The catch is, that it doesn't account for live ranges that cross basic blocks in the control flow graph.

I was thinking that having either source_sinks == 0 or this_sinks == 0 could be used as a proxy to see how often keeping the search within a single basic block would be interfering with the analysis.  Either of those conditions indicates that either the source or or the sink for the instruction is inside another basic block.  So I instrumented the script with a warning on those conditions, and it got triggered about 800 times (out of 942 'not' insns), and 40 times out of 63 `neg` instructions.

So, that's not great.  I've been thinking that rather than try to make the script build up the control flow graph and trace its way across basic blocks, that it might be easier to "just" add support for the candidate instructions in GCC and Binutils for A/B testing.  What do you think?

[0]: http://svn.clifford.at/handicraft/2017/bitcode/notneg.txt

Thanks,
-Jonathan

[Clifford Wolf]

Hi Jonathan,

you are correct, the merge-able mv+not is likely a false-positive caused by the heuristics used in that python script. (It might also be an issue with gcc register allocation and scheduling. I've seen multiple instances of gcc-generated risc-v assembler code where gcc allocated registers in a way that caused additional moves that would have been easily avoided using a different register allocation.)

However, the evaluations you are referring to were of course never meant as a substitute for A/B testing with a compiler. It's just a fist quick hack to get some preliminary data. The "next steps" section in the xbitmanip document explicitly says that adding compiler support and running tests is a major next step.

Furthermore, more interesting than static code size is actually dynamic instruction count. So we'll also need to add support to an execution environment (such as spike) and run experiments where we actually run code, not just look at it statically.

But that being said, let's assume for a moment that all "not+something" and "something+not" pairs are effected by false positives/negatives about equally, which is not a terribly bad assumption if your null hypothesis is that none of those pairs is "special". Then the data suggest very strongly that that null hypothesis is incorrect and that "not+and" is indeed a very special combination that occurs with much higher frequency than any other combination. I would not expect a fundamentally different result from a more rigorous analysis based on a properly patched compiler.

regards,

 - Clifford

--
You received this message because you are subscribed to the Google Groups "riscv-xbitmanip" group.
To unsubscribe from this group and stop receiving emails from it, send an email to riscv-xbitmanip+unsubscribe@googlegroups.com.
To post to this group, send email to riscv-xbitmanip@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/riscv-xbitmanip/e5d16b22-8a20-4881-aa1b-97098dfade23%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.