This is an archive of the discontinued LLVM Phabricator instance.

[GISel]: Change Legalization from top down to bottom up + DCE
ClosedPublic

Authored by aditya_nandakumar on Oct 24 2017, 5:30 PM.

Details

Summary

This patch changes the legalization order from top down to bottom up.
Also, this deletes trivially dead instructions while legalizing.
Additionally, the LegalizationCombiner tries to clean up artifacts before legalizeInstrStep. This lets the combiner clean up redundant extends/truncs before letting the target deal with them. This simplifies the legalization loop a little - where we don't need to have a separate list to track new legalization artifacts for combines - as we can try to clean up every artifact (vs just new ones).

I have updated AArch backend with this patch.

Diff Detail

Event Timeline

Updated X86,AMDGPU and part of as well.
Two large tests remain to be fixed -

LLVM :: CodeGen/ARM/GlobalISel/arm-legalize-fp.mir
LLVM :: CodeGen/ARM/GlobalISel/arm-legalizer.mir
aemerson edited edge metadata.Oct 27 2017, 8:59 AM

Hi Aditya,

As we discussed privately, looking forward with our plans to separate out the combiner mechanics, we should be extra careful here about our legalisation/combiner iteration scheme. From a design point of view, I'd like to see stricter separation between legalisation and combiner phases.[1] What do you think about changing the overall algorithm to instead run (legalize(), combine()) until we reach a fixed point? It would also be nice if we can share the same iteration scheme between legalizer's combiner and the separate combiner pass. That is, since you already compute the post-ordering of the blocks, we can just reverse them to have our ordering for the combine phase, and that would match the intended ordering for the combiner pass.

[1] To fill in everyone about our discussions: we plan to split the combiner mechanics into a separate pass/component, with the intention that the core routines can be shared between multiple clients. However, as a result of the GISel legaliser, we still have "artefacts" generated which, without optimisation before re-legalisation, could cause poor codegen. Therefore we need the ability for the legaliser to invoke some subset of the future GI-combiner/optimizer to clean these up.

Side note: it'll be easier to review codegen changes if we use the update test script in a separate commit first.

Cheers,
Amara

include/llvm/CodeGen/GlobalISel/LegalizerCombiner.h
229

I'm not sure about this approach to integrating combiners with the legalizer. Since we process the blocks and instructions bottom up with this change, having the combiner rather un-intuitively look at instructions top-down, and only in some cases, makes this harder to reason about.

Another thing is if we're going to separate out the combiner routines then we shouldn't have inconsistency between matching behaviour between different combiners.

Hi Aditya,

I now think this approach is ok to continue with, given the constraints of the MIR type system about needing artifact clean ups as a necessity. I'd also eventually like to see these renamed into something else to make it clear they're distinct from "optimization" combines.

We'll also likely need to have an API to allow later passes to invoke legalization, such as the later GI combiner(s), unless we restrict them to always create legal operations. To do that I think we'll need to refactor the code from this patch into another helper (or the existing LegalizerHelper).

Cheers,
Amara

Legalization Artifacts are all those insts that are there to make the type system happy. Currently, the target needs to say all combinations of extends and truncs are legal and there's no way of verifying that post legalization, we only have *truly* legal instructions. This patch changes roughly the legalization algorithm to process all illegal insts at one go, and then process all truncs/extends that were added to satisfy the type constraints separately trying to combine trivial cases until they converge. This has the added benefit that, the target legalizerinfo can only say which truncs and extends are okay and the artifact combiner would combine away other exts and truncs.

Updated legalization algorithm to roughly the following pseudo code.

WorkList Insts, Artifacts;
collect_all_insts_and_artifacts(Insts, Artifacts);

do {

for (Inst in Insts)
     legalizeInstrStep(Inst, Insts, Artifacts);
for (Artifact in Artifacts)
     tryCombineArtifact(Artifact, Insts, Artifacts);

} while(!Insts.empty());

