1 //===- OptimizePHIs.cpp - Optimize machine instruction PHIs ---------------===//
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 // This pass optimizes machine instruction PHIs to take advantage of
10 // opportunities created during DAG legalization.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ADT/SmallPtrSet.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/CodeGen/MachineBasicBlock.h"
17 #include "llvm/CodeGen/MachineFunction.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/MachineInstr.h"
20 #include "llvm/CodeGen/MachineOperand.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/CodeGen/TargetSubtargetInfo.h"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/Pass.h"
25 #include <cassert>
26 
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "opt-phis"
30 
31 STATISTIC(NumPHICycles, "Number of PHI cycles replaced");
32 STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles");
33 
34 namespace {
35 
36   class OptimizePHIs : public MachineFunctionPass {
37     MachineRegisterInfo *MRI;
38     const TargetInstrInfo *TII;
39 
40   public:
41     static char ID; // Pass identification
42 
43     OptimizePHIs() : MachineFunctionPass(ID) {
44       initializeOptimizePHIsPass(*PassRegistry::getPassRegistry());
45     }
46 
47     bool runOnMachineFunction(MachineFunction &Fn) override;
48 
49     void getAnalysisUsage(AnalysisUsage &AU) const override {
50       AU.setPreservesCFG();
51       MachineFunctionPass::getAnalysisUsage(AU);
52     }
53 
54   private:
55     using InstrSet = SmallPtrSet<MachineInstr *, 16>;
56     using InstrSetIterator = SmallPtrSetIterator<MachineInstr *>;
57 
58     bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg,
59                                InstrSet &PHIsInCycle);
60     bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle);
61     bool OptimizeBB(MachineBasicBlock &MBB);
62   };
63 
64 } // end anonymous namespace
65 
66 char OptimizePHIs::ID = 0;
67 
68 char &llvm::OptimizePHIsID = OptimizePHIs::ID;
69 
70 INITIALIZE_PASS(OptimizePHIs, DEBUG_TYPE,
71                 "Optimize machine instruction PHIs", false, false)
72 
73 bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) {
74   if (skipFunction(Fn.getFunction()))
75     return false;
76 
77   MRI = &Fn.getRegInfo();
78   TII = Fn.getSubtarget().getInstrInfo();
79 
80   // Find dead PHI cycles and PHI cycles that can be replaced by a single
81   // value.  InstCombine does these optimizations, but DAG legalization may
82   // introduce new opportunities, e.g., when i64 values are split up for
83   // 32-bit targets.
84   bool Changed = false;
85   for (MachineBasicBlock &MBB : Fn)
86     Changed |= OptimizeBB(MBB);
87 
88   return Changed;
89 }
90 
91 /// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands
92 /// are copies of SingleValReg, possibly via copies through other PHIs. If
93 /// SingleValReg is zero on entry, it is set to the register with the single
94 /// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that
95 /// have been scanned. PHIs may be grouped by cycle, several cycles or chains.
96 bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
97                                          unsigned &SingleValReg,
98                                          InstrSet &PHIsInCycle) {
99   assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
100   Register DstReg = MI->getOperand(0).getReg();
101 
102   // See if we already saw this register.
103   if (!PHIsInCycle.insert(MI).second)
104     return true;
105 
106   // Don't scan crazily complex things.
107   if (PHIsInCycle.size() == 16)
108     return false;
109 
110   // Scan the PHI operands.
111   for (unsigned i = 1; i != MI->getNumOperands(); i += 2) {
112     Register SrcReg = MI->getOperand(i).getReg();
113     if (SrcReg == DstReg)
114       continue;
115     MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
116 
117     // Skip over register-to-register moves.
118     if (SrcMI && SrcMI->isCopy() && !SrcMI->getOperand(0).getSubReg() &&
119         !SrcMI->getOperand(1).getSubReg() &&
120         Register::isVirtualRegister(SrcMI->getOperand(1).getReg())) {
121       SrcReg = SrcMI->getOperand(1).getReg();
122       SrcMI = MRI->getVRegDef(SrcReg);
123     }
124     if (!SrcMI)
125       return false;
126 
127     if (SrcMI->isPHI()) {
128       if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
129         return false;
130     } else {
131       // Fail if there is more than one non-phi/non-move register.
132       if (SingleValReg != 0 && SingleValReg != SrcReg)
133         return false;
134       SingleValReg = SrcReg;
135     }
136   }
137   return true;
138 }
139 
140 /// IsDeadPHICycle - Check if the register defined by a PHI is only used by
141 /// other PHIs in a cycle.
142 bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
143   assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
144   Register DstReg = MI->getOperand(0).getReg();
145   assert(Register::isVirtualRegister(DstReg) &&
146          "PHI destination is not a virtual register");
147 
148   // See if we already saw this register.
149   if (!PHIsInCycle.insert(MI).second)
150     return true;
151 
152   // Don't scan crazily complex things.
153   if (PHIsInCycle.size() == 16)
154     return false;
155 
156   for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DstReg)) {
157     if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle))
158       return false;
159   }
160 
161   return true;
162 }
163 
164 /// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
165 /// a single value.
166 bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
167   bool Changed = false;
168   for (MachineBasicBlock::iterator
169          MII = MBB.begin(), E = MBB.end(); MII != E; ) {
170     MachineInstr *MI = &*MII++;
171     if (!MI->isPHI())
172       break;
173 
174     // Check for single-value PHI cycles.
175     unsigned SingleValReg = 0;
176     InstrSet PHIsInCycle;
177     if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
178         SingleValReg != 0) {
179       Register OldReg = MI->getOperand(0).getReg();
180       if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg)))
181         continue;
182 
183       MRI->replaceRegWith(OldReg, SingleValReg);
184       MI->eraseFromParent();
185 
186       // The kill flags on OldReg and SingleValReg may no longer be correct.
187       MRI->clearKillFlags(SingleValReg);
188 
189       ++NumPHICycles;
190       Changed = true;
191       continue;
192     }
193 
194     // Check for dead PHI cycles.
195     PHIsInCycle.clear();
196     if (IsDeadPHICycle(MI, PHIsInCycle)) {
197       for (MachineInstr *PhiMI : PHIsInCycle) {
198         if (MII == PhiMI)
199           ++MII;
200         PhiMI->eraseFromParent();
201       }
202       ++NumDeadPHICycles;
203       Changed = true;
204     }
205   }
206   return Changed;
207 }
208