1 //===-- OptimizePHIs.cpp - Optimize machine instruction PHIs --------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass optimizes machine instruction PHIs to take advantage of
11 // opportunities created during DAG legalization.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/CodeGen/Passes.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/MachineInstr.h"
20 #include "llvm/CodeGen/MachineRegisterInfo.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/Target/TargetInstrInfo.h"
25 #define DEBUG_TYPE "phi-opt"
27 STATISTIC(NumPHICycles, "Number of PHI cycles replaced");
28 STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles");
31 class OptimizePHIs : public MachineFunctionPass {
32 MachineRegisterInfo *MRI;
33 const TargetInstrInfo *TII;
36 static char ID; // Pass identification
37 OptimizePHIs() : MachineFunctionPass(ID) {
38 initializeOptimizePHIsPass(*PassRegistry::getPassRegistry());
41 bool runOnMachineFunction(MachineFunction &MF) override;
43 void getAnalysisUsage(AnalysisUsage &AU) const override {
45 MachineFunctionPass::getAnalysisUsage(AU);
49 typedef SmallPtrSet<MachineInstr*, 16> InstrSet;
50 typedef SmallPtrSetIterator<MachineInstr*> InstrSetIterator;
52 bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg,
53 InstrSet &PHIsInCycle);
54 bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle);
55 bool OptimizeBB(MachineBasicBlock &MBB);
59 char OptimizePHIs::ID = 0;
60 char &llvm::OptimizePHIsID = OptimizePHIs::ID;
61 INITIALIZE_PASS(OptimizePHIs, "opt-phis",
62 "Optimize machine instruction PHIs", false, false)
64 bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) {
65 if (skipOptnoneFunction(*Fn.getFunction()))
68 MRI = &Fn.getRegInfo();
69 TII = Fn.getTarget().getInstrInfo();
71 // Find dead PHI cycles and PHI cycles that can be replaced by a single
72 // value. InstCombine does these optimizations, but DAG legalization may
73 // introduce new opportunities, e.g., when i64 values are split up for
76 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
77 Changed |= OptimizeBB(*I);
82 /// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands
83 /// are copies of SingleValReg, possibly via copies through other PHIs. If
84 /// SingleValReg is zero on entry, it is set to the register with the single
85 /// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that
86 /// have been scanned.
87 bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
88 unsigned &SingleValReg,
89 InstrSet &PHIsInCycle) {
90 assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
91 unsigned DstReg = MI->getOperand(0).getReg();
93 // See if we already saw this register.
94 if (!PHIsInCycle.insert(MI))
97 // Don't scan crazily complex things.
98 if (PHIsInCycle.size() == 16)
101 // Scan the PHI operands.
102 for (unsigned i = 1; i != MI->getNumOperands(); i += 2) {
103 unsigned SrcReg = MI->getOperand(i).getReg();
104 if (SrcReg == DstReg)
106 MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
108 // Skip over register-to-register moves.
109 if (SrcMI && SrcMI->isCopy() &&
110 !SrcMI->getOperand(0).getSubReg() &&
111 !SrcMI->getOperand(1).getSubReg() &&
112 TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg()))
113 SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg());
117 if (SrcMI->isPHI()) {
118 if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
121 // Fail if there is more than one non-phi/non-move register.
122 if (SingleValReg != 0)
124 SingleValReg = SrcReg;
130 /// IsDeadPHICycle - Check if the register defined by a PHI is only used by
131 /// other PHIs in a cycle.
132 bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
133 assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
134 unsigned DstReg = MI->getOperand(0).getReg();
135 assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&
136 "PHI destination is not a virtual register");
138 // See if we already saw this register.
139 if (!PHIsInCycle.insert(MI))
142 // Don't scan crazily complex things.
143 if (PHIsInCycle.size() == 16)
146 for (MachineInstr &UseMI : MRI->use_instructions(DstReg)) {
147 if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle))
154 /// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
156 bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
157 bool Changed = false;
158 for (MachineBasicBlock::iterator
159 MII = MBB.begin(), E = MBB.end(); MII != E; ) {
160 MachineInstr *MI = &*MII++;
164 // Check for single-value PHI cycles.
165 unsigned SingleValReg = 0;
166 InstrSet PHIsInCycle;
167 if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
169 unsigned OldReg = MI->getOperand(0).getReg();
170 if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg)))
173 MRI->replaceRegWith(OldReg, SingleValReg);
174 MI->eraseFromParent();
180 // Check for dead PHI cycles.
182 if (IsDeadPHICycle(MI, PHIsInCycle)) {
183 for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
185 MachineInstr *PhiMI = *PI;
188 PhiMI->eraseFromParent();