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