This is an archive of the discontinued LLVM Phabricator instance.

Split PGO memory intrinsic optimization into its own source file
ClosedPublic

Authored by tejohnson on Jun 15 2017, 1:19 PM.

Download Raw Diff

Details

Reviewers

Commits

rG152277952e6f: Split PGO memory intrinsic optimization into its own source file
rL305501: Split PGO memory intrinsic optimization into its own source file

Summary

Split the PGOMemOPSizeOpt pass out from IndirectCallPromotion.cpp into
its own file.

Diff Detail

Build Status

Buildable 7280
Build 7280: arc lint + arc unit

Event Timeline

tejohnson created this revision.Jun 15 2017, 1:19 PM

Herald added a subscriber: mgorny. · View Herald TranscriptJun 15 2017, 1:19 PM

lgtm

This revision is now accepted and ready to land.Jun 15 2017, 1:22 PM

Closed by commit rL305501: Split PGO memory intrinsic optimization into its own source file (authored by tejohnson). · Explain WhyJun 15 2017, 1:24 PM

This revision was automatically updated to reflect the committed changes.

Revision Contents

Path

Size

lib/

Transforms/

Instrumentation/

CMakeLists.txt

1 line

IndirectCallPromotion.cpp

361 lines

PGOMemOPSizeOpt.cpp

419 lines

Diff 102714

lib/Transforms/Instrumentation/CMakeLists.txt

	add_llvm_library(LLVMInstrumentation			add_llvm_library(LLVMInstrumentation
	AddressSanitizer.cpp			AddressSanitizer.cpp
	BoundsChecking.cpp			BoundsChecking.cpp
	DataFlowSanitizer.cpp			DataFlowSanitizer.cpp
	GCOVProfiling.cpp			GCOVProfiling.cpp
	MemorySanitizer.cpp			MemorySanitizer.cpp
	IndirectCallPromotion.cpp			IndirectCallPromotion.cpp
	Instrumentation.cpp			Instrumentation.cpp
	InstrProfiling.cpp			InstrProfiling.cpp
	PGOInstrumentation.cpp			PGOInstrumentation.cpp
				PGOMemOPSizeOpt.cpp
	SanitizerCoverage.cpp			SanitizerCoverage.cpp
	ThreadSanitizer.cpp			ThreadSanitizer.cpp
	EfficiencySanitizer.cpp			EfficiencySanitizer.cpp

	ADDITIONAL_HEADER_DIRS			ADDITIONAL_HEADER_DIRS
	${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms			${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms

	DEPENDS			DEPENDS
	intrinsics_gen			intrinsics_gen
	)			)

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

Show First 20 Lines • Show All 50 Lines • ▼ Show 20 Lines
#include <vector>		#include <vector>

using namespace llvm;		using namespace llvm;

#define DEBUG_TYPE "pgo-icall-prom"		#define DEBUG_TYPE "pgo-icall-prom"

STATISTIC(NumOfPGOICallPromotion, "Number of indirect call promotions.");		STATISTIC(NumOfPGOICallPromotion, "Number of indirect call promotions.");
STATISTIC(NumOfPGOICallsites, "Number of indirect call candidate sites.");		STATISTIC(NumOfPGOICallsites, "Number of indirect call candidate sites.");
STATISTIC(NumOfPGOMemOPOpt, "Number of memop intrinsics optimized.");
STATISTIC(NumOfPGOMemOPAnnotate, "Number of memop intrinsics annotated.");

// Command line option to disable indirect-call promotion with the default as		// Command line option to disable indirect-call promotion with the default as
// false. This is for debug purpose.		// false. This is for debug purpose.
static cl::opt<bool> DisableICP("disable-icp", cl::init(false), cl::Hidden,		static cl::opt<bool> DisableICP("disable-icp", cl::init(false), cl::Hidden,
cl::desc("Disable indirect call promotion"));		cl::desc("Disable indirect call promotion"));

// Set the cutoff value for the promotion. If the value is other than 0, we		// Set the cutoff value for the promotion. If the value is other than 0, we
// stop the transformation once the total number of promotions equals the cutoff		// stop the transformation once the total number of promotions equals the cutoff
Show All 37 Lines	static cl::opt<bool> ICPInvokeOnly("icp-invoke-only", cl::init(false),
"invoke instruction only"));		"invoke instruction only"));

// Dump the function level IR if the transformation happened in this		// Dump the function level IR if the transformation happened in this
// function. For debug use only.		// function. For debug use only.
static cl::opt<bool>		static cl::opt<bool>
ICPDUMPAFTER("icp-dumpafter", cl::init(false), cl::Hidden,		ICPDUMPAFTER("icp-dumpafter", cl::init(false), cl::Hidden,
cl::desc("Dump IR after transformation happens"));		cl::desc("Dump IR after transformation happens"));

