xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/OptimizePHIs.cpp (revision f976241773df2260e6170317080761d1c5814fe5)
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/TargetRegisterInfo.h"
23 #include "llvm/CodeGen/TargetSubtargetInfo.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 (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
86     Changed |= OptimizeBB(*I);
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   unsigned 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     unsigned 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() &&
119         !SrcMI->getOperand(0).getSubReg() &&
120         !SrcMI->getOperand(1).getSubReg() &&
121         TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg())) {
122       SrcReg = SrcMI->getOperand(1).getReg();
123       SrcMI = MRI->getVRegDef(SrcReg);
124     }
125     if (!SrcMI)
126       return false;
127 
128     if (SrcMI->isPHI()) {
129       if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
130         return false;
131     } else {
132       // Fail if there is more than one non-phi/non-move register.
133       if (SingleValReg != 0 && SingleValReg != SrcReg)
134         return false;
135       SingleValReg = SrcReg;
136     }
137   }
138   return true;
139 }
140 
141 /// IsDeadPHICycle - Check if the register defined by a PHI is only used by
142 /// other PHIs in a cycle.
143 bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
144   assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
145   unsigned DstReg = MI->getOperand(0).getReg();
146   assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&
147          "PHI destination is not a virtual register");
148 
149   // See if we already saw this register.
150   if (!PHIsInCycle.insert(MI).second)
151     return true;
152 
153   // Don't scan crazily complex things.
154   if (PHIsInCycle.size() == 16)
155     return false;
156 
157   for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DstReg)) {
158     if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle))
159       return false;
160   }
161 
162   return true;
163 }
164 
165 /// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
166 /// a single value.
167 bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
168   bool Changed = false;
169   for (MachineBasicBlock::iterator
170          MII = MBB.begin(), E = MBB.end(); MII != E; ) {
171     MachineInstr *MI = &*MII++;
172     if (!MI->isPHI())
173       break;
174 
175     // Check for single-value PHI cycles.
176     unsigned SingleValReg = 0;
177     InstrSet PHIsInCycle;
178     if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
179         SingleValReg != 0) {
180       unsigned OldReg = MI->getOperand(0).getReg();
181       if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg)))
182         continue;
183 
184       MRI->replaceRegWith(OldReg, SingleValReg);
185       MI->eraseFromParent();
186 
187       // The kill flags on OldReg and SingleValReg may no longer be correct.
188       MRI->clearKillFlags(SingleValReg);
189 
190       ++NumPHICycles;
191       Changed = true;
192       continue;
193     }
194 
195     // Check for dead PHI cycles.
196     PHIsInCycle.clear();
197     if (IsDeadPHICycle(MI, PHIsInCycle)) {
198       for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
199            PI != PE; ++PI) {
200         MachineInstr *PhiMI = *PI;
201         if (MII == PhiMI)
202           ++MII;
203         PhiMI->eraseFromParent();
204       }
205       ++NumDeadPHICycles;
206       Changed = true;
207     }
208   }
209   return Changed;
210 }
211