1 //===-------------- RISCVSExtWRemoval.cpp - MI sext.w Removal -------------===//
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 removes unneeded sext.w instructions at the MI level.
10 //
11 //===---------------------------------------------------------------------===//
12 
13 #include "RISCV.h"
14 #include "RISCVSubtarget.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/CodeGen/MachineFunctionPass.h"
17 #include "llvm/CodeGen/TargetInstrInfo.h"
18 
19 using namespace llvm;
20 
21 #define DEBUG_TYPE "riscv-sextw-removal"
22 
23 STATISTIC(NumRemovedSExtW, "Number of removed sign-extensions");
24 
25 static cl::opt<bool> DisableSExtWRemoval("riscv-disable-sextw-removal",
26                                          cl::desc("Disable removal of sext.w"),
27                                          cl::init(false), cl::Hidden);
28 namespace {
29 
30 class RISCVSExtWRemoval : public MachineFunctionPass {
31 public:
32   static char ID;
33 
34   RISCVSExtWRemoval() : MachineFunctionPass(ID) {
35     initializeRISCVSExtWRemovalPass(*PassRegistry::getPassRegistry());
36   }
37 
38   bool runOnMachineFunction(MachineFunction &MF) override;
39 
40   void getAnalysisUsage(AnalysisUsage &AU) const override {
41     AU.setPreservesCFG();
42     MachineFunctionPass::getAnalysisUsage(AU);
43   }
44 
45   StringRef getPassName() const override { return "RISCV sext.w Removal"; }
46 };
47 
48 } // end anonymous namespace
49 
50 char RISCVSExtWRemoval::ID = 0;
51 INITIALIZE_PASS(RISCVSExtWRemoval, DEBUG_TYPE, "RISCV sext.w Removal", false,
52                 false)
53 
54 FunctionPass *llvm::createRISCVSExtWRemovalPass() {
55   return new RISCVSExtWRemoval();
56 }
57 
58 // This function returns true if the machine instruction always outputs a value
59 // where bits 63:32 match bit 31.
60 // TODO: Allocate a bit in TSFlags for the W instructions?
61 // TODO: Add other W instructions.
62 static bool isSignExtendingOpW(const MachineInstr &MI) {
63   switch (MI.getOpcode()) {
64   case RISCV::LUI:
65   case RISCV::LW:
66   case RISCV::ADDW:
67   case RISCV::ADDIW:
68   case RISCV::SUBW:
69   case RISCV::MULW:
70   case RISCV::SLLW:
71   case RISCV::SLLIW:
72   case RISCV::SRAW:
73   case RISCV::SRAIW:
74   case RISCV::SRLW:
75   case RISCV::SRLIW:
76   case RISCV::DIVW:
77   case RISCV::DIVUW:
78   case RISCV::REMW:
79   case RISCV::REMUW:
80   case RISCV::ROLW:
81   case RISCV::RORW:
82   case RISCV::RORIW:
83   case RISCV::CLZW:
84   case RISCV::CTZW:
85   case RISCV::CPOPW:
86   case RISCV::FCVT_W_H:
87   case RISCV::FCVT_WU_H:
88   case RISCV::FCVT_W_S:
89   case RISCV::FCVT_WU_S:
90   case RISCV::FCVT_W_D:
91   case RISCV::FCVT_WU_D:
92   case RISCV::FMV_X_W:
93   // The following aren't W instructions, but are either sign extended from a
94   // smaller size, always outputs a small integer, or put zeros in bits 63:31.
95   case RISCV::LBU:
96   case RISCV::LHU:
97   case RISCV::LB:
98   case RISCV::LH:
99   case RISCV::SLT:
100   case RISCV::SLTI:
101   case RISCV::SLTU:
102   case RISCV::SLTIU:
103   case RISCV::SEXT_B:
104   case RISCV::SEXT_H:
105   case RISCV::ZEXT_H_RV64:
106   case RISCV::FMV_X_H:
107   case RISCV::BEXT:
108   case RISCV::BEXTI:
109   case RISCV::CLZ:
110   case RISCV::CPOP:
111   case RISCV::CTZ:
112     return true;
113   // shifting right sufficiently makes the value 32-bit sign-extended
114   case RISCV::SRAI:
115     return MI.getOperand(2).getImm() >= 32;
116   case RISCV::SRLI:
117     return MI.getOperand(2).getImm() > 32;
118   // The LI pattern ADDI rd, X0, imm is sign extended.
119   case RISCV::ADDI:
120     return MI.getOperand(1).isReg() && MI.getOperand(1).getReg() == RISCV::X0;
121   // An ANDI with an 11 bit immediate will zero bits 63:11.
122   case RISCV::ANDI:
123     return isUInt<11>(MI.getOperand(2).getImm());
124   // An ORI with an >11 bit immediate (negative 12-bit) will set bits 63:11.
125   case RISCV::ORI:
126     return !isUInt<11>(MI.getOperand(2).getImm());
127   // Copying from X0 produces zero.
128   case RISCV::COPY:
129     return MI.getOperand(1).getReg() == RISCV::X0;
130   }
131 
132   return false;
133 }
134 
135 static bool isSignExtendedW(const MachineInstr &OrigMI,
136                             MachineRegisterInfo &MRI) {
137 
138   SmallPtrSet<const MachineInstr *, 4> Visited;
139   SmallVector<const MachineInstr *, 4> Worklist;
140 
141   Worklist.push_back(&OrigMI);
142 
143   while (!Worklist.empty()) {
144     const MachineInstr *MI = Worklist.pop_back_val();
145 
146     // If we already visited this instruction, we don't need to check it again.
147     if (!Visited.insert(MI).second)
148       continue;
149 
150     // If this is a sign extending operation we don't need to look any further.
151     if (isSignExtendingOpW(*MI))
152       continue;
153 
154     // Is this an instruction that propagates sign extend.
155     switch (MI->getOpcode()) {
156     default:
157       // Unknown opcode, give up.
158       return false;
159     case RISCV::COPY: {
160       Register SrcReg = MI->getOperand(1).getReg();
161 
162       // TODO: Handle arguments and returns from calls?
163 
164       // If this is a copy from another register, check its source instruction.
165       if (!SrcReg.isVirtual())
166         return false;
167       const MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
168       if (!SrcMI)
169         return false;
170 
171       // Add SrcMI to the worklist.
172       Worklist.push_back(SrcMI);
173       break;
174     }
175 
176     // For these, we just need to check if the 1st operand is sign extended.
177     case RISCV::BCLRI:
178     case RISCV::BINVI:
179     case RISCV::BSETI:
180       if (MI->getOperand(2).getImm() >= 31)
181         return false;
182       LLVM_FALLTHROUGH;
183     case RISCV::REM:
184     case RISCV::ANDI:
185     case RISCV::ORI:
186     case RISCV::XORI: {
187       // |Remainder| is always <= |Dividend|. If D is 32-bit, then so is R.
188       // DIV doesn't work because of the edge case 0xf..f 8000 0000 / (long)-1
189       // Logical operations use a sign extended 12-bit immediate.
190       Register SrcReg = MI->getOperand(1).getReg();
191       if (!SrcReg.isVirtual())
192         return false;
193       const MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
194       if (!SrcMI)
195         return false;
196 
197       // Add SrcMI to the worklist.
198       Worklist.push_back(SrcMI);
199       break;
200     }
201     case RISCV::REMU:
202     case RISCV::AND:
203     case RISCV::OR:
204     case RISCV::XOR:
205     case RISCV::ANDN:
206     case RISCV::ORN:
207     case RISCV::XNOR:
208     case RISCV::MAX:
209     case RISCV::MAXU:
210     case RISCV::MIN:
211     case RISCV::MINU:
212     case RISCV::PHI: {
213       // If all incoming values are sign-extended, the output of AND, OR, XOR,
214       // MIN, MAX, or PHI is also sign-extended.
215 
216       // The input registers for PHI are operand 1, 3, ...
217       // The input registers for others are operand 1 and 2.
218       unsigned E = 3, D = 1;
219       if (MI->getOpcode() == RISCV::PHI) {
220         E = MI->getNumOperands();
221         D = 2;
222       }
223 
224       for (unsigned I = 1; I != E; I += D) {
225         if (!MI->getOperand(I).isReg())
226           return false;
227 
228         Register SrcReg = MI->getOperand(I).getReg();
229         if (!SrcReg.isVirtual())
230           return false;
231         const MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
232         if (!SrcMI)
233           return false;
234 
235         // Add SrcMI to the worklist.
236         Worklist.push_back(SrcMI);
237       }
238 
239       break;
240     }
241     }
242   }
243 
244   // If we get here, then every node we visited produces a sign extended value
245   // or propagated sign extended values. So the result must be sign extended.
246   return true;
247 }
248 
249 bool RISCVSExtWRemoval::runOnMachineFunction(MachineFunction &MF) {
250   if (skipFunction(MF.getFunction()) || DisableSExtWRemoval)
251     return false;
252 
253   MachineRegisterInfo &MRI = MF.getRegInfo();
254   const RISCVSubtarget &ST = MF.getSubtarget<RISCVSubtarget>();
255 
256   if (!ST.is64Bit())
257     return false;
258 
259   bool MadeChange = false;
260   for (MachineBasicBlock &MBB : MF) {
261     for (auto I = MBB.begin(), IE = MBB.end(); I != IE;) {
262       MachineInstr *MI = &*I++;
263 
264       // We're looking for the sext.w pattern ADDIW rd, rs1, 0.
265       if (MI->getOpcode() != RISCV::ADDIW || !MI->getOperand(2).isImm() ||
266           MI->getOperand(2).getImm() != 0 || !MI->getOperand(1).isReg())
267         continue;
268 
269       // Input should be a virtual register.
270       Register SrcReg = MI->getOperand(1).getReg();
271       if (!SrcReg.isVirtual())
272         continue;
273 
274       const MachineInstr &SrcMI = *MRI.getVRegDef(SrcReg);
275       if (!isSignExtendedW(SrcMI, MRI))
276         continue;
277 
278       Register DstReg = MI->getOperand(0).getReg();
279       if (!MRI.constrainRegClass(SrcReg, MRI.getRegClass(DstReg)))
280         continue;
281 
282       LLVM_DEBUG(dbgs() << "Removing redundant sign-extension\n");
283       MRI.replaceRegWith(DstReg, SrcReg);
284       MRI.clearKillFlags(SrcReg);
285       MI->eraseFromParent();
286       ++NumRemovedSExtW;
287       MadeChange = true;
288     }
289   }
290 
291   return MadeChange;
292 }
293