// The minimum call count to optimize memory intrinsic calls.
static cl::opt<unsigned>
MemOPCountThreshold("pgo-memop-count-threshold", cl::Hidden, cl::ZeroOrMore,
cl::init(1000),
cl::desc("The minimum count to optimize memory "
"intrinsic calls"));

// Command line option to disable memory intrinsic optimization. The default is
// false. This is for debug purpose.
static cl::opt<bool> DisableMemOPOPT("disable-memop-opt", cl::init(false),
cl::Hidden, cl::desc("Disable optimize"));

// The percent threshold to optimize memory intrinsic calls.
static cl::opt<unsigned>
MemOPPercentThreshold("pgo-memop-percent-threshold", cl::init(40),
cl::Hidden, cl::ZeroOrMore,
cl::desc("The percentage threshold for the "
"memory intrinsic calls optimization"));

// Maximum number of versions for optimizing memory intrinsic call.
static cl::opt<unsigned>
MemOPMaxVersion("pgo-memop-max-version", cl::init(3), cl::Hidden,
cl::ZeroOrMore,
cl::desc("The max version for the optimized memory "
" intrinsic calls"));

// Scale the counts from the annotation using the BB count value.
static cl::opt<bool>
MemOPScaleCount("pgo-memop-scale-count", cl::init(true), cl::Hidden,
cl::desc("Scale the memop size counts using the basic "
" block count value"));

// This option sets the rangge of precise profile memop sizes.
extern cl::opt<std::string> MemOPSizeRange;

// This option sets the value that groups large memop sizes
extern cl::opt<unsigned> MemOPSizeLarge;

namespace {		namespace {
class PGOIndirectCallPromotionLegacyPass : public ModulePass {		class PGOIndirectCallPromotionLegacyPass : public ModulePass {
public:		public:
static char ID;		static char ID;

PGOIndirectCallPromotionLegacyPass(bool InLTO = false, bool SamplePGO = false)		PGOIndirectCallPromotionLegacyPass(bool InLTO = false, bool SamplePGO = false)
: ModulePass(ID), InLTO(InLTO), SamplePGO(SamplePGO) {		: ModulePass(ID), InLTO(InLTO), SamplePGO(SamplePGO) {
initializePGOIndirectCallPromotionLegacyPassPass(		initializePGOIndirectCallPromotionLegacyPassPass(
*PassRegistry::getPassRegistry());		*PassRegistry::getPassRegistry());
}		}

StringRef getPassName() const override { return "PGOIndirectCallPromotion"; }		StringRef getPassName() const override { return "PGOIndirectCallPromotion"; }

private:		private:
bool runOnModule(Module &M) override;		bool runOnModule(Module &M) override;

// If this pass is called in LTO. We need to special handling the PGOFuncName		// If this pass is called in LTO. We need to special handling the PGOFuncName
// for the static variables due to LTO's internalization.		// for the static variables due to LTO's internalization.
bool InLTO;		bool InLTO;

// If this pass is called in SamplePGO. We need to add the prof metadata to		// If this pass is called in SamplePGO. We need to add the prof metadata to
// the promoted direct call.		// the promoted direct call.
bool SamplePGO;		bool SamplePGO;
};		};

class PGOMemOPSizeOptLegacyPass : public FunctionPass {
public:
static char ID;

PGOMemOPSizeOptLegacyPass() : FunctionPass(ID) {
initializePGOMemOPSizeOptLegacyPassPass(*PassRegistry::getPassRegistry());
}

StringRef getPassName() const override { return "PGOMemOPSize"; }

private:
bool runOnFunction(Function &F) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<BlockFrequencyInfoWrapperPass>();
AU.addPreserved<GlobalsAAWrapperPass>();
}
};
} // end anonymous namespace		} // end anonymous namespace

char PGOIndirectCallPromotionLegacyPass::ID = 0;		char PGOIndirectCallPromotionLegacyPass::ID = 0;
INITIALIZE_PASS(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom",		INITIALIZE_PASS(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom",
"Use PGO instrumentation profile to promote indirect calls to "		"Use PGO instrumentation profile to promote indirect calls to "
"direct calls.",		"direct calls.",
false, false)		false, false)

ModulePass *llvm::createPGOIndirectCallPromotionLegacyPass(bool InLTO,		ModulePass *llvm::createPGOIndirectCallPromotionLegacyPass(bool InLTO,
bool SamplePGO) {		bool SamplePGO) {
return new PGOIndirectCallPromotionLegacyPass(InLTO, SamplePGO);		return new PGOIndirectCallPromotionLegacyPass(InLTO, SamplePGO);
}		}

