1 //===-- X86FixupBWInsts.cpp - Fixup Byte or Word 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 /// \file 9 /// This file defines the pass that looks through the machine instructions 10 /// late in the compilation, and finds byte or word instructions that 11 /// can be profitably replaced with 32 bit instructions that give equivalent 12 /// results for the bits of the results that are used. There are two possible 13 /// reasons to do this. 14 /// 15 /// One reason is to avoid false-dependences on the upper portions 16 /// of the registers. Only instructions that have a destination register 17 /// which is not in any of the source registers can be affected by this. 18 /// Any instruction where one of the source registers is also the destination 19 /// register is unaffected, because it has a true dependence on the source 20 /// register already. So, this consideration primarily affects load 21 /// instructions and register-to-register moves. It would 22 /// seem like cmov(s) would also be affected, but because of the way cmov is 23 /// really implemented by most machines as reading both the destination and 24 /// and source registers, and then "merging" the two based on a condition, 25 /// it really already should be considered as having a true dependence on the 26 /// destination register as well. 27 /// 28 /// The other reason to do this is for potential code size savings. Word 29 /// operations need an extra override byte compared to their 32 bit 30 /// versions. So this can convert many word operations to their larger 31 /// size, saving a byte in encoding. This could introduce partial register 32 /// dependences where none existed however. As an example take: 33 /// orw ax, $0x1000 34 /// addw ax, $3 35 /// now if this were to get transformed into 36 /// orw ax, $1000 37 /// addl eax, $3 38 /// because the addl encodes shorter than the addw, this would introduce 39 /// a use of a register that was only partially written earlier. On older 40 /// Intel processors this can be quite a performance penalty, so this should 41 /// probably only be done when it can be proven that a new partial dependence 42 /// wouldn't be created, or when your know a newer processor is being 43 /// targeted, or when optimizing for minimum code size. 44 /// 45 //===----------------------------------------------------------------------===// 46 47 #include "X86.h" 48 #include "X86InstrInfo.h" 49 #include "X86Subtarget.h" 50 #include "llvm/ADT/Statistic.h" 51 #include "llvm/Analysis/ProfileSummaryInfo.h" 52 #include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h" 53 #include "llvm/CodeGen/LivePhysRegs.h" 54 #include "llvm/CodeGen/MachineFunctionPass.h" 55 #include "llvm/CodeGen/MachineInstrBuilder.h" 56 #include "llvm/CodeGen/MachineLoopInfo.h" 57 #include "llvm/CodeGen/MachineRegisterInfo.h" 58 #include "llvm/CodeGen/MachineSizeOpts.h" 59 #include "llvm/CodeGen/Passes.h" 60 #include "llvm/CodeGen/TargetInstrInfo.h" 61 #include "llvm/Support/Debug.h" 62 #include "llvm/Support/raw_ostream.h" 63 using namespace llvm; 64 65 #define FIXUPBW_DESC "X86 Byte/Word Instruction Fixup" 66 #define FIXUPBW_NAME "x86-fixup-bw-insts" 67 68 #define DEBUG_TYPE FIXUPBW_NAME 69 70 // Option to allow this optimization pass to have fine-grained control. 71 static cl::opt<bool> 72 FixupBWInsts("fixup-byte-word-insts", 73 cl::desc("Change byte and word instructions to larger sizes"), 74 cl::init(true), cl::Hidden); 75 76 namespace { 77 class FixupBWInstPass : public MachineFunctionPass { 78 /// Loop over all of the instructions in the basic block replacing applicable 79 /// byte or word instructions with better alternatives. 80 void processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB); 81 82 /// This sets the \p SuperDestReg to the 32 bit super reg of the original 83 /// destination register of the MachineInstr passed in. It returns true if 84 /// that super register is dead just prior to \p OrigMI, and false if not. 85 bool getSuperRegDestIfDead(MachineInstr *OrigMI, 86 Register &SuperDestReg) const; 87 88 /// Change the MachineInstr \p MI into the equivalent extending load to 32 bit 89 /// register if it is safe to do so. Return the replacement instruction if 90 /// OK, otherwise return nullptr. 91 MachineInstr *tryReplaceLoad(unsigned New32BitOpcode, MachineInstr *MI) const; 92 93 /// Change the MachineInstr \p MI into the equivalent 32-bit copy if it is 94 /// safe to do so. Return the replacement instruction if OK, otherwise return 95 /// nullptr. 96 MachineInstr *tryReplaceCopy(MachineInstr *MI) const; 97 98 /// Change the MachineInstr \p MI into the equivalent extend to 32 bit 99 /// register if it is safe to do so. Return the replacement instruction if 100 /// OK, otherwise return nullptr. 101 MachineInstr *tryReplaceExtend(unsigned New32BitOpcode, 102 MachineInstr *MI) const; 103 104 // Change the MachineInstr \p MI into an eqivalent 32 bit instruction if 105 // possible. Return the replacement instruction if OK, return nullptr 106 // otherwise. 107 MachineInstr *tryReplaceInstr(MachineInstr *MI, MachineBasicBlock &MBB) const; 108 109 public: 110 static char ID; 111 112 StringRef getPassName() const override { return FIXUPBW_DESC; } 113 114 FixupBWInstPass() : MachineFunctionPass(ID) { } 115 116 void getAnalysisUsage(AnalysisUsage &AU) const override { 117 AU.addRequired<MachineLoopInfo>(); // Machine loop info is used to 118 // guide some heuristics. 119 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 120 AU.addRequired<LazyMachineBlockFrequencyInfoPass>(); 121 MachineFunctionPass::getAnalysisUsage(AU); 122 } 123 124 /// Loop over all of the basic blocks, replacing byte and word instructions by 125 /// equivalent 32 bit instructions where performance or code size can be 126 /// improved. 127 bool runOnMachineFunction(MachineFunction &MF) override; 128 129 MachineFunctionProperties getRequiredProperties() const override { 130 return MachineFunctionProperties().set( 131 MachineFunctionProperties::Property::NoVRegs); 132 } 133 134 private: 135 MachineFunction *MF = nullptr; 136 137 /// Machine instruction info used throughout the class. 138 const X86InstrInfo *TII = nullptr; 139 140 /// Local member for function's OptForSize attribute. 141 bool OptForSize = false; 142 143 /// Machine loop info used for guiding some heruistics. 144 MachineLoopInfo *MLI = nullptr; 145 146 /// Register Liveness information after the current instruction. 147 LivePhysRegs LiveRegs; 148 149 ProfileSummaryInfo *PSI; 150 MachineBlockFrequencyInfo *MBFI; 151 }; 152 char FixupBWInstPass::ID = 0; 153 } 154 155 INITIALIZE_PASS(FixupBWInstPass, FIXUPBW_NAME, FIXUPBW_DESC, false, false) 156 157 FunctionPass *llvm::createX86FixupBWInsts() { return new FixupBWInstPass(); } 158 159 bool FixupBWInstPass::runOnMachineFunction(MachineFunction &MF) { 160 if (!FixupBWInsts || skipFunction(MF.getFunction())) 161 return false; 162 163 this->MF = &MF; 164 TII = MF.getSubtarget<X86Subtarget>().getInstrInfo(); 165 MLI = &getAnalysis<MachineLoopInfo>(); 166 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 167 MBFI = (PSI && PSI->hasProfileSummary()) ? 168 &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI() : 169 nullptr; 170 LiveRegs.init(TII->getRegisterInfo()); 171 172 LLVM_DEBUG(dbgs() << "Start X86FixupBWInsts\n";); 173 174 // Process all basic blocks. 175 for (auto &MBB : MF) 176 processBasicBlock(MF, MBB); 177 178 LLVM_DEBUG(dbgs() << "End X86FixupBWInsts\n";); 179 180 return true; 181 } 182 183 /// Check if after \p OrigMI the only portion of super register 184 /// of the destination register of \p OrigMI that is alive is that 185 /// destination register. 186 /// 187 /// If so, return that super register in \p SuperDestReg. 188 bool FixupBWInstPass::getSuperRegDestIfDead(MachineInstr *OrigMI, 189 Register &SuperDestReg) const { 190 const X86RegisterInfo *TRI = &TII->getRegisterInfo(); 191 Register OrigDestReg = OrigMI->getOperand(0).getReg(); 192 SuperDestReg = getX86SubSuperRegister(OrigDestReg, 32); 193 194 const auto SubRegIdx = TRI->getSubRegIndex(SuperDestReg, OrigDestReg); 195 196 // Make sure that the sub-register that this instruction has as its 197 // destination is the lowest order sub-register of the super-register. 198 // If it isn't, then the register isn't really dead even if the 199 // super-register is considered dead. 200 if (SubRegIdx == X86::sub_8bit_hi) 201 return false; 202 203 // If neither the destination-super register nor any applicable subregisters 204 // are live after this instruction, then the super register is safe to use. 205 if (!LiveRegs.contains(SuperDestReg)) { 206 // If the original destination register was not the low 8-bit subregister 207 // then the super register check is sufficient. 208 if (SubRegIdx != X86::sub_8bit) 209 return true; 210 // If the original destination register was the low 8-bit subregister and 211 // we also need to check the 16-bit subregister and the high 8-bit 212 // subregister. 213 if (!LiveRegs.contains(getX86SubSuperRegister(OrigDestReg, 16)) && 214 !LiveRegs.contains(getX86SubSuperRegister(SuperDestReg, 8, 215 /*High=*/true))) 216 return true; 217 // Otherwise, we have a little more checking to do. 218 } 219 220 // If we get here, the super-register destination (or some part of it) is 221 // marked as live after the original instruction. 222 // 223 // The X86 backend does not have subregister liveness tracking enabled, 224 // so liveness information might be overly conservative. Specifically, the 225 // super register might be marked as live because it is implicitly defined 226 // by the instruction we are examining. 227 // 228 // However, for some specific instructions (this pass only cares about MOVs) 229 // we can produce more precise results by analysing that MOV's operands. 230 // 231 // Indeed, if super-register is not live before the mov it means that it 232 // was originally <read-undef> and so we are free to modify these 233 // undef upper bits. That may happen in case where the use is in another MBB 234 // and the vreg/physreg corresponding to the move has higher width than 235 // necessary (e.g. due to register coalescing with a "truncate" copy). 236 // So, we would like to handle patterns like this: 237 // 238 // %bb.2: derived from LLVM BB %if.then 239 // Live Ins: %rdi 240 // Predecessors according to CFG: %bb.0 241 // %ax<def> = MOV16rm killed %rdi, 1, %noreg, 0, %noreg, implicit-def %eax 242 // ; No implicit %eax 243 // Successors according to CFG: %bb.3(?%) 244 // 245 // %bb.3: derived from LLVM BB %if.end 246 // Live Ins: %eax Only %ax is actually live 247 // Predecessors according to CFG: %bb.2 %bb.1 248 // %ax = KILL %ax, implicit killed %eax 249 // RET 0, %ax 250 unsigned Opc = OrigMI->getOpcode(); (void)Opc; 251 // These are the opcodes currently known to work with the code below, if 252 // something // else will be added we need to ensure that new opcode has the 253 // same properties. 254 if (Opc != X86::MOV8rm && Opc != X86::MOV16rm && Opc != X86::MOV8rr && 255 Opc != X86::MOV16rr) 256 return false; 257 258 bool IsDefined = false; 259 for (auto &MO: OrigMI->implicit_operands()) { 260 if (!MO.isReg()) 261 continue; 262 263 assert((MO.isDef() || MO.isUse()) && "Expected Def or Use only!"); 264 265 if (MO.isDef() && TRI->isSuperRegisterEq(OrigDestReg, MO.getReg())) 266 IsDefined = true; 267 268 // If MO is a use of any part of the destination register but is not equal 269 // to OrigDestReg or one of its subregisters, we cannot use SuperDestReg. 270 // For example, if OrigDestReg is %al then an implicit use of %ah, %ax, 271 // %eax, or %rax will prevent us from using the %eax register. 272 if (MO.isUse() && !TRI->isSubRegisterEq(OrigDestReg, MO.getReg()) && 273 TRI->regsOverlap(SuperDestReg, MO.getReg())) 274 return false; 275 } 276 // Reg is not Imp-def'ed -> it's live both before/after the instruction. 277 if (!IsDefined) 278 return false; 279 280 // Otherwise, the Reg is not live before the MI and the MOV can't 281 // make it really live, so it's in fact dead even after the MI. 282 return true; 283 } 284 285 MachineInstr *FixupBWInstPass::tryReplaceLoad(unsigned New32BitOpcode, 286 MachineInstr *MI) const { 287 Register NewDestReg; 288 289 // We are going to try to rewrite this load to a larger zero-extending 290 // load. This is safe if all portions of the 32 bit super-register 291 // of the original destination register, except for the original destination 292 // register are dead. getSuperRegDestIfDead checks that. 293 if (!getSuperRegDestIfDead(MI, NewDestReg)) 294 return nullptr; 295 296 // Safe to change the instruction. 297 MachineInstrBuilder MIB = 298 BuildMI(*MF, MI->getDebugLoc(), TII->get(New32BitOpcode), NewDestReg); 299 300 unsigned NumArgs = MI->getNumOperands(); 301 for (unsigned i = 1; i < NumArgs; ++i) 302 MIB.add(MI->getOperand(i)); 303 304 MIB.setMemRefs(MI->memoperands()); 305 306 return MIB; 307 } 308 309 MachineInstr *FixupBWInstPass::tryReplaceCopy(MachineInstr *MI) const { 310 assert(MI->getNumExplicitOperands() == 2); 311 auto &OldDest = MI->getOperand(0); 312 auto &OldSrc = MI->getOperand(1); 313 314 Register NewDestReg; 315 if (!getSuperRegDestIfDead(MI, NewDestReg)) 316 return nullptr; 317 318 Register NewSrcReg = getX86SubSuperRegister(OldSrc.getReg(), 32); 319 320 // This is only correct if we access the same subregister index: otherwise, 321 // we could try to replace "movb %ah, %al" with "movl %eax, %eax". 322 const X86RegisterInfo *TRI = &TII->getRegisterInfo(); 323 if (TRI->getSubRegIndex(NewSrcReg, OldSrc.getReg()) != 324 TRI->getSubRegIndex(NewDestReg, OldDest.getReg())) 325 return nullptr; 326 327 // Safe to change the instruction. 328 // Don't set src flags, as we don't know if we're also killing the superreg. 329 // However, the superregister might not be defined; make it explicit that 330 // we don't care about the higher bits by reading it as Undef, and adding 331 // an imp-use on the original subregister. 332 MachineInstrBuilder MIB = 333 BuildMI(*MF, MI->getDebugLoc(), TII->get(X86::MOV32rr), NewDestReg) 334 .addReg(NewSrcReg, RegState::Undef) 335 .addReg(OldSrc.getReg(), RegState::Implicit); 336 337 // Drop imp-defs/uses that would be redundant with the new def/use. 338 for (auto &Op : MI->implicit_operands()) 339 if (Op.getReg() != (Op.isDef() ? NewDestReg : NewSrcReg)) 340 MIB.add(Op); 341 342 return MIB; 343 } 344 345 MachineInstr *FixupBWInstPass::tryReplaceExtend(unsigned New32BitOpcode, 346 MachineInstr *MI) const { 347 Register NewDestReg; 348 if (!getSuperRegDestIfDead(MI, NewDestReg)) 349 return nullptr; 350 351 // Don't interfere with formation of CBW instructions which should be a 352 // shorter encoding than even the MOVSX32rr8. It's also immune to partial 353 // merge issues on Intel CPUs. 354 if (MI->getOpcode() == X86::MOVSX16rr8 && 355 MI->getOperand(0).getReg() == X86::AX && 356 MI->getOperand(1).getReg() == X86::AL) 357 return nullptr; 358 359 // Safe to change the instruction. 360 MachineInstrBuilder MIB = 361 BuildMI(*MF, MI->getDebugLoc(), TII->get(New32BitOpcode), NewDestReg); 362 363 unsigned NumArgs = MI->getNumOperands(); 364 for (unsigned i = 1; i < NumArgs; ++i) 365 MIB.add(MI->getOperand(i)); 366 367 MIB.setMemRefs(MI->memoperands()); 368 369 return MIB; 370 } 371 372 MachineInstr *FixupBWInstPass::tryReplaceInstr(MachineInstr *MI, 373 MachineBasicBlock &MBB) const { 374 // See if this is an instruction of the type we are currently looking for. 375 switch (MI->getOpcode()) { 376 377 case X86::MOV8rm: 378 // Only replace 8 bit loads with the zero extending versions if 379 // in an inner most loop and not optimizing for size. This takes 380 // an extra byte to encode, and provides limited performance upside. 381 if (MachineLoop *ML = MLI->getLoopFor(&MBB)) 382 if (ML->begin() == ML->end() && !OptForSize) 383 return tryReplaceLoad(X86::MOVZX32rm8, MI); 384 break; 385 386 case X86::MOV16rm: 387 // Always try to replace 16 bit load with 32 bit zero extending. 388 // Code size is the same, and there is sometimes a perf advantage 389 // from eliminating a false dependence on the upper portion of 390 // the register. 391 return tryReplaceLoad(X86::MOVZX32rm16, MI); 392 393 case X86::MOV8rr: 394 case X86::MOV16rr: 395 // Always try to replace 8/16 bit copies with a 32 bit copy. 396 // Code size is either less (16) or equal (8), and there is sometimes a 397 // perf advantage from eliminating a false dependence on the upper portion 398 // of the register. 399 return tryReplaceCopy(MI); 400 401 case X86::MOVSX16rr8: 402 return tryReplaceExtend(X86::MOVSX32rr8, MI); 403 case X86::MOVSX16rm8: 404 return tryReplaceExtend(X86::MOVSX32rm8, MI); 405 case X86::MOVZX16rr8: 406 return tryReplaceExtend(X86::MOVZX32rr8, MI); 407 case X86::MOVZX16rm8: 408 return tryReplaceExtend(X86::MOVZX32rm8, MI); 409 410 default: 411 // nothing to do here. 412 break; 413 } 414 415 return nullptr; 416 } 417 418 void FixupBWInstPass::processBasicBlock(MachineFunction &MF, 419 MachineBasicBlock &MBB) { 420 421 // This algorithm doesn't delete the instructions it is replacing 422 // right away. By leaving the existing instructions in place, the 423 // register liveness information doesn't change, and this makes the 424 // analysis that goes on be better than if the replaced instructions 425 // were immediately removed. 426 // 427 // This algorithm always creates a replacement instruction 428 // and notes that and the original in a data structure, until the 429 // whole BB has been analyzed. This keeps the replacement instructions 430 // from making it seem as if the larger register might be live. 431 SmallVector<std::pair<MachineInstr *, MachineInstr *>, 8> MIReplacements; 432 433 // Start computing liveness for this block. We iterate from the end to be able 434 // to update this for each instruction. 435 LiveRegs.clear(); 436 // We run after PEI, so we need to AddPristinesAndCSRs. 437 LiveRegs.addLiveOuts(MBB); 438 439 OptForSize = MF.getFunction().hasOptSize() || 440 llvm::shouldOptimizeForSize(&MBB, PSI, MBFI); 441 442 for (auto I = MBB.rbegin(); I != MBB.rend(); ++I) { 443 MachineInstr *MI = &*I; 444 445 if (MachineInstr *NewMI = tryReplaceInstr(MI, MBB)) 446 MIReplacements.push_back(std::make_pair(MI, NewMI)); 447 448 // We're done with this instruction, update liveness for the next one. 449 LiveRegs.stepBackward(*MI); 450 } 451 452 while (!MIReplacements.empty()) { 453 MachineInstr *MI = MIReplacements.back().first; 454 MachineInstr *NewMI = MIReplacements.back().second; 455 MIReplacements.pop_back(); 456 MBB.insert(MI, NewMI); 457 MBB.erase(MI); 458 } 459 } 460