1 //===- bolt/Core/MCPlusBuilder.cpp - Interface for MCPlus -----------------===//
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 file implements the MCPlusBuilder class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "bolt/Core/MCPlusBuilder.h"
14 #include "bolt/Core/MCPlus.h"
15 #include "llvm/MC/MCInst.h"
16 #include "llvm/MC/MCInstrAnalysis.h"
17 #include "llvm/MC/MCInstrDesc.h"
18 #include "llvm/MC/MCInstrInfo.h"
19 #include "llvm/Support/Debug.h"
20 #include <cstdint>
21 #include <queue>
22 
23 #define DEBUG_TYPE "mcplus"
24 
25 using namespace llvm;
26 using namespace bolt;
27 using namespace MCPlus;
28 
29 bool MCPlusBuilder::equals(const MCInst &A, const MCInst &B,
30                            CompFuncTy Comp) const {
31   if (A.getOpcode() != B.getOpcode())
32     return false;
33 
34   unsigned NumOperands = MCPlus::getNumPrimeOperands(A);
35   if (NumOperands != MCPlus::getNumPrimeOperands(B))
36     return false;
37 
38   for (unsigned Index = 0; Index < NumOperands; ++Index)
39     if (!equals(A.getOperand(Index), B.getOperand(Index), Comp))
40       return false;
41 
42   return true;
43 }
44 
45 bool MCPlusBuilder::equals(const MCOperand &A, const MCOperand &B,
46                            CompFuncTy Comp) const {
47   if (A.isReg()) {
48     if (!B.isReg())
49       return false;
50     return A.getReg() == B.getReg();
51   } else if (A.isImm()) {
52     if (!B.isImm())
53       return false;
54     return A.getImm() == B.getImm();
55   } else if (A.isSFPImm()) {
56     if (!B.isSFPImm())
57       return false;
58     return A.getSFPImm() == B.getSFPImm();
59   } else if (A.isDFPImm()) {
60     if (!B.isDFPImm())
61       return false;
62     return A.getDFPImm() == B.getDFPImm();
63   } else if (A.isExpr()) {
64     if (!B.isExpr())
65       return false;
66     return equals(*A.getExpr(), *B.getExpr(), Comp);
67   } else {
68     llvm_unreachable("unexpected operand kind");
69     return false;
70   }
71 }
72 
73 bool MCPlusBuilder::equals(const MCExpr &A, const MCExpr &B,
74                            CompFuncTy Comp) const {
75   if (A.getKind() != B.getKind())
76     return false;
77 
78   switch (A.getKind()) {
79   case MCExpr::Constant: {
80     const auto &ConstA = cast<MCConstantExpr>(A);
81     const auto &ConstB = cast<MCConstantExpr>(B);
82     return ConstA.getValue() == ConstB.getValue();
83   }
84 
85   case MCExpr::SymbolRef: {
86     const MCSymbolRefExpr &SymbolA = cast<MCSymbolRefExpr>(A);
87     const MCSymbolRefExpr &SymbolB = cast<MCSymbolRefExpr>(B);
88     return SymbolA.getKind() == SymbolB.getKind() &&
89            Comp(&SymbolA.getSymbol(), &SymbolB.getSymbol());
90   }
91 
92   case MCExpr::Unary: {
93     const auto &UnaryA = cast<MCUnaryExpr>(A);
94     const auto &UnaryB = cast<MCUnaryExpr>(B);
95     return UnaryA.getOpcode() == UnaryB.getOpcode() &&
96            equals(*UnaryA.getSubExpr(), *UnaryB.getSubExpr(), Comp);
97   }
98 
99   case MCExpr::Binary: {
100     const auto &BinaryA = cast<MCBinaryExpr>(A);
101     const auto &BinaryB = cast<MCBinaryExpr>(B);
102     return BinaryA.getOpcode() == BinaryB.getOpcode() &&
103            equals(*BinaryA.getLHS(), *BinaryB.getLHS(), Comp) &&
104            equals(*BinaryA.getRHS(), *BinaryB.getRHS(), Comp);
105   }
106 
107   case MCExpr::Target: {
108     const auto &TargetExprA = cast<MCTargetExpr>(A);
109     const auto &TargetExprB = cast<MCTargetExpr>(B);
110     return equals(TargetExprA, TargetExprB, Comp);
111   }
112   }
113 
114   llvm_unreachable("Invalid expression kind!");
115 }
116 
117 bool MCPlusBuilder::equals(const MCTargetExpr &A, const MCTargetExpr &B,
118                            CompFuncTy Comp) const {
119   llvm_unreachable("target-specific expressions are unsupported");
120 }
121 
122 void MCPlusBuilder::setTailCall(MCInst &Inst) {
123   assert(!hasAnnotation(Inst, MCAnnotation::kTailCall));
124   setAnnotationOpValue(Inst, MCAnnotation::kTailCall, true);
125 }
126 
127 bool MCPlusBuilder::isTailCall(const MCInst &Inst) const {
128   if (hasAnnotation(Inst, MCAnnotation::kTailCall))
129     return true;
130   if (getConditionalTailCall(Inst))
131     return true;
132   return false;
133 }
134 
135 Optional<MCLandingPad> MCPlusBuilder::getEHInfo(const MCInst &Inst) const {
136   if (!isCall(Inst))
137     return NoneType();
138   Optional<int64_t> LPSym =
139       getAnnotationOpValue(Inst, MCAnnotation::kEHLandingPad);
140   if (!LPSym)
141     return NoneType();
142   Optional<int64_t> Action =
143       getAnnotationOpValue(Inst, MCAnnotation::kEHAction);
144   if (!Action)
145     return NoneType();
146 
147   return std::make_pair(reinterpret_cast<const MCSymbol *>(*LPSym),
148                         static_cast<uint64_t>(*Action));
149 }
150 
151 void MCPlusBuilder::addEHInfo(MCInst &Inst, const MCLandingPad &LP) {
152   if (isCall(Inst)) {
153     assert(!getEHInfo(Inst));
154     setAnnotationOpValue(Inst, MCAnnotation::kEHLandingPad,
155                          reinterpret_cast<int64_t>(LP.first));
156     setAnnotationOpValue(Inst, MCAnnotation::kEHAction,
157                          static_cast<int64_t>(LP.second));
158   }
159 }
160 
161 int64_t MCPlusBuilder::getGnuArgsSize(const MCInst &Inst) const {
162   Optional<int64_t> Value =
163       getAnnotationOpValue(Inst, MCAnnotation::kGnuArgsSize);
164   if (!Value)
165     return -1LL;
166   return *Value;
167 }
168 
169 void MCPlusBuilder::addGnuArgsSize(MCInst &Inst, int64_t GnuArgsSize,
170                                    AllocatorIdTy AllocId) {
171   assert(GnuArgsSize >= 0 && "cannot set GNU_args_size to negative value");
172   assert(getGnuArgsSize(Inst) == -1LL && "GNU_args_size already set");
173   assert(isInvoke(Inst) && "GNU_args_size can only be set for invoke");
174 
175   setAnnotationOpValue(Inst, MCAnnotation::kGnuArgsSize, GnuArgsSize, AllocId);
176 }
177 
178 uint64_t MCPlusBuilder::getJumpTable(const MCInst &Inst) const {
179   Optional<int64_t> Value =
180       getAnnotationOpValue(Inst, MCAnnotation::kJumpTable);
181   if (!Value)
182     return 0;
183   return *Value;
184 }
185 
186 uint16_t MCPlusBuilder::getJumpTableIndexReg(const MCInst &Inst) const {
187   return getAnnotationAs<uint16_t>(Inst, "JTIndexReg");
188 }
189 
190 bool MCPlusBuilder::setJumpTable(MCInst &Inst, uint64_t Value,
191                                  uint16_t IndexReg, AllocatorIdTy AllocId) {
192   if (!isIndirectBranch(Inst))
193     return false;
194   setAnnotationOpValue(Inst, MCAnnotation::kJumpTable, Value, AllocId);
195   getOrCreateAnnotationAs<uint16_t>(Inst, "JTIndexReg", AllocId) = IndexReg;
196   return true;
197 }
198 
199 bool MCPlusBuilder::unsetJumpTable(MCInst &Inst) {
200   if (!getJumpTable(Inst))
201     return false;
202   removeAnnotation(Inst, MCAnnotation::kJumpTable);
203   removeAnnotation(Inst, "JTIndexReg");
204   return true;
205 }
206 
207 Optional<uint64_t>
208 MCPlusBuilder::getConditionalTailCall(const MCInst &Inst) const {
209   Optional<int64_t> Value =
210       getAnnotationOpValue(Inst, MCAnnotation::kConditionalTailCall);
211   if (!Value)
212     return NoneType();
213   return static_cast<uint64_t>(*Value);
214 }
215 
216 bool MCPlusBuilder::setConditionalTailCall(MCInst &Inst, uint64_t Dest) {
217   if (!isConditionalBranch(Inst))
218     return false;
219 
220   setAnnotationOpValue(Inst, MCAnnotation::kConditionalTailCall, Dest);
221   return true;
222 }
223 
224 bool MCPlusBuilder::unsetConditionalTailCall(MCInst &Inst) {
225   if (!getConditionalTailCall(Inst))
226     return false;
227   removeAnnotation(Inst, MCAnnotation::kConditionalTailCall);
228   return true;
229 }
230 
231 bool MCPlusBuilder::hasAnnotation(const MCInst &Inst, unsigned Index) const {
232   const MCInst *AnnotationInst = getAnnotationInst(Inst);
233   if (!AnnotationInst)
234     return false;
235 
236   return (bool)getAnnotationOpValue(Inst, Index);
237 }
238 
239 bool MCPlusBuilder::removeAnnotation(MCInst &Inst, unsigned Index) {
240   MCInst *AnnotationInst = getAnnotationInst(Inst);
241   if (!AnnotationInst)
242     return false;
243 
244   for (int I = AnnotationInst->getNumOperands() - 1; I >= 0; --I) {
245     int64_t ImmValue = AnnotationInst->getOperand(I).getImm();
246     if (extractAnnotationIndex(ImmValue) == Index) {
247       AnnotationInst->erase(AnnotationInst->begin() + I);
248       return true;
249     }
250   }
251   return false;
252 }
253 
254 void MCPlusBuilder::stripAnnotations(MCInst &Inst, bool KeepTC) {
255   MCInst *AnnotationInst = getAnnotationInst(Inst);
256   if (!AnnotationInst)
257     return;
258   // Preserve TailCall annotation.
259   auto IsTC = hasAnnotation(Inst, MCAnnotation::kTailCall);
260 
261   Inst.erase(std::prev(Inst.end()));
262   if (KeepTC && IsTC)
263     setTailCall(Inst);
264 }
265 
266 void MCPlusBuilder::printAnnotations(const MCInst &Inst,
267                                      raw_ostream &OS) const {
268   const MCInst *AnnotationInst = getAnnotationInst(Inst);
269   if (!AnnotationInst)
270     return;
271 
272   for (unsigned I = 0; I < AnnotationInst->getNumOperands(); ++I) {
273     const int64_t Imm = AnnotationInst->getOperand(I).getImm();
274     const unsigned Index = extractAnnotationIndex(Imm);
275     const int64_t Value = extractAnnotationValue(Imm);
276     const auto *Annotation = reinterpret_cast<const MCAnnotation *>(Value);
277     if (Index >= MCAnnotation::kGeneric) {
278       OS << " # " << AnnotationNames[Index - MCAnnotation::kGeneric] << ": ";
279       Annotation->print(OS);
280     }
281   }
282 }
283 
284 bool MCPlusBuilder::evaluateBranch(const MCInst &Inst, uint64_t Addr,
285                                    uint64_t Size, uint64_t &Target) const {
286   return Analysis->evaluateBranch(Inst, Addr, Size, Target);
287 }
288 
289 void MCPlusBuilder::getClobberedRegs(const MCInst &Inst,
290                                      BitVector &Regs) const {
291   if (isPrefix(Inst) || isCFI(Inst))
292     return;
293 
294   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
295 
296   const MCPhysReg *ImplicitDefs = InstInfo.getImplicitDefs();
297   for (unsigned I = 0, E = InstInfo.getNumImplicitDefs(); I != E; ++I)
298     Regs |= getAliases(ImplicitDefs[I], /*OnlySmaller=*/false);
299 
300   for (unsigned I = 0, E = InstInfo.getNumDefs(); I != E; ++I) {
301     const MCOperand &Operand = Inst.getOperand(I);
302     assert(Operand.isReg());
303     Regs |= getAliases(Operand.getReg(), /*OnlySmaller=*/false);
304   }
305 }
306 
307 void MCPlusBuilder::getTouchedRegs(const MCInst &Inst, BitVector &Regs) const {
308   if (isPrefix(Inst) || isCFI(Inst))
309     return;
310 
311   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
312 
313   const MCPhysReg *ImplicitDefs = InstInfo.getImplicitDefs();
314   for (unsigned I = 0, E = InstInfo.getNumImplicitDefs(); I != E; ++I)
315     Regs |= getAliases(ImplicitDefs[I], /*OnlySmaller=*/false);
316   const MCPhysReg *ImplicitUses = InstInfo.getImplicitUses();
317   for (unsigned I = 0, E = InstInfo.getNumImplicitUses(); I != E; ++I)
318     Regs |= getAliases(ImplicitUses[I], /*OnlySmaller=*/false);
319 
320   for (unsigned I = 0, E = Inst.getNumOperands(); I != E; ++I) {
321     if (!Inst.getOperand(I).isReg())
322       continue;
323     Regs |= getAliases(Inst.getOperand(I).getReg(), /*OnlySmaller=*/false);
324   }
325 }
326 
327 void MCPlusBuilder::getWrittenRegs(const MCInst &Inst, BitVector &Regs) const {
328   if (isPrefix(Inst) || isCFI(Inst))
329     return;
330 
331   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
332 
333   const MCPhysReg *ImplicitDefs = InstInfo.getImplicitDefs();
334   for (unsigned I = 0, E = InstInfo.getNumImplicitDefs(); I != E; ++I)
335     Regs |= getAliases(ImplicitDefs[I], /*OnlySmaller=*/true);
336 
337   for (unsigned I = 0, E = InstInfo.getNumDefs(); I != E; ++I) {
338     const MCOperand &Operand = Inst.getOperand(I);
339     assert(Operand.isReg());
340     Regs |= getAliases(Operand.getReg(), /*OnlySmaller=*/true);
341   }
342 }
343 
344 void MCPlusBuilder::getUsedRegs(const MCInst &Inst, BitVector &Regs) const {
345   if (isPrefix(Inst) || isCFI(Inst))
346     return;
347 
348   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
349 
350   const MCPhysReg *ImplicitUses = InstInfo.getImplicitUses();
351   for (unsigned I = 0, E = InstInfo.getNumImplicitUses(); I != E; ++I)
352     Regs |= getAliases(ImplicitUses[I], /*OnlySmaller=*/true);
353 
354   for (unsigned I = 0, E = Inst.getNumOperands(); I != E; ++I) {
355     if (!Inst.getOperand(I).isReg())
356       continue;
357     Regs |= getAliases(Inst.getOperand(I).getReg(), /*OnlySmaller=*/true);
358   }
359 }
360 
361 void MCPlusBuilder::getSrcRegs(const MCInst &Inst, BitVector &Regs) const {
362   if (isPrefix(Inst) || isCFI(Inst))
363     return;
364 
365   if (isCall(Inst)) {
366     BitVector CallRegs = BitVector(Regs.size(), false);
367     getCalleeSavedRegs(CallRegs);
368     CallRegs.flip();
369     Regs |= CallRegs;
370     return;
371   }
372 
373   if (isReturn(Inst)) {
374     getDefaultLiveOut(Regs);
375     return;
376   }
377 
378   if (isRep(Inst))
379     getRepRegs(Regs);
380 
381   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
382 
383   const MCPhysReg *ImplicitUses = InstInfo.getImplicitUses();
384   for (unsigned I = 0, E = InstInfo.getNumImplicitUses(); I != E; ++I)
385     Regs |= getAliases(ImplicitUses[I], /*OnlySmaller=*/true);
386 
387   for (unsigned I = InstInfo.getNumDefs(), E = InstInfo.getNumOperands();
388        I != E; ++I) {
389     if (!Inst.getOperand(I).isReg())
390       continue;
391     Regs |= getAliases(Inst.getOperand(I).getReg(), /*OnlySmaller=*/true);
392   }
393 }
394 
395 bool MCPlusBuilder::hasDefOfPhysReg(const MCInst &MI, unsigned Reg) const {
396   const MCInstrDesc &InstInfo = Info->get(MI.getOpcode());
397   return InstInfo.hasDefOfPhysReg(MI, Reg, *RegInfo);
398 }
399 
400 bool MCPlusBuilder::hasUseOfPhysReg(const MCInst &MI, unsigned Reg) const {
401   const MCInstrDesc &InstInfo = Info->get(MI.getOpcode());
402   for (int I = InstInfo.NumDefs; I < InstInfo.NumOperands; ++I)
403     if (MI.getOperand(I).isReg() &&
404         RegInfo->isSubRegisterEq(Reg, MI.getOperand(I).getReg()))
405       return true;
406   if (const uint16_t *ImpUses = InstInfo.ImplicitUses) {
407     for (; *ImpUses; ++ImpUses)
408       if (*ImpUses == Reg || RegInfo->isSubRegister(Reg, *ImpUses))
409         return true;
410   }
411   return false;
412 }
413 
414 const BitVector &MCPlusBuilder::getAliases(MCPhysReg Reg,
415                                            bool OnlySmaller) const {
416   // AliasMap caches a mapping of registers to the set of registers that
417   // alias (are sub or superregs of itself, including itself).
418   static std::vector<BitVector> AliasMap;
419   static std::vector<MCPhysReg> SuperReg;
420 
421   if (AliasMap.size() > 0) {
422     if (OnlySmaller)
423       return AliasMap[Reg];
424     return AliasMap[SuperReg[Reg]];
425   }
426   // Build alias map
427   for (MCPhysReg I = 0, E = RegInfo->getNumRegs(); I != E; ++I) {
428     BitVector BV(RegInfo->getNumRegs(), false);
429     BV.set(I);
430     AliasMap.emplace_back(std::move(BV));
431     SuperReg.emplace_back(I);
432   }
433   std::queue<MCPhysReg> Worklist;
434   // Propagate alias info upwards. Skip reg 0 (mapped to NoRegister)
435   for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I < E; ++I)
436     Worklist.push(I);
437   while (!Worklist.empty()) {
438     MCPhysReg I = Worklist.front();
439     Worklist.pop();
440     for (MCSubRegIterator SI(I, RegInfo); SI.isValid(); ++SI)
441       AliasMap[I] |= AliasMap[*SI];
442     for (MCSuperRegIterator SI(I, RegInfo); SI.isValid(); ++SI)
443       Worklist.push(*SI);
444   }
445   // Propagate parent reg downwards
446   for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I < E; ++I)
447     Worklist.push(I);
448   while (!Worklist.empty()) {
449     MCPhysReg I = Worklist.front();
450     Worklist.pop();
451     for (MCSubRegIterator SI(I, RegInfo); SI.isValid(); ++SI) {
452       SuperReg[*SI] = SuperReg[I];
453       Worklist.push(*SI);
454     }
455   }
456 
457   LLVM_DEBUG({
458     dbgs() << "Dumping reg alias table:\n";
459     for (MCPhysReg I = 0, E = RegInfo->getNumRegs(); I != E; ++I) {
460       dbgs() << "Reg " << I << ": ";
461       const BitVector &BV = AliasMap[SuperReg[I]];
462       int Idx = BV.find_first();
463       while (Idx != -1) {
464         dbgs() << Idx << " ";
465         Idx = BV.find_next(Idx);
466       }
467       dbgs() << "\n";
468     }
469   });
470 
471   if (OnlySmaller)
472     return AliasMap[Reg];
473   return AliasMap[SuperReg[Reg]];
474 }
475 
476 uint8_t MCPlusBuilder::getRegSize(MCPhysReg Reg) const {
477   // SizeMap caches a mapping of registers to their sizes
478   static std::vector<uint8_t> SizeMap;
479 
480   if (SizeMap.size() > 0) {
481     return SizeMap[Reg];
482   }
483   SizeMap = std::vector<uint8_t>(RegInfo->getNumRegs());
484   // Build size map
485   for (auto I = RegInfo->regclass_begin(), E = RegInfo->regclass_end(); I != E;
486        ++I) {
487     for (MCPhysReg Reg : *I)
488       SizeMap[Reg] = I->getSizeInBits() / 8;
489   }
490 
491   return SizeMap[Reg];
492 }
493 
494 bool MCPlusBuilder::setOperandToSymbolRef(MCInst &Inst, int OpNum,
495                                           const MCSymbol *Symbol,
496                                           int64_t Addend, MCContext *Ctx,
497                                           uint64_t RelType) const {
498   MCOperand Operand;
499   if (!Addend) {
500     Operand = MCOperand::createExpr(getTargetExprFor(
501         Inst, MCSymbolRefExpr::create(Symbol, *Ctx), *Ctx, RelType));
502   } else {
503     Operand = MCOperand::createExpr(getTargetExprFor(
504         Inst,
505         MCBinaryExpr::createAdd(MCSymbolRefExpr::create(Symbol, *Ctx),
506                                 MCConstantExpr::create(Addend, *Ctx), *Ctx),
507         *Ctx, RelType));
508   }
509   Inst.getOperand(OpNum) = Operand;
510   return true;
511 }
512