char PGOMemOPSizeOptLegacyPass::ID = 0;
INITIALIZE_PASS_BEGIN(PGOMemOPSizeOptLegacyPass, "pgo-memop-opt",
"Optimize memory intrinsic using its size value profile",
false, false)
INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
INITIALIZE_PASS_END(PGOMemOPSizeOptLegacyPass, "pgo-memop-opt",
"Optimize memory intrinsic using its size value profile",
false, false)

FunctionPass *llvm::createPGOMemOPSizeOptLegacyPass() {
return new PGOMemOPSizeOptLegacyPass();
}

namespace {		namespace {
// The class for main data structure to promote indirect calls to conditional		// The class for main data structure to promote indirect calls to conditional
// direct calls.		// direct calls.
class ICallPromotionFunc {		class ICallPromotionFunc {
private:		private:
Function &F;		Function &F;
Module *M;		Module *M;

▲ Show 20 Lines • Show All 516 Lines • ▼ Show 20 Lines
PreservedAnalyses PGOIndirectCallPromotion::run(Module &M,		PreservedAnalyses PGOIndirectCallPromotion::run(Module &M,
ModuleAnalysisManager &AM) {		ModuleAnalysisManager &AM) {
if (!promoteIndirectCalls(M, InLTO \| ICPLTOMode,		if (!promoteIndirectCalls(M, InLTO \| ICPLTOMode,
SamplePGO \| ICPSamplePGOMode))		SamplePGO \| ICPSamplePGOMode))
return PreservedAnalyses::all();		return PreservedAnalyses::all();

return PreservedAnalyses::none();		return PreservedAnalyses::none();
}		}

namespace {
class MemOPSizeOpt : public InstVisitor<MemOPSizeOpt> {
public:
MemOPSizeOpt(Function &Func, BlockFrequencyInfo &BFI)
: Func(Func), BFI(BFI), Changed(false) {
ValueDataArray =
llvm::make_unique<InstrProfValueData[]>(MemOPMaxVersion + 2);
// Get the MemOPSize range information from option MemOPSizeRange,
getMemOPSizeRangeFromOption(MemOPSizeRange, PreciseRangeStart,
PreciseRangeLast);
}
bool isChanged() const { return Changed; }
void perform() {
WorkList.clear();
visit(Func);

for (auto &MI : WorkList) {
++NumOfPGOMemOPAnnotate;
if (perform(MI)) {
Changed = true;
++NumOfPGOMemOPOpt;
DEBUG(dbgs() << "MemOP call: " << MI->getCalledFunction()->getName()
<< "is Transformed.\n");
}
}
}

void visitMemIntrinsic(MemIntrinsic &MI) {
Value *Length = MI.getLength();
// Not perform on constant length calls.
if (dyn_cast<ConstantInt>(Length))
return;
WorkList.push_back(&MI);
}

private:
Function &Func;
BlockFrequencyInfo &BFI;
bool Changed;
std::vector<MemIntrinsic *> WorkList;
// Start of the previse range.
int64_t PreciseRangeStart;
// Last value of the previse range.
int64_t PreciseRangeLast;
// The space to read the profile annotation.
std::unique_ptr<InstrProfValueData[]> ValueDataArray;
bool perform(MemIntrinsic *MI);

// This kind shows which group the value falls in. For PreciseValue, we have
// the profile count for that value. LargeGroup groups the values that are in
// range [LargeValue, +inf). NonLargeGroup groups the rest of values.
enum MemOPSizeKind { PreciseValue, NonLargeGroup, LargeGroup };

MemOPSizeKind getMemOPSizeKind(int64_t Value) const {
if (Value == MemOPSizeLarge && MemOPSizeLarge != 0)
return LargeGroup;
if (Value == PreciseRangeLast + 1)
return NonLargeGroup;
return PreciseValue;
}
};

static const char getMIName(const MemIntrinsic MI) {
switch (MI->getIntrinsicID()) {
case Intrinsic::memcpy:
return "memcpy";
case Intrinsic::memmove:
return "memmove";
case Intrinsic::memset:
return "memset";
default:
return "unknown";
}
}

static bool isProfitable(uint64_t Count, uint64_t TotalCount) {
assert(Count <= TotalCount);
if (Count < MemOPCountThreshold)
return false;
if (Count < TotalCount * MemOPPercentThreshold / 100)
return false;
return true;
}

static inline uint64_t getScaledCount(uint64_t Count, uint64_t Num,
uint64_t Denom) {
if (!MemOPScaleCount)
return Count;
bool Overflowed;
uint64_t ScaleCount = SaturatingMultiply(Count, Num, &Overflowed);
return ScaleCount / Denom;
}

bool MemOPSizeOpt::perform(MemIntrinsic *MI) {
assert(MI);
if (MI->getIntrinsicID() == Intrinsic::memmove)
return false;

uint32_t NumVals, MaxNumPromotions = MemOPMaxVersion + 2;
uint64_t TotalCount;
if (!getValueProfDataFromInst(*MI, IPVK_MemOPSize, MaxNumPromotions,
ValueDataArray.get(), NumVals, TotalCount))
return false;

uint64_t ActualCount = TotalCount;
uint64_t SavedTotalCount = TotalCount;
if (MemOPScaleCount) {
auto BBEdgeCount = BFI.getBlockProfileCount(MI->getParent());
if (!BBEdgeCount)
return false;
ActualCount = *BBEdgeCount;
}

ArrayRef<InstrProfValueData> VDs(ValueDataArray.get(), NumVals);
DEBUG(dbgs() << "Read one memory intrinsic profile with count " << ActualCount
<< "\n");
DEBUG(
for (auto &VD
: VDs) { dbgs() << " (" << VD.Value << "," << VD.Count << ")\n"; });

if (ActualCount < MemOPCountThreshold)
return false;
// Skip if the total value profiled count is 0, in which case we can't
// scale up the counts properly (and there is no profitable transformation).
if (TotalCount == 0)
return false;

TotalCount = ActualCount;
if (MemOPScaleCount)
DEBUG(dbgs() << "Scale counts: numerator = " << ActualCount
<< " denominator = " << SavedTotalCount << "\n");

// Keeping track of the count of the default case:
uint64_t RemainCount = TotalCount;
uint64_t SavedRemainCount = SavedTotalCount;
SmallVector<uint64_t, 16> SizeIds;
SmallVector<uint64_t, 16> CaseCounts;
uint64_t MaxCount = 0;
unsigned Version = 0;
// Default case is in the front -- save the slot here.
CaseCounts.push_back(0);
for (auto &VD : VDs) {
int64_t V = VD.Value;
uint64_t C = VD.Count;
if (MemOPScaleCount)
C = getScaledCount(C, ActualCount, SavedTotalCount);

// Only care precise value here.
if (getMemOPSizeKind(V) != PreciseValue)
continue;

// ValueCounts are sorted on the count. Break at the first un-profitable
// value.
if (!isProfitable(C, RemainCount))
break;

SizeIds.push_back(V);
CaseCounts.push_back(C);
if (C > MaxCount)
MaxCount = C;

assert(RemainCount >= C);
RemainCount -= C;
assert(SavedRemainCount >= VD.Count);
SavedRemainCount -= VD.Count;

if (++Version > MemOPMaxVersion && MemOPMaxVersion != 0)
break;
}

if (Version == 0)
return false;

CaseCounts[0] = RemainCount;
if (RemainCount > MaxCount)
MaxCount = RemainCount;

uint64_t SumForOpt = TotalCount - RemainCount;

DEBUG(dbgs() << "Optimize one memory intrinsic call to " << Version
<< " Versions (covering " << SumForOpt << " out of "
<< TotalCount << ")\n");

// mem_op(..., size)
// ==>
// switch (size) {
// case s1:
// mem_op(..., s1);
// goto merge_bb;
// case s2:
// mem_op(..., s2);
// goto merge_bb;
// ...
// default:
// mem_op(..., size);
// goto merge_bb;
// }
// merge_bb:

BasicBlock *BB = MI->getParent();
DEBUG(dbgs() << "\n\n== Basic Block Before ==\n");
DEBUG(dbgs() << *BB << "\n");
auto OrigBBFreq = BFI.getBlockFreq(BB);

BasicBlock *DefaultBB = SplitBlock(BB, MI);
BasicBlock::iterator It(*MI);
++It;
assert(It != DefaultBB->end());
BasicBlock MergeBB = SplitBlock(DefaultBB, &(It));
MergeBB->setName("MemOP.Merge");
BFI.setBlockFreq(MergeBB, OrigBBFreq.getFrequency());
DefaultBB->setName("MemOP.Default");

auto &Ctx = Func.getContext();
IRBuilder<> IRB(BB);
BB->getTerminator()->eraseFromParent();
Value *SizeVar = MI->getLength();
SwitchInst *SI = IRB.CreateSwitch(SizeVar, DefaultBB, SizeIds.size());

// Clear the value profile data.
MI->setMetadata(LLVMContext::MD_prof, nullptr);
// If all promoted, we don't need the MD.prof metadata.
if (SavedRemainCount > 0 \|\| Version != NumVals)
// Otherwise we need update with the un-promoted records back.
annotateValueSite(Func.getParent(), MI, VDs.slice(Version),
SavedRemainCount, IPVK_MemOPSize, NumVals);

DEBUG(dbgs() << "\n\n== Basic Block After==\n");

for (uint64_t SizeId : SizeIds) {
ConstantInt *CaseSizeId = ConstantInt::get(Type::getInt64Ty(Ctx), SizeId);
BasicBlock *CaseBB = BasicBlock::Create(
Ctx, Twine("MemOP.Case.") + Twine(SizeId), &Func, DefaultBB);
Instruction *NewInst = MI->clone();
// Fix the argument.
dyn_cast<MemIntrinsic>(NewInst)->setLength(CaseSizeId);
CaseBB->getInstList().push_back(NewInst);
IRBuilder<> IRBCase(CaseBB);
IRBCase.CreateBr(MergeBB);
SI->addCase(CaseSizeId, CaseBB);
DEBUG(dbgs() << *CaseBB << "\n");
}
setProfMetadata(Func.getParent(), SI, CaseCounts, MaxCount);

DEBUG(dbgs() << *BB << "\n");
DEBUG(dbgs() << *DefaultBB << "\n");
DEBUG(dbgs() << *MergeBB << "\n");

emitOptimizationRemark(Func.getContext(), "memop-opt", Func,
MI->getDebugLoc(),
Twine("optimize ") + getMIName(MI) + " with count " +
Twine(SumForOpt) + " out of " + Twine(TotalCount) +
" for " + Twine(Version) + " versions");

return true;
}
} // namespace

static bool PGOMemOPSizeOptImpl(Function &F, BlockFrequencyInfo &BFI) {
if (DisableMemOPOPT)
return false;

if (F.hasFnAttribute(Attribute::OptimizeForSize))
return false;
MemOPSizeOpt MemOPSizeOpt(F, BFI);
MemOPSizeOpt.perform();
return MemOPSizeOpt.isChanged();
}

bool PGOMemOPSizeOptLegacyPass::runOnFunction(Function &F) {
BlockFrequencyInfo &BFI =
getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
return PGOMemOPSizeOptImpl(F, BFI);
}

namespace llvm {
char &PGOMemOPSizeOptID = PGOMemOPSizeOptLegacyPass::ID;

PreservedAnalyses PGOMemOPSizeOpt::run(Function &F,
FunctionAnalysisManager &FAM) {
auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
bool Changed = PGOMemOPSizeOptImpl(F, BFI);
if (!Changed)
return PreservedAnalyses::all();
auto PA = PreservedAnalyses();
PA.preserve<GlobalsAA>();
return PA;
}
} // namespace llvm

lib/Transforms/Instrumentation/PGOMemOPSizeOpt.cpp

This file was added.

