This is an archive of the discontinued LLVM Phabricator instance.

Do not legalize large add with addc/adde, introduce addcarry and do it with uaddo/addcarry
ClosedPublic

Authored by deadalnix on Feb 12 2017, 5:00 AM.

Details

Summary

As per discution on how to get better codegen an large int legalization, it became clear that using a glue for the carry was preventing several desirable optimizations. Passing the carry down as a value allow for more flexibility.

Event Timeline

deadalnix created this revision.Feb 12 2017, 5:00 AM
jyknight edited edge metadata.Feb 17 2017, 2:12 PM

Haven't looked in great detail, but overall looks sane to me.

It'll be great to also eliminate ADDC/ADDE/SUBC/SUBE, instead of adding an alternative method. Oh...and, SETCCE. Will probably need a new variant of that as well?

The FIXME for x86 seems pretty distasteful...

Possibly could handle things by having ADDCARRY A, B, CARRY -> RES, OUTCARRY expand into something along the lines of:

  1. Create FLAGS value per CARRY input. (what's best way to spell that? New pseudo-op "setcarry" that expands into "ADD8RI CARRY, 255 -> unused, FLAGS", maybe?)
  2. Do addition, using carry frmo flags register, input and output: x86isd::ADC A, B, FLAGS -> RES, OUTFLAGS
  3. Grab carry bit from flags register: x86isd::setcc cond_b, OUTFLAGS -> OUTCARRY

Then, have a transform that converts "(setcarry (setcc cond_b FLAGS)) -> FLAGS" into just passing through FLAGS?

include/llvm/CodeGen/ISDOpcodes.h
232

Value should be allowed to come from anywhere, not just uaddo/addcarry, although those would be most common.

It'll be great to also eliminate ADDC/ADDE/SUBC/SUBE, instead of adding an alternative method. Oh...and, SETCCE. Will probably need a new variant of that as well?

Yes I think that where we want to go with this, but proceeding incrementally seems to make more sense. My plan was to get the new stuff up, move in tree backend to use it, and then deprecate it/remove it. SETCCE is also on my radar.

The FIXME for x86 seems pretty distasteful...

Yes I was very unhappy with that solution and was hopping for some advice on how to do this better. I'll try your solution and see how it goes. Do you see the setcarry as a generic ISD or as a X86 specific one ?

deadalnix updated this revision to Diff 89069.Feb 19 2017, 9:49 AM

Update the X86 addcarry generation.

deadalnix updated this revision to Diff 89073.Feb 19 2017, 3:21 PM

Fixed all test regressions. Turned out adding proper support for addcarry and uaddo in computeKnownBits was the missing piece.

mkuper resigned from this revision.Feb 21 2017, 10:52 AM
RKSimon edited edge metadata.Feb 21 2017, 11:30 AM

If possible it'd be great to split this down into smaller patches, which might be quicker to review overall.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1902

Split this into a separate small patch + tests?

lib/CodeGen/SelectionDAG/SelectionDAG.cpp
2517 ↗(On Diff #89073)

Could the ISD::UADDO case be split into a separate small patch + tests?

lib/Target/X86/X86ISelLowering.cpp
33951

Again, can this be extracted into its own patch + tests?

deadalnix added inline comments.Feb 21 2017, 12:48 PM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1902

No you get a bunch of regression without these. This is doing the same transforms as for ADDC, so this isn't actually new.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp
2517 ↗(On Diff #89073)

Same thing, bunch of regression without this.

lib/Target/X86/X86ISelLowering.cpp
33951

Without this, you get an add with a carry, followed by a setb or an sbb instruction to materialise the carry, followed by an add Carry, -1 to regenerate the carry. It's pretty bad.

What I meant was to pull out some of the codegen changes into smaller patches with their own tests that can be reviewed and accepted before this patch.

Then make this patch just about the addition of ADDCARRY and SUBCARRY instead of having to handle so many things at once.

I see, I can do that, but I'm afraid the test cases will be poor. In this patch the tests cases that exists for ADC are covering the transform, but these tests case can't be leveraged when not using UADDO/ADDCARRY .

efriedma added inline comments.
include/llvm/CodeGen/ISDOpcodes.h
236

Please explicitly note that the carry input to SUBCARRY supposed to be the output of USUBO; the "carry" bit is defined differently on some architectures.

deadalnix updated this revision to Diff 89940.Feb 27 2017, 2:29 PM

Extract UADDO changes into D30417 and D30379 .

deadalnix updated this revision to Diff 91370.Mar 10 2017, 9:54 AM

Remove all UADDO/USUBO related changes in their own diff.
Keep only the ADDCARRY/SUBCARRY related code in there.

deadalnix updated this revision to Diff 91551.Mar 13 2017, 6:39 AM

Rebase on top of D30611 and fix related issues.

zvi added inline comments.Mar 20 2017, 7:03 AM
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
516–521

Consider using a SmallVector here.

lib/Target/X86/X86ISelLowering.cpp
22973

I know this also appears at the top of LowerADDC_ADDE_SUBC_SUBE, but why it this check needed?

deadalnix added inline comments.Mar 20 2017, 7:30 AM
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
516–521

The can only be 2 or 3 element so i think just allocating for 2 on the stack is preferable. This is done in various other places in the codebase already.

lib/Target/X86/X86ISelLowering.cpp
22973

Because in that case, the backend wants to run some extra legalization code before coming back there.

A few minors for you to look at

include/llvm/CodeGen/ISDOpcodes.h
235

Please detail the results as well (similar to ADDE/SUBE).

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
7952

Update comment to describe addcarry too.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
517

This will be clearer with unsigned instead of auto

1277

Mixed use of SDValue and auto.

1764

clang-format

1922

clang-format

deadalnix updated this revision to Diff 92328.Mar 20 2017, 7:55 AM

Update as per comments.

zvi added inline comments.Mar 20 2017, 9:42 AM
lib/Target/X86/X86ISelLowering.cpp
22973

At the time this code runs, there should not be any illegal types present in the DAG.
So i am asking why is there a need to check for illegal types?

deadalnix added inline comments.Mar 20 2017, 11:34 AM
lib/Target/X86/X86ISelLowering.cpp
22973

I'm not sure what the X86 backend is doing, but this is clearly happening looking at the -debug output of llc.

RKSimon added inline comments.Apr 3 2017, 6:21 AM
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
516–521

Add explicit SDValue() to initialize Ops[2] ?

1809

Should this be a separate fix?

1911

Should this be added separately? At very least DAGTypeLegalizer::ExpandIntRes_UADDSUBO should be moved as an NFC pre-commit so that diff is more obvious.

lib/Target/X86/X86ISelLowering.cpp
33926

We already have a combineAdd function - this should be named something like combineX86Add

spatel edited edge metadata.Apr 3 2017, 8:20 AM

I haven't looked at carry codegen enough to approve, but see inline comments for some nits.

include/llvm/CodeGen/ISDOpcodes.h
215–218

If I'd just stumbled into this code, I'd be confused why we have ADDC and ADDE and ADDCARRY. If the intent is to remove these, please add a 'FIXME' comment here that says we should get rid of these.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1928–1930

This is copied from above, but comments are supposed to be full sentences (capital letter, period).
Use 'auto *' with dyn_cast because the type is obvious from the code and variable name.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
517

I'd call this 'NumOps' or similar. 'C' in LLVM usually means some kind of constant value.

lib/CodeGen/TargetLoweringBase.cpp
913–914

This code comment won't age well. Delete.

lib/Target/X86/X86ISelLowering.cpp
33926

+1 - we definitely do not want function names that only differ in captitalization.

33932

auto -> SDValue

33944

auto -> auto *

mkazantsev added inline comments.
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
1761

hasOpCarry? By analogy with hasCarry below.

1918

hasOpCarry?

1945

iff -> if?

deadalnix added inline comments.Apr 18 2017, 7:43 AM
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
1945

iff is a shorthand for if and only if, to indicate bijection. it is commonly used in the comment int hat file, so I think this is fine.

deadalnix updated this revision to Diff 95571.Apr 18 2017, 8:12 AM

Address comments

deadalnix updated this revision to Diff 96386.Apr 24 2017, 6:07 AM

Ping ?

I'd really would ike to move on with optimizing big integers better and this is gating everything. This needs to move forward.

RKSimon added inline comments.Apr 24 2017, 8:16 AM
include/llvm/CodeGen/ISDOpcodes.h
215–218

I agree with Sanjay - you need to document the plan for ADDC/SUBC here

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
1918

HasOpCarry (style)

1931

Please unsigned instead of auto for the simple types

1964

SDValue HiOps[3] = { LHSH, RHSH, SDValue() };

lib/Target/X86/X86ISelLowering.cpp
22970

unsigned

22988

SDValue

deadalnix updated this revision to Diff 96483.Apr 24 2017, 5:08 PM

Add a FIXME on ADDC/SUBC to explain they are deprecated in favor of ADDCARRY and SUBCARRY and will be removed in the future.

Replaced several uses of auto with explicit types as per request.

I see nothing to stop this being accepted now - does anyone have any further comments?

I see nothing to stop this being accepted now - does anyone have any further comments?

Having the FIXME note was my main concern...just in case the transition takes longer than expected. I have no other comments.

deadalnix updated this revision to Diff 97238.Apr 30 2017, 9:27 AM

If you guys are good with it, then let's move forward. I have various patches coming based on this, and we start moving backends to use ADDCARRY instead of ADC once it is in.

This revision is now accepted and ready to land.Apr 30 2017, 10:42 AM
This revision was automatically updated to reflect the committed changes.