1651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines//===--- CodeGenPGO.cpp - PGO Instrumentation for LLVM CodeGen --*- C++ -*-===// 2651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines// 3651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines// The LLVM Compiler Infrastructure 4651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines// 5651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines// This file is distributed under the University of Illinois Open Source 6651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines// License. See LICENSE.TXT for details. 7651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines// 8651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines//===----------------------------------------------------------------------===// 9651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines// 10651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines// Instrumentation-based profile-guided optimization 11651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines// 12651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines//===----------------------------------------------------------------------===// 13651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 14651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines#include "CodeGenPGO.h" 15651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines#include "CodeGenFunction.h" 16651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines#include "clang/AST/RecursiveASTVisitor.h" 17651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines#include "clang/AST/StmtVisitor.h" 18651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines#include "llvm/IR/MDBuilder.h" 196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include "llvm/ProfileData/InstrProfReader.h" 206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include "llvm/Support/Endian.h" 21651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines#include "llvm/Support/FileSystem.h" 226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include "llvm/Support/MD5.h" 23651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 24651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesusing namespace clang; 25651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesusing namespace CodeGen; 26651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 27651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesvoid CodeGenPGO::setFuncName(llvm::Function *Fn) { 28651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RawFuncName = Fn->getName(); 29651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 30651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Function names may be prefixed with a binary '1' to indicate 31651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // that the backend should not modify the symbols due to any platform 32651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // naming convention. Do not include that '1' in the PGO profile name. 33651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (RawFuncName[0] == '\1') 34651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RawFuncName = RawFuncName.substr(1); 35651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 36651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!Fn->hasLocalLinkage()) { 37651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines PrefixedFuncName.reset(new std::string(RawFuncName)); 38651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return; 39651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 40651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 41651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // For local symbols, prepend the main file name to distinguish them. 42651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Do not include the full path in the file name since there's no guarantee 43651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // that it will stay the same, e.g., if the files are checked out from 44651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // version control in different locations. 45651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines PrefixedFuncName.reset(new std::string(CGM.getCodeGenOpts().MainFileName)); 46651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (PrefixedFuncName->empty()) 47651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines PrefixedFuncName->assign("<unknown>"); 48651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines PrefixedFuncName->append(":"); 49651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines PrefixedFuncName->append(RawFuncName); 50651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 51651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 52651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesstatic llvm::Function *getRegisterFunc(CodeGenModule &CGM) { 53651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return CGM.getModule().getFunction("__llvm_profile_register_functions"); 54651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 55651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 56651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesstatic llvm::BasicBlock *getOrInsertRegisterBB(CodeGenModule &CGM) { 57651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Don't do this for Darwin. compiler-rt uses linker magic. 58651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (CGM.getTarget().getTriple().isOSDarwin()) 59651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return nullptr; 60651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 61651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Only need to insert this once per module. 62651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (llvm::Function *RegisterF = getRegisterFunc(CGM)) 63651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return &RegisterF->getEntryBlock(); 64651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 65651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Construct the function. 66651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *VoidTy = llvm::Type::getVoidTy(CGM.getLLVMContext()); 67651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *RegisterFTy = llvm::FunctionType::get(VoidTy, false); 68651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *RegisterF = llvm::Function::Create(RegisterFTy, 69651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::GlobalValue::InternalLinkage, 70651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines "__llvm_profile_register_functions", 71651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines &CGM.getModule()); 72651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegisterF->setUnnamedAddr(true); 73651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (CGM.getCodeGenOpts().DisableRedZone) 74651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegisterF->addFnAttr(llvm::Attribute::NoRedZone); 75651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 76651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Construct and return the entry block. 77651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *BB = llvm::BasicBlock::Create(CGM.getLLVMContext(), "", RegisterF); 78651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CGBuilderTy Builder(BB); 79651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Builder.CreateRetVoid(); 80651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return BB; 81651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 82651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 83651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesstatic llvm::Constant *getOrInsertRuntimeRegister(CodeGenModule &CGM) { 84651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *VoidTy = llvm::Type::getVoidTy(CGM.getLLVMContext()); 85651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *VoidPtrTy = llvm::Type::getInt8PtrTy(CGM.getLLVMContext()); 86651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *RuntimeRegisterTy = llvm::FunctionType::get(VoidTy, VoidPtrTy, false); 87651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return CGM.getModule().getOrInsertFunction("__llvm_profile_register_function", 88651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RuntimeRegisterTy); 89651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 90651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 91651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesstatic bool isMachO(const CodeGenModule &CGM) { 92651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return CGM.getTarget().getTriple().isOSBinFormatMachO(); 93651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 94651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 95651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesstatic StringRef getCountersSection(const CodeGenModule &CGM) { 96651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return isMachO(CGM) ? "__DATA,__llvm_prf_cnts" : "__llvm_prf_cnts"; 97651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 98651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 99651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesstatic StringRef getNameSection(const CodeGenModule &CGM) { 100651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return isMachO(CGM) ? "__DATA,__llvm_prf_names" : "__llvm_prf_names"; 101651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 102651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 103651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesstatic StringRef getDataSection(const CodeGenModule &CGM) { 104651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return isMachO(CGM) ? "__DATA,__llvm_prf_data" : "__llvm_prf_data"; 105651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 106651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 107651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesllvm::GlobalVariable *CodeGenPGO::buildDataVar() { 108651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Create name variable. 109651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::LLVMContext &Ctx = CGM.getLLVMContext(); 110651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *VarName = llvm::ConstantDataArray::getString(Ctx, getFuncName(), 111651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines false); 112651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *Name = new llvm::GlobalVariable(CGM.getModule(), VarName->getType(), 113651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines true, VarLinkage, VarName, 114651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines getFuncVarName("name")); 115651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Name->setSection(getNameSection(CGM)); 116651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Name->setAlignment(1); 117651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 118651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Create data variable. 119651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *Int32Ty = llvm::Type::getInt32Ty(Ctx); 120651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *Int64Ty = llvm::Type::getInt64Ty(Ctx); 121651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *Int8PtrTy = llvm::Type::getInt8PtrTy(Ctx); 122651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *Int64PtrTy = llvm::Type::getInt64PtrTy(Ctx); 123651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::Type *DataTypes[] = { 124651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Int32Ty, Int32Ty, Int64Ty, Int8PtrTy, Int64PtrTy 125651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines }; 126651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *DataTy = llvm::StructType::get(Ctx, makeArrayRef(DataTypes)); 127651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::Constant *DataVals[] = { 128651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::ConstantInt::get(Int32Ty, getFuncName().size()), 129651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::ConstantInt::get(Int32Ty, NumRegionCounters), 130651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::ConstantInt::get(Int64Ty, FunctionHash), 131651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::ConstantExpr::getBitCast(Name, Int8PtrTy), 132651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::ConstantExpr::getBitCast(RegionCounters, Int64PtrTy) 133651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines }; 134651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *Data = 135651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines new llvm::GlobalVariable(CGM.getModule(), DataTy, true, VarLinkage, 136651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::ConstantStruct::get(DataTy, DataVals), 137651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines getFuncVarName("data")); 138651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 139651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // All the data should be packed into an array in its own section. 140651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Data->setSection(getDataSection(CGM)); 141651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Data->setAlignment(8); 142651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 1436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Hide all these symbols so that we correctly get a copy for each 1446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // executable. The profile format expects names and counters to be 1456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // contiguous, so references into shared objects would be invalid. 1466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (!llvm::GlobalValue::isLocalLinkage(VarLinkage)) { 1476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Name->setVisibility(llvm::GlobalValue::HiddenVisibility); 1486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data->setVisibility(llvm::GlobalValue::HiddenVisibility); 1496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines RegionCounters->setVisibility(llvm::GlobalValue::HiddenVisibility); 1506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 152651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Make sure the data doesn't get deleted. 153651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CGM.addUsedGlobal(Data); 154651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return Data; 155651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 156651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 157651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesvoid CodeGenPGO::emitInstrumentationData() { 1586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (!RegionCounters) 159651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return; 160651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 161651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Build the data. 162651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *Data = buildDataVar(); 163651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 164651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Register the data. 165651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *RegisterBB = getOrInsertRegisterBB(CGM); 166651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!RegisterBB) 167651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return; 168651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CGBuilderTy Builder(RegisterBB->getTerminator()); 169651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *VoidPtrTy = llvm::Type::getInt8PtrTy(CGM.getLLVMContext()); 170651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Builder.CreateCall(getOrInsertRuntimeRegister(CGM), 171651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Builder.CreateBitCast(Data, VoidPtrTy)); 172651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 173651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 174651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesllvm::Function *CodeGenPGO::emitInitialization(CodeGenModule &CGM) { 175651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!CGM.getCodeGenOpts().ProfileInstrGenerate) 176651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return nullptr; 177651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 1786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(CGM.getModule().getFunction("__llvm_profile_init") == nullptr && 1796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines "profile initialization already emitted"); 180651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 181651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Get the function to call at initialization. 182651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::Constant *RegisterF = getRegisterFunc(CGM); 183651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!RegisterF) 184651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return nullptr; 185651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 186651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Create the initialization function. 187651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *VoidTy = llvm::Type::getVoidTy(CGM.getLLVMContext()); 188651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *F = llvm::Function::Create(llvm::FunctionType::get(VoidTy, false), 189651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::GlobalValue::InternalLinkage, 190651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines "__llvm_profile_init", &CGM.getModule()); 191651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines F->setUnnamedAddr(true); 192651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines F->addFnAttr(llvm::Attribute::NoInline); 193651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (CGM.getCodeGenOpts().DisableRedZone) 194651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines F->addFnAttr(llvm::Attribute::NoRedZone); 195651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 196651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Add the basic block and the necessary calls. 197651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CGBuilderTy Builder(llvm::BasicBlock::Create(CGM.getLLVMContext(), "", F)); 198651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Builder.CreateCall(RegisterF); 199651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Builder.CreateRetVoid(); 200651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 201651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return F; 202651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 203651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 204651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesnamespace { 2056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines/// \brief Stable hasher for PGO region counters. 2066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines/// 2076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines/// PGOHash produces a stable hash of a given function's control flow. 2086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines/// 2096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines/// Changing the output of this hash will invalidate all previously generated 2106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines/// profiles -- i.e., don't do it. 2116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines/// 2126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines/// \note When this hash does eventually change (years?), we still need to 2136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines/// support old hashes. We'll need to pull in the version number from the 2146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines/// profile data format and use the matching hash function. 2156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass PGOHash { 2166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines uint64_t Working; 2176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines unsigned Count; 2186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines llvm::MD5 MD5; 2196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static const int NumBitsPerType = 6; 2216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static const unsigned NumTypesPerWord = sizeof(uint64_t) * 8 / NumBitsPerType; 2226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static const unsigned TooBig = 1u << NumBitsPerType; 2236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 2256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines /// \brief Hash values for AST nodes. 2266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines /// 2276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines /// Distinct values for AST nodes that have region counters attached. 2286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines /// 2296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines /// These values must be stable. All new members must be added at the end, 2306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines /// and no members should be removed. Changing the enumeration value for an 2316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines /// AST node will affect the hash of every function that contains that node. 2326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines enum HashType : unsigned char { 2336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines None = 0, 2346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines LabelStmt = 1, 2356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines WhileStmt, 2366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines DoStmt, 2376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ForStmt, 2386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CXXForRangeStmt, 2396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ObjCForCollectionStmt, 2406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SwitchStmt, 2416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CaseStmt, 2426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines DefaultStmt, 2436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines IfStmt, 2446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CXXTryStmt, 2456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CXXCatchStmt, 2466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ConditionalOperator, 2476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BinaryOperatorLAnd, 2486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BinaryOperatorLOr, 2496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BinaryConditionalOperator, 2506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Keep this last. It's for the static assert that follows. 2526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines LastHashType 2536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines }; 2546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static_assert(LastHashType <= TooBig, "Too many types in HashType"); 2556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // TODO: When this format changes, take in a version number here, and use the 2576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // old hash calculation for file formats that used the old hash. 2586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines PGOHash() : Working(0), Count(0) {} 2596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void combine(HashType Type); 2606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines uint64_t finalize(); 2616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 2626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesconst int PGOHash::NumBitsPerType; 2636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesconst unsigned PGOHash::NumTypesPerWord; 2646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesconst unsigned PGOHash::TooBig; 2656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines /// A RecursiveASTVisitor that fills a map of statements to PGO counters. 2676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> { 268651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines /// The next counter value to assign. 269651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines unsigned NextCounter; 2706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines /// The function hash. 2716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines PGOHash Hash; 272651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines /// The map of statements to counters. 273651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::DenseMap<const Stmt *, unsigned> &CounterMap; 274651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 275651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines MapRegionCounters(llvm::DenseMap<const Stmt *, unsigned> &CounterMap) 276651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines : NextCounter(0), CounterMap(CounterMap) {} 277651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 2786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Blocks and lambdas are handled as separate functions, so we need not 2796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // traverse them in the parent context. 2806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines bool TraverseBlockExpr(BlockExpr *BE) { return true; } 2816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines bool TraverseLambdaBody(LambdaExpr *LE) { return true; } 2826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines bool TraverseCapturedStmt(CapturedStmt *CS) { return true; } 2836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines bool VisitDecl(const Decl *D) { 2856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines switch (D->getKind()) { 2866bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines default: 2876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines break; 2886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Decl::Function: 2896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Decl::CXXMethod: 2906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Decl::CXXConstructor: 2916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Decl::CXXDestructor: 2926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Decl::CXXConversion: 2936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Decl::ObjCMethod: 2946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Decl::Block: 2956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Decl::Captured: 2966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CounterMap[D->getBody()] = NextCounter++; 2976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines break; 2986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 2996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return true; 300651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 301651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 3026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines bool VisitStmt(const Stmt *S) { 3036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines auto Type = getHashType(S); 3046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Type == PGOHash::None) 3056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return true; 3066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 307651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CounterMap[S] = NextCounter++; 3086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Hash.combine(Type); 3096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return true; 310651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 3116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines PGOHash::HashType getHashType(const Stmt *S) { 3126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines switch (S->getStmtClass()) { 3136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines default: 3146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines break; 3156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::LabelStmtClass: 3166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::LabelStmt; 3176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::WhileStmtClass: 3186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::WhileStmt; 3196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::DoStmtClass: 3206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::DoStmt; 3216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::ForStmtClass: 3226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::ForStmt; 3236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::CXXForRangeStmtClass: 3246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::CXXForRangeStmt; 3256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::ObjCForCollectionStmtClass: 3266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::ObjCForCollectionStmt; 3276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::SwitchStmtClass: 3286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::SwitchStmt; 3296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::CaseStmtClass: 3306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::CaseStmt; 3316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::DefaultStmtClass: 3326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::DefaultStmt; 3336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::IfStmtClass: 3346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::IfStmt; 3356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::CXXTryStmtClass: 3366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::CXXTryStmt; 3376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::CXXCatchStmtClass: 3386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::CXXCatchStmt; 3396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::ConditionalOperatorClass: 3406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::ConditionalOperator; 3416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::BinaryConditionalOperatorClass: 3426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::BinaryConditionalOperator; 3436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case Stmt::BinaryOperatorClass: { 3446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const BinaryOperator *BO = cast<BinaryOperator>(S); 3456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (BO->getOpcode() == BO_LAnd) 3466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::BinaryOperatorLAnd; 3476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (BO->getOpcode() == BO_LOr) 3486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::BinaryOperatorLOr; 3496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines break; 3506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 3516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 3526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return PGOHash::None; 353651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 354651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines }; 355651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 356651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines /// A StmtVisitor that propagates the raw counts through the AST and 357651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines /// records the count at statements where the value may change. 358651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines struct ComputeRegionCounts : public ConstStmtVisitor<ComputeRegionCounts> { 359651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines /// PGO state. 360651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CodeGenPGO &PGO; 361651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 362651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines /// A flag that is set when the current count should be recorded on the 363651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines /// next statement, such as at the exit of a loop. 364651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines bool RecordNextStmtCount; 365651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 366651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines /// The map of statements to count values. 367651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::DenseMap<const Stmt *, uint64_t> &CountMap; 368651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 3696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines /// BreakContinueStack - Keep counts of breaks and continues inside loops. 370651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines struct BreakContinue { 371651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines uint64_t BreakCount; 372651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines uint64_t ContinueCount; 373651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinue() : BreakCount(0), ContinueCount(0) {} 374651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines }; 375651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines SmallVector<BreakContinue, 8> BreakContinueStack; 376651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 377651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines ComputeRegionCounts(llvm::DenseMap<const Stmt *, uint64_t> &CountMap, 378651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CodeGenPGO &PGO) 379651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines : PGO(PGO), RecordNextStmtCount(false), CountMap(CountMap) {} 380651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 381651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void RecordStmtCount(const Stmt *S) { 382651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (RecordNextStmtCount) { 383651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S] = PGO.getCurrentRegionCount(); 384651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = false; 385651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 386651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 387651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 388651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitStmt(const Stmt *S) { 389651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 390651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (Stmt::const_child_range I = S->children(); I; ++I) { 391651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (*I) 392651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines this->Visit(*I); 393651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 394651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 395651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 3966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void VisitFunctionDecl(const FunctionDecl *D) { 3976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks entry to the function body. 3986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines RegionCounter Cnt(PGO, D->getBody()); 399651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 4006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CountMap[D->getBody()] = PGO.getCurrentRegionCount(); 4016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Visit(D->getBody()); 402651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 403651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 4046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Skip lambda expressions. We visit these as FunctionDecls when we're 4056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // generating them and aren't interested in the body when generating a 4066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // parent context. 4076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void VisitLambdaExpr(const LambdaExpr *LE) {} 4086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void VisitCapturedDecl(const CapturedDecl *D) { 4106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks entry to the capture body. 4116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines RegionCounter Cnt(PGO, D->getBody()); 412651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 4136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CountMap[D->getBody()] = PGO.getCurrentRegionCount(); 4146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Visit(D->getBody()); 415651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 416651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 4176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void VisitObjCMethodDecl(const ObjCMethodDecl *D) { 4186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks entry to the method body. 4196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines RegionCounter Cnt(PGO, D->getBody()); 420651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 4216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CountMap[D->getBody()] = PGO.getCurrentRegionCount(); 4226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Visit(D->getBody()); 4236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 4246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void VisitBlockDecl(const BlockDecl *D) { 4266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks entry to the block body. 4276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines RegionCounter Cnt(PGO, D->getBody()); 4286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cnt.beginRegion(); 4296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CountMap[D->getBody()] = PGO.getCurrentRegionCount(); 4306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Visit(D->getBody()); 431651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 432651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 433651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitReturnStmt(const ReturnStmt *S) { 434651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 435651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (S->getRetValue()) 436651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getRetValue()); 437651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines PGO.setCurrentRegionUnreachable(); 438651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 439651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 440651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 441651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitGotoStmt(const GotoStmt *S) { 442651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 443651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines PGO.setCurrentRegionUnreachable(); 444651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 445651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 446651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 447651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitLabelStmt(const LabelStmt *S) { 448651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = false; 4496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the block following the label. 450651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, S); 451651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 452651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S] = PGO.getCurrentRegionCount(); 453651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getSubStmt()); 454651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 455651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 456651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitBreakStmt(const BreakStmt *S) { 457651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 458651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines assert(!BreakContinueStack.empty() && "break not in a loop or switch!"); 459651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinueStack.back().BreakCount += PGO.getCurrentRegionCount(); 460651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines PGO.setCurrentRegionUnreachable(); 461651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 462651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 463651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 464651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitContinueStmt(const ContinueStmt *S) { 465651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 466651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines assert(!BreakContinueStack.empty() && "continue stmt not in a loop!"); 467651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinueStack.back().ContinueCount += PGO.getCurrentRegionCount(); 468651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines PGO.setCurrentRegionUnreachable(); 469651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 470651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 471651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 472651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitWhileStmt(const WhileStmt *S) { 473651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 4746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the body of the loop. 475651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, S); 476651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinueStack.push_back(BreakContinue()); 477651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Visit the body region first so the break/continue adjustments can be 478651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // included when visiting the condition. 479651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 480651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getBody()] = PGO.getCurrentRegionCount(); 481651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getBody()); 482651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 483651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 484651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // ...then go back and propagate counts through the condition. The count 485651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // at the start of the condition is the sum of the incoming edges, 486651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // the backedge from the end of the loop body, and the edges from 487651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // continue statements. 488651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinue BC = BreakContinueStack.pop_back_val(); 489651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.setCurrentRegionCount(Cnt.getParentCount() + 490651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.getAdjustedCount() + BC.ContinueCount); 491651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getCond()] = PGO.getCurrentRegionCount(); 492651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getCond()); 493651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 494651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.applyAdjustmentsToRegion(BC.BreakCount + BC.ContinueCount); 495651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 496651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 497651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 498651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitDoStmt(const DoStmt *S) { 499651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 5006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the body of the loop. 501651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, S); 502651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinueStack.push_back(BreakContinue()); 503651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(/*AddIncomingFallThrough=*/true); 504651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getBody()] = PGO.getCurrentRegionCount(); 505651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getBody()); 506651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 507651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 508651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinue BC = BreakContinueStack.pop_back_val(); 509651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // The count at the start of the condition is equal to the count at the 510651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // end of the body. The adjusted count does not include either the 511651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // fall-through count coming into the loop or the continue count, so add 512651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // both of those separately. This is coincidentally the same equation as 513651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // with while loops but for different reasons. 514651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.setCurrentRegionCount(Cnt.getParentCount() + 515651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.getAdjustedCount() + BC.ContinueCount); 516651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getCond()] = PGO.getCurrentRegionCount(); 517651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getCond()); 518651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 519651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.applyAdjustmentsToRegion(BC.BreakCount + BC.ContinueCount); 520651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 521651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 522651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 523651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitForStmt(const ForStmt *S) { 524651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 525651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (S->getInit()) 526651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getInit()); 5276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the body of the loop. 528651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, S); 529651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinueStack.push_back(BreakContinue()); 530651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Visit the body region first. (This is basically the same as a while 531651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // loop; see further comments in VisitWhileStmt.) 532651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 533651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getBody()] = PGO.getCurrentRegionCount(); 534651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getBody()); 535651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 536651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 537651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // The increment is essentially part of the body but it needs to include 538651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // the count for all the continue statements. 539651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (S->getInc()) { 540651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.setCurrentRegionCount(PGO.getCurrentRegionCount() + 541651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinueStack.back().ContinueCount); 542651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getInc()] = PGO.getCurrentRegionCount(); 543651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getInc()); 544651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 545651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 546651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 547651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinue BC = BreakContinueStack.pop_back_val(); 548651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 549651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // ...then go back and propagate counts through the condition. 550651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (S->getCond()) { 551651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.setCurrentRegionCount(Cnt.getParentCount() + 552651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.getAdjustedCount() + 553651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BC.ContinueCount); 554651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getCond()] = PGO.getCurrentRegionCount(); 555651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getCond()); 556651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 557651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 558651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.applyAdjustmentsToRegion(BC.BreakCount + BC.ContinueCount); 559651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 560651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 561651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 562651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitCXXForRangeStmt(const CXXForRangeStmt *S) { 563651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 564651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getRangeStmt()); 565651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getBeginEndStmt()); 5666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the body of the loop. 567651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, S); 568651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinueStack.push_back(BreakContinue()); 569651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Visit the body region first. (This is basically the same as a while 570651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // loop; see further comments in VisitWhileStmt.) 571651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 572651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getLoopVarStmt()] = PGO.getCurrentRegionCount(); 573651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getLoopVarStmt()); 574651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getBody()); 575651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 576651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 577651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // The increment is essentially part of the body but it needs to include 578651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // the count for all the continue statements. 579651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.setCurrentRegionCount(PGO.getCurrentRegionCount() + 580651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinueStack.back().ContinueCount); 581651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getInc()] = PGO.getCurrentRegionCount(); 582651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getInc()); 583651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 584651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 585651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinue BC = BreakContinueStack.pop_back_val(); 586651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 587651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // ...then go back and propagate counts through the condition. 588651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.setCurrentRegionCount(Cnt.getParentCount() + 589651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.getAdjustedCount() + 590651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BC.ContinueCount); 591651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getCond()] = PGO.getCurrentRegionCount(); 592651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getCond()); 593651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 594651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.applyAdjustmentsToRegion(BC.BreakCount + BC.ContinueCount); 595651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 596651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 597651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 598651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) { 599651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 600651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getElement()); 6016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the body of the loop. 602651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, S); 603651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinueStack.push_back(BreakContinue()); 604651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 605651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getBody()] = PGO.getCurrentRegionCount(); 606651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getBody()); 607651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinue BC = BreakContinueStack.pop_back_val(); 608651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 609651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.applyAdjustmentsToRegion(BC.BreakCount + BC.ContinueCount); 610651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 611651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 612651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 613651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitSwitchStmt(const SwitchStmt *S) { 614651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 615651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getCond()); 616651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines PGO.setCurrentRegionUnreachable(); 617651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinueStack.push_back(BreakContinue()); 618651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getBody()); 619651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // If the switch is inside a loop, add the continue counts. 620651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinue BC = BreakContinueStack.pop_back_val(); 621651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!BreakContinueStack.empty()) 622651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BreakContinueStack.back().ContinueCount += BC.ContinueCount; 6236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the exit block of the switch. 624651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter ExitCnt(PGO, S); 625651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines ExitCnt.beginRegion(); 626651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 627651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 628651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 629651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitCaseStmt(const CaseStmt *S) { 630651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = false; 6316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter for this particular case. This counts only jumps from the 6326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // switch header and does not include fallthrough from the case before 6336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // this one. 634651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, S); 635651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(/*AddIncomingFallThrough=*/true); 636651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S] = Cnt.getCount(); 637651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 638651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getSubStmt()); 639651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 640651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 641651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitDefaultStmt(const DefaultStmt *S) { 642651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = false; 6436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter for this default case. This does not include fallthrough from 6446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // the previous case. 645651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, S); 646651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(/*AddIncomingFallThrough=*/true); 647651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S] = Cnt.getCount(); 648651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 649651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getSubStmt()); 650651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 651651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 652651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitIfStmt(const IfStmt *S) { 653651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 6546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the "then" part of an if statement. The count for 6556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // the "else" part, if it exists, will be calculated from this counter. 656651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, S); 657651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getCond()); 658651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 659651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 660651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getThen()] = PGO.getCurrentRegionCount(); 661651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getThen()); 662651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 663651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 664651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (S->getElse()) { 665651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginElseRegion(); 666651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S->getElse()] = PGO.getCurrentRegionCount(); 667651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getElse()); 668651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 669651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 670651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.applyAdjustmentsToRegion(0); 671651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 672651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 673651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 674651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitCXXTryStmt(const CXXTryStmt *S) { 675651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(S); 676651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getTryBlock()); 677651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (unsigned I = 0, E = S->getNumHandlers(); I < E; ++I) 678651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getHandler(I)); 6796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the continuation block of the try statement. 680651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, S); 681651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 682651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 683651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 684651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 685651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitCXXCatchStmt(const CXXCatchStmt *S) { 686651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = false; 6876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the catch statement's handler block. 688651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, S); 689651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 690651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[S] = PGO.getCurrentRegionCount(); 691651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(S->getHandlerBlock()); 692651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 693651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 6946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void VisitAbstractConditionalOperator( 6956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const AbstractConditionalOperator *E) { 696651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(E); 6976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the "true" part of a conditional operator. The 6986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // count in the "false" part will be calculated from this counter. 699651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, E); 700651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(E->getCond()); 701651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 702651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 703651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[E->getTrueExpr()] = PGO.getCurrentRegionCount(); 704651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(E->getTrueExpr()); 705651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 706651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 707651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginElseRegion(); 708651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[E->getFalseExpr()] = PGO.getCurrentRegionCount(); 709651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(E->getFalseExpr()); 710651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 711651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 712651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.applyAdjustmentsToRegion(0); 713651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 714651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 715651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 716651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitBinLAnd(const BinaryOperator *E) { 717651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(E); 7186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the right hand side of a logical and operator. 719651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, E); 720651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(E->getLHS()); 721651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 722651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[E->getRHS()] = PGO.getCurrentRegionCount(); 723651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(E->getRHS()); 724651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 725651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.applyAdjustmentsToRegion(0); 726651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 727651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 728651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 729651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void VisitBinLOr(const BinaryOperator *E) { 730651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordStmtCount(E); 7316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Counter tracks the right hand side of a logical or operator. 732651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter Cnt(PGO, E); 733651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(E->getLHS()); 734651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.beginRegion(); 735651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CountMap[E->getRHS()] = PGO.getCurrentRegionCount(); 736651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Visit(E->getRHS()); 737651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.adjustForControlFlow(); 738651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Cnt.applyAdjustmentsToRegion(0); 739651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RecordNextStmtCount = true; 740651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 741651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines }; 742651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 743651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 7446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesvoid PGOHash::combine(HashType Type) { 7456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Check that we never combine 0 and only have six bits. 7466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(Type && "Hash is invalid: unexpected type 0"); 7476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(unsigned(Type) < TooBig && "Hash is invalid: too many types"); 7486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Pass through MD5 if enough work has built up. 7506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Count && Count % NumTypesPerWord == 0) { 7516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines using namespace llvm::support; 7526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines uint64_t Swapped = endian::byte_swap<uint64_t, little>(Working); 7536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines MD5.update(llvm::makeArrayRef((uint8_t *)&Swapped, sizeof(Swapped))); 7546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Working = 0; 7556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 7566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Accumulate the current type. 7586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ++Count; 7596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Working = Working << NumBitsPerType | Type; 7606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 7616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesuint64_t PGOHash::finalize() { 7636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Use Working as the hash directly if we never used MD5. 7646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Count <= NumTypesPerWord) 7656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // No need to byte swap here, since none of the math was endian-dependent. 7666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // This number will be byte-swapped as required on endianness transitions, 7676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // so we will see the same value on the other side. 7686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Working; 7696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Check for remaining work in Working. 7716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Working) 7726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines MD5.update(Working); 7736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Finalize the MD5 and return the hash. 7756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines llvm::MD5::MD5Result Result; 7766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines MD5.final(Result); 7776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines using namespace llvm::support; 7786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return endian::read<uint64_t, little, unaligned>(Result); 7796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 7806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 781651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesstatic void emitRuntimeHook(CodeGenModule &CGM) { 7826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const char *const RuntimeVarName = "__llvm_profile_runtime"; 7836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const char *const RuntimeUserName = "__llvm_profile_runtime_user"; 784651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (CGM.getModule().getGlobalVariable(RuntimeVarName)) 785651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return; 786651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 787651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Declare the runtime hook. 788651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::LLVMContext &Ctx = CGM.getLLVMContext(); 789651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *Int32Ty = llvm::Type::getInt32Ty(Ctx); 790651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *Var = new llvm::GlobalVariable(CGM.getModule(), Int32Ty, false, 791651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::GlobalValue::ExternalLinkage, 792651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines nullptr, RuntimeVarName); 793651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 794651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Make a function that uses it. 795651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *User = llvm::Function::Create(llvm::FunctionType::get(Int32Ty, false), 796651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::GlobalValue::LinkOnceODRLinkage, 797651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RuntimeUserName, &CGM.getModule()); 798651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines User->addFnAttr(llvm::Attribute::NoInline); 799651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (CGM.getCodeGenOpts().DisableRedZone) 800651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines User->addFnAttr(llvm::Attribute::NoRedZone); 801651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CGBuilderTy Builder(llvm::BasicBlock::Create(CGM.getLLVMContext(), "", User)); 802651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines auto *Load = Builder.CreateLoad(Var); 803651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Builder.CreateRet(Load); 804651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 805651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Create a use of the function. Now the definition of the runtime variable 806651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // should get pulled in, along with any static initializears. 807651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines CGM.addUsedGlobal(User); 808651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 809651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 810651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesvoid CodeGenPGO::assignRegionCounters(const Decl *D, llvm::Function *Fn) { 811651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines bool InstrumentRegions = CGM.getCodeGenOpts().ProfileInstrGenerate; 8126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines llvm::IndexedInstrProfReader *PGOReader = CGM.getPGOReader(); 8136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (!InstrumentRegions && !PGOReader) 814651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return; 8156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (D->isImplicit()) 816651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return; 817651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines setFuncName(Fn); 818651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 819651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Set the linkage for variables based on the function linkage. Usually, we 820651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // want to match it, but available_externally and extern_weak both have the 821651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // wrong semantics. 822651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines VarLinkage = Fn->getLinkage(); 823651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines switch (VarLinkage) { 824651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines case llvm::GlobalValue::ExternalWeakLinkage: 825651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines VarLinkage = llvm::GlobalValue::LinkOnceAnyLinkage; 826651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines break; 827651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines case llvm::GlobalValue::AvailableExternallyLinkage: 828651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines VarLinkage = llvm::GlobalValue::LinkOnceODRLinkage; 829651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines break; 830651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines default: 831651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines break; 832651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 833651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 834651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines mapRegionCounters(D); 835651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (InstrumentRegions) { 836651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines emitRuntimeHook(CGM); 837651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines emitCounterVariables(); 838651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 8396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (PGOReader) { 840ef8225444452a1486bd721f3285301fe84643b00Stephen Hines SourceManager &SM = CGM.getContext().getSourceManager(); 841ef8225444452a1486bd721f3285301fe84643b00Stephen Hines loadRegionCounts(PGOReader, SM.isInMainFile(D->getLocation())); 842651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines computeRegionCounts(D); 8436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines applyFunctionAttributes(PGOReader, Fn); 844651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines } 845651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 846651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 847651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesvoid CodeGenPGO::mapRegionCounters(const Decl *D) { 848651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounterMap.reset(new llvm::DenseMap<const Stmt *, unsigned>); 849651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines MapRegionCounters Walker(*RegionCounterMap); 850651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(D)) 8516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Walker.TraverseDecl(const_cast<FunctionDecl *>(FD)); 852651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines else if (const ObjCMethodDecl *MD = dyn_cast_or_null<ObjCMethodDecl>(D)) 8536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Walker.TraverseDecl(const_cast<ObjCMethodDecl *>(MD)); 854651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines else if (const BlockDecl *BD = dyn_cast_or_null<BlockDecl>(D)) 8556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Walker.TraverseDecl(const_cast<BlockDecl *>(BD)); 8566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines else if (const CapturedDecl *CD = dyn_cast_or_null<CapturedDecl>(D)) 8576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Walker.TraverseDecl(const_cast<CapturedDecl *>(CD)); 8586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(Walker.NextCounter > 0 && "no entry counter mapped for decl"); 859651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines NumRegionCounters = Walker.NextCounter; 8606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines FunctionHash = Walker.Hash.finalize(); 861651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 862651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 863651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesvoid CodeGenPGO::computeRegionCounts(const Decl *D) { 864651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines StmtCountMap.reset(new llvm::DenseMap<const Stmt *, uint64_t>); 865651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines ComputeRegionCounts Walker(*StmtCountMap, *this); 866651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(D)) 867651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Walker.VisitFunctionDecl(FD); 868651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines else if (const ObjCMethodDecl *MD = dyn_cast_or_null<ObjCMethodDecl>(D)) 869651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Walker.VisitObjCMethodDecl(MD); 870651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines else if (const BlockDecl *BD = dyn_cast_or_null<BlockDecl>(D)) 871651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Walker.VisitBlockDecl(BD); 8726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines else if (const CapturedDecl *CD = dyn_cast_or_null<CapturedDecl>(D)) 8736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Walker.VisitCapturedDecl(const_cast<CapturedDecl *>(CD)); 874651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 875651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 8766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesvoid 8776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen HinesCodeGenPGO::applyFunctionAttributes(llvm::IndexedInstrProfReader *PGOReader, 8786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines llvm::Function *Fn) { 879651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!haveRegionCounts()) 880651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return; 881651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 8826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines uint64_t MaxFunctionCount = PGOReader->getMaximumFunctionCount(); 883651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines uint64_t FunctionCount = getRegionCount(0); 884651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (FunctionCount >= (uint64_t)(0.3 * (double)MaxFunctionCount)) 885651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Turn on InlineHint attribute for hot functions. 886651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // FIXME: 30% is from preliminary tuning on SPEC, it may not be optimal. 887651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Fn->addFnAttr(llvm::Attribute::InlineHint); 888651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines else if (FunctionCount <= (uint64_t)(0.01 * (double)MaxFunctionCount)) 889651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Turn on Cold attribute for cold functions. 890651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // FIXME: 1% is from preliminary tuning on SPEC, it may not be optimal. 891651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Fn->addFnAttr(llvm::Attribute::Cold); 892651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 893651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 894651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesvoid CodeGenPGO::emitCounterVariables() { 895651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::LLVMContext &Ctx = CGM.getLLVMContext(); 896651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::ArrayType *CounterTy = llvm::ArrayType::get(llvm::Type::getInt64Ty(Ctx), 897651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines NumRegionCounters); 898651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounters = 899651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines new llvm::GlobalVariable(CGM.getModule(), CounterTy, false, VarLinkage, 900651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::Constant::getNullValue(CounterTy), 901651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines getFuncVarName("counters")); 902651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounters->setAlignment(8); 903651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounters->setSection(getCountersSection(CGM)); 904651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 905651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 906651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesvoid CodeGenPGO::emitCounterIncrement(CGBuilderTy &Builder, unsigned Counter) { 907651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!RegionCounters) 908651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return; 909651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::Value *Addr = 910651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Builder.CreateConstInBoundsGEP2_64(RegionCounters, 0, Counter); 911651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::Value *Count = Builder.CreateLoad(Addr, "pgocount"); 912651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Count = Builder.CreateAdd(Count, Builder.getInt64(1)); 913651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines Builder.CreateStore(Count, Addr); 914651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 915651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 916ef8225444452a1486bd721f3285301fe84643b00Stephen Hinesvoid CodeGenPGO::loadRegionCounts(llvm::IndexedInstrProfReader *PGOReader, 917ef8225444452a1486bd721f3285301fe84643b00Stephen Hines bool IsInMainFile) { 918ef8225444452a1486bd721f3285301fe84643b00Stephen Hines CGM.getPGOStats().addVisited(IsInMainFile); 919651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounts.reset(new std::vector<uint64_t>); 920651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines uint64_t Hash; 9216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (PGOReader->getFunctionCounts(getFuncName(), Hash, *RegionCounts)) { 922ef8225444452a1486bd721f3285301fe84643b00Stephen Hines CGM.getPGOStats().addMissing(IsInMainFile); 9236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines RegionCounts.reset(); 9246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } else if (Hash != FunctionHash || 9256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines RegionCounts->size() != NumRegionCounters) { 926ef8225444452a1486bd721f3285301fe84643b00Stephen Hines CGM.getPGOStats().addMismatched(IsInMainFile); 927651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounts.reset(); 9286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 929651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 930651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 931651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesvoid CodeGenPGO::destroyRegionCounters() { 932651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounterMap.reset(); 933651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines StmtCountMap.reset(); 934651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounts.reset(); 9356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines RegionCounters = nullptr; 936651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 937651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 938651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// \brief Calculate what to divide by to scale weights. 939651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// 940651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// Given the maximum weight, calculate a divisor that will scale all the 941651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// weights to strictly less than UINT32_MAX. 942651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesstatic uint64_t calculateWeightScale(uint64_t MaxWeight) { 943651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return MaxWeight < UINT32_MAX ? 1 : MaxWeight / UINT32_MAX + 1; 944651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 945651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 946651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// \brief Scale an individual branch weight (and add 1). 947651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// 948651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// Scale a 64-bit weight down to 32-bits using \c Scale. 949651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// 950651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// According to Laplace's Rule of Succession, it is better to compute the 951651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// weight based on the count plus 1, so universally add 1 to the value. 952651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// 953651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// \pre \c Scale was calculated by \a calculateWeightScale() with a weight no 954651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines/// greater than \c Weight. 955651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesstatic uint32_t scaleBranchWeight(uint64_t Weight, uint64_t Scale) { 956651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines assert(Scale && "scale by 0?"); 957651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines uint64_t Scaled = Weight / Scale + 1; 958651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines assert(Scaled <= UINT32_MAX && "overflow 32-bits"); 959651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return Scaled; 960651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 961651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 962651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesllvm::MDNode *CodeGenPGO::createBranchWeights(uint64_t TrueCount, 963651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines uint64_t FalseCount) { 964651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Check for empty weights. 965651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!TrueCount && !FalseCount) 966651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return nullptr; 967651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 968651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Calculate how to scale down to 32-bits. 969651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines uint64_t Scale = calculateWeightScale(std::max(TrueCount, FalseCount)); 970651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 971651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::MDBuilder MDHelper(CGM.getLLVMContext()); 972651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return MDHelper.createBranchWeights(scaleBranchWeight(TrueCount, Scale), 973651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines scaleBranchWeight(FalseCount, Scale)); 974651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 975651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 976651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesllvm::MDNode *CodeGenPGO::createBranchWeights(ArrayRef<uint64_t> Weights) { 977651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // We need at least two elements to create meaningful weights. 978651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (Weights.size() < 2) 979651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return nullptr; 980651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 9816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Check for empty weights. 9826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines uint64_t MaxWeight = *std::max_element(Weights.begin(), Weights.end()); 9836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (MaxWeight == 0) 9846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 9856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 986651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines // Calculate how to scale down to 32-bits. 9876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines uint64_t Scale = calculateWeightScale(MaxWeight); 988651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 989651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines SmallVector<uint32_t, 16> ScaledWeights; 990651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines ScaledWeights.reserve(Weights.size()); 991651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (uint64_t W : Weights) 992651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines ScaledWeights.push_back(scaleBranchWeight(W, Scale)); 993651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 994651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines llvm::MDBuilder MDHelper(CGM.getLLVMContext()); 995651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return MDHelper.createBranchWeights(ScaledWeights); 996651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 997651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 998651f13cea278ec967336033dd032faef0e9fc2ecStephen Hinesllvm::MDNode *CodeGenPGO::createLoopWeights(const Stmt *Cond, 999651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines RegionCounter &Cnt) { 1000651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!haveRegionCounts()) 1001651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return nullptr; 1002651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines uint64_t LoopCount = Cnt.getCount(); 1003651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines uint64_t CondCount = 0; 1004651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines bool Found = getStmtCount(Cond, CondCount); 1005651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines assert(Found && "missing expected loop condition count"); 1006651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines (void)Found; 1007651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (CondCount == 0) 1008651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return nullptr; 1009651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return createBranchWeights(LoopCount, 1010651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines std::max(CondCount, LoopCount) - LoopCount); 1011651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines} 1012