				//===-- PGOMemOPSizeOpt.cpp - Optimizations based on value profiling ===//
				//
				// The LLVM Compiler Infrastructure
				//
				// This file is distributed under the University of Illinois Open Source
				// License. See LICENSE.TXT for details.
				//
				//===----------------------------------------------------------------------===//
				//
				// This file implements the transformation that optimizes memory intrinsics
				// such as memcpy using the size value profile. When memory intrinsic size
				// value profile metadata is available, a single memory intrinsic is expanded
				// to a sequence of guarded specialized versions that are called with the
				// hottest size(s), for later expansion into more optimal inline sequences.
				//
				//===----------------------------------------------------------------------===//

				#include "llvm/ADT/ArrayRef.h"
				#include "llvm/ADT/Statistic.h"
				#include "llvm/ADT/StringRef.h"
				#include "llvm/ADT/Twine.h"
				#include "llvm/Analysis/BlockFrequencyInfo.h"
				#include "llvm/Analysis/GlobalsModRef.h"
				#include "llvm/IR/BasicBlock.h"
				#include "llvm/IR/CallSite.h"
				#include "llvm/IR/DerivedTypes.h"
				#include "llvm/IR/DiagnosticInfo.h"
				#include "llvm/IR/Function.h"
				#include "llvm/IR/IRBuilder.h"
				#include "llvm/IR/InstrTypes.h"
				#include "llvm/IR/Instruction.h"
				#include "llvm/IR/Instructions.h"
				#include "llvm/IR/InstVisitor.h"
				#include "llvm/IR/LLVMContext.h"
				#include "llvm/IR/PassManager.h"
				#include "llvm/IR/Type.h"
				#include "llvm/Pass.h"
				#include "llvm/PassRegistry.h"
				#include "llvm/PassSupport.h"
				#include "llvm/ProfileData/InstrProf.h"
				#include "llvm/Support/Casting.h"
				#include "llvm/Support/CommandLine.h"
				#include "llvm/Support/Debug.h"
				#include "llvm/Support/ErrorHandling.h"
				#include "llvm/Support/MathExtras.h"
				#include "llvm/Transforms/Instrumentation.h"
				#include "llvm/Transforms/PGOInstrumentation.h"
				#include "llvm/Transforms/Utils/BasicBlockUtils.h"
				#include <cassert>
				#include <cstdint>
				#include <vector>