Also, wrote a simple wrapper equivalent to SetVector, except for erasing, it avoids moving all elements over by one and instead just nulls them out.

vsk added a subscriber: vsk.Nov 6 2017, 5:54 PM
vsk added inline comments.
include/llvm/CodeGen/GlobalISel/GISelWorkList.h
33

Do you mean to delete the copy methods as well?

42

Use WorklistMap.try_emplace?

47

Use '///' for Doxygen support?

aditya_nandakumar marked 2 inline comments as done.Nov 6 2017, 6:17 PM
aditya_nandakumar added inline comments.
include/llvm/CodeGen/GlobalISel/GISelWorkList.h
33

I don't really see the need to explicitly specify any special constructor here as I'm not doing anything special. I'm currently inclining towards only specifying the default constructor as that's the only use case for now.

42

Updated.

47

Updated.

aditya_nandakumar marked 2 inline comments as done.

Updated for a few comments by Vedant.

Hi Aditya,

This looks like a nice re-work. I have some minor comments. Since there's quite a bit of test churn, it's not clear to me what the test case (if any) applies to the new tryFoldImplicitDef() code.

Cheers,
Amara

include/llvm/CodeGen/GlobalISel/GISelWorkList.h
23

I thought the same with my original patch. I think this is fine to live here for now though especially if logging needs to be different.

include/llvm/CodeGen/GlobalISel/LegalizerCombiner.h
112

Can you add some comments explaining why this is needed/what it's trying to achieve.

265

A bit more concise if you test the inverse:

if (!SrcTy.isValid() || SrcTy != DstTy)
  break;
DefMI = MRI.getVRegDef(SrcReg)
lib/CodeGen/GlobalISel/Legalizer.cpp
88

I think it would be helpful to add a clarifying comment here about why we're doing bottom up traversal, and also that we're now using RPO because of the way we use the worklist below. I.e. populating the worklist top down and popping from back.

98

Do we still need this? If we only ever legalise these and the artefacts are always generic opcodes then can we move this check into the worklist population loop and leave an assert here?

105

Is there a specific test case?

aditya_nandakumar marked 3 inline comments as done.Nov 7 2017, 10:46 AM

Thanks Amara for your comments. The test for the folding of implicit_def is in X86/legalize_undef.

lib/CodeGen/GlobalISel/Legalizer.cpp
98

It's theoretically possible for the targets to have a pass before the legalizer where they emit target instructions. I'm not sure if not adding it to the list (during population) is better than ignoring them here.

105

I think we would hit it in a few places where we can have a trunc from two valid types (ie s32 and s16 in x86 for example).

Updated based on Amara's comments.

@rovka , would it be possible for you to look at the two failing arm tests ?

rovka edited edge metadata.Nov 7 2017, 8:47 PM

Sure, will do.

aemerson added inline comments.Nov 8 2017, 8:30 AM
lib/CodeGen/GlobalISel/Legalizer.cpp
98

You save a map lookup on each insertion for no real downside as the check is done at some point anyway, so I think it's worth it.

Thanks Amara - makes sense.

Updated.

Missed adding one assert.

rovka added a comment.Nov 13 2017, 8:16 AM

Hi, I've updated the ARM tests, and you'll need to also commit this together with your patch: https://reviews.llvm.org/differential/diff/122657/

Rebase + Update based on Diana's patch.

volkan accepted this revision.Nov 14 2017, 1:13 PM

Hi Aditya,

LGTM, nitpicks below.

Thank you,
Volkan

include/llvm/CodeGen/GlobalISel/LegalizerCombiner.h
115

This can be simplified as below.

unsigned Opcode = MI.getOpcode();
if(Opcode != TargetOpcode::G_ANYEXT && ...)
  return false;
lib/CodeGen/GlobalISel/Legalizer.cpp
119

Maybe we can rename LegalizerCombiner as ArtifactCombiner?

This revision is now accepted and ready to land.Nov 14 2017, 1:13 PM