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