				using namespace llvm;

				#define DEBUG_TYPE "pgo-memop-opt"

				STATISTIC(NumOfPGOMemOPOpt, "Number of memop intrinsics optimized.");
				STATISTIC(NumOfPGOMemOPAnnotate, "Number of memop intrinsics annotated.");

				// The minimum call count to optimize memory intrinsic calls.
				static cl::opt<unsigned>
				MemOPCountThreshold("pgo-memop-count-threshold", cl::Hidden, cl::ZeroOrMore,
				cl::init(1000),
				cl::desc("The minimum count to optimize memory "
				"intrinsic calls"));

				// Command line option to disable memory intrinsic optimization. The default is
				// false. This is for debug purpose.
				static cl::opt<bool> DisableMemOPOPT("disable-memop-opt", cl::init(false),
				cl::Hidden, cl::desc("Disable optimize"));

				// The percent threshold to optimize memory intrinsic calls.
				static cl::opt<unsigned>
				MemOPPercentThreshold("pgo-memop-percent-threshold", cl::init(40),
				cl::Hidden, cl::ZeroOrMore,
				cl::desc("The percentage threshold for the "
				"memory intrinsic calls optimization"));

				// Maximum number of versions for optimizing memory intrinsic call.
				static cl::opt<unsigned>
				MemOPMaxVersion("pgo-memop-max-version", cl::init(3), cl::Hidden,
				cl::ZeroOrMore,
				cl::desc("The max version for the optimized memory "
				" intrinsic calls"));

