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 ? 5 : 1); 198 assert(StackAdjust.isImm() && "Expecting immediate value."); 199 200 // Adjust stack pointer. 201 int StackAdj = StackAdjust.getImm(); 202 int MaxTCDelta = X86FI->getTCReturnAddrDelta(); 203 int Offset = 0; 204 assert(MaxTCDelta <= 0 && "MaxTCDelta should never be positive"); 205 206 // Incoporate the retaddr area. 207 Offset = StackAdj - MaxTCDelta; 208 assert(Offset >= 0 && "Offset should never be negative"); 209 210 if (Opcode == X86::TCRETURNdicc || Opcode == X86::TCRETURNdi64cc) { 211 assert(Offset == 0 && "Conditional tail call cannot adjust the stack."); 212 } 213 214 if (Offset) { 215 // Check for possible merge with preceding ADD instruction. 216 Offset += X86FL->mergeSPUpdates(MBB, MBBI, true); 217 X86FL->emitSPUpdate(MBB, MBBI, DL, Offset, /*InEpilogue=*/true); 218 } 219 220 // Jump to label or value in register. 221 bool IsWin64 = STI->isTargetWin64(); 222 if (Opcode == X86::TCRETURNdi || Opcode == X86::TCRETURNdicc || 223 Opcode == X86::TCRETURNdi64 || Opcode == X86::TCRETURNdi64cc) { 224 unsigned Op; 225 switch (Opcode) { 226 case X86::TCRETURNdi: 227 Op = X86::TAILJMPd; 228 break; 229 case X86::TCRETURNdicc: 230 Op = X86::TAILJMPd_CC; 231 break; 232 case X86::TCRETURNdi64cc: 233 assert(!MBB.getParent()->hasWinCFI() && 234 "Conditional tail calls confuse " 235 "the Win64 unwinder."); 236 Op = X86::TAILJMPd64_CC; 237 break; 238 default: 239 // Note: Win64 uses REX prefixes indirect jumps out of functions, but 240 // not direct ones. 241 Op = X86::TAILJMPd64; 242 break; 243 } 244 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(Op)); 245 if (JumpTarget.isGlobal()) { 246 MIB.addGlobalAddress(JumpTarget.getGlobal(), JumpTarget.getOffset(), 247 JumpTarget.getTargetFlags()); 248 } else { 249 assert(JumpTarget.isSymbol()); 250 MIB.addExternalSymbol(JumpTarget.getSymbolName(), 251 JumpTarget.getTargetFlags()); 252 } 253 if (Op == X86::TAILJMPd_CC || Op == X86::TAILJMPd64_CC) { 254 MIB.addImm(MBBI->getOperand(2).getImm()); 255 } 256 257 } else if (Opcode == X86::TCRETURNmi || Opcode == X86::TCRETURNmi64) { 258 unsigned Op = (Opcode == X86::TCRETURNmi) 259 ? X86::TAILJMPm 260 : (IsWin64 ? X86::TAILJMPm64_REX : X86::TAILJMPm64); 261 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(Op)); 262 for (unsigned i = 0; i != 5; ++i) 263 MIB.add(MBBI->getOperand(i)); 264 } else if (Opcode == X86::TCRETURNri64) { 265 JumpTarget.setIsKill(); 266 BuildMI(MBB, MBBI, DL, 267 TII->get(IsWin64 ? X86::TAILJMPr64_REX : X86::TAILJMPr64)) 268 .add(JumpTarget); 269 } else { 270 JumpTarget.setIsKill(); 271 BuildMI(MBB, MBBI, DL, TII->get(X86::TAILJMPr)) 272 .add(JumpTarget); 273 } 274 275 MachineInstr &NewMI = *std::prev(MBBI); 276 NewMI.copyImplicitOps(*MBBI->getParent()->getParent(), *MBBI); 277 MBB.getParent()->updateCallSiteInfo(&*MBBI, &NewMI); 278 279 // Delete the pseudo instruction TCRETURN. 280 MBB.erase(MBBI); 281 282 return true; 283 } 284 case X86::EH_RETURN: 285 case X86::EH_RETURN64: { 286 MachineOperand &DestAddr = MBBI->getOperand(0); 287 assert(DestAddr.isReg() && "Offset should be in register!"); 288 const bool Uses64BitFramePtr = 289 STI->isTarget64BitLP64() || STI->isTargetNaCl64(); 290 unsigned StackPtr = TRI->getStackRegister(); 291 BuildMI(MBB, MBBI, DL, 292 TII->get(Uses64BitFramePtr ? X86::MOV64rr : X86::MOV32rr), StackPtr) 293 .addReg(DestAddr.getReg()); 294 // The EH_RETURN pseudo is really removed during the MC Lowering. 295 return true; 296 } 297 case X86::IRET: { 298 // Adjust stack to erase error code 299 int64_t StackAdj = MBBI->getOperand(0).getImm(); 300 X86FL->emitSPUpdate(MBB, MBBI, DL, StackAdj, true); 301 // Replace pseudo with machine iret 302 BuildMI(MBB, MBBI, DL, 303 TII->get(STI->is64Bit() ? X86::IRET64 : X86::IRET32)); 304 MBB.erase(MBBI); 305 return true; 306 } 307 case X86::RET: { 308 // Adjust stack to erase error code 309 int64_t StackAdj = MBBI->getOperand(0).getImm(); 310 MachineInstrBuilder MIB; 311 if (StackAdj == 0) { 312 MIB = BuildMI(MBB, MBBI, DL, 313 TII->get(STI->is64Bit() ? X86::RETQ : X86::RETL)); 314 } else if (isUInt<16>(StackAdj)) { 315 MIB = BuildMI(MBB, MBBI, DL, 316 TII->get(STI->is64Bit() ? X86::RETIQ : X86::RETIL)) 317 .addImm(StackAdj); 318 } else { 319 assert(!STI->is64Bit() && 320 "shouldn't need to do this for x86_64 targets!"); 321 // A ret can only handle immediates as big as 2**16-1. If we need to pop 322 // off bytes before the return address, we must do it manually. 323 BuildMI(MBB, MBBI, DL, TII->get(X86::POP32r)).addReg(X86::ECX, RegState::Define); 324 X86FL->emitSPUpdate(MBB, MBBI, DL, StackAdj, /*InEpilogue=*/true); 325 BuildMI(MBB, MBBI, DL, TII->get(X86::PUSH32r)).addReg(X86::ECX); 326 MIB = BuildMI(MBB, MBBI, DL, TII->get(X86::RETL)); 327 } 328 for (unsigned I = 1, E = MBBI->getNumOperands(); I != E; ++I) 329 MIB.add(MBBI->getOperand(I)); 330 MBB.erase(MBBI); 331 return true; 332 } 333 case X86::EH_RESTORE: { 334 // Restore ESP and EBP, and optionally ESI if required. 335 bool IsSEH = isAsynchronousEHPersonality(classifyEHPersonality( 336 MBB.getParent()->getFunction().getPersonalityFn())); 337 X86FL->restoreWin32EHStackPointers(MBB, MBBI, DL, /*RestoreSP=*/IsSEH); 338 MBBI->eraseFromParent(); 339 return true; 340 } 341 case X86::LCMPXCHG8B_SAVE_EBX: 342 case X86::LCMPXCHG16B_SAVE_RBX: { 343 // Perform the following transformation. 344 // SaveRbx = pseudocmpxchg Addr, <4 opds for the address>, InArg, SaveRbx 345 // => 346 // [E|R]BX = InArg 347 // actualcmpxchg Addr 348 // [E|R]BX = SaveRbx 349 const MachineOperand &InArg = MBBI->getOperand(6); 350 unsigned SaveRbx = MBBI->getOperand(7).getReg(); 351 352 unsigned ActualInArg = 353 Opcode == X86::LCMPXCHG8B_SAVE_EBX ? X86::EBX : X86::RBX; 354 // Copy the input argument of the pseudo into the argument of the 355 // actual instruction. 356 TII->copyPhysReg(MBB, MBBI, DL, ActualInArg, InArg.getReg(), 357 InArg.isKill()); 358 // Create the actual instruction. 359 unsigned ActualOpc = 360 Opcode == X86::LCMPXCHG8B_SAVE_EBX ? X86::LCMPXCHG8B : X86::LCMPXCHG16B; 361 MachineInstr *NewInstr = BuildMI(MBB, MBBI, DL, TII->get(ActualOpc)); 362 // Copy the operands related to the address. 363 for (unsigned Idx = 1; Idx < 6; ++Idx) 364 NewInstr->addOperand(MBBI->getOperand(Idx)); 365 // Finally, restore the value of RBX. 366 TII->copyPhysReg(MBB, MBBI, DL, ActualInArg, SaveRbx, 367 /*SrcIsKill*/ true); 368 369 // Delete the pseudo. 370 MBBI->eraseFromParent(); 371 return true; 372 } 373 case TargetOpcode::ICALL_BRANCH_FUNNEL: 374 ExpandICallBranchFunnel(&MBB, MBBI); 375 return true; 376 } 377 llvm_unreachable("Previous switch has a fallthrough?"); 378 } 379 380 /// Expand all pseudo instructions contained in \p MBB. 381 /// \returns true if any expansion occurred for \p MBB. 382 bool X86ExpandPseudo::ExpandMBB(MachineBasicBlock &MBB) { 383 bool Modified = false; 384 385 // MBBI may be invalidated by the expansion. 386 MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end(); 387 while (MBBI != E) { 388 MachineBasicBlock::iterator NMBBI = std::next(MBBI); 389 Modified |= ExpandMI(MBB, MBBI); 390 MBBI = NMBBI; 391 } 392 393 return Modified; 394 } 395 396 bool X86ExpandPseudo::runOnMachineFunction(MachineFunction &MF) { 397 STI = &static_cast<const X86Subtarget &>(MF.getSubtarget()); 398 TII = STI->getInstrInfo(); 399 TRI = STI->getRegisterInfo(); 400 X86FI = MF.getInfo<X86MachineFunctionInfo>(); 401 X86FL = STI->getFrameLowering(); 402 403 bool Modified = false; 404 for (MachineBasicBlock &MBB : MF) 405 Modified |= ExpandMBB(MBB); 406 return Modified; 407 } 408 409 /// Returns an instance of the pseudo instruction expansion pass. 410 FunctionPass *llvm::createX86ExpandPseudoPass() { 411 return new X86ExpandPseudo(); 412 } 413