[misexpect] Re-implement MisExpect Diagnostics

[paulkirth]

Summary

Reimplements MisExpect diagnostics from D66324 to reconstruct its
original checking methodology only using MD_prof branch_weights
metadata.

New checks rely on 2 invariants:

1. For frontend instrumentation, MD_prof branch_weights will always be populated before llvm.expect intrinsics are lowered.

2. for IR and sample profiling, llvm.expect intrinsics will always be lowered before branch_weights are populated from the IR profiles.

These invariants allow the checking to assume how the existing branch
weights are populated depending on the profiling method used, and emit
the correct diagnostics. If these invariants are ever invalidated, the
MisExpect related checks would need to be updated, potentially by
re-introducing MD_misexpect metadata, and ensuring it always will be
transformed the same way as branch_weights in other optimization passes.

Frontend based profiling is now enabled without using LLVM Args, by
introducing a new CodeGen option, and checking if the -Wmisexpect flag
has been passed on the command line.

[paulkirth]

[misexpect] Fix Typo

[paulkirth]

Fix bad diff in arctool

[paulkirth]

Ready for review

[paulkirth]

• [misexpect] Add missing tests and modify diagnostic

[paulkirth]

• [misexpect] Add missing tests and modify diagnostic

[paulkirth]

• [misexpect] Add missing tests and modify diagnostic

[paulkirth]

ping

[tejohnson]

clang/include/clang/Basic/CodeGenOptions.def

178

"Set when ..."

clang/lib/CodeGen/CodeGenAction.cpp

1209

Out of curiosity, since I am less familiar with clang than llvm, when is this path taken vs where this is done at line 336 in HandleTranslationUnit?

Also, it might be nice to have this code placed either consistently before or after the OptRecordFile handling in these two locations, so it is easier to compare.

llvm/docs/MisExpect.rst

3

I don't see a mention of -Wmisexpect in the document. Should there be user-facing clang documentation, this seems more specific to the LLVM implementation?

23

Suggest using "profile weight" not profiling counter since we don't really have profile counters associated with instructions (rather with edges in the MST, at least in the IR PGO).

Also, doesn't the profile weight being too low only handle the LIKELY case? What about something being marked UNLIKELY with a hot/high profile weight? edit: After looking through the implementation, I think the comparison only being done in this direction is based on the way it is implemented, but it is unclear from this documentation here how the comparison is handling things being off in either direction.

28

grammatical issue "prior to when ... being assigned" - suggest "are assigned".

40

s/count/weight/

Also, similar to my earlier comment, what about an expect UNLIKELY branch with a high profile weight?

49

As noted in my comment at the top, it would be good to have user-facing clang documentation, in which case the clang version of this option is -Rpass=misexpect.

55

Looking at the code, the -pgo-warn-misexpect seems to be useful for internal LLVM testing via 'opt', to mimic -Wmisexpect, so it probably should be documented as such.

llvm/include/llvm/Transforms/Utils/MisExpect.h

40

Update function name.

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

110

Is there a reason why this line has changed ordering w.r.t. setMetadata?

llvm/lib/Transforms/Utils/MisExpect.cpp

158

This is the only use of Index - can you just use MaxId directly? I guess the assumption is that the ExpectedWeights array has the same ordering as the RealWeights array, so we can check if the corresponding real weight from profile is colder than the most likely weight from the expect. Some comments to describe how the comparison is being done in this code more intuitively would help make it easier to understand.

167

Why is this called a "Threshold" and not just a "Probability"?

171

Is this too strict - i.e. what if they are off by only a small amount?

199

A lot of the code in this and the backend case above are similar - could you refactor the common handling into a helper?

[paulkirth]

Consolodate common code, clarify documentation, and address comments

[paulkirth]

clang/lib/CodeGen/CodeGenAction.cpp

1209

That was a good catch, I had forgotten to remove this after patching in line 366. I moved that a bit a few lines lower to fit more nicely, and removed this one entirely.

llvm/docs/MisExpect.rst

3

I will update the patch to include similar documentation this for clang.

Additionally, my understanding is that documentation for warnings is auto-generated from the tablegen, so that at least will be available automatically.

23

Maybe my mental model is off here, but doesn't the llvm.expect intrinsic mark a specific value as the 'likely' or expected value? So if you want to mark a branch as unlikely, you're essentially marking the other half of it as 'hot'.

We could change the comparison to compare all parts of the branch weights too, but the case of an 'unlikely' branch being too hot in my model is captured by the 'likely' branch becoming too 'cold'.

If that is incorrect, I'd really appreciate some guidance on how to model this more accurately.

40

I think I've reworded this to clarify things a bit more, but let me know if it still needs some polish.

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

110

I think I actually restored this to what it was before the original MisExpect patch, but there is no need for that, so I've removed it.

llvm/lib/Transforms/Utils/MisExpect.cpp

171

Maybe. I don't know what a good default fudge factor would be, though. Maybe use 5%, and expose a flag that can override it?

Another approach is that the values used by llvm.expect can be changed via clang flags, which will update the weights checked against.

[xbolva00]

Please also consider https://github.com/llvm/llvm-project/issues/46534

[paulkirth]

MisExpect was originally intended to be quite strict, so that developers would audit their code and re-evaluate the correctness of their annotations,or if they were needed at all.

I think I'm still of a mind that getting flagged by MisExpect indicates that a different annotation would be more beneficial, such as llvm.expect.with.probability.

Regardless, I agree its good to give users an option to relax the checking when they want to, so I will add an option that allows them to specify a scaling factor for the threshold.

[paulkirth]

Add clang and llvm options to realx MisExpect checking.

The options take an integer, expected to bin in the range [0,100)
and reduce the threshold value we compare against by that percentage.

I modeled this on remark's hotness threshold option, which is close to what
we want here, but we would like this to use a percentage instead of the
profiling count directly.

[tejohnson]

clang/include/clang/Basic/CodeGenOptions.h

425

s/Tollerance/Tolerance/ (and elsewhere throughout patch)

clang/lib/Frontend/CompilerInvocation.cpp

1983

Add tests for expected errors?

clang/test/Profile/misexpect-branch.c

26

Can you add a case where an unlikely() is wrong?

llvm/docs/MisExpect.rst

3

Should the clang documentation already be added to this patch? I couldn't find it.

23

Yes I agree that is how llvm.expect is implemented, and I can see from your implementation that it should be handling that correctly. It was just unclear from the way it is written here what was happening. I like the new wording which is less specific to the way the checking is implemented.

40

I think the new version is good, thanks.

llvm/include/llvm/Transforms/Utils/MisExpectTolleranceParser.h

12 ↗