				// Scale the counts from the annotation using the BB count value.
				static cl::opt<bool>
				MemOPScaleCount("pgo-memop-scale-count", cl::init(true), cl::Hidden,
				cl::desc("Scale the memop size counts using the basic "
				" block count value"));

				// This option sets the rangge of precise profile memop sizes.
				extern cl::opt<std::string> MemOPSizeRange;

				// This option sets the value that groups large memop sizes
				extern cl::opt<unsigned> MemOPSizeLarge;

				namespace {
				class PGOMemOPSizeOptLegacyPass : public FunctionPass {
				public:
				static char ID;

				PGOMemOPSizeOptLegacyPass() : FunctionPass(ID) {
				initializePGOMemOPSizeOptLegacyPassPass(*PassRegistry::getPassRegistry());
				}

				StringRef getPassName() const override { return "PGOMemOPSize"; }

				private:
				bool runOnFunction(Function &F) override;
				void getAnalysisUsage(AnalysisUsage &AU) const override {
				AU.addRequired<BlockFrequencyInfoWrapperPass>();
				AU.addPreserved<GlobalsAAWrapperPass>();
				}
				};
				} // end anonymous namespace

				char PGOMemOPSizeOptLegacyPass::ID = 0;
				INITIALIZE_PASS_BEGIN(PGOMemOPSizeOptLegacyPass, "pgo-memop-opt",
				"Optimize memory intrinsic using its size value profile",
				false, false)
				INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
				INITIALIZE_PASS_END(PGOMemOPSizeOptLegacyPass, "pgo-memop-opt",
				"Optimize memory intrinsic using its size value profile",
				false, false)

				FunctionPass *llvm::createPGOMemOPSizeOptLegacyPass() {
				return new PGOMemOPSizeOptLegacyPass();
				}

				namespace {
				class MemOPSizeOpt : public InstVisitor<MemOPSizeOpt> {
				public:
				MemOPSizeOpt(Function &Func, BlockFrequencyInfo &BFI)
				: Func(Func), BFI(BFI), Changed(false) {
				ValueDataArray =
				llvm::make_unique<InstrProfValueData[]>(MemOPMaxVersion + 2);
				// Get the MemOPSize range information from option MemOPSizeRange,
				getMemOPSizeRangeFromOption(MemOPSizeRange, PreciseRangeStart,
				PreciseRangeLast);
				}
				bool isChanged() const { return Changed; }
				void perform() {
				WorkList.clear();
				visit(Func);

				for (auto &MI : WorkList) {
				++NumOfPGOMemOPAnnotate;
				if (perform(MI)) {
				Changed = true;
				++NumOfPGOMemOPOpt;
				DEBUG(dbgs() << "MemOP call: " << MI->getCalledFunction()->getName()
				<< "is Transformed.\n");
				}
				}
				}

				void visitMemIntrinsic(MemIntrinsic &MI) {
				Value *Length = MI.getLength();
				// Not perform on constant length calls.
				if (dyn_cast<ConstantInt>(Length))
				return;
				WorkList.push_back(&MI);
				}

