1233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames//===---------------------- ProcessImplicitDefs.cpp -----------------------===// 2233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// 3233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// The LLVM Compiler Infrastructure 4233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// 5233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// This file is distributed under the University of Illinois Open Source 6233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// License. See LICENSE.TXT for details. 7233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// 8233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames//===----------------------------------------------------------------------===// 9233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 105984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen#include "llvm/ADT/SetVector.h" 11233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/Analysis/AliasAnalysis.h" 120cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 13233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/MachineInstr.h" 14233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/MachineRegisterInfo.h" 15233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/Passes.h" 16233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/Support/Debug.h" 175984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 18233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/Target/TargetInstrInfo.h" 19233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 20233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesusing namespace llvm; 21233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 22dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "processimplicitdefs" 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 240cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesennamespace { 250cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen/// Process IMPLICIT_DEF instructions and make sure there is one implicit_def 260cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen/// for each use. Add isUndef marker to implicit_def defs and their uses. 270cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesenclass ProcessImplicitDefs : public MachineFunctionPass { 280cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen const TargetInstrInfo *TII; 290cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen const TargetRegisterInfo *TRI; 300cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen MachineRegisterInfo *MRI; 310cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen 325984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen SmallSetVector<MachineInstr*, 16> WorkList; 335984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen 345984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen void processImplicitDef(MachineInstr *MI); 355984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen bool canTurnIntoImplicitDef(MachineInstr *MI); 360cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen 370cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesenpublic: 380cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen static char ID; 390cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen 400cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen ProcessImplicitDefs() : MachineFunctionPass(ID) { 410cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen initializeProcessImplicitDefsPass(*PassRegistry::getPassRegistry()); 420cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen } 430cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &au) const override; 450cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnMachineFunction(MachineFunction &fn) override; 470cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen}; 480cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen} // end anonymous namespace 490cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen 50233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hameschar ProcessImplicitDefs::ID = 0; 518dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trickchar &llvm::ProcessImplicitDefsID = ProcessImplicitDefs::ID; 528dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick 532ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(ProcessImplicitDefs, "processimpdefs", 54dd061b317711d4165e01f30e8be4798c832819b8Cameron Zwarich "Process Implicit Definitions", false, false) 552ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(ProcessImplicitDefs, "processimpdefs", 56dd061b317711d4165e01f30e8be4798c832819b8Cameron Zwarich "Process Implicit Definitions", false, false) 57233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 58233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const { 59233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.setPreservesCFG(); 60233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<AliasAnalysis>(); 61233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineFunctionPass::getAnalysisUsage(AU); 62233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames} 63233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 645984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesenbool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) { 655984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (!MI->isCopyLike() && 665984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen !MI->isInsertSubreg() && 675984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen !MI->isRegSequence() && 685984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen !MI->isPHI()) 69db8980903717e1127463f00a34cae9bd29f82a91Evan Cheng return false; 705984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (MIOperands MO(MI); MO.isValid(); ++MO) 715984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (MO->isReg() && MO->isUse() && MO->readsReg()) 725984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen return false; 735984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen return true; 74db8980903717e1127463f00a34cae9bd29f82a91Evan Cheng} 75db8980903717e1127463f00a34cae9bd29f82a91Evan Cheng 765984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesenvoid ProcessImplicitDefs::processImplicitDef(MachineInstr *MI) { 775984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen DEBUG(dbgs() << "Processing " << *MI); 785984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen unsigned Reg = MI->getOperand(0).getReg(); 795984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen 805984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(Reg)) { 81b1aa5e43a2976caed47e21d31823a48bf8324000Matthias Braun // For virtual registers, mark all uses as <undef>, and convert users to 825984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // implicit-def when possible. 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { 845984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MO.setIsUndef(); 855984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MachineInstr *UserMI = MO.getParent(); 865984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (!canTurnIntoImplicitDef(UserMI)) 87233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames continue; 885984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI); 895984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen UserMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); 905984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen WorkList.insert(UserMI); 91233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 925984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MI->eraseFromParent(); 935984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen return; 945984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen } 95233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 965984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // This is a physreg implicit-def. 975984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // Look for the first instruction to use or define an alias. 985984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MachineBasicBlock::instr_iterator UserMI = MI; 995984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end(); 1005984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen bool Found = false; 1015984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (++UserMI; UserMI != UserE; ++UserMI) { 1025984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (MIOperands MO(UserMI); MO.isValid(); ++MO) { 1035984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (!MO->isReg()) 104233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames continue; 1055984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen unsigned UserReg = MO->getReg(); 1065984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (!TargetRegisterInfo::isPhysicalRegister(UserReg) || 1075984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen !TRI->regsOverlap(Reg, UserReg)) 108233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames continue; 1095984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // UserMI uses or redefines Reg. Set <undef> flags on all uses. 1105984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen Found = true; 1115984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (MO->isUse()) 1125984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MO->setIsUndef(); 1135984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen } 1145984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (Found) 1155984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen break; 1165984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen } 117233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1185984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // If we found the using MI, we can erase the IMPLICIT_DEF. 1195984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (Found) { 1205984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen DEBUG(dbgs() << "Physreg user: " << *UserMI); 1215984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MI->eraseFromParent(); 1225984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen return; 1235984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen } 124e7c9195706ce17b5016f74005ecab5523519deeaEvan Cheng 1255984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // Using instr wasn't found, it could be in another block. 1265984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // Leave the physreg IMPLICIT_DEF, but trim any extra operands. 1275984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (unsigned i = MI->getNumOperands() - 1; i; --i) 1285984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MI->RemoveOperand(i); 1295984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen DEBUG(dbgs() << "Keeping physreg: " << *MI); 1305984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen} 131233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1325984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen/// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into 1335984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen/// <undef> operands. 1345984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesenbool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) { 135e7c9195706ce17b5016f74005ecab5523519deeaEvan Cheng 1365984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n" 137986d76d7b3844b9a2f3d01a48975952749267a93David Blaikie << "********** Function: " << MF.getName() << '\n'); 138e7c9195706ce17b5016f74005ecab5523519deeaEvan Cheng 1395984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen bool Changed = false; 140233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1415984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen TII = MF.getTarget().getInstrInfo(); 1425984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen TRI = MF.getTarget().getRegisterInfo(); 1435984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MRI = &MF.getRegInfo(); 1445984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen assert(MRI->isSSA() && "ProcessImplicitDefs only works on SSA form."); 1455984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen assert(WorkList.empty() && "Inconsistent worklist state"); 1465984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen 1475984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (MachineFunction::iterator MFI = MF.begin(), MFE = MF.end(); 1485984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MFI != MFE; ++MFI) { 1495984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // Scan the basic block for implicit defs. 1505984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (MachineBasicBlock::instr_iterator MBBI = MFI->instr_begin(), 1515984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) 1525984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (MBBI->isImplicitDef()) 1535984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen WorkList.insert(MBBI); 1545984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen 1555984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (WorkList.empty()) 1565984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen continue; 1575984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen 1585984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << MFI->getNumber() << " has " << WorkList.size() 1595984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen << " implicit defs.\n"); 1605984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen Changed = true; 1615984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen 1625984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // Drain the WorkList to recursively process any new implicit defs. 1635984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen do processImplicitDef(WorkList.pop_back_val()); 1645984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen while (!WorkList.empty()); 165233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 166233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return Changed; 167233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames} 168