Page MenuHomePhabricator

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.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

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 ↗(On Diff #89073)

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 ↗(On Diff #89073)

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 ↗(On Diff #89073)

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 ↗(On Diff #89073)

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 ↗(On Diff #89073)

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 ↗(On Diff #91551)

Consider using a SmallVector here.

lib/Target/X86/X86ISelLowering.cpp
23103 ↗(On Diff #91551)

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 ↗(On Diff #91551)

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
23103 ↗(On Diff #91551)

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 ↗(On Diff #92313)

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

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
8256 ↗(On Diff #92313)

Update comment to describe addcarry too.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
517 ↗(On Diff #92313)

This will be clearer with unsigned instead of auto

1281 ↗(On Diff #92313)

Mixed use of SDValue and auto.

1768 ↗(On Diff #92313)

clang-format

1926 ↗(On Diff #92313)

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
23103 ↗(On Diff #91551)

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
23103 ↗(On Diff #91551)

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 ↗(On Diff #93090)

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

1832 ↗(On Diff #93090)

Should this be a separate fix?

1934 ↗(On Diff #93090)

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
34407 ↗(On Diff #93090)

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 ↗(On Diff #93856)

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
2084–2086 ↗(On Diff #93856)

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 ↗(On Diff #93856)

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

lib/CodeGen/TargetLoweringBase.cpp
913–914 ↗(On Diff #93856)

This code comment won't age well. Delete.

lib/Target/X86/X86ISelLowering.cpp
34407 ↗(On Diff #93090)

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

34507 ↗(On Diff #93856)

auto -> SDValue

34519 ↗(On Diff #93856)

auto -> auto *

mkazantsev added inline comments.
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
1785 ↗(On Diff #95431)

hasOpCarry? By analogy with hasCarry below.

1941 ↗(On Diff #95431)

hasOpCarry?

1968 ↗(On Diff #95431)

iff -> if?

deadalnix added inline comments.Apr 18 2017, 7:43 AM
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
1968 ↗(On Diff #95431)

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 ↗(On Diff #93856)

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

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
1954 ↗(On Diff #96386)

Please unsigned instead of auto for the simple types

1987 ↗(On Diff #96386)

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

1941 ↗(On Diff #95431)

HasOpCarry (style)

lib/Target/X86/X86ISelLowering.cpp
23359 ↗(On Diff #96386)

unsigned

23377 ↗(On Diff #96386)

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.