This is an archive of the discontinued LLVM Phabricator instance.

IR Outliner Pass
Needs ReviewPublic

Authored by trixirt on Oct 31 2018, 10:38 AM.

Details

Summary

This is a new pass that reduces code size by outlining at the IR level.

This is the work of River Riddle
https://github.com/River707/llvm.git, outliner branch

With some cleanup and minor fixes.

The discussion on llvm-dev of this can be found here
http://lists.llvm.org/pipermail/llvm-dev/2017-September/117814.html

River's presentation at the 2017 llvm dev conf
https://www.youtube.com/watch?v=SS1rJzggBu0

More recent rebases for master and release_70 to llvm can be found
https://github.com/trixirt/llvm/tree/master-iro
https://github.com/trixirt/llvm/tree/release_70-iro

Diff Detail

Repository
rL LLVM

Event Timeline

trixirt created this revision.Oct 31 2018, 10:38 AM
paquette requested changes to this revision.Oct 31 2018, 4:38 PM

Thanks for putting this up! I think this patch needs some work though.

I noticed there are lots of inconsistencies in commenting and code style here. I wrote some comments, but the issues seem to be prevalent throughout the code. I recommend looking through the LLVM Coding Standards (https://www.llvm.org/docs/CodingStandards.html) and revising the patch based off of that.

This patch is also extremely large, which makes it difficult to give a proper review. I suggest breaking it into several small patches, as per the LLVM Developer Policy. (https://llvm.org/docs/DeveloperPolicy.html#incremental-development)

I noticed that throughout this code, there are many shared structures with the MachineOutliner. For example, the instruction mapping stuff already exists in the MachineOutliner. Instead of rewriting all of these structures, I recommend making use of them and pulling them out into include/llvm/Transforms/Utils etc. This would reduce the number of changes to existing code necessary to add an IR outliner.

Also, with a patch like this, you need to attach some test-cases. I suggest looking through the LLVM Testing Guide. (https://llvm.org/docs/TestingGuide.html) I also recommend running the LLVM test suite and attaching some code size results versus a vanilla compiler.

As a final point, I think it'd be better to just call the pass "Outliner" rather than "CodeSizeOutliner", just for consistency with the other passes in LLVM.

include/llvm/Transforms/IPO.h
223

This shouldn't be here.

226

Extra line isn't necessary.

include/llvm/Transforms/IPO/CodeSizeOutliner.h
1 ↗(On Diff #171957)

I think this needs to be updated.

E.g, "Pulls common instruction sequences into functions."

2 ↗(On Diff #171957)

These should be on the same line as the header, not a separate line.

12 ↗(On Diff #171957)

Unnecessary indent.

23 ↗(On Diff #171957)

I don't think this comment is correct.

include/llvm/Transforms/Utils/Outliner.h
2

This can just be "A generic outlining utility interface."

29

Can we change this to Outlining or Outliner for consistency?

42

What does "instruction size" mean here? Number of instructions? This could be more clear.

49

This should be iterator for consistency with the rest of LLVM.

50

This should be const_iterator for consistency with the rest of LLVM.

61

\p Idx

This shows up a few times, so you might want to search + replace for it.

78

Might be better to pass in the std::vector as an output parameter instead of returning it?

113–116

Why void*?

Maybe it would be better to templatise the mapper class on the type of instruction. (e.g MachineInstr, Instruction)?

lib/Passes/PassBuilder.cpp
887

Is this intended to always be enabled when optimizing for size?

lib/Transforms/IPO/CodeSizeOutliner.cpp
1 ↗(On Diff #171957)

This header doesn't seem right...?

64 ↗(On Diff #171957)

Why short?

73 ↗(On Diff #171957)

You don't need \brief here

75 ↗(On Diff #171957)

These should be capitalized?

80 ↗(On Diff #171957)

Unnecessary indent

86 ↗(On Diff #171957)

What is the base input?

96 ↗(On Diff #171957)

Cost is initialized everywhere else, why not here?

105 ↗(On Diff #171957)

We use autobrief, so you don't need to add \brief here.

137 ↗(On Diff #171957)

Unnecessary indent, fix \p

150 ↗(On Diff #171957)

Why does this return 0? It would be good to explain what the expected return values are here.

153 ↗(On Diff #171957)
156–158 ↗(On Diff #171957)

You could probably just return getTypeSize(DL, Ty, WidestRegister) / WidestRegister; here, and then just return 0 otherwise.

161 ↗(On Diff #171957)

The cost model should be documented here. What is the cost measuring?

163–166 ↗(On Diff #171957)

There should probably be a comment explaining these decisions.

paquette added inline comments.Oct 31 2018, 4:38 PM
lib/Transforms/IPO/CodeSizeOutliner.cpp
183–184 ↗(On Diff #171957)

I'd move this above if (CE->getOpcode() == Instruction::GetElementPtr).

Then we could do if (CE->getOpcode() != Instruction::GetElementPtr) instead and just return TargetTransformInfo::TCC_Free. Then the more complicated GetElementPtr case can be moved out of the if block. I think that would be a bit more readable.

191–193 ↗(On Diff #171957)

Extra lines above + below aren't necessary.

Also, why is this a Doxygen comment?

212–216 ↗(On Diff #171957)

This can probably be under an LLVM_DEBUG macro?

e.g

LLVM_DEBUG(
  ... blah ...
);
220 ↗(On Diff #171957)

InstructionInfo is a type, and so you should refer to it as such in the comment here.

Also, this isn't a Doxygen comment, so there's no reason to have a \p.

232 ↗(On Diff #171957)

ParentBB or something similar is probably a bit more idiomatic.

234 ↗(On Diff #171957)

This doesn't need to be a Doxygen comment.

Also this could be more descriptive. What is it that you're calculating here?

238 ↗(On Diff #171957)

This could use a better name, or a comment explaining what it is.

245–246 ↗(On Diff #171957)

I'd move this to the top of the loop.

e.g

if (isa<BasicBlock>(Op))
    break;

Instruction *IOP = dyn_cast<Instruction>(Op);

...

250 ↗(On Diff #171957)

This doesn't need to be a Doxygen comment.

It could be more descriptive as well. What is it that you're calculating?

252 ↗(On Diff #171957)

This could use a better name. UserInst or something similar.

263–265 ↗(On Diff #171957)

This probably shouldn't be a Doxygen comment.

285 ↗(On Diff #171957)

Cost model should be documented.

287 ↗(On Diff #171957)

In some places, you use Inst as the name of the Instruction you're looking at. In other places, you use I. It would be good to just pick one of them and be consistent to make it easier to follow the code.

309 ↗(On Diff #171957)

Why times two?

317 ↗(On Diff #171957)

This case is pretty complex. Since calls have their own helper function, I think that this should have one too for consistency. IMO, most of the cases in here probably should for the sake of consistency.

323–324 ↗(On Diff #171957)

Unnecessary indent.

337 ↗(On Diff #171957)

Unnecessary indent, "Free probably shouldn't" be capitalized.

352–353 ↗(On Diff #171957)

Why is that true?

357 ↗(On Diff #171957)

Logic can probably be tightened up here. E.g.

if (!HasFreeAddressComp)
    break;

for (User *Usr : GVar->users()) {
...
}
break;
358–365 ↗(On Diff #171957)

This could probably be simplified using llvm::any_of.

377 ↗(On Diff #171957)

Can this be moved above the switch statement? Then the switch could just add to Cost and return rather than breaking everywhere? (In the spirit of https://llvm.org/docs/CodingStandards.html#use-early-exits-and-continue-to-simplify-code)

Also can OpI be a reference?

394 ↗(On Diff #171957)

This function is quite large, would it be possible to break it into some smaller pieces? E.g, the for loop after the switch could be a helper function etc.

410 ↗(On Diff #171957)

Please be consistent in usage of terminology; there are many comments that use "parameter", and many that use "param". I suggest using "parameter" always, since that seems more idiomatic.

See: https://llvm.org/docs/CodingStandards.html#commenting

415–418 ↗(On Diff #171957)

This loop doesn't need braces.

424 ↗(On Diff #171957)

This comment isn't useful. It would be better to describe what you're going to do with this in detail.

434 ↗(On Diff #171957)

s/instruction/instructions/

Also, why parallel?

443 ↗(On Diff #171957)

Outlined? Or outlining?

Also, this name seems strange for what this thing is?

474–486 ↗(On Diff #171957)

I think that this is one of those cases where you can use braces around an if. :)

493 ↗(On Diff #171957)

Please define terminology you'll use throughout the code. There is no definition of "outline chain" anywhere.

499 ↗(On Diff #171957)

It would be nice to have an explanation of why variables in the code are important.

502 ↗(On Diff #171957)

This shouldn't be a Doxygen comment.

506 ↗(On Diff #171957)

No doxygen here either.

510 ↗(On Diff #171957)

No doxygen.

513 ↗(On Diff #171957)

s/Sentinal/Sentinel/

521 ↗(On Diff #171957)

Because comments should be written like English prose, please use "vector" rather than "vec".

533 ↗(On Diff #171957)

I feel like this needs better explanation in general. Comments like these are fine, but the overall gist of the function needs to be written down somewhere.

For example,

"This function works by doing (blah). First we (do thing), then we (do other thing), and finally we (do another thing). At the end of this, (something) will (be in state)."

540–541 ↗(On Diff #171957)
  • This needs explanation.
  • Extra indent.
  • I recommend splitting this into two comments. The first can be something like, "Is this the first occurrence?", and the second can be something like "No. Merge metadata and attributes for the outlined instructions."
555 ↗(On Diff #171957)

What is special state?

561–562 ↗(On Diff #171957)

This sentence is awkward. The phrase "congruency finding" is kind of clunky IMO.

Also, once again, please define terminology you'll use throughout the code. I haven't seen a definition of "congruency" anywhere. That's a pretty heavily-overloaded math word, so it's good to make sure everyone is on the same page early in.

569 ↗(On Diff #171957)

No tails? Is that correct?

576–577 ↗(On Diff #171957)

Please be consistent with braces.

Also, when I see something like this, it smells like the logic can probably be tightened up a bit.

591 ↗(On Diff #171957)

I'm seeing a lot of inconsistencies in the variable names in for loops here.

Also, can this just be a range-based for?

599 ↗(On Diff #171957)

This should be in the else case.

600–601 ↗(On Diff #171957)

Once again, consistency with braces?

603 ↗(On Diff #171957)

I think basically everywhere there's a comment like this should have its own helper function. This function is very long.

613 ↗(On Diff #171957)

This comment should be in the else case.

625 ↗(On Diff #171957)

NumOutputs > 0 makes the assumption here more clear.

644 ↗(On Diff #171957)

What does finalize mean here?

Also, \brief is meaningless outside of Doxygen comments. This should be like

/// Finalize ...
648–660 ↗(On Diff #171957)

This probably deserves its own function.

679 ↗(On Diff #171957)

Re-unique

685 ↗(On Diff #171957)

Extra indent.

690 ↗(On Diff #171957)

"Group" is super confusing when you're using the word "congruency" here.

Some people might end up thinking of things like this when the terminology isn't defined:
https://en.wikipedia.org/wiki/Congruence_subgroup

702 ↗(On Diff #171957)

s/arg/argument/

Also, it makes more sense to say what you're *going to do*, since we're reading top-to-bottom. For example,

"Did we already evaluate the equivalencies for this argument? If so, then skip it."

721 ↗(On Diff #171957)

This smells like it deserves its own helper function.

728 ↗(On Diff #171957)

then

733 ↗(On Diff #171957)

non-congruent

747 ↗(On Diff #171957)

"non-congruent"

This shows up in a few places, so I guess a search + replace should help here.

751 ↗(On Diff #171957)

This could use a string explaining why you want this to be true.

763 ↗(On Diff #171957)

I'm not sure if clang-format will catch these, but... it would be good to remove all of these extra indents.

778 ↗(On Diff #171957)

s/Build new/Build a new/

Also, it's weird that this function is doing so many things. It should probably be split up into different tasks.

791 ↗(On Diff #171957)
  • Shouldn't be a Doxygen comment.
  • s/Fn/function/
  • Body doesn't need to be capitalized.
809 ↗(On Diff #171957)

Don't use Doxygen here.

812 ↗(On Diff #171957)

Don't use Doxygen here.

826 ↗(On Diff #171957)

Consistency with braces?

831–832 ↗(On Diff #171957)

There should be a comment here explaining what you did at the end of the function, and what's true now.

835 ↗(On Diff #171957)

Replace with a doxygen comment.

/// Outline...

Also why is this a separate case?

841 ↗(On Diff #171957)

Don't use Doxygen here.

848 ↗(On Diff #171957)

Don't use Doxygen here.

851 ↗(On Diff #171957)

This needs a comment explaining why (along with the other attributes).

858 ↗(On Diff #171957)

Don't use Doxygen here.

866 ↗(On Diff #171957)

Is this a safe thing to do? Can you explain why in the comment?

875 ↗(On Diff #171957)

Is this something you should really do? I can understand the motivation, but I don't know if I agree with tagging things as cold when they really might not be.

886 ↗(On Diff #171957)

Don't use Doxygen here.

Also this needs its own function. This function is too long.

891 ↗(On Diff #171957)

NumOutputs > 0?

I feel like this could be tightened up a bit more as is anyway...

904 ↗(On Diff #171957)

Don't use Doxygen here.

911 ↗(On Diff #171957)

Don't use Doxygen here.

931 ↗(On Diff #171957)

Don't use Doxygen here.

955 ↗(On Diff #171957)

"Set if" or "True if"

965 ↗(On Diff #171957)

Don't need \brief.

"Outline" is clunky, probably better to use "outlining".

This revision now requires changes to proceed.Oct 31 2018, 4:38 PM

Jessica,

Thanks for the quick review!

Please keep in mind, this is not my original work, but River's. I
inherited it once he moved on from Sony.  So I may not be able to answer
all of your questions, nor break this into smaller pieces

On testing.
I believe there are a couple of tests in River's source.  I will import
those.
Testing has been done mostly by csmith for correctness and then
baselining a regression set.
The regression set does
  clang -Oz
  clang -Oz -mllvm -enable-cso
  checksize

checksize 'crashes' when iro produces a smaller object.
After a couple of thousand 'crashes', creduce minimizes them into a
couple of thousand testcases.
This i believe will provide better coverage than the few tests in llvm's
regression testsuite. The downside, is they would be brittle.  And so
needs to be down wrt a stable branch, that is why I also have a
release_70-iro.

I agree that there is overlap between MO and would agree that using what
is in the tree is better than add more to it.  I have done a POC on how
this would go, mostly it is generalizing the MO bits with templates. 
This would be a fairly large refactor with some risk of breaking MO and IRO.

So similar to IRO, I am also generating a 1000+ MO csmith/creduce baseline.

I agree on the clunkyness of the name 'codesizeoutliner',  I would
rather it be ir-outliner, to be consistent with machine-outliner.

If you would like to help on the refactor, that would be good.

Tom

dmgreen added a subscriber: dmgreen.Nov 4 2018, 8:22 AM
zzheng added a subscriber: zzheng.Nov 7 2018, 2:20 PM
trixirt updated this revision to Diff 174435.Nov 16 2018, 1:07 PM

CodesizeOutliner has been changed to IROutliner
cli to enable has changed for *-cso to *-ir-outliner
Generated functions prefix changed for cso_ to _iro_
Some tests add.
Most issues in review fixed.
Exception is for significant refactoring, which was deferred to the larger task for refactoring MO/IRO to use MO infra.
A proof-of-concept of this refactor is https://github.com/trixirt/llvm/tree/master-poc-mo-refactor

yroux added a subscriber: yroux.Nov 21 2018, 8:42 AM

Hi Tom,

I've tested your patch on 32 bits ARM target (in thumb2 mode) on top of my
Machine Outliner prototype. The code size reduction is not as good as good as
the ones reported a year ago on x86 and AArch64 (around 1% in geomean over Oz
for Spec2k6 and 1.7% when combined with the Machine Outliner), but it is the
same thing for the Machine Outliner in Thumb2, and it is still interesting, so
thanks for the work done.

On CoremarkPro, which is not good candidate for Ouliners, it performs a bit
better than the Machine Ouliner, but there is a build issue for sha256.c when
early and late IR Outlining are combined. I didn't had time to make a reduce
test case, but let me know if you are not able to reproduce it.

Yvan,
Thanks for giving this a try!
I do not have codemark pro, but tried the scenarios you mentioned out on the codemark.
No build problems, unfortunately.
If you can reproduce the problem, please send me the *.i
The MO/IRO refactoring i am doing may impact your thumb mo.
If you have a public dev branch for this, please send me the link.

yroux added a comment.Nov 26 2018, 4:51 AM

Ok, I don't think I'm allowed to share the bench sources, so I've creduced the problem and will send you the small obfuscated testcase and command lines.

I don't have a public branch available, but I'll submit a MO ARM support RFC soon.

Yvan,
I believe have a fix for the issue you found which can be found in my master-iro branch
https://github.com/trixirt/llvm/commit/873ce17e5fced2048b8c37b72cb5639041758226
Once it has made it through some more testing, I will merge it into this request.

Herald added a project: Restricted Project. · View Herald TranscriptApr 16 2019, 12:26 PM
Herald added a subscriber: dexonsmith. · View Herald Transcript

What is the status of this diff? I tried this on a LLVM IR generated from swift compiler and found errors related to broken functions.

swifterror argument for call has mismatched parameter
%swift.error** %0
  tail call swiftcc void @swift_willThrow(i8* swiftself undef, %swift.error** noalias nocapture nonnull readonly swifterror dereferenceable(8) %0) #4
in function _iro_109
LLVM ERROR: Broken function found, compilation aborted!
kyulee added a subscriber: kyulee.Jun 15 2021, 7:10 AM