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