Why change "sub x, 5" to "add x, -5" ?

Dear all,

I have been working on a new LLVM backend. Some instructions, like sub, can take an positive constante, encoded into 5 bits thus lower than 32, and a register, as operands.

Unfortunately, DAGCombiner.cpp changes patterns like ‘sub x, 5’ into ‘add x,-5’.

Similarly, I found changes in some IR to IR passes, with no clear gain (at least not clear to me), and even penalty for my specific ISA.

%add = add i32 %a, %b
%tobool = icmp eq i32 %add, 0

becomes :

%add = sub i32 0, %b
%tobool = icmp eq i32 %a, %

My question is not how to workaround those, but why such changes are done for all targets, in DAG selection or in IR passes.
AFAIK, there is no target which has some better encoding with a negative value than with a positive one.
And “sub” looks as costly as “add” to me.

Is there some other practical reason to perform this kind of change ?
Thanks for your highlights.

Other people can elaborate on that, but the general idea is to transform functionally equivalent programs into the same internal representation. In this case, the desired representation is "add-immediate" for instructions that are equivalent to it.

Target-specific selection patterns can deal with it by having predicates that accept or reject the pattern depending on specific values in the DAG: in case of your ISA they could reject the "add" pattern in favor of the "sub" pattern when the immediate is negative.

-Krzysztof

Many don’t have a sub-with-immediate at all, they have an add-with-sign-extended-immediate. Having a single canonical form simplifies matching for these.

David

Having a single canonical form makes optimizations easier, since you don’t have to check both possibilities at every optimization stage.

If you want to “revert" this sort of thing, you can do it at Select() time or PreprocessISelDAG(), which is what I did on an out-of-tree backend to turn add X, -C into sub X, C on selection time. This still lets all the intermediate optimizations take advantage of the canonicalization.

—escha

Normalizing values also makes optimizations more powerful as equivalent values become apparent. Simple example:
a = sub x, 5
b = add x, -5
c = sub a, b
gets normalized to:
a = add x, -5
b = add x, -5
c = sub a, b
after CSE:
a = add x, -5
c = sub a, a
and after instcombine:
c = 0

- Matthias

Thanks for the explainations and examples.
Is the IR canonical form specified somewhere ?

Unaware of your proposal, I used the TargetLowering::PerformDAGCombine hook.
Is there a reason to prefere PreprocessISelDAG ?

Target-specific PerformDAGCombine only runs when the standard combiner doesn't do anything. Also, various legalization steps can potentially undo what it did. PreprocessISelDAG runs always and there is nothing to get in its way.

-Krzysztof

If you write a target-specific combine that conflicts with a canonicalization, it’ll infinite loop because it’ll oscillate between the two forms.

—escha

I saw that :wink:
However, I used DAGCombinerInfo::CombineTo(oldNode, newNode, false) to
prevent DAGCombiner to add the returned SDValue to worklist and recombine
it back to the canical form.
Did I miss the purpose of CombineTo ?

fred