lib/Target/X86/X86ExpandPseudo.cpp

   1 //===------- X86ExpandPseudo.cpp - Expand pseudo instructions -------------===//
   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 contains a pass that expands pseudo instructions into target
  10 // instructions to allow proper scheduling, if-conversion, other late
  11 // optimizations, or simply the encoding of the instructions.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "X86.h"
  16 #include "X86FrameLowering.h"
  17 #include "X86InstrBuilder.h"
  18 #include "X86InstrInfo.h"
  19 #include "X86MachineFunctionInfo.h"
  20 #include "X86Subtarget.h"
  21 #include "llvm/Analysis/EHPersonalities.h"
  22 #include "llvm/CodeGen/MachineFunctionPass.h"
  23 #include "llvm/CodeGen/MachineInstrBuilder.h"
  24 #include "llvm/CodeGen/Passes.h" // For IDs of passes that are preserved.
  25 #include "llvm/IR/GlobalValue.h"
  26 using namespace llvm;
  27
  28 #define DEBUG_TYPE "x86-pseudo"
  29
  30 namespace {
  31 class X86ExpandPseudo : public MachineFunctionPass {
  32 public:
  33   static char ID;
  34   X86ExpandPseudo() : MachineFunctionPass(ID) {}
  35
  36   void getAnalysisUsage(AnalysisUsage &AU) const override {
  37     AU.setPreservesCFG();
  38     AU.addPreservedID(MachineLoopInfoID);
  39     AU.addPreservedID(MachineDominatorsID);
  40     MachineFunctionPass::getAnalysisUsage(AU);
  41   }
  42
  43   const X86Subtarget *STI;
  44   const X86InstrInfo *TII;
  45   const X86RegisterInfo *TRI;
  46   const X86MachineFunctionInfo *X86FI;
  47   const X86FrameLowering *X86FL;
  48
  49   bool runOnMachineFunction(MachineFunction &Fn) override;
  50
  51   MachineFunctionProperties getRequiredProperties() const override {
  52     return MachineFunctionProperties().set(
  53         MachineFunctionProperties::Property::NoVRegs);
  54   }
  55
  56   StringRef getPassName() const override {
  57     return "X86 pseudo instruction expansion pass";
  58   }
  59
  60 private:
  61   void ExpandICallBranchFunnel(MachineBasicBlock *MBB,
  62                                MachineBasicBlock::iterator MBBI);
  63
  64   bool ExpandMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI);
  65   bool ExpandMBB(MachineBasicBlock &MBB);
  66 };
  67 char X86ExpandPseudo::ID = 0;
  68 } // End anonymous namespace.
  69
  70 void X86ExpandPseudo::ExpandICallBranchFunnel(
  71     MachineBasicBlock *MBB, MachineBasicBlock::iterator MBBI) {
  72   MachineBasicBlock *JTMBB = MBB;
  73   MachineInstr *JTInst = &*MBBI;
  74   MachineFunction *MF = MBB->getParent();
  75   const BasicBlock *BB = MBB->getBasicBlock();
  76   auto InsPt = MachineFunction::iterator(MBB);
  77   ++InsPt;
  78
  79   std::vector<std::pair<MachineBasicBlock *, unsigned>> TargetMBBs;
  80   DebugLoc DL = JTInst->getDebugLoc();
  81   MachineOperand Selector = JTInst->getOperand(0);
  82   const GlobalValue *CombinedGlobal = JTInst->getOperand(1).getGlobal();
  83
  84   auto CmpTarget = [&](unsigned Target) {
  85     BuildMI(*MBB, MBBI, DL, TII->get(X86::LEA64r), X86::R11)
  86         .addReg(X86::RIP)
  87         .addImm(1)
  88         .addReg(0)
  89         .addGlobalAddress(CombinedGlobal,
  90                           JTInst->getOperand(2 + 2 * Target).getImm())
  91         .addReg(0);
  92     BuildMI(*MBB, MBBI, DL, TII->get(X86::CMP64rr))
  93         .add(Selector)
  94         .addReg(X86::R11);
  95   };
  96
  97   auto CreateMBB = [&]() {
  98     auto *NewMBB = MF->CreateMachineBasicBlock(BB);
  99     MBB->addSuccessor(NewMBB);
 100     return NewMBB;
 101   };
 102
 103   auto EmitCondJump = [&](unsigned Opcode, MachineBasicBlock *ThenMBB) {
 104     BuildMI(*MBB, MBBI, DL, TII->get(Opcode)).addMBB(ThenMBB);
 105
 106     auto *ElseMBB = CreateMBB();
 107     MF->insert(InsPt, ElseMBB);
 108     MBB = ElseMBB;
 109     MBBI = MBB->end();
 110   };
 111
 112   auto EmitCondJumpTarget = [&](unsigned Opcode, unsigned Target) {
 113     auto *ThenMBB = CreateMBB();
 114     TargetMBBs.push_back({ThenMBB, Target});
 115     EmitCondJump(Opcode, ThenMBB);
 116   };
 117
 118   auto EmitTailCall = [&](unsigned Target) {
 119     BuildMI(*MBB, MBBI, DL, TII->get(X86::TAILJMPd64))
 120         .add(JTInst->getOperand(3 + 2 * Target));
 121   };
 122
 123   std::function<void(unsigned, unsigned)> EmitBranchFunnel =
 124       [&](unsigned FirstTarget, unsigned NumTargets) {
 125     if (NumTargets == 1) {
 126       EmitTailCall(FirstTarget);
 127       return;
 128     }
 129
 130     if (NumTargets == 2) {
 131       CmpTarget(FirstTarget + 1);
 132       EmitCondJumpTarget(X86::JB_1, FirstTarget);
 133       EmitTailCall(FirstTarget + 1);
 134       return;
 135     }
 136
 137     if (NumTargets < 6) {
 138       CmpTarget(FirstTarget + 1);
 139       EmitCondJumpTarget(X86::JB_1, FirstTarget);
 140       EmitCondJumpTarget(X86::JE_1, FirstTarget + 1);
 141       EmitBranchFunnel(FirstTarget + 2, NumTargets - 2);
 142       return;
 143     }
 144
 145     auto *ThenMBB = CreateMBB();
 146     CmpTarget(FirstTarget + (NumTargets / 2));
 147     EmitCondJump(X86::JB_1, ThenMBB);
 148     EmitCondJumpTarget(X86::JE_1, FirstTarget + (NumTargets / 2));
 149     EmitBranchFunnel(FirstTarget + (NumTargets / 2) + 1,
 150                   NumTargets - (NumTargets / 2) - 1);
 151
 152     MF->insert(InsPt, ThenMBB);
 153     MBB = ThenMBB;
 154     MBBI = MBB->end();
 155     EmitBranchFunnel(FirstTarget, NumTargets / 2);
 156   };
 157
 158   EmitBranchFunnel(0, (JTInst->getNumOperands() - 2) / 2);
 159   for (auto P : TargetMBBs) {
 160     MF->insert(InsPt, P.first);
 161     BuildMI(P.first, DL, TII->get(X86::TAILJMPd64))
 162         .add(JTInst->getOperand(3 + 2 * P.second));
 163   }
 164   JTMBB->erase(JTInst);
 165 }
 166
 167 /// If \p MBBI is a pseudo instruction, this method expands
 168 /// it to the corresponding (sequence of) actual instruction(s).
 169 /// \returns true if \p MBBI has been expanded.
 170 bool X86ExpandPseudo::ExpandMI(MachineBasicBlock &MBB,
 171                                MachineBasicBlock::iterator MBBI) {
 172   MachineInstr &MI = *MBBI;
 173   unsigned Opcode = MI.getOpcode();
 174   DebugLoc DL = MBBI->getDebugLoc();
 175   switch (Opcode) {
 176   default:
 177     return false;
 178   case X86::TCRETURNdi:
 179   case X86::TCRETURNdicc:
 180   case X86::TCRETURNri:
 181   case X86::TCRETURNmi:
 182   case X86::TCRETURNdi64:
 183   case X86::TCRETURNdi64cc:
 184   case X86::TCRETURNri64:
 185   case X86::TCRETURNmi64: {
 186     bool isMem = Opcode == X86::TCRETURNmi || Opcode == X86::TCRETURNmi64;
 187     MachineOperand &JumpTarget = MBBI->getOperand(0);
 188     MachineOperand &StackAdjust = MBBI->getOperand(isMem ? 5 : 1);
 189     assert(StackAdjust.isImm() && "Expecting immediate value.");
 190
 191     // Adjust stack pointer.
 192     int StackAdj = StackAdjust.getImm();
 193     int MaxTCDelta = X86FI->getTCReturnAddrDelta();
 194     int Offset = 0;
 195     assert(MaxTCDelta <= 0 && "MaxTCDelta should never be positive");
 196
 197     // Incoporate the retaddr area.
 198     Offset = StackAdj - MaxTCDelta;
 199     assert(Offset >= 0 && "Offset should never be negative");
 200
 201     if (Opcode == X86::TCRETURNdicc || Opcode == X86::TCRETURNdi64cc) {
 202       assert(Offset == 0 && "Conditional tail call cannot adjust the stack.");
 203     }
 204
 205     if (Offset) {
 206       // Check for possible merge with preceding ADD instruction.
 207       Offset += X86FL->mergeSPUpdates(MBB, MBBI, true);
 208       X86FL->emitSPUpdate(MBB, MBBI, DL, Offset, /*InEpilogue=*/true);
 209     }
 210
 211     // Jump to label or value in register.
 212     bool IsWin64 = STI->isTargetWin64();
 213     if (Opcode == X86::TCRETURNdi || Opcode == X86::TCRETURNdicc ||
 214         Opcode == X86::TCRETURNdi64 || Opcode == X86::TCRETURNdi64cc) {
 215       unsigned Op;
 216       switch (Opcode) {
 217       case X86::TCRETURNdi:
 218         Op = X86::TAILJMPd;
 219         break;
 220       case X86::TCRETURNdicc:
 221         Op = X86::TAILJMPd_CC;
 222         break;
 223       case X86::TCRETURNdi64cc:
 224         assert(!MBB.getParent()->hasWinCFI() &&
 225                "Conditional tail calls confuse "
 226                "the Win64 unwinder.");
 227         Op = X86::TAILJMPd64_CC;
 228         break;
 229       default:
 230         // Note: Win64 uses REX prefixes indirect jumps out of functions, but
 231         // not direct ones.
 232         Op = X86::TAILJMPd64;
 233         break;
 234       }
 235       MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(Op));
 236       if (JumpTarget.isGlobal()) {
 237         MIB.addGlobalAddress(JumpTarget.getGlobal(), JumpTarget.getOffset(),
 238                              JumpTarget.getTargetFlags());
 239       } else {
 240         assert(JumpTarget.isSymbol());
 241         MIB.addExternalSymbol(JumpTarget.getSymbolName(),
 242                               JumpTarget.getTargetFlags());
 243       }
 244       if (Op == X86::TAILJMPd_CC || Op == X86::TAILJMPd64_CC) {
 245         MIB.addImm(MBBI->getOperand(2).getImm());
 246       }
 247
 248     } else if (Opcode == X86::TCRETURNmi || Opcode == X86::TCRETURNmi64) {
 249       unsigned Op = (Opcode == X86::TCRETURNmi)
 250                         ? X86::TAILJMPm
 251                         : (IsWin64 ? X86::TAILJMPm64_REX : X86::TAILJMPm64);
 252       MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(Op));
 253       for (unsigned i = 0; i != 5; ++i)
 254         MIB.add(MBBI->getOperand(i));
 255     } else if (Opcode == X86::TCRETURNri64) {
 256       BuildMI(MBB, MBBI, DL,
 257               TII->get(IsWin64 ? X86::TAILJMPr64_REX : X86::TAILJMPr64))
 258           .addReg(JumpTarget.getReg(), RegState::Kill);
 259     } else {
 260       BuildMI(MBB, MBBI, DL, TII->get(X86::TAILJMPr))
 261           .addReg(JumpTarget.getReg(), RegState::Kill);
 262     }
 263
 264     MachineInstr &NewMI = *std::prev(MBBI);
 265     NewMI.copyImplicitOps(*MBBI->getParent()->getParent(), *MBBI);
 266
 267     // Delete the pseudo instruction TCRETURN.
 268     MBB.erase(MBBI);
 269
 270     return true;
 271   }
 272   case X86::EH_RETURN:
 273   case X86::EH_RETURN64: {
 274     MachineOperand &DestAddr = MBBI->getOperand(0);
 275     assert(DestAddr.isReg() && "Offset should be in register!");
 276     const bool Uses64BitFramePtr =
 277         STI->isTarget64BitLP64() || STI->isTargetNaCl64();
 278     unsigned StackPtr = TRI->getStackRegister();
 279     BuildMI(MBB, MBBI, DL,
 280             TII->get(Uses64BitFramePtr ? X86::MOV64rr : X86::MOV32rr), StackPtr)
 281         .addReg(DestAddr.getReg());
 282     // The EH_RETURN pseudo is really removed during the MC Lowering.
 283     return true;
 284   }
 285   case X86::IRET: {
 286     // Adjust stack to erase error code
 287     int64_t StackAdj = MBBI->getOperand(0).getImm();
 288     X86FL->emitSPUpdate(MBB, MBBI, DL, StackAdj, true);
 289     // Replace pseudo with machine iret
 290     BuildMI(MBB, MBBI, DL,
 291             TII->get(STI->is64Bit() ? X86::IRET64 : X86::IRET32));
 292     MBB.erase(MBBI);
 293     return true;
 294   }
 295   case X86::RET: {
 296     // Adjust stack to erase error code
 297     int64_t StackAdj = MBBI->getOperand(0).getImm();
 298     MachineInstrBuilder MIB;
 299     if (StackAdj == 0) {
 300       MIB = BuildMI(MBB, MBBI, DL,
 301                     TII->get(STI->is64Bit() ? X86::RETQ : X86::RETL));
 302     } else if (isUInt<16>(StackAdj)) {
 303       MIB = BuildMI(MBB, MBBI, DL,
 304                     TII->get(STI->is64Bit() ? X86::RETIQ : X86::RETIL))
 305                 .addImm(StackAdj);
 306     } else {
 307       assert(!STI->is64Bit() &&
 308              "shouldn't need to do this for x86_64 targets!");
 309       // A ret can only handle immediates as big as 2**16-1.  If we need to pop
 310       // off bytes before the return address, we must do it manually.
 311       BuildMI(MBB, MBBI, DL, TII->get(X86::POP32r)).addReg(X86::ECX, RegState::Define);
 312       X86FL->emitSPUpdate(MBB, MBBI, DL, StackAdj, /*InEpilogue=*/true);
 313       BuildMI(MBB, MBBI, DL, TII->get(X86::PUSH32r)).addReg(X86::ECX);
 314       MIB = BuildMI(MBB, MBBI, DL, TII->get(X86::RETL));
 315     }
 316     for (unsigned I = 1, E = MBBI->getNumOperands(); I != E; ++I)
 317       MIB.add(MBBI->getOperand(I));
 318     MBB.erase(MBBI);
 319     return true;
 320   }
 321   case X86::EH_RESTORE: {
 322     // Restore ESP and EBP, and optionally ESI if required.
 323     bool IsSEH = isAsynchronousEHPersonality(classifyEHPersonality(
 324         MBB.getParent()->getFunction().getPersonalityFn()));
 325     X86FL->restoreWin32EHStackPointers(MBB, MBBI, DL, /*RestoreSP=*/IsSEH);
 326     MBBI->eraseFromParent();
 327     return true;
 328   }
 329   case X86::LCMPXCHG8B_SAVE_EBX:
 330   case X86::LCMPXCHG16B_SAVE_RBX: {
 331     // Perform the following transformation.
 332     // SaveRbx = pseudocmpxchg Addr, <4 opds for the address>, InArg, SaveRbx
 333     // =>
 334     // [E|R]BX = InArg
 335     // actualcmpxchg Addr
 336     // [E|R]BX = SaveRbx
 337     const MachineOperand &InArg = MBBI->getOperand(6);
 338     unsigned SaveRbx = MBBI->getOperand(7).getReg();
 339
 340     unsigned ActualInArg =
 341         Opcode == X86::LCMPXCHG8B_SAVE_EBX ? X86::EBX : X86::RBX;
 342     // Copy the input argument of the pseudo into the argument of the
 343     // actual instruction.
 344     TII->copyPhysReg(MBB, MBBI, DL, ActualInArg, InArg.getReg(),
 345                      InArg.isKill());
 346     // Create the actual instruction.
 347     unsigned ActualOpc =
 348         Opcode == X86::LCMPXCHG8B_SAVE_EBX ? X86::LCMPXCHG8B : X86::LCMPXCHG16B;
 349     MachineInstr *NewInstr = BuildMI(MBB, MBBI, DL, TII->get(ActualOpc));
 350     // Copy the operands related to the address.
 351     for (unsigned Idx = 1; Idx < 6; ++Idx)
 352       NewInstr->addOperand(MBBI->getOperand(Idx));
 353     // Finally, restore the value of RBX.
 354     TII->copyPhysReg(MBB, MBBI, DL, ActualInArg, SaveRbx,
 355                      /*SrcIsKill*/ true);
 356
 357     // Delete the pseudo.
 358     MBBI->eraseFromParent();
 359     return true;
 360   }
 361   case TargetOpcode::ICALL_BRANCH_FUNNEL:
 362     ExpandICallBranchFunnel(&MBB, MBBI);
 363     return true;
 364   }
 365   llvm_unreachable("Previous switch has a fallthrough?");
 366 }
 367
 368 /// Expand all pseudo instructions contained in \p MBB.
 369 /// \returns true if any expansion occurred for \p MBB.
 370 bool X86ExpandPseudo::ExpandMBB(MachineBasicBlock &MBB) {
 371   bool Modified = false;
 372
 373   // MBBI may be invalidated by the expansion.
 374   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
 375   while (MBBI != E) {
 376     MachineBasicBlock::iterator NMBBI = std::next(MBBI);
 377     Modified |= ExpandMI(MBB, MBBI);
 378     MBBI = NMBBI;
 379   }
 380
 381   return Modified;
 382 }
 383
 384 bool X86ExpandPseudo::runOnMachineFunction(MachineFunction &MF) {
 385   STI = &static_cast<const X86Subtarget &>(MF.getSubtarget());
 386   TII = STI->getInstrInfo();
 387   TRI = STI->getRegisterInfo();
 388   X86FI = MF.getInfo<X86MachineFunctionInfo>();
 389   X86FL = STI->getFrameLowering();
 390
 391   bool Modified = false;
 392   for (MachineBasicBlock &MBB : MF)
 393     Modified |= ExpandMBB(MBB);
 394   return Modified;
 395 }
 396
 397 /// Returns an instance of the pseudo instruction expansion pass.
 398 FunctionPass *llvm::createX86ExpandPseudoPass() {
 399   return new X86ExpandPseudo();
 400 }