1 //===---------------------- ProcessImplicitDefs.cpp -----------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #define DEBUG_TYPE "processimplicitdefs"
11
12 #include "llvm/ADT/SetVector.h"
13 #include "llvm/Analysis/AliasAnalysis.h"
14 #include "llvm/CodeGen/MachineFunctionPass.h"
15 #include "llvm/CodeGen/MachineInstr.h"
16 #include "llvm/CodeGen/MachineRegisterInfo.h"
17 #include "llvm/CodeGen/Passes.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/raw_ostream.h"
20 #include "llvm/Target/TargetInstrInfo.h"
21
22 using namespace llvm;
23
24 namespace {
25 /// Process IMPLICIT_DEF instructions and make sure there is one implicit_def
26 /// for each use. Add isUndef marker to implicit_def defs and their uses.
27 class ProcessImplicitDefs : public MachineFunctionPass {
28 const TargetInstrInfo *TII;
29 const TargetRegisterInfo *TRI;
30 MachineRegisterInfo *MRI;
31
32 SmallSetVector<MachineInstr*, 16> WorkList;
33
34 void processImplicitDef(MachineInstr *MI);
35 bool canTurnIntoImplicitDef(MachineInstr *MI);
36
37 public:
38 static char ID;
39
ProcessImplicitDefs()40 ProcessImplicitDefs() : MachineFunctionPass(ID) {
41 initializeProcessImplicitDefsPass(*PassRegistry::getPassRegistry());
42 }
43
44 virtual void getAnalysisUsage(AnalysisUsage &au) const;
45
46 virtual bool runOnMachineFunction(MachineFunction &fn);
47 };
48 } // end anonymous namespace
49
50 char ProcessImplicitDefs::ID = 0;
51 char &llvm::ProcessImplicitDefsID = ProcessImplicitDefs::ID;
52
53 INITIALIZE_PASS_BEGIN(ProcessImplicitDefs, "processimpdefs",
54 "Process Implicit Definitions", false, false)
55 INITIALIZE_PASS_END(ProcessImplicitDefs, "processimpdefs",
56 "Process Implicit Definitions", false, false)
57
getAnalysisUsage(AnalysisUsage & AU) const58 void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const {
59 AU.setPreservesCFG();
60 AU.addPreserved<AliasAnalysis>();
61 MachineFunctionPass::getAnalysisUsage(AU);
62 }
63
canTurnIntoImplicitDef(MachineInstr * MI)64 bool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) {
65 if (!MI->isCopyLike() &&
66 !MI->isInsertSubreg() &&
67 !MI->isRegSequence() &&
68 !MI->isPHI())
69 return false;
70 for (MIOperands MO(MI); MO.isValid(); ++MO)
71 if (MO->isReg() && MO->isUse() && MO->readsReg())
72 return false;
73 return true;
74 }
75
processImplicitDef(MachineInstr * MI)76 void ProcessImplicitDefs::processImplicitDef(MachineInstr *MI) {
77 DEBUG(dbgs() << "Processing " << *MI);
78 unsigned Reg = MI->getOperand(0).getReg();
79
80 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
81 // For virtual regiusters, mark all uses as <undef>, and convert users to
82 // implicit-def when possible.
83 for (MachineRegisterInfo::use_nodbg_iterator UI =
84 MRI->use_nodbg_begin(Reg),
85 UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
86 MachineOperand &MO = UI.getOperand();
87 MO.setIsUndef();
88 MachineInstr *UserMI = MO.getParent();
89 if (!canTurnIntoImplicitDef(UserMI))
90 continue;
91 DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI);
92 UserMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
93 WorkList.insert(UserMI);
94 }
95 MI->eraseFromParent();
96 return;
97 }
98
99 // This is a physreg implicit-def.
100 // Look for the first instruction to use or define an alias.
101 MachineBasicBlock::instr_iterator UserMI = MI;
102 MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end();
103 bool Found = false;
104 for (++UserMI; UserMI != UserE; ++UserMI) {
105 for (MIOperands MO(UserMI); MO.isValid(); ++MO) {
106 if (!MO->isReg())
107 continue;
108 unsigned UserReg = MO->getReg();
109 if (!TargetRegisterInfo::isPhysicalRegister(UserReg) ||
110 !TRI->regsOverlap(Reg, UserReg))
111 continue;
112 // UserMI uses or redefines Reg. Set <undef> flags on all uses.
113 Found = true;
114 if (MO->isUse())
115 MO->setIsUndef();
116 }
117 if (Found)
118 break;
119 }
120
121 // If we found the using MI, we can erase the IMPLICIT_DEF.
122 if (Found) {
123 DEBUG(dbgs() << "Physreg user: " << *UserMI);
124 MI->eraseFromParent();
125 return;
126 }
127
128 // Using instr wasn't found, it could be in another block.
129 // Leave the physreg IMPLICIT_DEF, but trim any extra operands.
130 for (unsigned i = MI->getNumOperands() - 1; i; --i)
131 MI->RemoveOperand(i);
132 DEBUG(dbgs() << "Keeping physreg: " << *MI);
133 }
134
135 /// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into
136 /// <undef> operands.
runOnMachineFunction(MachineFunction & MF)137 bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) {
138
139 DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n"
140 << "********** Function: " << MF.getName() << '\n');
141
142 bool Changed = false;
143
144 TII = MF.getTarget().getInstrInfo();
145 TRI = MF.getTarget().getRegisterInfo();
146 MRI = &MF.getRegInfo();
147 assert(MRI->isSSA() && "ProcessImplicitDefs only works on SSA form.");
148 assert(WorkList.empty() && "Inconsistent worklist state");
149
150 for (MachineFunction::iterator MFI = MF.begin(), MFE = MF.end();
151 MFI != MFE; ++MFI) {
152 // Scan the basic block for implicit defs.
153 for (MachineBasicBlock::instr_iterator MBBI = MFI->instr_begin(),
154 MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI)
155 if (MBBI->isImplicitDef())
156 WorkList.insert(MBBI);
157
158 if (WorkList.empty())
159 continue;
160
161 DEBUG(dbgs() << "BB#" << MFI->getNumber() << " has " << WorkList.size()
162 << " implicit defs.\n");
163 Changed = true;
164
165 // Drain the WorkList to recursively process any new implicit defs.
166 do processImplicitDef(WorkList.pop_back_val());
167 while (!WorkList.empty());
168 }
169 return Changed;
170 }
171