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