(On Diff #414523)

Is the end of the sentence incomplete? I.e. should be "both int and (something else)"?

26 ↗

(On Diff #414523)

Fix line wrapping. But sentence could be simplified too - is this just saying that the input must be an integer?

42 ↗

(On Diff #414523)

Where is this class used?

51 ↗

(On Diff #414523)

I don't see where 'auto' is handled?

llvm/lib/Transforms/IPO/SampleProfile.cpp

1744

Document const parameter (e.g. "/*IsFrontend=*/false"), here and in other calls.

llvm/lib/Transforms/Utils/MisExpect.cpp

79

Suggest renaming to something more intuitive. E.g. getInstCondition?

181

typo in calculate

182

typo in collected

189

afaict this handling duplicates what is done in parseTolleranceOption when the tolerance comes in from the clang option. Can you just do this handling once, here?

llvm/test/Transforms/PGOProfile/misexpect-branch-correct.ll

2

Add a one sentence description at the top of the llvm tests about what they are testing.

4

The old PM is gone in the optimization pipeline, so these old PM lines in this and other tests and the comment about the new PM can go away.

[paulkirth]

Address comments.

Added clang documentation.

Fixed various typos.

Updated tests per comments for clang and LLVM.

Removed dead class definition.

Removed clamping from tolerance parser.

[paulkirth]

clang/test/Profile/misexpect-branch.c

26

I've added one, but I'm not sure it tests anything meaningfully, since an unlikely path being too hot is really the same check as a likely path being too cold.

llvm/docs/MisExpect.rst

3

In the last update the clang documentation was a bit too close to the llvm documentation. I think they are distinct enough now to be separately useful, but maybe it's better to merge the two?

55

Yes, its useful to test llvm, but shouldn't opt be usable in the same way? To me it seems useful for opt to support the warning directly too, but I'm happy to defer here if you think that's confusing or shouldn't be the case.

llvm/lib/Transforms/Utils/MisExpect.cpp

79

That's definitely a better name. Thanks for the suggestion.

189

This is now the only place we check/modify the value.

[tejohnson]

lgtm

Just some minor cleanup before submitting as noted below.

clang/test/Profile/misexpect-branch.c

4

Comment is a little unclear, as it is testing both likely and unlikely branches.

10

nit: stray empty comment line?

26

Right, it is just for completeness to test / illustrate that the handling works in both directions.

llvm/docs/MisExpect.rst

3

Yeah there is a fair amount of overlap, but I at least would want the clang documentation you added. Seems fine to have the llvm internals documentation too, though.

55

Oh I'm not disagreeing with having the internal option and using it for opt, that's very useful. My comment was in the context of not having the user-facing clang documentation with the clang driver level option (which you since added). I was just suggesting you add a note that this option is an alternative to the clang option for use when e.g. testing via opt. Since there is now separate clang documentation I think it is less important now.

llvm/include/llvm/Transforms/Utils/MisExpectToleranceParser.h

27 ↗

(On Diff #415990)

Given that there is only one callsite to this helper, I think just move it into the calling source file and avoid adding a new header.

llvm/lib/IR/LLVMContextImpl.h

1384

s/tollerate/tolerate/

llvm/test/Transforms/PGOProfile/misexpect-branch-correct.ll

4

I see you removed the NewPM-style invocations and kept the legacy ones - afaict opt will now convert the legacy style pass invocations to the new PM, but I think it is preferable to use the New PM style invocations.

[xbolva00]

Add Clang release note as well please.

clang/docs/MisExpect.rst

59

value

[paulkirth]

Fixup remaining outstanding issues

• fix typos
• add misexpect to clang release notes
• restore new pm style opt invocations in llvm tests
• move single header function into implementation file
• clarify comment in test file

[paulkirth]

llvm/docs/MisExpect.rst

55

Thanks for the clarification.

llvm/test/Transforms/PGOProfile/misexpect-branch-correct.ll

4

yes, I misread your earlier comment. I have restored the New PM style opt invocations, and removed the legacy PM ones.

[thakis]

Looks like this breaks tests: http://45.33.8.238/linux/71396/step_7.txt

Please take a look, and revert for now if it takes a while to fix.

[paulkirth]

These pass for me locally, so I'm reverting for now and will dig into this tomorrow.

[fhahn]

The test also failed in the Phabricator pre-commit CI, please keep an eye on it before re-submitting (failure link for latest diff was https://buildkite.com/llvm-project/premerge-checks/builds/83983#39c06525-7452-412d-af83-ae2cc2d30cdc)

[paulkirth]

Add missing GenerateArgs call to propagate flags to the backend outside of cc1

[paulkirth]

clang/lib/Frontend/CompilerInvocation.cpp

1554

I really don't understand why this step is necessary, or why in my local builds omitting the call to GenerateArgs works at all. I only arrived at this change by noticing other options do the same, and this seemed to fix the issue with tests using the repro instructions from the precommit bots.

It seems a bit strange that Clang parses the option, stores it to a CodeGenOption then puts it back as a string argument to be parsed again later and put into the same data structure. Is this a result of an earlier architecture in Clang? if so, should we reconsider its design?

[paulkirth]

Fix check for tolerance diagnostic since we now use GenerateArgs the same way as hotness threshold.

Since it has a default value, we need to also ensure that it uses a pattern similar to other options.

[paulkirth]

rebase

[tejohnson]

clang/lib/Frontend/CompilerInvocation.cpp

1554

My understanding is that this is required as part of the cc1 command line parsing. Not sure why it worked in your local builds but not elsewhere. There is some info here: https://clang.llvm.org/docs/InternalsManual.html#adding-new-command-line-option

[paulkirth]

@tejohnson thanks for pointing me to the document. I knew it had something to do w/ CC1 but missed that this was well documented.

Is there anything else that needs to be done, or do you think this is good to land again?

[tejohnson]

In D115907#3412685, @paulkirth wrote:

@tejohnson thanks for pointing me to the document. I knew it had something to do w/ CC1 but missed that this was well documented.

I was equally unaware of the documentation of this until you asked and I tried to come up with a reasonable explanation for you =)

Is there anything else that needs to be done, or do you think this is good to land again?

lgtm

[tonic]

This is breaking the docs build with the following warning: "MisExpect.rst:document isn't included in any toctree." By default, docs warnings are treated as errors. Can you fix this?

[paulkirth]

reverted. I will fix this tomorrow. Sorry for the trouble

[paulkirth]

Fix missing reference in TOC & fix formatting of tables

[paulkirth]

Rebase

[jgorbe]

Hi, this patch is causing floating point exceptions for us during profile generation. On a debug build I get this assertion failure (see stack trace below):

clang: /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Support/BranchProbability.cpp:41: llvm::BranchProbability::BranchProbability(uint32_t, uint32_t): Assertion `Denominator > 0 && "Denominator cannot be 0!"' failed.

Printing some values around the problem I got

TotalBranchWeight = 4294967296                   
LikelyBranchWeight = 2147483648                                                                                                                                                                              
UnlikelyBranchWeight = 2147483648                                                                                                                                                                            
NumUnlikelyTargets = 1

I see the BranchProbability constructor takes uint32_ts, so this looks like it's overflowing to 0 (4294967296 is exactly 2**32).

I'm going to revert the patch to unbreak our build. Please let me know if you need more details and I'll try to come up with a reproducer I can share. Here's the stack trace for the assertion.

 #0 0x000000000a7f992a llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Support/Unix/Signals.inc:565:11
 #1 0x000000000a7f9afb PrintStackTraceSignalHandler(void*) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Support/Unix/Signals.inc:632:1                                                                   
 #2 0x000000000a7f80bb llvm::sys::RunSignalHandlers() /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Support/Signals.cpp:102:5                                                                             
 #3 0x000000000a7fa271 SignalHandler(int) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Support/Unix/Signals.inc:407:1                                                                                    
 #4 0x00007ff57cfe2200 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x13200)                                                                                                                          
 #5 0x00007ff57ca678a1 raise ./signal/../sysdeps/unix/sysv/linux/raise.c:50:1                                                                                                                                
 #6 0x00007ff57ca51546 abort ./stdlib/abort.c:81:7                                                                                                                                                           
 #7 0x00007ff57ca5142f get_sysdep_segment_value ./intl/loadmsgcat.c:509:8                                                                                                                                    
 #8 0x00007ff57ca5142f _nl_load_domain ./intl/loadmsgcat.c:970:34                                                                                                                                            
 #9 0x00007ff57ca60222 (/lib/x86_64-linux-gnu/libc.so.6+0x35222)                                                                                                                                             
#10 0x000000000a6cb517 llvm::BranchProbability::BranchProbability(unsigned int, unsigned int) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Support/BranchProbability.cpp:0:3                             
#11 0x000000000a937a4d llvm::misexpect::verifyMisExpect(llvm::Instruction&, llvm::ArrayRef<unsigned int>, llvm::ArrayRef<unsigned int>) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Transforms/Utils/MisExpect.cpp:190:54                                                                                                                                                                                            
#12 0x000000000a937ef3 llvm::misexpect::checkBackendInstrumentation(llvm::Instruction&, llvm::ArrayRef<unsigned int>) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Transforms/Utils/MisExpect.cpp:217:1  
#13 0x000000000a93807b llvm::misexpect::checkExpectAnnotations(llvm::Instruction&, llvm::ArrayRef<unsigned int>, bool) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Transforms/Utils/MisExpect.cpp:236:1 
#14 0x0000000009e1339c (anonymous namespace)::SampleProfileLoader::generateMDProfMetadata(llvm::Function&) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Transforms/IPO/SampleProfile.cpp:1755:19         
#15 0x0000000009e10d94 (anonymous namespace)::SampleProfileLoader::emitAnnotations(llvm::Function&) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Transforms/IPO/SampleProfile.cpp:0:5                    
#16 0x0000000009e1022b (anonymous namespace)::SampleProfileLoader::runOnFunction(llvm::Function&, llvm::AnalysisManager<llvm::Module>*) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Transforms/IPO/SampleProfile.cpp:2199:5                                                                                                                                                                                          
#17 0x0000000009e0ce8b (anonymous namespace)::SampleProfileLoader::runOnModule(llvm::Module&, llvm::AnalysisManager<llvm::Module>*, llvm::ProfileSummaryInfo*, llvm::CallGraph*) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Transforms/IPO/SampleProfile.cpp:2113:15                                                                                                                                                
#18 0x0000000009e0b882 llvm::SampleProfileLoaderPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/Transforms/IPO/SampleProfile.cpp:2229:7
#19 0x000000000c6e35c5 llvm::detail::PassModel<llvm::Module, llvm::SampleProfileLoaderPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/local/google/home/jgorbe/code/llvm/llvm/include/llvm/IR/PassManagerInternal.h:88:17
#20 0x0000000009a7ee41 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/local/google/home/jgorbe/code/llvm/llvm/include/llvm/IR/PassManager.h:522:16
#21 0x000000000c5c9ae1 runNewPMPasses(llvm::lto::Config const&, llvm::Module&, llvm::TargetMachine*, unsigned int, bool, llvm::ModuleSummaryIndex*, llvm::ModuleSummaryIndex const*) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/LTO/LTOBackend.cpp:312:3
#22 0x000000000c5c8cfe llvm::lto::opt(llvm::lto::Config const&, llvm::TargetMachine*, unsigned int, llvm::Module&, bool, llvm::ModuleSummaryIndex*, llvm::ModuleSummaryIndex const*, std::vector<unsigned char, std::allocator<unsigned char> > const&) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/LTO/LTOBackend.cpp:373:3
#23 0x000000000c5cba45 llvm::lto::thinBackend(llvm::lto::Config const&, unsigned int, std::function<llvm::Expected<std::unique_ptr<llvm::CachedFileStream, std::default_delete<llvm::CachedFileStream> > > (unsigned int)>, llvm::Module&, llvm::ModuleSummaryIndex const&, llvm::StringMap<std::unordered_set<unsigned long, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<unsigned long> >, llvm::MallocAllocator> const&, llvm::DenseMap<unsigned long, llvm::GlobalValueSummary*, llvm::DenseMapInfo<unsigned long, void>, llvm::detail::DenseMapPair<unsigned long, llvm::GlobalValueSummary*> > const&, llvm::MapVector<llvm::StringRef, llvm::BitcodeModule, llvm::DenseMap<llvm::StringRef, unsigned int, llvm::DenseMapInfo<llvm::StringRef, void>, llvm::detail::DenseMapPair<llvm::StringRef, unsigned int> >, std::vector<std::pair<llvm::StringRef, llvm::BitcodeModule>, std::allocator<std::pair<llvm::StringRef, llvm::BitcodeModule> > > >*, std::vector<unsigned char, std::allocator<unsigned char> > const&)::$_6::operator()(llvm::Module&, llvm::TargetMachine*, std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile> >) const /usr/local/google/home/jgorbe/code/llvm/llvm/lib/LTO/LTOBackend.cpp:594:13
#24 0x000000000c5cb971 llvm::lto::thinBackend(llvm::lto::Config const&, unsigned int, std::function<llvm::Expected<std::unique_ptr<llvm::CachedFileStream, std::default_delete<llvm::CachedFileStream> > > (unsigned int)>, llvm::Module&, llvm::ModuleSummaryIndex const&, llvm::StringMap<std::unordered_set<unsigned long, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<unsigned long> >, llvm::MallocAllocator> const&, llvm::DenseMap<unsigned long, llvm::GlobalValueSummary*, llvm::DenseMapInfo<unsigned long, void>, llvm::detail::DenseMapPair<unsigned long, llvm::GlobalValueSummary*> > const&, llvm::MapVector<llvm::StringRef, llvm::BitcodeModule, llvm::DenseMap<llvm::StringRef, unsigned int, llvm::DenseMapInfo<llvm::StringRef, void>, llvm::detail::DenseMapPair<llvm::StringRef, unsigned int> >, std::vector<std::pair<llvm::StringRef, llvm::BitcodeModule>, std::allocator<std::pair<llvm::StringRef, llvm::BitcodeModule> > > >*, std::vector<unsigned char, std::allocator<unsigned char> > const&) /usr/local/google/home/jgorbe/code/llvm/llvm/lib/LTO/LTOBackend.cpp:670:3
#25 0x000000000ad17e95 runThinLTOBackend(clang::DiagnosticsEngine&, llvm::ModuleSummaryIndex*, llvm::Module*, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, clang::BackendAction) /usr/local/google/home/jgorbe/code/llvm/clang/lib/CodeGen/BackendUtil.cpp:1670:11
#26 0x000000000ad174c8 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) /usr/local/google/home/jgorbe/code/llvm/clang/lib/CodeGen/BackendUtil.cpp:1711:9
#27 0x000000000bbd802f clang::CodeGenAction::ExecuteAction() /usr/local/google/home/jgorbe/code/llvm/clang/lib/CodeGen/CodeGenAction.cpp:1209:3
#28 0x000000000b9f1368 clang::FrontendAction::Execute() /usr/local/google/home/jgorbe/code/llvm/clang/lib/Frontend/FrontendAction.cpp:1036:7
#29 0x000000000b9206ab clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) /usr/local/google/home/jgorbe/code/llvm/clang/lib/Frontend/CompilerInstance.cpp:1036:23
#30 0x000000000bbc34b9 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) /usr/local/google/home/jgorbe/code/llvm/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:266:8
#31 0x0000000006c0de77 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) /usr/local/google/home/jgorbe/code/llvm/clang/tools/driver/cc1_main.cpp:248:13
#32 0x0000000006c0076b ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) /usr/local/google/home/jgorbe/code/llvm/clang/tools/driver/driver.cpp:317:5
#33 0x0000000006bff778 main /usr/local/google/home/jgorbe/code/llvm/clang/tools/driver/driver.cpp:388:5
#34 0x00007ff57ca527fd __libc_start_main ./csu/../csu/libc-start.c:332:16
#35 0x0000000006bfef3a _start (/usr/local/google/home/jgorbe/code/llvm-build/bin/clang+0x6bfef3a)

[jgorbe]

By the way, the line number for llvm::misexpect::verifyMisExpect in the stack trace above includes the debug printfs I inserted to get the variable values so it won't match the exact line number in the repo. But I think that's the only call to BranchProbability in that function so I hope it's not very confusing anyway. Sorry about that.

[paulkirth]

@jgorbe Sorry for the trouble. Thank you for the backtrace and the revert. Indeed, it seems like I've missed an assumption w.r.t. over/underflow, and will have to sort that out before re-landing.

[paulkirth]

Replace direct use of BranchProbability constructor w/ getBranchProbability().

getBranchProbability() already accounts for and scales branch probability
correctly using uint64_t parameters to fit into a 32-bit integer. This
should avoid any problems w/ overflow when using misexpect.

[paulkirth]

Remove commented out code

[tejohnson]

llvm/lib/Transforms/Utils/MisExpect.cpp

151

Nit: seems more intuitive to pass low before high. But not sure the low is needed in this case, see comment at callsite.

202

Looks like Tolerance is unsigned, as are the arguments to clamp. So it can never go below 0.

[paulkirth]

Swap parameters in clamp routine

[paulkirth]

rebase

[paulkirth]

rebase

[tejohnson]

lgtm if you are waiting for a re-review. As noted in my previous comment, you have added a little bit of unnecessary checking at the lower end with your new clamp function, since it is an unsigned value and can never go below 0. But it isn't a big deal if you prefer to keep that in to make it easier to transition to std::clamp.

[paulkirth]

Ah, thanks. I've had to try to re-land this so many times, I wanted to be sure the pre-submit was looking OK after rebasing. or at least be sure it didn't look like it was failing from any of my changes.

w.r.t. clamp, keeping it compatible was my intent.

[hans]

We gave this a try in Chromium: https://bugs.chromium.org/p/chromium/issues/detail?id=1434989

While the diagnostics are interesting, two things make this less useful for our developers:

1. It also fires in situations where the developer didn't set any expectations, for example for static variable initialization guards where clang implicitly adds branch weights (https://crbug.com/1434989#c7)
2. Due to inlining etc., it often gets the source locations wrong, which means it points at code where again there were no expectations -- but perhaps that code got inlined into an expectations somewhere else. (e.g. https://crbug.com/1434989#c9)

Especially 2) is probably not easy to fix. Do you have any tips on how developers can use this more effectively?

clang/include/clang/Driver/Options.td

1430

Should this be a driver mode option and not just cc1? The doc suggests using it, which currently won't work without an -Xclang prefix.

[paulkirth]

Thanks for the report Hans.

In D115907#4295363, @hans wrote:

We gave this a try in Chromium: https://bugs.chromium.org/p/chromium/issues/detail?id=1434989

While the diagnostics are interesting, two things make this less useful for our developers:

1. It also fires in situations where the developer didn't set any expectations, for example for static variable initialization guards where clang implicitly adds branch weights (https://crbug.com/1434989#c7)

Hmm, I wasn't even aware that clang would insert llvm.expect without a user annotation. I'm also a bit surprised to see this crop up, since we haven't run into it on Fuchsia.

The problem is that we can't really distinguish those cases in IR... and even when we could, for IR based instrumentation we'd need to embed that into the branch weights somehow. D131306 explores a way to track the provenance of branch weights, so we could probably use that to distinguish them if we could also distinguish the llvm.expect usages the compiler inserts from user inserted ones. I put that work on hold, since it needs an RFC and I've been busy w/ other things, but I'll take some time in the next day or two to write that out and post the RFC to discord, since D131306 should solve a big part of that issue.

2. Due to inlining etc., it often gets the source locations wrong, which means it points at code where again there were no expectations -- but perhaps that code got inlined into an expectations somewhere else. (e.g. https://crbug.com/1434989#c9)

The checking depends somewhat on the instrumentation type (frontend vs. backend instrumentation) In the case of frontend instrumentation, when the expect intrinsic is lowered (very early in the pipeline) we can report the diagnostic right away, since branch weights from profiling have already been attached. The should mean that you should get fairly accurate source information, since this happens before any optimizations run.

Backend instrumentation is more complicated, since we can't report the discrepancy until we're adding the branch weights to the IR. Whether inlining plays a role there or not is highly dependent on how you're compiling (i.e., no LTO, LTO, ThinLTO). The ordering is also somewhat dependent on if you're using Sampling or Instrumentation based profiles, but I believe both of those will always add weights before inlining. ThinLTO may be an outlier here, since I think weights from sampling based profiles can run multiple times in the ThinLTO pipeline.

Especially 2) is probably not easy to fix. Do you have any tips on how developers can use this more effectively?

When we report the diagnostic, we do our best to provide the source location, but that is only as good as what is available in the IR. I can certainly take a look at how we could improve reporting, but my recollection is that source information isn't always maintained well as the various passes run.If we're lucky in this case, we can maybe just tweak how its reporting the source location to include the inlining context. There's probably a bigger discussion that needs to be had about how to preserve debug and source location info through the backend passes.

The log also reported several places where expected hot code was never executed. If that isn't desirable, I'd also suggest that you could use the -fdiagnostic-hotness-threshold= to ignore reporting about branches that are not executed some minimum number of times. MisExpect is remarks based, so I beleive that is currently working. If not I'm happy to add that functionality.

clang/include/clang/Driver/Options.td

1430

That should also work from clang w/o -Xclang, shouldn't it? This is used exactly like -fdiagnostics-hotness-threshold=, so IIRC that should still work from clang.

[hans]

In D115907#4295923, @paulkirth wrote:

2. Due to inlining etc., it often gets the source locations wrong, which means it points at code where again there were no expectations -- but perhaps that code got inlined into an expectations somewhere else. (e.g. https://crbug.com/1434989#c9)

The checking depends somewhat on the instrumentation type (frontend vs. backend instrumentation) In the case of frontend instrumentation, when the expect intrinsic is lowered (very early in the pipeline) we can report the diagnostic right away, since branch weights from profiling have already been attached. The should mean that you should get fairly accurate source information, since this happens before any optimizations run.

We use the backend instrumentation since that gives the best performance, but it's good to hear that the locations may be more accurate with frontend instrumentation. Maybe we should add that to the docs?

The log also reported several places where expected hot code was never executed. If that isn't desirable, I'd also suggest that you could use the -fdiagnostic-hotness-threshold= to ignore reporting about branches that are not executed some minimum number of times. MisExpect is remarks based, so I beleive that is currently working. If not I'm happy to add that functionality.

Oh nice, I will try that flag.

clang/include/clang/Driver/Options.td

1430

Hmm, if I add -fdiagnostics-misexpect-tolerance=10 I get errors about the flag being unused. I had to use -Xclang for it to work.

[paulkirth]

In D115907#4296154, @hans wrote:

In D115907#4295923, @paulkirth wrote:

2. Due to inlining etc., it often gets the source locations wrong, which means it points at code where again there were no expectations -- but perhaps that code got inlined into an expectations somewhere else. (e.g. https://crbug.com/1434989#c9)

The checking depends somewhat on the instrumentation type (frontend vs. backend instrumentation) In the case of frontend instrumentation, when the expect intrinsic is lowered (very early in the pipeline) we can report the diagnostic right away, since branch weights from profiling have already been attached. The should mean that you should get fairly accurate source information, since this happens before any optimizations run.

We use the backend instrumentation since that gives the best performance, but it's good to hear that the locations may be more accurate with frontend instrumentation. Maybe we should add that to the docs?

Let me look into this a bit. I'm not sure if this is just we're not doing the best practice when printing the diagnostic, or if the resolution is being degraded due to optimizations. We may want to update the documentation anyway, but I'd like to be certain.

clang/include/clang/Driver/Options.td

1430

That isn't WAI then. I'll try to address that today.

clang/docs/MisExpect.rst

+===================
+Misexpect
+===================
+.. contents::
+
+.. toctree::
+   :maxdepth: 1
+
+When developers use ``llvm.expect`` intrinsics, i.e., through use of
+``__builtin_expect(...)``, they are trying to communicate how their code is
+expected to behave at runtime to the optimizer. These annotations, however, can
+be incorrect for a variety of reasons: changes to the code base invalidate them
+silently, the developer mis-annotated them (e.g., using ``LIKELY`` instead of
+``UNLIKELY``), or perhaps they assumed something incorrectly when they wrote
+the annotation. Regardless of why, it is useful to detect these situations so
+that the optimizer can make more useful decisions about the code. 
+
+MisExpect diagnostics are intended to help developers identify and address
+these situations, by comparing the branch weights added by the ``llvm.expect``
+intrinsic to those collected through profiling. Whenever these values are
+mismatched, a diagnostic is surfaced to the user. Details on how the checks
+operate in the LLVM backed can be found in LLVM's documentation.
+
+By default MisExpect checking is quite strict, because the use of the
+``llvm.expect`` intrinsic is designed for specialized cases, where the outcome
+of a condition is severely skewed. As a result, the optimizer can be extremely
+aggressive, which can result in performance degradation if the outcome is less
+predictable than the annotation suggests. Even when the annotation is correct
+90% of the time, it may be beneficial to either remove the annotation or to use
+a different intrinsic that can communicate the probability more directly.
+
+Because this may be too strict, MisExpect diagnostics are not enabled by
+default, and support an additional flag to tolerate some deviation from the
+exact thresholds. The ``-fdiagnostic-misexpect-tolerance=N`` accepts
+deviations when comparing branch weights within ``N%`` of the expected values.
+So passing ``-fdiagnostic-misexpect-tolerance=5`` will not report diagnostic messages
+if the branch weight from the profile is within 5% of the weight added by
+the ``llvm.expect`` intrinsic.
+
+MisExpect diagnostics are also available in the form of optimization remarks,
+which can be serialized and processed through the ``opt-viewer.py``
+scripts in LLVM.
+
+.. option:: -Rpass=misexpect
+
+  Enables optimization remarks for misexpect when profiling data conflicts with
+  use of ``llvm.expect`` intrinsics.
+
+
+.. option:: -Wmisexpect
+
+  Enables misexpect warnings when profiling data conflicts with use of
+  ``llvm.expect`` intrinsics.
+
+.. option:: -fdiagnostic-misexpect-tolerance=N
+
+   Relaxes misexpect checking to tolerate profiling values within N% of the 
+   expected branch weight. e.g., a value of ``N=5`` allows misexpect to check against
+   ``0.95 * Threshold``
+
+LLVM supports 4 types of profile formats: Frontend, IR, CS-IR, and
+Sampling. MisExpect Diagnostics are compatible with all Profiling formats.
+
++----------------+--------------------------------------------------------------------------------------+
+| Profile Type   | Description                                                                          |
++================+======================================================================================+
+| Frontend       | Profiling instrumentation added during compilation by the frontend, i.e. ``clang``    |
++----------------+--------------------------------------------------------------------------------------+
+| IR             | Profiling instrumentation added during by the LLVM backend                           |
++----------------+--------------------------------------------------------------------------------------+
+| CS-IR          | Context Sensitive IR based profiles                                                  |
++----------------+--------------------------------------------------------------------------------------+
+| Sampling       | Profiles collected through sampling with external tools, such as ``perf`` on Linux   |
++----------------+--------------------------------------------------------------------------------------+
+

clang/docs/ReleaseNotes.rst

 - ``-Winline-namespace-reopened-noninline`` now takes into account that the
   ``inline`` keyword must appear on the original but not necessarily all
   extension definitions of an inline namespace and therefore points its note
   at the original definition. This fixes `Issue 50794 (PR51452)
   <https://github.com/llvm/llvm-project/issues/50794>`_.
 - ``-Wunused-but-set-variable`` now also warns if the variable is only used
   by unary operators.
 
+- ``-Wmisexpect`` warns when the branch weights collected during profiling
+  conflict with those added by ``llvm.expect``.
+
 Non-comprehensive list of changes in this release
 -------------------------------------------------
 - The builtin function __builtin_dump_struct would crash clang when the target 
   struct have bitfield. Now it fixed, and __builtin_dump_struct support dump
   the bitwidth of bitfields.
   This fixes `Issue 54462 <https://github.com/llvm/llvm-project/issues/54462>`_.
 
 New Compiler Flags

clang/include/clang/Basic/CodeGenOptions.h

public:
   /// 3. None         => 'auto' threshold by user. The actual value is not
   ///                    available at command line, but will be synced with
   ///                    hotness threshold from profile summary during
   ///                    compilation.
   ///
   /// If threshold option is not specified, it is disabled by default.
   Optional<uint64_t> DiagnosticsHotnessThreshold = 0;
 
+  /// The maximum percentage profiling weights can deviate from the expected
+  /// values in order to be included in misexpect diagnostics.
+  Optional<uint64_t> DiagnosticsMisExpectTolerance = 0;
+
 public:
   // Define accessors/mutators for code generation options of enumeration type.
 #define CODEGENOPT(Name, Bits, Default)
 #define ENUM_CODEGENOPT(Name, Type, Bits, Default) \
   Type get##Name() const { return static_cast<Type>(Name); } \
   void set##Name(Type Value) { Name = static_cast<unsigned>(Value); }
 #include "clang/Basic/CodeGenOptions.def"
 

clang/include/clang/Basic/CodeGenOptions.def

 CODEGENOPT(MSVolatile        , 1, 0) ///< Set when /volatile:ms is enabled.
 CODEGENOPT(NoCommon          , 1, 0) ///< Set when -fno-common or C++ is enabled.
 CODEGENOPT(NoDwarfDirectoryAsm , 1, 0) ///< Set when -fno-dwarf-directory-asm is
                                        ///< enabled.
 CODEGENOPT(NoExecStack       , 1, 0) ///< Set when -Wa,--noexecstack is enabled.
 CODEGENOPT(FatalWarnings     , 1, 0) ///< Set when -Wa,--fatal-warnings is
                                      ///< enabled.
 CODEGENOPT(NoWarn            , 1, 0) ///< Set when -Wa,--no-warn is enabled.
+CODEGENOPT(MisExpect         , 1, 0) ///< Set when -Wmisexpect is enabled
 CODEGENOPT(EnableSegmentedStacks , 1, 0) ///< Set when -fsplit-stack is enabled.
 CODEGENOPT(NoInlineLineTables, 1, 0) ///< Whether debug info should contain
                                      ///< inline line tables.
 CODEGENOPT(StackClashProtector, 1, 0) ///< Set when -fstack-clash-protection is enabled.
 CODEGENOPT(NoImplicitFloat   , 1, 0) ///< Set when -mno-implicit-float is enabled.
 CODEGENOPT(NullPointerIsValid , 1, 0) ///< Assume Null pointer deference is defined.
 CODEGENOPT(OpenCLCorrectlyRoundedDivSqrt, 1, 0) ///< -cl-fp32-correctly-rounded-divide-sqrt
 CODEGENOPT(HIPCorrectlyRoundedDivSqrt, 1, 1) ///< -fno-hip-fp32-correctly-rounded-divide-sqrt

clang/include/clang/Basic/DiagnosticDriverKinds.td

 def err_drv_unable_to_set_working_directory : Error <
   "unable to set working directory: %0">;
 def err_drv_command_failure : Error<
   "unable to execute command: %0">;
 def err_drv_invalid_darwin_version : Error<
   "invalid Darwin version number: %0">;
 def err_drv_invalid_diagnotics_hotness_threshold : Error<
   "invalid argument in '%0', only integer or 'auto' is supported">;
+def err_drv_invalid_diagnotics_misexpect_tolerance : Error<
+  "invalid argument in '%0', only integers are supported">;
 def err_drv_missing_argument : Error<
   "argument to '%0' is missing (expected %1 value%s1)">;
 def err_drv_invalid_Xarch_argument_with_args : Error<
   "invalid Xarch argument: '%0', options requiring arguments are unsupported">;
 def err_drv_Xopenmp_target_missing_triple : Error<
   "cannot deduce implicit triple value for -Xopenmp-target, specify triple using -Xopenmp-target=<triple>">;
 def err_drv_invalid_Xopenmp_target_with_args : Error<
   "invalid -Xopenmp-target argument: '%0', options requiring arguments are unsupported">;
def warn_drv_unused_x : Warning<
   "'-x %0' after last input file has no effect">,
   InGroup<UnusedCommandLineArgument>;
 def warn_drv_empty_joined_argument : Warning<
   "joined argument expects additional value: '%0'">,
   InGroup<UnusedCommandLineArgument>;
 def warn_drv_diagnostics_hotness_requires_pgo : Warning<
   "argument '%0' requires profile-guided optimization information">,
   InGroup<UnusedCommandLineArgument>;
+def warn_drv_diagnostics_misexpect_requires_pgo : Warning<
+  "argument '%0' requires profile-guided optimization information">,
+  InGroup<UnusedCommandLineArgument>;
 def warn_drv_clang_unsupported : Warning<
   "the clang compiler does not support '%0'">;
 def warn_drv_deprecated_arg : Warning<
   "argument '%0' is deprecated, use '%1' instead">, InGroup<Deprecated>;
 def warn_drv_assuming_mfloat_abi_is : Warning<
   "unknown platform, assuming -mfloat-abi=%0">;
 def warn_drv_unsupported_float_abi_by_lib : Warning<
   "float ABI '%0' is not supported by current library">,

clang/include/clang/Basic/DiagnosticFrontendKinds.td

 def warn_profile_data_missing : Warning<
   "profile data may be incomplete: of %0 function%s0, %1 %plural{1:has|:have}1"
   " no data">,
   InGroup<ProfileInstrMissing>,
   DefaultIgnore;
 def warn_profile_data_unprofiled : Warning<
   "no profile data available for file \"%0\"">,
   InGroup<ProfileInstrUnprofiled>;
+def warn_profile_data_misexpect : Warning<
+  "Potential performance regression from use of __builtin_expect(): "
+  "Annotation was correct on %0 of profiled executions.">,
+  BackendInfo,
+  InGroup<MisExpect>;
 } // end of instrumentation issue category
 
 }

clang/include/clang/Basic/DiagnosticGroups.td

 def BackendOptimizationRemarkAnalysis : DiagGroup<"pass-analysis">;
 def BackendOptimizationFailure : DiagGroup<"pass-failed">;
 def BackendWarningAttributes : DiagGroup<"attribute-warning">;
 
 // Instrumentation based profiling warnings.
 def ProfileInstrMissing : DiagGroup<"profile-instr-missing">;
 def ProfileInstrOutOfDate : DiagGroup<"profile-instr-out-of-date">;
 def ProfileInstrUnprofiled : DiagGroup<"profile-instr-unprofiled">;
+def MisExpect : DiagGroup<"misexpect">;
 
 // AddressSanitizer frontend instrumentation remarks.
 def SanitizeAddressRemarks : DiagGroup<"sanitize-address">;
 
 // Issues with serialized diagnostics.
 def SerializedDiagnostics : DiagGroup<"serialized-diagnostics">;
 
 // A warning group for warnings about code that clang accepts when

clang/include/clang/Driver/Options.td

 defm diagnostics_show_hotness : BoolFOption<"diagnostics-show-hotness",
   CodeGenOpts<"DiagnosticsWithHotness">, DefaultFalse,
   PosFlag<SetTrue, [CC1Option], "Enable profile hotness information in diagnostic line">,
   NegFlag<SetFalse>>;
 def fdiagnostics_hotness_threshold_EQ : Joined<["-"], "fdiagnostics-hotness-threshold=">,
     Group<f_Group>, Flags<[CC1Option]>, MetaVarName<"<value>">,
     HelpText<"Prevent optimization remarks from being output if they do not have at least this profile count. "
     "Use 'auto' to apply the threshold from profile summary">;
+def fdiagnostics_misexpect_tolerance_EQ : Joined<["-"], "fdiagnostics-misexpect-tolerance=">,
+    Group<f_Group>, Flags<[CC1Option]>, MetaVarName<"<value>">,
+    HelpText<"Prevent misexpect diagnostics from being output if the profile counts are within N% of the expected. ">;
 defm diagnostics_show_option : BoolFOption<"diagnostics-show-option",
     DiagnosticOpts<"ShowOptionNames">, DefaultTrue,
     NegFlag<SetFalse, [CC1Option]>, PosFlag<SetTrue, [], "Print option name with mappable diagnostics">>;
 defm diagnostics_show_note_include_stack : BoolFOption<"diagnostics-show-note-include-stack",
     DiagnosticOpts<"ShowNoteIncludeStack">, DefaultFalse,
     PosFlag<SetTrue, [], "Display include stacks for diagnostic notes">,
     NegFlag<SetFalse>, BothFlags<[CC1Option]>>;
 def fdiagnostics_format_EQ : Joined<["-"], "fdiagnostics-format=">, Group<f_clang_Group>;

clang/lib/CodeGen/BackendUtil.cpp

for (const auto &Entry : HSOpts.UserEntries)
     if (!Entry.IsFramework &&
         (Entry.Group == frontend::IncludeDirGroup::Quoted ||
          Entry.Group == frontend::IncludeDirGroup::Angled ||
          Entry.Group == frontend::IncludeDirGroup::System))
       Options.MCOptions.IASSearchPaths.push_back(
           Entry.IgnoreSysRoot ? Entry.Path : HSOpts.Sysroot + Entry.Path);
   Options.MCOptions.Argv0 = CodeGenOpts.Argv0;
   Options.MCOptions.CommandLineArgs = CodeGenOpts.CommandLineArgs;
+  Options.MisExpect = CodeGenOpts.MisExpect;
 
   return true;
 }
 
 static Optional<GCOVOptions> getGCOVOptions(const CodeGenOptions &CodeGenOpts,
                                             const LangOptions &LangOpts) {
   if (!CodeGenOpts.EmitGcovArcs && !CodeGenOpts.EmitGcovNotes)
     return None;

clang/lib/CodeGen/CodeGenAction.cpp

void HandleTranslationUnit(ASTContext &C) override {
 
       std::unique_ptr<llvm::ToolOutputFile> OptRecordFile =
           std::move(*OptRecordFileOrErr);
 
       if (OptRecordFile &&
           CodeGenOpts.getProfileUse() != CodeGenOptions::ProfileNone)
         Ctx.setDiagnosticsHotnessRequested(true);
 
+      if (CodeGenOpts.MisExpect) {
+        Ctx.setMisExpectWarningRequested(true);
+      }
+
+      if (CodeGenOpts.DiagnosticsMisExpectTolerance) {
+        Ctx.setDiagnosticsMisExpectTolerance(
+            CodeGenOpts.DiagnosticsMisExpectTolerance);
+      }
+
       // Link each LinkModule into our module.
       if (LinkInModules())
         return;
 
       for (auto &F : getModule()->functions()) {
         if (const Decl *FD = Gen->GetDeclForMangledName(F.getName())) {
           auto Loc = FD->getASTContext().getFullLoc(FD->getLocation());
           // TODO: use a fast content hash when available.
public:
     OptimizationRemarkHandler(const llvm::DiagnosticInfoOptimizationBase &D);
     void OptimizationRemarkHandler(
         const llvm::OptimizationRemarkAnalysisFPCommute &D);
     void OptimizationRemarkHandler(
         const llvm::OptimizationRemarkAnalysisAliasing &D);
     void OptimizationFailureHandler(
         const llvm::DiagnosticInfoOptimizationFailure &D);
     void DontCallDiagHandler(const DiagnosticInfoDontCall &D);
+    /// Specialized handler for misexpect warnings.
+    /// Note that misexpect remarks are emitted through ORE
+    void MisExpectDiagHandler(const llvm::DiagnosticInfoMisExpect &D);
   };
 
   void BackendConsumer::anchor() {}
 }
 
 bool ClangDiagnosticHandler::handleDiagnostics(const DiagnosticInfo &DI) {
   BackendCon->DiagnosticHandlerImpl(DI);
   return true;
if (!LocCookie.isValid())
     return;
 
   Diags.Report(LocCookie, D.getSeverity() == DiagnosticSeverity::DS_Error
                               ? diag::err_fe_backend_error_attr
                               : diag::warn_fe_backend_warning_attr)
       << llvm::demangle(D.getFunctionName().str()) << D.getNote();
 }
 
+void BackendConsumer::MisExpectDiagHandler(
+    const llvm::DiagnosticInfoMisExpect &D) {
+  StringRef Filename;
+  unsigned Line, Column;
+  bool BadDebugInfo = false;
+  FullSourceLoc Loc =
+      getBestLocationFromDebugLoc(D, BadDebugInfo, Filename, Line, Column);
+
+  Diags.Report(Loc, diag::warn_profile_data_misexpect) << D.getMsg().str();
+
+  if (BadDebugInfo)
+    // If we were not able to translate the file:line:col information
+    // back to a SourceLocation, at least emit a note stating that
+    // we could not translate this location. This can happen in the
+    // case of #line directives.
+    Diags.Report(Loc, diag::note_fe_backend_invalid_loc)
+        << Filename << Line << Column;
+}
+
 /// This function is invoked when the backend needs
 /// to report something to the user.
 void BackendConsumer::DiagnosticHandlerImpl(const DiagnosticInfo &DI) {
   unsigned DiagID = diag::err_fe_inline_asm;
   llvm::DiagnosticSeverity Severity = DI.getSeverity();
   // Get the diagnostic ID based.
   switch (DI.getKind()) {
   case llvm::DK_InlineAsm:
case llvm::DK_OptimizationFailure:
     OptimizationFailureHandler(cast<DiagnosticInfoOptimizationFailure>(DI));
     return;
   case llvm::DK_Unsupported:
     UnsupportedDiagHandler(cast<DiagnosticInfoUnsupported>(DI));
     return;
   case llvm::DK_DontCall:
     DontCallDiagHandler(cast<DiagnosticInfoDontCall>(DI));
     return;
+  case llvm::DK_MisExpect:
+    MisExpectDiagHandler(cast<DiagnosticInfoMisExpect>(DI));
+    return;
   default:
     // Plugin IDs are not bound to any value as they are set dynamically.
     ComputeDiagRemarkID(Severity, backend_plugin, DiagID);
     break;
   }
   std::string MsgStorage;
   {
     raw_string_ostream Stream(MsgStorage);
void CodeGenAction::ExecuteAction() {
 
   if (Error E = OptRecordFileOrErr.takeError()) {
     reportOptRecordError(std::move(E), Diagnostics, CodeGenOpts);
     return;
   }
   std::unique_ptr<llvm::ToolOutputFile> OptRecordFile =
       std::move(*OptRecordFileOrErr);
 
   EmitBackendOutput(Diagnostics, CI.getHeaderSearchOpts(), CodeGenOpts,
                     TargetOpts, CI.getLangOpts(),
                     CI.getTarget().getDataLayoutString(), TheModule.get(), BA,
                     std::move(OS));
   if (OptRecordFile)
     OptRecordFile->keep();
 }
 
 //

clang/lib/Frontend/CompilerInvocation.cpp

 #include <vector>
 
 using namespace clang;
 using namespace driver;
 using namespace options;
 using namespace llvm::opt;
 
 //===----------------------------------------------------------------------===//
+// Helpers.
+//===----------------------------------------------------------------------===//
+
+// Parse misexpect tolerance argument value.
+// Valid option values are integers in the range [0, 100)
+inline Expected<Optional<uint64_t>> parseToleranceOption(StringRef Arg) {
+  int64_t Val;
+  if (Arg.getAsInteger(10, Val))
+    return llvm::createStringError(llvm::inconvertibleErrorCode(),
+                                   "Not an integer: %s", Arg.data());
+  return Val;
+}
+
+//===----------------------------------------------------------------------===//
 // Initialization.
 //===----------------------------------------------------------------------===//
 
 CompilerInvocationRefBase::CompilerInvocationRefBase()
     : LangOpts(new LangOptions()), TargetOpts(new TargetOptions()),
       DiagnosticOpts(new DiagnosticOptions()),
       HeaderSearchOpts(new HeaderSearchOptions()),
       PreprocessorOpts(new PreprocessorOptions()),
GenerateOptimizationRemark(Args, SA, OPT_Rpass_analysis_EQ, "pass-analysis",
                              Opts.OptimizationRemarkAnalysis);
 
   GenerateArg(Args, OPT_fdiagnostics_hotness_threshold_EQ,
               Opts.DiagnosticsHotnessThreshold
                   ? Twine(*Opts.DiagnosticsHotnessThreshold)
                   : "auto",
               SA);
 
+  GenerateArg(Args, OPT_fdiagnostics_misexpect_tolerance_EQ,
+              Twine(*Opts.DiagnosticsMisExpectTolerance), SA);
+
   for (StringRef Sanitizer : serializeSanitizerKinds(Opts.SanitizeRecover))
     GenerateArg(Args, OPT_fsanitize_recover_EQ, Sanitizer, SA);
 
   for (StringRef Sanitizer : serializeSanitizerKinds(Opts.SanitizeTrap))
     GenerateArg(Args, OPT_fsanitize_trap_EQ, Sanitizer, SA);
 
   if (!Opts.EmitVersionIdentMetadata)
     GenerateArg(Args, OPT_Qn, SA);
if (!ResultOrErr) {
       if ((!Opts.DiagnosticsHotnessThreshold.hasValue() ||
            Opts.DiagnosticsHotnessThreshold.getValue() > 0) &&
           !UsingProfile)
         Diags.Report(diag::warn_drv_diagnostics_hotness_requires_pgo)
             << "-fdiagnostics-hotness-threshold=";
     }
   }
 
+  if (auto *arg =
+          Args.getLastArg(options::OPT_fdiagnostics_misexpect_tolerance_EQ)) {
+    auto ResultOrErr = parseToleranceOption(arg->getValue());
+
+    if (!ResultOrErr) {
+      Diags.Report(diag::err_drv_invalid_diagnotics_misexpect_tolerance)
+          << "-fdiagnostics-misexpect-tolerance=";
+    } else {
+      Opts.DiagnosticsMisExpectTolerance = *ResultOrErr;
+      if ((!Opts.DiagnosticsMisExpectTolerance.hasValue() ||
+           Opts.DiagnosticsMisExpectTolerance.getValue() > 0) &&
+          !UsingProfile)
+        Diags.Report(diag::warn_drv_diagnostics_misexpect_requires_pgo)
+            << "-fdiagnostics-misexpect-tolerance=";
+    }
+  }
+
   // If the user requested to use a sample profile for PGO, then the
   // backend will need to track source location information so the profile
   // can be incorporated into the IR.
   if (UsingSampleProfile)
     NeedLocTracking = true;
 
   if (!Opts.StackUsageOutput.empty())
     NeedLocTracking = true;
bool CompilerInvocation::CreateFromArgsImpl(
   ParseHeaderSearchArgs(Res.getHeaderSearchOpts(), Args, Diags,
                         Res.getFileSystemOpts().WorkingDir);
 
   ParseLangArgs(LangOpts, Args, DashX, T, Res.getPreprocessorOpts().Includes,
                 Diags);
   if (Res.getFrontendOpts().ProgramAction == frontend::RewriteObjC)
     LangOpts.ObjCExceptions = 1;
 
+  for (auto Warning : Res.getDiagnosticOpts().Warnings) {
+    if (Warning == "misexpect" &&
+        !Diags.isIgnored(diag::warn_profile_data_misexpect, SourceLocation())) {
+      Res.getCodeGenOpts().MisExpect = true;
+    }
+  }
+
   if (LangOpts.CUDA) {
     // During CUDA device-side compilation, the aux triple is the
     // triple used for host compilation.
     if (LangOpts.CUDAIsDevice)
       Res.getTargetOpts().HostTriple = Res.getFrontendOpts().AuxTriple;
   }
 
   // Set the triple of the host for OpenMP device compile.

clang/test/Profile/Inputs/misexpect-branch-nonconst-expect-arg.proftext

+bar
+# Func Hash:
[phone]
+# Num Counters:
+2
+# Counter Values:
+200000
+2

clang/test/Profile/Inputs/misexpect-branch.proftext

+bar
+# Func Hash:
[phone]
+# Num Counters:
+2
+# Counter Values:
+200000
+180000
+
+fizz
+# Func Hash:
[phone]
+# Num Counters:
+2
+# Counter Values:
+200000
+18000

clang/test/Profile/Inputs/misexpect-switch-default-only.proftext

+main
+# Func Hash:
+79676873694057560
+# Num Counters:
+5
+# Counter Values:
+1
+20
+20000
+20000
+20000
+

clang/test/Profile/Inputs/misexpect-switch-default.proftext

+main
+# Func Hash:
+8734802134600123338
+# Num Counters:
+9
+# Counter Values:
+1
+20000
+20000
+4066
+11889
+0
+0
+4045
+0
+

clang/test/Profile/Inputs/misexpect-switch-nonconst.proftext

+main
+# Func Hash:
+3721743393642630379
+# Num Counters:
+10
+# Counter Values:
+1
+20
+20000
+20000
+1
+0
+0
+0
+19999
+0

clang/test/Profile/Inputs/misexpect-switch.proftext

+main
+# Func Hash:
+872687477373597607
+# Num Counters:
+9
+# Counter Values:
+1
+20
+20000
+20000
+3
+3
+1
+3
+19990
+
+random_sample
+# Func Hash:
+24
+# Num Counters:
+1
+# Counter Values:
+19990
+
+sum
+# Func Hash:
+24
+# Num Counters:
+1
+# Counter Values:
+3
+

clang/test/Profile/misexpect-branch-cold.c

+// Test that misexpect emits no warning when prediction is correct
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-branch.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify -Wmisexpect
+
+// expected-no-diagnostics
+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+
+int foo(int);
+int baz(int);
+int buzz();
+
+const int inner_loop = 100;
+const int outer_loop = 2000;
+
+int bar() {
+  int rando = buzz();
+  int x = 0;
+  if (unlikely(rando % (outer_loop * inner_loop) == 0)) {
+    x = baz(rando);
+  } else {
+    x = foo(50);
+  }
+  return x;
+}

clang/test/Profile/misexpect-branch-nonconst-expected-val.c

+// Test that misexpect emits no warning when condition is not a compile-time constant
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-branch-nonconst-expect-arg.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify -Wmisexpect
+
+// expected-no-diagnostics
+int foo(int);
+int baz(int);
+int buzz();
+
+const int inner_loop = 100;
+const int outer_loop = 2000;
+
+int bar() {
+  int rando = buzz();
+  int x = 0;
+  if (__builtin_expect(rando % (outer_loop * inner_loop) == 0, buzz())) {
+    x = baz(rando);
+  } else {
+    x = foo(50);
+  }
+  return x;
+}

clang/test/Profile/misexpect-branch-unpredictable.c

+// Test that misexpect emits no warning when prediction is correct
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-branch.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify -Wmisexpect
+
+// expected-no-diagnostics
+#define unpredictable(x) __builtin_unpredictable(!!(x))
+
+int foo(int);
+int baz(int);
+int buzz();
+
+const int inner_loop = 100;
+const int outer_loop = 2000;
+
+int bar() {
+  int rando = buzz();
+  int x = 0;
+  if (unpredictable(rando % (outer_loop * inner_loop) == 0)) {
+    x = baz(rando);
+  } else {
+    x = foo(50);
+  }
+  return x;
+}

clang/test/Profile/misexpect-branch.c

+// Test that misexpect detects mis-annotated branches
+
+// test diagnostics are issued when profiling data mis-matches annotations
+// RUN: llvm-profdata merge %S/Inputs/misexpect-branch.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify=imprecise -Wmisexpect
+// RUN: %clang_cc1 %s -O2 -o - -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify=exact -Wmisexpect -debug-info-kind=line-tables-only
+
+// there should be no diagnostics when the tolerance is sufficiently high, or when -Wmisexpect is not requested
+// RUN: %clang_cc1 %s -O2 -o - -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify=foo -fdiagnostics-misexpect-tolerance=10 -Wmisexpect -debug-info-kind=line-tables-only
+// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify=foo
+
+// Ensure we emit an error when we don't use pgo with tolerance threshold
+// RUN: %clang_cc1 %s -O2 -o - -emit-llvm  -fdiagnostics-misexpect-tolerance=10 -Wmisexpect -debug-info-kind=line-tables-only 2>&1 | FileCheck -check-prefix=NO_PGO %s
+
+// Test -fdiagnostics-misexpect-tolerance=  requires pgo profile
+// NO_PGO: '-fdiagnostics-misexpect-tolerance=' requires profile-guided optimization information
+
+// foo-no-diagnostics
+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+
+int foo(int);
+int baz(int);
+int buzz();
+
+const int inner_loop = 100;
+const int outer_loop = 2000;
+
+int bar() { // imprecise-warning-re {{Potential performance regression from use of __builtin_expect(): Annotation was correct on {{.+}}% ({{[0-9]+ / [0-9]+}}) of profiled executions.}}
+  int rando = buzz();
+  int x = 0;
+  if (likely(rando % (outer_loop * inner_loop) == 0)) { // exact-warning-re {{Potential performance regression from use of __builtin_expect(): Annotation was correct on {{.+}}% ({{[0-9]+ / [0-9]+}}) of profiled executions.}}
+    x = baz(rando);
+  } else {
+    x = foo(50);
+  }
+  return x;
+}
+
+int fizz() { // imprecise-warning-re {{Potential performance regression from use of __builtin_expect(): Annotation was correct on {{.+}}% ({{[0-9]+ / [0-9]+}}) of profiled executions.}}
+  int rando = buzz();
+  int x = 0;
+  if (unlikely(rando % (outer_loop * inner_loop) == 0)) { // exact-warning-re {{Potential performance regression from use of __builtin_expect(): Annotation was correct on {{.+}}% ({{[0-9]+ / [0-9]+}}) of profiled executions.}}
+    x = baz(rando);
+  } else {
+    x = foo(50);
+  }
+  return x;
+}

clang/test/Profile/misexpect-switch-default.c

+// Test that misexpect detects mis-annotated switch statements for default case
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-switch-default.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify -Wmisexpect -debug-info-kind=line-tables-only
+
+#define inner_loop 1000
+#define outer_loop 20
+#define arry_size 25
+
+int sum(int *buff, int size);
+int random_sample(int *buff, int size);
+int rand();
+void init_arry();
+
+int arry[arry_size] = {0};
+
+int main() {
+  init_arry();
+  int val = 0;
+  int j;
+  for (j = 0; j < outer_loop * inner_loop; ++j) {
+    unsigned condition = rand() % 5;
+    switch (__builtin_expect(condition, 6)) { // expected-warning-re {{Potential performance regression from use of __builtin_expect(): Annotation was correct on {{.+}}% ({{[0-9]+ / [0-9]+}}) of profiled executions.}}
+    case 0:
+      val += sum(arry, arry_size);
+      break;
+    case 1:
+    case 2:
+    case 3:
+      break;
+    case 4:
+      val += random_sample(arry, arry_size);
+      break;
+    default:
+      __builtin_unreachable();
+    } // end switch
+  }   // end outer_loop
+
+  return 0;
+}

clang/test/Profile/misexpect-switch-nonconst.c

+// Test that misexpect emits no warning when switch condition is non-const
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-switch-nonconst.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify
+
+// expected-no-diagnostics
+
+#define inner_loop 1000
+#define outer_loop 20
+#define arry_size 25
+
+int sum(int *buff, int size);
+int random_sample(int *buff, int size);
+int rand();
+void init_arry();
+
+int arry[arry_size] = {0};
+
+int main() {
+  init_arry();
+  int val = 0;
+
+  int j, k;
+  for (j = 0; j < outer_loop; ++j) {
+    for (k = 0; k < inner_loop; ++k) {
+      unsigned condition = rand() % 10000;
+      switch (__builtin_expect(condition, rand())) {
+      case 0:
+        val += sum(arry, arry_size);
+        break;
+      case 1:
+      case 2:
+      case 3:
+      case 4:
+        val += random_sample(arry, arry_size);
+        break;
+      default:
+        __builtin_unreachable();
+      } // end switch
+    }   // end inner_loop
+  }     // end outer_loop
+
+  return 0;
+}

clang/test/Profile/misexpect-switch-only-default-case.c

+// Test that misexpect emits no warning when there is only one switch case
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-switch-default-only.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify -Wmisexpect -debug-info-kind=line-tables-only
+
+// expected-no-diagnostics
+
+#define inner_loop 1000
+#define outer_loop 20
+#define arry_size 25
+
+int sum(int *buff, int size);
+int random_sample(int *buff, int size);
+int rand();
+void init_arry();
+
+int arry[arry_size] = {0};
+
+int main() {
+  init_arry();
+  int val = 0;
+
+  int j, k;
+  for (j = 0; j < outer_loop; ++j) {
+    for (k = 0; k < inner_loop; ++k) {
+      unsigned condition = rand() % 10000;
+      switch (__builtin_expect(condition, 0)) {
+      default:
+        val += random_sample(arry, arry_size);
+        break;
+      }; // end switch
+    }    // end inner_loop
+  }      // end outer_loop
+
+  return 0;
+}

clang/test/Profile/misexpect-switch.c

+// Test that misexpect detects mis-annotated switch statements
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-switch.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify -Wmisexpect -debug-info-kind=line-tables-only
+
+#define inner_loop 1000
+#define outer_loop 20
+#define arry_size 25
+
+int arry[arry_size] = {0};
+
+int rand();
+int sum(int *buff, int size);
+int random_sample(int *buff, int size);
+
+int main() {
+  int val = 0;
+
+  int j, k;
+  for (j = 0; j < outer_loop; ++j) {
+    for (k = 0; k < inner_loop; ++k) {
+      unsigned condition = rand() % 10000;
+      switch (__builtin_expect(condition, 0)) { // expected-warning-re {{Potential performance regression from use of __builtin_expect(): Annotation was correct on {{.+}}% ({{[0-9]+ / [0-9]+}}) of profiled executions.}}
+      case 0:
+        val += sum(arry, arry_size);
+        break;
+      case 1:
+      case 2:
+      case 3:
+        break;
+      default:
+        val += random_sample(arry, arry_size);
+        break;
+      } // end switch
+    }   // end inner_loop
+  }     // end outer_loop
+
+  return 0;
+}

llvm/docs/MisExpect.rst

+===================
+Misexpect
+===================
+.. contents::
+
+.. toctree::
+   :maxdepth: 1
+
+When developers use ``llvm.expect`` intrinsics, i.e., through use of
+``__builtin_expect(...)``, they are trying to communicate how their code is
+expected to behave at runtime to the optimizer. These annotations, however, can
+be incorrect for a variety of reasons: changes to the code base invalidate them
+silently, the developer mis-annotated them (e.g., using ``LIKELY`` instead of
+``UNLIKELY``), or perhaps they assumed something incorrectly when they wrote
+the annotation. Regardless of why, it is useful to detect these situations so
+that the optimizer can make more useful decisions about the code. MisExpect
+diagnostics are intended to help developers identify and address these
+situations, by comparing the use of the ``llvm.expect`` intrinsic to the ground
+truth provided by a profiling input.
+
+The MisExpect checks in the LLVM backend follow a simple procedure: if there is
+a mismatch between the branch weights collected during profiling and those
+supplied by an ``llvm.expect`` intrinsic, then it will emit a diagnostic
+message to the user.
+
+The most natural place to perform the verification is just prior to when
+branch weights are assigned to the target instruction in the form of
+branch weight metadata.
+
+There are 3 key places in the LLVM backend where branch weights are
+created and assigned based on profiling information or the use of the
+``llvm.expect`` intrinsic, and our implementation focuses on these
+places to perform the verification.
+
+We calculate the threshold for emitting MisExpect related diagnostics
+based on the values the compiler assigns to ``llvm.expect`` intrinsics,
+which can be set through the ``-likely-branch-weight`` and
+``-unlikely-branch-weight`` LLVM options. During verification, if the
+profile weights mismatch the calculated threshold, then we will emit a
+remark or warning detailing a potential performance regression. The
+diagnostic also reports the percentage of the time the annotation was
+correct during profiling to help developers reason about how to proceed.
+
+The diagnostics are also available in the form of optimization remarks,
+which can be serialized and processed through the ``opt-viewer.py``
+scripts in LLVM.
+
+.. option:: -pass-remarks=misexpect
+
+  Enables optimization remarks for misexpect when profiling data conflicts with
+  use of ``llvm.expect`` intrinsics.
+
+
+.. option:: -pgo-warn-misexpect
+
+  Enables misexpect warnings when profiling data conflicts with use of
+  ``llvm.expect`` intrinsics.
+
+LLVM supports 4 types of profile formats: Frontend, IR, CS-IR, and
+Sampling. MisExpect Diagnostics are compatible with all Profiling formats.
+
++----------------+--------------------------------------------------------------------------------------+
+| Profile Type   | Description                                                                          |
++================+======================================================================================+
+| Frontend       | Profiling instrumentation added during compilation by the frontend, i.e. ``clang``    |
++----------------+--------------------------------------------------------------------------------------+
+| IR             | Profiling instrumentation added during by the LLVM backend                           |
++----------------+--------------------------------------------------------------------------------------+
+| CS-IR          | Context Sensitive IR based profiles                                                  |
++----------------+--------------------------------------------------------------------------------------+
+| Sampling       | Profiles collected through sampling with external tools, such as ``perf`` on Linux   |
++----------------+--------------------------------------------------------------------------------------+
+

llvm/include/llvm/IR/DiagnosticInfo.h

enum DiagnosticKind {
   DK_MachineOptimizationRemarkAnalysis,
   DK_FirstMachineRemark = DK_MachineOptimizationRemark,
   DK_LastMachineRemark = DK_MachineOptimizationRemarkAnalysis,
   DK_MIRParser,
   DK_PGOProfile,
   DK_Unsupported,
   DK_SrcMgr,
   DK_DontCall,
+  DK_MisExpect,
   DK_FirstPluginKind // Must be last value to work with
                      // getNextAvailablePluginDiagnosticKind
 };
 
 /// 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
static bool classof(const DiagnosticInfo *DI) {
     return DI->getKind() == DK_Unsupported;
   }
 
   const Twine &getMessage() const { return Msg; }
 
   void print(DiagnosticPrinter &DP) const override;
 };
 
+/// Diagnostic information for MisExpect analysis.
+class DiagnosticInfoMisExpect : public DiagnosticInfoWithLocationBase {
+public:
+  DiagnosticInfoMisExpect(const Instruction *Inst, Twine &Msg);
+
+  /// \see DiagnosticInfo::print.
+  void print(DiagnosticPrinter &DP) const override;
+
+  static bool classof(const DiagnosticInfo *DI) {
+    return DI->getKind() == DK_MisExpect;
+  }
+
+  const Twine &getMsg() const { return Msg; }
+
+private:
+  /// Message to report.
+  const Twine &Msg;
+};
+
 static DiagnosticSeverity getDiagnosticSeverity(SourceMgr::DiagKind DK) {
   switch (DK) {
   case llvm::SourceMgr::DK_Error:
     return DS_Error;
     break;
   case llvm::SourceMgr::DK_Warning:
     return DS_Warning;
     break;

llvm/include/llvm/IR/LLVMContext.h

#undef LLVM_FIXED_MD_KIND
 
   /// Return if a code hotness metric should be included in optimization
   /// diagnostics.
   bool getDiagnosticsHotnessRequested() const;
   /// Set if a code hotness metric should be included in optimization
   /// diagnostics.
   void setDiagnosticsHotnessRequested(bool Requested);
 
+  bool getMisExpectWarningRequested() const;
+  void setMisExpectWarningRequested(bool Requested);
+  void setDiagnosticsMisExpectTolerance(Optional<uint64_t> Tolerance);
+  uint64_t getDiagnosticsMisExpectTolerance() const;
+
   /// Return the minimum hotness value a diagnostic would need in order
   /// to be included in optimization diagnostics.
   ///
   /// Three possible return values:
   /// 0            - threshold is disabled. Everything will be printed out.
   /// positive int - threshold is set.
   /// UINT64_MAX   - threshold is not yet set, and needs to be synced from
   ///                profile summary. Note that in case of missing profile

llvm/include/llvm/Target/TargetOptions.h

TargetOptions()
           ExplicitEmulatedTLS(false), EnableIPRA(false),
           EmitStackSizeSection(false), EnableMachineOutliner(false),
           EnableMachineFunctionSplitter(false), SupportsDefaultOutlining(false),
           EmitAddrsig(false), EmitCallSiteInfo(false),
           SupportsDebugEntryValues(false), EnableDebugEntryValues(false),
           ValueTrackingVariableLocations(false), ForceDwarfFrameSection(false),
           XRayOmitFunctionIndex(false), DebugStrictDwarf(false),
           Hotpatch(false), PPCGenScalarMASSEntries(false), JMCInstrument(false),
+          MisExpect(false),
           FPDenormalMode(DenormalMode::IEEE, DenormalMode::IEEE) {}
 
     /// DisableFramePointerElim - This returns true if frame pointer elimination
     /// optimization should be disabled for the given machine function.
     bool DisableFramePointerElim(const MachineFunction &MF) const;
 
     /// If greater than 0, override the default value of
     /// MCAsmInfo::BinutilsVersion.
public:
     unsigned Hotpatch : 1;
 
     /// Enables scalar MASS conversions
     unsigned PPCGenScalarMASSEntries : 1;
 
     /// Enable JustMyCode instrumentation.
     unsigned JMCInstrument : 1;
 
+    /// When set to true, enable MisExpect Diagnostics
+    /// By default, it is set to false
+    unsigned MisExpect : 1;
+
     /// Name of the stack usage file (i.e., .su file) if user passes
     /// -fstack-usage. If empty, it can be implied that -fstack-usage is not
     /// passed on the command line.
     std::string StackUsageOutput;
 
     /// If greater than 0, override TargetLoweringBase::PrefLoopAlignment.
     unsigned LoopAlignment = 0;
 

llvm/include/llvm/Transforms/Utils/MisExpect.h

+//===--- MisExpect.h - Check the use of llvm.expect with PGO data ---------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This contains code to emit diagnostic messages for potentially incorrect
+// usage of the llvm.expect intrinsic. This utility extracts the threshold
+// values from metadata associated with the instrumented Branch or Switch
+// instruction. The threshold values are then used to determine if a diagnostic
+// should be emitted.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+
+namespace llvm {
+namespace misexpect {
+
+/// checkBackendInstrumentation - compares PGO counters to the thresholds used
+/// for llvm.expect and warns if the PGO counters are outside of the expected
+/// range. It extracts the expected weights from the MD_prof weights attatched
+/// to the instruction, which are are assumed to come from lowered llvm.expect
+/// intrinsics. The RealWeights parameter and the extracted expected weights are
+/// then passed to verifyMisexpect() for verification
+///
+/// \param I The Instruction being checked
+/// \param RealWeights A vector of profile weights for each target block
+void checkBackendInstrumentation(Instruction &I,
+                                 const llvm::ArrayRef<uint32_t> RealWeights);
+
+/// checkFrontendInstrumentation - compares PGO counters to the thresholds used
+/// for llvm.expect and warns if the PGO counters are outside of the expected
+/// range. It extracts the expected weights from the MD_prof weights attatched
+/// to the instruction, which are are assumed to come from profiling data
+/// attached by the frontend prior to llvm.expect intrinsic lowering. The
+/// ExpectedWeights parameter and the extracted real weights are then passed to
+/// verifyMisexpect() for verification
+///
+/// \param I The Instruction being checked
+/// \param ExpectedWeights A vector of the expected weights for each target
+/// block, this determines the threshold values used when emiting diagnostics
+void checkFrontendInstrumentation(Instruction &I,
+                                  const ArrayRef<uint32_t> ExpectedWeights);
+
+/// veryifyMisExpect - compares RealWeights to the thresholds used
+/// for llvm.expect and warns if the PGO counters are outside of the expected
+/// range.
+///
+/// \param I The Instruction being checked
+/// \param RealWeights A vector of profile weights from the profile data
+/// \param ExpectedWeights A vector of the weights attatch by llvm.expect
+void verifyMisExpect(Instruction &I, ArrayRef<uint32_t> RealWeights,
+                     const ArrayRef<uint32_t> ExpectedWeights);
+
+/// checkExpectAnnotations - compares PGO counters to the thresholds used
+/// for llvm.expect and warns if the PGO counters are outside of the expected
+/// range. It extracts the expected weights from the MD_prof weights attatched
+/// to the instruction, which are are assumed to come from lowered llvm.expect
+/// intrinsics. The RealWeights parameter and the extracted expected weights are
+/// then passed to verifyMisexpect() for verification. It is a thin wrapper
+/// around the checkFrontendInstrumentation and checkBackendInstrumentation APIs
+///
+/// \param I The Instruction being checked
+/// \param RealWeights A vector of profile weights for each target block
+/// \param IsBackend A boolean describing if this is Frontend instrumentation
+void checkExpectAnnotations(Instruction &I,
+                            const ArrayRef<uint32_t> ExistingWeights,
+                            bool IsFrontend);
+
+} // namespace misexpect
+} // namespace llvm

llvm/lib/IR/DiagnosticInfo.cpp

std::string DiagnosticInfoOptimizationBase::getMsg() const {
   for (const DiagnosticInfoOptimizationBase::Argument &Arg :
        make_range(Args.begin(), FirstExtraArgIndex == -1
                                     ? Args.end()
                                     : Args.begin() + FirstExtraArgIndex))
     OS << Arg.Val;
   return OS.str();
 }
 
+DiagnosticInfoMisExpect::DiagnosticInfoMisExpect(const Instruction *Inst,
+                                                 Twine &Msg)
+    : DiagnosticInfoWithLocationBase(DK_MisExpect, DS_Warning,
+                                     *Inst->getParent()->getParent(),
+                                     Inst->getDebugLoc()),
+      Msg(Msg) {}
+
+void DiagnosticInfoMisExpect::print(DiagnosticPrinter &DP) const {
+  DP << getLocationStr() << ": " << getMsg();
+}
+
 void OptimizationRemarkAnalysisFPCommute::anchor() {}
 void OptimizationRemarkAnalysisAliasing::anchor() {}
 
 void llvm::diagnoseDontCall(const CallInst &CI) {
   auto *F = CI.getCalledFunction();
   if (!F)
     return;
 

llvm/lib/IR/LLVMContext.cpp

 }
 bool LLVMContext::getDiagnosticsHotnessRequested() const {
   return pImpl->DiagnosticsHotnessRequested;
 }
 
 void LLVMContext::setDiagnosticsHotnessThreshold(Optional<uint64_t> Threshold) {
   pImpl->DiagnosticsHotnessThreshold = Threshold;
 }
-
+void LLVMContext::setMisExpectWarningRequested(bool Requested) {
+  pImpl->MisExpectWarningRequested = Requested;
+}
+bool LLVMContext::getMisExpectWarningRequested() const {
+  return pImpl->MisExpectWarningRequested;
+}
 uint64_t LLVMContext::getDiagnosticsHotnessThreshold() const {
   return pImpl->DiagnosticsHotnessThreshold.getValueOr(UINT64_MAX);
 }
+void LLVMContext::setDiagnosticsMisExpectTolerance(
+    Optional<uint64_t> Tolerance) {
+  pImpl->DiagnosticsMisExpectTolerance = Tolerance;
+}
+uint64_t LLVMContext::getDiagnosticsMisExpectTolerance() const {
+  return pImpl->DiagnosticsMisExpectTolerance.getValueOr(0);
+}
 
 bool LLVMContext::isDiagnosticsHotnessThresholdSetFromPSI() const {
   return !pImpl->DiagnosticsHotnessThreshold.hasValue();
 }
 
 remarks::RemarkStreamer *LLVMContext::getMainRemarkStreamer() {
   return pImpl->MainRemarkStreamer.get();
 }

llvm/lib/IR/LLVMContextImpl.h

public:
   /// State 1 and 2 are considered as terminal states. State transition is
   /// only allowed from 3 to 2, when the threshold is first synced with profile
   /// summary. This ensures that the threshold is set only once and stays
   /// constant.
   ///
   /// If threshold option is not specified, it is disabled (0) by default.
   Optional<uint64_t> DiagnosticsHotnessThreshold = 0;
 
+  /// The percentage of difference between profiling branch weights and
+  // llvm.expect branch weights to tolerate when emiting MisExpect diagnostics
+  Optional<uint64_t> DiagnosticsMisExpectTolerance = 0;
+  bool MisExpectWarningRequested = false;
+
   /// The specialized remark streamer used by LLVM's OptimizationRemarkEmitter.
   std::unique_ptr<LLVMRemarkStreamer> LLVMRS;
 
   LLVMContext::YieldCallbackTy YieldCallback = nullptr;
   void *YieldOpaqueHandle = nullptr;
 
   using IntMapTy =
       DenseMap<APInt, std::unique_ptr<ConstantInt>, DenseMapAPIntKeyInfo>;

llvm/lib/Transforms/IPO/SampleProfile.cpp

 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/ProfiledCallGraph.h"
 #include "llvm/Transforms/IPO/SampleContextTracker.h"
 #include "llvm/Transforms/IPO/SampleProfileProbe.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Utils/CallPromotionUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/MisExpect.h"
+#include "llvm/Transforms/Utils/SampleProfileInference.h"
 #include "llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h"
 #include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <functional>
 #include <limits>
 #include <map>
for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) {
       if (Weight != 0) {
         if (Weight > MaxWeight) {
           MaxWeight = Weight;
           MaxDestInst = Succ->getFirstNonPHIOrDbgOrLifetime();
         }
       }
     }
 
+    misexpect::checkExpectAnnotations(*TI, Weights, /*IsFrontend=*/false);
+
     uint64_t TempWeight;
     // Only set weights if there is at least one non-zero weight.
     // In any other case, let the analyzer set weights.
     // Do not set weights if the weights are present unless under
     // OverwriteExistingWeights. In ThinLTO, the profile annotation is done
     // twice. If the first annotation already set the weights, the second pass
     // does not need to set it. With OverwriteExistingWeights, Blocks with zero
     // weight should have their existing metadata (possibly annotated by LTO

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

 #include "llvm/Support/DOTGraphTraits.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/GraphWriter.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/MisExpect.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <memory>
 #include <numeric>
 #include <string>
 #include <unordered_map>
void llvm::setProfMetadata(Module *M, Instruction *TI,
   for (const auto &ECI : EdgeCounts)
     Weights.push_back(scaleBranchCount(ECI, Scale));
 
   LLVM_DEBUG(dbgs() << "Weight is: "; for (const auto &W
                                            : Weights) {
     dbgs() << W << " ";
   } dbgs() << "\n";);
 
+  misexpect::checkExpectAnnotations(*TI, Weights, /*IsFrontend=*/false);
+
   TI->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
   if (EmitBranchProbability) {
     std::string BrCondStr = getBranchCondString(TI);
     if (BrCondStr.empty())
       return;
 
     uint64_t WSum =
         std::accumulate(Weights.begin(), Weights.end(), (uint64_t)0,

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/MisExpect.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "lower-expect-intrinsic"
 
 STATISTIC(ExpectIntrinsicsHandled,
           "Number of 'expect' intrinsic instructions handled");
 
static bool handleSwitchExpect(SwitchInst &SI) {
   std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) =
       getBranchWeight(Fn->getIntrinsicID(), CI, n + 1);
 
   SmallVector<uint32_t, 16> Weights(n + 1, UnlikelyBranchWeightVal);
 
   uint64_t Index = (Case == *SI.case_default()) ? 0 : Case.getCaseIndex() + 1;
   Weights[Index] = LikelyBranchWeightVal;
 
+  misexpect::checkExpectAnnotations(SI, Weights, /*IsFrontend=*/true);
+
   SI.setCondition(ArgValue);
 
   SI.setMetadata(LLVMContext::MD_prof,
                  MDBuilder(CI->getContext()).createBranchWeights(Weights));
 
   return true;
 }
 
 /// Handler for PHINodes that define the value argument to an
 /// @llvm.expect call.
 ///
 /// If the operand of the phi has a constant value and it 'contradicts'
 /// with the expected value of phi def, then the corresponding incoming
 /// edge of the phi is unlikely to be taken. Using that information,
template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) {
 
   MDBuilder MDB(CI->getContext());
   MDNode *Node;
 
   uint32_t LikelyBranchWeightVal, UnlikelyBranchWeightVal;
   std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) =
       getBranchWeight(Fn->getIntrinsicID(), CI, 2);
 
+  SmallVector<uint32_t, 4> ExpectedWeights;
   if ((ExpectedValue->getZExtValue() == ValueComparedTo) ==
       (Predicate == CmpInst::ICMP_EQ)) {
     Node =
         MDB.createBranchWeights(LikelyBranchWeightVal, UnlikelyBranchWeightVal);
+    ExpectedWeights = {LikelyBranchWeightVal, UnlikelyBranchWeightVal};
   } else {
     Node =
         MDB.createBranchWeights(UnlikelyBranchWeightVal, LikelyBranchWeightVal);
+    ExpectedWeights = {UnlikelyBranchWeightVal, LikelyBranchWeightVal};
   }
 
   if (CmpI)
     CmpI->setOperand(0, ArgValue);
   else
     BSI.setCondition(ArgValue);
 
+  misexpect::checkFrontendInstrumentation(BSI, ExpectedWeights);
+
   BSI.setMetadata(LLVMContext::MD_prof, Node);
 
   return true;
 }
 
 static bool handleBranchExpect(BranchInst &BI) {
   if (BI.isUnconditional())
     return false;

 public:
   static char ID;
   LowerExpectIntrinsic() : FunctionPass(ID) {
     initializeLowerExpectIntrinsicPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); }
 };
-}
+} // namespace
 
 char LowerExpectIntrinsic::ID = 0;
 INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect",
                 "Lower 'expect' Intrinsics", false, false)
 
 FunctionPass *llvm::createLowerExpectIntrinsicPass() {
   return new LowerExpectIntrinsic();
 }

llvm/lib/Transforms/Utils/CMakeLists.txt

add_llvm_component_library(LLVMTransformUtils
   LowerInvoke.cpp
   LowerMemIntrinsics.cpp
   LowerSwitch.cpp
   MatrixUtils.cpp
   MemoryOpRemark.cpp
   MemoryTaggingSupport.cpp
   Mem2Reg.cpp
   MetaRenamer.cpp
+  MisExpect.cpp
   ModuleUtils.cpp
   NameAnonGlobals.cpp
   PredicateInfo.cpp
   PromoteMemoryToRegister.cpp
   RelLookupTableConverter.cpp
   ScalarEvolutionExpander.cpp
   SCCPSolver.cpp
   StripGCRelocates.cpp

llvm/lib/Transforms/Utils/MisExpect.cpp

+//===--- MisExpect.cpp - Check the use of llvm.expect with PGO data -------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This contains code to emit warnings for potentially incorrect usage of the
+// llvm.expect intrinsic. This utility extracts the threshold values from
+// metadata associated with the instrumented Branch or Switch instruction. The
+// threshold values are then used to determine if a warning should be emmited.
+//
+// MisExpect's implementation relies on two assumptions about how branch weights
+// are managed in LLVM.
+//
+// 1) Frontend profiling weights are always in place before llvm.expect is
+// lowered in LowerExpectIntrinsic.cpp. Frontend based instrumentation therefore
+// needs to extract the branch weights and then compare them to the weights
+// being added by the llvm.expect intrinsic lowering.
+//
+// 2) Sampling and IR based profiles will *only* have branch weight metadata
+// before profiling data is consulted if they are from a lowered llvm.expect
+// intrinsic. These profiles thus always extract the expected weights and then
+// compare them to the weights collected during profiling to determine if a
+// diagnostic message is warranted.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/MisExpect.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/Support/BranchProbability.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FormatVariadic.h"
+#include <cstdint>
+#include <functional>
+#include <numeric>
+
+#define DEBUG_TYPE "misexpect"
+
+using namespace llvm;
+using namespace misexpect;
+
+namespace llvm {
+
+// Command line option to enable/disable the warning when profile data suggests
+// a mismatch with the use of the llvm.expect intrinsic
+static cl::opt<bool> PGOWarnMisExpect(
+    "pgo-warn-misexpect", cl::init(false), cl::Hidden,
+    cl::desc("Use this option to turn on/off "
+             "warnings about incorrect usage of llvm.expect intrinsics."));
+
+static cl::opt<unsigned> MisExpectTolerance(
+    "misexpect-tolerance", cl::init(0),
+    cl::desc("Prevents emiting diagnostics when profile counts are "
+             "within N% of the threshold.."));
+
+} // namespace llvm
+
+namespace {
+
+bool isMisExpectDiagEnabled(LLVMContext &Ctx) {
+  return PGOWarnMisExpect || Ctx.getMisExpectWarningRequested();
+}
+
+uint64_t getMisExpectTolerance(LLVMContext &Ctx) {
+  return std::max(static_cast<uint64_t>(MisExpectTolerance),
+                  Ctx.getDiagnosticsMisExpectTolerance());
+}
+
+Instruction *getInstCondition(Instruction *I) {
+  assert(I != nullptr && "MisExpect target Instruction cannot be nullptr");
+  Instruction *Ret = nullptr;
+  if (auto *B = dyn_cast<BranchInst>(I)) {
+    Ret = dyn_cast<Instruction>(B->getCondition());
+  }
+  // TODO: Find a way to resolve condition location for switches
+  // Using the condition of the switch seems to often resolve to an earlier
+  // point in the program, i.e. the calculation of the switch condition, rather
+  // than the switch's location in the source code. Thus, we should use the
+  // instruction to get source code locations rather than the condition to
+  // improve diagnostic output, such as the caret. If the same problem exists
+  // for branch instructions, then we should remove this function and directly
+  // use the instruction
+  //
+  else if (auto *S = dyn_cast<SwitchInst>(I)) {
+    Ret = dyn_cast<Instruction>(S->getCondition());
+  }
+  return Ret ? Ret : I;
+}
+
+void emitMisexpectDiagnostic(Instruction *I, LLVMContext &Ctx,
+                             uint64_t ProfCount, uint64_t TotalCount) {
+  double PercentageCorrect = (double)ProfCount / TotalCount;
+  auto PerString =
+      formatv("{0:P} ({1} / {2})", PercentageCorrect, ProfCount, TotalCount);
+  auto RemStr = formatv(
+      "Potential performance regression from use of the llvm.expect intrinsic: "
+      "Annotation was correct on {0} of profiled executions.",
+      PerString);
+  Twine Msg(PerString);
+  Instruction *Cond = getInstCondition(I);
+  if (isMisExpectDiagEnabled(Ctx))
+    Ctx.diagnose(DiagnosticInfoMisExpect(Cond, Msg));
+  OptimizationRemarkEmitter ORE(I->getParent()->getParent());
+  ORE.emit(OptimizationRemark(DEBUG_TYPE, "misexpect", Cond) << RemStr.str());
+}
+
+} // namespace
+
+namespace llvm {
+namespace misexpect {
+
+// Helper function to extract branch weights into a vector
+Optional<SmallVector<uint32_t, 4>> extractWeights(Instruction *I,
+                                                  LLVMContext &Ctx) {
+  assert(I && "MisExpect::extractWeights given invalid pointer");
+
+  auto *ProfileData = I->getMetadata(LLVMContext::MD_prof);
+  if (!ProfileData)
+    return None;
+
+  unsigned NOps = ProfileData->getNumOperands();
+  if (NOps < 3)
+    return None;
+
+  auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(0));
+  if (!ProfDataName || !ProfDataName->getString().equals("branch_weights"))
+    return None;
+
+  SmallVector<uint32_t, 4> Weights(NOps - 1);
+  for (unsigned Idx = 1; Idx < NOps; Idx++) {
+    ConstantInt *Value =
+        mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(Idx));
+    uint32_t V = Value->getZExtValue();
+    Weights[Idx - 1] = V;
+  }
+
+  return Weights;
+}
+
+void verifyMisExpect(Instruction &I, ArrayRef<uint32_t> RealWeights,
+                     ArrayRef<uint32_t> ExpectedWeights) {
+  // To determine if we emit a diagnostic, we need to compare the branch weights
+  // from the profile to those added by the llvm.expect intrinsic.
+  // So first, we extract the "likely" and "unlikely" weights from
+  // ExpectedWeights And determine the correct weight in the profile to compare
+  // against.
+  uint64_t LikelyBranchWeight = 0,
+           UnlikelyBranchWeight = std::numeric_limits<uint32_t>::max();
+  size_t MaxIndex = 0;
+  for (size_t Idx = 0, End = ExpectedWeights.size(); Idx < End; Idx++) {
+    uint32_t V = ExpectedWeights[Idx];
+    if (LikelyBranchWeight < V) {
+      LikelyBranchWeight = V;
+      MaxIndex = Idx;
+    }
+    if (UnlikelyBranchWeight > V) {
+      UnlikelyBranchWeight = V;
+    }
+  }
+
+  const uint64_t ProfiledWeight = RealWeights[MaxIndex];
+  const uint64_t RealWeightsTotal =
+      std::accumulate(RealWeights.begin(), RealWeights.end(), (uint64_t)0,
+                      std::plus<uint64_t>());
+  const uint64_t NumUnlikelyTargets = RealWeights.size() - 1;
+
+  const uint64_t TotalBranchWeight =
+      LikelyBranchWeight + (UnlikelyBranchWeight * NumUnlikelyTargets);
+
+  // To determine our threshold value we need to obtain the branch probability
+  // for the weights added by llvm.expect and use that proportion to calculate
+  // our threshold based on the collected profile data.
+  const llvm::BranchProbability LikelyProbablilty(LikelyBranchWeight,
+                                                  TotalBranchWeight);
+  uint64_t ScaledThreshold = LikelyProbablilty.scale(RealWeightsTotal);
+
+  // clamp tolerance range to [0, 100)
+  auto Tolerance = getMisExpectTolerance(I.getContext());
+  if (Tolerance < 0)
+    Tolerance = 0;
+  else if (MisExpectTolerance > 99)
+    Tolerance = 99;
+
+  // Allow users to relax checking by N%  i.e., if they use a 5% tolerance,
+  // then we check against 0.95*ScaledThreshold
+  if (Tolerance > 0)
+    ScaledThreshold *= (1.0 - Tolerance / 100.0);
+
+  // When the profile weight is below the threshold, we emit the diagnostic
+  if (ProfiledWeight < ScaledThreshold)
+    emitMisexpectDiagnostic(&I, I.getContext(), ProfiledWeight,
+                            RealWeightsTotal);
+}
+
+void checkBackendInstrumentation(Instruction &I,
+                                 const ArrayRef<uint32_t> RealWeights) {
+  auto ExpectedWeightsOpt = extractWeights(&I, I.getContext());
+  if (!ExpectedWeightsOpt.hasValue())
+    return;
+  auto ExpectedWeights = ExpectedWeightsOpt.getValue();
+  verifyMisExpect(I, RealWeights, ExpectedWeights);
+}
+
+void checkFrontendInstrumentation(Instruction &I,
+                                  const ArrayRef<uint32_t> ExpectedWeights) {
+  auto RealWeightsOpt = extractWeights(&I, I.getContext());
+  if (!RealWeightsOpt.hasValue())
+    return;
+  auto RealWeights = RealWeightsOpt.getValue();
+  verifyMisExpect(I, RealWeights, ExpectedWeights);
+}
+
+void checkExpectAnnotations(Instruction &I,
+                            const ArrayRef<uint32_t> ExistingWeights,
+                            bool IsFrontendInstr) {
+  if (IsFrontendInstr) {
+    checkFrontendInstrumentation(I, ExistingWeights);
+  } else {
+    checkBackendInstrumentation(I, ExistingWeights);
+  }
+}
+
+} // namespace misexpect
+} // namespace llvm
+#undef DEBUG_TYPE

llvm/test/Transforms/PGOProfile/Inputs/misexpect-branch-correct.proftext

+# IR level Instrumentation Flag
+:ir
+bar
+# Func Hash:
+146835647075900052
+# Num Counters:
+2
+# Counter Values:
+200000
+0
+
+baz
+# Func Hash:
[phone]
+# Num Counters:
+1
+# Counter Values:
+399668
+
+foo
+# Func Hash:
[phone]
+# Num Counters:
+2
+# Counter Values:
[phone]
+1600332
+
+main
+# Func Hash:
[phone]
+# Num Counters:
+3
+# Counter Values:
+2000000
+2000
+1
+

llvm/test/Transforms/PGOProfile/Inputs/misexpect-branch-threshold.proftext

+# IR level Instrumentation Flag
+:ir
+bar
+# Func Hash:
+146835647075900052
+# Num Counters:
+2
+# Counter Values:
+100
+10
+
+baz
+# Func Hash:
[phone]
+# Num Counters:
+1
+# Counter Values:
+399668
+
+foo
+# Func Hash:
[phone]
+# Num Counters:
+2
+# Counter Values:
[phone]
+1600332
+
+main
+# Func Hash:
[phone]
+# Num Counters:
+3
+# Counter Values:
+2000000
+2000
+1
+

llvm/test/Transforms/PGOProfile/Inputs/misexpect-branch.proftext

+# IR level Instrumentation Flag
+:ir
+bar
+# Func Hash:
+146835647075900052
+# Num Counters:
+2
+# Counter Values:
+399668
+1600332
+
+baz
+# Func Hash:
[phone]
+# Num Counters:
+1
+# Counter Values:
+399668
+
+foo
+# Func Hash:
[phone]
+# Num Counters:
+2
+# Counter Values:
[phone]
+1600332
+
+main
+# Func Hash:
[phone]
+# Num Counters:
+3
+# Counter Values:
+2000000
+2000
+1
+

llvm/test/Transforms/PGOProfile/Inputs/misexpect-switch-correct.proftext

+# IR level Instrumentation Flag
+:ir
+main
+# Func Hash:
+391331300939170156
+# Num Counters:
+7
+# Counter Values:
+0
+0
+20000
+0
+0
+1
+0

llvm/test/Transforms/PGOProfile/Inputs/misexpect-switch.proftext

+# IR level Instrumentation Flag
+:ir
+main
+# Func Hash:
+391331300939170156
+# Num Counters:
+7
+# Counter Values:
+3973
+3970
+0
+11889
+8111
+1
+0

llvm/test/Transforms/PGOProfile/misexpect-branch-correct.ll

+; Test misexpect checks do not issue diagnostics when profiling weights and
+; branch weights added by llvm.expect agree
+
+; RUN: llvm-profdata merge %S/Inputs/misexpect-branch-correct.proftext -o %t.profdata
+
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -pass-remarks=misexpect -S  2>&1 | FileCheck %s
+
+; CHECK-NOT: warning: {{.*}}
+; CHECK-NOT: remark: {{.*}}
+; CHECK: !{!"branch_weights", i32 0, i32 200000}
+
+
+; ModuleID = 'misexpect-branch-correct.c'
+source_filename = "misexpect-branch-correct.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@inner_loop = constant i32 100, align 4
+@outer_loop = constant i32 2000, align 4
+
+; Function Attrs: nounwind
+define i32 @bar() #0 {
+entry:
+  %rando = alloca i32, align 4
+  %x = alloca i32, align 4
+  %0 = bitcast i32* %rando to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #4
+  %call = call i32 (...) @buzz()
+  store i32 %call, i32* %rando, align 4, !tbaa !3
+  %1 = bitcast i32* %x to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %1) #4
+  store i32 0, i32* %x, align 4, !tbaa !3
+  %2 = load i32, i32* %rando, align 4, !tbaa !3
+  %rem = srem i32 %2, 200000
+  %cmp = icmp eq i32 %rem, 0
+  %lnot = xor i1 %cmp, true
+  %lnot1 = xor i1 %lnot, true
+  %lnot.ext = zext i1 %lnot1 to i32
+  %conv = sext i32 %lnot.ext to i64
+  %expval = call i64 @llvm.expect.i64(i64 %conv, i64 0)
+  %tobool = icmp ne i64 %expval, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %3 = load i32, i32* %rando, align 4, !tbaa !3
+  %call2 = call i32 @baz(i32 %3)
+  store i32 %call2, i32* %x, align 4, !tbaa !3
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %call3 = call i32 @foo(i32 50)
+  store i32 %call3, i32* %x, align 4, !tbaa !3
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %4 = load i32, i32* %x, align 4, !tbaa !3
+  %5 = bitcast i32* %x to i8*
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %5) #4
+  %6 = bitcast i32* %rando to i8*
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %6) #4
+  ret i32 %4
+}
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
+
+declare i32 @buzz(...) #2
+
+; Function Attrs: nounwind readnone willreturn
+declare i64 @llvm.expect.i64(i64, i64) #3
+
+declare i32 @baz(i32) #2
+
+declare i32 @foo(i32) #2
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+cx8,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind willreturn }
+attributes #2 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+cx8,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { nounwind readnone willreturn }
+attributes #4 = { nounwind }
+
+!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
+
+!0 = !{i32 2, !"Debug Info Version", i32 3}
+!1 = !{i32 1, !"wchar_size", i32 4}
+!2 = !{!"clang version 10.0.0 (c20270bfffc9d6965219de339d66c61e9fe7d82d)"}
+!3 = !{!4, !4, i64 0}
+!4 = !{!"int", !5, i64 0}
+!5 = !{!"omnipotent char", !6, i64 0}
+!6 = !{!"Simple C/C++ TBAA"}

