1 //===-- PGOMemOPSizeOpt.cpp - Optimizations based on value profiling ===//
2 //
3 //                      The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the transformation that optimizes memory intrinsics
11 // such as memcpy using the size value profile. When memory intrinsic size
12 // value profile metadata is available, a single memory intrinsic is expanded
13 // to a sequence of guarded specialized versions that are called with the
14 // hottest size(s), for later expansion into more optimal inline sequences.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/ADT/Twine.h"
22 #include "llvm/Analysis/BlockFrequencyInfo.h"
23 #include "llvm/Analysis/GlobalsModRef.h"
24 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
25 #include "llvm/IR/BasicBlock.h"
26 #include "llvm/IR/CallSite.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/Function.h"
29 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/InstVisitor.h"
31 #include "llvm/IR/InstrTypes.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/LLVMContext.h"
35 #include "llvm/IR/PassManager.h"
36 #include "llvm/IR/Type.h"
37 #include "llvm/Pass.h"
38 #include "llvm/PassRegistry.h"
39 #include "llvm/PassSupport.h"
40 #include "llvm/ProfileData/InstrProf.h"
41 #include "llvm/Support/Casting.h"
42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Support/Debug.h"
44 #include "llvm/Support/ErrorHandling.h"
45 #include "llvm/Support/MathExtras.h"
46 #include "llvm/Transforms/Instrumentation.h"
47 #include "llvm/Transforms/Instrumentation/PGOInstrumentation.h"
48 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
49 #include <cassert>
50 #include <cstdint>
51 #include <vector>
52 
53 using namespace llvm;
54 
55 #define DEBUG_TYPE "pgo-memop-opt"
56 
57 STATISTIC(NumOfPGOMemOPOpt, "Number of memop intrinsics optimized.");
58 STATISTIC(NumOfPGOMemOPAnnotate, "Number of memop intrinsics annotated.");
59 
60 // The minimum call count to optimize memory intrinsic calls.
61 static cl::opt<unsigned>
62     MemOPCountThreshold("pgo-memop-count-threshold", cl::Hidden, cl::ZeroOrMore,
63                         cl::init(1000),
64                         cl::desc("The minimum count to optimize memory "
65                                  "intrinsic calls"));
66 
67 // Command line option to disable memory intrinsic optimization. The default is
68 // false. This is for debug purpose.
69 static cl::opt<bool> DisableMemOPOPT("disable-memop-opt", cl::init(false),
70                                      cl::Hidden, cl::desc("Disable optimize"));
71 
72 // The percent threshold to optimize memory intrinsic calls.
73 static cl::opt<unsigned>
74     MemOPPercentThreshold("pgo-memop-percent-threshold", cl::init(40),
75                           cl::Hidden, cl::ZeroOrMore,
76                           cl::desc("The percentage threshold for the "
77                                    "memory intrinsic calls optimization"));
78 
79 // Maximum number of versions for optimizing memory intrinsic call.
80 static cl::opt<unsigned>
81     MemOPMaxVersion("pgo-memop-max-version", cl::init(3), cl::Hidden,
82                     cl::ZeroOrMore,
83                     cl::desc("The max version for the optimized memory "
84                              " intrinsic calls"));
85 
86 // Scale the counts from the annotation using the BB count value.
87 static cl::opt<bool>
88     MemOPScaleCount("pgo-memop-scale-count", cl::init(true), cl::Hidden,
89                     cl::desc("Scale the memop size counts using the basic "
90                              " block count value"));
91 
92 // This option sets the rangge of precise profile memop sizes.
93 extern cl::opt<std::string> MemOPSizeRange;
94 
95 // This option sets the value that groups large memop sizes
96 extern cl::opt<unsigned> MemOPSizeLarge;
97 
98 namespace {
99 class PGOMemOPSizeOptLegacyPass : public FunctionPass {
100 public:
101   static char ID;
102 
103   PGOMemOPSizeOptLegacyPass() : FunctionPass(ID) {
104     initializePGOMemOPSizeOptLegacyPassPass(*PassRegistry::getPassRegistry());
105   }
106 
107   StringRef getPassName() const override { return "PGOMemOPSize"; }
108 
109 private:
110   bool runOnFunction(Function &F) override;
111   void getAnalysisUsage(AnalysisUsage &AU) const override {
112     AU.addRequired<BlockFrequencyInfoWrapperPass>();
113     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
114     AU.addPreserved<GlobalsAAWrapperPass>();
115   }
116 };
117 } // end anonymous namespace
118 
119 char PGOMemOPSizeOptLegacyPass::ID = 0;
120 INITIALIZE_PASS_BEGIN(PGOMemOPSizeOptLegacyPass, "pgo-memop-opt",
121                       "Optimize memory intrinsic using its size value profile",
122                       false, false)
123 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
124 INITIALIZE_PASS_END(PGOMemOPSizeOptLegacyPass, "pgo-memop-opt",
125                     "Optimize memory intrinsic using its size value profile",
126                     false, false)
127 
128 FunctionPass *llvm::createPGOMemOPSizeOptLegacyPass() {
129   return new PGOMemOPSizeOptLegacyPass();
130 }
131 
132 namespace {
133 class MemOPSizeOpt : public InstVisitor<MemOPSizeOpt> {
134 public:
135   MemOPSizeOpt(Function &Func, BlockFrequencyInfo &BFI,
136                OptimizationRemarkEmitter &ORE)
137       : Func(Func), BFI(BFI), ORE(ORE), Changed(false) {
138     ValueDataArray =
139         llvm::make_unique<InstrProfValueData[]>(MemOPMaxVersion + 2);
140     // Get the MemOPSize range information from option MemOPSizeRange,
141     getMemOPSizeRangeFromOption(MemOPSizeRange, PreciseRangeStart,
142                                 PreciseRangeLast);
143   }
144   bool isChanged() const { return Changed; }
145   void perform() {
146     WorkList.clear();
147     visit(Func);
148 
149     for (auto &MI : WorkList) {
150       ++NumOfPGOMemOPAnnotate;
151       if (perform(MI)) {
152         Changed = true;
153         ++NumOfPGOMemOPOpt;
154         LLVM_DEBUG(dbgs() << "MemOP call: "
155                           << MI->getCalledFunction()->getName()
156                           << "is Transformed.\n");
157       }
158     }
159   }
160 
161   void visitMemIntrinsic(MemIntrinsic &MI) {
162     Value *Length = MI.getLength();
163     // Not perform on constant length calls.
164     if (dyn_cast<ConstantInt>(Length))
165       return;
166     WorkList.push_back(&MI);
167   }
168 
169 private:
170   Function &Func;
171   BlockFrequencyInfo &BFI;
172   OptimizationRemarkEmitter &ORE;
173   bool Changed;
174   std::vector<MemIntrinsic *> WorkList;
175   // Start of the previse range.
176   int64_t PreciseRangeStart;
177   // Last value of the previse range.
178   int64_t PreciseRangeLast;
179   // The space to read the profile annotation.
180   std::unique_ptr<InstrProfValueData[]> ValueDataArray;
181   bool perform(MemIntrinsic *MI);
182 
183   // This kind shows which group the value falls in. For PreciseValue, we have
184   // the profile count for that value. LargeGroup groups the values that are in
185   // range [LargeValue, +inf). NonLargeGroup groups the rest of values.
186   enum MemOPSizeKind { PreciseValue, NonLargeGroup, LargeGroup };
187 
188   MemOPSizeKind getMemOPSizeKind(int64_t Value) const {
189     if (Value == MemOPSizeLarge && MemOPSizeLarge != 0)
190       return LargeGroup;
191     if (Value == PreciseRangeLast + 1)
192       return NonLargeGroup;
193     return PreciseValue;
194   }
195 };
196 
197 static const char *getMIName(const MemIntrinsic *MI) {
198   switch (MI->getIntrinsicID()) {
199   case Intrinsic::memcpy:
200     return "memcpy";
201   case Intrinsic::memmove:
202     return "memmove";
203   case Intrinsic::memset:
204     return "memset";
205   default:
206     return "unknown";
207   }
208 }
209 
210 static bool isProfitable(uint64_t Count, uint64_t TotalCount) {
211   assert(Count <= TotalCount);
212   if (Count < MemOPCountThreshold)
213     return false;
214   if (Count < TotalCount * MemOPPercentThreshold / 100)
215     return false;
216   return true;
217 }
218 
219 static inline uint64_t getScaledCount(uint64_t Count, uint64_t Num,
220                                       uint64_t Denom) {
221   if (!MemOPScaleCount)
222     return Count;
223   bool Overflowed;
224   uint64_t ScaleCount = SaturatingMultiply(Count, Num, &Overflowed);
225   return ScaleCount / Denom;
226 }
227 
228 bool MemOPSizeOpt::perform(MemIntrinsic *MI) {
229   assert(MI);
230   if (MI->getIntrinsicID() == Intrinsic::memmove)
231     return false;
232 
233   uint32_t NumVals, MaxNumPromotions = MemOPMaxVersion + 2;
234   uint64_t TotalCount;
235   if (!getValueProfDataFromInst(*MI, IPVK_MemOPSize, MaxNumPromotions,
236                                 ValueDataArray.get(), NumVals, TotalCount))
237     return false;
238 
239   uint64_t ActualCount = TotalCount;
240   uint64_t SavedTotalCount = TotalCount;
241   if (MemOPScaleCount) {
242     auto BBEdgeCount = BFI.getBlockProfileCount(MI->getParent());
243     if (!BBEdgeCount)
244       return false;
245     ActualCount = *BBEdgeCount;
246   }
247 
248   ArrayRef<InstrProfValueData> VDs(ValueDataArray.get(), NumVals);
249   LLVM_DEBUG(dbgs() << "Read one memory intrinsic profile with count "
250                     << ActualCount << "\n");
251   LLVM_DEBUG(
252       for (auto &VD
253            : VDs) { dbgs() << "  (" << VD.Value << "," << VD.Count << ")\n"; });
254 
255   if (ActualCount < MemOPCountThreshold)
256     return false;
257   // Skip if the total value profiled count is 0, in which case we can't
258   // scale up the counts properly (and there is no profitable transformation).
259   if (TotalCount == 0)
260     return false;
261 
262   TotalCount = ActualCount;
263   if (MemOPScaleCount)
264     LLVM_DEBUG(dbgs() << "Scale counts: numerator = " << ActualCount
265                       << " denominator = " << SavedTotalCount << "\n");
266 
267   // Keeping track of the count of the default case:
268   uint64_t RemainCount = TotalCount;
269   uint64_t SavedRemainCount = SavedTotalCount;
270   SmallVector<uint64_t, 16> SizeIds;
271   SmallVector<uint64_t, 16> CaseCounts;
272   uint64_t MaxCount = 0;
273   unsigned Version = 0;
274   // Default case is in the front -- save the slot here.
275   CaseCounts.push_back(0);
276   for (auto &VD : VDs) {
277     int64_t V = VD.Value;
278     uint64_t C = VD.Count;
279     if (MemOPScaleCount)
280       C = getScaledCount(C, ActualCount, SavedTotalCount);
281 
282     // Only care precise value here.
283     if (getMemOPSizeKind(V) != PreciseValue)
284       continue;
285 
286     // ValueCounts are sorted on the count. Break at the first un-profitable
287     // value.
288     if (!isProfitable(C, RemainCount))
289       break;
290 
291     SizeIds.push_back(V);
292     CaseCounts.push_back(C);
293     if (C > MaxCount)
294       MaxCount = C;
295 
296     assert(RemainCount >= C);
297     RemainCount -= C;
298     assert(SavedRemainCount >= VD.Count);
299     SavedRemainCount -= VD.Count;
300 
301     if (++Version > MemOPMaxVersion && MemOPMaxVersion != 0)
302       break;
303   }
304 
305   if (Version == 0)
306     return false;
307 
308   CaseCounts[0] = RemainCount;
309   if (RemainCount > MaxCount)
310     MaxCount = RemainCount;
311 
312   uint64_t SumForOpt = TotalCount - RemainCount;
313 
314   LLVM_DEBUG(dbgs() << "Optimize one memory intrinsic call to " << Version
315                     << " Versions (covering " << SumForOpt << " out of "
316                     << TotalCount << ")\n");
317 
318   // mem_op(..., size)
319   // ==>
320   // switch (size) {
321   //   case s1:
322   //      mem_op(..., s1);
323   //      goto merge_bb;
324   //   case s2:
325   //      mem_op(..., s2);
326   //      goto merge_bb;
327   //   ...
328   //   default:
329   //      mem_op(..., size);
330   //      goto merge_bb;
331   // }
332   // merge_bb:
333 
334   BasicBlock *BB = MI->getParent();
335   LLVM_DEBUG(dbgs() << "\n\n== Basic Block Before ==\n");
336   LLVM_DEBUG(dbgs() << *BB << "\n");
337   auto OrigBBFreq = BFI.getBlockFreq(BB);
338 
339   BasicBlock *DefaultBB = SplitBlock(BB, MI);
340   BasicBlock::iterator It(*MI);
341   ++It;
342   assert(It != DefaultBB->end());
343   BasicBlock *MergeBB = SplitBlock(DefaultBB, &(*It));
344   MergeBB->setName("MemOP.Merge");
345   BFI.setBlockFreq(MergeBB, OrigBBFreq.getFrequency());
346   DefaultBB->setName("MemOP.Default");
347 
348   auto &Ctx = Func.getContext();
349   IRBuilder<> IRB(BB);
350   BB->getTerminator()->eraseFromParent();
351   Value *SizeVar = MI->getLength();
352   SwitchInst *SI = IRB.CreateSwitch(SizeVar, DefaultBB, SizeIds.size());
353 
354   // Clear the value profile data.
355   MI->setMetadata(LLVMContext::MD_prof, nullptr);
356   // If all promoted, we don't need the MD.prof metadata.
357   if (SavedRemainCount > 0 || Version != NumVals)
358     // Otherwise we need update with the un-promoted records back.
359     annotateValueSite(*Func.getParent(), *MI, VDs.slice(Version),
360                       SavedRemainCount, IPVK_MemOPSize, NumVals);
361 
362   LLVM_DEBUG(dbgs() << "\n\n== Basic Block After==\n");
363 
364   for (uint64_t SizeId : SizeIds) {
365     BasicBlock *CaseBB = BasicBlock::Create(
366         Ctx, Twine("MemOP.Case.") + Twine(SizeId), &Func, DefaultBB);
367     Instruction *NewInst = MI->clone();
368     // Fix the argument.
369     MemIntrinsic * MemI = dyn_cast<MemIntrinsic>(NewInst);
370     IntegerType *SizeType = dyn_cast<IntegerType>(MemI->getLength()->getType());
371     assert(SizeType && "Expected integer type size argument.");
372     ConstantInt *CaseSizeId = ConstantInt::get(SizeType, SizeId);
373     MemI->setLength(CaseSizeId);
374     CaseBB->getInstList().push_back(NewInst);
375     IRBuilder<> IRBCase(CaseBB);
376     IRBCase.CreateBr(MergeBB);
377     SI->addCase(CaseSizeId, CaseBB);
378     LLVM_DEBUG(dbgs() << *CaseBB << "\n");
379   }
380   setProfMetadata(Func.getParent(), SI, CaseCounts, MaxCount);
381 
382   LLVM_DEBUG(dbgs() << *BB << "\n");
383   LLVM_DEBUG(dbgs() << *DefaultBB << "\n");
384   LLVM_DEBUG(dbgs() << *MergeBB << "\n");
385 
386   ORE.emit([&]() {
387     using namespace ore;
388     return OptimizationRemark(DEBUG_TYPE, "memopt-opt", MI)
389              << "optimized " << NV("Intrinsic", StringRef(getMIName(MI)))
390              << " with count " << NV("Count", SumForOpt) << " out of "
391              << NV("Total", TotalCount) << " for " << NV("Versions", Version)
392              << " versions";
393   });
394 
395   return true;
396 }
397 } // namespace
398 
399 static bool PGOMemOPSizeOptImpl(Function &F, BlockFrequencyInfo &BFI,
400                                 OptimizationRemarkEmitter &ORE) {
401   if (DisableMemOPOPT)
402     return false;
403 
404   if (F.hasFnAttribute(Attribute::OptimizeForSize))
405     return false;
406   MemOPSizeOpt MemOPSizeOpt(F, BFI, ORE);
407   MemOPSizeOpt.perform();
408   return MemOPSizeOpt.isChanged();
409 }
410 
411 bool PGOMemOPSizeOptLegacyPass::runOnFunction(Function &F) {
412   BlockFrequencyInfo &BFI =
413       getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
414   auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
415   return PGOMemOPSizeOptImpl(F, BFI, ORE);
416 }
417 
418 namespace llvm {
419 char &PGOMemOPSizeOptID = PGOMemOPSizeOptLegacyPass::ID;
420 
421 PreservedAnalyses PGOMemOPSizeOpt::run(Function &F,
422                                        FunctionAnalysisManager &FAM) {
423   auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
424   auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
425   bool Changed = PGOMemOPSizeOptImpl(F, BFI, ORE);
426   if (!Changed)
427     return PreservedAnalyses::all();
428   auto PA = PreservedAnalyses();
429   PA.preserve<GlobalsAA>();
430   return PA;
431 }
432 } // namespace llvm
433