1 //===-- OptimizeExts.cpp - Optimize sign / zero extension instrs -----===//
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 performs optimization of sign / zero extension instructions. It
11 // may be extended to handle other instructions of similar property.
13 // On some targets, some instructions, e.g. X86 sign / zero extension, may
14 // leave the source value in the lower part of the result. This pass will
15 // replace (some) uses of the pre-extension value with uses of the sub-register
18 //===----------------------------------------------------------------------===//
20 #define DEBUG_TYPE "ext-opt"
21 #include "llvm/CodeGen/Passes.h"
22 #include "llvm/CodeGen/MachineDominators.h"
23 #include "llvm/CodeGen/MachineInstrBuilder.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/Target/TargetInstrInfo.h"
26 #include "llvm/Target/TargetRegisterInfo.h"
27 #include "llvm/Support/CommandLine.h"
28 #include "llvm/ADT/SmallPtrSet.h"
29 #include "llvm/ADT/Statistic.h"
32 static cl::opt<bool> Aggressive("aggressive-ext-opt", cl::Hidden,
33 cl::desc("Aggressive extension optimization"));
35 STATISTIC(NumReuse, "Number of extension results reused");
38 class OptimizeExts : public MachineFunctionPass {
39 const TargetMachine *TM;
40 const TargetInstrInfo *TII;
41 MachineRegisterInfo *MRI;
42 MachineDominatorTree *DT; // Machine dominator tree
45 static char ID; // Pass identification
46 OptimizeExts() : MachineFunctionPass(&ID) {}
48 virtual bool runOnMachineFunction(MachineFunction &MF);
50 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
52 MachineFunctionPass::getAnalysisUsage(AU);
54 AU.addRequired<MachineDominatorTree>();
55 AU.addPreserved<MachineDominatorTree>();
60 bool OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB,
61 SmallPtrSet<MachineInstr*, 8> &LocalMIs);
65 char OptimizeExts::ID = 0;
66 INITIALIZE_PASS(OptimizeExts, "opt-exts",
67 "Optimize sign / zero extensions", false, false);
69 FunctionPass *llvm::createOptimizeExtsPass() { return new OptimizeExts(); }
71 /// OptimizeInstr - If instruction is a copy-like instruction, i.e. it reads
72 /// a single register and writes a single register and it does not modify
73 /// the source, and if the source value is preserved as a sub-register of
74 /// the result, then replace all reachable uses of the source with the subreg
76 /// Do not generate an EXTRACT that is used only in a debug use, as this
77 /// changes the code. Since this code does not currently share EXTRACTs, just
78 /// ignore all debug uses.
79 bool OptimizeExts::OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB,
80 SmallPtrSet<MachineInstr*, 8> &LocalMIs) {
83 unsigned SrcReg, DstReg, SubIdx;
84 if (!TII->isCoalescableExtInstr(*MI, SrcReg, DstReg, SubIdx))
87 if (TargetRegisterInfo::isPhysicalRegister(DstReg) ||
88 TargetRegisterInfo::isPhysicalRegister(SrcReg))
91 MachineRegisterInfo::use_nodbg_iterator UI = MRI->use_nodbg_begin(SrcReg);
92 if (++UI == MRI->use_nodbg_end())
96 // Ok, the source has other uses. See if we can replace the other uses
97 // with use of the result of the extension.
98 SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs;
99 UI = MRI->use_nodbg_begin(DstReg);
100 for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end();
102 ReachedBBs.insert(UI->getParent());
104 bool ExtendLife = true;
105 // Uses that are in the same BB of uses of the result of the instruction.
106 SmallVector<MachineOperand*, 8> Uses;
107 // Uses that the result of the instruction can reach.
108 SmallVector<MachineOperand*, 8> ExtendedUses;
110 UI = MRI->use_nodbg_begin(SrcReg);
111 for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end();
113 MachineOperand &UseMO = UI.getOperand();
114 MachineInstr *UseMI = &*UI;
117 if (UseMI->isPHI()) {
122 // It's an error to translate this:
124 // %reg1025 = <sext> %reg1024
126 // %reg1026 = SUBREG_TO_REG 0, %reg1024, 4
130 // %reg1025 = <sext> %reg1024
132 // %reg1027 = COPY %reg1025:4
133 // %reg1026 = SUBREG_TO_REG 0, %reg1027, 4
135 // The problem here is that SUBREG_TO_REG is there to assert that an
136 // implicit zext occurs. It doesn't insert a zext instruction. If we allow
137 // the COPY here, it will give us the value after the <sext>, not the
138 // original value of %reg1024 before <sext>.
139 if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG)
142 MachineBasicBlock *UseMBB = UseMI->getParent();
144 // Local uses that come after the extension.
145 if (!LocalMIs.count(UseMI))
146 Uses.push_back(&UseMO);
147 } else if (ReachedBBs.count(UseMBB))
148 // Non-local uses where the result of extension is used. Always replace
149 // these unless it's a PHI.
150 Uses.push_back(&UseMO);
151 else if (Aggressive && DT->dominates(MBB, UseMBB))
152 // We may want to extend live range of the extension result in order to
153 // replace these uses.
154 ExtendedUses.push_back(&UseMO);
156 // Both will be live out of the def MBB anyway. Don't extend live range of
157 // the extension result.
163 if (ExtendLife && !ExtendedUses.empty())
164 // Ok, we'll extend the liveness of the extension result.
165 std::copy(ExtendedUses.begin(), ExtendedUses.end(),
166 std::back_inserter(Uses));
168 // Now replace all uses.
169 bool Changed = false;
171 SmallPtrSet<MachineBasicBlock*, 4> PHIBBs;
172 // Look for PHI uses of the extended result, we don't want to extend the
173 // liveness of a PHI input. It breaks all kinds of assumptions down
174 // stream. A PHI use is expected to be the kill of its source values.
175 UI = MRI->use_nodbg_begin(DstReg);
176 for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end();
179 PHIBBs.insert(UI->getParent());
181 const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
182 for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
183 MachineOperand *UseMO = Uses[i];
184 MachineInstr *UseMI = UseMO->getParent();
185 MachineBasicBlock *UseMBB = UseMI->getParent();
186 if (PHIBBs.count(UseMBB))
188 unsigned NewVR = MRI->createVirtualRegister(RC);
189 BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(),
190 TII->get(TargetOpcode::COPY), NewVR)
191 .addReg(DstReg, 0, SubIdx);
192 UseMO->setReg(NewVR);
201 bool OptimizeExts::runOnMachineFunction(MachineFunction &MF) {
202 TM = &MF.getTarget();
203 TII = TM->getInstrInfo();
204 MRI = &MF.getRegInfo();
205 DT = Aggressive ? &getAnalysis<MachineDominatorTree>() : 0;
207 bool Changed = false;
209 SmallPtrSet<MachineInstr*, 8> LocalMIs;
210 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
211 MachineBasicBlock *MBB = &*I;
213 for (MachineBasicBlock::iterator MII = I->begin(), ME = I->end(); MII != ME;
215 MachineInstr *MI = &*MII;
216 Changed |= OptimizeInstr(MI, MBB, LocalMIs);