llvm/test/Transforms/PGOProfile/misexpect-branch-stripped.ll

+; Test that misexpect diagnostics handle stripped debug info gracefully
+
+; RUN: llvm-profdata merge %S/Inputs/misexpect-branch.proftext -o %t.profdata
+
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -S 2>&1 | FileCheck %s --check-prefix=WARNING
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pass-remarks=misexpect -S 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -pass-remarks=misexpect -S 2>&1 | FileCheck %s --check-prefix=BOTH
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -S 2>&1 | FileCheck %s --check-prefix=DISABLED
+
+; WARNING-DAG: warning: <unknown>:0:0: 19.98%
+; WARNING-NOT: remark: <unknown>:0:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 19.98% (399668 / 2000000) of profiled executions.
+
+; REMARK-NOT: warning: <unknown>:0:0: 19.98%
+; REMARK-DAG: remark: <unknown>:0:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 19.98% (399668 / 2000000) of profiled executions.
+
+; BOTH-DAG: warning: <unknown>:0:0: 19.98%
+; BOTH-DAG: remark: <unknown>:0:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 19.98% (399668 / 2000000) of profiled executions.
+
+; DISABLED-NOT: warning: <unknown>:0:0: 19.98%
+; DISABLED-NOT: remark: <unknown>:0:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 19.98% (399668 / 2000000) of profiled executions.
+
+
+; ModuleID = 'misexpect-branch.c'
+source_filename = "misexpect-branch.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@inner_loop = constant i32 100, align 4
+@outer_loop = constant i32 2000, align 4
+
+; Function Attrs: nounwind
+define i32 @bar() #0 {
+entry:
+  %rando = alloca i32, align 4
+  %x = alloca i32, align 4
+  %0 = bitcast i32* %rando to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #4
+  %call = call i32 (...) @buzz()
+  store i32 %call, i32* %rando, align 4, !tbaa !3
+  %1 = bitcast i32* %x to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %1) #4
+  store i32 0, i32* %x, align 4, !tbaa !3
+  %2 = load i32, i32* %rando, align 4, !tbaa !3
+  %rem = srem i32 %2, 200000
+  %cmp = icmp eq i32 %rem, 0
+  %lnot = xor i1 %cmp, true
+  %lnot1 = xor i1 %lnot, true
+  %lnot.ext = zext i1 %lnot1 to i32
+  %conv = sext i32 %lnot.ext to i64
+  %expval = call i64 @llvm.expect.i64(i64 %conv, i64 1)
+  %tobool = icmp ne i64 %expval, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %3 = load i32, i32* %rando, align 4, !tbaa !3
+  %call2 = call i32 @baz(i32 %3)
+  store i32 %call2, i32* %x, align 4, !tbaa !3
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %call3 = call i32 @foo(i32 50)
+  store i32 %call3, i32* %x, align 4, !tbaa !3
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %4 = load i32, i32* %x, align 4, !tbaa !3
+  %5 = bitcast i32* %x to i8*
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %5) #4
+  %6 = bitcast i32* %rando to i8*
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %6) #4
+  ret i32 %4
+}
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
+
+declare i32 @buzz(...) #2
+
+; Function Attrs: nounwind readnone willreturn
+declare i64 @llvm.expect.i64(i64, i64) #3
+
+declare i32 @baz(i32) #2
+
+declare i32 @foo(i32) #2
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+cx8,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind willreturn }
+attributes #2 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+cx8,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { nounwind readnone willreturn }
+attributes #4 = { nounwind }
+
+!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
+
+!0 = !{i32 2, !"Debug Info Version", i32 3}
+!1 = !{i32 1, !"wchar_size", i32 4}
+!2 = !{!"clang version 10.0.0 (trunk c20270bfffc9d6965219de339d66c61e9fe7d82d)"}
+!3 = !{!4, !4, i64 0}
+!4 = !{!"int", !5, i64 0}
+!5 = !{!"omnipotent char", !6, i64 0}
+!6 = !{!"Simple C/C++ TBAA"}

