1 //==---- SystemZPostRewrite.cpp - Select pseudos after RegAlloc ---*- C++ -*-=//
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 file contains a pass that is run immediately after VirtRegRewriter
10 // but before MachineCopyPropagation. The purpose is to lower pseudos to
11 // target instructions before any later pass might substitute a register for
12 // another.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "SystemZ.h"
17 #include "SystemZInstrInfo.h"
18 #include "SystemZSubtarget.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/CodeGen/LivePhysRegs.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/MachineInstrBuilder.h"
23 using namespace llvm;
24 
25 #define DEBUG_TYPE "systemz-postrewrite"
26 STATISTIC(MemFoldCopies, "Number of copies inserted before folded mem ops.");
27 STATISTIC(LOCRMuxJumps, "Number of LOCRMux jump-sequences (lower is better)");
28 
29 namespace {
30 
31 class SystemZPostRewrite : public MachineFunctionPass {
32 public:
33   static char ID;
34   SystemZPostRewrite() : MachineFunctionPass(ID) {
35     initializeSystemZPostRewritePass(*PassRegistry::getPassRegistry());
36   }
37 
38   const SystemZInstrInfo *TII;
39 
40   bool runOnMachineFunction(MachineFunction &Fn) override;
41 
42 private:
43   void selectLOCRMux(MachineBasicBlock &MBB,
44                      MachineBasicBlock::iterator MBBI,
45                      MachineBasicBlock::iterator &NextMBBI,
46                      unsigned LowOpcode,
47                      unsigned HighOpcode);
48   void selectSELRMux(MachineBasicBlock &MBB,
49                      MachineBasicBlock::iterator MBBI,
50                      MachineBasicBlock::iterator &NextMBBI,
51                      unsigned LowOpcode,
52                      unsigned HighOpcode);
53   bool expandCondMove(MachineBasicBlock &MBB,
54                       MachineBasicBlock::iterator MBBI,
55                       MachineBasicBlock::iterator &NextMBBI);
56   bool selectMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
57                 MachineBasicBlock::iterator &NextMBBI);
58   bool selectMBB(MachineBasicBlock &MBB);
59 };
60 
61 char SystemZPostRewrite::ID = 0;
62 
63 } // end anonymous namespace
64 
65 INITIALIZE_PASS(SystemZPostRewrite, "systemz-post-rewrite",
66                 "SystemZ Post Rewrite pass", false, false)
67 
68 /// Returns an instance of the Post Rewrite pass.
69 FunctionPass *llvm::createSystemZPostRewritePass(SystemZTargetMachine &TM) {
70   return new SystemZPostRewrite();
71 }
72 
73 // MI is a load-register-on-condition pseudo instruction.  Replace it with
74 // LowOpcode if source and destination are both low GR32s and HighOpcode if
75 // source and destination are both high GR32s. Otherwise, a branch sequence
76 // is created.
77 void SystemZPostRewrite::selectLOCRMux(MachineBasicBlock &MBB,
78                                        MachineBasicBlock::iterator MBBI,
79                                        MachineBasicBlock::iterator &NextMBBI,
80                                        unsigned LowOpcode,
81                                        unsigned HighOpcode) {
82   Register DestReg = MBBI->getOperand(0).getReg();
83   Register SrcReg = MBBI->getOperand(2).getReg();
84   bool DestIsHigh = SystemZ::isHighReg(DestReg);
85   bool SrcIsHigh = SystemZ::isHighReg(SrcReg);
86 
87   if (!DestIsHigh && !SrcIsHigh)
88     MBBI->setDesc(TII->get(LowOpcode));
89   else if (DestIsHigh && SrcIsHigh)
90     MBBI->setDesc(TII->get(HighOpcode));
91   else
92     expandCondMove(MBB, MBBI, NextMBBI);
93 }
94 
95 // MI is a select pseudo instruction.  Replace it with LowOpcode if source
96 // and destination are all low GR32s and HighOpcode if source and destination
97 // are all high GR32s. Otherwise, a branch sequence is created.
98 void SystemZPostRewrite::selectSELRMux(MachineBasicBlock &MBB,
99                                        MachineBasicBlock::iterator MBBI,
100                                        MachineBasicBlock::iterator &NextMBBI,
101                                        unsigned LowOpcode,
102                                        unsigned HighOpcode) {
103   Register DestReg = MBBI->getOperand(0).getReg();
104   Register Src1Reg = MBBI->getOperand(1).getReg();
105   Register Src2Reg = MBBI->getOperand(2).getReg();
106   bool DestIsHigh = SystemZ::isHighReg(DestReg);
107   bool Src1IsHigh = SystemZ::isHighReg(Src1Reg);
108   bool Src2IsHigh = SystemZ::isHighReg(Src2Reg);
109 
110   // If sources and destination aren't all high or all low, we may be able to
111   // simplify the operation by moving one of the sources to the destination
112   // first.  But only if this doesn't clobber the other source.
113   if (DestReg != Src1Reg && DestReg != Src2Reg) {
114     if (DestIsHigh != Src1IsHigh) {
115       BuildMI(*MBBI->getParent(), MBBI, MBBI->getDebugLoc(),
116               TII->get(SystemZ::COPY), DestReg)
117         .addReg(MBBI->getOperand(1).getReg(), getRegState(MBBI->getOperand(1)));
118       MBBI->getOperand(1).setReg(DestReg);
119       Src1Reg = DestReg;
120       Src1IsHigh = DestIsHigh;
121     } else if (DestIsHigh != Src2IsHigh) {
122       BuildMI(*MBBI->getParent(), MBBI, MBBI->getDebugLoc(),
123               TII->get(SystemZ::COPY), DestReg)
124         .addReg(MBBI->getOperand(2).getReg(), getRegState(MBBI->getOperand(2)));
125       MBBI->getOperand(2).setReg(DestReg);
126       Src2Reg = DestReg;
127       Src2IsHigh = DestIsHigh;
128     }
129   }
130 
131   // If the destination (now) matches one source, prefer this to be first.
132   if (DestReg != Src1Reg && DestReg == Src2Reg) {
133     TII->commuteInstruction(*MBBI, false, 1, 2);
134     std::swap(Src1Reg, Src2Reg);
135     std::swap(Src1IsHigh, Src2IsHigh);
136   }
137 
138   if (!DestIsHigh && !Src1IsHigh && !Src2IsHigh)
139     MBBI->setDesc(TII->get(LowOpcode));
140   else if (DestIsHigh && Src1IsHigh && Src2IsHigh)
141     MBBI->setDesc(TII->get(HighOpcode));
142   else
143     // Given the simplification above, we must already have a two-operand case.
144     expandCondMove(MBB, MBBI, NextMBBI);
145 }
146 
147 // Replace MBBI by a branch sequence that performs a conditional move of
148 // operand 2 to the destination register. Operand 1 is expected to be the
149 // same register as the destination.
150 bool SystemZPostRewrite::expandCondMove(MachineBasicBlock &MBB,
151                                         MachineBasicBlock::iterator MBBI,
152                                         MachineBasicBlock::iterator &NextMBBI) {
153   MachineFunction &MF = *MBB.getParent();
154   const BasicBlock *BB = MBB.getBasicBlock();
155   MachineInstr &MI = *MBBI;
156   DebugLoc DL = MI.getDebugLoc();
157   Register DestReg = MI.getOperand(0).getReg();
158   Register SrcReg = MI.getOperand(2).getReg();
159   unsigned CCValid = MI.getOperand(3).getImm();
160   unsigned CCMask = MI.getOperand(4).getImm();
161   assert(DestReg == MI.getOperand(1).getReg() &&
162          "Expected destination and first source operand to be the same.");
163 
164   LivePhysRegs LiveRegs(TII->getRegisterInfo());
165   LiveRegs.addLiveOuts(MBB);
166   for (auto I = std::prev(MBB.end()); I != MBBI; --I)
167     LiveRegs.stepBackward(*I);
168 
169   // Splice MBB at MI, moving the rest of the block into RestMBB.
170   MachineBasicBlock *RestMBB = MF.CreateMachineBasicBlock(BB);
171   MF.insert(std::next(MachineFunction::iterator(MBB)), RestMBB);
172   RestMBB->splice(RestMBB->begin(), &MBB, MI, MBB.end());
173   RestMBB->transferSuccessors(&MBB);
174   for (MCPhysReg R : LiveRegs)
175     RestMBB->addLiveIn(R);
176 
177   // Create a new block MoveMBB to hold the move instruction.
178   MachineBasicBlock *MoveMBB = MF.CreateMachineBasicBlock(BB);
179   MF.insert(std::next(MachineFunction::iterator(MBB)), MoveMBB);
180   MoveMBB->addLiveIn(SrcReg);
181   for (MCPhysReg R : LiveRegs)
182     MoveMBB->addLiveIn(R);
183 
184   // At the end of MBB, create a conditional branch to RestMBB if the
185   // condition is false, otherwise fall through to MoveMBB.
186   BuildMI(&MBB, DL, TII->get(SystemZ::BRC))
187     .addImm(CCValid).addImm(CCMask ^ CCValid).addMBB(RestMBB);
188   MBB.addSuccessor(RestMBB);
189   MBB.addSuccessor(MoveMBB);
190 
191   // In MoveMBB, emit an instruction to move SrcReg into DestReg,
192   // then fall through to RestMBB.
193   BuildMI(*MoveMBB, MoveMBB->end(), DL, TII->get(SystemZ::COPY), DestReg)
194       .addReg(MI.getOperand(2).getReg(), getRegState(MI.getOperand(2)));
195   MoveMBB->addSuccessor(RestMBB);
196 
197   NextMBBI = MBB.end();
198   MI.eraseFromParent();
199   LOCRMuxJumps++;
200   return true;
201 }
202 
203 /// If MBBI references a pseudo instruction that should be selected here,
204 /// do it and return true.  Otherwise return false.
205 bool SystemZPostRewrite::selectMI(MachineBasicBlock &MBB,
206                                   MachineBasicBlock::iterator MBBI,
207                                   MachineBasicBlock::iterator &NextMBBI) {
208   MachineInstr &MI = *MBBI;
209   unsigned Opcode = MI.getOpcode();
210 
211   // Note: If this could be done during regalloc in foldMemoryOperandImpl()
212   // while also updating the LiveIntervals, there would be no need for the
213   // MemFoldPseudo to begin with.
214   int TargetMemOpcode = SystemZ::getTargetMemOpcode(Opcode);
215   if (TargetMemOpcode != -1) {
216     MI.setDesc(TII->get(TargetMemOpcode));
217     MI.tieOperands(0, 1);
218     Register DstReg = MI.getOperand(0).getReg();
219     MachineOperand &SrcMO = MI.getOperand(1);
220     if (DstReg != SrcMO.getReg()) {
221       BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(SystemZ::COPY), DstReg)
222         .addReg(SrcMO.getReg());
223       SrcMO.setReg(DstReg);
224       MemFoldCopies++;
225     }
226     return true;
227   }
228 
229   switch (Opcode) {
230   case SystemZ::LOCRMux:
231     selectLOCRMux(MBB, MBBI, NextMBBI, SystemZ::LOCR, SystemZ::LOCFHR);
232     return true;
233   case SystemZ::SELRMux:
234     selectSELRMux(MBB, MBBI, NextMBBI, SystemZ::SELR, SystemZ::SELFHR);
235     return true;
236   }
237 
238   return false;
239 }
240 
241 /// Iterate over the instructions in basic block MBB and select any
242 /// pseudo instructions.  Return true if anything was modified.
243 bool SystemZPostRewrite::selectMBB(MachineBasicBlock &MBB) {
244   bool Modified = false;
245 
246   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
247   while (MBBI != E) {
248     MachineBasicBlock::iterator NMBBI = std::next(MBBI);
249     Modified |= selectMI(MBB, MBBI, NMBBI);
250     MBBI = NMBBI;
251   }
252 
253   return Modified;
254 }
255 
256 bool SystemZPostRewrite::runOnMachineFunction(MachineFunction &MF) {
257   TII = MF.getSubtarget<SystemZSubtarget>().getInstrInfo();
258 
259   bool Modified = false;
260   for (auto &MBB : MF)
261     Modified |= selectMBB(MBB);
262 
263   return Modified;
264 }
265 
266