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