1//===-- HexagonGlobalRegion.cpp - VLIW global scheduling infrastructure ---===//
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// Basic infrastructure for global scheduling. Liveness update.
9// This is the least complete portion. Basically it is empty infrastructure
10// to be extended and improved.
11// Currently in place only trace region formation routines and non fully
12// functional skeleton for incremental liveness update.
13//
14//===----------------------------------------------------------------------===//
15#define DEBUG_TYPE "global_sched"
16#include "HexagonGlobalRegion.h"
17#include "HexagonTargetMachine.h"
18#include "llvm/Support/raw_ostream.h"
19
20using namespace llvm;
21
22LivenessInfo::LivenessInfo(const TargetInstrInfo *TII,
23 const TargetRegisterInfo *TRI,
24 MachineBasicBlock *MBB)
25 : TII(TII), TRI(TRI) {
26 LiveIns.resize(N: TRI->getNumRegs());
27 LiveOuts.resize(N: TRI->getNumRegs());
28
29 LiveIns.reset();
30 LiveOuts.reset();
31
32 // Live-ins are simple, just copy from MBB.
33 for (const auto &LI : MBB->liveins())
34 setUsed(Set&: LiveIns, Reg: LI.PhysReg);
35
36 // Live-outs are concatenation of all the BB successors.
37 // As of now, we are only dealing with a-cyclic regions
38 // with side exits, but no side entrances.
39 for (const MachineBasicBlock *Succ : MBB->successors())
40 for (const auto &LI : Succ->liveins())
41 setUsed(Set&: LiveOuts, Reg: LI.PhysReg);
42}
43
44// Pessimistically check if at least one def of this register in this
45// instruction (bundle or not) is done under predication.
46static bool isPredicatedDef(MachineInstr *MI, unsigned Reg,
47 const HexagonInstrInfo *QII) {
48 if (!MI->isBundle())
49 return QII->isPredicated(MI: *MI);
50 MachineBasicBlock *Parent = MI->getParent();
51 if (!Parent)
52 return false;
53 MachineBasicBlock::instr_iterator MII = MI->getIterator();
54 MachineBasicBlock::instr_iterator MIIE = Parent->instr_end();
55 for (++MII; MII != MIIE && MII->isInsideBundle(); ++MII) {
56 if (!QII->isPredicated(MI: *MII))
57 continue;
58 for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
59 const MachineOperand &MO = MII->getOperand(i);
60 if (!MO.isReg())
61 continue;
62 if (MO.isDef() && !MO.isDead() && MO.getReg() == Reg) {
63 LLVM_DEBUG(dbgs() << "\t\tCond def: "; MII->dump());
64 return true;
65 }
66 }
67 }
68 return false;
69}
70
71/// Determine def/use set for MI.
72/// Beware, if def is conditional, like here:
73/// BUNDLE %PC<imp-def>, %R0<imp-def>, %P0<imp-use,kill>, %R16<imp-use>
74/// * %R0<def> = LDriuh_cdnNotPt %P0<kill,internal>, %R16, 0;
75/// * %P0<def> = C2_cmpeqi %R16, 0;
76/// It is not a statefull definition of R0.
77///
78void LivenessInfo::parseOperands(MachineInstr *MI, BitVector &Gen,
79 BitVector &Kill, BitVector &Use) {
80 const auto *QII = static_cast<const HexagonInstrInfo *>(TII);
81
82 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
83 const MachineOperand &MO = MI->getOperand(i);
84 if (!MO.isReg())
85 continue;
86 // If it is a predicated instruction, it may, or may not
87 // be setting its destination, and we do not know it
88 // at the compile time.
89 if (MO.isDef() && !MO.isDead()) {
90 if (isPredicatedDef(MI, Reg: MO.getReg(), QII))
91 LLVM_DEBUG(dbgs() << "\tConditional define of "
92 << printReg(MO.getReg(), TRI) << " in ";
93 MI->dump());
94 else
95 setUsed(Set&: Gen, Reg: MO.getReg());
96 }
97 if (MO.isKill())
98 setUsed(Set&: Kill, Reg: MO.getReg());
99 if (MO.isUse())
100 setUsed(Set&: Use, Reg: MO.getReg());
101 }
102}
103
104void LivenessInfo::parseOperandsWithReset(MachineInstr *MI, BitVector &Gen,
105 BitVector &Kill, BitVector &Use) {
106 Gen.reset();
107 Use.reset();
108 Kill.reset();
109 parseOperands(MI, Gen, Kill, Use);
110}
111
112/// setUsed - Set the register and its sub-registers as being used.
113/// Taken from RegScavenger::setUsed().
114void LivenessInfo::setUsed(BitVector &Set, unsigned Reg) {
115 Set.set(Reg);
116
117 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
118 Set.set(*SubRegs);
119}
120
121#ifndef NDEBUG
122static void dumpRI(const TargetRegisterInfo *TRI, BitVector &Set) {
123 for (unsigned i = 0; i < Set.size(); i++)
124 if (Set.test(i))
125 LLVM_DEBUG(dbgs() << " " << printReg(i, TRI));
126}
127#endif
128
129// This function incrementally updates liveness for the given BB.
130// First it gathers LiveOut set, and then iterates bottom-up
131// over bundles/instructions while updating live set.
132void LivenessInfo::UpdateLiveness(MachineBasicBlock *MBB) {
133 BitVector NewLiveIns(TRI->getNumRegs());
134 BitVector NewLiveOuts(TRI->getNumRegs());
135 BitVector LiveIns(TRI->getNumRegs());
136 BitVector LocalGen(TRI->getNumRegs());
137 BitVector LocalUse(TRI->getNumRegs());
138 BitVector LocalKill(TRI->getNumRegs());
139
140 NewLiveIns.reset();
141 NewLiveOuts.reset();
142
143 LLVM_DEBUG(dbgs() << "\n\t\tUpdateLiveness for BB(" << MBB->getNumber()
144 << ")\n");
145
146 // Original Live-ins are simple, just copy from MBB.
147 for (const auto &LI : MBB->liveins())
148 setUsed(Set&: NewLiveIns, Reg: LI.PhysReg);
149
150 // Live-outs are concatenation of all the BB successors.
151 // As of now, we are only dealing with a-cyclic regions
152 // with side exits, but no side entrances.
153 for (const MachineBasicBlock *Succ : MBB->successors())
154 for (const auto &LI : Succ->liveins())
155 setUsed(Set&: NewLiveOuts, Reg: LI.PhysReg);
156
157 LiveIns = NewLiveIns;
158 // This needs to be a sequential walk, not parallel update.
159 LLVM_DEBUG(dbgs() << "\t\tOriginal live ins :\t"; dumpRI(TRI, NewLiveIns);
160 dbgs() << "\n");
161 LLVM_DEBUG(dbgs() << "\t\tOriginal live outs:\t"; dumpRI(TRI, NewLiveOuts);
162 dbgs() << "\n");
163
164 NewLiveIns = NewLiveOuts;
165 // Scan BB backwards to get exposed uses.
166 // TODO: Handle predicates if needed.
167 std::vector<MachineInstr *> BundleList;
168 for (MachineBasicBlock::iterator MI = MBB->begin(), MIE = MBB->end();
169 MI != MIE; ++MI)
170 if (!MI->isDebugInstr())
171 BundleList.push_back(x: &*MI);
172
173 while (!BundleList.empty()) {
174 MachineInstr *MI = BundleList.back();
175 BundleList.pop_back();
176 parseOperandsWithReset(MI, Gen&: LocalGen, Kill&: LocalKill, Use&: LocalUse);
177 LLVM_DEBUG(dbgs() << "\t\tIncr gen:\t"; dumpRI(TRI, LocalGen);
178 dbgs() << "\n");
179 LLVM_DEBUG(dbgs() << "\t\tIncr use:\t"; dumpRI(TRI, LocalUse);
180 dbgs() << "\n");
181 // NewLiveIns = (NewLiveIns - LocalGen) U LocalUse.
182 BitVector NotGen(LocalGen);
183 NotGen.flip();
184 NewLiveIns &= NotGen;
185 NewLiveIns |= LocalUse;
186 }
187
188 LLVM_DEBUG(dbgs() << "\t\tAnswer:\t"; dumpRI(TRI, NewLiveIns);
189 dbgs() << "\n");
190
191 // TODO: Consider implementing a register aliasing filter if duplicate
192 // live-in entries become problematic.
193
194 // Set new live in.
195 LLVM_DEBUG(dbgs() << "\t\tNew LiveIn :\t");
196
197 for (unsigned i = 0; i < LiveIns.size(); ++i) {
198 if (NewLiveIns.test(Idx: i))
199 LLVM_DEBUG(dbgs() << " " << printReg(i, TRI));
200 if (LiveIns.test(Idx: i) == NewLiveIns.test(Idx: i))
201 continue;
202 if (LiveIns.test(Idx: i))
203 MBB->removeLiveIn(Reg: i);
204 if (NewLiveIns.test(Idx: i))
205 MBB->addLiveIn(PhysReg: i);
206 }
207 LLVM_DEBUG(dbgs() << "\n");
208}
209
210void LivenessInfo::dump() {
211 for (unsigned i = 0; i < LiveIns.size(); i++)
212 if (LiveIns.test(Idx: i))
213 LLVM_DEBUG(dbgs() << "\t\tlive-in: " << printReg(i, TRI) << "\n");
214 for (unsigned i = 0; i < LiveOuts.size(); i++)
215 if (LiveOuts.test(Idx: i))
216 LLVM_DEBUG(dbgs() << "\t\tlive-out: " << printReg(i, TRI) << "\n");
217}
218
219///
220/// BasicBlockRegion Methods.
221///
222BasicBlockRegion::BasicBlockRegion(const TargetInstrInfo *TII,
223 const TargetRegisterInfo *TRI,
224 MachineBasicBlock *MBB)
225 : TII(TII), TRI(TRI) {
226 // Should be the root BB.
227 Elements.push_back(x: MBB);
228 ElementIndex[MBB] = 0;
229 LiveInfo[MBB] = std::make_unique<LivenessInfo>(args&: TII, args&: TRI, args&: MBB);
230}
231
232BasicBlockRegion::~BasicBlockRegion() {
233 LiveInfo.clear();
234 Elements.clear();
235 ElementIndex.clear();
236}
237
238LivenessInfo *BasicBlockRegion::getLivenessInfoForBB(MachineBasicBlock *MBB) {
239 auto It = LiveInfo.find(x: MBB);
240 assert(It != LiveInfo.end() && "Missing Liveness info");
241 assert(It->second && "Missing Liveness info");
242 return It->second.get();
243}
244
245void BasicBlockRegion::addBBtoRegion(MachineBasicBlock *MBB) {
246 // It is OK to have duplicates if we reparse for additional BBs.
247 if (LiveInfo.find(x: MBB) != LiveInfo.end())
248 return;
249 ElementIndex[MBB] = static_cast<unsigned>(Elements.size());
250 Elements.push_back(x: MBB);
251 LiveInfo[MBB] = std::make_unique<LivenessInfo>(args&: TII, args&: TRI, args&: MBB);
252}
253