llvm/test/Transforms/PGOProfile/misexpect-branch-unpredictable.ll

+; Test misexpect doesn't issue diagnostics when a branch is marked unpredictable
+
+; RUN: llvm-profdata merge %S/Inputs/misexpect-branch-correct.proftext -o %t.profdata
+
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -pass-remarks=misexpect -S  2>&1 | FileCheck %s
+
+; CHECK-NOT: warning: {{.*}}
+; CHECK-NOT: remark: {{.*}}
+
+
+; ModuleID = 'misexpect-branch-unpredictable.c'
+source_filename = "clang/test/Profile/misexpect-branch-unpredictable.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@inner_loop = constant i32 100, align 4
+@outer_loop = constant i32 2000, align 4
+
+; Function Attrs: nounwind
+define i32 @bar() #0 {
+entry:
+  %rando = alloca i32, align 4
+  %x = alloca i32, align 4
+  %0 = bitcast i32* %rando to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #3
+  %call = call i32 (...) @buzz()
+  store i32 %call, i32* %rando, align 4, !tbaa !2
+  %1 = bitcast i32* %x to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %1) #3
+  store i32 0, i32* %x, align 4, !tbaa !2
+  %2 = load i32, i32* %rando, align 4, !tbaa !2
+  %rem = srem i32 %2, 200000
+  %cmp = icmp eq i32 %rem, 0
+  %lnot = xor i1 %cmp, true
+  %lnot1 = xor i1 %lnot, true
+  %lnot.ext = zext i1 %lnot1 to i32
+  %conv = sext i32 %lnot.ext to i64
+  %tobool = icmp ne i64 %conv, 0
+  br i1 %tobool, label %if.then, label %if.else, !unpredictable !6
+
+if.then:                                          ; preds = %entry
+  %3 = load i32, i32* %rando, align 4, !tbaa !2
+  %call2 = call i32 @baz(i32 %3)
+  store i32 %call2, i32* %x, align 4, !tbaa !2
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %call3 = call i32 @foo(i32 50)
+  store i32 %call3, i32* %x, align 4, !tbaa !2
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %4 = load i32, i32* %x, align 4, !tbaa !2
+  %5 = bitcast i32* %x to i8*
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %5) #3
+  %6 = bitcast i32* %rando to i8*
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %6) #3
+  ret i32 %4
+}
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
+
+declare i32 @buzz(...) #2
+
+declare i32 @baz(i32) #2
+
+declare i32 @foo(i32) #2
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+cx8,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind willreturn }
+attributes #2 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+cx8,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { nounwind }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"Fuchsia clang version 10.0.0 (153b453014c94291c8c6cf6320b2f46df40f26f3) (based on LLVM 10.0.0svn)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}
+!6 = !{}

