464 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8/// \file9/// This file defines the pass that looks through the machine instructions10/// late in the compilation, and finds byte or word instructions that11/// can be profitably replaced with 32 bit instructions that give equivalent12/// results for the bits of the results that are used. There are two possible13/// reasons to do this.14///15/// One reason is to avoid false-dependences on the upper portions16/// of the registers. Only instructions that have a destination register17/// 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 destination19/// register is unaffected, because it has a true dependence on the source20/// register already. So, this consideration primarily affects load21/// instructions and register-to-register moves. It would22/// seem like cmov(s) would also be affected, but because of the way cmov is23/// really implemented by most machines as reading both the destination and24/// 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 the26/// destination register as well.27///28/// The other reason to do this is for potential code size savings. Word29/// operations need an extra override byte compared to their 32 bit30/// versions. So this can convert many word operations to their larger31/// size, saving a byte in encoding. This could introduce partial register32/// dependences where none existed however. As an example take:33/// orw ax, $0x100034/// addw ax, $335/// now if this were to get transformed into36/// orw ax, $100037/// addl eax, $338/// because the addl encodes shorter than the addw, this would introduce39/// a use of a register that was only partially written earlier. On older40/// Intel processors this can be quite a performance penalty, so this should41/// probably only be done when it can be proven that a new partial dependence42/// wouldn't be created, or when your know a newer processor is being43/// 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/LiveRegUnits.h"54#include "llvm/CodeGen/MachineFunctionPass.h"55#include "llvm/CodeGen/MachineInstrBuilder.h"56#include "llvm/CodeGen/MachineRegisterInfo.h"57#include "llvm/CodeGen/MachineSizeOpts.h"58#include "llvm/CodeGen/Passes.h"59#include "llvm/CodeGen/TargetInstrInfo.h"60#include "llvm/Support/Debug.h"61#include "llvm/Support/raw_ostream.h"62using namespace llvm;63 64#define FIXUPBW_DESC "X86 Byte/Word Instruction Fixup"65#define FIXUPBW_NAME "x86-fixup-bw-insts"66 67#define DEBUG_TYPE FIXUPBW_NAME68 69// Option to allow this optimization pass to have fine-grained control.70static cl::opt<bool>71 FixupBWInsts("fixup-byte-word-insts",72 cl::desc("Change byte and word instructions to larger sizes"),73 cl::init(true), cl::Hidden);74 75namespace {76class FixupBWInstPass : public MachineFunctionPass {77 /// Loop over all of the instructions in the basic block replacing applicable78 /// byte or word instructions with better alternatives.79 void processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB);80 81 /// This returns the 32 bit super reg of the original destination register of82 /// the MachineInstr passed in, if that super register is dead just prior to83 /// \p OrigMI. Otherwise it returns Register().84 Register getSuperRegDestIfDead(MachineInstr *OrigMI) const;85 86 /// Change the MachineInstr \p MI into the equivalent extending load to 32 bit87 /// register if it is safe to do so. Return the replacement instruction if88 /// OK, otherwise return nullptr.89 MachineInstr *tryReplaceLoad(unsigned New32BitOpcode, MachineInstr *MI) const;90 91 /// Change the MachineInstr \p MI into the equivalent 32-bit copy if it is92 /// safe to do so. Return the replacement instruction if OK, otherwise return93 /// nullptr.94 MachineInstr *tryReplaceCopy(MachineInstr *MI) const;95 96 /// Change the MachineInstr \p MI into the equivalent extend to 32 bit97 /// register if it is safe to do so. Return the replacement instruction if98 /// OK, otherwise return nullptr.99 MachineInstr *tryReplaceExtend(unsigned New32BitOpcode,100 MachineInstr *MI) const;101 102 // Change the MachineInstr \p MI into an eqivalent 32 bit instruction if103 // possible. Return the replacement instruction if OK, return nullptr104 // otherwise.105 MachineInstr *tryReplaceInstr(MachineInstr *MI, MachineBasicBlock &MBB) const;106 107public:108 static char ID;109 110 StringRef getPassName() const override { return FIXUPBW_DESC; }111 112 FixupBWInstPass() : MachineFunctionPass(ID) { }113 114 void getAnalysisUsage(AnalysisUsage &AU) const override {115 AU.addRequired<ProfileSummaryInfoWrapperPass>();116 AU.addRequired<LazyMachineBlockFrequencyInfoPass>();117 MachineFunctionPass::getAnalysisUsage(AU);118 }119 120 /// Loop over all of the basic blocks, replacing byte and word instructions by121 /// equivalent 32 bit instructions where performance or code size can be122 /// improved.123 bool runOnMachineFunction(MachineFunction &MF) override;124 125 MachineFunctionProperties getRequiredProperties() const override {126 return MachineFunctionProperties().setNoVRegs();127 }128 129private:130 MachineFunction *MF = nullptr;131 132 /// Machine instruction info used throughout the class.133 const X86InstrInfo *TII = nullptr;134 135 const TargetRegisterInfo *TRI = nullptr;136 137 /// Local member for function's OptForSize attribute.138 bool OptForSize = false;139 140 /// Register Liveness information after the current instruction.141 LiveRegUnits LiveUnits;142 143 ProfileSummaryInfo *PSI = nullptr;144 MachineBlockFrequencyInfo *MBFI = nullptr;145};146char FixupBWInstPass::ID = 0;147}148 149INITIALIZE_PASS(FixupBWInstPass, FIXUPBW_NAME, FIXUPBW_DESC, false, false)150 151FunctionPass *llvm::createX86FixupBWInsts() { return new FixupBWInstPass(); }152 153bool FixupBWInstPass::runOnMachineFunction(MachineFunction &MF) {154 if (!FixupBWInsts || skipFunction(MF.getFunction()))155 return false;156 157 this->MF = &MF;158 TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();159 TRI = MF.getRegInfo().getTargetRegisterInfo();160 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();161 MBFI = (PSI && PSI->hasProfileSummary()) ?162 &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI() :163 nullptr;164 LiveUnits.init(TII->getRegisterInfo());165 166 LLVM_DEBUG(dbgs() << "Start X86FixupBWInsts\n";);167 168 // Process all basic blocks.169 for (auto &MBB : MF)170 processBasicBlock(MF, MBB);171 172 LLVM_DEBUG(dbgs() << "End X86FixupBWInsts\n";);173 174 return true;175}176 177/// Check if after \p OrigMI the only portion of super register178/// of the destination register of \p OrigMI that is alive is that179/// destination register.180///181/// If so, return that super register in \p SuperDestReg.182Register FixupBWInstPass::getSuperRegDestIfDead(MachineInstr *OrigMI) const {183 const X86RegisterInfo *TRI = &TII->getRegisterInfo();184 Register OrigDestReg = OrigMI->getOperand(0).getReg();185 Register SuperDestReg = getX86SubSuperRegister(OrigDestReg, 32);186 assert(SuperDestReg.isValid() && "Invalid Operand");187 188 const auto SubRegIdx = TRI->getSubRegIndex(SuperDestReg, OrigDestReg);189 190 // Make sure that the sub-register that this instruction has as its191 // destination is the lowest order sub-register of the super-register.192 // If it isn't, then the register isn't really dead even if the193 // super-register is considered dead.194 if (SubRegIdx == X86::sub_8bit_hi)195 return Register();196 197 // Test all regunits of the super register that are not part of the198 // sub register. If none of them are live then the super register is safe to199 // use.200 bool SuperIsLive = false;201 auto Range = TRI->regunits(OrigDestReg);202 MCRegUnitIterator I = Range.begin(), E = Range.end();203 for (MCRegUnit S : TRI->regunits(SuperDestReg)) {204 I = std::lower_bound(I, E, S);205 if ((I == E || *I > S) &&206 LiveUnits.getBitVector().test(static_cast<unsigned>(S))) {207 SuperIsLive = true;208 break;209 }210 }211 if (!SuperIsLive)212 return SuperDestReg;213 214 // If we get here, the super-register destination (or some part of it) is215 // marked as live after the original instruction.216 //217 // The X86 backend does not have subregister liveness tracking enabled,218 // so liveness information might be overly conservative. Specifically, the219 // super register might be marked as live because it is implicitly defined220 // by the instruction we are examining.221 //222 // However, for some specific instructions (this pass only cares about MOVs)223 // we can produce more precise results by analysing that MOV's operands.224 //225 // Indeed, if super-register is not live before the mov it means that it226 // was originally <read-undef> and so we are free to modify these227 // undef upper bits. That may happen in case where the use is in another MBB228 // and the vreg/physreg corresponding to the move has higher width than229 // necessary (e.g. due to register coalescing with a "truncate" copy).230 // So, we would like to handle patterns like this:231 //232 // %bb.2: derived from LLVM BB %if.then233 // Live Ins: %rdi234 // Predecessors according to CFG: %bb.0235 // %ax<def> = MOV16rm killed %rdi, 1, %noreg, 0, %noreg, implicit-def %eax236 // ; No implicit %eax237 // Successors according to CFG: %bb.3(?%)238 //239 // %bb.3: derived from LLVM BB %if.end240 // Live Ins: %eax Only %ax is actually live241 // Predecessors according to CFG: %bb.2 %bb.1242 // %ax = KILL %ax, implicit killed %eax243 // RET 0, %ax244 unsigned Opc = OrigMI->getOpcode();245 // These are the opcodes currently known to work with the code below, if246 // something // else will be added we need to ensure that new opcode has the247 // same properties.248 if (Opc != X86::MOV8rm && Opc != X86::MOV16rm && Opc != X86::MOV8rr &&249 Opc != X86::MOV16rr)250 return Register();251 252 bool IsDefined = false;253 for (auto &MO: OrigMI->implicit_operands()) {254 if (!MO.isReg())255 continue;256 257 if (MO.isDef() && TRI->isSuperRegisterEq(OrigDestReg, MO.getReg()))258 IsDefined = true;259 260 // If MO is a use of any part of the destination register but is not equal261 // to OrigDestReg or one of its subregisters, we cannot use SuperDestReg.262 // For example, if OrigDestReg is %al then an implicit use of %ah, %ax,263 // %eax, or %rax will prevent us from using the %eax register.264 if (MO.isUse() && !TRI->isSubRegisterEq(OrigDestReg, MO.getReg()) &&265 TRI->regsOverlap(SuperDestReg, MO.getReg()))266 return Register();267 }268 // Reg is not Imp-def'ed -> it's live both before/after the instruction.269 if (!IsDefined)270 return Register();271 272 // Otherwise, the Reg is not live before the MI and the MOV can't273 // make it really live, so it's in fact dead even after the MI.274 return SuperDestReg;275}276 277MachineInstr *FixupBWInstPass::tryReplaceLoad(unsigned New32BitOpcode,278 MachineInstr *MI) const {279 // We are going to try to rewrite this load to a larger zero-extending280 // load. This is safe if all portions of the 32 bit super-register281 // of the original destination register, except for the original destination282 // register are dead. getSuperRegDestIfDead checks that.283 Register NewDestReg = getSuperRegDestIfDead(MI);284 if (!NewDestReg)285 return nullptr;286 287 // Safe to change the instruction.288 MachineInstrBuilder MIB =289 BuildMI(*MF, MIMetadata(*MI), TII->get(New32BitOpcode), NewDestReg);290 291 unsigned NumArgs = MI->getNumOperands();292 for (unsigned i = 1; i < NumArgs; ++i)293 MIB.add(MI->getOperand(i));294 295 MIB.setMemRefs(MI->memoperands());296 297 // If it was debug tracked, record a substitution.298 if (unsigned OldInstrNum = MI->peekDebugInstrNum()) {299 unsigned Subreg = TRI->getSubRegIndex(MIB->getOperand(0).getReg(),300 MI->getOperand(0).getReg());301 unsigned NewInstrNum = MIB->getDebugInstrNum(*MF);302 MF->makeDebugValueSubstitution({OldInstrNum, 0}, {NewInstrNum, 0}, Subreg);303 }304 305 return MIB;306}307 308MachineInstr *FixupBWInstPass::tryReplaceCopy(MachineInstr *MI) const {309 assert(MI->getNumExplicitOperands() == 2);310 auto &OldDest = MI->getOperand(0);311 auto &OldSrc = MI->getOperand(1);312 313 Register NewDestReg = getSuperRegDestIfDead(MI);314 if (!NewDestReg)315 return nullptr;316 317 Register NewSrcReg = getX86SubSuperRegister(OldSrc.getReg(), 32);318 assert(NewSrcReg.isValid() && "Invalid Operand");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 that330 // we don't care about the higher bits by reading it as Undef, and adding331 // an imp-use on the original subregister.332 MachineInstrBuilder MIB =333 BuildMI(*MF, MIMetadata(*MI), 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 345MachineInstr *FixupBWInstPass::tryReplaceExtend(unsigned New32BitOpcode,346 MachineInstr *MI) const {347 Register NewDestReg = getSuperRegDestIfDead(MI);348 if (!NewDestReg)349 return nullptr;350 351 // Don't interfere with formation of CBW instructions which should be a352 // shorter encoding than even the MOVSX32rr8. It's also immune to partial353 // 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, MIMetadata(*MI), 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 if (unsigned OldInstrNum = MI->peekDebugInstrNum()) {370 unsigned Subreg = TRI->getSubRegIndex(MIB->getOperand(0).getReg(),371 MI->getOperand(0).getReg());372 unsigned NewInstrNum = MIB->getDebugInstrNum(*MF);373 MF->makeDebugValueSubstitution({OldInstrNum, 0}, {NewInstrNum, 0}, Subreg);374 }375 376 return MIB;377}378 379MachineInstr *FixupBWInstPass::tryReplaceInstr(MachineInstr *MI,380 MachineBasicBlock &MBB) const {381 // See if this is an instruction of the type we are currently looking for.382 switch (MI->getOpcode()) {383 384 case X86::MOV8rm:385 // Replace 8-bit loads with the zero-extending version if not optimizing386 // for size. The extending op is cheaper across a wide range of uarch and387 // it avoids a potentially expensive partial register stall. It takes an388 // extra byte to encode, however, so don't do this when optimizing for size.389 if (!OptForSize)390 return tryReplaceLoad(X86::MOVZX32rm8, MI);391 break;392 393 case X86::MOV16rm:394 // Always try to replace 16 bit load with 32 bit zero extending.395 // Code size is the same, and there is sometimes a perf advantage396 // from eliminating a false dependence on the upper portion of397 // the register.398 return tryReplaceLoad(X86::MOVZX32rm16, MI);399 400 case X86::MOV8rr:401 case X86::MOV16rr:402 // Always try to replace 8/16 bit copies with a 32 bit copy.403 // Code size is either less (16) or equal (8), and there is sometimes a404 // perf advantage from eliminating a false dependence on the upper portion405 // of the register.406 return tryReplaceCopy(MI);407 408 case X86::MOVSX16rr8:409 return tryReplaceExtend(X86::MOVSX32rr8, MI);410 case X86::MOVSX16rm8:411 return tryReplaceExtend(X86::MOVSX32rm8, MI);412 case X86::MOVZX16rr8:413 return tryReplaceExtend(X86::MOVZX32rr8, MI);414 case X86::MOVZX16rm8:415 return tryReplaceExtend(X86::MOVZX32rm8, MI);416 417 default:418 // nothing to do here.419 break;420 }421 422 return nullptr;423}424 425void FixupBWInstPass::processBasicBlock(MachineFunction &MF,426 MachineBasicBlock &MBB) {427 428 // This algorithm doesn't delete the instructions it is replacing429 // right away. By leaving the existing instructions in place, the430 // register liveness information doesn't change, and this makes the431 // analysis that goes on be better than if the replaced instructions432 // were immediately removed.433 //434 // This algorithm always creates a replacement instruction435 // and notes that and the original in a data structure, until the436 // whole BB has been analyzed. This keeps the replacement instructions437 // from making it seem as if the larger register might be live.438 SmallVector<std::pair<MachineInstr *, MachineInstr *>, 8> MIReplacements;439 440 // Start computing liveness for this block. We iterate from the end to be able441 // to update this for each instruction.442 LiveUnits.clear();443 // We run after PEI, so we need to AddPristinesAndCSRs.444 LiveUnits.addLiveOuts(MBB);445 446 OptForSize = llvm::shouldOptimizeForSize(&MBB, PSI, MBFI);447 448 for (MachineInstr &MI : llvm::reverse(MBB)) {449 if (MachineInstr *NewMI = tryReplaceInstr(&MI, MBB))450 MIReplacements.push_back(std::make_pair(&MI, NewMI));451 452 // We're done with this instruction, update liveness for the next one.453 LiveUnits.stepBackward(MI);454 }455 456 while (!MIReplacements.empty()) {457 MachineInstr *MI = MIReplacements.back().first;458 MachineInstr *NewMI = MIReplacements.back().second;459 MIReplacements.pop_back();460 MBB.insert(MI, NewMI);461 MBB.erase(MI);462 }463}464