bolt/lib/Core/MCPlusBuilder.cpp

   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 (std::optional<int64_t> Label =
 271           getAnnotationOpValue(Inst, MCAnnotation::kLabel))
 272     return reinterpret_cast<MCSymbol *>(*Label);
 273   return nullptr;
 274 }
 275
 276 bool MCPlusBuilder::setLabel(MCInst &Inst, MCSymbol *Label) const {
 277   setAnnotationOpValue(Inst, MCAnnotation::kLabel,
 278                        reinterpret_cast<int64_t>(Label));
 279   return true;
 280 }
 281
 282 std::optional<uint32_t> MCPlusBuilder::getSize(const MCInst &Inst) const {
 283   if (std::optional<int64_t> Value =
 284           getAnnotationOpValue(Inst, MCAnnotation::kSize))
 285     return static_cast<uint32_t>(*Value);
 286   return std::nullopt;
 287 }
 288
 289 void MCPlusBuilder::setSize(MCInst &Inst, uint32_t Size) const {
 290   setAnnotationOpValue(Inst, MCAnnotation::kSize, Size);
 291 }
 292
 293 bool MCPlusBuilder::hasAnnotation(const MCInst &Inst, unsigned Index) const {
 294   return (bool)getAnnotationOpValue(Inst, Index);
 295 }
 296
 297 bool MCPlusBuilder::removeAnnotation(MCInst &Inst, unsigned Index) const {
 298   std::optional<unsigned> FirstAnnotationOp = getFirstAnnotationOpIndex(Inst);
 299   if (!FirstAnnotationOp)
 300     return false;
 301
 302   for (unsigned I = Inst.getNumOperands() - 1; I >= *FirstAnnotationOp; --I) {
 303     const int64_t ImmValue = Inst.getOperand(I).getImm();
 304     if (extractAnnotationIndex(ImmValue) == Index) {
 305       Inst.erase(Inst.begin() + I);
 306       return true;
 307     }
 308   }
 309   return false;
 310 }
 311
 312 void MCPlusBuilder::stripAnnotations(MCInst &Inst, bool KeepTC) const {
 313   KeepTC &= hasAnnotation(Inst, MCAnnotation::kTailCall);
 314
 315   removeAnnotations(Inst);
 316
 317   if (KeepTC)
 318     setTailCall(Inst);
 319 }
 320
 321 void MCPlusBuilder::printAnnotations(const MCInst &Inst,
 322                                      raw_ostream &OS) const {
 323   std::optional<unsigned> FirstAnnotationOp = getFirstAnnotationOpIndex(Inst);
 324   if (!FirstAnnotationOp)
 325     return;
 326
 327   for (unsigned I = *FirstAnnotationOp; I < Inst.getNumOperands(); ++I) {
 328     const int64_t Imm = Inst.getOperand(I).getImm();
 329     const unsigned Index = extractAnnotationIndex(Imm);
 330     const int64_t Value = extractAnnotationValue(Imm);
 331     const auto *Annotation = reinterpret_cast<const MCAnnotation *>(Value);
 332     if (Index >= MCAnnotation::kGeneric) {
 333       OS << " # " << AnnotationNames[Index - MCAnnotation::kGeneric] << ": ";
 334       Annotation->print(OS);
 335     }
 336   }
 337 }
 338
 339 void MCPlusBuilder::getClobberedRegs(const MCInst &Inst,
 340                                      BitVector &Regs) const {
 341   if (isPrefix(Inst) || isCFI(Inst))
 342     return;
 343
 344   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
 345
 346   for (MCPhysReg ImplicitDef : InstInfo.implicit_defs())
 347     Regs |= getAliases(ImplicitDef, /*OnlySmaller=*/false);
 348
 349   for (const MCOperand &Operand : defOperands(Inst)) {
 350     assert(Operand.isReg());
 351     Regs |= getAliases(Operand.getReg(), /*OnlySmaller=*/false);
 352   }
 353 }
 354
 355 void MCPlusBuilder::getTouchedRegs(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   for (MCPhysReg ImplicitDef : InstInfo.implicit_defs())
 362     Regs |= getAliases(ImplicitDef, /*OnlySmaller=*/false);
 363   for (MCPhysReg ImplicitUse : InstInfo.implicit_uses())
 364     Regs |= getAliases(ImplicitUse, /*OnlySmaller=*/false);
 365
 366   for (unsigned I = 0, E = Inst.getNumOperands(); I != E; ++I) {
 367     if (!Inst.getOperand(I).isReg())
 368       continue;
 369     Regs |= getAliases(Inst.getOperand(I).getReg(), /*OnlySmaller=*/false);
 370   }
 371 }
 372
 373 void MCPlusBuilder::getWrittenRegs(const MCInst &Inst, BitVector &Regs) const {
 374   if (isPrefix(Inst) || isCFI(Inst))
 375     return;
 376
 377   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
 378
 379   for (MCPhysReg ImplicitDef : InstInfo.implicit_defs())
 380     Regs |= getAliases(ImplicitDef, /*OnlySmaller=*/true);
 381
 382   for (const MCOperand &Operand : defOperands(Inst)) {
 383     assert(Operand.isReg());
 384     Regs |= getAliases(Operand.getReg(), /*OnlySmaller=*/true);
 385   }
 386 }
 387
 388 void MCPlusBuilder::getUsedRegs(const MCInst &Inst, BitVector &Regs) const {
 389   if (isPrefix(Inst) || isCFI(Inst))
 390     return;
 391
 392   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
 393
 394   for (MCPhysReg ImplicitUse : InstInfo.implicit_uses())
 395     Regs |= getAliases(ImplicitUse, /*OnlySmaller=*/true);
 396
 397   for (unsigned I = 0, E = Inst.getNumOperands(); I != E; ++I) {
 398     if (!Inst.getOperand(I).isReg())
 399       continue;
 400     Regs |= getAliases(Inst.getOperand(I).getReg(), /*OnlySmaller=*/true);
 401   }
 402 }
 403
 404 void MCPlusBuilder::getSrcRegs(const MCInst &Inst, BitVector &Regs) const {
 405   if (isPrefix(Inst) || isCFI(Inst))
 406     return;
 407
 408   if (isCall(Inst)) {
 409     BitVector CallRegs = BitVector(Regs.size(), false);
 410     getCalleeSavedRegs(CallRegs);
 411     CallRegs.flip();
 412     Regs |= CallRegs;
 413     return;
 414   }
 415
 416   if (isReturn(Inst)) {
 417     getDefaultLiveOut(Regs);
 418     return;
 419   }
 420
 421   if (isRep(Inst))
 422     getRepRegs(Regs);
 423
 424   const MCInstrDesc &InstInfo = Info->get(Inst.getOpcode());
 425
 426   for (MCPhysReg ImplicitUse : InstInfo.implicit_uses())
 427     Regs |= getAliases(ImplicitUse, /*OnlySmaller=*/true);
 428
 429   for (const MCOperand &Operand : useOperands(Inst))
 430     if (Operand.isReg())
 431       Regs |= getAliases(Operand.getReg(), /*OnlySmaller=*/true);
 432 }
 433
 434 bool MCPlusBuilder::hasDefOfPhysReg(const MCInst &MI, unsigned Reg) const {
 435   const MCInstrDesc &InstInfo = Info->get(MI.getOpcode());
 436   return InstInfo.hasDefOfPhysReg(MI, Reg, *RegInfo);
 437 }
 438
 439 bool MCPlusBuilder::hasUseOfPhysReg(const MCInst &MI, unsigned Reg) const {
 440   const MCInstrDesc &InstInfo = Info->get(MI.getOpcode());
 441   for (int I = InstInfo.NumDefs; I < InstInfo.NumOperands; ++I)
 442     if (MI.getOperand(I).isReg() && MI.getOperand(I).getReg() &&
 443         RegInfo->isSubRegisterEq(Reg, MI.getOperand(I).getReg()))
 444       return true;
 445   for (MCPhysReg ImplicitUse : InstInfo.implicit_uses()) {
 446     if (ImplicitUse == Reg || RegInfo->isSubRegister(Reg, ImplicitUse))
 447       return true;
 448   }
 449   return false;
 450 }
 451
 452 const BitVector &MCPlusBuilder::getAliases(MCPhysReg Reg,
 453                                            bool OnlySmaller) const {
 454   if (OnlySmaller)
 455     return SmallerAliasMap[Reg];
 456   return AliasMap[Reg];
 457 }
 458
 459 void MCPlusBuilder::initAliases() {
 460   assert(AliasMap.size() == 0 && SmallerAliasMap.size() == 0);
 461   // Build alias map
 462   for (MCPhysReg I = 0, E = RegInfo->getNumRegs(); I != E; ++I) {
 463     BitVector BV(RegInfo->getNumRegs(), false);
 464     BV.set(I);
 465     AliasMap.emplace_back(BV);
 466     SmallerAliasMap.emplace_back(BV);
 467   }
 468
 469   // Cache all aliases for each register
 470   for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I != E; ++I) {
 471     for (MCRegAliasIterator AI(I, RegInfo, true); AI.isValid(); ++AI)
 472       AliasMap[I].set(*AI);
 473   }
 474
 475   // Propagate smaller alias info upwards. Skip reg 0 (mapped to NoRegister)
 476   for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I < E; ++I)
 477     for (MCSubRegIterator SI(I, RegInfo); SI.isValid(); ++SI)
 478       SmallerAliasMap[I] |= SmallerAliasMap[*SI];
 479
 480   LLVM_DEBUG({
 481     dbgs() << "Dumping reg alias table:\n";
 482     for (MCPhysReg I = 0, E = RegInfo->getNumRegs(); I != E; ++I) {
 483       dbgs() << "Reg " << I << ": ";
 484       const BitVector &BV = AliasMap[I];
 485       int Idx = BV.find_first();
 486       while (Idx != -1) {
 487         dbgs() << Idx << " ";
 488         Idx = BV.find_next(Idx);
 489       }
 490       dbgs() << "\n";
 491     }
 492   });
 493 }
 494
 495 void MCPlusBuilder::initSizeMap() {
 496   SizeMap.resize(RegInfo->getNumRegs());
 497   // Build size map
 498   for (auto RC : RegInfo->regclasses())
 499     for (MCPhysReg Reg : RC)
 500       SizeMap[Reg] = RC.getSizeInBits() / 8;
 501 }
 502
 503 bool MCPlusBuilder::setOperandToSymbolRef(MCInst &Inst, int OpNum,
 504                                           const MCSymbol *Symbol,
 505                                           int64_t Addend, MCContext *Ctx,
 506                                           uint64_t RelType) const {
 507   MCOperand Operand;
 508   if (!Addend) {
 509     Operand = MCOperand::createExpr(getTargetExprFor(
 510         Inst, MCSymbolRefExpr::create(Symbol, *Ctx), *Ctx, RelType));
 511   } else {
 512     Operand = MCOperand::createExpr(getTargetExprFor(
 513         Inst,
 514         MCBinaryExpr::createAdd(MCSymbolRefExpr::create(Symbol, *Ctx),
 515                                 MCConstantExpr::create(Addend, *Ctx), *Ctx),
 516         *Ctx, RelType));
 517   }
 518   Inst.getOperand(OpNum) = Operand;
 519   return true;
 520 }