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