				private:
				Function &Func;
				BlockFrequencyInfo &BFI;
				bool Changed;
				std::vector<MemIntrinsic *> WorkList;
				// Start of the previse range.
				int64_t PreciseRangeStart;
				// Last value of the previse range.
				int64_t PreciseRangeLast;
				// The space to read the profile annotation.
				std::unique_ptr<InstrProfValueData[]> ValueDataArray;
				bool perform(MemIntrinsic *MI);

				// This kind shows which group the value falls in. For PreciseValue, we have
				// the profile count for that value. LargeGroup groups the values that are in
				// range [LargeValue, +inf). NonLargeGroup groups the rest of values.
				enum MemOPSizeKind { PreciseValue, NonLargeGroup, LargeGroup };

				MemOPSizeKind getMemOPSizeKind(int64_t Value) const {
				if (Value == MemOPSizeLarge && MemOPSizeLarge != 0)
				return LargeGroup;
				if (Value == PreciseRangeLast + 1)
				return NonLargeGroup;
				return PreciseValue;
				}
				};

				static const char getMIName(const MemIntrinsic MI) {
				switch (MI->getIntrinsicID()) {
				case Intrinsic::memcpy:
				return "memcpy";
				case Intrinsic::memmove:
				return "memmove";
				case Intrinsic::memset:
				return "memset";
				default:
				return "unknown";
				}
				}

				static bool isProfitable(uint64_t Count, uint64_t TotalCount) {
				assert(Count <= TotalCount);
				if (Count < MemOPCountThreshold)
				return false;
				if (Count < TotalCount * MemOPPercentThreshold / 100)
				return false;
				return true;
				}

				static inline uint64_t getScaledCount(uint64_t Count, uint64_t Num,
				uint64_t Denom) {
				if (!MemOPScaleCount)
				return Count;
				bool Overflowed;
				uint64_t ScaleCount = SaturatingMultiply(Count, Num, &Overflowed);
				return ScaleCount / Denom;
				}

