xref: /llvm-project/bolt/lib/Core/MCPlusBuilder.cpp (revision 74e0a26fd114cac39e251e4c2b6fbbadd6009887) 
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) const {
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 std::optional<MCLandingPad> MCPlusBuilder::getEHInfo(const MCInst &Inst) const {
137   if (!isCall(Inst))
138     return std::nullopt;
139   std::optional<int64_t> LPSym =
140       getAnnotationOpValue(Inst, MCAnnotation::kEHLandingPad);
141   if (!LPSym)
142     return std::nullopt;
143   std::optional<int64_t> Action =
144       getAnnotationOpValue(Inst, MCAnnotation::kEHAction);
145   if (!Action)
146     return std::nullopt;
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) const {
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 bool MCPlusBuilder::updateEHInfo(MCInst &Inst, const MCLandingPad &LP) const {
163   if (!isInvoke(Inst))
164     return false;
165 
166   setAnnotationOpValue(Inst, MCAnnotation::kEHLandingPad,
167                        reinterpret_cast<int64_t>(LP.first));
168   setAnnotationOpValue(Inst, MCAnnotation::kEHAction,
169                        static_cast<int64_t>(LP.second));
170   return true;
171 }
172 
173 int64_t MCPlusBuilder::getGnuArgsSize(const MCInst &Inst) const {
174   std::optional<int64_t> Value =
175       getAnnotationOpValue(Inst, MCAnnotation::kGnuArgsSize);
176   if (!Value)
177     return -1LL;
178   return *Value;
179 }
180 
181 void MCPlusBuilder::addGnuArgsSize(MCInst &Inst, int64_t GnuArgsSize) const {
182   assert(GnuArgsSize >= 0 && "cannot set GNU_args_size to negative value");
183   assert(getGnuArgsSize(Inst) == -1LL && "GNU_args_size already set");
184   assert(isInvoke(Inst) && "GNU_args_size can only be set for invoke");
185 
186   setAnnotationOpValue(Inst, MCAnnotation::kGnuArgsSize, GnuArgsSize);
187 }
188 
189 uint64_t MCPlusBuilder::getJumpTable(const MCInst &Inst) const {
190   std::optional<int64_t> Value =
191       getAnnotationOpValue(Inst, MCAnnotation::kJumpTable);
192   if (!Value)
193     return 0;
194   return *Value;
195 }
196 
197 uint16_t MCPlusBuilder::getJumpTableIndexReg(const MCInst &Inst) const {
198   return getAnnotationAs<uint16_t>(Inst, "JTIndexReg");
199 }
200 
201 bool MCPlusBuilder::setJumpTable(MCInst &Inst, uint64_t Value,
202                                  uint16_t IndexReg, AllocatorIdTy AllocId) {
203   if (!isIndirectBranch(Inst))
204     return false;
205   setAnnotationOpValue(Inst, MCAnnotation::kJumpTable, Value);
206   getOrCreateAnnotationAs<uint16_t>(Inst, "JTIndexReg", AllocId) = IndexReg;
207   return true;
208 }
209 
210 bool MCPlusBuilder::unsetJumpTable(MCInst &Inst) const {
211   if (!getJumpTable(Inst))
212     return false;
213   removeAnnotation(Inst, MCAnnotation::kJumpTable);
214   removeAnnotation(Inst, "JTIndexReg");
215   return true;
216 }
217 
218 std::optional<uint64_t>
219 MCPlusBuilder::getConditionalTailCall(const MCInst &Inst) const {
220   std::optional<int64_t> Value =
221       getAnnotationOpValue(Inst, MCAnnotation::kConditionalTailCall);
222   if (!Value)
223     return std::nullopt;
224   return static_cast<uint64_t>(*Value);
225 }
226 
227 bool MCPlusBuilder::setConditionalTailCall(MCInst &Inst, uint64_t Dest) const {
228   if (!isConditionalBranch(Inst))
229     return false;
230 
231   setAnnotationOpValue(Inst, MCAnnotation::kConditionalTailCall, Dest);
232   return true;
233 }
234 
235 bool MCPlusBuilder::unsetConditionalTailCall(MCInst &Inst) const {
236   if (!getConditionalTailCall(Inst))
237     return false;
238   removeAnnotation(Inst, MCAnnotation::kConditionalTailCall);
239   return true;
240 }
241 
242 std::optional<uint32_t> MCPlusBuilder::getOffset(const MCInst &Inst) const {
243   std::optional<int64_t> Value =
244       getAnnotationOpValue(Inst, MCAnnotation::kOffset);
245   if (!Value)
246     return std::nullopt;
247   return static_cast<uint32_t>(*Value);
248 }
249 
250 uint32_t MCPlusBuilder::getOffsetWithDefault(const MCInst &Inst,
251                                              uint32_t Default) const {
252   if (std::optional<uint32_t> Offset = getOffset(Inst))
253     return *Offset;
254   return Default;
255 }
256 
257 bool MCPlusBuilder::setOffset(MCInst &Inst, uint32_t Offset) const {
258   setAnnotationOpValue(Inst, MCAnnotation::kOffset, Offset);
259   return true;
260 }
261 
262 bool MCPlusBuilder::clearOffset(MCInst &Inst) const {
263   if (!hasAnnotation(Inst, MCAnnotation::kOffset))
264     return false;
265   removeAnnotation(Inst, MCAnnotation::kOffset);
266   return true;
267 }
268 
269 MCSymbol *MCPlusBuilder::getLabel(const MCInst &Inst) const {
270   if (auto Label = tryGetAnnotationAs<MCSymbol *>(Inst, MCAnnotation::kLabel))
271     return *Label;
272   return nullptr;
273 }
274 
275 bool MCPlusBuilder::setLabel(MCInst &Inst, MCSymbol *Label,
276                              AllocatorIdTy AllocatorId) {
277   getOrCreateAnnotationAs<MCSymbol *>(Inst, MCAnnotation::kLabel, AllocatorId) =
278       Label;
279   return true;
280 }
281 
282 bool MCPlusBuilder::hasAnnotation(const MCInst &Inst, unsigned Index) const {
283   return (bool)getAnnotationOpValue(Inst, Index);
284 }
285 
286 bool MCPlusBuilder::removeAnnotation(MCInst &Inst, unsigned Index) const {
287   std::optional<unsigned> FirstAnnotationOp = getFirstAnnotationOpIndex(Inst);
288   if (!FirstAnnotationOp)
289     return false;
290 
291   for (unsigned I = Inst.getNumOperands() - 1; I >= *FirstAnnotationOp; --I) {
292     const int64_t ImmValue = Inst.getOperand(I).getImm();
293     if (extractAnnotationIndex(ImmValue) == Index) {
294       Inst.erase(Inst.begin() + I);
295       return true;
296     }
297   }
298   return false;
299 }
300 
301 void MCPlusBuilder::stripAnnotations(MCInst &Inst, bool KeepTC) const {
302   KeepTC &= hasAnnotation(Inst, MCAnnotation::kTailCall);
303 
304   removeAnnotations(Inst);
305 
306   if (KeepTC)
307     setTailCall(Inst);
308 }
309 
310 void MCPlusBuilder::printAnnotations(const MCInst &Inst,
311                                      raw_ostream &OS) const {
312   std::optional<unsigned> FirstAnnotationOp = getFirstAnnotationOpIndex(Inst);
313   if (!FirstAnnotationOp)
314     return;
315 
316   for (unsigned I = *FirstAnnotationOp; I < Inst.getNumOperands(); ++I) {
317     const int64_t Imm = Inst.getOperand(I).getImm();
318     const unsigned Index = extractAnnotationIndex(Imm);
319     const int64_t Value = extractAnnotationValue(Imm);
320     const auto *Annotation = reinterpret_cast<const MCAnnotation *>(Value);
321     if (Index >= MCAnnotation::kGeneric) {
322       OS << " # " << AnnotationNames[Index - MCAnnotation::kGeneric] << ": ";
323       Annotation->print(OS);
324     }
325   }
326 }
327 
328 void MCPlusBuilder::getClobberedRegs(const MCInst &Inst,
329                                      BitVector &Regs) const {
330   if (isPrefix(Inst) || isCFI(Inst))
331     return;
332 
333   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
334 
335   for (MCPhysReg ImplicitDef : InstInfo.implicit_defs())
336     Regs |= getAliases(ImplicitDef, /*OnlySmaller=*/false);
337 
338   for (const MCOperand &Operand : defOperands(Inst)) {
339     assert(Operand.isReg());
340     Regs |= getAliases(Operand.getReg(), /*OnlySmaller=*/false);
341   }
342 }
343 
344 void MCPlusBuilder::getTouchedRegs(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   for (MCPhysReg ImplicitDef : InstInfo.implicit_defs())
351     Regs |= getAliases(ImplicitDef, /*OnlySmaller=*/false);
352   for (MCPhysReg ImplicitUse : InstInfo.implicit_uses())
353     Regs |= getAliases(ImplicitUse, /*OnlySmaller=*/false);
354 
355   for (unsigned I = 0, E = Inst.getNumOperands(); I != E; ++I) {
356     if (!Inst.getOperand(I).isReg())
357       continue;
358     Regs |= getAliases(Inst.getOperand(I).getReg(), /*OnlySmaller=*/false);
359   }
360 }
361 
362 void MCPlusBuilder::getWrittenRegs(const MCInst &Inst, BitVector &Regs) const {
363   if (isPrefix(Inst) || isCFI(Inst))
364     return;
365 
366   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
367 
368   for (MCPhysReg ImplicitDef : InstInfo.implicit_defs())
369     Regs |= getAliases(ImplicitDef, /*OnlySmaller=*/true);
370 
371   for (const MCOperand &Operand : defOperands(Inst)) {
372     assert(Operand.isReg());
373     Regs |= getAliases(Operand.getReg(), /*OnlySmaller=*/true);
374   }
375 }
376 
377 void MCPlusBuilder::getUsedRegs(const MCInst &Inst, BitVector &Regs) const {
378   if (isPrefix(Inst) || isCFI(Inst))
379     return;
380 
381   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
382 
383   for (MCPhysReg ImplicitUse : InstInfo.implicit_uses())
384     Regs |= getAliases(ImplicitUse, /*OnlySmaller=*/true);
385 
386   for (unsigned I = 0, E = Inst.getNumOperands(); I != E; ++I) {
387     if (!Inst.getOperand(I).isReg())
388       continue;
389     Regs |= getAliases(Inst.getOperand(I).getReg(), /*OnlySmaller=*/true);
390   }
391 }
392 
393 void MCPlusBuilder::getSrcRegs(const MCInst &Inst, BitVector &Regs) const {
394   if (isPrefix(Inst) || isCFI(Inst))
395     return;
396 
397   if (isCall(Inst)) {
398     BitVector CallRegs = BitVector(Regs.size(), false);
399     getCalleeSavedRegs(CallRegs);
400     CallRegs.flip();
401     Regs |= CallRegs;
402     return;
403   }
404 
405   if (isReturn(Inst)) {
406     getDefaultLiveOut(Regs);
407     return;
408   }
409 
410   if (isRep(Inst))
411     getRepRegs(Regs);
412 
413   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
414 
415   for (MCPhysReg ImplicitUse : InstInfo.implicit_uses())
416     Regs |= getAliases(ImplicitUse, /*OnlySmaller=*/true);
417 
418   for (const MCOperand &Operand : useOperands(Inst))
419     if (Operand.isReg())
420       Regs |= getAliases(Operand.getReg(), /*OnlySmaller=*/true);
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() && MI.getOperand(I).getReg() &&
432         RegInfo->isSubRegisterEq(Reg, MI.getOperand(I).getReg()))
433       return true;
434   for (MCPhysReg ImplicitUse : InstInfo.implicit_uses()) {
435     if (ImplicitUse == Reg || RegInfo->isSubRegister(Reg, ImplicitUse))
436       return true;
437   }
438   return false;
439 }
440 
441 const BitVector &MCPlusBuilder::getAliases(MCPhysReg Reg,
442                                            bool OnlySmaller) const {
443   if (OnlySmaller)
444     return SmallerAliasMap[Reg];
445   return AliasMap[Reg];
446 }
447 
448 void MCPlusBuilder::initAliases() {
449   assert(AliasMap.size() == 0 && SmallerAliasMap.size() == 0);
450   // Build alias map
451   for (MCPhysReg I = 0, E = RegInfo->getNumRegs(); I != E; ++I) {
452     BitVector BV(RegInfo->getNumRegs(), false);
453     BV.set(I);
454     AliasMap.emplace_back(BV);
455     SmallerAliasMap.emplace_back(BV);
456   }
457 
458   // Cache all aliases for each register
459   for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I != E; ++I) {
460     for (MCRegAliasIterator AI(I, RegInfo, true); AI.isValid(); ++AI)
461       AliasMap[I].set(*AI);
462   }
463 
464   // Propagate smaller alias info upwards. Skip reg 0 (mapped to NoRegister)
465   for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I < E; ++I)
466     for (MCSubRegIterator SI(I, RegInfo); SI.isValid(); ++SI)
467       SmallerAliasMap[I] |= SmallerAliasMap[*SI];
468 
469   LLVM_DEBUG({
470     dbgs() << "Dumping reg alias table:\n";
471     for (MCPhysReg I = 0, E = RegInfo->getNumRegs(); I != E; ++I) {
472       dbgs() << "Reg " << I << ": ";
473       const BitVector &BV = AliasMap[I];
474       int Idx = BV.find_first();
475       while (Idx != -1) {
476         dbgs() << Idx << " ";
477         Idx = BV.find_next(Idx);
478       }
479       dbgs() << "\n";
480     }
481   });
482 }
483 
484 void MCPlusBuilder::initSizeMap() {
485   SizeMap.resize(RegInfo->getNumRegs());
486   // Build size map
487   for (auto RC : RegInfo->regclasses())
488     for (MCPhysReg Reg : RC)
489       SizeMap[Reg] = RC.getSizeInBits() / 8;
490 }
491 
492 bool MCPlusBuilder::setOperandToSymbolRef(MCInst &Inst, int OpNum,
493                                           const MCSymbol *Symbol,
494                                           int64_t Addend, MCContext *Ctx,
495                                           uint64_t RelType) const {
496   MCOperand Operand;
497   if (!Addend) {
498     Operand = MCOperand::createExpr(getTargetExprFor(
499         Inst, MCSymbolRefExpr::create(Symbol, *Ctx), *Ctx, RelType));
500   } else {
501     Operand = MCOperand::createExpr(getTargetExprFor(
502         Inst,
503         MCBinaryExpr::createAdd(MCSymbolRefExpr::create(Symbol, *Ctx),
504                                 MCConstantExpr::create(Addend, *Ctx), *Ctx),
505         *Ctx, RelType));
506   }
507   Inst.getOperand(OpNum) = Operand;
508   return true;
509 }
510