llvm/test/Transforms/PGOProfile/misexpect-branch.ll

+; Test that misexpect diagnostics are emtted when profile branch weights are
+; below the branch weights added by llvm.expect intrinsics
+
+; RUN: llvm-profdata merge %S/Inputs/misexpect-branch.proftext -o %t.profdata
+
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -S 2>&1 | FileCheck %s --check-prefix=WARNING
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pass-remarks=misexpect -S 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -pass-remarks=misexpect -S 2>&1 | FileCheck %s --check-prefix=BOTH
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -S 2>&1 | FileCheck %s --check-prefix=DISABLED
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -misexpect-tolerance=81 -pass-remarks=misexpect -S 2>&1 | FileCheck %s --check-prefix=THRESHOLD
+
+; WARNING-DAG: warning: misexpect-branch.c:22:0: 19.98%
+; WARNING-NOT: remark: misexpect-branch.c:22:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 19.98% (399668 / 2000000) of profiled executions.
+
+; REMARK-NOT: warning: misexpect-branch.c:22:0: 19.98%
+; REMARK-DAG: remark: misexpect-branch.c:22:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 19.98% (399668 / 2000000) of profiled executions.
+
+; BOTH-DAG: warning: misexpect-branch.c:22:0: 19.98%
+; BOTH-DAG: remark: misexpect-branch.c:22:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 19.98% (399668 / 2000000) of profiled executions.
+
+; DISABLED-NOT: warning: misexpect-branch.c:22:0: 19.98%
+; DISABLED-NOT: remark: misexpect-branch.c:22:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 19.98% (399668 / 2000000) of profiled executions.
+
+; THRESHOLD-NOT: warning: misexpect-branch.c:22:0: 19.98%
+; THRESHOLD-NOT: remark: misexpect-branch.c:22:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 19.98% (399668 / 2000000) of profiled executions.
+
+
+; ModuleID = 'misexpect-branch.c'
+source_filename = "misexpect-branch.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@inner_loop = constant i32 100, align 4
+@outer_loop = constant i32 2000, align 4
+
+; Function Attrs: nounwind
+define i32 @bar() #0 !dbg !6 {
+entry:
+  %rando = alloca i32, align 4
+  %x = alloca i32, align 4
+  %0 = bitcast i32* %rando to i8*, !dbg !9
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #4, !dbg !9
+  %call = call i32 (...) @buzz(), !dbg !9
+  store i32 %call, i32* %rando, align 4, !dbg !9, !tbaa !10
+  %1 = bitcast i32* %x to i8*, !dbg !14
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %1) #4, !dbg !14
+  store i32 0, i32* %x, align 4, !dbg !14, !tbaa !10
+  %2 = load i32, i32* %rando, align 4, !dbg !15, !tbaa !10
+  %rem = srem i32 %2, 200000, !dbg !15
+  %cmp = icmp eq i32 %rem, 0, !dbg !15
+  %lnot = xor i1 %cmp, true, !dbg !15
+  %lnot1 = xor i1 %lnot, true, !dbg !15
+  %lnot.ext = zext i1 %lnot1 to i32, !dbg !15
+  %conv = sext i32 %lnot.ext to i64, !dbg !15
+  %expval = call i64 @llvm.expect.i64(i64 %conv, i64 1), !dbg !15
+  %tobool = icmp ne i64 %expval, 0, !dbg !15
+  br i1 %tobool, label %if.then, label %if.else, !dbg !15
+
+if.then:                                          ; preds = %entry
+  %3 = load i32, i32* %rando, align 4, !dbg !16, !tbaa !10
+  %call2 = call i32 @baz(i32 %3), !dbg !16
+  store i32 %call2, i32* %x, align 4, !dbg !16, !tbaa !10
+  br label %if.end, !dbg !17
+
+if.else:                                          ; preds = %entry
+  %call3 = call i32 @foo(i32 50), !dbg !18
+  store i32 %call3, i32* %x, align 4, !dbg !18, !tbaa !10
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %4 = load i32, i32* %x, align 4, !dbg !19, !tbaa !10
+  %5 = bitcast i32* %x to i8*, !dbg !20
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %5) #4, !dbg !20
+  %6 = bitcast i32* %rando to i8*, !dbg !20
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %6) #4, !dbg !20
+  ret i32 %4, !dbg !19
+}
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
+
+declare i32 @buzz(...) #2
+
+; Function Attrs: nounwind readnone willreturn
+declare i64 @llvm.expect.i64(i64, i64) #3
+
+declare i32 @baz(i32) #2
+
+declare i32 @foo(i32) #2
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+cx8,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind willreturn }
+attributes #2 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+cx8,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { nounwind readnone willreturn }
+attributes #4 = { nounwind }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+!llvm.ident = !{!5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 10.0.0 (trunk c20270bfffc9d6965219de339d66c61e9fe7d82d)", isOptimized: true, runtimeVersion: 0, emissionKind: LineTablesOnly, enums: !2, nameTableKind: None)
+!1 = !DIFile(filename: "<stdin>", directory: ".")
+!2 = !{}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = !{i32 1, !"wchar_size", i32 4}
+!5 = !{!"clang version 10.0.0 (trunk c20270bfffc9d6965219de339d66c61e9fe7d82d)"}
+!6 = distinct !DISubprogram(name: "bar", scope: !7, file: !7, line: 19, type: !8, scopeLine: 19, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+!7 = !DIFile(filename: "misexpect-branch.c", directory: ".")
+!8 = !DISubroutineType(types: !2)
+!9 = !DILocation(line: 20, scope: !6)
+!10 = !{!11, !11, i64 0}
+!11 = !{!"int", !12, i64 0}
+!12 = !{!"omnipotent char", !13, i64 0}
+!13 = !{!"Simple C/C++ TBAA"}
+!14 = !DILocation(line: 21, scope: !6)
+!15 = !DILocation(line: 22, scope: !6)
+!16 = !DILocation(line: 23, scope: !6)
+!17 = !DILocation(line: 24, scope: !6)
+!18 = !DILocation(line: 25, scope: !6)
+!19 = !DILocation(line: 27, scope: !6)
+!20 = !DILocation(line: 28, scope: !6)

llvm/test/Transforms/PGOProfile/misexpect-switch-default.ll

+; Test misexpect handles switch statements when debug information is stripped
+
+; RUN: llvm-profdata merge %S/Inputs/misexpect-switch.proftext -o %t.profdata
+
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -S 2>&1 | FileCheck %s --check-prefix=WARNING
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pass-remarks=misexpect -S 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -pass-remarks=misexpect -S 2>&1 | FileCheck %s --check-prefix=BOTH
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -S 2>&1 | FileCheck %s --check-prefix=DISABLED
+
+; WARNING-DAG: warning: <unknown>:0:0: 0.00%
+; WARNING-NOT: remark: <unknown>:0:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 0.00% (0 / 27943) of profiled executions.
+
+; REMARK-NOT: warning: <unknown>:0:0: 0.00%
+; REMARK-DAG: remark: <unknown>:0:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 0.00% (0 / 27943) of profiled executions.
+
+; BOTH-DAG: warning: <unknown>:0:0: 0.00%
+; BOTH-DAG: remark: <unknown>:0:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 0.00% (0 / 27943) of profiled executions.
+
+; DISABLED-NOT: warning: <unknown>:0:0: 0.00%
+; DISABLED-NOT: remark: <unknown>:0:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 0.00% (0 / 27943) of profiled executions.
+
+; DISABLED-NOT: warning: <unknown>:0:0: 0.00%
+; DISABLED-NOT: remark: <unknown>:0:0: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 0.00% (0 / 27943) of profiled executions.
+
+; CORRECT-NOT: warning: {{.*}}
+; CORRECT-NOT: remark: {{.*}}
+
+
+; ModuleID = 'misexpect-switch.c'
+source_filename = "misexpect-switch.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@inner_loop = dso_local constant i32 1000, align 4
+@outer_loop = dso_local constant i32 20, align 4
+@arry_size = dso_local constant i32 25, align 4
+@arry = dso_local global [25 x i32] zeroinitializer, align 16
+
+; Function Attrs: nounwind uwtable
+define dso_local void @init_arry() #0 {
+entry:
+  %i = alloca i32, align 4
+  %0 = bitcast i32* %i to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #6
+  store i32 0, i32* %i, align 4, !tbaa !4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %1 = load i32, i32* %i, align 4, !tbaa !4
+  %cmp = icmp slt i32 %1, 25
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %call = call i32 @rand() #6
+  %rem = srem i32 %call, 10
+  %2 = load i32, i32* %i, align 4, !tbaa !4
+  %idxprom = sext i32 %2 to i64
+  %arrayidx = getelementptr inbounds [25 x i32], [25 x i32]* @arry, i64 0, i64 %idxprom
+  store i32 %rem, i32* %arrayidx, align 4, !tbaa !4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %3 = load i32, i32* %i, align 4, !tbaa !4
+  %inc = add nsw i32 %3, 1
+  store i32 %inc, i32* %i, align 4, !tbaa !4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  %4 = bitcast i32* %i to i8*
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %4) #6
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
+
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #2
+
+; Function Attrs: nounwind
+declare dso_local i32 @rand() #3
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
+
+; Function Attrs: nounwind uwtable
+define dso_local i32 @main() #0 {
+entry:
+  %retval = alloca i32, align 4
+  %val = alloca i32, align 4
+  %j = alloca i32, align 4
+  %condition = alloca i32, align 4
+  store i32 0, i32* %retval, align 4
+  call void @init_arry()
+  %0 = bitcast i32* %val to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #6
+  store i32 0, i32* %val, align 4, !tbaa !4
+  %1 = bitcast i32* %j to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %1) #6
+  store i32 0, i32* %j, align 4, !tbaa !4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %2 = load i32, i32* %j, align 4, !tbaa !4
+  %cmp = icmp slt i32 %2, 20000
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %3 = bitcast i32* %condition to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %3) #6
+  %call = call i32 @rand() #6
+  %rem = srem i32 %call, 5
+  store i32 %rem, i32* %condition, align 4, !tbaa !4
+  %4 = load i32, i32* %condition, align 4, !tbaa !4
+  %conv = zext i32 %4 to i64
+  %expval = call i64 @llvm.expect.i64(i64 %conv, i64 6)
+  switch i64 %expval, label %sw.default [
+    i64 0, label %sw.bb
+    i64 1, label %sw.bb2
+    i64 2, label %sw.bb2
+    i64 3, label %sw.bb2
+    i64 4, label %sw.bb3
+  ]
+
+sw.bb:                                            ; preds = %for.body
+  %call1 = call i32 @sum(i32* getelementptr inbounds ([25 x i32], [25 x i32]* @arry, i64 0, i64 0), i32 25)
+  %5 = load i32, i32* %val, align 4, !tbaa !4
+  %add = add nsw i32 %5, %call1
+  store i32 %add, i32* %val, align 4, !tbaa !4
+  br label %sw.epilog
+
+sw.bb2:                                           ; preds = %for.body, %for.body, %for.body
+  br label %sw.epilog
+
+sw.bb3:                                           ; preds = %for.body
+  %call4 = call i32 @random_sample(i32* getelementptr inbounds ([25 x i32], [25 x i32]* @arry, i64 0, i64 0), i32 25)
+  %6 = load i32, i32* %val, align 4, !tbaa !4
+  %add5 = add nsw i32 %6, %call4
+  store i32 %add5, i32* %val, align 4, !tbaa !4
+  br label %sw.epilog
+
+sw.default:                                       ; preds = %for.body
+  unreachable
+
+sw.epilog:                                        ; preds = %sw.bb3, %sw.bb2, %sw.bb
+  %7 = bitcast i32* %condition to i8*
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %7) #6
+  br label %for.inc
+
+for.inc:                                          ; preds = %sw.epilog
+  %8 = load i32, i32* %j, align 4, !tbaa !4
+  %inc = add nsw i32 %8, 1
+  store i32 %inc, i32* %j, align 4, !tbaa !4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  %9 = bitcast i32* %j to i8*
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %9) #6
+  %10 = bitcast i32* %val to i8*
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %10) #6
+  ret i32 0
+}
+
+; Function Attrs: nounwind readnone willreturn
+declare i64 @llvm.expect.i64(i64, i64) #4
+
+declare dso_local i32 @sum(i32*, i32) #5
+
+declare dso_local i32 @random_sample(i32*, i32) #5
+
+attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind willreturn }
+attributes #2 = { nounwind readnone speculatable willreturn }
+attributes #3 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #4 = { nounwind readnone willreturn }
+attributes #5 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #6 = { nounwind }
+
+!llvm.module.flags = !{!0, !1, !2}
+!llvm.ident = !{!3}
+
+!0 = !{i32 2, !"Dwarf Version", i32 4}
+!1 = !{i32 2, !"Debug Info Version", i32 3}
+!2 = !{i32 1, !"wchar_size", i32 4}
+!3 = !{!"clang version 10.0.0 (60b79b85b1763d3d25630261e5cd1adb7f0835bc)"}
+!4 = !{!5, !5, i64 0}
+!5 = !{!"int", !6, i64 0}
+!6 = !{!"omnipotent char", !7, i64 0}
+!7 = !{!"Simple C/C++ TBAA"}

