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