				bool MemOPSizeOpt::perform(MemIntrinsic *MI) {
				assert(MI);
				if (MI->getIntrinsicID() == Intrinsic::memmove)
				return false;

				uint32_t NumVals, MaxNumPromotions = MemOPMaxVersion + 2;
				uint64_t TotalCount;
				if (!getValueProfDataFromInst(*MI, IPVK_MemOPSize, MaxNumPromotions,
				ValueDataArray.get(), NumVals, TotalCount))
				return false;

				uint64_t ActualCount = TotalCount;
				uint64_t SavedTotalCount = TotalCount;
				if (MemOPScaleCount) {
				auto BBEdgeCount = BFI.getBlockProfileCount(MI->getParent());
				if (!BBEdgeCount)
				return false;
				ActualCount = *BBEdgeCount;
				}

				ArrayRef<InstrProfValueData> VDs(ValueDataArray.get(), NumVals);
				DEBUG(dbgs() << "Read one memory intrinsic profile with count " << ActualCount
				<< "\n");
				DEBUG(
				for (auto &VD
				: VDs) { dbgs() << " (" << VD.Value << "," << VD.Count << ")\n"; });

				if (ActualCount < MemOPCountThreshold)
				return false;
				// Skip if the total value profiled count is 0, in which case we can't
				// scale up the counts properly (and there is no profitable transformation).
				if (TotalCount == 0)
				return false;

				TotalCount = ActualCount;
				if (MemOPScaleCount)
				DEBUG(dbgs() << "Scale counts: numerator = " << ActualCount
				<< " denominator = " << SavedTotalCount << "\n");

				// Keeping track of the count of the default case:
				uint64_t RemainCount = TotalCount;
				uint64_t SavedRemainCount = SavedTotalCount;
				SmallVector<uint64_t, 16> SizeIds;
				SmallVector<uint64_t, 16> CaseCounts;
				uint64_t MaxCount = 0;
				unsigned Version = 0;
				// Default case is in the front -- save the slot here.
				CaseCounts.push_back(0);
				for (auto &VD : VDs) {
				int64_t V = VD.Value;
				uint64_t C = VD.Count;
				if (MemOPScaleCount)
				C = getScaledCount(C, ActualCount, SavedTotalCount);

				// Only care precise value here.
				if (getMemOPSizeKind(V) != PreciseValue)
				continue;

				// ValueCounts are sorted on the count. Break at the first un-profitable
				// value.
				if (!isProfitable(C, RemainCount))
				break;

				SizeIds.push_back(V);
				CaseCounts.push_back(C);
				if (C > MaxCount)
				MaxCount = C;

				assert(RemainCount >= C);
				RemainCount -= C;
				assert(SavedRemainCount >= VD.Count);
				SavedRemainCount -= VD.Count;

				if (++Version > MemOPMaxVersion && MemOPMaxVersion != 0)
				break;
				}

				if (Version == 0)
				return false;

				CaseCounts[0] = RemainCount;
				if (RemainCount > MaxCount)
				MaxCount = RemainCount;

				uint64_t SumForOpt = TotalCount - RemainCount;

				DEBUG(dbgs() << "Optimize one memory intrinsic call to " << Version
				<< " Versions (covering " << SumForOpt << " out of "
				<< TotalCount << ")\n");

				// mem_op(..., size)
				// ==>
				// switch (size) {
				// case s1:
				// mem_op(..., s1);
				// goto merge_bb;
				// case s2:
				// mem_op(..., s2);
				// goto merge_bb;
				// ...
				// default:
				// mem_op(..., size);
				// goto merge_bb;
				// }
				// merge_bb:

				BasicBlock *BB = MI->getParent();
				DEBUG(dbgs() << "\n\n== Basic Block Before ==\n");
				DEBUG(dbgs() << *BB << "\n");
				auto OrigBBFreq = BFI.getBlockFreq(BB);

				BasicBlock *DefaultBB = SplitBlock(BB, MI);
				BasicBlock::iterator It(*MI);
				++It;
				assert(It != DefaultBB->end());
				BasicBlock MergeBB = SplitBlock(DefaultBB, &(It));
				MergeBB->setName("MemOP.Merge");
				BFI.setBlockFreq(MergeBB, OrigBBFreq.getFrequency());
				DefaultBB->setName("MemOP.Default");

				auto &Ctx = Func.getContext();
				IRBuilder<> IRB(BB);
				BB->getTerminator()->eraseFromParent();
				Value *SizeVar = MI->getLength();
				SwitchInst *SI = IRB.CreateSwitch(SizeVar, DefaultBB, SizeIds.size());

				// Clear the value profile data.
				MI->setMetadata(LLVMContext::MD_prof, nullptr);
				// If all promoted, we don't need the MD.prof metadata.
				if (SavedRemainCount > 0 \|\| Version != NumVals)
				// Otherwise we need update with the un-promoted records back.
				annotateValueSite(Func.getParent(), MI, VDs.slice(Version),
				SavedRemainCount, IPVK_MemOPSize, NumVals);

				DEBUG(dbgs() << "\n\n== Basic Block After==\n");

				for (uint64_t SizeId : SizeIds) {
				ConstantInt *CaseSizeId = ConstantInt::get(Type::getInt64Ty(Ctx), SizeId);
				BasicBlock *CaseBB = BasicBlock::Create(
				Ctx, Twine("MemOP.Case.") + Twine(SizeId), &Func, DefaultBB);
				Instruction *NewInst = MI->clone();
				// Fix the argument.
				dyn_cast<MemIntrinsic>(NewInst)->setLength(CaseSizeId);
				CaseBB->getInstList().push_back(NewInst);
				IRBuilder<> IRBCase(CaseBB);
				IRBCase.CreateBr(MergeBB);
				SI->addCase(CaseSizeId, CaseBB);
				DEBUG(dbgs() << *CaseBB << "\n");
				}
				setProfMetadata(Func.getParent(), SI, CaseCounts, MaxCount);

				DEBUG(dbgs() << *BB << "\n");
				DEBUG(dbgs() << *DefaultBB << "\n");
				DEBUG(dbgs() << *MergeBB << "\n");

				emitOptimizationRemark(Func.getContext(), "memop-opt", Func,
				MI->getDebugLoc(),
				Twine("optimize ") + getMIName(MI) + " with count " +
				Twine(SumForOpt) + " out of " + Twine(TotalCount) +
				" for " + Twine(Version) + " versions");

				return true;
				}
				} // namespace

				static bool PGOMemOPSizeOptImpl(Function &F, BlockFrequencyInfo &BFI) {
				if (DisableMemOPOPT)
				return false;

				if (F.hasFnAttribute(Attribute::OptimizeForSize))
				return false;
				MemOPSizeOpt MemOPSizeOpt(F, BFI);
				MemOPSizeOpt.perform();
				return MemOPSizeOpt.isChanged();
				}

				bool PGOMemOPSizeOptLegacyPass::runOnFunction(Function &F) {
				BlockFrequencyInfo &BFI =
				getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
				return PGOMemOPSizeOptImpl(F, BFI);
				}

				namespace llvm {
				char &PGOMemOPSizeOptID = PGOMemOPSizeOptLegacyPass::ID;

				PreservedAnalyses PGOMemOPSizeOpt::run(Function &F,
				FunctionAnalysisManager &FAM) {
				auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
				bool Changed = PGOMemOPSizeOptImpl(F, BFI);
				if (!Changed)
				return PreservedAnalyses::all();
				auto PA = PreservedAnalyses();
				PA.preserve<GlobalsAA>();
				return PA;
				}
				} // namespace llvm