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