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 10233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#define DEBUG_TYPE "processimplicitdefs" 11233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 125984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen#include "llvm/ADT/SetVector.h" 13233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/Analysis/AliasAnalysis.h" 140cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 15233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/MachineInstr.h" 16233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/MachineRegisterInfo.h" 17233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/Passes.h" 18233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/Support/Debug.h" 195984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 20233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/Target/TargetInstrInfo.h" 21233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 22233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesusing namespace llvm; 23233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 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 440cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &au) const; 450cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen 460cafa139c01aa9d5072b185d686a05b9d8ab1ee7Jakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &fn); 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)) { 815984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // For virtual regiusters, mark all uses as <undef>, and convert users to 825984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // implicit-def when possible. 835984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (MachineRegisterInfo::use_nodbg_iterator UI = 845984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MRI->use_nodbg_begin(Reg), 855984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 865984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MachineOperand &MO = UI.getOperand(); 875984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MO.setIsUndef(); 885984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MachineInstr *UserMI = MO.getParent(); 895984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (!canTurnIntoImplicitDef(UserMI)) 90233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames continue; 915984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI); 925984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen UserMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); 935984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen WorkList.insert(UserMI); 94233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 955984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MI->eraseFromParent(); 965984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen return; 975984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen } 98233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 995984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // This is a physreg implicit-def. 1005984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // Look for the first instruction to use or define an alias. 1015984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MachineBasicBlock::instr_iterator UserMI = MI; 1025984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end(); 1035984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen bool Found = false; 1045984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (++UserMI; UserMI != UserE; ++UserMI) { 1055984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (MIOperands MO(UserMI); MO.isValid(); ++MO) { 1065984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (!MO->isReg()) 107233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames continue; 1085984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen unsigned UserReg = MO->getReg(); 1095984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (!TargetRegisterInfo::isPhysicalRegister(UserReg) || 1105984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen !TRI->regsOverlap(Reg, UserReg)) 111233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames continue; 1125984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // UserMI uses or redefines Reg. Set <undef> flags on all uses. 1135984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen Found = true; 1145984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (MO->isUse()) 1155984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MO->setIsUndef(); 1165984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen } 1175984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (Found) 1185984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen break; 1195984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen } 120233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1215984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // If we found the using MI, we can erase the IMPLICIT_DEF. 1225984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (Found) { 1235984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen DEBUG(dbgs() << "Physreg user: " << *UserMI); 1245984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MI->eraseFromParent(); 1255984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen return; 1265984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen } 127e7c9195706ce17b5016f74005ecab5523519deeaEvan Cheng 1285984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // Using instr wasn't found, it could be in another block. 1295984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // Leave the physreg IMPLICIT_DEF, but trim any extra operands. 1305984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (unsigned i = MI->getNumOperands() - 1; i; --i) 1315984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MI->RemoveOperand(i); 1325984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen DEBUG(dbgs() << "Keeping physreg: " << *MI); 1335984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen} 134233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1355984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen/// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into 1365984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen/// <undef> operands. 1375984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesenbool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) { 138e7c9195706ce17b5016f74005ecab5523519deeaEvan Cheng 1395984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n" 140986d76d7b3844b9a2f3d01a48975952749267a93David Blaikie << "********** Function: " << MF.getName() << '\n'); 141e7c9195706ce17b5016f74005ecab5523519deeaEvan Cheng 1425984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen bool Changed = false; 143233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1445984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen TII = MF.getTarget().getInstrInfo(); 1455984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen TRI = MF.getTarget().getRegisterInfo(); 1465984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MRI = &MF.getRegInfo(); 1475984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen assert(MRI->isSSA() && "ProcessImplicitDefs only works on SSA form."); 1485984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen assert(WorkList.empty() && "Inconsistent worklist state"); 1495984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen 1505984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (MachineFunction::iterator MFI = MF.begin(), MFE = MF.end(); 1515984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MFI != MFE; ++MFI) { 1525984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // Scan the basic block for implicit defs. 1535984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen for (MachineBasicBlock::instr_iterator MBBI = MFI->instr_begin(), 1545984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) 1555984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (MBBI->isImplicitDef()) 1565984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen WorkList.insert(MBBI); 1575984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen 1585984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen if (WorkList.empty()) 1595984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen continue; 1605984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen 1615984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << MFI->getNumber() << " has " << WorkList.size() 1625984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen << " implicit defs.\n"); 1635984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen Changed = true; 1645984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen 1655984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen // Drain the WorkList to recursively process any new implicit defs. 1665984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen do processImplicitDef(WorkList.pop_back_val()); 1675984d2b31fe3c69e46d2b81439a8c3ef0bdf9a91Jakob Stoklund Olesen while (!WorkList.empty()); 168233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 169233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return Changed; 170233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames} 171