1 //===------- X86InsertPrefetch.cpp - Insert cache prefetch hints ----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass applies cache prefetch instructions based on a profile. The pass
10 // assumes DiscriminateMemOps ran immediately before, to ensure debug info
11 // matches the one used at profile generation time. The profile is encoded in
12 // afdo format (text or binary). It contains prefetch hints recommendations.
13 // Each recommendation is made in terms of debug info locations, a type (i.e.
14 // nta, t{0|1|2}) and a delta. The debug info identifies an instruction with a
15 // memory operand (see X86DiscriminateMemOps). The prefetch will be made for
16 // a location at that memory operand + the delta specified in the
17 // recommendation.
18 //
19 //===----------------------------------------------------------------------===//
20 
21 #include "X86.h"
22 #include "X86InstrBuilder.h"
23 #include "X86InstrInfo.h"
24 #include "X86MachineFunctionInfo.h"
25 #include "X86Subtarget.h"
26 #include "llvm/CodeGen/MachineFunctionPass.h"
27 #include "llvm/CodeGen/MachineModuleInfo.h"
28 #include "llvm/IR/DebugInfoMetadata.h"
29 #include "llvm/ProfileData/SampleProf.h"
30 #include "llvm/ProfileData/SampleProfReader.h"
31 #include "llvm/Support/VirtualFileSystem.h"
32 #include "llvm/Transforms/IPO/SampleProfile.h"
33 using namespace llvm;
34 using namespace sampleprof;
35 
36 static cl::opt<std::string>
37     PrefetchHintsFile("prefetch-hints-file",
38                       cl::desc("Path to the prefetch hints profile. See also "
39                                "-x86-discriminate-memops"),
40                       cl::Hidden);
41 namespace {
42 
43 class X86InsertPrefetch : public MachineFunctionPass {
44   void getAnalysisUsage(AnalysisUsage &AU) const override;
45   bool doInitialization(Module &) override;
46 
47   bool runOnMachineFunction(MachineFunction &MF) override;
48   struct PrefetchInfo {
49     unsigned InstructionID;
50     int64_t Delta;
51   };
52   typedef SmallVectorImpl<PrefetchInfo> Prefetches;
53   bool findPrefetchInfo(const FunctionSamples *Samples, const MachineInstr &MI,
54                         Prefetches &prefetches) const;
55 
56 public:
57   static char ID;
58   X86InsertPrefetch(const std::string &PrefetchHintsFilename);
59   StringRef getPassName() const override {
60     return "X86 Insert Cache Prefetches";
61   }
62 
63 private:
64   std::string Filename;
65   std::unique_ptr<SampleProfileReader> Reader;
66 };
67 
68 using PrefetchHints = SampleRecord::CallTargetMap;
69 
70 // Return any prefetching hints for the specified MachineInstruction. The hints
71 // are returned as pairs (name, delta).
72 ErrorOr<const PrefetchHints &>
73 getPrefetchHints(const FunctionSamples *TopSamples, const MachineInstr &MI) {
74   if (const auto &Loc = MI.getDebugLoc())
75     if (const auto *Samples = TopSamples->findFunctionSamples(Loc))
76       return Samples->findCallTargetMapAt(FunctionSamples::getOffset(Loc),
77                                           Loc->getBaseDiscriminator());
78   return std::error_code();
79 }
80 
81 // The prefetch instruction can't take memory operands involving vector
82 // registers.
83 bool IsMemOpCompatibleWithPrefetch(const MachineInstr &MI, int Op) {
84   Register BaseReg = MI.getOperand(Op + X86::AddrBaseReg).getReg();
85   Register IndexReg = MI.getOperand(Op + X86::AddrIndexReg).getReg();
86   return (BaseReg == 0 ||
87           X86MCRegisterClasses[X86::GR64RegClassID].contains(BaseReg) ||
88           X86MCRegisterClasses[X86::GR32RegClassID].contains(BaseReg)) &&
89          (IndexReg == 0 ||
90           X86MCRegisterClasses[X86::GR64RegClassID].contains(IndexReg) ||
91           X86MCRegisterClasses[X86::GR32RegClassID].contains(IndexReg));
92 }
93 
94 } // end anonymous namespace
95 
96 //===----------------------------------------------------------------------===//
97 //            Implementation
98 //===----------------------------------------------------------------------===//
99 
100 char X86InsertPrefetch::ID = 0;
101 
102 X86InsertPrefetch::X86InsertPrefetch(const std::string &PrefetchHintsFilename)
103     : MachineFunctionPass(ID), Filename(PrefetchHintsFilename) {}
104 
105 /// Return true if the provided MachineInstruction has cache prefetch hints. In
106 /// that case, the prefetch hints are stored, in order, in the Prefetches
107 /// vector.
108 bool X86InsertPrefetch::findPrefetchInfo(const FunctionSamples *TopSamples,
109                                          const MachineInstr &MI,
110                                          Prefetches &Prefetches) const {
111   assert(Prefetches.empty() &&
112          "Expected caller passed empty PrefetchInfo vector.");
113 
114   // There is no point to match prefetch hints if the profile is using MD5.
115   if (FunctionSamples::UseMD5)
116     return false;
117 
118   static constexpr std::pair<StringLiteral, unsigned> HintTypes[] = {
119       {"_nta_", X86::PREFETCHNTA},
120       {"_t0_", X86::PREFETCHT0},
121       {"_t1_", X86::PREFETCHT1},
122       {"_t2_", X86::PREFETCHT2},
123   };
124   static const char *SerializedPrefetchPrefix = "__prefetch";
125 
126   auto T = getPrefetchHints(TopSamples, MI);
127   if (!T)
128     return false;
129   int16_t max_index = -1;
130   // Convert serialized prefetch hints into PrefetchInfo objects, and populate
131   // the Prefetches vector.
132   for (const auto &S_V : *T) {
133     StringRef Name = S_V.first.stringRef();
134     if (Name.consume_front(SerializedPrefetchPrefix)) {
135       int64_t D = static_cast<int64_t>(S_V.second);
136       unsigned IID = 0;
137       for (const auto &HintType : HintTypes) {
138         if (Name.consume_front(HintType.first)) {
139           IID = HintType.second;
140           break;
141         }
142       }
143       if (IID == 0)
144         return false;
145       uint8_t index = 0;
146       Name.consumeInteger(10, index);
147 
148       if (index >= Prefetches.size())
149         Prefetches.resize(index + 1);
150       Prefetches[index] = {IID, D};
151       max_index = std::max(max_index, static_cast<int16_t>(index));
152     }
153   }
154   assert(max_index + 1 >= 0 &&
155          "Possible overflow: max_index + 1 should be positive.");
156   assert(static_cast<size_t>(max_index + 1) == Prefetches.size() &&
157          "The number of prefetch hints received should match the number of "
158          "PrefetchInfo objects returned");
159   return !Prefetches.empty();
160 }
161 
162 bool X86InsertPrefetch::doInitialization(Module &M) {
163   if (Filename.empty())
164     return false;
165 
166   LLVMContext &Ctx = M.getContext();
167   // TODO: Propagate virtual file system into LLVM targets.
168   auto FS = vfs::getRealFileSystem();
169   ErrorOr<std::unique_ptr<SampleProfileReader>> ReaderOrErr =
170       SampleProfileReader::create(Filename, Ctx, *FS);
171   if (std::error_code EC = ReaderOrErr.getError()) {
172     std::string Msg = "Could not open profile: " + EC.message();
173     Ctx.diagnose(DiagnosticInfoSampleProfile(Filename, Msg,
174                                              DiagnosticSeverity::DS_Warning));
175     return false;
176   }
177   Reader = std::move(ReaderOrErr.get());
178   Reader->read();
179   return true;
180 }
181 
182 void X86InsertPrefetch::getAnalysisUsage(AnalysisUsage &AU) const {
183   AU.setPreservesAll();
184   MachineFunctionPass::getAnalysisUsage(AU);
185 }
186 
187 bool X86InsertPrefetch::runOnMachineFunction(MachineFunction &MF) {
188   if (!Reader)
189     return false;
190   const FunctionSamples *Samples = Reader->getSamplesFor(MF.getFunction());
191   if (!Samples)
192     return false;
193 
194   bool Changed = false;
195 
196   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
197   SmallVector<PrefetchInfo, 4> Prefetches;
198   for (auto &MBB : MF) {
199     for (auto MI = MBB.instr_begin(); MI != MBB.instr_end();) {
200       auto Current = MI;
201       ++MI;
202 
203       int Offset = X86II::getMemoryOperandNo(Current->getDesc().TSFlags);
204       if (Offset < 0)
205         continue;
206       unsigned Bias = X86II::getOperandBias(Current->getDesc());
207       int MemOpOffset = Offset + Bias;
208       // FIXME(mtrofin): ORE message when the recommendation cannot be taken.
209       if (!IsMemOpCompatibleWithPrefetch(*Current, MemOpOffset))
210         continue;
211       Prefetches.clear();
212       if (!findPrefetchInfo(Samples, *Current, Prefetches))
213         continue;
214       assert(!Prefetches.empty() &&
215              "The Prefetches vector should contain at least a value if "
216              "findPrefetchInfo returned true.");
217       for (auto &PrefInfo : Prefetches) {
218         unsigned PFetchInstrID = PrefInfo.InstructionID;
219         int64_t Delta = PrefInfo.Delta;
220         const MCInstrDesc &Desc = TII->get(PFetchInstrID);
221         MachineInstr *PFetch =
222             MF.CreateMachineInstr(Desc, Current->getDebugLoc(), true);
223         MachineInstrBuilder MIB(MF, PFetch);
224 
225         static_assert(X86::AddrBaseReg == 0 && X86::AddrScaleAmt == 1 &&
226                           X86::AddrIndexReg == 2 && X86::AddrDisp == 3 &&
227                           X86::AddrSegmentReg == 4,
228                       "Unexpected change in X86 operand offset order.");
229 
230         // This assumes X86::AddBaseReg = 0, {...}ScaleAmt = 1, etc.
231         // FIXME(mtrofin): consider adding a:
232         //     MachineInstrBuilder::set(unsigned offset, op).
233         MIB.addReg(Current->getOperand(MemOpOffset + X86::AddrBaseReg).getReg())
234             .addImm(
235                 Current->getOperand(MemOpOffset + X86::AddrScaleAmt).getImm())
236             .addReg(
237                 Current->getOperand(MemOpOffset + X86::AddrIndexReg).getReg())
238             .addImm(Current->getOperand(MemOpOffset + X86::AddrDisp).getImm() +
239                     Delta)
240             .addReg(Current->getOperand(MemOpOffset + X86::AddrSegmentReg)
241                         .getReg());
242 
243         if (!Current->memoperands_empty()) {
244           MachineMemOperand *CurrentOp = *(Current->memoperands_begin());
245           MIB.addMemOperand(MF.getMachineMemOperand(
246               CurrentOp, CurrentOp->getOffset() + Delta, CurrentOp->getSize()));
247         }
248 
249         // Insert before Current. This is because Current may clobber some of
250         // the registers used to describe the input memory operand.
251         MBB.insert(Current, PFetch);
252         Changed = true;
253       }
254     }
255   }
256   return Changed;
257 }
258 
259 FunctionPass *llvm::createX86InsertPrefetchPass() {
260   return new X86InsertPrefetch(PrefetchHintsFile);
261 }
262