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