Page MenuHomePhabricator

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

There are a very large number of changes, so older changes are hidden. Show Older Changes
paquette added inline comments.Oct 31 2018, 4:38 PM
lib/Transforms/IPO/CodeSizeOutliner.cpp
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.

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