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