Page MenuHomePhabricator

[misexpect] Re-implement MisExpect Diagnostics
ClosedPublic

Authored by paulkirth on Dec 16 2021, 2:01 PM.

Details

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

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
paulkirth added inline comments.Mar 16 2022, 2:55 PM
llvm/lib/Transforms/Utils/MisExpect.cpp
189

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

tejohnson accepted this revision.Mar 17 2022, 3:16 PM

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
1388

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.

This revision is now accepted and ready to land.Mar 17 2022, 3:16 PM

Add Clang release note as well please.

clang/docs/MisExpect.rst
59

value

paulkirth updated this revision to Diff 416356.Mar 17 2022, 4:34 PM
paulkirth marked 4 inline comments as done.

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 marked 5 inline comments as done.Mar 17 2022, 4:39 PM
paulkirth added inline comments.
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.

This revision was landed with ongoing or failed builds.Mar 17 2022, 4:48 PM
This revision was automatically updated to reflect the committed changes.
thakis added a subscriber: thakis.Mar 17 2022, 5:20 PM

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.

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

fhahn added a subscriber: fhahn.Mar 18 2022, 3:16 AM

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 reopened this revision.Mar 24 2022, 12:46 PM
This revision is now accepted and ready to land.Mar 24 2022, 12:46 PM

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

paulkirth added inline comments.Mar 24 2022, 12:56 PM
clang/lib/Frontend/CompilerInvocation.cpp
1566

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?

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.

tejohnson added inline comments.Mar 28 2022, 9:57 AM
clang/lib/Frontend/CompilerInvocation.cpp
1566

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

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

This revision was automatically updated to reflect the committed changes.
tonic added a subscriber: tonic.Mar 28 2022, 10:52 PM

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?

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

paulkirth reopened this revision.Mar 28 2022, 11:23 PM
This revision is now accepted and ready to land.Mar 28 2022, 11:23 PM

Fix missing reference in TOC & fix formatting of tables

This revision was landed with ongoing or failed builds.Mar 31 2022, 10:38 AM
This revision was automatically updated to reflect the committed changes.
jgorbe added a subscriber: jgorbe.Mar 31 2022, 2:51 PM

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)

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.

@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 reopened this revision.Apr 1 2022, 3:03 PM
This revision is now accepted and ready to land.Apr 1 2022, 3:03 PM
paulkirth updated this revision to Diff 419931.Apr 1 2022, 10:08 PM

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 updated this revision to Diff 419933.Apr 1 2022, 10:12 PM

Remove commented out code

tejohnson added inline comments.Apr 4 2022, 9:55 PM
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 updated this revision to Diff 420397.Apr 5 2022, 12:16 AM

Swap parameters in clamp routine

paulkirth marked an inline comment as done.

rebase

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.

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.

This revision was landed with ongoing or failed builds.Apr 19 2022, 2:24 PM
This revision was automatically updated to reflect the committed changes.
bgraur added a subscriber: bgraur.Fri, Apr 22, 10:56 AM