1 //===---------------------------- StackMaps.cpp ---------------------------===//
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 #include "llvm/CodeGen/StackMaps.h"
11 #include "llvm/CodeGen/AsmPrinter.h"
12 #include "llvm/CodeGen/MachineFrameInfo.h"
13 #include "llvm/CodeGen/MachineFunction.h"
14 #include "llvm/CodeGen/MachineInstr.h"
15 #include "llvm/IR/DataLayout.h"
16 #include "llvm/MC/MCContext.h"
17 #include "llvm/MC/MCExpr.h"
18 #include "llvm/MC/MCObjectFileInfo.h"
19 #include "llvm/MC/MCSectionMachO.h"
20 #include "llvm/MC/MCStreamer.h"
21 #include "llvm/Support/CommandLine.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include "llvm/Target/TargetMachine.h"
25 #include "llvm/Target/TargetOpcodes.h"
26 #include "llvm/Target/TargetRegisterInfo.h"
27 #include <iterator>
28 
29 using namespace llvm;
30 
31 #define DEBUG_TYPE "stackmaps"
32 
33 static cl::opt<int> StackMapVersion("stackmap-version", cl::init(1),
34   cl::desc("Specify the stackmap encoding version (default = 1)"));
35 
36 const char *StackMaps::WSMP = "Stack Maps: ";
37 
38 PatchPointOpers::PatchPointOpers(const MachineInstr *MI)
39   : MI(MI),
40     HasDef(MI->getOperand(0).isReg() && MI->getOperand(0).isDef() &&
41            !MI->getOperand(0).isImplicit()),
42     IsAnyReg(MI->getOperand(getMetaIdx(CCPos)).getImm() == CallingConv::AnyReg)
43 {
44 #ifndef NDEBUG
45   unsigned CheckStartIdx = 0, e = MI->getNumOperands();
46   while (CheckStartIdx < e && MI->getOperand(CheckStartIdx).isReg() &&
47          MI->getOperand(CheckStartIdx).isDef() &&
48          !MI->getOperand(CheckStartIdx).isImplicit())
49     ++CheckStartIdx;
50 
51   assert(getMetaIdx() == CheckStartIdx &&
52          "Unexpected additional definition in Patchpoint intrinsic.");
53 #endif
54 }
55 
56 unsigned PatchPointOpers::getNextScratchIdx(unsigned StartIdx) const {
57   if (!StartIdx)
58     StartIdx = getVarIdx();
59 
60   // Find the next scratch register (implicit def and early clobber)
61   unsigned ScratchIdx = StartIdx, e = MI->getNumOperands();
62   while (ScratchIdx < e &&
63          !(MI->getOperand(ScratchIdx).isReg() &&
64            MI->getOperand(ScratchIdx).isDef() &&
65            MI->getOperand(ScratchIdx).isImplicit() &&
66            MI->getOperand(ScratchIdx).isEarlyClobber()))
67     ++ScratchIdx;
68 
69   assert(ScratchIdx != e && "No scratch register available");
70   return ScratchIdx;
71 }
72 
73 StackMaps::StackMaps(AsmPrinter &AP) : AP(AP) {
74   if (StackMapVersion != 1)
75     llvm_unreachable("Unsupported stackmap version!");
76 }
77 
78 MachineInstr::const_mop_iterator
79 StackMaps::parseOperand(MachineInstr::const_mop_iterator MOI,
80                         MachineInstr::const_mop_iterator MOE,
81                         LocationVec &Locs, LiveOutVec &LiveOuts) const {
82   if (MOI->isImm()) {
83     switch (MOI->getImm()) {
84     default: llvm_unreachable("Unrecognized operand type.");
85     case StackMaps::DirectMemRefOp: {
86       unsigned Size = AP.TM.getDataLayout()->getPointerSizeInBits();
87       assert((Size % 8) == 0 && "Need pointer size in bytes.");
88       Size /= 8;
89       unsigned Reg = (++MOI)->getReg();
90       int64_t Imm = (++MOI)->getImm();
91       Locs.push_back(Location(StackMaps::Location::Direct, Size, Reg, Imm));
92       break;
93     }
94     case StackMaps::IndirectMemRefOp: {
95       int64_t Size = (++MOI)->getImm();
96       assert(Size > 0 && "Need a valid size for indirect memory locations.");
97       unsigned Reg = (++MOI)->getReg();
98       int64_t Imm = (++MOI)->getImm();
99       Locs.push_back(Location(StackMaps::Location::Indirect, Size, Reg, Imm));
100       break;
101     }
102     case StackMaps::ConstantOp: {
103       ++MOI;
104       assert(MOI->isImm() && "Expected constant operand.");
105       int64_t Imm = MOI->getImm();
106       Locs.push_back(Location(Location::Constant, sizeof(int64_t), 0, Imm));
107       break;
108     }
109     }
110     return ++MOI;
111   }
112 
113   // The physical register number will ultimately be encoded as a DWARF regno.
114   // The stack map also records the size of a spill slot that can hold the
115   // register content. (The runtime can track the actual size of the data type
116   // if it needs to.)
117   if (MOI->isReg()) {
118     // Skip implicit registers (this includes our scratch registers)
119     if (MOI->isImplicit())
120       return ++MOI;
121 
122     assert(TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) &&
123            "Virtreg operands should have been rewritten before now.");
124     const TargetRegisterClass *RC =
125       AP.TM.getRegisterInfo()->getMinimalPhysRegClass(MOI->getReg());
126     assert(!MOI->getSubReg() && "Physical subreg still around.");
127     Locs.push_back(
128       Location(Location::Register, RC->getSize(), MOI->getReg(), 0));
129     return ++MOI;
130   }
131 
132   if (MOI->isRegLiveOut())
133     LiveOuts = parseRegisterLiveOutMask(MOI->getRegLiveOut());
134 
135   return ++MOI;
136 }
137 
138 /// Go up the super-register chain until we hit a valid dwarf register number.
139 static unsigned getDwarfRegNum(unsigned Reg, const TargetRegisterInfo *TRI) {
140   int RegNo = TRI->getDwarfRegNum(Reg, false);
141   for (MCSuperRegIterator SR(Reg, TRI); SR.isValid() && RegNo < 0; ++SR)
142     RegNo = TRI->getDwarfRegNum(*SR, false);
143 
144   assert(RegNo >= 0 && "Invalid Dwarf register number.");
145   return (unsigned) RegNo;
146 }
147 
148 /// Create a live-out register record for the given register Reg.
149 StackMaps::LiveOutReg
150 StackMaps::createLiveOutReg(unsigned Reg, const TargetRegisterInfo *TRI) const {
151   unsigned RegNo = getDwarfRegNum(Reg, TRI);
152   unsigned Size = TRI->getMinimalPhysRegClass(Reg)->getSize();
153   return LiveOutReg(Reg, RegNo, Size);
154 }
155 
156 /// Parse the register live-out mask and return a vector of live-out registers
157 /// that need to be recorded in the stackmap.
158 StackMaps::LiveOutVec
159 StackMaps::parseRegisterLiveOutMask(const uint32_t *Mask) const {
160   assert(Mask && "No register mask specified");
161   const TargetRegisterInfo *TRI = AP.TM.getRegisterInfo();
162   LiveOutVec LiveOuts;
163 
164   // Create a LiveOutReg for each bit that is set in the register mask.
165   for (unsigned Reg = 0, NumRegs = TRI->getNumRegs(); Reg != NumRegs; ++Reg)
166     if ((Mask[Reg / 32] >> Reg % 32) & 1)
167       LiveOuts.push_back(createLiveOutReg(Reg, TRI));
168 
169   // We don't need to keep track of a register if its super-register is already
170   // in the list. Merge entries that refer to the same dwarf register and use
171   // the maximum size that needs to be spilled.
172   std::sort(LiveOuts.begin(), LiveOuts.end());
173   for (LiveOutVec::iterator I = LiveOuts.begin(), E = LiveOuts.end();
174        I != E; ++I) {
175     for (LiveOutVec::iterator II = std::next(I); II != E; ++II) {
176       if (I->RegNo != II->RegNo) {
177         // Skip all the now invalid entries.
178         I = --II;
179         break;
180       }
181       I->Size = std::max(I->Size, II->Size);
182       if (TRI->isSuperRegister(I->Reg, II->Reg))
183         I->Reg = II->Reg;
184       II->MarkInvalid();
185     }
186   }
187   LiveOuts.erase(std::remove_if(LiveOuts.begin(), LiveOuts.end(),
188                                 LiveOutReg::IsInvalid), LiveOuts.end());
189   return LiveOuts;
190 }
191 
192 void StackMaps::recordStackMapOpers(const MachineInstr &MI, uint64_t ID,
193                                     MachineInstr::const_mop_iterator MOI,
194                                     MachineInstr::const_mop_iterator MOE,
195                                     bool recordResult) {
196 
197   MCContext &OutContext = AP.OutStreamer.getContext();
198   MCSymbol *MILabel = OutContext.CreateTempSymbol();
199   AP.OutStreamer.EmitLabel(MILabel);
200 
201   LocationVec Locations;
202   LiveOutVec LiveOuts;
203 
204   if (recordResult) {
205     assert(PatchPointOpers(&MI).hasDef() && "Stackmap has no return value.");
206     parseOperand(MI.operands_begin(), std::next(MI.operands_begin()),
207                  Locations, LiveOuts);
208   }
209 
210   // Parse operands.
211   while (MOI != MOE) {
212     MOI = parseOperand(MOI, MOE, Locations, LiveOuts);
213   }
214 
215   // Move large constants into the constant pool.
216   for (LocationVec::iterator I = Locations.begin(), E = Locations.end();
217        I != E; ++I) {
218     // Constants are encoded as sign-extended integers.
219     // -1 is directly encoded as .long 0xFFFFFFFF with no constant pool.
220     if (I->LocType == Location::Constant &&
221         ((I->Offset + (int64_t(1)<<31)) >> 32) != 0) {
222       I->LocType = Location::ConstantIndex;
223       auto Result = ConstPool.insert(std::make_pair(I->Offset, I->Offset));
224       I->Offset = Result.first - ConstPool.begin();
225     }
226   }
227 
228   // Create an expression to calculate the offset of the callsite from function
229   // entry.
230   const MCExpr *CSOffsetExpr = MCBinaryExpr::CreateSub(
231     MCSymbolRefExpr::Create(MILabel, OutContext),
232     MCSymbolRefExpr::Create(AP.CurrentFnSym, OutContext),
233     OutContext);
234 
235   CSInfos.push_back(CallsiteInfo(CSOffsetExpr, ID, Locations, LiveOuts));
236 
237   // Record the stack size of the current function.
238   const MachineFrameInfo *MFI = AP.MF->getFrameInfo();
239   const TargetRegisterInfo *RegInfo = AP.MF->getTarget().getRegisterInfo();
240   const bool DynamicFrameSize = MFI->hasVarSizedObjects() ||
241     RegInfo->needsStackRealignment(*(AP.MF));
242   FnStackSize[AP.CurrentFnSym] =
243     DynamicFrameSize ? UINT64_MAX : MFI->getStackSize();
244 }
245 
246 void StackMaps::recordStackMap(const MachineInstr &MI) {
247   assert(MI.getOpcode() == TargetOpcode::STACKMAP && "expected stackmap");
248 
249   int64_t ID = MI.getOperand(0).getImm();
250   recordStackMapOpers(MI, ID, std::next(MI.operands_begin(), 2),
251                       MI.operands_end());
252 }
253 
254 void StackMaps::recordPatchPoint(const MachineInstr &MI) {
255   assert(MI.getOpcode() == TargetOpcode::PATCHPOINT && "expected patchpoint");
256 
257   PatchPointOpers opers(&MI);
258   int64_t ID = opers.getMetaOper(PatchPointOpers::IDPos).getImm();
259 
260   MachineInstr::const_mop_iterator MOI =
261     std::next(MI.operands_begin(), opers.getStackMapStartIdx());
262   recordStackMapOpers(MI, ID, MOI, MI.operands_end(),
263                       opers.isAnyReg() && opers.hasDef());
264 
265 #ifndef NDEBUG
266   // verify anyregcc
267   LocationVec &Locations = CSInfos.back().Locations;
268   if (opers.isAnyReg()) {
269     unsigned NArgs = opers.getMetaOper(PatchPointOpers::NArgPos).getImm();
270     for (unsigned i = 0, e = (opers.hasDef() ? NArgs+1 : NArgs); i != e; ++i)
271       assert(Locations[i].LocType == Location::Register &&
272              "anyreg arg must be in reg.");
273   }
274 #endif
275 }
276 
277 /// Emit the stackmap header.
278 ///
279 /// Header {
280 ///   uint8  : Stack Map Version (currently 1)
281 ///   uint8  : Reserved (expected to be 0)
282 ///   uint16 : Reserved (expected to be 0)
283 /// }
284 /// uint32 : NumFunctions
285 /// uint32 : NumConstants
286 /// uint32 : NumRecords
287 void StackMaps::emitStackmapHeader(MCStreamer &OS) {
288   // Header.
289   OS.EmitIntValue(StackMapVersion, 1); // Version.
290   OS.EmitIntValue(0, 1); // Reserved.
291   OS.EmitIntValue(0, 2); // Reserved.
292 
293   // Num functions.
294   DEBUG(dbgs() << WSMP << "#functions = " << FnStackSize.size() << '\n');
295   OS.EmitIntValue(FnStackSize.size(), 4);
296   // Num constants.
297   DEBUG(dbgs() << WSMP << "#constants = " << ConstPool.size() << '\n');
298   OS.EmitIntValue(ConstPool.size(), 4);
299   // Num callsites.
300   DEBUG(dbgs() << WSMP << "#callsites = " << CSInfos.size() << '\n');
301   OS.EmitIntValue(CSInfos.size(), 4);
302 }
303 
304 /// Emit the function frame record for each function.
305 ///
306 /// StkSizeRecord[NumFunctions] {
307 ///   uint64 : Function Address
308 ///   uint64 : Stack Size
309 /// }
310 void StackMaps::emitFunctionFrameRecords(MCStreamer &OS) {
311   // Function Frame records.
312   DEBUG(dbgs() << WSMP << "functions:\n");
313   for (auto const &FR : FnStackSize) {
314     DEBUG(dbgs() << WSMP << "function addr: " << FR.first
315                          << " frame size: " << FR.second);
316     OS.EmitSymbolValue(FR.first, 8);
317     OS.EmitIntValue(FR.second, 8);
318   }
319 }
320 
321 /// Emit the constant pool.
322 ///
323 /// int64  : Constants[NumConstants]
324 void StackMaps::emitConstantPoolEntries(MCStreamer &OS) {
325   // Constant pool entries.
326   DEBUG(dbgs() << WSMP << "constants:\n");
327   for (auto ConstEntry : ConstPool) {
328     DEBUG(dbgs() << WSMP << ConstEntry.second << '\n');
329     OS.EmitIntValue(ConstEntry.second, 8);
330   }
331 }
332 
333 /// Emit the callsite info for each callsite.
334 ///
335 /// StkMapRecord[NumRecords] {
336 ///   uint64 : PatchPoint ID
337 ///   uint32 : Instruction Offset
338 ///   uint16 : Reserved (record flags)
339 ///   uint16 : NumLocations
340 ///   Location[NumLocations] {
341 ///     uint8  : Register | Direct | Indirect | Constant | ConstantIndex
342 ///     uint8  : Size in Bytes
343 ///     uint16 : Dwarf RegNum
344 ///     int32  : Offset
345 ///   }
346 ///   uint16 : Padding
347 ///   uint16 : NumLiveOuts
348 ///   LiveOuts[NumLiveOuts] {
349 ///     uint16 : Dwarf RegNum
350 ///     uint8  : Reserved
351 ///     uint8  : Size in Bytes
352 ///   }
353 ///   uint32 : Padding (only if required to align to 8 byte)
354 /// }
355 ///
356 /// Location Encoding, Type, Value:
357 ///   0x1, Register, Reg                 (value in register)
358 ///   0x2, Direct, Reg + Offset          (frame index)
359 ///   0x3, Indirect, [Reg + Offset]      (spilled value)
360 ///   0x4, Constant, Offset              (small constant)
361 ///   0x5, ConstIndex, Constants[Offset] (large constant)
362 void StackMaps::emitCallsiteEntries(MCStreamer &OS,
363                                     const TargetRegisterInfo *TRI) {
364   // Callsite entries.
365   DEBUG(dbgs() << WSMP << "callsites:\n");
366   for (const auto &CSI : CSInfos) {
367     const LocationVec &CSLocs = CSI.Locations;
368     const LiveOutVec &LiveOuts = CSI.LiveOuts;
369 
370     DEBUG(dbgs() << WSMP << "callsite " << CSI.ID << "\n");
371 
372     // Verify stack map entry. It's better to communicate a problem to the
373     // runtime than crash in case of in-process compilation. Currently, we do
374     // simple overflow checks, but we may eventually communicate other
375     // compilation errors this way.
376     if (CSLocs.size() > UINT16_MAX || LiveOuts.size() > UINT16_MAX) {
377       OS.EmitIntValue(UINT64_MAX, 8); // Invalid ID.
378       OS.EmitValue(CSI.CSOffsetExpr, 4);
379       OS.EmitIntValue(0, 2); // Reserved.
380       OS.EmitIntValue(0, 2); // 0 locations.
381       OS.EmitIntValue(0, 2); // padding.
382       OS.EmitIntValue(0, 2); // 0 live-out registers.
383       OS.EmitIntValue(0, 4); // padding.
384       continue;
385     }
386 
387     OS.EmitIntValue(CSI.ID, 8);
388     OS.EmitValue(CSI.CSOffsetExpr, 4);
389 
390     // Reserved for flags.
391     OS.EmitIntValue(0, 2);
392 
393     DEBUG(dbgs() << WSMP << "  has " << CSLocs.size() << " locations\n");
394 
395     OS.EmitIntValue(CSLocs.size(), 2);
396 
397     unsigned OperIdx = 0;
398     for (const auto &Loc : CSLocs) {
399       unsigned RegNo = 0;
400       int Offset = Loc.Offset;
401       if(Loc.Reg) {
402         RegNo = getDwarfRegNum(Loc.Reg, TRI);
403 
404         // If this is a register location, put the subregister byte offset in
405         // the location offset.
406         if (Loc.LocType == Location::Register) {
407           assert(!Loc.Offset && "Register location should have zero offset");
408           unsigned LLVMRegNo = TRI->getLLVMRegNum(RegNo, false);
409           unsigned SubRegIdx = TRI->getSubRegIndex(LLVMRegNo, Loc.Reg);
410           if (SubRegIdx)
411             Offset = TRI->getSubRegIdxOffset(SubRegIdx);
412         }
413       }
414       else {
415         assert(Loc.LocType != Location::Register &&
416                "Missing location register");
417       }
418 
419       DEBUG(dbgs() << WSMP << "  Loc " << OperIdx << ": ";
420             switch (Loc.LocType) {
421             case Location::Unprocessed:
422               dbgs() << "<Unprocessed operand>";
423               break;
424             case Location::Register:
425               dbgs() << "Register " << TRI->getName(Loc.Reg);
426               break;
427             case Location::Direct:
428               dbgs() << "Direct " << TRI->getName(Loc.Reg);
429               if (Loc.Offset)
430               dbgs() << " + " << Loc.Offset;
431               break;
432             case Location::Indirect:
433               dbgs() << "Indirect " << TRI->getName(Loc.Reg)
434               << " + " << Loc.Offset;
435               break;
436             case Location::Constant:
437               dbgs() << "Constant " << Loc.Offset;
438               break;
439             case Location::ConstantIndex:
440               dbgs() << "Constant Index " << Loc.Offset;
441               break;
442               }
443             dbgs() << "     [encoding: .byte " << Loc.LocType
444             << ", .byte " << Loc.Size
445             << ", .short " << RegNo
446             << ", .int " << Offset << "]\n";
447             );
448 
449       OS.EmitIntValue(Loc.LocType, 1);
450       OS.EmitIntValue(Loc.Size, 1);
451       OS.EmitIntValue(RegNo, 2);
452       OS.EmitIntValue(Offset, 4);
453       OperIdx++;
454     }
455 
456     DEBUG(dbgs() << WSMP << "  has " << LiveOuts.size()
457                          << " live-out registers\n");
458 
459     // Num live-out registers and padding to align to 4 byte.
460     OS.EmitIntValue(0, 2);
461     OS.EmitIntValue(LiveOuts.size(), 2);
462 
463     OperIdx = 0;
464     for (const auto &LO : LiveOuts) {
465       DEBUG(dbgs() << WSMP << "  LO " << OperIdx << ": "
466                            << TRI->getName(LO.Reg)
467                            << "     [encoding: .short " << LO.RegNo
468                            << ", .byte 0, .byte " << LO.Size << "]\n");
469       OS.EmitIntValue(LO.RegNo, 2);
470       OS.EmitIntValue(0, 1);
471       OS.EmitIntValue(LO.Size, 1);
472     }
473     // Emit alignment to 8 byte.
474     OS.EmitValueToAlignment(8);
475   }
476 }
477 
478 /// Serialize the stackmap data.
479 void StackMaps::serializeToStackMapSection() {
480   (void) WSMP;
481   // Bail out if there's no stack map data.
482   assert((!CSInfos.empty() || (CSInfos.empty() && ConstPool.empty())) &&
483          "Expected empty constant pool too!");
484   assert((!CSInfos.empty() || (CSInfos.empty() && FnStackSize.empty())) &&
485          "Expected empty function record too!");
486   if (CSInfos.empty())
487     return;
488 
489   MCContext &OutContext = AP.OutStreamer.getContext();
490   MCStreamer &OS = AP.OutStreamer;
491   const TargetRegisterInfo *TRI = AP.TM.getRegisterInfo();
492 
493   // Create the section.
494   const MCSection *StackMapSection =
495     OutContext.getObjectFileInfo()->getStackMapSection();
496   OS.SwitchSection(StackMapSection);
497 
498   // Emit a dummy symbol to force section inclusion.
499   OS.EmitLabel(OutContext.GetOrCreateSymbol(Twine("__LLVM_StackMaps")));
500 
501   // Serialize data.
502   DEBUG(dbgs() << "********** Stack Map Output **********\n");
503   emitStackmapHeader(OS);
504   emitFunctionFrameRecords(OS);
505   emitConstantPoolEntries(OS);
506   emitCallsiteEntries(OS, TRI);
507   OS.AddBlankLine();
508 
509   // Clean up.
510   CSInfos.clear();
511   ConstPool.clear();
512 }
513