xref: /llvm-project/bolt/lib/Core/MCPlusBuilder.cpp (revision a9cd49d50e88aa142e6d57de90321d8810e1027f) 
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 Optional<uint32_t> MCPlusBuilder::getOffset(const MCInst &Inst) const {
232   Optional<int64_t> Value = getAnnotationOpValue(Inst, MCAnnotation::kOffset);
233   if (!Value)
234     return NoneType();
235   return static_cast<uint32_t>(*Value);
236 }
237 
238 uint32_t MCPlusBuilder::getOffsetWithDefault(const MCInst &Inst,
239                                              uint32_t Default) const {
240   if (Optional<uint32_t> Offset = getOffset(Inst))
241     return *Offset;
242   return Default;
243 }
244 
245 bool MCPlusBuilder::setOffset(MCInst &Inst, uint32_t Offset,
246                               AllocatorIdTy AllocatorId) {
247   setAnnotationOpValue(Inst, MCAnnotation::kOffset, Offset, AllocatorId);
248   return true;
249 }
250 
251 bool MCPlusBuilder::clearOffset(MCInst &Inst) {
252   if (!hasAnnotation(Inst, MCAnnotation::kOffset))
253     return false;
254   removeAnnotation(Inst, MCAnnotation::kOffset);
255   return true;
256 }
257 
258 bool MCPlusBuilder::hasAnnotation(const MCInst &Inst, unsigned Index) const {
259   const MCInst *AnnotationInst = getAnnotationInst(Inst);
260   if (!AnnotationInst)
261     return false;
262 
263   return (bool)getAnnotationOpValue(Inst, Index);
264 }
265 
266 bool MCPlusBuilder::removeAnnotation(MCInst &Inst, unsigned Index) {
267   MCInst *AnnotationInst = getAnnotationInst(Inst);
268   if (!AnnotationInst)
269     return false;
270 
271   for (int I = AnnotationInst->getNumOperands() - 1; I >= 0; --I) {
272     int64_t ImmValue = AnnotationInst->getOperand(I).getImm();
273     if (extractAnnotationIndex(ImmValue) == Index) {
274       AnnotationInst->erase(AnnotationInst->begin() + I);
275       return true;
276     }
277   }
278   return false;
279 }
280 
281 void MCPlusBuilder::stripAnnotations(MCInst &Inst, bool KeepTC) {
282   MCInst *AnnotationInst = getAnnotationInst(Inst);
283   if (!AnnotationInst)
284     return;
285   // Preserve TailCall annotation.
286   auto IsTC = hasAnnotation(Inst, MCAnnotation::kTailCall);
287 
288   Inst.erase(std::prev(Inst.end()));
289   if (KeepTC && IsTC)
290     setTailCall(Inst);
291 }
292 
293 void MCPlusBuilder::printAnnotations(const MCInst &Inst,
294                                      raw_ostream &OS) const {
295   const MCInst *AnnotationInst = getAnnotationInst(Inst);
296   if (!AnnotationInst)
297     return;
298 
299   for (unsigned I = 0; I < AnnotationInst->getNumOperands(); ++I) {
300     const int64_t Imm = AnnotationInst->getOperand(I).getImm();
301     const unsigned Index = extractAnnotationIndex(Imm);
302     const int64_t Value = extractAnnotationValue(Imm);
303     const auto *Annotation = reinterpret_cast<const MCAnnotation *>(Value);
304     if (Index >= MCAnnotation::kGeneric) {
305       OS << " # " << AnnotationNames[Index - MCAnnotation::kGeneric] << ": ";
306       Annotation->print(OS);
307     }
308   }
309 }
310 
311 bool MCPlusBuilder::evaluateBranch(const MCInst &Inst, uint64_t Addr,
312                                    uint64_t Size, uint64_t &Target) const {
313   return Analysis->evaluateBranch(Inst, Addr, Size, Target);
314 }
315 
316 void MCPlusBuilder::getClobberedRegs(const MCInst &Inst,
317                                      BitVector &Regs) const {
318   if (isPrefix(Inst) || isCFI(Inst))
319     return;
320 
321   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
322 
323   const MCPhysReg *ImplicitDefs = InstInfo.getImplicitDefs();
324   for (unsigned I = 0, E = InstInfo.getNumImplicitDefs(); I != E; ++I)
325     Regs |= getAliases(ImplicitDefs[I], /*OnlySmaller=*/false);
326 
327   for (unsigned I = 0, E = InstInfo.getNumDefs(); I != E; ++I) {
328     const MCOperand &Operand = Inst.getOperand(I);
329     assert(Operand.isReg());
330     Regs |= getAliases(Operand.getReg(), /*OnlySmaller=*/false);
331   }
332 }
333 
334 void MCPlusBuilder::getTouchedRegs(const MCInst &Inst, BitVector &Regs) const {
335   if (isPrefix(Inst) || isCFI(Inst))
336     return;
337 
338   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
339 
340   const MCPhysReg *ImplicitDefs = InstInfo.getImplicitDefs();
341   for (unsigned I = 0, E = InstInfo.getNumImplicitDefs(); I != E; ++I)
342     Regs |= getAliases(ImplicitDefs[I], /*OnlySmaller=*/false);
343   const MCPhysReg *ImplicitUses = InstInfo.getImplicitUses();
344   for (unsigned I = 0, E = InstInfo.getNumImplicitUses(); I != E; ++I)
345     Regs |= getAliases(ImplicitUses[I], /*OnlySmaller=*/false);
346 
347   for (unsigned I = 0, E = Inst.getNumOperands(); I != E; ++I) {
348     if (!Inst.getOperand(I).isReg())
349       continue;
350     Regs |= getAliases(Inst.getOperand(I).getReg(), /*OnlySmaller=*/false);
351   }
352 }
353 
354 void MCPlusBuilder::getWrittenRegs(const MCInst &Inst, BitVector &Regs) const {
355   if (isPrefix(Inst) || isCFI(Inst))
356     return;
357 
358   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
359 
360   const MCPhysReg *ImplicitDefs = InstInfo.getImplicitDefs();
361   for (unsigned I = 0, E = InstInfo.getNumImplicitDefs(); I != E; ++I)
362     Regs |= getAliases(ImplicitDefs[I], /*OnlySmaller=*/true);
363 
364   for (unsigned I = 0, E = InstInfo.getNumDefs(); I != E; ++I) {
365     const MCOperand &Operand = Inst.getOperand(I);
366     assert(Operand.isReg());
367     Regs |= getAliases(Operand.getReg(), /*OnlySmaller=*/true);
368   }
369 }
370 
371 void MCPlusBuilder::getUsedRegs(const MCInst &Inst, BitVector &Regs) const {
372   if (isPrefix(Inst) || isCFI(Inst))
373     return;
374 
375   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
376 
377   const MCPhysReg *ImplicitUses = InstInfo.getImplicitUses();
378   for (unsigned I = 0, E = InstInfo.getNumImplicitUses(); I != E; ++I)
379     Regs |= getAliases(ImplicitUses[I], /*OnlySmaller=*/true);
380 
381   for (unsigned I = 0, E = Inst.getNumOperands(); I != E; ++I) {
382     if (!Inst.getOperand(I).isReg())
383       continue;
384     Regs |= getAliases(Inst.getOperand(I).getReg(), /*OnlySmaller=*/true);
385   }
386 }
387 
388 void MCPlusBuilder::getSrcRegs(const MCInst &Inst, BitVector &Regs) const {
389   if (isPrefix(Inst) || isCFI(Inst))
390     return;
391 
392   if (isCall(Inst)) {
393     BitVector CallRegs = BitVector(Regs.size(), false);
394     getCalleeSavedRegs(CallRegs);
395     CallRegs.flip();
396     Regs |= CallRegs;
397     return;
398   }
399 
400   if (isReturn(Inst)) {
401     getDefaultLiveOut(Regs);
402     return;
403   }
404 
405   if (isRep(Inst))
406     getRepRegs(Regs);
407 
408   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
409 
410   const MCPhysReg *ImplicitUses = InstInfo.getImplicitUses();
411   for (unsigned I = 0, E = InstInfo.getNumImplicitUses(); I != E; ++I)
412     Regs |= getAliases(ImplicitUses[I], /*OnlySmaller=*/true);
413 
414   for (unsigned I = InstInfo.getNumDefs(), E = InstInfo.getNumOperands();
415        I != E; ++I) {
416     if (!Inst.getOperand(I).isReg())
417       continue;
418     Regs |= getAliases(Inst.getOperand(I).getReg(), /*OnlySmaller=*/true);
419   }
420 }
421 
422 bool MCPlusBuilder::hasDefOfPhysReg(const MCInst &MI, unsigned Reg) const {
423   const MCInstrDesc &InstInfo = Info->get(MI.getOpcode());
424   return InstInfo.hasDefOfPhysReg(MI, Reg, *RegInfo);
425 }
426 
427 bool MCPlusBuilder::hasUseOfPhysReg(const MCInst &MI, unsigned Reg) const {
428   const MCInstrDesc &InstInfo = Info->get(MI.getOpcode());
429   for (int I = InstInfo.NumDefs; I < InstInfo.NumOperands; ++I)
430     if (MI.getOperand(I).isReg() &&
431         RegInfo->isSubRegisterEq(Reg, MI.getOperand(I).getReg()))
432       return true;
433   if (const uint16_t *ImpUses = InstInfo.ImplicitUses) {
434     for (; *ImpUses; ++ImpUses)
435       if (*ImpUses == Reg || RegInfo->isSubRegister(Reg, *ImpUses))
436         return true;
437   }
438   return false;
439 }
440 
441 const BitVector &MCPlusBuilder::getAliases(MCPhysReg Reg,
442                                            bool OnlySmaller) const {
443   // AliasMap caches a mapping of registers to the set of registers that
444   // alias (are sub or superregs of itself, including itself).
445   static std::vector<BitVector> AliasMap;
446   static std::vector<MCPhysReg> SuperReg;
447 
448   if (AliasMap.size() > 0) {
449     if (OnlySmaller)
450       return AliasMap[Reg];
451     return AliasMap[SuperReg[Reg]];
452   }
453   // Build alias map
454   for (MCPhysReg I = 0, E = RegInfo->getNumRegs(); I != E; ++I) {
455     BitVector BV(RegInfo->getNumRegs(), false);
456     BV.set(I);
457     AliasMap.emplace_back(std::move(BV));
458     SuperReg.emplace_back(I);
459   }
460   std::queue<MCPhysReg> Worklist;
461   // Propagate alias info upwards. Skip reg 0 (mapped to NoRegister)
462   for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I < E; ++I)
463     Worklist.push(I);
464   while (!Worklist.empty()) {
465     MCPhysReg I = Worklist.front();
466     Worklist.pop();
467     for (MCSubRegIterator SI(I, RegInfo); SI.isValid(); ++SI)
468       AliasMap[I] |= AliasMap[*SI];
469     for (MCSuperRegIterator SI(I, RegInfo); SI.isValid(); ++SI)
470       Worklist.push(*SI);
471   }
472   // Propagate parent reg downwards
473   for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I < E; ++I)
474     Worklist.push(I);
475   while (!Worklist.empty()) {
476     MCPhysReg I = Worklist.front();
477     Worklist.pop();
478     for (MCSubRegIterator SI(I, RegInfo); SI.isValid(); ++SI) {
479       SuperReg[*SI] = SuperReg[I];
480       Worklist.push(*SI);
481     }
482   }
483 
484   LLVM_DEBUG({
485     dbgs() << "Dumping reg alias table:\n";
486     for (MCPhysReg I = 0, E = RegInfo->getNumRegs(); I != E; ++I) {
487       dbgs() << "Reg " << I << ": ";
488       const BitVector &BV = AliasMap[SuperReg[I]];
489       int Idx = BV.find_first();
490       while (Idx != -1) {
491         dbgs() << Idx << " ";
492         Idx = BV.find_next(Idx);
493       }
494       dbgs() << "\n";
495     }
496   });
497 
498   if (OnlySmaller)
499     return AliasMap[Reg];
500   return AliasMap[SuperReg[Reg]];
501 }
502 
503 uint8_t MCPlusBuilder::getRegSize(MCPhysReg Reg) const {
504   // SizeMap caches a mapping of registers to their sizes
505   static std::vector<uint8_t> SizeMap;
506 
507   if (SizeMap.size() > 0) {
508     return SizeMap[Reg];
509   }
510   SizeMap = std::vector<uint8_t>(RegInfo->getNumRegs());
511   // Build size map
512   for (auto I = RegInfo->regclass_begin(), E = RegInfo->regclass_end(); I != E;
513        ++I) {
514     for (MCPhysReg Reg : *I)
515       SizeMap[Reg] = I->getSizeInBits() / 8;
516   }
517 
518   return SizeMap[Reg];
519 }
520 
521 bool MCPlusBuilder::setOperandToSymbolRef(MCInst &Inst, int OpNum,
522                                           const MCSymbol *Symbol,
523                                           int64_t Addend, MCContext *Ctx,
524                                           uint64_t RelType) const {
525   MCOperand Operand;
526   if (!Addend) {
527     Operand = MCOperand::createExpr(getTargetExprFor(
528         Inst, MCSymbolRefExpr::create(Symbol, *Ctx), *Ctx, RelType));
529   } else {
530     Operand = MCOperand::createExpr(getTargetExprFor(
531         Inst,
532         MCBinaryExpr::createAdd(MCSymbolRefExpr::create(Symbol, *Ctx),
533                                 MCConstantExpr::create(Addend, *Ctx), *Ctx),
534         *Ctx, RelType));
535   }
536   Inst.getOperand(OpNum) = Operand;
537   return true;
538 }
539