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.

[xur]

This new patch integrated David's review comments. The main changes are
(1) more efficient code for union-find algorithm.
(2) merge EdgeCount structure into Edge
(3) merge BBGroupInfo and BBCount into and rename it to BBInfo.

[xur]

The reason I do not call SplitAllCriticalEdges is because I don't want to
split all critical edges. I only split these critical edges that need to be
instrumented. For critical edges, I prioritize them into MST to avoid the
split.

-Rong

[silvas]

A couple more comments I spotted when going back through the patch again.

include/llvm/ProfileData/InstrProfWriter.h

44–45 ↗

(On Diff #35559)

Why do we need to modify InstrProfWriter.{h,cpp}? That seems like a layering violation.

lib/Transforms/Instrumentation/PGOLateInstr.cpp

270–278 ↗

(On Diff #35559)

No naked new/delete. Use RAII (e.g. you can probably use BumpPtrAllocator to allocate these).

[davidxl]

lib/ProfileData/InstrProfWriter.cpp

86–94 ↗

(On Diff #35559)

Please add a comment.

lib/Transforms/Instrumentation/PGOLateInstr.cpp

117 ↗

(On Diff #35559)

make it std::vector<std::unique_ptr<Edge>>

150 ↗

(On Diff #35559)

make it DenseMap<const BasicBlock *, std::unique_ptr<BBInfo>> BBInfos;

272 ↗

(On Diff #35559)

No need for explicit delete with unique_ptr

336 ↗

(On Diff #35559)

You can use the ReversePostOrderTraversal Class defined in ADT/PostOrderIterator.h. Actually does the order of traverse matter here?

349 ↗

(On Diff #35559)

What is the rationale of this heuristic?

351 ↗

(On Diff #35559)

Why not compute BlockFrequencyInfo and use the real static Edge frequency (from BB freq and edge prob)? For Critical edge, the weight can be increased to infinite.

493 ↗

(On Diff #35559)

As the name linkage function, the name globalization function also needs to be a common interface which FE instrumentation can share in the future.

516 ↗

(On Diff #35559)

This code is shared with FE based instrumentation and it should be refactored as a utility function. Suggested location: include/llvm/Transformation/Instrumentation.h.

Converting FE to use the common interface can be done as a follow-up patch

666 ↗

(On Diff #35559)

Make reader a shared object at module level.

[xur]

Here is the updated patch that integrated David and Sean's comments and suggestions. The major changes are:

• move profile reader to module level.
• move minimum spanning tree into a utility class.
• separate profile generate and use into to two separated passes.
• use static profile to set the edge weights.
• move the code that can be shared with clang instrumentation to include/llvm/Transforms/Instrumentation.h as utility functions.
• name change (using IR instrumentation now)
• move InstrProfWrite to a later patch.

I did not use ReversePostOrderTraversal in ADT/PostOrderiterator.h (David suggested) as compared to current version, it leads to more passes to populate the counters.

I think it is better to separate this IR level instrumentation from FE code, to avoid code duplication for other language frond-ends. So I keep to pass the file name instead of IndexedInstrProfRead to llvm. The error checking is already well encapsulated in getFunctioncounts() and ProfReader(). I kept it in middle end too.

I will add unit tests for both minimum spanning tree and IR instrumentation later.

[manmanren]

Thanks for working on this!

Mostly nitpicking. I haven't really looked at the implementation yet.

Manman

include/llvm/InitializePasses.h

123 ↗

(On Diff #39382)

Nit: it is a little strange to change some of the formatting.

include/llvm/Support/CFGMST.h

35 ↗

(On Diff #39382)

Nit: It may contain

49 ↗

(On Diff #39382)

Nit: Find

165 ↗

(On Diff #39382)

This will cause "unused variable" warning when building clang without assertion.

173 ↗

(On Diff #39382)

Same here.

lib/Transforms/IPO/PassManagerBuilder.cpp

247 ↗

(On Diff #39382)

Can you commit this separately if it is necessary?

lib/Transforms/Instrumentation/PGOIRInstr.cpp

140 ↗

(On Diff #39382)

Should you add const here "infoString() const {"?

145 ↗

(On Diff #39382)

This seems wrong. StringRef does not own the string data.

[manmanren]

include/llvm/Support/CFGMST.h

36 ↗

(On Diff #39382)

Can you add some high-level comments for CFGMST? What fields does this class expect on Edge and BBInfo? And what Removed field is used for? Do all members need to be public?

92 ↗

(On Diff #39382)

Use nullptr instead of 0?

181 ↗

(On Diff #39382)

typo

187 ↗

(On Diff #39382)

make_unique?

195 ↗

(On Diff #39382)

emplace_back maybe?

lib/Transforms/IPO/PassManagerBuilder.cpp

194 ↗

(On Diff #39382)

typo: option

[majnemer]

lib/Transforms/Instrumentation/PGOLateInstr.cpp

301–302 ↗

(On Diff #34503)

We already have a CRC implementation in LLVM, do we need another one? Ours lives in <llvm/Support/JamCRC.h>

I'd imagine the one we have in-tree is considerably faster than this one...

[davidxl]

include/llvm/Support/CFGMST.h

1 ↗

(On Diff #39382)

CFGMST.h.

29 ↗

(On Diff #39382)

It seems that this class is still not general enough to be put into llvm/Support/ directory, I suggest move this file back to PGO directory for now.

A more general implementation should also support MachineBB. Also what interfaces need to be exposed, and what template parameters are needed, do we really need to expose edge at interface level (for this class, instead just use a pair of BBs to query on-tree status?) do we need to pass in opaque edge info types (which only clients know about) etc are all open questions -- this is the reason I don't think it is ready to be put into Support. Add a TODO for future work there.

More comments will follow later.

[xur]

Thanks Manman Ren and David Majnemer for the code review. I have integrated their feedbacks to the newly upload patch.
The only thing I did not do is the "make_unque" suggestion by Manman. It seems to be a c++14 feature and I got an compile time error for that.

I'll integrate David Li's feedback in a later patch.

Thanks,

-Rong

[silvas]

This is looking really good!

My biggest concern overall about the implementation is that there seems to be overuse of classes (unnecessary inheritance; unusual use of constructors). It creates quite a maze.

I think that in the process of cleaning up the awkward PGOIRInstrumentationGenFunc Func(F, &M, BPI, BFI); to be free functions (see comment inline) you will find many simplifications to the entire implementation.

Remember, the purpose of a constructor is to initialize the invariants for the class's data members. Don't "do an algorithm" in a constructor or execute "steps" of a procedural computation.

include/llvm/Transforms/Instrumentation.h

182 ↗

(On Diff #39600)

Use correct capitalization http://llvm.org/docs/CodingStandards.html#commenting

184 ↗

(On Diff #39600)

http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

(here and elsewhere)

lib/Transforms/Instrumentation/PGOIRInstr.cpp

10 ↗

(On Diff #39600)

"IR level" is redundant since this is in lib/Transforms.

Please give an overview here of the structure of the file. (2 module passes: "use" and "gen"). Also explain their relationship, sharing data structures, etc.

124 ↗

(On Diff #39600)

There's a lot of things here that don't seem to be used externally. So use an anonymous namespace.

161 ↗

(On Diff #39600)

Do you actually need dynamic dispatch?

167 ↗

(On Diff #39600)

Why "IR"? Are you planning to generalize this to Machine? For now just leave off "IR" (here and elsewhere).

193 ↗

(On Diff #39600)

Switch to using a trailing underscore. Names starting with underscore followed by a capital letter are reserved for the implementation (it is undefined behavior to name a variable like that).

295 ↗

(On Diff #39600)

Avoid std::unique_ptr<T> &. For a simple non-owning handle, use a T *. If you don't need to store the handle and the value is guaranteed non-null, consider using T &.

Same applies in many other parts of this patch where std::unique_ptr<T> & is used.

337 ↗

(On Diff #39600)

This class is local to this file, right? No need to use such a large name; makes it sound like this is for an external interface or something.

(same comment applies to many other things in this file; I think that the module passes themselves are the only things that really need "PGOInstrumentation" prefix on their name)

Look at e.g. lib/Transforms/SROA.cpp with e.g. names like Slice or AllocaSlices.

340 ↗

(On Diff #39600)

I don't think wrapping behavior is intended, so avoid unsigned types.

368 ↗

(On Diff #39600)

Nit: ArrayRef

440 ↗

(On Diff #39600)

Nit: no braces.

505 ↗

(On Diff #39600)

http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

517 ↗

(On Diff #39600)

nullptr.

524 ↗

(On Diff #39600)

In what way? And why does it matter to know that here?

563 ↗

(On Diff #39600)

Just use reverse adapter from llvm/ADT/STLExtras.h

627 ↗

(On Diff #39600)

Just declare this as SmallVector<unsigned, 2> EdgeCounts(Size, 0);

631 ↗

(On Diff #39600)

Is this ever initialized?

632 ↗

(On Diff #39600)

Can you use a range-for?

638 ↗

(On Diff #39600)

Can you fix GetSuccessorNumber to take a const BasicBlock *? (hopefully it is a pretty obvious fix and there is no need for pre-commit review).
Then you can get rid of all these const_cast's.

665 ↗

(On Diff #39600)

This is extremely awkward (declaring a local variable as a way to do a stateful mutating operation). Just use a free function. Same thing for the similar line with PGOIRInstrumentationUseFunc below.

[davidxl]

include/llvm/Support/CFGMST.h

78 ↗

(On Diff #39600)

Return BBInfo& instead of unique_ptr<BBInfo>&. It is more efficient for uses later .

81 ↗

(On Diff #39600)

assert It->second.get() != null.

Return *It->second.get().

94 ↗

(On Diff #39600)

Add more comments explaining here why need two duplicate fake edges.

104 ↗

(On Diff #39600)

Redundant guard.

105 ↗

(On Diff #39600)

Make successors and i 'unsigned' type.

110 ↗

(On Diff #39600)

Use a macro for 1000? CRITICAL_EDGE_MULTIPLIER? Also handling overflow situation?

113 ↗

(On Diff #39600)

Stale code.

127 ↗

(On Diff #39600)

--> sortEdgesByWeight

146 ↗

(On Diff #39600)

Should this be marked unconditionally here? Otherwise, we can simply boost the weight for such edges even higher without special treatment here?

184 ↗

(On Diff #39600)

Make Edge* the return type for efficiency.

185 ↗

(On Diff #39600)

Use a const var for default weight.

186 ↗

(On Diff #39600)

Combine the find + insert pattern into one insert (with pair of source BB and null ptr). If the map is updated, a iterator is returned that can be updated with unique_ptr reset.

191 ↗

(On Diff #39600)

Same here.

197 ↗

(On Diff #39600)

return AllEdges.back().get();

lib/Transforms/Instrumentation/PGOIRInstr.cpp

167 ↗

(On Diff #39600)

There was an earlier suggestion to change 'Late' in PGOLateInstrumentation to 'IR'. To add more to the bikeshed, I suggest change the class name to

class FuncPGOInstrumentation {
};

181 ↗

(On Diff #39600)

Mst --> MST or MinSpanTree.

185 ↗

(On Diff #39600)

BasicBlock *getInstrBB(const Edge &E);

[silvas]

lib/Transforms/Instrumentation/PGOIRInstr.cpp

167 ↗

(On Diff #39600)

The suggestion to use "IR" instead of "Late" is just for informal discussion when needed to differentiate from what we currently have in clang. For comments in code or naming variables, all code in lib/Transforms is inherently at IR level so it is redundant. For example, we do not have a "SROAIR" pass or "InstCombineIR" pass etc. (grep for "IR" in lib/Transforms to see typical usage; it is almost never used)

[davidxl]

include/llvm/Transforms/Instrumentation.h

183 ↗

(On Diff #39600)

An interface is available in ProfileData/InstrProf.h:

llvm::getPGOFuncName

which is also used by cfe.

Remove this dup.

210 ↗

(On Diff #39600)

Similarly llvm::createPGOFuncNameVar will do what you need.

Remove this duplicate.

[xur]

Thank David and Sean for the detailed comments -- they are really helpful.
I integrated the review to the patch. Could you please take a look. Thanks!

include/llvm/Support/CFGMST.h

94 ↗

(On Diff #39600)

This is a mistaken introduced in the lat minute formatting. Fixed.

104 ↗

(On Diff #39600)

why Redundant? numsuccessors can be 0 (and these is else branch)

146 ↗

(On Diff #39600)

The reason to split two passes is for the case of using profile count value as the weight, in which the values can vary drastically.

185 ↗

(On Diff #39600)

removed the default weight.

lib/Transforms/Instrumentation/PGOIRInstr.cpp

161 ↗

(On Diff #39600)

it returns different information strings. I can get rid of it. But I don't think it really matters -- it only used in debug printing.

524 ↗

(On Diff #39600)

you are right. This comment is unnecessary and does not belong here. Deleted.

631 ↗

(On Diff #39600)

good catch. fixed.

638 ↗

(On Diff #39600)

Will do this later.

[xur]

Here is the latest patch that integrated David and Sean's comments.

[silvas]

The use of inheritance is still excessive. For example, PGOUseFunc and PGOGenFunc don't seem to need inheritance. Their "subclass state" would be better as local variables of a free function. FuncPGOInstrumentation does not need to be a base class. It can simply be a FuncInfo class that manages/caches information about a single function. Both uses of FuncPGOInstrumentation seem to call performOnFunc before they do anything else, so this appears to be establishing an invariant for the class, so this operation should be performed in the constructor (this is much more natural as FuncInfo; the complex construction was confusing when it was a base class).

lib/Transforms/Instrumentation/CFGMST.h

39 ↗

(On Diff #40187)

Use a lambda.

110 ↗

(On Diff #40187)

Move the declaration for bool Critical = false; down one line and simplify to bool Critical = isCriticalEdge(TI, i);

138 ↗

(On Diff #40187)

No need to mention clang here. Please file a bug report for this if there isn't one open already.

206 ↗

(On Diff #40187)

Avoid using reserved names.

[silvas]

lib/Transforms/Instrumentation/CFGMST.h

161 ↗

(On Diff #40187)

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.

186 ↗

(On Diff #40187)

Use std::tie

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

151 ↗

(On Diff #40187)

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

177 ↗

(On Diff #40187)

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

217 ↗

(On Diff #40187)

"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);
)

439 ↗

(On Diff #40187)

Avoid having debug code be non-conditional.

449 ↗

(On Diff #40187)

Avoid const std::unique_ptr<PGOUseEdge> &.

654 ↗

(On Diff #40187)

Use a free function instrumentOneFunc

685 ↗

(On Diff #40187)

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

200 ↗

(On Diff #40187)

if there is no BB ..

408 ↗

(On Diff #40187)

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.

449 ↗

(On Diff #40187)

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

460 ↗

(On Diff #40187)

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.

496 ↗

(On Diff #40187)

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

[xur]

lib/Transforms/Instrumentation/CFGMST.h

110 ↗

(On Diff #40187)

reorganized the code, also handles overflow.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

151 ↗

(On Diff #40187)

changed to uint64_t.

439 ↗

(On Diff #40187)

Now guarded by DEBUG.

460 ↗

(On Diff #40187)

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

93 ↗

(On Diff #40361)

Use a real variable.

191 ↗

(On Diff #40361)

llvm::make_unique

193 ↗

(On Diff #40361)

return *AllEdges.back()

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

31 ↗

(On Diff #40361)

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?

148 ↗

(On Diff #40361)

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)).

293 ↗

(On Diff #40361)

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

306 ↗

(On Diff #40361)

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

473 ↗

(On Diff #40361)

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 )

513 ↗

(On Diff #40361)

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

518 ↗

(On Diff #40361)

e instead of E, as is common in LLVM.

543 ↗

(On Diff #40361)

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).

566 ↗

(On Diff #40361)

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

633 ↗

(On Diff #40361)

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))

652 ↗

(On Diff #40361)

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

309 ↗

(On Diff #41062)

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

128 ↗

(On Diff #41175)

Naming convention.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1 ↗

(On Diff #41175)

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

11 ↗

(On Diff #41175)

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

31 ↗

(On Diff #41175)

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

34 ↗

(On Diff #41175)

typo: "is done"

41 ↗

(On Diff #41175)

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

45 ↗

(On Diff #41175)

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.

86 ↗

(On Diff #41175)

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

280 ↗

(On Diff #41175)

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

493 ↗

(On Diff #41175)

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

31 ↗

(On Diff #41428)

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

9 ↗

(On Diff #41428)

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

9 ↗

(On Diff #41428)

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

llvm/trunk/include/llvm/IR/DiagnosticInfo.h

enum DiagnosticKind {
   DK_SampleProfile,
   DK_OptimizationRemark,
   DK_OptimizationRemarkMissed,
   DK_OptimizationRemarkAnalysis,
   DK_OptimizationRemarkAnalysisFPCommute,
   DK_OptimizationRemarkAnalysisAliasing,
   DK_OptimizationFailure,
   DK_MIRParser,
+  DK_PGOProfile,
   DK_FirstPluginKind
 };
 
 /// \brief Get the next available kind ID for a plugin diagnostic.
 /// Each time this function is called, it returns a different number.
 /// Therefore, a plugin that wants to "identify" its own classes
 /// with a dynamic identifier, just have to use this method to get a new ID
 /// and assign it to each of its classes.
private:
   /// Line number where the diagnostic occurred. If 0, no line number will
   /// be emitted in the message.
   unsigned LineNum;
 
   /// Message to report.
   const Twine &Msg;
 };
 
+/// Diagnostic information for the PGO profiler.
+class DiagnosticInfoPGOProfile : public DiagnosticInfo {
+public:
+  DiagnosticInfoPGOProfile(const char *FileName, const Twine &Msg,
+                           DiagnosticSeverity Severity = DS_Error)
+      : DiagnosticInfo(DK_PGOProfile, Severity), FileName(FileName), Msg(Msg) {}
+
+  /// \see DiagnosticInfo::print.
+  void print(DiagnosticPrinter &DP) const override;
+
+  static bool classof(const DiagnosticInfo *DI) {
+    return DI->getKind() == DK_PGOProfile;
+  }
+
+  const char *getFileName() const { return FileName; }
+  const Twine &getMsg() const { return Msg; }
+
+private:
+  /// Name of the input file associated with this diagnostic.
+  const char *FileName;
+
+  /// Message to report.
+  const Twine &Msg;
+};
+
 /// Common features for diagnostics dealing with optimization remarks.
 class DiagnosticInfoOptimizationBase : public DiagnosticInfo {
 public:
   /// \p PassName is the name of the pass emitting this diagnostic.
   /// \p Fn is the function where the diagnostic is being emitted. \p DLoc is
   /// the location information to use in the diagnostic. If line table
   /// information is available, the diagnostic will include the source code
   /// location. \p Msg is the message to show. Note that this class does not

llvm/trunk/include/llvm/InitializePasses.h

 void initializeDomViewerPass(PassRegistry&);
 void initializeDominanceFrontierPass(PassRegistry&);
 void initializeDominatorTreeWrapperPassPass(PassRegistry&);
 void initializeEarlyIfConverterPass(PassRegistry&);
 void initializeEdgeBundlesPass(PassRegistry&);
 void initializeExpandPostRAPass(PassRegistry&);
 void initializeAAResultsWrapperPassPass(PassRegistry &);
 void initializeGCOVProfilerPass(PassRegistry&);
+void initializePGOInstrumentationGenPass(PassRegistry&);
+void initializePGOInstrumentationUsePass(PassRegistry&);
 void initializeInstrProfilingPass(PassRegistry&);
 void initializeAddressSanitizerPass(PassRegistry&);
 void initializeAddressSanitizerModulePass(PassRegistry&);
 void initializeMemorySanitizerPass(PassRegistry&);
 void initializeThreadSanitizerPass(PassRegistry&);
 void initializeSanitizerCoverageModulePass(PassRegistry&);
 void initializeDataFlowSanitizerPass(PassRegistry&);
 void initializeScalarizerPass(PassRegistry&);

llvm/trunk/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createDeadStoreEliminationPass();
       (void) llvm::createDependenceAnalysisPass();
       (void) llvm::createDivergenceAnalysisPass();
       (void) llvm::createDomOnlyPrinterPass();
       (void) llvm::createDomPrinterPass();
       (void) llvm::createDomOnlyViewerPass();
       (void) llvm::createDomViewerPass();
       (void) llvm::createGCOVProfilerPass();
+      (void) llvm::createPGOInstrumentationGenPass();
+      (void) llvm::createPGOInstrumentationUsePass();
       (void) llvm::createInstrProfilingPass();
       (void) llvm::createFunctionInliningPass();
       (void) llvm::createAlwaysInlinerPass();
       (void) llvm::createGlobalDCEPass();
       (void) llvm::createGlobalOptimizerPass();
       (void) llvm::createGlobalsAAWrapperPass();
       (void) llvm::createIPConstantPropagationPass();
       (void) llvm::createIPSCCPPass();

llvm/trunk/include/llvm/Transforms/Instrumentation.h

struct GCOVOptions {
 
   // Emit the exit block immediately after the start block, rather than after
   // all of the function body's blocks.
   bool ExitBlockBeforeBody;
 };
 ModulePass *createGCOVProfilerPass(const GCOVOptions &Options =
                                    GCOVOptions::getDefault());
 
+// PGO Instrumention
+ModulePass *createPGOInstrumentationGenPass();
+ModulePass *
+createPGOInstrumentationUsePass(StringRef Filename = StringRef(""));
+
 /// Options for the frontend instrumentation based profiling pass.
 struct InstrProfOptions {
   InstrProfOptions() : NoRedZone(false) {}
 
   // Add the 'noredzone' attribute to added runtime library calls.
   bool NoRedZone;
 
   // Name of the profile file to use as output

 // BoundsChecking - This pass instruments the code to perform run-time bounds
 // checking on loads, stores, and other memory intrinsics.
 FunctionPass *createBoundsCheckingPass();
 
 /// \brief This pass splits the stack into a safe stack and an unsafe stack to
 /// protect against stack-based overflow vulnerabilities.
 FunctionPass *createSafeStackPass(const TargetMachine *TM = nullptr);
 
+/// \brief Calculate what to divide by to scale counts.
+///
+/// Given the maximum count, calculate a divisor that will scale all the
+/// weights to strictly less than UINT32_MAX.
+static inline uint64_t calculateCountScale(uint64_t MaxCount) {
+  return MaxCount < UINT32_MAX ? 1 : MaxCount / UINT32_MAX + 1;
+}
+
+/// \brief Scale an individual branch count.
+///
+/// Scale a 64-bit weight down to 32-bits using \c Scale.
+///
+static inline uint32_t scaleBranchCount(uint64_t Count, uint64_t Scale) {
+  uint64_t Scaled = Count / Scale;
+  assert(Scaled <= UINT32_MAX && "overflow 32-bits");
+  return Scaled;
+}
+
 } // End llvm namespace
 
 #endif

llvm/trunk/lib/IR/DiagnosticInfo.cpp

if (!FileName.empty()) {
     DP << getFileName();
     if (LineNum > 0)
       DP << ":" << getLineNum();
     DP << ": ";
   }
   DP << getMsg();
 }
 
+void DiagnosticInfoPGOProfile::print(DiagnosticPrinter &DP) const {
+  if (getFileName())
+    DP << getFileName() << ": ";
+  DP << getMsg();
+}
+
 bool DiagnosticInfoOptimizationBase::isLocationAvailable() const {
   return getDebugLoc();
 }
 
 void DiagnosticInfoOptimizationBase::getLocation(StringRef *Filename,
                                                  unsigned *Line,
                                                  unsigned *Column) const {
   DILocation *L = getDebugLoc();

llvm/trunk/lib/Transforms/IPO/LLVMBuild.txt

 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Library
 name = IPO
 parent = Transforms
 library_name = ipo
-required_libraries = Analysis Core InstCombine IRReader Linker Object ProfileData Scalar Support TransformUtils Vectorize
+required_libraries = Analysis Core InstCombine IRReader Linker Object ProfileData Scalar Support TransformUtils Vectorize Instrumentation

llvm/trunk/lib/Transforms/Instrumentation/CFGMST.h

+//===-- CFGMST.h - Minimum Spanning Tree for CFG -------*- C++ -*-===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements Union-find algorithm to compute Minimum Spanning Tree
+// for a given CFG.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/BranchProbability.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include <string>
+#include <vector>
+#include <utility>
+
+namespace llvm {
+
+#define DEBUG_TYPE "cfgmst"
+
+template <class Edge, class BBInfo> class CFGMST {
+public:
+  Function &F;
+
+  // Store all the edges in CFG. It may contain some stale edges
+  // when Removed is set.
+  std::vector<std::unique_ptr<Edge>> AllEdges;
+
+  // This map records the auxiliary information for each BB.
+  DenseMap<const BasicBlock *, std::unique_ptr<BBInfo>> BBInfos;
+
+  // Find the root group of the G and compress the path from G to the root.
+  BBInfo *findAndCompressGroup(BBInfo *G) {
+    if (G->Group != G)
+      G->Group = findAndCompressGroup(static_cast<BBInfo *>(G->Group));
+    return static_cast<BBInfo *>(G->Group);
+  }
+
+  // Union BB1 and BB2 into the same group and return true.
+  // Returns false if BB1 and BB2 are already in the same group.
+  bool unionGroups(const BasicBlock *BB1, const BasicBlock *BB2) {
+    BBInfo *BB1G = findAndCompressGroup(&getBBInfo(BB1));
+    BBInfo *BB2G = findAndCompressGroup(&getBBInfo(BB2));
+
+    if (BB1G == BB2G)
+      return false;
+
+    // Make the smaller rank tree a direct child or the root of high rank tree.
+    if (BB1G->Rank < BB2G->Rank)
+      BB1G->Group = BB2G;
+    else {
+      BB2G->Group = BB1G;
+      // If the ranks are the same, increment root of one tree by one.
+      if (BB1G->Rank == BB2G->Rank)
+        BB1G->Rank++;
+    }
+    return true;
+  }
+
+  // Give BB, return the auxiliary information.
+  BBInfo &getBBInfo(const BasicBlock *BB) const {
+    auto It = BBInfos.find(BB);
+    assert(It->second.get() != nullptr);
+    return *It->second.get();
+  }
+
+  // Traverse the CFG using a stack. Find all the edges and assign the weight.
+  // Edges with large weight will be put into MST first so they are less likely
+  // to be instrumented.
+  void buildEdges() {
+    DEBUG(dbgs() << "Build Edge on " << F.getName() << "\n");
+
+    const BasicBlock *BB = &(F.getEntryBlock());
+    // Add a fake edge to the entry.
+    addEdge(nullptr, BB, BFI->getEntryFreq());
+
+    // Special handling for single BB functions.
+    if (succ_empty(BB)) {
+      addEdge(BB, nullptr, BFI->getEntryFreq());
+      return;
+    }
+
+    static const uint32_t CriticalEdgeMultiplier = 1000;
+
+    for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
+      TerminatorInst *TI = BB->getTerminator();
+      uint64_t BBWeight = BFI->getBlockFreq(&*BB).getFrequency();
+      uint64_t Weight;
+      if (int successors = TI->getNumSuccessors()) {
+        for (uint32_t i = 0; i != successors; ++i) {
+          BasicBlock *TargetBB = TI->getSuccessor(i);
+          bool Critical = isCriticalEdge(TI, i);
+          uint64_t scaleFactor = BBWeight;
+          if (Critical) {
+            if (scaleFactor < UINT64_MAX / CriticalEdgeMultiplier)
+              scaleFactor *= CriticalEdgeMultiplier;
+            else
+              scaleFactor = UINT64_MAX;
+          }
+          Weight = BPI->getEdgeProbability(&*BB, TargetBB).scale(scaleFactor);
+          addEdge(&*BB, TargetBB, Weight).IsCritical = Critical;
+          DEBUG(dbgs() << "  Edge: from " << BB->getName() << " to "
+                       << TargetBB->getName() << "  w=" << Weight << "\n");
+        }
+      } else {
+        addEdge(&*BB, nullptr, BBWeight);
+        DEBUG(dbgs() << "  Edge: from " << BB->getName() << " to exit"
+                     << " w = " << BBWeight << "\n");
+      }
+    }
+  }
+
+  // Sort CFG edges based on its weight.
+  void sortEdgesByWeight() {
+    std::sort(
+        AllEdges.begin(), AllEdges.end(),
+        [](const std::unique_ptr<Edge> &lhs, const std::unique_ptr<Edge> &rhs) {
+          return lhs->Weight > rhs->Weight;
+        });
+  }
+
+  // Traverse all the edges and compute the Minimum Weight Spanning Tree
+  // using union-find algorithm.
+  void computeMinimumSpanningTree() {
+    // First, put all the critical edge with landing-pad as the Dest to MST.
+    // This works around the insufficient support of critical edges split
+    // when destination BB is a landing pad.
+    for (auto &Ei : AllEdges) {
+      if (Ei->Removed)
+        continue;
+      if (Ei->IsCritical) {
+        if (Ei->DestBB && Ei->DestBB->isLandingPad()) {
+          if (unionGroups(Ei->SrcBB, Ei->DestBB))
+            Ei->InMST = true;
+        }
+      }
+    }
+
+    for (auto &Ei : AllEdges) {
+      if (Ei->Removed)
+        continue;
+      if (unionGroups(Ei->SrcBB, Ei->DestBB))
+        Ei->InMST = true;
+    }
+  }
+
+  // Dump the Debug information about the instrumentation.
+  void dumpEdges(raw_ostream &OS, const StringRef Message = StringRef()) const {
+    if (!Message.empty())
+      OS << Message << "\n";
+    OS << "  Number of Basic Blocks: " << BBInfos.size() << "\n";
+    for (auto &BI : BBInfos) {
+      const BasicBlock *BB = BI.first;
+      OS << "  BB: " << (BB == nullptr ? "FakeNode" : BB->getName()) << "  "
+         << BI.second->infoString() << "\n";
+    }
+
+    OS << "  Number of Edges: " << AllEdges.size()
+       << " (*: Instrument, C: CriticalEdge, -: Removed)\n";
+    uint32_t Count = 0;
+    for (auto &EI : AllEdges) {
+      OS << "  Edge " << Count++ << ": " << getBBInfo(EI->SrcBB).Index << "-->"
+         << getBBInfo(EI->DestBB).Index << EI->infoString() << "\n";
+    };
+  }
+
+  // Add an edge to AllEdges with weight W.
+  Edge &addEdge(const BasicBlock *Src, const BasicBlock *Dest, uint64_t W) {
+    uint32_t Index = BBInfos.size();
+    auto Iter = BBInfos.end();
+    bool Inserted;
+    std::tie(Iter, Inserted) = BBInfos.insert(std::make_pair(Src, nullptr));
+    if (Inserted) {
+      // Newly inserted, update the real info.
+      Iter->second = std::move(llvm::make_unique<BBInfo>(Index));
+      Index++;
+    }
+    std::tie(Iter, Inserted) = BBInfos.insert(std::make_pair(Dest, nullptr));
+    if (Inserted)
+      // Newly inserted, update the real info.
+      Iter->second = std::move(llvm::make_unique<BBInfo>(Index));
+    AllEdges.emplace_back(new Edge(Src, Dest, W));
+    return *AllEdges.back();
+  }
+
+  BranchProbabilityInfo *BPI;
+  BlockFrequencyInfo *BFI;
+
+public:
+  CFGMST(Function &Func, BranchProbabilityInfo *BPI_ = nullptr,
+         BlockFrequencyInfo *BFI_ = nullptr)
+      : F(Func), BPI(BPI_), BFI(BFI_) {
+    buildEdges();
+    sortEdgesByWeight();
+    computeMinimumSpanningTree();
+  }
+};
+
+#undef DEBUG_TYPE // "cfgmst"
+} // end namespace llvm

llvm/trunk/lib/Transforms/Instrumentation/CMakeLists.txt

 add_llvm_library(LLVMInstrumentation
   AddressSanitizer.cpp
   BoundsChecking.cpp
   DataFlowSanitizer.cpp
   GCOVProfiling.cpp
   MemorySanitizer.cpp
   Instrumentation.cpp
   InstrProfiling.cpp
+  PGOInstrumentation.cpp
   SafeStack.cpp
   SanitizerCoverage.cpp
   ThreadSanitizer.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   )
 
 add_dependencies(LLVMInstrumentation intrinsics_gen)

llvm/trunk/lib/Transforms/Instrumentation/Instrumentation.cpp

 
 /// initializeInstrumentation - Initialize all passes in the TransformUtils
 /// library.
 void llvm::initializeInstrumentation(PassRegistry &Registry) {
   initializeAddressSanitizerPass(Registry);
   initializeAddressSanitizerModulePass(Registry);
   initializeBoundsCheckingPass(Registry);
   initializeGCOVProfilerPass(Registry);
+  initializePGOInstrumentationGenPass(Registry);
+  initializePGOInstrumentationUsePass(Registry);
   initializeInstrProfilingPass(Registry);
   initializeMemorySanitizerPass(Registry);
   initializeThreadSanitizerPass(Registry);
   initializeSanitizerCoverageModulePass(Registry);
   initializeDataFlowSanitizerPass(Registry);
   initializeSafeStackPass(Registry);
 }
 
 /// LLVMInitializeInstrumentation - C binding for
 /// initializeInstrumentation.
 void LLVMInitializeInstrumentation(LLVMPassRegistryRef R) {
   initializeInstrumentation(*unwrap(R));
 }

llvm/trunk/lib/Transforms/Instrumentation/LLVMBuild.txt

 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Library
 name = Instrumentation
 parent = Transforms
-required_libraries = Analysis Core MC Support TransformUtils
+required_libraries = Analysis Core MC Support TransformUtils ProfileData

llvm/trunk/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

+//===- PGOInstru.cpp - PGO Instrumentation --------===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements PGO instrumentation using a minimum spanning tree based
+// on the  following paper.
+//   [1] Donald E. Knuth, Francis R. Stevenson. Optimal measurement of points
+//   for program frequency counts. BIT Numerical Mathematics 1973, Volume 13,
+//   Issue 3, pp 313-322
+// The idea of the algorithm based on the fact that for each node (except for
+// the entry and exit), the sum of incoming edge counts equals the sum of
+// outgoing edge counts. The count of edge on spanning tree can be derived from
+// those edges not on the spanning tree. Knuth proves this method instruments
+// the minimum number of edges.
+//
+// The minimal spanning tree here is actually a maximum weight tree -- on-tree
+// edges have higher frequencies (most likely to execute). The idea is to
+// instrument those less frequently executed edges which speeds up the
+// instrumented binaries.
+//
+// This file contains two passes:
+// (1) Pass PGOInstrumentationGen which instruments the IR to generate edge
+// count profile, and
+// (2) Pass PGOInstrumentationUse which reads the edge count profile and
+// annotates the branch weight.
+// These two passes are mutually exclusive, and they are called at the same
+// compilation point (so they see the same IR). For PGOInstrumentationGen,
+// the real work is done instrumentOneFunc(). For PGOInstrumentationUse, the
+// real work in done in class PGOUseFunc and the profile is opened in module
+// level and passed to each PGOUseFunc instance.
+// The shared code for PGOInstrumentationGen and PGOInstrumentationUse is put
+// in class FuncPGOInstrumentation.
+//
+// Class PGOEdge represents a CFG edge and some auxiliary information. Class
+// BBInfo contains auxiliary information for a BB. These two classes are used
+// in PGOGenFunc. Class PGOUseEdge and UseBBInfo are the derived class of
+// PGOEdge and BBInfo, respectively. They contains extra data structure used
+// in populating profile counters.
+// The MST implementation is in Class CFGMST.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Instrumentation.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/Pass.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/BranchProbability.h"
+#include "llvm/Support/JamCRC.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/ProfileData/InstrProfReader.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include <string>
+#include <vector>
+#include <utility>
+#include "CFGMST.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "pgo-instr"
+
+STATISTIC(NumOfPGOInstrument, "Number of edges instrumented.");
+STATISTIC(NumOfPGOEdge, "Number of edges.");
+STATISTIC(NumOfPGOBB, "Number of basic-blocks.");
+STATISTIC(NumOfPGOSplit, "Number of critical edge splits.");
+STATISTIC(NumOfPGOFunc, "Number of functions having valid profile counts.");
+STATISTIC(NumOfPGOMismatch, "Number of functions having mismatch profile.");
+STATISTIC(NumOfPGOMissing, "Number of functions without profile.");
+
+static cl::opt<std::string>
+    PGOProfileFile("pgo-profile-file", cl::init(""), cl::Hidden,
+                   cl::value_desc("filename"),
+                   cl::desc("Specify the path of profile data file"));
+
+namespace {
+class PGOInstrumentationGen : public ModulePass {
+public:
+  static char ID;
+
+  PGOInstrumentationGen() : ModulePass(ID) {
+    initializePGOInstrumentationGenPass(*PassRegistry::getPassRegistry());
+  }
+
+  const char *getPassName() const override {
+    return "PGOInstrumentationGenPass";
+  }
+
+private:
+  bool runOnModule(Module &M) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<BlockFrequencyInfoWrapperPass>();
+    AU.addRequired<BranchProbabilityInfoWrapperPass>();
+  }
+};
+
+class PGOInstrumentationUse : public ModulePass {
+public:
+  static char ID;
+
+  // Provide the profile filename as the parameter.
+  PGOInstrumentationUse(StringRef Filename = StringRef(""))
+      : ModulePass(ID), ProfileFileName(Filename) {
+    if (!PGOProfileFile.empty())
+      ProfileFileName = StringRef(PGOProfileFile);
+    initializePGOInstrumentationUsePass(*PassRegistry::getPassRegistry());
+  }
+
+  const char *getPassName() const override {
+    return "PGOInstrumentationUsePass";
+  }
+
+private:
+  StringRef ProfileFileName;
+  std::unique_ptr<IndexedInstrProfReader> PGOReader;
+  bool runOnModule(Module &M) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<BlockFrequencyInfoWrapperPass>();
+    AU.addRequired<BranchProbabilityInfoWrapperPass>();
+  }
+};
+} // end anonymous namespace
+
+char PGOInstrumentationGen::ID = 0;
+INITIALIZE_PASS_BEGIN(PGOInstrumentationGen, "pgo-instr-gen",
+                      "PGO instrumentation.", false, false)
+INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
+INITIALIZE_PASS_END(PGOInstrumentationGen, "pgo-instr-gen",
+                    "PGO instrumentation.", false, false)
+
+ModulePass *llvm::createPGOInstrumentationGenPass() {
+  return new PGOInstrumentationGen();
+}
+
+char PGOInstrumentationUse::ID = 0;
+INITIALIZE_PASS_BEGIN(PGOInstrumentationUse, "pgo-instr-use",
+                      "Read PGO instrumentation profile.", false, false)
+INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
+INITIALIZE_PASS_END(PGOInstrumentationUse, "pgo-instr-use",
+                    "Read PGO instrumentation profile.", false, false)
+
+ModulePass *llvm::createPGOInstrumentationUsePass(StringRef Filename) {
+  return new PGOInstrumentationUse(Filename);
+}
+
+namespace {
+/// \brief An MST based instrumentation for PGO
+///
+/// Implements a Minimum Spanning Tree (MST) based instrumentation for PGO
+/// in the function level.
+//
+// This class implements the CFG edges. Note the CFG can be a multi-graph.
+struct PGOEdge {
+  const BasicBlock *SrcBB;
+  const BasicBlock *DestBB;
+  uint64_t Weight;
+  bool InMST;
+  bool Removed;
+  bool IsCritical;
+  PGOEdge(const BasicBlock *Src, const BasicBlock *Dest, unsigned W = 1)
+      : SrcBB(Src), DestBB(Dest), Weight(W), InMST(false), Removed(false),
+        IsCritical(false) {}
+  // Return the information string of an edge.
+  const std::string infoString() const {
+    std::string Str = (Removed ? "-" : " ");
+    Str += (InMST ? " " : "*");
+    Str += (IsCritical ? "c" : " ");
+    Str += "  W=" + std::to_string(Weight);
+    return Str;
+  }
+};
+
+// This class stores the auxiliary information for each BB.
+struct BBInfo {
+  BBInfo *Group;
+  uint32_t Index;
+  uint32_t Rank;
+
+  BBInfo(unsigned IX) : Group(this), Index(IX), Rank(0) {}
+
+  // Return the information string of this object.
+  const std::string infoString() const {
+    return "Index=" + std::to_string(Index);
+  }
+};
+
+// This class implements the CFG edges. Note the CFG can be a multi-graph.
+template <class Edge, class BBInfo> class FuncPGOInstrumentation {
+private:
+  Function &F;
+  void computeCFGHash();
+
+public:
+  std::string FuncName;
+  GlobalVariable *FuncNameVar;
+  // CFG hash value for this function.
+  uint64_t FunctionHash;
+
+  // The Minimum Spanning Tree of function CFG.
+  CFGMST<Edge, BBInfo> MST;
+
+  // Give an edge, find the BB that will be instrumented.
+  // Return nullptr if there is no BB to be instrumented.
+  BasicBlock *getInstrBB(Edge *E);
+
+  // Return the auxiliary BB information.
+  BBInfo &getBBInfo(const BasicBlock *BB) const { return MST.getBBInfo(BB); }
+
+  // Dump edges and BB information.
+  void dumpInfo(std::string Str = "") const {
+    std::string Message = "Dump Function " + FuncName + " Hash: " +
+                          std::to_string(FunctionHash) + "\t" + Str;
+    MST.dumpEdges(dbgs(), Message);
+  }
+
+  FuncPGOInstrumentation(Function &Func, bool CreateGlobalVar = false,
+                         BranchProbabilityInfo *BPI_ = nullptr,
+                         BlockFrequencyInfo *BFI_ = nullptr)
+      : F(Func), FunctionHash(0), MST(F, BPI_, BFI_) {
+    FuncName = getPGOFuncName(F);
+    computeCFGHash();
+    DEBUG(dumpInfo("after CFGMST"));
+
+    NumOfPGOBB += MST.BBInfos.size();
+    for (auto &Ei : MST.AllEdges) {
+      if (Ei->Removed)
+        continue;
+      NumOfPGOEdge++;
+      if (!Ei->InMST)
+        NumOfPGOInstrument++;
+    }
+
+    if (CreateGlobalVar)
+      FuncNameVar = createPGOFuncNameVar(F, FuncName);
+  };
+};
+
+// Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index
+// value of each BB in the CFG. The higher 32 bits record the number of edges.
+template <class Edge, class BBInfo>
+void FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash() {
+  std::vector<char> Indexes;
+  JamCRC JC;
+  for (auto &BB : F) {
+    const TerminatorInst *TI = BB.getTerminator();
+    for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) {
+      BasicBlock *Succ = TI->getSuccessor(s);
+      uint32_t Index = getBBInfo(Succ).Index;
+      for (int i = 0; i < sizeof(uint32_t) / sizeof(char); i++)
+        Indexes.push_back((char)(Index >> (i * sizeof(char))));
+    }
+  }
+  JC.update(Indexes);
+  FunctionHash = MST.AllEdges.size() << 32 | JC.getCRC();
+}
+
+template <class Edge, class BBInfo>
+BasicBlock *FuncPGOInstrumentation<Edge, BBInfo>::getInstrBB(Edge *E) {
+  if (E->InMST || E->Removed)
+    return nullptr;
+
+  BasicBlock *SrcBB = const_cast<BasicBlock *>(E->SrcBB);
+  BasicBlock *DestBB = const_cast<BasicBlock *>(E->DestBB);
+  // For a fake edge, instrument the real BB.
+  if (SrcBB == nullptr)
+    return DestBB;
+  if (DestBB == nullptr)
+    return SrcBB;
+
+  // Instrument the SrcBB if it has a single successor,
+  // otherwise, the DestBB if this is not a critical edge.
+  TerminatorInst *TI = SrcBB->getTerminator();
+  if (TI->getNumSuccessors() <= 1)
+    return SrcBB;
+  if (!E->IsCritical)
+    return DestBB;
+
+  // For a critical edge, we have to split. Instrument the newly
+  // created BB.
+  NumOfPGOSplit++;
+  DEBUG(dbgs() << "Split critical edge: " << getBBInfo(SrcBB).Index << " --> "
+               << getBBInfo(DestBB).Index << "\n");
+  unsigned SuccNum = GetSuccessorNumber(SrcBB, DestBB);
+  BasicBlock *InstrBB = SplitCriticalEdge(TI, SuccNum);
+  assert(InstrBB && "Critical edge is not split");
+
+  E->Removed = true;
+  return InstrBB;
+}
+
+// Visit all edge and instrument the edges not in MST.
+// Critical edges will be split.
+static void instrumentOneFunc(Function &F, Module *M,
+                              BranchProbabilityInfo *BPI,
+                              BlockFrequencyInfo *BFI) {
+  unsigned NumCounters = 0;
+  FuncPGOInstrumentation<PGOEdge, BBInfo> FuncInfo(F, true, BPI, BFI);
+  for (auto &Ei : FuncInfo.MST.AllEdges) {
+    if (!Ei->InMST && !Ei->Removed)
+      NumCounters++;
+  }
+
+  uint32_t j = 0;
+  for (auto &Ei : FuncInfo.MST.AllEdges) {
+    BasicBlock *InstrBB = FuncInfo.getInstrBB(Ei.get());
+    if (!InstrBB)
+      continue;
+
+    IRBuilder<> Builder(InstrBB, InstrBB->getFirstInsertionPt());
+    assert(Builder.GetInsertPoint() != InstrBB->end() &&
+           "Cannot get the Instrumentation point");
+    auto *I8PtrTy = Type::getInt8PtrTy(M->getContext());
+    Builder.CreateCall(
+        Intrinsic::getDeclaration(M, Intrinsic::instrprof_increment),
+        {llvm::ConstantExpr::getBitCast(FuncInfo.FuncNameVar, I8PtrTy),
+         Builder.getInt64(FuncInfo.FunctionHash), Builder.getInt32(NumCounters),
+         Builder.getInt32(j++)});
+  }
+}
+
+struct PGOUseEdge : public PGOEdge {
+  bool CountValid;
+  uint64_t CountValue;
+  PGOUseEdge(const BasicBlock *Src, const BasicBlock *Dest, unsigned W = 1)
+      : PGOEdge(Src, Dest, W), CountValid(false), CountValue(0) {}
+
+  // Set edge count value
+  void setEdgeCount(uint64_t Value) {
+    CountValue = Value;
+    CountValid = true;
+  }
+
+  // Return the information string for this object.
+  const std::string infoString() const {
+    if (!CountValid)
+      return PGOEdge::infoString();
+    return PGOEdge::infoString() + "  Count=" + std::to_string(CountValue);
+  }
+};
+
+typedef SmallVector<PGOUseEdge *, 2> DirectEdges;
+
+// This class stores the auxiliary information for each BB.
+struct UseBBInfo : public BBInfo {
+  uint64_t CountValue;
+  bool CountValid;
+  int32_t UnknownCountInEdge;
+  int32_t UnknownCountOutEdge;
+  DirectEdges InEdges;
+  DirectEdges OutEdges;
+  UseBBInfo(unsigned IX)
+      : BBInfo(IX), CountValue(0), CountValid(false), UnknownCountInEdge(0),
+        UnknownCountOutEdge(0) {}
+  UseBBInfo(unsigned IX, uint64_t C)
+      : BBInfo(IX), CountValue(C), CountValid(true), UnknownCountInEdge(0),
+        UnknownCountOutEdge(0) {}
+
+  // Set the profile count value for this BB.
+  void setBBInfoCount(uint64_t Value) {
+    CountValue = Value;
+    CountValid = true;
+  }
+
+  // Return the information string of this object.
+  const std::string infoString() const {
+    if (!CountValid)
+      return BBInfo::infoString();
+    return BBInfo::infoString() + "  Count=" + std::to_string(CountValue);
+  }
+};
+
+// Sum up the count values for all the edges.
+static uint64_t sumEdgeCount(const ArrayRef<PGOUseEdge *> Edges) {
+  uint64_t Total = 0;
+  for (auto &Ei : Edges) {
+    if (Ei->Removed)
+      continue;
+    Total += Ei->CountValue;
+  }
+  return Total;
+}
+
+class PGOUseFunc {
+private:
+  Function &F;
+  Module *M;
+  // This member stores the shared information with class PGOGenFunc.
+  FuncPGOInstrumentation<PGOUseEdge, UseBBInfo> FuncInfo;
+
+  // Return the auxiliary BB information.
+  UseBBInfo &getBBInfo(const BasicBlock *BB) const {
+    return FuncInfo.getBBInfo(BB);
+  }
+
+  // The maximum count value in the profile. This is only used in PGO use
+  // compilation.
+  uint64_t ProgramMaxCount;
+
+  // Find the Instrumented BB and set the value.
+  void setInstrumentedCounts(const std::vector<uint64_t> &CountFromProfile);
+
+  // Set the edge counter value for the unknown edge -- there should be only
+  // one unknown edge.
+  void setEdgeCount(DirectEdges &Edges, uint64_t Value);
+
+  // Return FuncName string;
+  const std::string getFuncName() const { return FuncInfo.FuncName; }
+
+  // Set the hot/cold inline hints based on the count values.
+  void applyFunctionAttributes(uint64_t EntryCount, uint64_t MaxCount) {
+    if (ProgramMaxCount == 0)
+      return;
+    // Threshold of the hot functions.
+    const BranchProbability HotFunctionThreshold(1, 100);
+    // Threshold of the cold functions.
+    const BranchProbability ColdFunctionThreshold(2, 10000);
+    if (EntryCount >= HotFunctionThreshold.scale(ProgramMaxCount))
+      F.addFnAttr(llvm::Attribute::InlineHint);
+    else if (MaxCount <= ColdFunctionThreshold.scale(ProgramMaxCount))
+      F.addFnAttr(llvm::Attribute::Cold);
+  }
+
+public:
+  PGOUseFunc(Function &Func, Module *Modu,
+             BranchProbabilityInfo *BPI_ = nullptr,
+             BlockFrequencyInfo *BFI_ = nullptr)
+      : F(Func), M(Modu), FuncInfo(Func, false, BPI_, BFI_) {}
+
+  // Read counts for the instrumented BB from profile.
+  bool readCounters(IndexedInstrProfReader *PGOReader);
+
+  // Populate the counts for all BBs.
+  void populateCounters();
+
+  // Set the branch weights based on the count values.
+  void setBranchWeights();
+};
+
+// Visit all the edges and assign the count value for the instrumented
+// edges and the BB.
+void PGOUseFunc::setInstrumentedCounts(
+    const std::vector<uint64_t> &CountFromProfile) {
+
+  // Use a worklist as we will update the vector during the iteration.
+  std::vector<PGOUseEdge *> WorkList;
+  for (auto &Ei : FuncInfo.MST.AllEdges)
+    WorkList.push_back(Ei.get());
+
+  uint32_t j = 0;
+  for (auto &Ei : WorkList) {
+    BasicBlock *InstrBB = FuncInfo.getInstrBB(Ei);
+    if (!InstrBB)
+      continue;
+    uint64_t CountValue = CountFromProfile[j++];
+    if (!Ei->Removed) {
+      getBBInfo(InstrBB).setBBInfoCount(CountValue);
+      Ei->setEdgeCount(CountValue);
+      continue;
+    }
+
+    // Need to add two new edges.
+    BasicBlock *SrcBB = const_cast<BasicBlock *>(Ei->SrcBB);
+    BasicBlock *DestBB = const_cast<BasicBlock *>(Ei->DestBB);
+    // Add new edge of SrcBB->InstrBB.
+    PGOUseEdge &NewEdge = FuncInfo.MST.addEdge(SrcBB, InstrBB, 0);
+    NewEdge.setEdgeCount(CountValue);
+    // Add new edge of InstrBB->DestBB.
+    PGOUseEdge &NewEdge1 = FuncInfo.MST.addEdge(InstrBB, DestBB, 0);
+    NewEdge1.setEdgeCount(CountValue);
+    NewEdge1.InMST = true;
+    getBBInfo(InstrBB).setBBInfoCount(CountValue);
+  }
+}
+
+// Set the count value for the unknown edges. There should be one and only one
+// unknown edge in Edges vector.
+void PGOUseFunc::setEdgeCount(DirectEdges &Edges, uint64_t Value) {
+  for (auto &Ei : Edges) {
+    if (Ei->CountValid)
+      continue;
+    Ei->setEdgeCount(Value);
+
+    getBBInfo(Ei->SrcBB).UnknownCountOutEdge--;
+    getBBInfo(Ei->DestBB).UnknownCountInEdge--;
+    return;
+  }
+  llvm_unreachable("Cannot find the unknown count edge");
+}
+
+// Read the profile from ProfileFileName and assign the value to the
+// instrumented BB and the edges. This function also updates ProgramMaxCount.
+// Return true if the profile are successfully read, and false on errors.
+bool PGOUseFunc::readCounters(IndexedInstrProfReader *PGOReader) {
+  auto &Ctx = M->getContext();
+  ErrorOr<InstrProfRecord> Result =
+      PGOReader->getInstrProfRecord(FuncInfo.FuncName, FuncInfo.FunctionHash);
+  if (std::error_code EC = Result.getError()) {
+    if (EC == instrprof_error::unknown_function)
+      NumOfPGOMissing++;
+    else if (EC == instrprof_error::hash_mismatch ||
+             EC == llvm::instrprof_error::malformed)
+      NumOfPGOMismatch++;
+
+    std::string Msg = EC.message() + std::string(" ") + F.getName().str();
+    Ctx.diagnose(
+        DiagnosticInfoPGOProfile(M->getName().data(), Msg, DS_Warning));
+    return false;
+  }
+  std::vector<uint64_t> &CountFromProfile = Result.get().Counts;
+
+  NumOfPGOFunc++;
+  DEBUG(dbgs() << CountFromProfile.size() << " counts\n");
+  uint64_t ValueSum = 0;
+  for (unsigned i = 0, e = CountFromProfile.size(); i < e; i++) {
+    DEBUG(dbgs() << "  " << i << ": " << CountFromProfile[i] << "\n");
+    ValueSum += CountFromProfile[i];
+  }
+
+  DEBUG(dbgs() << "SUM =  " << ValueSum << "\n");
+
+  getBBInfo(nullptr).UnknownCountOutEdge = 2;
+  getBBInfo(nullptr).UnknownCountInEdge = 2;
+
+  setInstrumentedCounts(CountFromProfile);
+  ProgramMaxCount = PGOReader->getMaximumFunctionCount();
+  return true;
+}
+
+// Populate the counters from instrumented BBs to all BBs.
+// In the end of this operation, all BBs should have a valid count value.
+void PGOUseFunc::populateCounters() {
+  // First set up Count variable for all BBs.
+  for (auto &Ei : FuncInfo.MST.AllEdges) {
+    if (Ei->Removed)
+      continue;
+
+    const BasicBlock *SrcBB = Ei->SrcBB;
+    const BasicBlock *DestBB = Ei->DestBB;
+    UseBBInfo &SrcInfo = getBBInfo(SrcBB);
+    UseBBInfo &DestInfo = getBBInfo(DestBB);
+    SrcInfo.OutEdges.push_back(Ei.get());
+    DestInfo.InEdges.push_back(Ei.get());
+    SrcInfo.UnknownCountOutEdge++;
+    DestInfo.UnknownCountInEdge++;
+
+    if (!Ei->CountValid)
+      continue;
+    DestInfo.UnknownCountInEdge--;
+    SrcInfo.UnknownCountOutEdge--;
+  }
+
+  bool Changes = true;
+  unsigned NumPasses = 0;
+  while (Changes) {
+    NumPasses++;
+    Changes = false;
+
+    // For efficient traversal, it's better to start from the end as most
+    // of the instrumented edges are at the end.
+    for (auto &BB : reverse(F)) {
+      UseBBInfo &Count = getBBInfo(&BB);
+      if (!Count.CountValid) {
+        if (Count.UnknownCountOutEdge == 0) {
+          Count.CountValue = sumEdgeCount(Count.OutEdges);
+          Count.CountValid = true;
+          Changes = true;
+        } else if (Count.UnknownCountInEdge == 0) {
+          Count.CountValue = sumEdgeCount(Count.InEdges);
+          Count.CountValid = true;
+          Changes = true;
+        }
+      }
+      if (Count.CountValid) {
+        if (Count.UnknownCountOutEdge == 1) {
+          uint64_t Total = Count.CountValue - sumEdgeCount(Count.OutEdges);
+          setEdgeCount(Count.OutEdges, Total);
+          Changes = true;
+        }
+        if (Count.UnknownCountInEdge == 1) {
+          uint64_t Total = Count.CountValue - sumEdgeCount(Count.InEdges);
+          setEdgeCount(Count.InEdges, Total);
+          Changes = true;
+        }
+      }
+    }
+  }
+
+  DEBUG(dbgs() << "Populate counts in " << NumPasses << " passes.\n");
+  // Assert every BB has a valid counter.
+  uint64_t FuncEntryCount = getBBInfo(&*F.begin()).CountValue;
+  uint64_t FuncMaxCount = FuncEntryCount;
+  for (auto &BB : F) {
+    assert(getBBInfo(&BB).CountValid && "BB count is not valid");
+    uint64_t Count = getBBInfo(&BB).CountValue;
+    if (Count > FuncMaxCount)
+      FuncMaxCount = Count;
+  }
+  applyFunctionAttributes(FuncEntryCount, FuncMaxCount);
+
+  DEBUG(FuncInfo.dumpInfo("after reading profile."));
+}
+
+// Assign the scaled count values to the BB with multiple out edges.
+void PGOUseFunc::setBranchWeights() {
+  // Generate MD_prof metadata for every branch instruction.
+  DEBUG(dbgs() << "\nSetting branch weights.\n");
+  MDBuilder MDB(M->getContext());
+  for (auto &BB : F) {
+    TerminatorInst *TI = BB.getTerminator();
+    if (TI->getNumSuccessors() < 2)
+      continue;
+    if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
+      continue;
+    if (getBBInfo(&BB).CountValue == 0)
+      continue;
+
+    // We have a non-zero Branch BB.
+    const UseBBInfo &BBCountInfo = getBBInfo(&BB);
+    unsigned Size = BBCountInfo.OutEdges.size();
+    SmallVector<unsigned, 2> EdgeCounts(Size, 0);
+    uint64_t MaxCount = 0;
+    for (unsigned s = 0; s < Size; s++) {
+      const PGOUseEdge *E = BBCountInfo.OutEdges[s];
+      const BasicBlock *SrcBB = E->SrcBB;
+      const BasicBlock *DestBB = E->DestBB;
+      if (DestBB == 0)
+        continue;
+      unsigned SuccNum = GetSuccessorNumber(SrcBB, DestBB);
+      uint64_t EdgeCount = E->CountValue;
+      if (EdgeCount > MaxCount)
+        MaxCount = EdgeCount;
+      EdgeCounts[SuccNum] = EdgeCount;
+    }
+    assert(MaxCount > 0 && "Bad max count");
+    uint64_t Scale = calculateCountScale(MaxCount);
+    SmallVector<unsigned, 4> Weights;
+    for (const auto &ECI : EdgeCounts)
+      Weights.push_back(scaleBranchCount(ECI, Scale));
+
+    TI->setMetadata(llvm::LLVMContext::MD_prof,
+                    MDB.createBranchWeights(Weights));
+    DEBUG(dbgs() << "Weight is: "; for (const auto &W
+                                        : Weights) dbgs()
+                                   << W << " ";
+          dbgs() << "\n";);
+  }
+}
+} // end anonymous namespace
+
+bool PGOInstrumentationGen::runOnModule(Module &M) {
+  for (auto &F : M) {
+    if (F.isDeclaration())
+      continue;
+    BranchProbabilityInfo *BPI =
+        &(getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI());
+    BlockFrequencyInfo *BFI =
+        &(getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI());
+    instrumentOneFunc(F, &M, BPI, BFI);
+  }
+  return true;
+}
+
+static void setPGOCountOnFunc(PGOUseFunc &Func,
+                              IndexedInstrProfReader *PGOReader) {
+  if (Func.readCounters(PGOReader)) {
+    Func.populateCounters();
+    Func.setBranchWeights();
+  }
+}
+
+bool PGOInstrumentationUse::runOnModule(Module &M) {
+  DEBUG(dbgs() << "Read in profile counters: ");
+  auto &Ctx = M.getContext();
+  // Read the counter array from file.
+  auto ReaderOrErr = IndexedInstrProfReader::create(ProfileFileName);
+  if (std::error_code EC = ReaderOrErr.getError()) {
+    Ctx.diagnose(
+        DiagnosticInfoPGOProfile(ProfileFileName.data(), EC.message()));
+    return false;
+  }
+
+  PGOReader = std::move(ReaderOrErr.get());
+  if (!PGOReader) {
+    Ctx.diagnose(DiagnosticInfoPGOProfile(ProfileFileName.data(),
+                                          "Cannot get PGOReader"));
+    return false;
+  }
+
+  for (auto &F : M) {
+    if (F.isDeclaration())
+      continue;
+    BranchProbabilityInfo *BPI =
+        &(getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI());
+    BlockFrequencyInfo *BFI =
+        &(getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI());
+    PGOUseFunc Func(F, &M, BPI, BFI);
+    setPGOCountOnFunc(Func, PGOReader.get());
+  }
+  return true;
+}

llvm/trunk/test/Transforms/PGOProfile/Inputs/branch1.proftext

+_Z9test_br_1i
[phone]
+2
+3
+2
+

llvm/trunk/test/Transforms/PGOProfile/Inputs/branch2.proftext

+_Z9test_br_2i
[phone]
+2
+1
+1
+

llvm/trunk/test/Transforms/PGOProfile/Inputs/criticaledge.proftext

+_Z17test_criticalEdgeii
[phone]
+8
+2
+1
+2
+2
+0
+1
+2
+1
+
+<stdin>:_ZL3bari
[phone]
+1
+7
+

llvm/trunk/test/Transforms/PGOProfile/Inputs/landingpad.proftext

+_Z3fooi
[phone]
+4
+3
+1
+2
+0
+
+_Z3bari
[phone]
+2
+1
+2
+

llvm/trunk/test/Transforms/PGOProfile/Inputs/loop1.proftext

+_Z15test_simple_fori
[phone]
+2
+96
+4
+

llvm/trunk/test/Transforms/PGOProfile/Inputs/loop2.proftext

+_Z13test_do_whilei
[phone]
+2
+96
+4
+

llvm/trunk/test/Transforms/PGOProfile/Inputs/loop3.proftext

+_Z15test_nested_foriii
[phone]
+4
+186
+33
+10
+6
+

llvm/trunk/test/Transforms/PGOProfile/Inputs/single_bb.proftext

+_Z9single_bbv
[phone]
+1
+1
+

llvm/trunk/test/Transforms/PGOProfile/Inputs/switch.proftext

+_Z13test_switch_1i
[phone]
+4
+0
+0
+0
+3
+

llvm/trunk/test/Transforms/PGOProfile/branch1_gen.ll

+; RUN: opt < %s -pgo-instr-gen -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: @__llvm_profile_name__Z9test_br_1i = private constant [13 x i8] c"_Z9test_br_1i"
+
+define i32 @_Z9test_br_1i(i32 %i) {
+entry:
+  %cmp = icmp sgt i32 %i, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @__llvm_profile_name__Z9test_br_1i, i32 0, i32 0), i64 23925403969, i32 2, i32 1)
+  %add = add nsw i32 %i, 2
+  br label %if.end
+
+if.end:
+  %retv = phi i32 [ %add, %if.then ], [ %i, %entry ]
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @__llvm_profile_name__Z9test_br_1i, i32 0, i32 0), i64 23925403969, i32 2, i32 0)
+  ret i32 %retv
+}

llvm/trunk/test/Transforms/PGOProfile/branch1_use.ll

+; RUN: llvm-profdata merge %S/Inputs/branch1.proftext -o %T/branch1.profdata
+; RUN: opt < %s -pgo-instr-use -pgo-profile-file=%T/branch1.profdata -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z9test_br_1i(i32 %i) {
+entry:
+  %cmp = icmp sgt i32 %i, 0
+  br i1 %cmp, label %if.then, label %if.end
+; CHECK: !prof !0
+
+if.then:
+  %add = add nsw i32 %i, 2
+  br label %if.end
+
+if.end:
+  %retv = phi i32 [ %add, %if.then ], [ %i, %entry ]
+  ret i32 %retv
+}
+
+; CHECK: !0 = !{!"branch_weights", i32 2, i32 1}

llvm/trunk/test/Transforms/PGOProfile/branch2_gen.ll

+; RUN: opt < %s -pgo-instr-gen -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: @__llvm_profile_name__Z9test_br_2i = private constant [13 x i8] c"_Z9test_br_2i"
+
+define i32 @_Z9test_br_2i(i32 %i) {
+entry:
+  %cmp = icmp sgt i32 %i, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @__llvm_profile_name__Z9test_br_2i, i32 0, i32 0), i64 29368252703, i32 2, i32 0)
+  %add = add nsw i32 %i, 2
+  br label %if.end
+
+if.else:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @__llvm_profile_name__Z9test_br_2i, i32 0, i32 0), i64 29368252703, i32 2, i32 1)
+  %sub = sub nsw i32 %i, 2
+  br label %if.end
+
+if.end:
+  %retv = phi i32 [ %add, %if.then ], [ %sub, %if.else ]
+  ret i32 %retv
+}

llvm/trunk/test/Transforms/PGOProfile/branch2_use.ll

+; RUN: llvm-profdata merge %S/Inputs/branch2.proftext -o %T/branch2.profdata
+; RUN: opt < %s -pgo-instr-use -pgo-profile-file=%T/branch2.profdata -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z9test_br_2i(i32 %i) {
+entry:
+  %cmp = icmp sgt i32 %i, 0
+  br i1 %cmp, label %if.then, label %if.else
+; CHECK: !prof !0
+
+if.then:
+  %add = add nsw i32 %i, 2
+  br label %if.end
+
+if.else:
+  %sub = sub nsw i32 %i, 2
+  br label %if.end
+
+if.end:
+  %retv = phi i32 [ %add, %if.then ], [ %sub, %if.else ]
+  ret i32 %retv
+}
+
+; CHECK: !0 = !{!"branch_weights", i32 1, i32 1}

llvm/trunk/test/Transforms/PGOProfile/checksum_mismatch.ll

+; RUN: llvm-profdata merge %S/Inputs/single_bb.proftext -o %T/single_bb.profdata
+; RUN: opt < %s -pgo-instr-use -pgo-profile-file=%T/single_bb.profdata -S 2>&1 | FileCheck %s
+
+; CHECK: Function control flow change detected (hash mismatch) _Z9single_bbv
+; CHECK: No profile data available for function _ZL8uncalledii
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z9single_bbv() {
+entry:
+  ret i32 0
+}
+
+define i32 @_ZL8uncalledii(i32 %i, i32 %j) {
+  %mul = mul nsw i32 %i, %j
+  ret i32 %mul
+}

llvm/trunk/test/Transforms/PGOProfile/criticaledge_gen.ll

+; RUN: opt < %s -pgo-instr-gen -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: @__llvm_profile_name__Z17test_criticalEdgeii = private constant [23 x i8] c"_Z17test_criticalEdgeii"
+; CHECK: @"__llvm_profile_name_<stdin>:_ZL3bari" = private constant [16 x i8] c"<stdin>:_ZL3bari"
+
+define i32 @_Z17test_criticalEdgeii(i32 %i, i32 %j) {
+entry:
+  switch i32 %i, label %sw.default [
+    i32 1, label %sw.bb
+    i32 2, label %sw.bb1
+    i32 3, label %sw.bb3
+    i32 4, label %sw.bb3
+; CHECK:    i32 3, label %entry.sw.bb3_crit_edge
+; CHECK:    i32 4, label %entry.sw.bb3_crit_edge1
+    i32 5, label %sw.bb3
+  ]
+
+; CHECK: entry.sw.bb3_crit_edge1:
+; CHECK:   call void @llvm.instrprof.increment(i8* getelementptr inbounds ([23 x i8], [23 x i8]* @__llvm_profile_name__Z17test_criticalEdgeii, i32 0, i32 0), i64 82348442248, i32 8, i32 1)
+; CHECK:   br label %sw.bb3
+
+; CHECK: entry.sw.bb3_crit_edge:
+; CHECK:   call void @llvm.instrprof.increment(i8* getelementptr inbounds ([23 x i8], [23 x i8]* @__llvm_profile_name__Z17test_criticalEdgeii, i32 0, i32 0), i64 82348442248, i32 8, i32 0)
+; CHECK:   br label %sw.bb3
+
+sw.bb:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([23 x i8], [23 x i8]* @__llvm_profile_name__Z17test_criticalEdgeii, i32 0, i32 0), i64 82348442248, i32 8, i32 5)
+  %call = call i32 @_ZL3bari(i32 2)
+  br label %sw.epilog
+
+sw.bb1:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([23 x i8], [23 x i8]* @__llvm_profile_name__Z17test_criticalEdgeii, i32 0, i32 0), i64 82348442248, i32 8, i32 4)
+  %call2 = call i32 @_ZL3bari(i32 1024)
+  br label %sw.epilog
+
+sw.bb3:
+  %cmp = icmp eq i32 %j, 2
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([23 x i8], [23 x i8]* @__llvm_profile_name__Z17test_criticalEdgeii, i32 0, i32 0), i64 82348442248, i32 8, i32 2)
+  %call4 = call i32 @_ZL3bari(i32 4)
+  br label %return
+
+if.end:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([23 x i8], [23 x i8]* @__llvm_profile_name__Z17test_criticalEdgeii, i32 0, i32 0), i64 82348442248, i32 8, i32 3)
+  %call5 = call i32 @_ZL3bari(i32 8)
+  br label %sw.epilog
+
+sw.default:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([23 x i8], [23 x i8]* @__llvm_profile_name__Z17test_criticalEdgeii, i32 0, i32 0), i64 82348442248, i32 8, i32 6)
+  %call6 = call i32 @_ZL3bari(i32 32)
+  %cmp7 = icmp sgt i32 %j, 10
+  br i1 %cmp7, label %if.then8, label %if.end9
+
+if.then8:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([23 x i8], [23 x i8]* @__llvm_profile_name__Z17test_criticalEdgeii, i32 0, i32 0), i64 82348442248, i32 8, i32 7)
+  %add = add nsw i32 %call6, 10
+  br label %if.end9
+
+if.end9:
+  %res.0 = phi i32 [ %add, %if.then8 ], [ %call6, %sw.default ]
+  br label %sw.epilog
+
+sw.epilog:
+  %res.1 = phi i32 [ %res.0, %if.end9 ], [ %call5, %if.end ], [ %call2, %sw.bb1 ], [ %call, %sw.bb ]
+  br label %return
+
+return:
+  %retval = phi i32 [ %res.1, %sw.epilog ], [ %call4, %if.then ]
+  ret i32 %retval
+}
+
+define internal i32 @_ZL3bari(i32 %i) {
+entry:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([16 x i8], [16 x i8]* @"__llvm_profile_name_<stdin>:_ZL3bari", i32 0, i32 0), i64 12884901887, i32 1, i32 0)
+  ret i32 %i
+}

llvm/trunk/test/Transforms/PGOProfile/criticaledge_use.ll

+; RUN: llvm-profdata merge %S/Inputs/criticaledge.proftext -o %T/criticaledge.profdata
+; RUN: opt < %s -pgo-instr-use -pgo-profile-file=%T/criticaledge.profdata -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z17test_criticalEdgeii(i32 %i, i32 %j) {
+entry:
+  switch i32 %i, label %sw.default [
+    i32 1, label %sw.bb
+    i32 2, label %sw.bb1
+    i32 3, label %sw.bb3
+    i32 4, label %sw.bb3
+; CHECK:    i32 3, label %entry.sw.bb3_crit_edge
+; CHECK:    i32 4, label %entry.sw.bb3_crit_edge1
+    i32 5, label %sw.bb3
+  ]
+; CHECK: !prof !0
+
+; CHECK: entry.sw.bb3_crit_edge1:
+; CHECK:   br label %sw.bb3
+; CHECK: entry.sw.bb3_crit_edge:
+; CHECK:   br label %sw.bb3
+
+sw.bb:
+  %call = call i32 @_ZL3bari(i32 2)
+  br label %sw.epilog
+
+sw.bb1:
+  %call2 = call i32 @_ZL3bari(i32 1024)
+  br label %sw.epilog
+
+sw.bb3:
+  %cmp = icmp eq i32 %j, 2
+  br i1 %cmp, label %if.then, label %if.end
+; CHECK: !prof !1
+
+if.then:
+  %call4 = call i32 @_ZL3bari(i32 4)
+  br label %return
+
+if.end:
+  %call5 = call i32 @_ZL3bari(i32 8)
+  br label %sw.epilog
+
+sw.default:
+  %call6 = call i32 @_ZL3bari(i32 32)
+  %cmp7 = icmp sgt i32 %j, 10
+  br i1 %cmp7, label %if.then8, label %if.end9
+; CHECK: !prof !2
+
+if.then8:
+  %add = add nsw i32 %call6, 10
+  br label %if.end9
+
+if.end9:
+  %res.0 = phi i32 [ %add, %if.then8 ], [ %call6, %sw.default ]
+  br label %sw.epilog
+
+sw.epilog:
+  %res.1 = phi i32 [ %res.0, %if.end9 ], [ %call5, %if.end ], [ %call2, %sw.bb1 ], [ %call, %sw.bb ]
+  br label %return
+
+return:
+  %retval = phi i32 [ %res.1, %sw.epilog ], [ %call4, %if.then ]
+  ret i32 %retval
+}
+
+define internal i32 @_ZL3bari(i32 %i) {
+entry:
+  ret i32 %i
+}
+
+; CHECK: !0 = !{!"branch_weights", i32 2, i32 1, i32 0, i32 2, i32 1, i32 1}
+; CHECK: !1 = !{!"branch_weights", i32 2, i32 2}
+; CHECK: !2 = !{!"branch_weights", i32 1, i32 1}

llvm/trunk/test/Transforms/PGOProfile/landingpad_gen.ll

+; RUN: opt < %s -pgo-instr-gen -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@val = global i32 0, align 4
+@_ZTIi = external constant i8*
+; CHECK: @__llvm_profile_name__Z3bari = private constant [7 x i8] c"_Z3bari"
+; CHECK: @__llvm_profile_name__Z3fooi = private constant [7 x i8] c"_Z3fooi"
+
+define i32 @_Z3bari(i32 %i) {
+entry:
+  %rem = srem i32 %i, 3
+  %tobool = icmp ne i32 %rem, 0
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @__llvm_profile_name__Z3bari, i32 0, i32 0), i64 23319865734, i32 2, i32 1)
+  %exception = call i8* @__cxa_allocate_exception(i64 4)
+  %tmp = bitcast i8* %exception to i32*
+  store i32 %i, i32* %tmp, align 16
+  call void @__cxa_throw(i8* %exception, i8* bitcast (i8** @_ZTIi to i8*), i8* null)
+  unreachable
+
+if.end:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @__llvm_profile_name__Z3bari, i32 0, i32 0), i64 23319865734, i32 2, i32 0)
+  ret i32 0
+}
+
+declare i8* @__cxa_allocate_exception(i64)
+
+declare void @__cxa_throw(i8*, i8*, i8*)
+
+define i32 @_Z3fooi(i32 %i) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  %rem = srem i32 %i, 2
+  %tobool = icmp ne i32 %rem, 0
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:
+  %mul = mul nsw i32 %i, 7
+  %call = invoke i32 @_Z3bari(i32 %mul)
+          to label %invoke.cont unwind label %lpad
+
+invoke.cont:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @__llvm_profile_name__Z3fooi, i32 0, i32 0), i64 57451243578, i32 4, i32 1)
+  br label %if.end
+
+lpad:
+  %tmp = landingpad { i8*, i32 }
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %tmp1 = extractvalue { i8*, i32 } %tmp, 0
+  %tmp2 = extractvalue { i8*, i32 } %tmp, 1
+  br label %catch.dispatch
+
+catch.dispatch:
+  %tmp3 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %tmp2, %tmp3
+  br i1 %matches, label %catch, label %eh.resume
+
+catch:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @__llvm_profile_name__Z3fooi, i32 0, i32 0), i64 57451243578, i32 4, i32 2)
+  %tmp4 = call i8* @__cxa_begin_catch(i8* %tmp1)
+  %tmp5 = bitcast i8* %tmp4 to i32*
+  %tmp6 = load i32, i32* %tmp5, align 4
+  %tmp7 = load i32, i32* @val, align 4
+  %sub = sub nsw i32 %tmp7, %tmp6
+  store i32 %sub, i32* @val, align 4
+  call void @__cxa_end_catch()
+  br label %try.cont
+
+try.cont:
+  ret i32 -1
+
+if.end:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @__llvm_profile_name__Z3fooi, i32 0, i32 0), i64 57451243578, i32 4, i32 0)
+  %tmp8 = load i32, i32* @val, align 4
+  %add = add nsw i32 %tmp8, %i
+  store i32 %add, i32* @val, align 4
+  br label %try.cont
+
+eh.resume:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @__llvm_profile_name__Z3fooi, i32 0, i32 0), i64 57451243578, i32 4, i32 3)
+  %lpad.val = insertvalue { i8*, i32 } undef, i8* %tmp1, 0
+  %lpad.val3 = insertvalue { i8*, i32 } %lpad.val, i32 %tmp2, 1
+  resume { i8*, i32 } %lpad.val3
+}
+
+declare i32 @__gxx_personality_v0(...)
+
+declare i32 @llvm.eh.typeid.for(i8*)
+
+declare i8* @__cxa_begin_catch(i8*)
+
+declare void @__cxa_end_catch()
+

llvm/trunk/test/Transforms/PGOProfile/landingpad_use.ll

+; RUN: llvm-profdata merge %S/Inputs/landingpad.proftext -o %T/landingpad.profdata
+; RUN: opt < %s -pgo-instr-use -pgo-profile-file=%T/landingpad.profdata -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@val = global i32 0, align 4
+@_ZTIi = external constant i8*
+
+define i32 @_Z3bari(i32 %i) {
+entry:
+  %rem = srem i32 %i, 3
+  %tobool = icmp ne i32 %rem, 0
+  br i1 %tobool, label %if.then, label %if.end
+; CHECK: !prof !0
+
+if.then:
+  %exception = call i8* @__cxa_allocate_exception(i64 4)
+  %tmp = bitcast i8* %exception to i32*
+  store i32 %i, i32* %tmp, align 16
+  call void @__cxa_throw(i8* %exception, i8* bitcast (i8** @_ZTIi to i8*), i8* null)
+  unreachable
+
+if.end:
+  ret i32 0
+}
+
+declare i8* @__cxa_allocate_exception(i64)
+
+declare void @__cxa_throw(i8*, i8*, i8*)
+
+define i32 @_Z3fooi(i32 %i) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  %rem = srem i32 %i, 2
+  %tobool = icmp ne i32 %rem, 0
+  br i1 %tobool, label %if.then, label %if.end
+; CHECK: !prof !1
+
+if.then:
+  %mul = mul nsw i32 %i, 7
+  %call = invoke i32 @_Z3bari(i32 %mul)
+          to label %invoke.cont unwind label %lpad
+
+invoke.cont:
+  br label %if.end
+
+lpad:
+  %tmp = landingpad { i8*, i32 }
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %tmp1 = extractvalue { i8*, i32 } %tmp, 0
+  %tmp2 = extractvalue { i8*, i32 } %tmp, 1
+  br label %catch.dispatch
+
+catch.dispatch:
+  %tmp3 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %tmp2, %tmp3
+  br i1 %matches, label %catch, label %eh.resume
+; CHECK: !prof !2
+
+catch:
+  %tmp4 = call i8* @__cxa_begin_catch(i8* %tmp1)
+  %tmp5 = bitcast i8* %tmp4 to i32*
+  %tmp6 = load i32, i32* %tmp5, align 4
+  %tmp7 = load i32, i32* @val, align 4
+  %sub = sub nsw i32 %tmp7, %tmp6
+  store i32 %sub, i32* @val, align 4
+  call void @__cxa_end_catch()
+  br label %try.cont
+
+try.cont:
+  ret i32 -1
+
+if.end:
+  %tmp8 = load i32, i32* @val, align 4
+  %add = add nsw i32 %tmp8, %i
+  store i32 %add, i32* @val, align 4
+  br label %try.cont
+
+eh.resume:
+  %lpad.val = insertvalue { i8*, i32 } undef, i8* %tmp1, 0
+  %lpad.val3 = insertvalue { i8*, i32 } %lpad.val, i32 %tmp2, 1
+  resume { i8*, i32 } %lpad.val3
+}
+
+declare i32 @__gxx_personality_v0(...)
+
+declare i32 @llvm.eh.typeid.for(i8*)
+
+declare i8* @__cxa_begin_catch(i8*)
+
+declare void @__cxa_end_catch()
+
+; CHECK: !0 = !{!"branch_weights", i32 2, i32 1}
+; CHECK: !1 = !{!"branch_weights", i32 3, i32 2}
+; CHECK: !2 = !{!"branch_weights", i32 2, i32 0}

llvm/trunk/test/Transforms/PGOProfile/loop1_gen.ll

+; RUN: opt < %s -pgo-instr-gen -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: @__llvm_profile_name__Z15test_simple_fori = private constant [20 x i8] c"_Z15test_simple_fori"
+
+define i32 @_Z15test_simple_fori(i32 %n) {
+entry:
+  br label %for.cond
+
+for.cond:
+  %i = phi i32 [ 0, %entry ], [ %inc1, %for.inc ]
+  %sum = phi i32 [ 1, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i, %n
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+  %inc = add nsw i32 %sum, 1
+  br label %for.inc
+
+for.inc:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([20 x i8], [20 x i8]* @__llvm_profile_name__Z15test_simple_fori, i32 0, i32 0), i64 32052181608, i32 2, i32 0)
+  %inc1 = add nsw i32 %i, 1
+  br label %for.cond
+
+for.end:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([20 x i8], [20 x i8]* @__llvm_profile_name__Z15test_simple_fori, i32 0, i32 0), i64 32052181608, i32 2, i32 1)
+  ret i32 %sum
+}

llvm/trunk/test/Transforms/PGOProfile/loop1_use.ll

+; RUN: llvm-profdata merge %S/Inputs/loop1.proftext -o %T/loop1.profdata
+; RUN: opt < %s -pgo-instr-use -pgo-profile-file=%T/loop1.profdata -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z15test_simple_fori(i32 %n) {
+entry:
+  br label %for.cond
+
+for.cond:
+  %i = phi i32 [ 0, %entry ], [ %inc1, %for.inc ]
+  %sum = phi i32 [ 1, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i, %n
+  br i1 %cmp, label %for.body, label %for.end
+; CHECK: !prof !0
+
+for.body:
+  %inc = add nsw i32 %sum, 1
+  br label %for.inc
+
+for.inc:
+  %inc1 = add nsw i32 %i, 1
+  br label %for.cond
+
+for.end:
+  ret i32 %sum
+}
+
+; CHECK: !0 = !{!"branch_weights", i32 96, i32 4}

llvm/trunk/test/Transforms/PGOProfile/loop2_gen.ll

+; RUN: opt < %s -pgo-instr-gen -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: @__llvm_profile_name__Z13test_do_whilei = private constant [18 x i8] c"_Z13test_do_whilei"
+
+define i32 @_Z13test_do_whilei(i32 %n) {
+entry:
+  br label %do.body
+
+do.body:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc1, %do.cond ]
+  %sum = phi i32 [ 1, %entry ], [ %inc, %do.cond ]
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([18 x i8], [18 x i8]* @__llvm_profile_name__Z13test_do_whilei, i32 0, i32 0), i64 29706172832, i32 2, i32 0)
+  %inc = add nsw i32 %sum, 1
+  br label %do.cond
+
+do.cond:
+  %inc1 = add nsw i32 %i.0, 1
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %do.body, label %do.end
+
+do.end:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([18 x i8], [18 x i8]* @__llvm_profile_name__Z13test_do_whilei, i32 0, i32 0), i64 29706172832, i32 2, i32 1)
+  ret i32 %inc
+}

llvm/trunk/test/Transforms/PGOProfile/loop2_use.ll

+; RUN: llvm-profdata merge %S/Inputs/loop2.proftext -o %T/loop2.profdata
+; RUN: opt < %s -pgo-instr-use -pgo-profile-file=%T/loop2.profdata -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z13test_do_whilei(i32 %n) {
+entry:
+  br label %do.body
+
+do.body:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc1, %do.cond ]
+  %sum = phi i32 [ 1, %entry ], [ %inc, %do.cond ]
+  %inc = add nsw i32 %sum, 1
+  br label %do.cond
+
+do.cond:
+  %inc1 = add nsw i32 %i.0, 1
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %do.body, label %do.end
+; CHECK: !prof !0
+
+do.end:
+  ret i32 %inc
+}
+
+; CHECK: !0 = !{!"branch_weights", i32 92, i32 4}

llvm/trunk/test/Transforms/PGOProfile/loop3_gen.ll

+; RUN: opt < %s -pgo-instr-gen -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: @__llvm_profile_name__Z15test_nested_foriii = private constant [22 x i8] c"_Z15test_nested_foriii"
+
+define i32 @_Z15test_nested_foriii(i32 %r, i32 %s, i32 %t) {
+entry:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([22 x i8], [22 x i8]* @__llvm_profile_name__Z15test_nested_foriii, i32 0, i32 0), i64 75296580464, i32 4, i32 3)
+  br label %for.cond
+
+for.cond:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc12, %for.inc11 ]
+  %nested_for_sum.0 = phi i32 [ 1, %entry ], [ %nested_for_sum.1, %for.inc11 ]
+  %cmp = icmp slt i32 %i.0, %r
+  br i1 %cmp, label %for.body, label %for.end13
+
+for.body:
+  br label %for.cond1
+
+for.cond1:
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc9, %for.inc8 ]
+  %nested_for_sum.1 = phi i32 [ %nested_for_sum.0, %for.body ], [ %nested_for_sum.2, %for.inc8 ]
+  %cmp2 = icmp slt i32 %j.0, %s
+  br i1 %cmp2, label %for.body3, label %for.end10
+
+for.body3:
+  br label %for.cond4
+
+for.cond4:
+  %k.0 = phi i32 [ 0, %for.body3 ], [ %inc7, %for.inc ]
+  %nested_for_sum.2 = phi i32 [ %nested_for_sum.1, %for.body3 ], [ %inc, %for.inc ]
+  %cmp5 = icmp slt i32 %k.0, %t
+  br i1 %cmp5, label %for.body6, label %for.end
+
+for.body6:
+  %inc = add nsw i32 %nested_for_sum.2, 1
+  br label %for.inc
+
+for.inc:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([22 x i8], [22 x i8]* @__llvm_profile_name__Z15test_nested_foriii, i32 0, i32 0), i64 75296580464, i32 4, i32 0)
+  %inc7 = add nsw i32 %k.0, 1
+  br label %for.cond4
+
+for.end:
+  br label %for.inc8
+
+for.inc8:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([22 x i8], [22 x i8]* @__llvm_profile_name__Z15test_nested_foriii, i32 0, i32 0), i64 75296580464, i32 4, i32 1)
+  %inc9 = add nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.end10:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([22 x i8], [22 x i8]* @__llvm_profile_name__Z15test_nested_foriii, i32 0, i32 0), i64 75296580464, i32 4, i32 2)
+  br label %for.inc11
+
+for.inc11:
+  %inc12 = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end13:
+  ret i32 %nested_for_sum.0
+}

llvm/trunk/test/Transforms/PGOProfile/loop3_use.ll

+; RUN: llvm-profdata merge %S/Inputs/loop3.proftext -o %T/loop3.profdata
+; RUN: opt < %s -pgo-instr-use -pgo-profile-file=%T/loop3.profdata -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z15test_nested_foriii(i32 %r, i32 %s, i32 %t) {
+entry:
+  br label %for.cond
+
+for.cond:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc12, %for.inc11 ]
+  %nested_for_sum.0 = phi i32 [ 1, %entry ], [ %nested_for_sum.1, %for.inc11 ]
+  %cmp = icmp slt i32 %i.0, %r
+  br i1 %cmp, label %for.body, label %for.end13
+; CHECK: !prof !0
+
+for.body:
+  br label %for.cond1
+
+for.cond1:
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc9, %for.inc8 ]
+  %nested_for_sum.1 = phi i32 [ %nested_for_sum.0, %for.body ], [ %nested_for_sum.2, %for.inc8 ]
+  %cmp2 = icmp slt i32 %j.0, %s
+  br i1 %cmp2, label %for.body3, label %for.end10
+; CHECK: !prof !1
+
+for.body3:
+  br label %for.cond4
+
+for.cond4:
+  %k.0 = phi i32 [ 0, %for.body3 ], [ %inc7, %for.inc ]
+  %nested_for_sum.2 = phi i32 [ %nested_for_sum.1, %for.body3 ], [ %inc, %for.inc ]
+  %cmp5 = icmp slt i32 %k.0, %t
+  br i1 %cmp5, label %for.body6, label %for.end
+; CHECK: !prof !2
+
+for.body6:
+  %inc = add nsw i32 %nested_for_sum.2, 1
+  br label %for.inc
+
+for.inc:
+  %inc7 = add nsw i32 %k.0, 1
+  br label %for.cond4
+
+for.end:
+  br label %for.inc8
+
+for.inc8:
+  %inc9 = add nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.end10:
+  br label %for.inc11
+
+for.inc11:
+  %inc12 = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end13:
+  ret i32 %nested_for_sum.0
+}
+
+; CHECK: !0 = !{!"branch_weights", i32 10, i32 6}
+; CHECK: !1 = !{!"branch_weights", i32 33, i32 10}
+; CHECK: !2 = !{!"branch_weights", i32 186, i32 33}

llvm/trunk/test/Transforms/PGOProfile/noprofile_use.ll

+; RUN: not opt < %s -pgo-instr-use -pgo-profile-file=%T/notexisting.profdata -S  2>&1 |grep 'notexisting.profdata: No such file or directory'
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z9single_bbv() {
+entry:
+  ret i32 0
+}

llvm/trunk/test/Transforms/PGOProfile/single_bb_gen.ll

+; RUN: opt < %s -pgo-instr-gen -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: @__llvm_profile_name__Z9single_bbv = private constant [13 x i8] c"_Z9single_bbv"
+
+define i32 @_Z9single_bbv() {
+entry:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @__llvm_profile_name__Z9single_bbv, i32 0, i32 0), i64 12884901887, i32 1, i32 0)
+  ret i32 0
+}

llvm/trunk/test/Transforms/PGOProfile/switch_gen.ll

+; RUN: opt < %s -pgo-instr-gen -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: @__llvm_profile_name__Z13test_switch_1i = private constant [18 x i8] c"_Z13test_switch_1i"
+
+define i32 @_Z13test_switch_1i(i32 %i) {
+entry:
+  switch i32 %i, label %sw.default [
+    i32 1, label %sw.bb
+    i32 2, label %sw.bb1
+    i32 3, label %sw.bb3
+  ]
+
+sw.bb:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([18 x i8], [18 x i8]* @__llvm_profile_name__Z13test_switch_1i, i32 0, i32 0), i64 46628225222, i32 4, i32 2)
+  %add = add nsw i32 %i, 2
+  br label %sw.epilog
+
+sw.bb1:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([18 x i8], [18 x i8]* @__llvm_profile_name__Z13test_switch_1i, i32 0, i32 0), i64 46628225222, i32 4, i32 0)
+  %add2 = add nsw i32 %i, 100
+  br label %sw.epilog
+
+sw.bb3:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([18 x i8], [18 x i8]* @__llvm_profile_name__Z13test_switch_1i, i32 0, i32 0), i64 46628225222, i32 4, i32 1)
+  %add4 = add nsw i32 %i, 4
+  br label %sw.epilog
+
+sw.default:
+; CHECK: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([18 x i8], [18 x i8]* @__llvm_profile_name__Z13test_switch_1i, i32 0, i32 0), i64 46628225222, i32 4, i32 3)
+  %add5 = add nsw i32 %i, 1
+  br label %sw.epilog
+
+sw.epilog:
+  %retv = phi i32 [ %add5, %sw.default ], [ %add4, %sw.bb3 ], [ %add2, %sw.bb1 ], [ %add, %sw.bb ]
+  ret i32 %retv
+}

llvm/trunk/test/Transforms/PGOProfile/switch_use.ll

+; RUN: llvm-profdata merge %S/Inputs/switch.proftext -o %T/switch.profdata
+; RUN: opt < %s -pgo-instr-use -pgo-profile-file=%T/switch.profdata -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z13test_switch_1i(i32 %i) {
+entry:
+  switch i32 %i, label %sw.default [
+    i32 1, label %sw.bb
+    i32 2, label %sw.bb1
+    i32 3, label %sw.bb3
+  ]
+; CHECK: !prof !0
+
+sw.bb:
+  %add = add nsw i32 %i, 2
+  br label %sw.epilog
+
+sw.bb1:
+  %add2 = add nsw i32 %i, 100
+  br label %sw.epilog
+
+sw.bb3:
+  %add4 = add nsw i32 %i, 4
+  br label %sw.epilog
+
+sw.default:
+  %add5 = add nsw i32 %i, 1
+  br label %sw.epilog
+
+sw.epilog:
+  %retv = phi i32 [ %add5, %sw.default ], [ %add4, %sw.bb3 ], [ %add2, %sw.bb1 ], [ %add, %sw.bb ]
+  ret i32 %retv
+}
+
+;CHECK: !0 = !{!"branch_weights", i32 3, i32 0, i32 0, i32 0}