948 lines · cpp
1//====- X86FlagsCopyLowering.cpp - Lowers COPY nodes of EFLAGS ------------===//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///10/// Lowers COPY nodes of EFLAGS by directly extracting and preserving individual11/// flag bits.12///13/// We have to do this by carefully analyzing and rewriting the usage of the14/// copied EFLAGS register because there is no general way to rematerialize the15/// entire EFLAGS register safely and efficiently. Using `popf` both forces16/// dynamic stack adjustment and can create correctness issues due to IF, TF,17/// and other non-status flags being overwritten. Using sequences involving18/// SAHF don't work on all x86 processors and are often quite slow compared to19/// directly testing a single status preserved in its own GPR.20///21//===----------------------------------------------------------------------===//22 23#include "X86.h"24#include "X86InstrInfo.h"25#include "X86Subtarget.h"26#include "llvm/ADT/DepthFirstIterator.h"27#include "llvm/ADT/PostOrderIterator.h"28#include "llvm/ADT/STLExtras.h"29#include "llvm/ADT/ScopeExit.h"30#include "llvm/ADT/SmallPtrSet.h"31#include "llvm/ADT/SmallVector.h"32#include "llvm/ADT/Statistic.h"33#include "llvm/CodeGen/MachineBasicBlock.h"34#include "llvm/CodeGen/MachineConstantPool.h"35#include "llvm/CodeGen/MachineDominators.h"36#include "llvm/CodeGen/MachineFunction.h"37#include "llvm/CodeGen/MachineFunctionPass.h"38#include "llvm/CodeGen/MachineInstr.h"39#include "llvm/CodeGen/MachineInstrBuilder.h"40#include "llvm/CodeGen/MachineModuleInfo.h"41#include "llvm/CodeGen/MachineOperand.h"42#include "llvm/CodeGen/MachineRegisterInfo.h"43#include "llvm/CodeGen/MachineSSAUpdater.h"44#include "llvm/CodeGen/TargetInstrInfo.h"45#include "llvm/CodeGen/TargetRegisterInfo.h"46#include "llvm/CodeGen/TargetSchedule.h"47#include "llvm/CodeGen/TargetSubtargetInfo.h"48#include "llvm/IR/DebugLoc.h"49#include "llvm/MC/MCSchedule.h"50#include "llvm/Pass.h"51#include "llvm/Support/Debug.h"52#include "llvm/Support/raw_ostream.h"53#include <cassert>54#include <iterator>55#include <utility>56 57using namespace llvm;58 59#define PASS_KEY "x86-flags-copy-lowering"60#define DEBUG_TYPE PASS_KEY61 62STATISTIC(NumCopiesEliminated, "Number of copies of EFLAGS eliminated");63STATISTIC(NumSetCCsInserted, "Number of setCC instructions inserted");64STATISTIC(NumTestsInserted, "Number of test instructions inserted");65STATISTIC(NumAddsInserted, "Number of adds instructions inserted");66STATISTIC(NumNFsConvertedTo, "Number of NF instructions converted to");67 68extern cl::opt<bool> X86EnableAPXForRelocation;69 70namespace {71 72// Convenient array type for storing registers associated with each condition.73using CondRegArray = std::array<Register, X86::LAST_VALID_COND + 1>;74 75class X86FlagsCopyLoweringPass : public MachineFunctionPass {76public:77 X86FlagsCopyLoweringPass() : MachineFunctionPass(ID) {}78 79 StringRef getPassName() const override { return "X86 EFLAGS copy lowering"; }80 bool runOnMachineFunction(MachineFunction &MF) override;81 void getAnalysisUsage(AnalysisUsage &AU) const override;82 83 /// Pass identification, replacement for typeid.84 static char ID;85 86private:87 MachineRegisterInfo *MRI = nullptr;88 const X86Subtarget *Subtarget = nullptr;89 const X86InstrInfo *TII = nullptr;90 const TargetRegisterInfo *TRI = nullptr;91 const TargetRegisterClass *PromoteRC = nullptr;92 MachineDominatorTree *MDT = nullptr;93 94 CondRegArray collectCondsInRegs(MachineBasicBlock &MBB,95 MachineBasicBlock::iterator CopyDefI);96 97 Register promoteCondToReg(MachineBasicBlock &MBB,98 MachineBasicBlock::iterator TestPos,99 const DebugLoc &TestLoc, X86::CondCode Cond);100 std::pair<Register, bool> getCondOrInverseInReg(101 MachineBasicBlock &TestMBB, MachineBasicBlock::iterator TestPos,102 const DebugLoc &TestLoc, X86::CondCode Cond, CondRegArray &CondRegs);103 void insertTest(MachineBasicBlock &MBB, MachineBasicBlock::iterator Pos,104 const DebugLoc &Loc, Register Reg);105 106 void rewriteSetCC(MachineBasicBlock &MBB, MachineBasicBlock::iterator Pos,107 const DebugLoc &Loc, MachineInstr &MI,108 CondRegArray &CondRegs);109 void rewriteArithmetic(MachineBasicBlock &MBB,110 MachineBasicBlock::iterator Pos, const DebugLoc &Loc,111 MachineInstr &MI, CondRegArray &CondRegs);112 void rewriteMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator Pos,113 const DebugLoc &Loc, MachineInstr &MI, CondRegArray &CondRegs);114};115 116} // end anonymous namespace117 118INITIALIZE_PASS_BEGIN(X86FlagsCopyLoweringPass, DEBUG_TYPE,119 "X86 EFLAGS copy lowering", false, false)120INITIALIZE_PASS_END(X86FlagsCopyLoweringPass, DEBUG_TYPE,121 "X86 EFLAGS copy lowering", false, false)122 123FunctionPass *llvm::createX86FlagsCopyLoweringPass() {124 return new X86FlagsCopyLoweringPass();125}126 127char X86FlagsCopyLoweringPass::ID = 0;128 129void X86FlagsCopyLoweringPass::getAnalysisUsage(AnalysisUsage &AU) const {130 AU.addUsedIfAvailable<MachineDominatorTreeWrapperPass>();131 MachineFunctionPass::getAnalysisUsage(AU);132}133 134static bool isArithmeticOp(unsigned Opc) {135 return X86::isADC(Opc) || X86::isSBB(Opc) || X86::isRCL(Opc) ||136 X86::isRCR(Opc) || (Opc == X86::SETB_C32r || Opc == X86::SETB_C64r);137}138 139static MachineBasicBlock &splitBlock(MachineBasicBlock &MBB,140 MachineInstr &SplitI,141 const X86InstrInfo &TII) {142 MachineFunction &MF = *MBB.getParent();143 144 assert(SplitI.getParent() == &MBB &&145 "Split instruction must be in the split block!");146 assert(SplitI.isBranch() &&147 "Only designed to split a tail of branch instructions!");148 assert(X86::getCondFromBranch(SplitI) != X86::COND_INVALID &&149 "Must split on an actual jCC instruction!");150 151 // Dig out the previous instruction to the split point.152 MachineInstr &PrevI = *std::prev(SplitI.getIterator());153 assert(PrevI.isBranch() && "Must split after a branch!");154 assert(X86::getCondFromBranch(PrevI) != X86::COND_INVALID &&155 "Must split after an actual jCC instruction!");156 assert(!std::prev(PrevI.getIterator())->isTerminator() &&157 "Must only have this one terminator prior to the split!");158 159 // Grab the one successor edge that will stay in `MBB`.160 MachineBasicBlock &UnsplitSucc = *PrevI.getOperand(0).getMBB();161 162 // Analyze the original block to see if we are actually splitting an edge163 // into two edges. This can happen when we have multiple conditional jumps to164 // the same successor.165 bool IsEdgeSplit =166 std::any_of(SplitI.getIterator(), MBB.instr_end(),167 [&](MachineInstr &MI) {168 assert(MI.isTerminator() &&169 "Should only have spliced terminators!");170 return llvm::any_of(171 MI.operands(), [&](MachineOperand &MOp) {172 return MOp.isMBB() && MOp.getMBB() == &UnsplitSucc;173 });174 }) ||175 MBB.getFallThrough() == &UnsplitSucc;176 177 MachineBasicBlock &NewMBB = *MF.CreateMachineBasicBlock();178 179 // Insert the new block immediately after the current one. Any existing180 // fallthrough will be sunk into this new block anyways.181 MF.insert(std::next(MachineFunction::iterator(&MBB)), &NewMBB);182 183 // Splice the tail of instructions into the new block.184 NewMBB.splice(NewMBB.end(), &MBB, SplitI.getIterator(), MBB.end());185 186 // Copy the necessary succesors (and their probability info) into the new187 // block.188 for (auto SI = MBB.succ_begin(), SE = MBB.succ_end(); SI != SE; ++SI)189 if (IsEdgeSplit || *SI != &UnsplitSucc)190 NewMBB.copySuccessor(&MBB, SI);191 // Normalize the probabilities if we didn't end up splitting the edge.192 if (!IsEdgeSplit)193 NewMBB.normalizeSuccProbs();194 195 // Now replace all of the moved successors in the original block with the new196 // block. This will merge their probabilities.197 for (MachineBasicBlock *Succ : NewMBB.successors())198 if (Succ != &UnsplitSucc)199 MBB.replaceSuccessor(Succ, &NewMBB);200 201 // We should always end up replacing at least one successor.202 assert(MBB.isSuccessor(&NewMBB) &&203 "Failed to make the new block a successor!");204 205 // Now update all the PHIs.206 for (MachineBasicBlock *Succ : NewMBB.successors()) {207 for (MachineInstr &MI : *Succ) {208 if (!MI.isPHI())209 break;210 211 for (int OpIdx = 1, NumOps = MI.getNumOperands(); OpIdx < NumOps;212 OpIdx += 2) {213 MachineOperand &OpV = MI.getOperand(OpIdx);214 MachineOperand &OpMBB = MI.getOperand(OpIdx + 1);215 assert(OpMBB.isMBB() && "Block operand to a PHI is not a block!");216 if (OpMBB.getMBB() != &MBB)217 continue;218 219 // Replace the operand for unsplit successors220 if (!IsEdgeSplit || Succ != &UnsplitSucc) {221 OpMBB.setMBB(&NewMBB);222 223 // We have to continue scanning as there may be multiple entries in224 // the PHI.225 continue;226 }227 228 // When we have split the edge append a new successor.229 MI.addOperand(MF, OpV);230 MI.addOperand(MF, MachineOperand::CreateMBB(&NewMBB));231 break;232 }233 }234 }235 236 return NewMBB;237}238 239enum EFLAGSClobber { NoClobber, EvitableClobber, InevitableClobber };240 241static EFLAGSClobber getClobberType(const MachineInstr &MI) {242 const MachineOperand *FlagDef =243 MI.findRegisterDefOperand(X86::EFLAGS, /*TRI=*/nullptr);244 if (!FlagDef)245 return NoClobber;246 247 // For the instructions are ADDrm/ADDmr with relocation, we'll skip the248 // optimization for replacing non-NF with NF. This is to keep backward249 // compatiblity with old version of linkers without APX relocation type250 // support on Linux OS.251 bool IsWithReloc =252 X86EnableAPXForRelocation ? false : isAddMemInstrWithRelocation(MI);253 254 if (FlagDef->isDead() && X86::getNFVariant(MI.getOpcode()) && !IsWithReloc)255 return EvitableClobber;256 257 return InevitableClobber;258}259 260bool X86FlagsCopyLoweringPass::runOnMachineFunction(MachineFunction &MF) {261 LLVM_DEBUG(dbgs() << "********** " << getPassName() << " : " << MF.getName()262 << " **********\n");263 264 Subtarget = &MF.getSubtarget<X86Subtarget>();265 MRI = &MF.getRegInfo();266 TII = Subtarget->getInstrInfo();267 TRI = Subtarget->getRegisterInfo();268 PromoteRC = &X86::GR8RegClass;269 270 if (MF.empty())271 // Nothing to do for a degenerate empty function...272 return false;273 274 if (none_of(MRI->def_instructions(X86::EFLAGS), [](const MachineInstr &MI) {275 return MI.getOpcode() == TargetOpcode::COPY;276 }))277 return false;278 279 // We change the code, so we don't preserve the dominator tree anyway. If we280 // got a valid MDT from the pass manager, use that, otherwise construct one281 // now. This is an optimization that avoids unnecessary MDT construction for282 // functions that have no flag copies.283 284 auto MDTWrapper = getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>();285 std::unique_ptr<MachineDominatorTree> OwnedMDT;286 if (MDTWrapper) {287 MDT = &MDTWrapper->getDomTree();288 } else {289 OwnedMDT = std::make_unique<MachineDominatorTree>(MF);290 MDT = OwnedMDT.get();291 }292 293 // Collect the copies in RPO so that when there are chains where a copy is in294 // turn copied again we visit the first one first. This ensures we can find295 // viable locations for testing the original EFLAGS that dominate all the296 // uses across complex CFGs.297 SmallSetVector<MachineInstr *, 4> Copies;298 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);299 for (MachineBasicBlock *MBB : RPOT)300 for (MachineInstr &MI : *MBB)301 if (MI.getOpcode() == TargetOpcode::COPY &&302 MI.getOperand(0).getReg() == X86::EFLAGS)303 Copies.insert(&MI);304 305 // Try to elminate the copys by transform the instructions between copy and306 // copydef to the NF (no flags update) variants, e.g.307 //308 // %1:gr64 = COPY $eflags309 // OP1 implicit-def dead $eflags310 // $eflags = COPY %1311 // OP2 cc, implicit $eflags312 //313 // ->314 //315 // OP1_NF316 // OP2 implicit $eflags317 if (Subtarget->hasNF()) {318 SmallSetVector<MachineInstr *, 4> RemovedCopies;319 // CopyIIt may be invalidated by removing copies.320 auto CopyIIt = Copies.begin(), CopyIEnd = Copies.end();321 while (CopyIIt != CopyIEnd) {322 auto NCopyIIt = std::next(CopyIIt);323 SmallSetVector<MachineInstr *, 4> EvitableClobbers;324 MachineInstr *CopyI = *CopyIIt;325 MachineOperand &VOp = CopyI->getOperand(1);326 MachineInstr *CopyDefI = MRI->getVRegDef(VOp.getReg());327 MachineBasicBlock *CopyIMBB = CopyI->getParent();328 MachineBasicBlock *CopyDefIMBB = CopyDefI->getParent();329 // Walk all basic blocks reachable in depth-first iteration on the inverse330 // CFG from CopyIMBB to CopyDefIMBB. These blocks are all the blocks that331 // may be executed between the execution of CopyDefIMBB and CopyIMBB. On332 // all execution paths, instructions from CopyDefI to CopyI (exclusive)333 // has to be NF-convertible if it clobbers flags.334 for (auto BI = idf_begin(CopyIMBB), BE = idf_end(CopyDefIMBB); BI != BE;335 ++BI) {336 MachineBasicBlock *MBB = *BI;337 for (auto I = (MBB != CopyDefIMBB)338 ? MBB->begin()339 : std::next(MachineBasicBlock::iterator(CopyDefI)),340 E = (MBB != CopyIMBB) ? MBB->end()341 : MachineBasicBlock::iterator(CopyI);342 I != E; ++I) {343 MachineInstr &MI = *I;344 EFLAGSClobber ClobberType = getClobberType(MI);345 if (ClobberType == NoClobber)346 continue;347 348 if (ClobberType == InevitableClobber)349 goto ProcessNextCopyI;350 351 assert(ClobberType == EvitableClobber && "unexpected workflow");352 EvitableClobbers.insert(&MI);353 }354 }355 // Covert evitable clobbers into NF variants and remove the copyies.356 RemovedCopies.insert(CopyI);357 CopyI->eraseFromParent();358 if (MRI->use_nodbg_empty(CopyDefI->getOperand(0).getReg())) {359 RemovedCopies.insert(CopyDefI);360 CopyDefI->eraseFromParent();361 }362 ++NumCopiesEliminated;363 for (auto *Clobber : EvitableClobbers) {364 unsigned NewOpc = X86::getNFVariant(Clobber->getOpcode());365 assert(NewOpc && "evitable clobber must have a NF variant");366 Clobber->setDesc(TII->get(NewOpc));367 Clobber->removeOperand(368 Clobber->findRegisterDefOperand(X86::EFLAGS, /*TRI=*/nullptr)369 ->getOperandNo());370 ++NumNFsConvertedTo;371 }372 // Update liveins for basic blocks in the path373 for (auto BI = idf_begin(CopyIMBB), BE = idf_end(CopyDefIMBB); BI != BE;374 ++BI)375 if (*BI != CopyDefIMBB)376 BI->addLiveIn(X86::EFLAGS);377 ProcessNextCopyI:378 CopyIIt = NCopyIIt;379 }380 Copies.set_subtract(RemovedCopies);381 }382 383 // For the rest of copies that cannot be eliminated by NF transform, we use384 // setcc to preserve the flags in GPR32 before OP1, and recheck its value385 // before using the flags, e.g.386 //387 // %1:gr64 = COPY $eflags388 // OP1 implicit-def dead $eflags389 // $eflags = COPY %1390 // OP2 cc, implicit $eflags391 //392 // ->393 //394 // %1:gr8 = SETCCr cc, implicit $eflags395 // OP1 implicit-def dead $eflags396 // TEST8rr %1, %1, implicit-def $eflags397 // OP2 ne, implicit $eflags398 for (MachineInstr *CopyI : Copies) {399 MachineBasicBlock &MBB = *CopyI->getParent();400 401 MachineOperand &VOp = CopyI->getOperand(1);402 assert(VOp.isReg() &&403 "The input to the copy for EFLAGS should always be a register!");404 MachineInstr &CopyDefI = *MRI->getVRegDef(VOp.getReg());405 if (CopyDefI.getOpcode() != TargetOpcode::COPY) {406 // FIXME: The big likely candidate here are PHI nodes. We could in theory407 // handle PHI nodes, but it gets really, really hard. Insanely hard. Hard408 // enough that it is probably better to change every other part of LLVM409 // to avoid creating them. The issue is that once we have PHIs we won't410 // know which original EFLAGS value we need to capture with our setCCs411 // below. The end result will be computing a complete set of setCCs that412 // we *might* want, computing them in every place where we copy *out* of413 // EFLAGS and then doing SSA formation on all of them to insert necessary414 // PHI nodes and consume those here. Then hoping that somehow we DCE the415 // unnecessary ones. This DCE seems very unlikely to be successful and so416 // we will almost certainly end up with a glut of dead setCC417 // instructions. Until we have a motivating test case and fail to avoid418 // it by changing other parts of LLVM's lowering, we refuse to handle419 // this complex case here.420 LLVM_DEBUG(421 dbgs() << "ERROR: Encountered unexpected def of an eflags copy: ";422 CopyDefI.dump());423 report_fatal_error(424 "Cannot lower EFLAGS copy unless it is defined in turn by a copy!");425 }426 427 auto Cleanup = make_scope_exit([&] {428 // All uses of the EFLAGS copy are now rewritten, kill the copy into429 // eflags and if dead the copy from.430 CopyI->eraseFromParent();431 if (MRI->use_empty(CopyDefI.getOperand(0).getReg()))432 CopyDefI.eraseFromParent();433 ++NumCopiesEliminated;434 });435 436 MachineOperand &DOp = CopyI->getOperand(0);437 assert(DOp.isDef() && "Expected register def!");438 assert(DOp.getReg() == X86::EFLAGS && "Unexpected copy def register!");439 if (DOp.isDead())440 continue;441 442 MachineBasicBlock *TestMBB = CopyDefI.getParent();443 auto TestPos = CopyDefI.getIterator();444 DebugLoc TestLoc = CopyDefI.getDebugLoc();445 446 LLVM_DEBUG(dbgs() << "Rewriting copy: "; CopyI->dump());447 448 // Walk up across live-in EFLAGS to find where they were actually def'ed.449 //450 // This copy's def may just be part of a region of blocks covered by451 // a single def of EFLAGS and we want to find the top of that region where452 // possible.453 //454 // This is essentially a search for a *candidate* reaching definition455 // location. We don't need to ever find the actual reaching definition here,456 // but we want to walk up the dominator tree to find the highest point which457 // would be viable for such a definition.458 auto HasEFLAGSClobber = [&](MachineBasicBlock::iterator Begin,459 MachineBasicBlock::iterator End) {460 // Scan backwards as we expect these to be relatively short and often find461 // a clobber near the end.462 return llvm::any_of(463 llvm::reverse(llvm::make_range(Begin, End)), [&](MachineInstr &MI) {464 // Flag any instruction (other than the copy we are465 // currently rewriting) that defs EFLAGS.466 return &MI != CopyI &&467 MI.findRegisterDefOperand(X86::EFLAGS, /*TRI=*/nullptr);468 });469 };470 auto HasEFLAGSClobberPath = [&](MachineBasicBlock *BeginMBB,471 MachineBasicBlock *EndMBB) {472 assert(MDT->dominates(BeginMBB, EndMBB) &&473 "Only support paths down the dominator tree!");474 SmallPtrSet<MachineBasicBlock *, 4> Visited;475 SmallVector<MachineBasicBlock *, 4> Worklist;476 // We terminate at the beginning. No need to scan it.477 Visited.insert(BeginMBB);478 Worklist.push_back(EndMBB);479 do {480 auto *MBB = Worklist.pop_back_val();481 for (auto *PredMBB : MBB->predecessors()) {482 if (!Visited.insert(PredMBB).second)483 continue;484 if (HasEFLAGSClobber(PredMBB->begin(), PredMBB->end()))485 return true;486 // Enqueue this block to walk its predecessors.487 Worklist.push_back(PredMBB);488 }489 } while (!Worklist.empty());490 // No clobber found along a path from the begin to end.491 return false;492 };493 while (TestMBB->isLiveIn(X86::EFLAGS) && !TestMBB->pred_empty() &&494 !HasEFLAGSClobber(TestMBB->begin(), TestPos)) {495 // Find the nearest common dominator of the predecessors, as496 // that will be the best candidate to hoist into.497 MachineBasicBlock *HoistMBB =498 std::accumulate(std::next(TestMBB->pred_begin()), TestMBB->pred_end(),499 *TestMBB->pred_begin(),500 [&](MachineBasicBlock *LHS, MachineBasicBlock *RHS) {501 return MDT->findNearestCommonDominator(LHS, RHS);502 });503 504 // Now we need to scan all predecessors that may be reached along paths to505 // the hoist block. A clobber anywhere in any of these blocks the hoist.506 // Note that this even handles loops because we require *no* clobbers.507 if (HasEFLAGSClobberPath(HoistMBB, TestMBB))508 break;509 510 // We also need the terminators to not sneakily clobber flags.511 if (HasEFLAGSClobber(HoistMBB->getFirstTerminator()->getIterator(),512 HoistMBB->instr_end()))513 break;514 515 // We found a viable location, hoist our test position to it.516 TestMBB = HoistMBB;517 TestPos = TestMBB->getFirstTerminator()->getIterator();518 // Clear the debug location as it would just be confusing after hoisting.519 TestLoc = DebugLoc();520 }521 LLVM_DEBUG({522 auto DefIt = llvm::find_if(523 llvm::reverse(llvm::make_range(TestMBB->instr_begin(), TestPos)),524 [&](MachineInstr &MI) {525 return MI.findRegisterDefOperand(X86::EFLAGS, /*TRI=*/nullptr);526 });527 if (DefIt.base() != TestMBB->instr_begin()) {528 dbgs() << " Using EFLAGS defined by: ";529 DefIt->dump();530 } else {531 dbgs() << " Using live-in flags for BB:\n";532 TestMBB->dump();533 }534 });535 536 // While rewriting uses, we buffer jumps and rewrite them in a second pass537 // because doing so will perturb the CFG that we are walking to find the538 // uses in the first place.539 SmallVector<MachineInstr *, 4> JmpIs;540 541 // Gather the condition flags that have already been preserved in542 // registers. We do this from scratch each time as we expect there to be543 // very few of them and we expect to not revisit the same copy definition544 // many times. If either of those change sufficiently we could build a map545 // of these up front instead.546 CondRegArray CondRegs = collectCondsInRegs(*TestMBB, TestPos);547 548 // Collect the basic blocks we need to scan. Typically this will just be549 // a single basic block but we may have to scan multiple blocks if the550 // EFLAGS copy lives into successors.551 SmallVector<MachineBasicBlock *, 2> Blocks;552 SmallPtrSet<MachineBasicBlock *, 2> VisitedBlocks;553 Blocks.push_back(&MBB);554 555 do {556 MachineBasicBlock &UseMBB = *Blocks.pop_back_val();557 558 // Track when if/when we find a kill of the flags in this block.559 bool FlagsKilled = false;560 561 // In most cases, we walk from the beginning to the end of the block. But562 // when the block is the same block as the copy is from, we will visit it563 // twice. The first time we start from the copy and go to the end. The564 // second time we start from the beginning and go to the copy. This lets565 // us handle copies inside of cycles.566 // FIXME: This loop is *super* confusing. This is at least in part567 // a symptom of all of this routine needing to be refactored into568 // documentable components. Once done, there may be a better way to write569 // this loop.570 for (auto MII = (&UseMBB == &MBB && !VisitedBlocks.count(&UseMBB))571 ? std::next(CopyI->getIterator())572 : UseMBB.instr_begin(),573 MIE = UseMBB.instr_end();574 MII != MIE;) {575 MachineInstr &MI = *MII++;576 // If we are in the original copy block and encounter either the copy577 // def or the copy itself, break so that we don't re-process any part of578 // the block or process the instructions in the range that was copied579 // over.580 if (&MI == CopyI || &MI == &CopyDefI) {581 assert(&UseMBB == &MBB && VisitedBlocks.count(&MBB) &&582 "Should only encounter these on the second pass over the "583 "original block.");584 break;585 }586 587 MachineOperand *FlagUse =588 MI.findRegisterUseOperand(X86::EFLAGS, /*TRI=*/nullptr);589 FlagsKilled = MI.modifiesRegister(X86::EFLAGS, TRI);590 591 if (!FlagUse && FlagsKilled)592 break;593 else if (!FlagUse)594 continue;595 596 LLVM_DEBUG(dbgs() << " Rewriting use: "; MI.dump());597 598 // Check the kill flag before we rewrite as that may change it.599 if (FlagUse->isKill())600 FlagsKilled = true;601 602 // Once we encounter a branch, the rest of the instructions must also be603 // branches. We can't rewrite in place here, so we handle them below.604 //605 // Note that we don't have to handle tail calls here, even conditional606 // tail calls, as those are not introduced into the X86 MI until post-RA607 // branch folding or black placement. As a consequence, we get to deal608 // with the simpler formulation of conditional branches followed by tail609 // calls.610 if (X86::getCondFromBranch(MI) != X86::COND_INVALID) {611 auto JmpIt = MI.getIterator();612 do {613 JmpIs.push_back(&*JmpIt);614 ++JmpIt;615 } while (JmpIt != UseMBB.instr_end() &&616 X86::getCondFromBranch(*JmpIt) != X86::COND_INVALID);617 break;618 }619 620 // Otherwise we can just rewrite in-place.621 unsigned Opc = MI.getOpcode();622 if (Opc == TargetOpcode::COPY) {623 // Just replace this copy with the original copy def.624 MRI->replaceRegWith(MI.getOperand(0).getReg(),625 CopyDefI.getOperand(0).getReg());626 MI.eraseFromParent();627 } else if (X86::isSETCC(Opc) || X86::isSETZUCC(Opc)) {628 rewriteSetCC(*TestMBB, TestPos, TestLoc, MI, CondRegs);629 } else if (isArithmeticOp(Opc)) {630 rewriteArithmetic(*TestMBB, TestPos, TestLoc, MI, CondRegs);631 } else {632 rewriteMI(*TestMBB, TestPos, TestLoc, MI, CondRegs);633 }634 635 // If this was the last use of the flags, we're done.636 if (FlagsKilled)637 break;638 }639 640 // If the flags were killed, we're done with this block.641 if (FlagsKilled)642 continue;643 644 // Otherwise we need to scan successors for ones where the flags live-in645 // and queue those up for processing.646 for (MachineBasicBlock *SuccMBB : UseMBB.successors())647 if (SuccMBB->isLiveIn(X86::EFLAGS) &&648 VisitedBlocks.insert(SuccMBB).second) {649 // We currently don't do any PHI insertion and so we require that the650 // test basic block dominates all of the use basic blocks. Further, we651 // can't have a cycle from the test block back to itself as that would652 // create a cycle requiring a PHI to break it.653 //654 // We could in theory do PHI insertion here if it becomes useful by655 // just taking undef values in along every edge that we don't trace656 // this EFLAGS copy along. This isn't as bad as fully general PHI657 // insertion, but still seems like a great deal of complexity.658 //659 // Because it is theoretically possible that some earlier MI pass or660 // other lowering transformation could induce this to happen, we do661 // a hard check even in non-debug builds here.662 if (SuccMBB == TestMBB || !MDT->dominates(TestMBB, SuccMBB)) {663 LLVM_DEBUG({664 dbgs()665 << "ERROR: Encountered use that is not dominated by our test "666 "basic block! Rewriting this would require inserting PHI "667 "nodes to track the flag state across the CFG.\n\nTest "668 "block:\n";669 TestMBB->dump();670 dbgs() << "Use block:\n";671 SuccMBB->dump();672 });673 report_fatal_error(674 "Cannot lower EFLAGS copy when original copy def "675 "does not dominate all uses.");676 }677 678 Blocks.push_back(SuccMBB);679 680 // After this, EFLAGS will be recreated before each use.681 SuccMBB->removeLiveIn(X86::EFLAGS);682 }683 } while (!Blocks.empty());684 685 // Now rewrite the jumps that use the flags. These we handle specially686 // because if there are multiple jumps in a single basic block we'll have687 // to do surgery on the CFG.688 MachineBasicBlock *LastJmpMBB = nullptr;689 for (MachineInstr *JmpI : JmpIs) {690 // Past the first jump within a basic block we need to split the blocks691 // apart.692 if (JmpI->getParent() == LastJmpMBB)693 splitBlock(*JmpI->getParent(), *JmpI, *TII);694 else695 LastJmpMBB = JmpI->getParent();696 697 rewriteMI(*TestMBB, TestPos, TestLoc, *JmpI, CondRegs);698 }699 700 // FIXME: Mark the last use of EFLAGS before the copy's def as a kill if701 // the copy's def operand is itself a kill.702 }703 704#ifndef NDEBUG705 for (MachineBasicBlock &MBB : MF)706 for (MachineInstr &MI : MBB)707 if (MI.getOpcode() == TargetOpcode::COPY &&708 (MI.getOperand(0).getReg() == X86::EFLAGS ||709 MI.getOperand(1).getReg() == X86::EFLAGS)) {710 LLVM_DEBUG(dbgs() << "ERROR: Found a COPY involving EFLAGS: ";711 MI.dump());712 llvm_unreachable("Unlowered EFLAGS copy!");713 }714#endif715 716 return true;717}718 719/// Collect any conditions that have already been set in registers so that we720/// can re-use them rather than adding duplicates.721CondRegArray X86FlagsCopyLoweringPass::collectCondsInRegs(722 MachineBasicBlock &MBB, MachineBasicBlock::iterator TestPos) {723 CondRegArray CondRegs = {};724 725 // Scan backwards across the range of instructions with live EFLAGS.726 for (MachineInstr &MI :727 llvm::reverse(llvm::make_range(MBB.begin(), TestPos))) {728 X86::CondCode Cond = X86::getCondFromSETCC(MI);729 if (Cond != X86::COND_INVALID && !MI.mayStore() &&730 MI.getOperand(0).isReg() && MI.getOperand(0).getReg().isVirtual()) {731 assert(MI.getOperand(0).isDef() &&732 "A non-storing SETcc should always define a register!");733 CondRegs[Cond] = MI.getOperand(0).getReg();734 }735 736 // Stop scanning when we see the first definition of the EFLAGS as prior to737 // this we would potentially capture the wrong flag state.738 if (MI.findRegisterDefOperand(X86::EFLAGS, /*TRI=*/nullptr))739 break;740 }741 return CondRegs;742}743 744Register X86FlagsCopyLoweringPass::promoteCondToReg(745 MachineBasicBlock &TestMBB, MachineBasicBlock::iterator TestPos,746 const DebugLoc &TestLoc, X86::CondCode Cond) {747 Register Reg = MRI->createVirtualRegister(PromoteRC);748 auto SetI = BuildMI(TestMBB, TestPos, TestLoc, TII->get(X86::SETCCr), Reg)749 .addImm(Cond);750 (void)SetI;751 LLVM_DEBUG(dbgs() << " save cond: "; SetI->dump());752 ++NumSetCCsInserted;753 return Reg;754}755 756std::pair<Register, bool> X86FlagsCopyLoweringPass::getCondOrInverseInReg(757 MachineBasicBlock &TestMBB, MachineBasicBlock::iterator TestPos,758 const DebugLoc &TestLoc, X86::CondCode Cond, CondRegArray &CondRegs) {759 Register &CondReg = CondRegs[Cond];760 Register &InvCondReg = CondRegs[X86::GetOppositeBranchCondition(Cond)];761 if (!CondReg && !InvCondReg)762 CondReg = promoteCondToReg(TestMBB, TestPos, TestLoc, Cond);763 764 if (CondReg)765 return {CondReg, false};766 else767 return {InvCondReg, true};768}769 770void X86FlagsCopyLoweringPass::insertTest(MachineBasicBlock &MBB,771 MachineBasicBlock::iterator Pos,772 const DebugLoc &Loc, Register Reg) {773 auto TestI =774 BuildMI(MBB, Pos, Loc, TII->get(X86::TEST8rr)).addReg(Reg).addReg(Reg);775 (void)TestI;776 LLVM_DEBUG(dbgs() << " test cond: "; TestI->dump());777 ++NumTestsInserted;778}779 780void X86FlagsCopyLoweringPass::rewriteSetCC(MachineBasicBlock &MBB,781 MachineBasicBlock::iterator Pos,782 const DebugLoc &Loc,783 MachineInstr &MI,784 CondRegArray &CondRegs) {785 X86::CondCode Cond = X86::getCondFromSETCC(MI);786 // Note that we can't usefully rewrite this to the inverse without complex787 // analysis of the users of the setCC. Largely we rely on duplicates which788 // could have been avoided already being avoided here.789 Register &CondReg = CondRegs[Cond];790 if (!CondReg)791 CondReg = promoteCondToReg(MBB, Pos, Loc, Cond);792 793 if (X86::isSETZUCC(MI.getOpcode())) {794 // SETZUCC is generated for register only for now.795 assert(!MI.mayStore() && "Cannot handle memory variants");796 assert(MI.getOperand(0).isReg() &&797 "Cannot have a non-register defined operand to SETZUcc!");798 Register OldReg = MI.getOperand(0).getReg();799 // Drop Kill flags on the old register before replacing. CondReg may have800 // a longer live range.801 MRI->clearKillFlags(OldReg);802 for (auto &Use : MRI->use_instructions(OldReg)) {803 assert(Use.getOpcode() == X86::INSERT_SUBREG &&804 "SETZUCC should be only used by INSERT_SUBREG");805 Use.getOperand(2).setReg(CondReg);806 // Recover MOV32r0 before INSERT_SUBREG, which removed by SETZUCC.807 Register ZeroReg = MRI->createVirtualRegister(&X86::GR32RegClass);808 BuildMI(*Use.getParent(), &Use, Use.getDebugLoc(), TII->get(X86::MOV32r0),809 ZeroReg);810 Use.getOperand(1).setReg(ZeroReg);811 }812 MI.eraseFromParent();813 return;814 }815 816 // Rewriting a register def is trivial: we just replace the register and817 // remove the setcc.818 if (!MI.mayStore()) {819 assert(MI.getOperand(0).isReg() &&820 "Cannot have a non-register defined operand to SETcc!");821 Register OldReg = MI.getOperand(0).getReg();822 // Drop Kill flags on the old register before replacing. CondReg may have823 // a longer live range.824 MRI->clearKillFlags(OldReg);825 MRI->replaceRegWith(OldReg, CondReg);826 MI.eraseFromParent();827 return;828 }829 830 // Otherwise, we need to emit a store.831 auto MIB = BuildMI(*MI.getParent(), MI.getIterator(), MI.getDebugLoc(),832 TII->get(X86::MOV8mr));833 // Copy the address operands.834 for (int i = 0; i < X86::AddrNumOperands; ++i)835 MIB.add(MI.getOperand(i));836 837 MIB.addReg(CondReg);838 MIB.setMemRefs(MI.memoperands());839 MI.eraseFromParent();840}841 842void X86FlagsCopyLoweringPass::rewriteArithmetic(843 MachineBasicBlock &MBB, MachineBasicBlock::iterator Pos,844 const DebugLoc &Loc, MachineInstr &MI, CondRegArray &CondRegs) {845 // Arithmetic is either reading CF or OF.846 X86::CondCode Cond = X86::COND_B; // CF == 1847 // The addend to use to reset CF or OF when added to the flag value.848 // Set up an addend that when one is added will need a carry due to not849 // having a higher bit available.850 int Addend = 255;851 852 // Now get a register that contains the value of the flag input to the853 // arithmetic. We require exactly this flag to simplify the arithmetic854 // required to materialize it back into the flag.855 Register &CondReg = CondRegs[Cond];856 if (!CondReg)857 CondReg = promoteCondToReg(MBB, Pos, Loc, Cond);858 859 // Insert an instruction that will set the flag back to the desired value.860 Register TmpReg = MRI->createVirtualRegister(PromoteRC);861 auto AddI =862 BuildMI(*MI.getParent(), MI.getIterator(), MI.getDebugLoc(),863 TII->get(Subtarget->hasNDD() ? X86::ADD8ri_ND : X86::ADD8ri))864 .addDef(TmpReg, RegState::Dead)865 .addReg(CondReg)866 .addImm(Addend);867 (void)AddI;868 LLVM_DEBUG(dbgs() << " add cond: "; AddI->dump());869 ++NumAddsInserted;870 MI.findRegisterUseOperand(X86::EFLAGS, /*TRI=*/nullptr)->setIsKill(true);871}872 873static X86::CondCode getImplicitCondFromMI(unsigned Opc) {874#define FROM_TO(A, B) \875 case X86::CMOV##A##_Fp32: \876 case X86::CMOV##A##_Fp64: \877 case X86::CMOV##A##_Fp80: \878 return X86::COND_##B;879 880 switch (Opc) {881 default:882 return X86::COND_INVALID;883 FROM_TO(B, B)884 FROM_TO(E, E)885 FROM_TO(P, P)886 FROM_TO(BE, BE)887 FROM_TO(NB, AE)888 FROM_TO(NE, NE)889 FROM_TO(NP, NP)890 FROM_TO(NBE, A)891 }892#undef FROM_TO893}894 895static unsigned getOpcodeWithCC(unsigned Opc, X86::CondCode CC) {896 assert((CC == X86::COND_E || CC == X86::COND_NE) && "Unexpected CC");897#define CASE(A) \898 case X86::CMOVB_##A: \899 case X86::CMOVE_##A: \900 case X86::CMOVP_##A: \901 case X86::CMOVBE_##A: \902 case X86::CMOVNB_##A: \903 case X86::CMOVNE_##A: \904 case X86::CMOVNP_##A: \905 case X86::CMOVNBE_##A: \906 return (CC == X86::COND_E) ? X86::CMOVE_##A : X86::CMOVNE_##A;907 switch (Opc) {908 default:909 llvm_unreachable("Unexpected opcode");910 CASE(Fp32)911 CASE(Fp64)912 CASE(Fp80)913 }914#undef CASE915}916 917void X86FlagsCopyLoweringPass::rewriteMI(MachineBasicBlock &MBB,918 MachineBasicBlock::iterator Pos,919 const DebugLoc &Loc, MachineInstr &MI,920 CondRegArray &CondRegs) {921 // First get the register containing this specific condition.922 bool IsImplicitCC = false;923 X86::CondCode CC = X86::getCondFromMI(MI);924 if (CC == X86::COND_INVALID) {925 CC = getImplicitCondFromMI(MI.getOpcode());926 IsImplicitCC = true;927 }928 assert(CC != X86::COND_INVALID && "Unknown EFLAG user!");929 Register CondReg;930 bool Inverted;931 std::tie(CondReg, Inverted) =932 getCondOrInverseInReg(MBB, Pos, Loc, CC, CondRegs);933 934 // Insert a direct test of the saved register.935 insertTest(*MI.getParent(), MI.getIterator(), MI.getDebugLoc(), CondReg);936 937 // Rewrite the instruction to use the !ZF flag from the test, and then kill938 // its use of the flags afterward.939 X86::CondCode NewCC = Inverted ? X86::COND_E : X86::COND_NE;940 if (IsImplicitCC)941 MI.setDesc(TII->get(getOpcodeWithCC(MI.getOpcode(), NewCC)));942 else943 MI.getOperand(MI.getDesc().getNumOperands() - 1).setImm(NewCC);944 945 MI.findRegisterUseOperand(X86::EFLAGS, /*TRI=*/nullptr)->setIsKill(true);946 LLVM_DEBUG(dbgs() << " fixed instruction: "; MI.dump());947}948