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