1//===- HexagonBlockRanges.cpp ---------------------------------------------===//
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#include "HexagonBlockRanges.h"
10#include "HexagonInstrInfo.h"
11#include "HexagonSubtarget.h"
12#include "llvm/ADT/BitVector.h"
13#include "llvm/ADT/STLExtras.h"
14#include "llvm/CodeGen/MachineBasicBlock.h"
15#include "llvm/CodeGen/MachineFunction.h"
16#include "llvm/CodeGen/MachineInstr.h"
17#include "llvm/CodeGen/MachineOperand.h"
18#include "llvm/CodeGen/MachineRegisterInfo.h"
19#include "llvm/CodeGen/TargetRegisterInfo.h"
20#include "llvm/MC/MCRegisterInfo.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/raw_ostream.h"
23#include <cassert>
24#include <cstdint>
25#include <iterator>
26#include <map>
27#include <utility>
28
29using namespace llvm;
30
31#define DEBUG_TYPE "hbr"
32
33bool HexagonBlockRanges::IndexRange::overlaps(const IndexRange &A) const {
34 // If A contains start(), or "this" contains A.start(), then overlap.
35 IndexType S = start(), E = end(), AS = A.start(), AE = A.end();
36 if (AS == S)
37 return true;
38 bool SbAE = (S < AE) || (S == AE && A.TiedEnd); // S-before-AE.
39 bool ASbE = (AS < E) || (AS == E && TiedEnd); // AS-before-E.
40 if ((AS < S && SbAE) || (S < AS && ASbE))
41 return true;
42 // Otherwise no overlap.
43 return false;
44}
45
46bool HexagonBlockRanges::IndexRange::contains(const IndexRange &A) const {
47 if (start() <= A.start()) {
48 // Treat "None" in the range end as equal to the range start.
49 IndexType E = (end() != IndexType::None) ? end() : start();
50 IndexType AE = (A.end() != IndexType::None) ? A.end() : A.start();
51 if (AE <= E)
52 return true;
53 }
54 return false;
55}
56
57void HexagonBlockRanges::IndexRange::merge(const IndexRange &A) {
58 // Allow merging adjacent ranges.
59 assert(end() == A.start() || overlaps(A));
60 IndexType AS = A.start(), AE = A.end();
61 if (AS < start() || start() == IndexType::None)
62 setStart(AS);
63 if (end() < AE || end() == IndexType::None) {
64 setEnd(AE);
65 TiedEnd = A.TiedEnd;
66 } else {
67 if (end() == AE)
68 TiedEnd |= A.TiedEnd;
69 }
70 if (A.Fixed)
71 Fixed = true;
72}
73
74void HexagonBlockRanges::RangeList::include(const RangeList &RL) {
75 for (const auto &R : RL)
76 if (!is_contained(Range&: *this, Element: R))
77 push_back(x: R);
78}
79
80// Merge all overlapping ranges in the list, so that all that remains
81// is a list of disjoint ranges.
82void HexagonBlockRanges::RangeList::unionize(bool MergeAdjacent) {
83 if (empty())
84 return;
85
86 llvm::sort(C&: *this);
87 iterator Iter = begin();
88
89 while (Iter != end()-1) {
90 iterator Next = std::next(x: Iter);
91 // If MergeAdjacent is true, merge ranges A and B, where A.end == B.start.
92 // This allows merging dead ranges, but is not valid for live ranges.
93 bool Merge = MergeAdjacent && (Iter->end() == Next->start());
94 if (Merge || Iter->overlaps(A: *Next)) {
95 Iter->merge(A: *Next);
96 erase(position: Next);
97 continue;
98 }
99 ++Iter;
100 }
101}
102
103// Compute a range A-B and add it to the list.
104void HexagonBlockRanges::RangeList::addsub(const IndexRange &A,
105 const IndexRange &B) {
106 // Exclusion of non-overlapping ranges makes some checks simpler
107 // later in this function.
108 if (!A.overlaps(A: B)) {
109 // A - B = A.
110 add(Range: A);
111 return;
112 }
113
114 IndexType AS = A.start(), AE = A.end();
115 IndexType BS = B.start(), BE = B.end();
116
117 // If AE is None, then A is included in B, since A and B overlap.
118 // The result of subtraction if empty, so just return.
119 if (AE == IndexType::None)
120 return;
121
122 if (AS < BS) {
123 // A starts before B.
124 // AE cannot be None since A and B overlap.
125 assert(AE != IndexType::None);
126 // Add the part of A that extends on the "less" side of B.
127 add(Start: AS, End: BS, Fixed: A.Fixed, TiedEnd: false);
128 }
129
130 if (BE < AE) {
131 // BE cannot be Exit here.
132 if (BE == IndexType::None)
133 add(Start: BS, End: AE, Fixed: A.Fixed, TiedEnd: false);
134 else
135 add(Start: BE, End: AE, Fixed: A.Fixed, TiedEnd: false);
136 }
137}
138
139// Subtract a given range from each element in the list.
140void HexagonBlockRanges::RangeList::subtract(const IndexRange &Range) {
141 // Cannot assume that the list is unionized (i.e. contains only non-
142 // overlapping ranges.
143 RangeList T;
144 for (iterator Next, I = begin(); I != end(); I = Next) {
145 IndexRange &Rg = *I;
146 if (Rg.overlaps(A: Range)) {
147 T.addsub(A: Rg, B: Range);
148 Next = this->erase(position: I);
149 } else {
150 Next = std::next(x: I);
151 }
152 }
153 include(RL: T);
154}
155
156HexagonBlockRanges::InstrIndexMap::InstrIndexMap(MachineBasicBlock &B)
157 : Block(B) {
158 IndexType Idx = IndexType::First;
159 First = Idx;
160 for (auto &In : B) {
161 if (In.isDebugInstr())
162 continue;
163 assert(getIndex(&In) == IndexType::None && "Instruction already in map");
164 Map.insert(x: std::make_pair(x&: Idx, y: &In));
165 ++Idx;
166 }
167 Last = B.empty() ? IndexType::None : unsigned(Idx)-1;
168}
169
170MachineInstr *HexagonBlockRanges::InstrIndexMap::getInstr(IndexType Idx) const {
171 auto F = Map.find(x: Idx);
172 return (F != Map.end()) ? F->second : nullptr;
173}
174
175HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getIndex(
176 MachineInstr *MI) const {
177 for (const auto &I : Map)
178 if (I.second == MI)
179 return I.first;
180 return IndexType::None;
181}
182
183HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getPrevIndex(
184 IndexType Idx) const {
185 assert (Idx != IndexType::None);
186 if (Idx == IndexType::Entry)
187 return IndexType::None;
188 if (Idx == IndexType::Exit)
189 return Last;
190 if (Idx == First)
191 return IndexType::Entry;
192 return unsigned(Idx)-1;
193}
194
195HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getNextIndex(
196 IndexType Idx) const {
197 assert (Idx != IndexType::None);
198 if (Idx == IndexType::Entry)
199 return IndexType::First;
200 if (Idx == IndexType::Exit || Idx == Last)
201 return IndexType::None;
202 return unsigned(Idx)+1;
203}
204
205void HexagonBlockRanges::InstrIndexMap::replaceInstr(MachineInstr *OldMI,
206 MachineInstr *NewMI) {
207 for (auto &I : Map) {
208 if (I.second != OldMI)
209 continue;
210 if (NewMI != nullptr)
211 I.second = NewMI;
212 else
213 Map.erase(x: I.first);
214 break;
215 }
216}
217
218HexagonBlockRanges::HexagonBlockRanges(MachineFunction &mf)
219 : MF(mf), HST(mf.getSubtarget<HexagonSubtarget>()),
220 TII(*HST.getInstrInfo()), TRI(*HST.getRegisterInfo()),
221 Reserved(TRI.getReservedRegs(MF: mf)) {
222 // Consider all non-allocatable registers as reserved.
223 for (const TargetRegisterClass *RC : TRI.regclasses()) {
224 if (RC->isAllocatable())
225 continue;
226 for (unsigned R : *RC)
227 Reserved[R] = true;
228 }
229}
230
231HexagonBlockRanges::RegisterSet HexagonBlockRanges::getLiveIns(
232 const MachineBasicBlock &B, const MachineRegisterInfo &MRI,
233 const TargetRegisterInfo &TRI) {
234 RegisterSet LiveIns;
235 RegisterSet Tmp;
236
237 for (auto I : B.liveins()) {
238 MCSubRegIndexIterator S(I.PhysReg, &TRI);
239 if (I.LaneMask.all() || (I.LaneMask.any() && !S.isValid())) {
240 Tmp.insert(x: {.Reg: I.PhysReg, .Sub: 0});
241 continue;
242 }
243 for (; S.isValid(); ++S) {
244 unsigned SI = S.getSubRegIndex();
245 if ((I.LaneMask & TRI.getSubRegIndexLaneMask(SubIdx: SI)).any())
246 Tmp.insert(x: {.Reg: S.getSubReg(), .Sub: 0});
247 }
248 }
249
250 for (auto R : Tmp) {
251 if (!Reserved[R.Reg])
252 LiveIns.insert(x: R);
253 for (auto S : expandToSubRegs(R, MRI, TRI))
254 if (!Reserved[S.Reg])
255 LiveIns.insert(x: S);
256 }
257 return LiveIns;
258}
259
260HexagonBlockRanges::RegisterSet HexagonBlockRanges::expandToSubRegs(
261 RegisterRef R, const MachineRegisterInfo &MRI,
262 const TargetRegisterInfo &TRI) {
263 RegisterSet SRs;
264
265 if (R.Sub != 0) {
266 SRs.insert(x: R);
267 return SRs;
268 }
269
270 if (R.Reg.isPhysical()) {
271 if (TRI.subregs(Reg: R.Reg).empty())
272 SRs.insert(x: {.Reg: R.Reg, .Sub: 0});
273 for (MCPhysReg I : TRI.subregs(Reg: R.Reg))
274 SRs.insert(x: {.Reg: I, .Sub: 0});
275 } else {
276 assert(R.Reg.isVirtual());
277 auto &RC = *MRI.getRegClass(Reg: R.Reg);
278 unsigned PReg = *RC.begin();
279 MCSubRegIndexIterator I(PReg, &TRI);
280 if (!I.isValid())
281 SRs.insert(x: {.Reg: R.Reg, .Sub: 0});
282 for (; I.isValid(); ++I)
283 SRs.insert(x: {.Reg: R.Reg, .Sub: I.getSubRegIndex()});
284 }
285 return SRs;
286}
287
288void HexagonBlockRanges::computeInitialLiveRanges(InstrIndexMap &IndexMap,
289 RegToRangeMap &LiveMap) {
290 std::map<RegisterRef,IndexType> LastDef, LastUse;
291 RegisterSet LiveOnEntry;
292 MachineBasicBlock &B = IndexMap.getBlock();
293 MachineRegisterInfo &MRI = B.getParent()->getRegInfo();
294
295 for (auto R : getLiveIns(B, MRI, TRI))
296 LiveOnEntry.insert(x: R);
297
298 for (auto R : LiveOnEntry)
299 LastDef[R] = IndexType::Entry;
300
301 auto closeRange = [&LastUse,&LastDef,&LiveMap] (RegisterRef R) -> void {
302 auto LD = LastDef[R], LU = LastUse[R];
303 if (LD == IndexType::None)
304 LD = IndexType::Entry;
305 if (LU == IndexType::None)
306 LU = IndexType::Exit;
307 LiveMap[R].add(Start: LD, End: LU, Fixed: false, TiedEnd: false);
308 LastUse[R] = LastDef[R] = IndexType::None;
309 };
310
311 RegisterSet Defs, Clobbers;
312
313 for (auto &In : B) {
314 if (In.isDebugInstr())
315 continue;
316 IndexType Index = IndexMap.getIndex(MI: &In);
317 // Process uses first.
318 for (auto &Op : In.operands()) {
319 if (!Op.isReg() || !Op.isUse() || Op.isUndef())
320 continue;
321 RegisterRef R = { .Reg: Op.getReg(), .Sub: Op.getSubReg() };
322 if (R.Reg.isPhysical() && Reserved[R.Reg])
323 continue;
324 bool IsKill = Op.isKill();
325 for (auto S : expandToSubRegs(R, MRI, TRI)) {
326 LastUse[S] = Index;
327 if (IsKill)
328 closeRange(S);
329 }
330 }
331 // Process defs and clobbers.
332 Defs.clear();
333 Clobbers.clear();
334 for (auto &Op : In.operands()) {
335 if (!Op.isReg() || !Op.isDef() || Op.isUndef())
336 continue;
337 RegisterRef R = { .Reg: Op.getReg(), .Sub: Op.getSubReg() };
338 for (auto S : expandToSubRegs(R, MRI, TRI)) {
339 if (S.Reg.isPhysical() && Reserved[S.Reg])
340 continue;
341 if (Op.isDead())
342 Clobbers.insert(x: S);
343 else
344 Defs.insert(x: S);
345 }
346 }
347
348 for (auto &Op : In.operands()) {
349 if (!Op.isRegMask())
350 continue;
351 const uint32_t *BM = Op.getRegMask();
352 for (unsigned PR = 1, N = TRI.getNumRegs(); PR != N; ++PR) {
353 // Skip registers that have subregisters. A register is preserved
354 // iff its bit is set in the regmask, so if R1:0 was preserved, both
355 // R1 and R0 would also be present.
356 if (!TRI.subregs(Reg: PR).empty())
357 continue;
358 if (Reserved[PR])
359 continue;
360 if (BM[PR/32] & (1u << (PR%32)))
361 continue;
362 RegisterRef R = { .Reg: PR, .Sub: 0 };
363 if (!Defs.count(x: R))
364 Clobbers.insert(x: R);
365 }
366 }
367 // Defs and clobbers can overlap, e.g.
368 // dead %d0 = COPY %5, implicit-def %r0, implicit-def %r1
369 for (RegisterRef R : Defs)
370 Clobbers.erase(x: R);
371
372 // Update maps for defs.
373 for (RegisterRef S : Defs) {
374 // Defs should already be expanded into subregs.
375 assert(!S.Reg.isPhysical() || TRI.subregs(S.Reg).empty());
376 if (LastDef[S] != IndexType::None || LastUse[S] != IndexType::None)
377 closeRange(S);
378 LastDef[S] = Index;
379 }
380 // Update maps for clobbers.
381 for (RegisterRef S : Clobbers) {
382 // Clobbers should already be expanded into subregs.
383 assert(!S.Reg.isPhysical() || TRI.subregs(S.Reg).empty());
384 if (LastDef[S] != IndexType::None || LastUse[S] != IndexType::None)
385 closeRange(S);
386 // Create a single-instruction range.
387 LastDef[S] = LastUse[S] = Index;
388 closeRange(S);
389 }
390 }
391
392 // Collect live-on-exit.
393 RegisterSet LiveOnExit;
394 for (auto *SB : B.successors())
395 for (auto R : getLiveIns(B: *SB, MRI, TRI))
396 LiveOnExit.insert(x: R);
397
398 for (auto R : LiveOnExit)
399 LastUse[R] = IndexType::Exit;
400
401 // Process remaining registers.
402 RegisterSet Left;
403 for (auto &I : LastUse)
404 if (I.second != IndexType::None)
405 Left.insert(x: I.first);
406 for (auto &I : LastDef)
407 if (I.second != IndexType::None)
408 Left.insert(x: I.first);
409 for (auto R : Left)
410 closeRange(R);
411
412 // Finalize the live ranges.
413 for (auto &P : LiveMap)
414 P.second.unionize();
415}
416
417HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeLiveMap(
418 InstrIndexMap &IndexMap) {
419 RegToRangeMap LiveMap;
420 LLVM_DEBUG(dbgs() << __func__ << ": index map\n" << IndexMap << '\n');
421 computeInitialLiveRanges(IndexMap, LiveMap);
422 LLVM_DEBUG(dbgs() << __func__ << ": live map\n"
423 << PrintRangeMap(LiveMap, TRI) << '\n');
424 return LiveMap;
425}
426
427HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeDeadMap(
428 InstrIndexMap &IndexMap, RegToRangeMap &LiveMap) {
429 RegToRangeMap DeadMap;
430
431 auto addDeadRanges = [&IndexMap,&LiveMap,&DeadMap] (RegisterRef R) -> void {
432 auto F = LiveMap.find(x: R);
433 if (F == LiveMap.end() || F->second.empty()) {
434 DeadMap[R].add(Start: IndexType::Entry, End: IndexType::Exit, Fixed: false, TiedEnd: false);
435 return;
436 }
437
438 RangeList &RL = F->second;
439 RangeList::iterator A = RL.begin(), Z = RL.end()-1;
440
441 // Try to create the initial range.
442 if (A->start() != IndexType::Entry) {
443 IndexType DE = IndexMap.getPrevIndex(Idx: A->start());
444 if (DE != IndexType::Entry)
445 DeadMap[R].add(Start: IndexType::Entry, End: DE, Fixed: false, TiedEnd: false);
446 }
447
448 while (A != Z) {
449 // Creating a dead range that follows A. Pay attention to empty
450 // ranges (i.e. those ending with "None").
451 IndexType AE = (A->end() == IndexType::None) ? A->start() : A->end();
452 IndexType DS = IndexMap.getNextIndex(Idx: AE);
453 ++A;
454 IndexType DE = IndexMap.getPrevIndex(Idx: A->start());
455 if (DS < DE)
456 DeadMap[R].add(Start: DS, End: DE, Fixed: false, TiedEnd: false);
457 }
458
459 // Try to create the final range.
460 if (Z->end() != IndexType::Exit) {
461 IndexType ZE = (Z->end() == IndexType::None) ? Z->start() : Z->end();
462 IndexType DS = IndexMap.getNextIndex(Idx: ZE);
463 if (DS < IndexType::Exit)
464 DeadMap[R].add(Start: DS, End: IndexType::Exit, Fixed: false, TiedEnd: false);
465 }
466 };
467
468 MachineFunction &MF = *IndexMap.getBlock().getParent();
469 auto &MRI = MF.getRegInfo();
470 unsigned NumRegs = TRI.getNumRegs();
471 BitVector Visited(NumRegs);
472 for (unsigned R = 1; R < NumRegs; ++R) {
473 for (auto S : expandToSubRegs(R: {.Reg: R,.Sub: 0}, MRI, TRI)) {
474 if (Reserved[S.Reg] || Visited[S.Reg])
475 continue;
476 addDeadRanges(S);
477 Visited[S.Reg] = true;
478 }
479 }
480 for (auto &P : LiveMap)
481 if (P.first.Reg.isVirtual())
482 addDeadRanges(P.first);
483
484 LLVM_DEBUG(dbgs() << __func__ << ": dead map\n"
485 << PrintRangeMap(DeadMap, TRI) << '\n');
486 return DeadMap;
487}
488
489raw_ostream &llvm::operator<<(raw_ostream &OS,
490 HexagonBlockRanges::IndexType Idx) {
491 if (Idx == HexagonBlockRanges::IndexType::None)
492 return OS << '-';
493 if (Idx == HexagonBlockRanges::IndexType::Entry)
494 return OS << 'n';
495 if (Idx == HexagonBlockRanges::IndexType::Exit)
496 return OS << 'x';
497 return OS << unsigned(Idx)-HexagonBlockRanges::IndexType::First+1;
498}
499
500// A mapping to translate between instructions and their indices.
501raw_ostream &llvm::operator<<(raw_ostream &OS,
502 const HexagonBlockRanges::IndexRange &IR) {
503 OS << '[' << IR.start() << ':' << IR.end() << (IR.TiedEnd ? '}' : ']');
504 if (IR.Fixed)
505 OS << '!';
506 return OS;
507}
508
509raw_ostream &llvm::operator<<(raw_ostream &OS,
510 const HexagonBlockRanges::RangeList &RL) {
511 for (const auto &R : RL)
512 OS << R << " ";
513 return OS;
514}
515
516raw_ostream &llvm::operator<<(raw_ostream &OS,
517 const HexagonBlockRanges::InstrIndexMap &M) {
518 for (auto &In : M.Block) {
519 HexagonBlockRanges::IndexType Idx = M.getIndex(MI: &In);
520 OS << Idx << (Idx == M.Last ? ". " : " ") << In;
521 }
522 return OS;
523}
524
525raw_ostream &llvm::operator<<(raw_ostream &OS,
526 const HexagonBlockRanges::PrintRangeMap &P) {
527 for (const auto &I : P.Map) {
528 const HexagonBlockRanges::RangeList &RL = I.second;
529 OS << printReg(Reg: I.first.Reg, TRI: &P.TRI, SubIdx: I.first.Sub) << " -> " << RL << "\n";
530 }
531 return OS;
532}
533