llvm/test/Transforms/PGOProfile/misexpect-switch.ll

+; Test misexpect diagnostics handle swich statements, and report source locations correctly
+
+; RUN: llvm-profdata merge %S/Inputs/misexpect-switch.proftext -o %t.profdata
+; RUN: llvm-profdata merge %S/Inputs/misexpect-switch-correct.proftext -o %t.c.profdata
+
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -S 2>&1 | FileCheck %s --check-prefix=WARNING
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pass-remarks=misexpect -S 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -pgo-warn-misexpect -pass-remarks=misexpect -S 2>&1 | FileCheck %s --check-prefix=BOTH
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.profdata -S 2>&1 | FileCheck %s --check-prefix=DISABLED
+
+; RUN: opt < %s -passes="function(lower-expect),pgo-instr-use" -pgo-test-profile-file=%t.c.profdata -pgo-warn-misexpect -pass-remarks=misexpect -S 2>&1 | FileCheck %s --check-prefix=CORRECT
+
+; WARNING-DAG: warning: misexpect-switch.c:26:30: 0.00%
+; WARNING-NOT: remark: misexpect-switch.c:26:30: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 0.00% (0 / 8112) of profiled executions.
+
+; REMARK-NOT: warning: misexpect-switch.c:26:30: 0.00%
+; REMARK-DAG: remark: misexpect-switch.c:26:30: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 0.00% (0 / 8112) of profiled executions.
+
+; BOTH-DAG: warning: misexpect-switch.c:26:30: 0.00%
+; BOTH-DAG: remark: misexpect-switch.c:26:30: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 0.00% (0 / 8112) of profiled executions.
+
+; DISABLED-NOT: warning: misexpect-switch.c:26:30: 0.00%
+; DISABLED-NOT: remark: misexpect-switch.c:26:30: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 0.00% (0 / 8112) of profiled executions.
+
+; DISABLED-NOT: warning: misexpect-switch.c:26:30: 0.00%
+; DISABLED-NOT: remark: misexpect-switch.c:26:30: Potential performance regression from use of the llvm.expect intrinsic: Annotation was correct on 0.00% (0 / 8112) of profiled executions.
+
+; CORRECT-NOT: warning: {{.*}}
+; CORRECT-NOT: remark: {{.*}}
+
+
+; ModuleID = 'misexpect-switch.c'
+source_filename = "misexpect-switch.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@inner_loop = dso_local constant i32 1000, align 4, !dbg !0
+@outer_loop = dso_local constant i32 20, align 4, !dbg !6
+@arry_size = dso_local constant i32 25, align 4, !dbg !10
+@arry = dso_local global [25 x i32] zeroinitializer, align 16, !dbg !12
+
+; Function Attrs: nounwind uwtable
+define dso_local void @init_arry() #0 !dbg !21 {
+entry:
+  %i = alloca i32, align 4
+  %0 = bitcast i32* %i to i8*, !dbg !26
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #6, !dbg !26
+  call void @llvm.dbg.declare(metadata i32* %i, metadata !25, metadata !DIExpression()), !dbg !27
+  store i32 0, i32* %i, align 4, !dbg !28, !tbaa !30
+  br label %for.cond, !dbg !34
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %1 = load i32, i32* %i, align 4, !dbg !35, !tbaa !30
+  %cmp = icmp slt i32 %1, 25, !dbg !37
+  br i1 %cmp, label %for.body, label %for.end, !dbg !38
+
+for.body:                                         ; preds = %for.cond
+  %call = call i32 @rand() #6, !dbg !39
+  %rem = srem i32 %call, 10, !dbg !41
+  %2 = load i32, i32* %i, align 4, !dbg !42, !tbaa !30
+  %idxprom = sext i32 %2 to i64, !dbg !43
+  %arrayidx = getelementptr inbounds [25 x i32], [25 x i32]* @arry, i64 0, i64 %idxprom, !dbg !43
+  store i32 %rem, i32* %arrayidx, align 4, !dbg !44, !tbaa !30
+  br label %for.inc, !dbg !45
+
+for.inc:                                          ; preds = %for.body
+  %3 = load i32, i32* %i, align 4, !dbg !46, !tbaa !30
+  %inc = add nsw i32 %3, 1, !dbg !46
+  store i32 %inc, i32* %i, align 4, !dbg !46, !tbaa !30
+  br label %for.cond, !dbg !47, !llvm.loop !48
+
+for.end:                                          ; preds = %for.cond
+  %4 = bitcast i32* %i to i8*, !dbg !50
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %4) #6, !dbg !50
+  ret void, !dbg !50
+}
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
+
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #2
+
+; Function Attrs: nounwind
+declare dso_local i32 @rand() #3
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
+
+; Function Attrs: nounwind uwtable
+define dso_local i32 @main() #0 !dbg !51 {
+entry:
+  %retval = alloca i32, align 4
+  %val = alloca i32, align 4
+  %j = alloca i32, align 4
+  %condition = alloca i32, align 4
+  store i32 0, i32* %retval, align 4
+  call void @init_arry(), !dbg !62
+  %0 = bitcast i32* %val to i8*, !dbg !63
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #6, !dbg !63
+  call void @llvm.dbg.declare(metadata i32* %val, metadata !55, metadata !DIExpression()), !dbg !64
+  store i32 0, i32* %val, align 4, !dbg !64, !tbaa !30
+  %1 = bitcast i32* %j to i8*, !dbg !65
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %1) #6, !dbg !65
+  call void @llvm.dbg.declare(metadata i32* %j, metadata !56, metadata !DIExpression()), !dbg !66
+  store i32 0, i32* %j, align 4, !dbg !67, !tbaa !30
+  br label %for.cond, !dbg !68
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %2 = load i32, i32* %j, align 4, !dbg !69, !tbaa !30
+  %cmp = icmp slt i32 %2, 20000, !dbg !70
+  br i1 %cmp, label %for.body, label %for.end, !dbg !71
+
+for.body:                                         ; preds = %for.cond
+  %3 = bitcast i32* %condition to i8*, !dbg !72
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %3) #6, !dbg !72
+  call void @llvm.dbg.declare(metadata i32* %condition, metadata !57, metadata !DIExpression()), !dbg !73
+  %call = call i32 @rand() #6, !dbg !74
+  %rem = srem i32 %call, 5, !dbg !75
+  store i32 %rem, i32* %condition, align 4, !dbg !73, !tbaa !30
+  %4 = load i32, i32* %condition, align 4, !dbg !76, !tbaa !30
+  %conv = zext i32 %4 to i64, !dbg !76
+  %expval = call i64 @llvm.expect.i64(i64 %conv, i64 0), !dbg !77
+  switch i64 %expval, label %sw.default [
+    i64 0, label %sw.bb
+    i64 1, label %sw.bb2
+    i64 2, label %sw.bb2
+    i64 3, label %sw.bb2
+    i64 4, label %sw.bb3
+  ], !dbg !78
+
+sw.bb:                                            ; preds = %for.body
+  %call1 = call i32 @sum(i32* getelementptr inbounds ([25 x i32], [25 x i32]* @arry, i64 0, i64 0), i32 25), !dbg !79
+  %5 = load i32, i32* %val, align 4, !dbg !81, !tbaa !30
+  %add = add nsw i32 %5, %call1, !dbg !81
+  store i32 %add, i32* %val, align 4, !dbg !81, !tbaa !30
+  br label %sw.epilog, !dbg !82
+
+sw.bb2:                                           ; preds = %for.body, %for.body, %for.body
+  br label %sw.epilog, !dbg !83
+
+sw.bb3:                                           ; preds = %for.body
+  %call4 = call i32 @random_sample(i32* getelementptr inbounds ([25 x i32], [25 x i32]* @arry, i64 0, i64 0), i32 25), !dbg !84
+  %6 = load i32, i32* %val, align 4, !dbg !85, !tbaa !30
+  %add5 = add nsw i32 %6, %call4, !dbg !85
+  store i32 %add5, i32* %val, align 4, !dbg !85, !tbaa !30
+  br label %sw.epilog, !dbg !86
+
+sw.default:                                       ; preds = %for.body
+  unreachable, !dbg !87
+
+sw.epilog:                                        ; preds = %sw.bb3, %sw.bb2, %sw.bb
+  %7 = bitcast i32* %condition to i8*, !dbg !88
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %7) #6, !dbg !88
+  br label %for.inc, !dbg !89
+
+for.inc:                                          ; preds = %sw.epilog
+  %8 = load i32, i32* %j, align 4, !dbg !90, !tbaa !30
+  %inc = add nsw i32 %8, 1, !dbg !90
+  store i32 %inc, i32* %j, align 4, !dbg !90, !tbaa !30
+  br label %for.cond, !dbg !91, !llvm.loop !92
+
+for.end:                                          ; preds = %for.cond
+  %9 = bitcast i32* %j to i8*, !dbg !94
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %9) #6, !dbg !94
+  %10 = bitcast i32* %val to i8*, !dbg !94
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %10) #6, !dbg !94
+  ret i32 0, !dbg !95
+}
+
+; Function Attrs: nounwind readnone willreturn
+declare i64 @llvm.expect.i64(i64, i64) #4
+
+declare dso_local i32 @sum(i32*, i32) #5
+
+declare dso_local i32 @random_sample(i32*, i32) #5
+
+attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind willreturn }
+attributes #2 = { nounwind readnone speculatable willreturn }
+attributes #3 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #4 = { nounwind readnone willreturn }
+attributes #5 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #6 = { nounwind }
+
+!llvm.dbg.cu = !{!2}
+!llvm.module.flags = !{!17, !18, !19}
+!llvm.ident = !{!20}
+
+!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
+!1 = distinct !DIGlobalVariable(name: "inner_loop", scope: !2, file: !3, line: 7, type: !8, isLocal: false, isDefinition: true)
+!2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, producer: "clang version 10.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5, nameTableKind: None)
+!3 = !DIFile(filename: "misexpect-switch.c", directory: ".")
+!4 = !{}
+!5 = !{!0, !6, !10, !12}
+!6 = !DIGlobalVariableExpression(var: !7, expr: !DIExpression())
+!7 = distinct !DIGlobalVariable(name: "outer_loop", scope: !2, file: !3, line: 8, type: !8, isLocal: false, isDefinition: true)
+!8 = !DIDerivedType(tag: DW_TAG_const_type, baseType: !9)
+!9 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!10 = !DIGlobalVariableExpression(var: !11, expr: !DIExpression())
+!11 = distinct !DIGlobalVariable(name: "arry_size", scope: !2, file: !3, line: 9, type: !8, isLocal: false, isDefinition: true)
+!12 = !DIGlobalVariableExpression(var: !13, expr: !DIExpression())
+!13 = distinct !DIGlobalVariable(name: "arry", scope: !2, file: !3, line: 11, type: !14, isLocal: false, isDefinition: true)
+!14 = !DICompositeType(tag: DW_TAG_array_type, baseType: !9, size: 800, elements: !15)
+!15 = !{!16}
+!16 = !DISubrange(count: 25)
+!17 = !{i32 2, !"Dwarf Version", i32 4}
+!18 = !{i32 2, !"Debug Info Version", i32 3}
+!19 = !{i32 1, !"wchar_size", i32 4}
+!20 = !{!"clang version 10.0.0"}
+!21 = distinct !DISubprogram(name: "init_arry", scope: !3, file: !3, line: 13, type: !22, scopeLine: 13, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !2, retainedNodes: !24)
+!22 = !DISubroutineType(types: !23)
+!23 = !{null}
+!24 = !{!25}
+!25 = !DILocalVariable(name: "i", scope: !21, file: !3, line: 14, type: !9)
+!26 = !DILocation(line: 14, column: 3, scope: !21)
+!27 = !DILocation(line: 14, column: 7, scope: !21)
+!28 = !DILocation(line: 15, column: 10, scope: !29)
+!29 = distinct !DILexicalBlock(scope: !21, file: !3, line: 15, column: 3)
+!30 = !{!31, !31, i64 0}
+!31 = !{!"int", !32, i64 0}
+!32 = !{!"omnipotent char", !33, i64 0}
+!33 = !{!"Simple C/C++ TBAA"}
+!34 = !DILocation(line: 15, column: 8, scope: !29)
+!35 = !DILocation(line: 15, column: 15, scope: !36)
+!36 = distinct !DILexicalBlock(scope: !29, file: !3, line: 15, column: 3)
+!37 = !DILocation(line: 15, column: 17, scope: !36)
+!38 = !DILocation(line: 15, column: 3, scope: !29)
+!39 = !DILocation(line: 16, column: 15, scope: !40)
+!40 = distinct !DILexicalBlock(scope: !36, file: !3, line: 15, column: 35)
+!41 = !DILocation(line: 16, column: 22, scope: !40)
+!42 = !DILocation(line: 16, column: 10, scope: !40)
+!43 = !DILocation(line: 16, column: 5, scope: !40)
+!44 = !DILocation(line: 16, column: 13, scope: !40)
+!45 = !DILocation(line: 17, column: 3, scope: !40)
+!46 = !DILocation(line: 15, column: 30, scope: !36)
+!47 = !DILocation(line: 15, column: 3, scope: !36)
+!48 = distinct !{!48, !38, !49}
+!49 = !DILocation(line: 17, column: 3, scope: !29)
+!50 = !DILocation(line: 18, column: 1, scope: !21)
+!51 = distinct !DISubprogram(name: "main", scope: !3, file: !3, line: 20, type: !52, scopeLine: 20, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !2, retainedNodes: !54)
+!52 = !DISubroutineType(types: !53)
+!53 = !{!9}
+!54 = !{!55, !56, !57}
+!55 = !DILocalVariable(name: "val", scope: !51, file: !3, line: 22, type: !9)
+!56 = !DILocalVariable(name: "j", scope: !51, file: !3, line: 23, type: !9)
+!57 = !DILocalVariable(name: "condition", scope: !58, file: !3, line: 25, type: !61)
+!58 = distinct !DILexicalBlock(scope: !59, file: !3, line: 24, column: 49)
+!59 = distinct !DILexicalBlock(scope: !60, file: !3, line: 24, column: 3)
+!60 = distinct !DILexicalBlock(scope: !51, file: !3, line: 24, column: 3)
+!61 = !DIBasicType(name: "unsigned int", size: 32, encoding: DW_ATE_unsigned)
+!62 = !DILocation(line: 21, column: 3, scope: !51)
+!63 = !DILocation(line: 22, column: 3, scope: !51)
+!64 = !DILocation(line: 22, column: 7, scope: !51)
+!65 = !DILocation(line: 23, column: 3, scope: !51)
+!66 = !DILocation(line: 23, column: 7, scope: !51)
+!67 = !DILocation(line: 24, column: 10, scope: !60)
+!68 = !DILocation(line: 24, column: 8, scope: !60)
+!69 = !DILocation(line: 24, column: 15, scope: !59)
+!70 = !DILocation(line: 24, column: 17, scope: !59)
+!71 = !DILocation(line: 24, column: 3, scope: !60)
+!72 = !DILocation(line: 25, column: 5, scope: !58)
+!73 = !DILocation(line: 25, column: 14, scope: !58)
+!74 = !DILocation(line: 25, column: 26, scope: !58)
+!75 = !DILocation(line: 25, column: 33, scope: !58)
+!76 = !DILocation(line: 26, column: 30, scope: !58)
+!77 = !DILocation(line: 26, column: 13, scope: !58)
+!78 = !DILocation(line: 26, column: 5, scope: !58)
+!79 = !DILocation(line: 28, column: 14, scope: !80)
+!80 = distinct !DILexicalBlock(scope: !58, file: !3, line: 26, column: 45)
+!81 = !DILocation(line: 28, column: 11, scope: !80)
+!82 = !DILocation(line: 29, column: 7, scope: !80)
+!83 = !DILocation(line: 33, column: 7, scope: !80)
+!84 = !DILocation(line: 35, column: 14, scope: !80)
+!85 = !DILocation(line: 35, column: 11, scope: !80)
+!86 = !DILocation(line: 36, column: 7, scope: !80)
+!87 = !DILocation(line: 38, column: 7, scope: !80)
+!88 = !DILocation(line: 40, column: 3, scope: !59)
+!89 = !DILocation(line: 40, column: 3, scope: !58)
+!90 = !DILocation(line: 24, column: 44, scope: !59)
+!91 = !DILocation(line: 24, column: 3, scope: !59)
+!92 = distinct !{!92, !71, !93}
+!93 = !DILocation(line: 40, column: 3, scope: !60)
+!94 = !DILocation(line: 43, column: 1, scope: !51)
+!95 = !DILocation(line: 42, column: 3, scope: !51)