PGO IR-level instrumentation infrastructure

[xur]

Summary

This patch implements the infrastructure for PGO late (i.e. IR-level) instrumentation. (Refer to RFC: PGO Late instrumentation for LLVM http://lists.llvm.org/pipermail/llvm-dev/2015-August/089058.html)

The main part of code is in a newly added file: lib/Transforms/Instrumentation/PGOLateInstr.cpp
This file implements a module pass PGOLateInstrumeatnion. It applies the instrumentation to each function by class PGOLateInstrumentationFunc. For each function, perform the following steps:
(1) Collect all the CFG edges. Assign an estimated weight to each edge. Critical edges and back-edges are assigned to high value of weights. One fake node and a few fake edges (from the fake node to the entry node, and from the exit nodes to the fake node) are also added to the worklist.
(2) Construct the MST. The edges with the higher weight will be put to MST first, unless it forms a cycle.
(3) Traverse the CFG and compute the CFG hash.

The above three steps are the same for profile-generate and profile-use compilation.

In the next step, for profile-generation compilation:
(4-gen) Instrument all the edges that not in the MST. If this is a critical edge, split the edge first. The actual instrumentation is to generate Intrinsic::instrprof_increment() in the instrumented BB. This intrinsic will be lowed by pass createInstrProfilingPass().

For profile-use compilation,
(4-use) Read in the counters and the CFG hash from the profile file.
(5-use) If there is no error, populate the counters to all the edges in reverse topological order of the MST.
(6-use) Once having all the edge counts, set the branch weights metadata for the IR having multiple branches. Also apply the cold/hot function attributes based on function level counts.

This pass is added to PassManagerBuilder when populate module passes. see lib/Transforms/IPO/PassManagerBuilder.cpp.

[silvas]

lib/Transforms/Instrumentation/CFGMST.h

162

Factor the DEBUG macro usage into a single point of truth here. E.g. factor out a function printEdges(raw_ostream &OS, const StringRef Message). Then change this function to be simply DEBUG(dumpEdges(dbgs(), Message)). (this is similar to the pattern used by Value, for example).

This will also give clang-format an easier time.

187

Use std::tie

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

152

Other places seem to use uint64_t for weight. Why unsigned here?

178

Does this actually need to be virtual? Same for all the other virtual methods in this file.

218

"dump" functions are for debugging and should be conditionalized. For example, I suggest refactoring to allow a call

DEBUG(
std::string Message = "Dump Function " + FuncName +
                          " after CFGMST: \t Hash: " +
                          std::to_string(FunctionHash);
MST.dumpEdges(dbgs(), Message);
)

440

Avoid having debug code be non-conditional.

450

Avoid const std::unique_ptr<PGOUseEdge> &.

655

Use a free function instrumentOneFunc

686

Use a free function setPGOCountOnFunc

[silvas]

Also, can you begin to work on tests? I think right now the core algorithm is pretty good. There are some cleanups to the implementation that I'd like to see but I can do those post-commit if necessary. Right now the main missing piece needed before this is committed are tests.

[davidxl]

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

201

if there is no BB ..

409

It is better to just call it 'setEdgeCount' with same documentation -- or make it just

getUnknownCountEdge() and let the client to set the edge directly.

450

Sean's comment here is not addressed -- use raw PGOUseEdge&

461

In general it is not safe to update the container (AllEdges) while iterating -- it may invalidate the iterator or element reference saved before. The code should create a worklist of edges before the count setting -- the worklist will then be 'frozen' (It is safe to update worklist, but there is no need to push new split edges into the list) and AllEdges can be safely updated.

497

Use the new getInstrProfRecord method -- eventually we will need to read value profile data too.

[xur]

lib/Transforms/Instrumentation/CFGMST.h

111

reorganized the code, also handles overflow.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

152

changed to uint64_t.

440

Now guarded by DEBUG.

461

I see your point. But this is exactly the reason I did not use range-based loop like all others in the file. I get the vector size in the loop initialization and use the index to reference the vector elements in the body. So adding element to the vector will not be a problem. I could use a worklist, but the effect should be the same.

[xur]

Here is the latest patch that integrated Sean and David Li's comments.
I'm working on the test case. One thing I'm not clear is that I need the passmanagerbuild change to invoke the new functionality. That part of code was split from this patch from Manman's review comments.

-Rong

[silvas]

Some more small comments.

lib/Transforms/Instrumentation/CFGMST.h

94

Use a real variable.

192

llvm::make_unique

194

return *AllEdges.back()

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

32

Give intuition for why it is edges *not in* the MST rather than edges *in* the MST? Edges with high counts should have high weight and therefore *not* be in the MST (which tries for minimum weight); we don't want to instrument edges with high counts, and they are *not* in the MST, so why would we place counters there?

149

Please cite the Knuth paper. Also explain what we actually do with the MST (and give intuition for why that makes sense (it's fairly simple, should not need a long explanation)).

294

Make these two variable just local variables of instrumentOnFunc free function.

307

This is only called in one place, inline the code into instrumentOnFunc.

474

Can you use continue to reduce indentation for the "large" side of the if? ( http://llvm.org/docs/CodingStandards.html#use-early-exits-and-continue-to-simplify-code )

514

Do you mean to do a copy here? Probably std::vector<uint64_t> & is intended.

519

e instead of E, as is common in LLVM.

544

getBBInfo(Ei->SrcBB). You shouldn't need a cast here (if you do, then please fix whatever code is requiring this to cast away constness).

567

Just make the iteration variable BB and use getBBInfo(&BB), like you do below in the loop // Assert every BB has a valid counter..

634

Remove the const_cast (I think this will require making GetSuccessorNumber take const BasicBlock *, which you can do as a separate patch (no need for pre-commit review))

653

Do you mean instrumentOneFunc? instrumentOnFunc doesn't make sense (weird use of "on").

[xur]

Thanks for the suggestion. All fixed. Please refer to the newest patch for the update.

[xur]

Updated with Sean's new comments.
Also includes the unit tests.

Thanks,

-Rong

[davidxl]

Can you also add a script to re-generate the binary profile data needed whenever profile format changes ?

[xur]

These .ll files are the complete program IR that can generate the
profiles. I can embed the commands in the comment of the .ll files. Just
to make sure: You want a separated shell script in the same director to
generate the profiles?

Thanks,

-Rong

[silvas]

These test files look like they are just a dump of IR generated from a C/C++, which is extremely verbose and has a lot of inessential details. I also don't like checking in binary profdata files. Overall these tests seem extremely brittle. I also don't understand why the test files have names like "for" or "goto" or "ifelse". Those concepts don't exist in the IR. Surely the tests should have names like "criticaledge" etc.

It seems like this testing might be more readable as C++ unit tests. Using the new pass manager this should be easy to wire up. I think the hardest part would be to stub out IndexedInstrProfReader.

[davidxl]

I thought about the size of the test case too. Initially I had the same
concern, but in second look, it does not seem to be brittle -- because it
just checks whether the key branches are properly annotated with the right
profile count or not, or profile counter update instruction is inserted or
not.

I think adding C++ unit tests are independent tasks which can be done once
the driver part of the changes land.

David

[xur]

I changed the regression tests based on the feedbacks from Sean, David and Justin. The IR is much simplified and the profile uses the text format.
I still keep the target triplet as x86_64-unknown-linux-gnu, because this is the only platform I tested. I will try to relax it later.

Thanks,

-Rong

[davidxl]

Looks good with the minor fix.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

310

Remove unused code.

[chapuni]

Seems it behaves differently on i686. Investigating.

See also; http://bb.pgr.jp/builders/clang-3stage-i686-linux/builds/3865
(It is configured as "gcc -m32")

[silvas]

Hi Rong,

Typically, when there have been multiple active reviewers, it is common
courtesy to wait for all of them to LGTM the patch.

I had further comments on the testing here (which the bots seem to have
caught you on anyway), so I recommend reverting this patch for the moment
and reopening the review.

• Sean Silva

[xur]

Fix a few issues that being exposed by the buildbot:
(1) wrong shift operation in functionhash computing,
(2) missing type cast for vector<...>size_type (which results bad functionhash in m32 host)
(3) sorting is not stable

Also improved the test checks suggested by Sean.

Thanks,

-Rong

[silvas]

I took another pass through, so some of the comments are nits. But most of the comments on the tests in particular are quite significant and not just "nits".

lib/Transforms/IPO/LLVMBuild.txt

23 ↗

(On Diff #41175)

Why does IPO now depend on Instrumentation, but didn't previously?
What is different about the PGO passes vs the other instrumentation passes?

lib/Transforms/Instrumentation/CFGMST.h

129

Naming convention.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

2

The length of this line does not match the one below.

12

typo: two spaces after 'the' should be just one space.

32

Why are they mutually exclusive? Weren't you wanting to the the count profile in MST computation eventually?

35

typo: "is done"

42

class PGOGenFunc is no longer present, please update the comment.

46

These header comments easily go out of date during patch review. I would recommend reading the comment from top to bottom and verifying that it is up to date.

87

This option is only for testing, so please rename it to make that clear (also update the description).

281

Do you still need these const_cast<>'s after r253733?

494

You say "edges" (plural) here but then say "There should be one and only one".

test/Transforms/PGOProfile/branch1_gen.ll

7 ↗

(On Diff #41175)

This would be more readable with a non-mangled name. (same for the other tests)

test/Transforms/PGOProfile/branch2_use.ll

10 ↗

(On Diff #41175)

Verify that it is attached to the instruction you expect (CHECK-SAME may be useful).

(same for the other "use" tests)

test/Transforms/PGOProfile/criticaledge_gen.ll

53 ↗

(On Diff #41175)

Will this test fail if the call ends up in the previous or next BB?

I would recommend, for each BB, having a CHECK line verifying the BB name, followed by either CHECK or CHECK-NOT verifying the presence or absence of the increment call.

test/Transforms/PGOProfile/criticaledge_use.ll

10 ↗

(On Diff #41175)

Please have the names consistent with the switch values.

25 ↗

(On Diff #41175)

This test case can be simplified further. At the very least, the function bar is not needed.

49 ↗

(On Diff #41175)

The convention for FileCheck variable captures is all upper case (e.g. [[BW2:[0-9]+]]).
Also, can you use more semantic names instead of numbers? E.g. BW_<name> instead of BW<number>.

test/Transforms/PGOProfile/loop2_use.ll

5 ↗

(On Diff #41175)

What part of the code is this test trying to cover that is not covered by loop3 or loop1? Do we need this test?

test/Transforms/PGOProfile/switch_gen.ll

6 ↗

(On Diff #41175)

You can merge the _gen and _use files by using FileCheck's option --check-prefix (e.g. --check-prefix=GEN or --check-prefix=USE).

Actually, doing this is necessary so that there is a single point of truth for the IR used by both.

test/Transforms/PGOProfile/switch_use.ll

16 ↗

(On Diff #41175)

These add instructions are not needed. Just make the function return void.

[xur]

Thanks for Sean's suggestion. They indeed make the tests cleaner and more robust. I integrated his reviews in the latest patch that I'll post soon.

lib/Transforms/IPO/LLVMBuild.txt

23 ↗

(On Diff #41175)

thanks for catching this. This should not be there -- it is only needed for the passmangerbuilder change.

test/Transforms/PGOProfile/criticaledge_use.ll

25 ↗

(On Diff #41175)

bar is a file static function and was used to check the source name is part of the profile variable name.

[xur]

Integrated Sean's most recently review comments.

[silvas]

The tests are looking great! A couple nits and a final question about the test.

test/Transforms/PGOProfile/branch1.ll

32

Can you use CHECK-DAG directive to move these next to the place where the BW_* capture occurs? That would improve locality and clarify what is being checked.

(same in the other files)

test/Transforms/PGOProfile/checksum_mismatch.ll

4 ↗

(On Diff #41428)

Tiny nit: could you name all the tests which are just checking diagnostics to match diag_*.ll? (or whatever naming convention seems appropriate)

That will help to clearly identify them.

test/Transforms/PGOProfile/loop2.ll

10

What is the importance of testing a nested for loop? What part of the code are you trying to exercise that isn't covered by loop1.ll?

[davidxl]

test/Transforms/PGOProfile/loop2.ll

10

Having loop nest in the test for better coverage is fine -- but looks like we don't actually need 3-deep nest -- a 2-deep loop nest is good enough and will be easier to read.

loop1.ll has a loop with top test. How about a loop test with bottom testing. Also a loop with more control flow inside the body, and a loop with early exit might be nice to have -- but those can be added later as follow ups if needed.

[xur]

@silvas:
It's not clear how can I use CHECK-DAG to group together the branch weight
meta data and the related instruction. if there is a single instruction and
single meta data, I can move up the branch weight meta data next the the
instruction. But if there are multiple, I don't know how to do it. From
the document, CHECK-DAG can be used b/w two matches (or before the first
match, or after the last match). Move the branch-weight meta data and use
USE-DAG is not working.

I also tried to change all use USE to USE (except the first and last). That
won't work either.

As for the loop2, it just a more complex data flow. I'll change it to two
level nexted loop according to David's suggestion.

@david:
I used to use a buttom test loop, but I removed based on silvas's
suggestion. I'll add more tests later if necessary.

[xur]

Integrated most recent review comments from Sean, David and Justin.
Let me know if I missed anything.

Thanks,

-Rong

[xur]

Sean, Justin and David: Do you have any comment on the latest patch?
If it looks fine to you, I plan to submit it again this week.

Thanks!

-Rong