1//===-- AMDGPUIndirectAddressing.cpp - Indirect Adressing Support ---------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10/// \file
11///
12/// Instructions can use indirect addressing to index the register file as if it
13/// were memory.  This pass lowers RegisterLoad and RegisterStore instructions
14/// to either a COPY or a MOV that uses indirect addressing.
15//
16//===----------------------------------------------------------------------===//
17
18#include "AMDGPU.h"
19#include "R600InstrInfo.h"
20#include "R600MachineFunctionInfo.h"
21#include "llvm/CodeGen/MachineFunction.h"
22#include "llvm/CodeGen/MachineFunctionPass.h"
23#include "llvm/CodeGen/MachineInstrBuilder.h"
24#include "llvm/CodeGen/MachineRegisterInfo.h"
25#include "llvm/Support/Debug.h"
26
27using namespace llvm;
28
29namespace {
30
31class AMDGPUIndirectAddressingPass : public MachineFunctionPass {
32
33private:
34  static char ID;
35  const AMDGPUInstrInfo *TII;
36
37  bool regHasExplicitDef(MachineRegisterInfo &MRI, unsigned Reg) const;
38
39public:
40  AMDGPUIndirectAddressingPass(TargetMachine &tm) :
41    MachineFunctionPass(ID),
42    TII(0)
43    { }
44
45  virtual bool runOnMachineFunction(MachineFunction &MF);
46
47  const char *getPassName() const { return "R600 Handle indirect addressing"; }
48
49};
50
51} // End anonymous namespace
52
53char AMDGPUIndirectAddressingPass::ID = 0;
54
55FunctionPass *llvm::createAMDGPUIndirectAddressingPass(TargetMachine &tm) {
56  return new AMDGPUIndirectAddressingPass(tm);
57}
58
59bool AMDGPUIndirectAddressingPass::runOnMachineFunction(MachineFunction &MF) {
60  MachineRegisterInfo &MRI = MF.getRegInfo();
61
62  TII = static_cast<const AMDGPUInstrInfo*>(MF.getTarget().getInstrInfo());
63
64  int IndirectBegin = TII->getIndirectIndexBegin(MF);
65  int IndirectEnd = TII->getIndirectIndexEnd(MF);
66
67  if (IndirectBegin == -1) {
68    // No indirect addressing, we can skip this pass
69    assert(IndirectEnd == -1);
70    return false;
71  }
72
73  // The map keeps track of the indirect address that is represented by
74  // each virtual register. The key is the register and the value is the
75  // indirect address it uses.
76  std::map<unsigned, unsigned> RegisterAddressMap;
77
78  // First pass - Lower all of the RegisterStore instructions and track which
79  // registers are live.
80  for (MachineFunction::iterator BB = MF.begin(), BB_E = MF.end();
81                                                      BB != BB_E; ++BB) {
82    // This map keeps track of the current live indirect registers.
83    // The key is the address and the value is the register
84    std::map<unsigned, unsigned> LiveAddressRegisterMap;
85    MachineBasicBlock &MBB = *BB;
86
87    for (MachineBasicBlock::iterator I = MBB.begin(), Next = llvm::next(I);
88                               I != MBB.end(); I = Next) {
89      Next = llvm::next(I);
90      MachineInstr &MI = *I;
91
92      if (!TII->isRegisterStore(MI)) {
93        continue;
94      }
95
96      // Lower RegisterStore
97
98      unsigned RegIndex = MI.getOperand(2).getImm();
99      unsigned Channel = MI.getOperand(3).getImm();
100      unsigned Address = TII->calculateIndirectAddress(RegIndex, Channel);
101      const TargetRegisterClass *IndirectStoreRegClass =
102                   TII->getIndirectAddrStoreRegClass(MI.getOperand(0).getReg());
103
104      if (MI.getOperand(1).getReg() == AMDGPU::INDIRECT_BASE_ADDR) {
105        // Direct register access.
106        unsigned DstReg = MRI.createVirtualRegister(IndirectStoreRegClass);
107
108        BuildMI(MBB, I, MBB.findDebugLoc(I), TII->get(AMDGPU::COPY), DstReg)
109                .addOperand(MI.getOperand(0));
110
111        RegisterAddressMap[DstReg] = Address;
112        LiveAddressRegisterMap[Address] = DstReg;
113      } else {
114        // Indirect register access.
115        MachineInstrBuilder MOV = TII->buildIndirectWrite(BB, I,
116                                           MI.getOperand(0).getReg(), // Value
117                                           Address,
118                                           MI.getOperand(1).getReg()); // Offset
119        for (int i = IndirectBegin; i <= IndirectEnd; ++i) {
120          unsigned Addr = TII->calculateIndirectAddress(i, Channel);
121          unsigned DstReg = MRI.createVirtualRegister(IndirectStoreRegClass);
122          MOV.addReg(DstReg, RegState::Define | RegState::Implicit);
123          RegisterAddressMap[DstReg] = Addr;
124          LiveAddressRegisterMap[Addr] = DstReg;
125        }
126      }
127      MI.eraseFromParent();
128    }
129
130    // Update the live-ins of the succesor blocks
131    for (MachineBasicBlock::succ_iterator Succ = MBB.succ_begin(),
132                                          SuccEnd = MBB.succ_end();
133                                          SuccEnd != Succ; ++Succ) {
134      std::map<unsigned, unsigned>::const_iterator Key, KeyEnd;
135      for (Key = LiveAddressRegisterMap.begin(),
136           KeyEnd = LiveAddressRegisterMap.end(); KeyEnd != Key; ++Key) {
137        (*Succ)->addLiveIn(Key->second);
138      }
139    }
140  }
141
142  // Second pass - Lower the RegisterLoad instructions
143  for (MachineFunction::iterator BB = MF.begin(), BB_E = MF.end();
144                                                      BB != BB_E; ++BB) {
145    // Key is the address and the value is the register
146    std::map<unsigned, unsigned> LiveAddressRegisterMap;
147    MachineBasicBlock &MBB = *BB;
148
149    MachineBasicBlock::livein_iterator LI = MBB.livein_begin();
150    while (LI != MBB.livein_end()) {
151      std::vector<unsigned> PhiRegisters;
152
153      // Make sure this live in is used for indirect addressing
154      if (RegisterAddressMap.find(*LI) == RegisterAddressMap.end()) {
155        ++LI;
156        continue;
157      }
158
159      unsigned Address = RegisterAddressMap[*LI];
160      LiveAddressRegisterMap[Address] = *LI;
161      PhiRegisters.push_back(*LI);
162
163      // Check if there are other live in registers which map to the same
164      // indirect address.
165      for (MachineBasicBlock::livein_iterator LJ = llvm::next(LI),
166                                              LE = MBB.livein_end();
167                                              LJ != LE; ++LJ) {
168        unsigned Reg = *LJ;
169        if (RegisterAddressMap.find(Reg) == RegisterAddressMap.end()) {
170          continue;
171        }
172
173        if (RegisterAddressMap[Reg] == Address) {
174          PhiRegisters.push_back(Reg);
175        }
176      }
177
178      if (PhiRegisters.size() == 1) {
179        // We don't need to insert a Phi instruction, so we can just add the
180        // registers to the live list for the block.
181        LiveAddressRegisterMap[Address] = *LI;
182        MBB.removeLiveIn(*LI);
183      } else {
184        // We need to insert a PHI, because we have the same address being
185        // written in multiple predecessor blocks.
186        const TargetRegisterClass *PhiDstClass =
187                   TII->getIndirectAddrStoreRegClass(*(PhiRegisters.begin()));
188        unsigned PhiDstReg = MRI.createVirtualRegister(PhiDstClass);
189        MachineInstrBuilder Phi = BuildMI(MBB, MBB.begin(),
190                                          MBB.findDebugLoc(MBB.begin()),
191                                          TII->get(AMDGPU::PHI), PhiDstReg);
192
193        for (std::vector<unsigned>::const_iterator RI = PhiRegisters.begin(),
194                                                   RE = PhiRegisters.end();
195                                                   RI != RE; ++RI) {
196          unsigned Reg = *RI;
197          MachineInstr *DefInst = MRI.getVRegDef(Reg);
198          assert(DefInst);
199          MachineBasicBlock *RegBlock = DefInst->getParent();
200          Phi.addReg(Reg);
201          Phi.addMBB(RegBlock);
202          MBB.removeLiveIn(Reg);
203        }
204        RegisterAddressMap[PhiDstReg] = Address;
205        LiveAddressRegisterMap[Address] = PhiDstReg;
206      }
207      LI = MBB.livein_begin();
208    }
209
210    for (MachineBasicBlock::iterator I = MBB.begin(), Next = llvm::next(I);
211                               I != MBB.end(); I = Next) {
212      Next = llvm::next(I);
213      MachineInstr &MI = *I;
214
215      if (!TII->isRegisterLoad(MI)) {
216        if (MI.getOpcode() == AMDGPU::PHI) {
217          continue;
218        }
219        // Check for indirect register defs
220        for (unsigned OpIdx = 0, NumOperands = MI.getNumOperands();
221                                 OpIdx < NumOperands; ++OpIdx) {
222          MachineOperand &MO = MI.getOperand(OpIdx);
223          if (MO.isReg() && MO.isDef() &&
224              RegisterAddressMap.find(MO.getReg()) != RegisterAddressMap.end()) {
225            unsigned Reg = MO.getReg();
226            unsigned LiveAddress = RegisterAddressMap[Reg];
227            // Chain the live-ins
228            if (LiveAddressRegisterMap.find(LiveAddress) !=
229                LiveAddressRegisterMap.end()) {
230              MI.addOperand(MachineOperand::CreateReg(
231                                  LiveAddressRegisterMap[LiveAddress],
232                                  false, // isDef
233                                  true,  // isImp
234                                  true));  // isKill
235            }
236            LiveAddressRegisterMap[LiveAddress] = Reg;
237          }
238        }
239        continue;
240      }
241
242      const TargetRegisterClass *SuperIndirectRegClass =
243                                                TII->getSuperIndirectRegClass();
244      const TargetRegisterClass *IndirectLoadRegClass =
245                                             TII->getIndirectAddrLoadRegClass();
246      unsigned IndirectReg = MRI.createVirtualRegister(SuperIndirectRegClass);
247
248      unsigned RegIndex = MI.getOperand(2).getImm();
249      unsigned Channel = MI.getOperand(3).getImm();
250      unsigned Address = TII->calculateIndirectAddress(RegIndex, Channel);
251
252      if (MI.getOperand(1).getReg() == AMDGPU::INDIRECT_BASE_ADDR) {
253        // Direct register access
254        unsigned Reg = LiveAddressRegisterMap[Address];
255        unsigned AddrReg = IndirectLoadRegClass->getRegister(Address);
256
257        if (regHasExplicitDef(MRI, Reg)) {
258          // If the register we are reading from has an explicit def, then that
259          // means it was written via a direct register access (i.e. COPY
260          // or other instruction that doesn't use indirect addressing).  In
261          // this case we know where the value has been stored, so we can just
262          // issue a copy.
263          BuildMI(MBB, I, MBB.findDebugLoc(I), TII->get(AMDGPU::COPY),
264                  MI.getOperand(0).getReg())
265                  .addReg(Reg);
266        } else {
267          // If the register we are reading has an implicit def, then that
268          // means it was written by an indirect register access (i.e. An
269          // instruction that uses indirect addressing.
270          BuildMI(MBB, I, MBB.findDebugLoc(I), TII->get(AMDGPU::COPY),
271                   MI.getOperand(0).getReg())
272                   .addReg(AddrReg)
273                   .addReg(Reg, RegState::Implicit);
274        }
275      } else {
276        // Indirect register access
277
278        // Note on REQ_SEQUENCE instructons: You can't actually use the register
279        // it defines unless  you have an instruction that takes the defined
280        // register class as an operand.
281
282        MachineInstrBuilder Sequence = BuildMI(MBB, I, MBB.findDebugLoc(I),
283                                               TII->get(AMDGPU::REG_SEQUENCE),
284                                               IndirectReg);
285        for (int i = IndirectBegin; i <= IndirectEnd; ++i) {
286          unsigned Addr = TII->calculateIndirectAddress(i, Channel);
287          if (LiveAddressRegisterMap.find(Addr) == LiveAddressRegisterMap.end()) {
288            continue;
289          }
290          unsigned Reg = LiveAddressRegisterMap[Addr];
291
292          // We only need to use REG_SEQUENCE for explicit defs, since the
293          // register coalescer won't do anything with the implicit defs.
294          if (!regHasExplicitDef(MRI, Reg)) {
295            continue;
296          }
297
298          // Insert a REQ_SEQUENCE instruction to force the register allocator
299          // to allocate the virtual register to the correct physical register.
300          Sequence.addReg(LiveAddressRegisterMap[Addr]);
301          Sequence.addImm(TII->getRegisterInfo().getIndirectSubReg(Addr));
302        }
303        MachineInstrBuilder Mov = TII->buildIndirectRead(BB, I,
304                                           MI.getOperand(0).getReg(), // Value
305                                           Address,
306                                           MI.getOperand(1).getReg()); // Offset
307
308
309
310        Mov.addReg(IndirectReg, RegState::Implicit | RegState::Kill);
311        Mov.addReg(LiveAddressRegisterMap[Address], RegState::Implicit);
312
313      }
314      MI.eraseFromParent();
315    }
316  }
317  return false;
318}
319
320bool AMDGPUIndirectAddressingPass::regHasExplicitDef(MachineRegisterInfo &MRI,
321                                                  unsigned Reg) const {
322  MachineInstr *DefInstr = MRI.getVRegDef(Reg);
323
324  if (!DefInstr) {
325    return false;
326  }
327
328  if (DefInstr->getOpcode() == AMDGPU::PHI) {
329    bool Explicit = false;
330    for (MachineInstr::const_mop_iterator I = DefInstr->operands_begin(),
331                                          E = DefInstr->operands_end();
332                                          I != E; ++I) {
333      const MachineOperand &MO = *I;
334      if (!MO.isReg() || MO.isDef()) {
335        continue;
336      }
337
338      Explicit = Explicit || regHasExplicitDef(MRI, MO.getReg());
339    }
340    return Explicit;
341  }
342
343  return DefInstr->getOperand(0).isReg() &&
344         DefInstr->getOperand(0).getReg() == Reg;
345}
346