1//===-- SIFixSGPRLiveRanges.cpp - Fix SGPR live ranges ----------------------===//
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/// SALU instructions ignore control flow, so we need to modify the live ranges
12/// of the registers they define in some cases.
13///
14/// The main case we need to handle is when a def is used in one side of a
15/// branch and not another.  For example:
16///
17/// %def
18/// IF
19///   ...
20///   ...
21/// ELSE
22///   %use
23///   ...
24/// ENDIF
25///
26/// Here we need the register allocator to avoid assigning any of the defs
27/// inside of the IF to the same register as %def.  In traditional live
28/// interval analysis %def is not live inside the IF branch, however, since
29/// SALU instructions inside of IF will be executed even if the branch is not
30/// taken, there is the chance that one of the instructions will overwrite the
31/// value of %def, so the use in ELSE will see the wrong value.
32///
33/// The strategy we use for solving this is to add an extra use after the ENDIF:
34///
35/// %def
36/// IF
37///   ...
38///   ...
39/// ELSE
40///   %use
41///   ...
42/// ENDIF
43/// %use
44///
45/// Adding this use will make the def live thoughout the IF branch, which is
46/// what we want.
47
48#include "AMDGPU.h"
49#include "SIInstrInfo.h"
50#include "SIRegisterInfo.h"
51#include "llvm/CodeGen/LiveIntervalAnalysis.h"
52#include "llvm/CodeGen/MachineFunctionPass.h"
53#include "llvm/CodeGen/MachineInstrBuilder.h"
54#include "llvm/CodeGen/MachinePostDominators.h"
55#include "llvm/CodeGen/MachineRegisterInfo.h"
56#include "llvm/Support/Debug.h"
57#include "llvm/Support/raw_ostream.h"
58#include "llvm/Target/TargetMachine.h"
59
60using namespace llvm;
61
62#define DEBUG_TYPE "si-fix-sgpr-live-ranges"
63
64namespace {
65
66class SIFixSGPRLiveRanges : public MachineFunctionPass {
67public:
68  static char ID;
69
70public:
71  SIFixSGPRLiveRanges() : MachineFunctionPass(ID) {
72    initializeSIFixSGPRLiveRangesPass(*PassRegistry::getPassRegistry());
73  }
74
75  bool runOnMachineFunction(MachineFunction &MF) override;
76
77  const char *getPassName() const override {
78    return "SI Fix SGPR live ranges";
79  }
80
81  void getAnalysisUsage(AnalysisUsage &AU) const override {
82    AU.addRequired<LiveIntervals>();
83    AU.addRequired<MachinePostDominatorTree>();
84    AU.setPreservesCFG();
85    MachineFunctionPass::getAnalysisUsage(AU);
86  }
87};
88
89} // End anonymous namespace.
90
91INITIALIZE_PASS_BEGIN(SIFixSGPRLiveRanges, DEBUG_TYPE,
92                      "SI Fix SGPR Live Ranges", false, false)
93INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
94INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
95INITIALIZE_PASS_END(SIFixSGPRLiveRanges, DEBUG_TYPE,
96                    "SI Fix SGPR Live Ranges", false, false)
97
98char SIFixSGPRLiveRanges::ID = 0;
99
100char &llvm::SIFixSGPRLiveRangesID = SIFixSGPRLiveRanges::ID;
101
102FunctionPass *llvm::createSIFixSGPRLiveRangesPass() {
103  return new SIFixSGPRLiveRanges();
104}
105
106bool SIFixSGPRLiveRanges::runOnMachineFunction(MachineFunction &MF) {
107  MachineRegisterInfo &MRI = MF.getRegInfo();
108  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
109  const SIRegisterInfo *TRI = static_cast<const SIRegisterInfo *>(
110      MF.getSubtarget().getRegisterInfo());
111  LiveIntervals *LIS = &getAnalysis<LiveIntervals>();
112 MachinePostDominatorTree *PDT = &getAnalysis<MachinePostDominatorTree>();
113  std::vector<std::pair<unsigned, LiveRange *>> SGPRLiveRanges;
114
115  // First pass, collect all live intervals for SGPRs
116  for (const MachineBasicBlock &MBB : MF) {
117    for (const MachineInstr &MI : MBB) {
118      for (const MachineOperand &MO : MI.defs()) {
119        if (MO.isImplicit())
120          continue;
121        unsigned Def = MO.getReg();
122        if (TargetRegisterInfo::isVirtualRegister(Def)) {
123          if (TRI->isSGPRClass(MRI.getRegClass(Def)))
124            SGPRLiveRanges.push_back(
125                std::make_pair(Def, &LIS->getInterval(Def)));
126        } else if (TRI->isSGPRClass(TRI->getPhysRegClass(Def))) {
127            SGPRLiveRanges.push_back(
128                std::make_pair(Def, &LIS->getRegUnit(Def)));
129        }
130      }
131    }
132  }
133
134  // Second pass fix the intervals
135  for (MachineFunction::iterator BI = MF.begin(), BE = MF.end();
136                                                  BI != BE; ++BI) {
137    MachineBasicBlock &MBB = *BI;
138    if (MBB.succ_size() < 2)
139      continue;
140
141    // We have structured control flow, so number of succesors should be two.
142    assert(MBB.succ_size() == 2);
143    MachineBasicBlock *SuccA = *MBB.succ_begin();
144    MachineBasicBlock *SuccB = *(++MBB.succ_begin());
145    MachineBasicBlock *NCD = PDT->findNearestCommonDominator(SuccA, SuccB);
146
147    if (!NCD)
148      continue;
149
150    MachineBasicBlock::iterator NCDTerm = NCD->getFirstTerminator();
151
152    if (NCDTerm != NCD->end() && NCDTerm->getOpcode() == AMDGPU::SI_ELSE) {
153      assert(NCD->succ_size() == 2);
154      // We want to make sure we insert the Use after the ENDIF, not after
155      // the ELSE.
156      NCD = PDT->findNearestCommonDominator(*NCD->succ_begin(),
157                                            *(++NCD->succ_begin()));
158    }
159    assert(SuccA && SuccB);
160    for (std::pair<unsigned, LiveRange*> RegLR : SGPRLiveRanges) {
161      unsigned Reg = RegLR.first;
162      LiveRange *LR = RegLR.second;
163
164      // FIXME: We could be smarter here.  If the register is Live-In to
165      // one block, but the other doesn't have any SGPR defs, then there
166      // won't be a conflict.  Also, if the branch decision is based on
167      // a value in an SGPR, then there will be no conflict.
168      bool LiveInToA = LIS->isLiveInToMBB(*LR, SuccA);
169      bool LiveInToB = LIS->isLiveInToMBB(*LR, SuccB);
170
171      if ((!LiveInToA && !LiveInToB) ||
172          (LiveInToA && LiveInToB))
173        continue;
174
175      // This interval is live in to one successor, but not the other, so
176      // we need to update its range so it is live in to both.
177      DEBUG(dbgs() << "Possible SGPR conflict detected " <<  " in " << *LR <<
178                      " BB#" << SuccA->getNumber() << ", BB#" <<
179                      SuccB->getNumber() <<
180                      " with NCD = " << NCD->getNumber() << '\n');
181
182      // FIXME: Need to figure out how to update LiveRange here so this pass
183      // will be able to preserve LiveInterval analysis.
184      BuildMI(*NCD, NCD->getFirstNonPHI(), DebugLoc(),
185              TII->get(AMDGPU::SGPR_USE))
186              .addReg(Reg, RegState::Implicit);
187      DEBUG(NCD->getFirstNonPHI()->dump());
188    }
189  }
190
191  return false;
192}
193