LLVM 17.0.0git
HexagonExpandCondsets.cpp
Go to the documentation of this file.
1//===- HexagonExpandCondsets.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// Replace mux instructions with the corresponding legal instructions.
10// It is meant to work post-SSA, but still on virtual registers. It was
11// originally placed between register coalescing and machine instruction
12// scheduler.
13// In this place in the optimization sequence, live interval analysis had
14// been performed, and the live intervals should be preserved. A large part
15// of the code deals with preserving the liveness information.
16//
17// Liveness tracking aside, the main functionality of this pass is divided
18// into two steps. The first step is to replace an instruction
19// %0 = C2_mux %1, %2, %3
20// with a pair of conditional transfers
21// %0 = A2_tfrt %1, %2
22// %0 = A2_tfrf %1, %3
23// It is the intention that the execution of this pass could be terminated
24// after this step, and the code generated would be functionally correct.
25//
26// If the uses of the source values %1 and %2 are kills, and their
27// definitions are predicable, then in the second step, the conditional
28// transfers will then be rewritten as predicated instructions. E.g.
29// %0 = A2_or %1, %2
30// %3 = A2_tfrt %99, killed %0
31// will be rewritten as
32// %3 = A2_port %99, %1, %2
33//
34// This replacement has two variants: "up" and "down". Consider this case:
35// %0 = A2_or %1, %2
36// ... [intervening instructions] ...
37// %3 = A2_tfrt %99, killed %0
38// variant "up":
39// %3 = A2_port %99, %1, %2
40// ... [intervening instructions, %0->vreg3] ...
41// [deleted]
42// variant "down":
43// [deleted]
44// ... [intervening instructions] ...
45// %3 = A2_port %99, %1, %2
46//
47// Both, one or none of these variants may be valid, and checks are made
48// to rule out inapplicable variants.
49//
50// As an additional optimization, before either of the two steps above is
51// executed, the pass attempts to coalesce the target register with one of
52// the source registers, e.g. given an instruction
53// %3 = C2_mux %0, %1, %2
54// %3 will be coalesced with either %1 or %2. If this succeeds,
55// the instruction would then be (for example)
56// %3 = C2_mux %0, %3, %2
57// and, under certain circumstances, this could result in only one predicated
58// instruction:
59// %3 = A2_tfrf %0, %2
60//
61
62// Splitting a definition of a register into two predicated transfers
63// creates a complication in liveness tracking. Live interval computation
64// will see both instructions as actual definitions, and will mark the
65// first one as dead. The definition is not actually dead, and this
66// situation will need to be fixed. For example:
67// dead %1 = A2_tfrt ... ; marked as dead
68// %1 = A2_tfrf ...
69//
70// Since any of the individual predicated transfers may end up getting
71// removed (in case it is an identity copy), some pre-existing def may
72// be marked as dead after live interval recomputation:
73// dead %1 = ... ; marked as dead
74// ...
75// %1 = A2_tfrf ... ; if A2_tfrt is removed
76// This case happens if %1 was used as a source in A2_tfrt, which means
77// that is it actually live at the A2_tfrf, and so the now dead definition
78// of %1 will need to be updated to non-dead at some point.
79//
80// This issue could be remedied by adding implicit uses to the predicated
81// transfers, but this will create a problem with subsequent predication,
82// since the transfers will no longer be possible to reorder. To avoid
83// that, the initial splitting will not add any implicit uses. These
84// implicit uses will be added later, after predication. The extra price,
85// however, is that finding the locations where the implicit uses need
86// to be added, and updating the live ranges will be more involved.
87
88#include "HexagonInstrInfo.h"
89#include "HexagonRegisterInfo.h"
90#include "llvm/ADT/DenseMap.h"
91#include "llvm/ADT/SetVector.h"
93#include "llvm/ADT/StringRef.h"
107#include "llvm/IR/DebugLoc.h"
108#include "llvm/IR/Function.h"
110#include "llvm/MC/LaneBitmask.h"
111#include "llvm/Pass.h"
113#include "llvm/Support/Debug.h"
116#include <cassert>
117#include <iterator>
118#include <set>
119#include <utility>
120
121#define DEBUG_TYPE "expand-condsets"
122
123using namespace llvm;
124
125static cl::opt<unsigned> OptTfrLimit("expand-condsets-tfr-limit",
126 cl::init(~0U), cl::Hidden, cl::desc("Max number of mux expansions"));
127static cl::opt<unsigned> OptCoaLimit("expand-condsets-coa-limit",
128 cl::init(~0U), cl::Hidden, cl::desc("Max number of segment coalescings"));
129
130namespace llvm {
131
134
135} // end namespace llvm
136
137namespace {
138
139 class HexagonExpandCondsets : public MachineFunctionPass {
140 public:
141 static char ID;
142
143 HexagonExpandCondsets() : MachineFunctionPass(ID) {
144 if (OptCoaLimit.getPosition())
145 CoaLimitActive = true, CoaLimit = OptCoaLimit;
146 if (OptTfrLimit.getPosition())
147 TfrLimitActive = true, TfrLimit = OptTfrLimit;
149 }
150
151 StringRef getPassName() const override { return "Hexagon Expand Condsets"; }
152
153 void getAnalysisUsage(AnalysisUsage &AU) const override {
160 }
161
162 bool runOnMachineFunction(MachineFunction &MF) override;
163
164 private:
165 const HexagonInstrInfo *HII = nullptr;
166 const TargetRegisterInfo *TRI = nullptr;
168 MachineRegisterInfo *MRI = nullptr;
169 LiveIntervals *LIS = nullptr;
170 bool CoaLimitActive = false;
171 bool TfrLimitActive = false;
172 unsigned CoaLimit;
173 unsigned TfrLimit;
174 unsigned CoaCounter = 0;
175 unsigned TfrCounter = 0;
176
177 // FIXME: Consolidate duplicate definitions of RegisterRef
178 struct RegisterRef {
179 RegisterRef(const MachineOperand &Op) : Reg(Op.getReg()),
180 Sub(Op.getSubReg()) {}
181 RegisterRef(unsigned R = 0, unsigned S = 0) : Reg(R), Sub(S) {}
182
183 bool operator== (RegisterRef RR) const {
184 return Reg == RR.Reg && Sub == RR.Sub;
185 }
186 bool operator!= (RegisterRef RR) const { return !operator==(RR); }
187 bool operator< (RegisterRef RR) const {
188 return Reg < RR.Reg || (Reg == RR.Reg && Sub < RR.Sub);
189 }
190
192 unsigned Sub;
193 };
194
195 using ReferenceMap = DenseMap<unsigned, unsigned>;
196 enum { Sub_Low = 0x1, Sub_High = 0x2, Sub_None = (Sub_Low | Sub_High) };
197 enum { Exec_Then = 0x10, Exec_Else = 0x20 };
198
199 unsigned getMaskForSub(unsigned Sub);
200 bool isCondset(const MachineInstr &MI);
201 LaneBitmask getLaneMask(Register Reg, unsigned Sub);
202
203 void addRefToMap(RegisterRef RR, ReferenceMap &Map, unsigned Exec);
204 bool isRefInMap(RegisterRef, ReferenceMap &Map, unsigned Exec);
205
206 void updateDeadsInRange(Register Reg, LaneBitmask LM, LiveRange &Range);
207 void updateKillFlags(Register Reg);
208 void updateDeadFlags(Register Reg);
209 void recalculateLiveInterval(Register Reg);
210 void removeInstr(MachineInstr &MI);
211 void updateLiveness(const std::set<Register> &RegSet, bool Recalc,
212 bool UpdateKills, bool UpdateDeads);
213 void distributeLiveIntervals(const std::set<Register> &Regs);
214
215 unsigned getCondTfrOpcode(const MachineOperand &SO, bool Cond);
216 MachineInstr *genCondTfrFor(MachineOperand &SrcOp,
217 MachineBasicBlock::iterator At, unsigned DstR,
218 unsigned DstSR, const MachineOperand &PredOp, bool PredSense,
219 bool ReadUndef, bool ImpUse);
220 bool split(MachineInstr &MI, std::set<Register> &UpdRegs);
221
222 bool isPredicable(MachineInstr *MI);
223 MachineInstr *getReachingDefForPred(RegisterRef RD,
224 MachineBasicBlock::iterator UseIt, unsigned PredR, bool Cond);
225 bool canMoveOver(MachineInstr &MI, ReferenceMap &Defs, ReferenceMap &Uses);
226 bool canMoveMemTo(MachineInstr &MI, MachineInstr &ToI, bool IsDown);
227 void predicateAt(const MachineOperand &DefOp, MachineInstr &MI,
229 const MachineOperand &PredOp, bool Cond,
230 std::set<Register> &UpdRegs);
231 void renameInRange(RegisterRef RO, RegisterRef RN, unsigned PredR,
234 bool predicate(MachineInstr &TfrI, bool Cond, std::set<Register> &UpdRegs);
235 bool predicateInBlock(MachineBasicBlock &B, std::set<Register> &UpdRegs);
236
237 bool isIntReg(RegisterRef RR, unsigned &BW);
238 bool isIntraBlocks(LiveInterval &LI);
239 bool coalesceRegisters(RegisterRef R1, RegisterRef R2);
240 bool coalesceSegments(const SmallVectorImpl<MachineInstr *> &Condsets,
241 std::set<Register> &UpdRegs);
242 };
243
244} // end anonymous namespace
245
246char HexagonExpandCondsets::ID = 0;
247
248namespace llvm {
249
250 char &HexagonExpandCondsetsID = HexagonExpandCondsets::ID;
251
252} // end namespace llvm
253
254INITIALIZE_PASS_BEGIN(HexagonExpandCondsets, "expand-condsets",
255 "Hexagon Expand Condsets", false, false)
259INITIALIZE_PASS_END(HexagonExpandCondsets, "expand-condsets",
260 "Hexagon Expand Condsets", false, false)
261
262unsigned HexagonExpandCondsets::getMaskForSub(unsigned Sub) {
263 switch (Sub) {
264 case Hexagon::isub_lo:
265 case Hexagon::vsub_lo:
266 return Sub_Low;
267 case Hexagon::isub_hi:
268 case Hexagon::vsub_hi:
269 return Sub_High;
270 case Hexagon::NoSubRegister:
271 return Sub_None;
272 }
273 llvm_unreachable("Invalid subregister");
274}
275
276bool HexagonExpandCondsets::isCondset(const MachineInstr &MI) {
277 unsigned Opc = MI.getOpcode();
278 switch (Opc) {
279 case Hexagon::C2_mux:
280 case Hexagon::C2_muxii:
281 case Hexagon::C2_muxir:
282 case Hexagon::C2_muxri:
283 case Hexagon::PS_pselect:
284 return true;
285 break;
286 }
287 return false;
288}
289
290LaneBitmask HexagonExpandCondsets::getLaneMask(Register Reg, unsigned Sub) {
291 assert(Reg.isVirtual());
292 return Sub != 0 ? TRI->getSubRegIndexLaneMask(Sub)
293 : MRI->getMaxLaneMaskForVReg(Reg);
294}
295
296void HexagonExpandCondsets::addRefToMap(RegisterRef RR, ReferenceMap &Map,
297 unsigned Exec) {
298 unsigned Mask = getMaskForSub(RR.Sub) | Exec;
299 ReferenceMap::iterator F = Map.find(RR.Reg);
300 if (F == Map.end())
301 Map.insert(std::make_pair(RR.Reg, Mask));
302 else
303 F->second |= Mask;
304}
305
306bool HexagonExpandCondsets::isRefInMap(RegisterRef RR, ReferenceMap &Map,
307 unsigned Exec) {
308 ReferenceMap::iterator F = Map.find(RR.Reg);
309 if (F == Map.end())
310 return false;
311 unsigned Mask = getMaskForSub(RR.Sub) | Exec;
312 if (Mask & F->second)
313 return true;
314 return false;
315}
316
317void HexagonExpandCondsets::updateKillFlags(Register Reg) {
318 auto KillAt = [this,Reg] (SlotIndex K, LaneBitmask LM) -> void {
319 // Set the <kill> flag on a use of Reg whose lane mask is contained in LM.
320 MachineInstr *MI = LIS->getInstructionFromIndex(K);
321 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
322 MachineOperand &Op = MI->getOperand(i);
323 if (!Op.isReg() || !Op.isUse() || Op.getReg() != Reg ||
324 MI->isRegTiedToDefOperand(i))
325 continue;
326 LaneBitmask SLM = getLaneMask(Reg, Op.getSubReg());
327 if ((SLM & LM) == SLM) {
328 // Only set the kill flag on the first encountered use of Reg in this
329 // instruction.
330 Op.setIsKill(true);
331 break;
332 }
333 }
334 };
335
336 LiveInterval &LI = LIS->getInterval(Reg);
337 for (auto I = LI.begin(), E = LI.end(); I != E; ++I) {
338 if (!I->end.isRegister())
339 continue;
340 // Do not mark the end of the segment as <kill>, if the next segment
341 // starts with a predicated instruction.
342 auto NextI = std::next(I);
343 if (NextI != E && NextI->start.isRegister()) {
344 MachineInstr *DefI = LIS->getInstructionFromIndex(NextI->start);
345 if (HII->isPredicated(*DefI))
346 continue;
347 }
348 bool WholeReg = true;
349 if (LI.hasSubRanges()) {
350 auto EndsAtI = [I] (LiveInterval::SubRange &S) -> bool {
351 LiveRange::iterator F = S.find(I->end);
352 return F != S.end() && I->end == F->end;
353 };
354 // Check if all subranges end at I->end. If so, make sure to kill
355 // the whole register.
356 for (LiveInterval::SubRange &S : LI.subranges()) {
357 if (EndsAtI(S))
358 KillAt(I->end, S.LaneMask);
359 else
360 WholeReg = false;
361 }
362 }
363 if (WholeReg)
364 KillAt(I->end, MRI->getMaxLaneMaskForVReg(Reg));
365 }
366}
367
368void HexagonExpandCondsets::updateDeadsInRange(Register Reg, LaneBitmask LM,
369 LiveRange &Range) {
370 assert(Reg.isVirtual());
371 if (Range.empty())
372 return;
373
374 // Return two booleans: { def-modifes-reg, def-covers-reg }.
375 auto IsRegDef = [this,Reg,LM] (MachineOperand &Op) -> std::pair<bool,bool> {
376 if (!Op.isReg() || !Op.isDef())
377 return { false, false };
378 Register DR = Op.getReg(), DSR = Op.getSubReg();
379 if (!DR.isVirtual() || DR != Reg)
380 return { false, false };
381 LaneBitmask SLM = getLaneMask(DR, DSR);
382 LaneBitmask A = SLM & LM;
383 return { A.any(), A == SLM };
384 };
385
386 // The splitting step will create pairs of predicated definitions without
387 // any implicit uses (since implicit uses would interfere with predication).
388 // This can cause the reaching defs to become dead after live range
389 // recomputation, even though they are not really dead.
390 // We need to identify predicated defs that need implicit uses, and
391 // dead defs that are not really dead, and correct both problems.
392
393 auto Dominate = [this] (SetVector<MachineBasicBlock*> &Defs,
394 MachineBasicBlock *Dest) -> bool {
395 for (MachineBasicBlock *D : Defs) {
396 if (D != Dest && MDT->dominates(D, Dest))
397 return true;
398 }
399 MachineBasicBlock *Entry = &Dest->getParent()->front();
400 SetVector<MachineBasicBlock*> Work(Dest->pred_begin(), Dest->pred_end());
401 for (unsigned i = 0; i < Work.size(); ++i) {
402 MachineBasicBlock *B = Work[i];
403 if (Defs.count(B))
404 continue;
405 if (B == Entry)
406 return false;
407 for (auto *P : B->predecessors())
408 Work.insert(P);
409 }
410 return true;
411 };
412
413 // First, try to extend live range within individual basic blocks. This
414 // will leave us only with dead defs that do not reach any predicated
415 // defs in the same block.
418 for (auto &Seg : Range) {
419 if (!Seg.start.isRegister())
420 continue;
421 MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
422 Defs.insert(DefI->getParent());
423 if (HII->isPredicated(*DefI))
424 PredDefs.push_back(Seg.start);
425 }
426
428 LiveInterval &LI = LIS->getInterval(Reg);
429 LI.computeSubRangeUndefs(Undefs, LM, *MRI, *LIS->getSlotIndexes());
430
431 for (auto &SI : PredDefs) {
432 MachineBasicBlock *BB = LIS->getMBBFromIndex(SI);
433 auto P = Range.extendInBlock(Undefs, LIS->getMBBStartIdx(BB), SI);
434 if (P.first != nullptr || P.second)
435 SI = SlotIndex();
436 }
437
438 // Calculate reachability for those predicated defs that were not handled
439 // by the in-block extension.
441 for (auto &SI : PredDefs) {
442 if (!SI.isValid())
443 continue;
444 MachineBasicBlock *BB = LIS->getMBBFromIndex(SI);
445 if (BB->pred_empty())
446 continue;
447 // If the defs from this range reach SI via all predecessors, it is live.
448 // It can happen that SI is reached by the defs through some paths, but
449 // not all. In the IR coming into this optimization, SI would not be
450 // considered live, since the defs would then not jointly dominate SI.
451 // That means that SI is an overwriting def, and no implicit use is
452 // needed at this point. Do not add SI to the extension points, since
453 // extendToIndices will abort if there is no joint dominance.
454 // If the abort was avoided by adding extra undefs added to Undefs,
455 // extendToIndices could actually indicate that SI is live, contrary
456 // to the original IR.
457 if (Dominate(Defs, BB))
458 ExtTo.push_back(SI);
459 }
460
461 if (!ExtTo.empty())
462 LIS->extendToIndices(Range, ExtTo, Undefs);
463
464 // Remove <dead> flags from all defs that are not dead after live range
465 // extension, and collect all def operands. They will be used to generate
466 // the necessary implicit uses.
467 // At the same time, add <dead> flag to all defs that are actually dead.
468 // This can happen, for example, when a mux with identical inputs is
469 // replaced with a COPY: the use of the predicate register disappears and
470 // the dead can become dead.
471 std::set<RegisterRef> DefRegs;
472 for (auto &Seg : Range) {
473 if (!Seg.start.isRegister())
474 continue;
475 MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
476 for (auto &Op : DefI->operands()) {
477 auto P = IsRegDef(Op);
478 if (P.second && Seg.end.isDead()) {
479 Op.setIsDead(true);
480 } else if (P.first) {
481 DefRegs.insert(Op);
482 Op.setIsDead(false);
483 }
484 }
485 }
486
487 // Now, add implicit uses to each predicated def that is reached
488 // by other defs.
489 for (auto &Seg : Range) {
490 if (!Seg.start.isRegister() || !Range.liveAt(Seg.start.getPrevSlot()))
491 continue;
492 MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
493 if (!HII->isPredicated(*DefI))
494 continue;
495 // Construct the set of all necessary implicit uses, based on the def
496 // operands in the instruction. We need to tie the implicit uses to
497 // the corresponding defs.
498 std::map<RegisterRef,unsigned> ImpUses;
499 for (unsigned i = 0, e = DefI->getNumOperands(); i != e; ++i) {
500 MachineOperand &Op = DefI->getOperand(i);
501 if (!Op.isReg() || !DefRegs.count(Op))
502 continue;
503 if (Op.isDef()) {
504 // Tied defs will always have corresponding uses, so no extra
505 // implicit uses are needed.
506 if (!Op.isTied())
507 ImpUses.insert({Op, i});
508 } else {
509 // This function can be called for the same register with different
510 // lane masks. If the def in this instruction was for the whole
511 // register, we can get here more than once. Avoid adding multiple
512 // implicit uses (or adding an implicit use when an explicit one is
513 // present).
514 if (Op.isTied())
515 ImpUses.erase(Op);
516 }
517 }
518 if (ImpUses.empty())
519 continue;
520 MachineFunction &MF = *DefI->getParent()->getParent();
521 for (auto [R, DefIdx] : ImpUses) {
522 MachineInstrBuilder(MF, DefI).addReg(R.Reg, RegState::Implicit, R.Sub);
523 DefI->tieOperands(DefIdx, DefI->getNumOperands()-1);
524 }
525 }
526}
527
528void HexagonExpandCondsets::updateDeadFlags(Register Reg) {
529 LiveInterval &LI = LIS->getInterval(Reg);
530 if (LI.hasSubRanges()) {
531 for (LiveInterval::SubRange &S : LI.subranges()) {
532 updateDeadsInRange(Reg, S.LaneMask, S);
533 LIS->shrinkToUses(S, Reg);
534 }
535 LI.clear();
536 LIS->constructMainRangeFromSubranges(LI);
537 } else {
538 updateDeadsInRange(Reg, MRI->getMaxLaneMaskForVReg(Reg), LI);
539 }
540}
541
542void HexagonExpandCondsets::recalculateLiveInterval(Register Reg) {
543 LIS->removeInterval(Reg);
544 LIS->createAndComputeVirtRegInterval(Reg);
545}
546
547void HexagonExpandCondsets::removeInstr(MachineInstr &MI) {
548 LIS->RemoveMachineInstrFromMaps(MI);
549 MI.eraseFromParent();
550}
551
552void HexagonExpandCondsets::updateLiveness(const std::set<Register> &RegSet,
553 bool Recalc, bool UpdateKills,
554 bool UpdateDeads) {
555 UpdateKills |= UpdateDeads;
556 for (Register R : RegSet) {
557 if (!R.isVirtual()) {
558 assert(R.isPhysical());
559 // There shouldn't be any physical registers as operands, except
560 // possibly reserved registers.
561 assert(MRI->isReserved(R));
562 continue;
563 }
564 if (Recalc)
565 recalculateLiveInterval(R);
566 if (UpdateKills)
567 MRI->clearKillFlags(R);
568 if (UpdateDeads)
569 updateDeadFlags(R);
570 // Fixing <dead> flags may extend live ranges, so reset <kill> flags
571 // after that.
572 if (UpdateKills)
573 updateKillFlags(R);
574 LIS->getInterval(R).verify();
575 }
576}
577
578void HexagonExpandCondsets::distributeLiveIntervals(
579 const std::set<Register> &Regs) {
580 ConnectedVNInfoEqClasses EQC(*LIS);
581 for (Register R : Regs) {
582 if (!R.isVirtual())
583 continue;
584 LiveInterval &LI = LIS->getInterval(R);
585 unsigned NumComp = EQC.Classify(LI);
586 if (NumComp == 1)
587 continue;
588
590 const TargetRegisterClass *RC = MRI->getRegClass(LI.reg());
591 for (unsigned I = 1; I < NumComp; ++I) {
592 Register NewR = MRI->createVirtualRegister(RC);
593 NewLIs.push_back(&LIS->createEmptyInterval(NewR));
594 }
595 EQC.Distribute(LI, NewLIs.begin(), *MRI);
596 }
597}
598
599/// Get the opcode for a conditional transfer of the value in SO (source
600/// operand). The condition (true/false) is given in Cond.
601unsigned HexagonExpandCondsets::getCondTfrOpcode(const MachineOperand &SO,
602 bool IfTrue) {
603 if (SO.isReg()) {
604 MCRegister PhysR;
605 RegisterRef RS = SO;
606 if (RS.Reg.isVirtual()) {
607 const TargetRegisterClass *VC = MRI->getRegClass(RS.Reg);
608 assert(VC->begin() != VC->end() && "Empty register class");
609 PhysR = *VC->begin();
610 } else {
611 PhysR = RS.Reg;
612 }
613 MCRegister PhysS = (RS.Sub == 0) ? PhysR : TRI->getSubReg(PhysR, RS.Sub);
614 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(PhysS);
615 switch (TRI->getRegSizeInBits(*RC)) {
616 case 32:
617 return IfTrue ? Hexagon::A2_tfrt : Hexagon::A2_tfrf;
618 case 64:
619 return IfTrue ? Hexagon::A2_tfrpt : Hexagon::A2_tfrpf;
620 }
621 llvm_unreachable("Invalid register operand");
622 }
623 switch (SO.getType()) {
632 return IfTrue ? Hexagon::C2_cmoveit : Hexagon::C2_cmoveif;
633 default:
634 break;
635 }
636 llvm_unreachable("Unexpected source operand");
637}
638
639/// Generate a conditional transfer, copying the value SrcOp to the
640/// destination register DstR:DstSR, and using the predicate register from
641/// PredOp. The Cond argument specifies whether the predicate is to be
642/// if(PredOp), or if(!PredOp).
643MachineInstr *HexagonExpandCondsets::genCondTfrFor(MachineOperand &SrcOp,
645 unsigned DstR, unsigned DstSR, const MachineOperand &PredOp,
646 bool PredSense, bool ReadUndef, bool ImpUse) {
647 MachineInstr *MI = SrcOp.getParent();
648 MachineBasicBlock &B = *At->getParent();
649 const DebugLoc &DL = MI->getDebugLoc();
650
651 // Don't avoid identity copies here (i.e. if the source and the destination
652 // are the same registers). It is actually better to generate them here,
653 // since this would cause the copy to potentially be predicated in the next
654 // step. The predication will remove such a copy if it is unable to
655 /// predicate.
656
657 unsigned Opc = getCondTfrOpcode(SrcOp, PredSense);
658 unsigned DstState = RegState::Define | (ReadUndef ? RegState::Undef : 0);
659 unsigned PredState = getRegState(PredOp) & ~RegState::Kill;
661
662 if (SrcOp.isReg()) {
663 unsigned SrcState = getRegState(SrcOp);
664 if (RegisterRef(SrcOp) == RegisterRef(DstR, DstSR))
665 SrcState &= ~RegState::Kill;
666 MIB = BuildMI(B, At, DL, HII->get(Opc))
667 .addReg(DstR, DstState, DstSR)
668 .addReg(PredOp.getReg(), PredState, PredOp.getSubReg())
669 .addReg(SrcOp.getReg(), SrcState, SrcOp.getSubReg());
670 } else {
671 MIB = BuildMI(B, At, DL, HII->get(Opc))
672 .addReg(DstR, DstState, DstSR)
673 .addReg(PredOp.getReg(), PredState, PredOp.getSubReg())
674 .add(SrcOp);
675 }
676
677 LLVM_DEBUG(dbgs() << "created an initial copy: " << *MIB);
678 return &*MIB;
679}
680
681/// Replace a MUX instruction MI with a pair A2_tfrt/A2_tfrf. This function
682/// performs all necessary changes to complete the replacement.
683bool HexagonExpandCondsets::split(MachineInstr &MI,
684 std::set<Register> &UpdRegs) {
685 if (TfrLimitActive) {
686 if (TfrCounter >= TfrLimit)
687 return false;
688 TfrCounter++;
689 }
690 LLVM_DEBUG(dbgs() << "\nsplitting " << printMBBReference(*MI.getParent())
691 << ": " << MI);
692 MachineOperand &MD = MI.getOperand(0); // Definition
693 MachineOperand &MP = MI.getOperand(1); // Predicate register
694 assert(MD.isDef());
695 Register DR = MD.getReg(), DSR = MD.getSubReg();
696 bool ReadUndef = MD.isUndef();
698
699 auto updateRegs = [&UpdRegs] (const MachineInstr &MI) -> void {
700 for (auto &Op : MI.operands()) {
701 if (Op.isReg())
702 UpdRegs.insert(Op.getReg());
703 }
704 };
705
706 // If this is a mux of the same register, just replace it with COPY.
707 // Ideally, this would happen earlier, so that register coalescing would
708 // see it.
709 MachineOperand &ST = MI.getOperand(2);
710 MachineOperand &SF = MI.getOperand(3);
711 if (ST.isReg() && SF.isReg()) {
712 RegisterRef RT(ST);
713 if (RT == RegisterRef(SF)) {
714 // Copy regs to update first.
715 updateRegs(MI);
716 MI.setDesc(HII->get(TargetOpcode::COPY));
717 unsigned S = getRegState(ST);
718 while (MI.getNumOperands() > 1)
719 MI.removeOperand(MI.getNumOperands()-1);
720 MachineFunction &MF = *MI.getParent()->getParent();
721 MachineInstrBuilder(MF, MI).addReg(RT.Reg, S, RT.Sub);
722 return true;
723 }
724 }
725
726 // First, create the two invididual conditional transfers, and add each
727 // of them to the live intervals information. Do that first and then remove
728 // the old instruction from live intervals.
729 MachineInstr *TfrT =
730 genCondTfrFor(ST, At, DR, DSR, MP, true, ReadUndef, false);
731 MachineInstr *TfrF =
732 genCondTfrFor(SF, At, DR, DSR, MP, false, ReadUndef, true);
733 LIS->InsertMachineInstrInMaps(*TfrT);
734 LIS->InsertMachineInstrInMaps(*TfrF);
735
736 // Will need to recalculate live intervals for all registers in MI.
737 updateRegs(MI);
738
739 removeInstr(MI);
740 return true;
741}
742
743bool HexagonExpandCondsets::isPredicable(MachineInstr *MI) {
744 if (HII->isPredicated(*MI) || !HII->isPredicable(*MI))
745 return false;
746 if (MI->hasUnmodeledSideEffects() || MI->mayStore())
747 return false;
748 // Reject instructions with multiple defs (e.g. post-increment loads).
749 bool HasDef = false;
750 for (auto &Op : MI->operands()) {
751 if (!Op.isReg() || !Op.isDef())
752 continue;
753 if (HasDef)
754 return false;
755 HasDef = true;
756 }
757 for (auto &Mo : MI->memoperands()) {
758 if (Mo->isVolatile() || Mo->isAtomic())
759 return false;
760 }
761 return true;
762}
763
764/// Find the reaching definition for a predicated use of RD. The RD is used
765/// under the conditions given by PredR and Cond, and this function will ignore
766/// definitions that set RD under the opposite conditions.
767MachineInstr *HexagonExpandCondsets::getReachingDefForPred(RegisterRef RD,
768 MachineBasicBlock::iterator UseIt, unsigned PredR, bool Cond) {
769 MachineBasicBlock &B = *UseIt->getParent();
770 MachineBasicBlock::iterator I = UseIt, S = B.begin();
771 if (I == S)
772 return nullptr;
773
774 bool PredValid = true;
775 do {
776 --I;
777 MachineInstr *MI = &*I;
778 // Check if this instruction can be ignored, i.e. if it is predicated
779 // on the complementary condition.
780 if (PredValid && HII->isPredicated(*MI)) {
781 if (MI->readsRegister(PredR) && (Cond != HII->isPredicatedTrue(*MI)))
782 continue;
783 }
784
785 // Check the defs. If the PredR is defined, invalidate it. If RD is
786 // defined, return the instruction or 0, depending on the circumstances.
787 for (auto &Op : MI->operands()) {
788 if (!Op.isReg() || !Op.isDef())
789 continue;
790 RegisterRef RR = Op;
791 if (RR.Reg == PredR) {
792 PredValid = false;
793 continue;
794 }
795 if (RR.Reg != RD.Reg)
796 continue;
797 // If the "Reg" part agrees, there is still the subregister to check.
798 // If we are looking for %1:loreg, we can skip %1:hireg, but
799 // not %1 (w/o subregisters).
800 if (RR.Sub == RD.Sub)
801 return MI;
802 if (RR.Sub == 0 || RD.Sub == 0)
803 return nullptr;
804 // We have different subregisters, so we can continue looking.
805 }
806 } while (I != S);
807
808 return nullptr;
809}
810
811/// Check if the instruction MI can be safely moved over a set of instructions
812/// whose side-effects (in terms of register defs and uses) are expressed in
813/// the maps Defs and Uses. These maps reflect the conditional defs and uses
814/// that depend on the same predicate register to allow moving instructions
815/// over instructions predicated on the opposite condition.
816bool HexagonExpandCondsets::canMoveOver(MachineInstr &MI, ReferenceMap &Defs,
817 ReferenceMap &Uses) {
818 // In order to be able to safely move MI over instructions that define
819 // "Defs" and use "Uses", no def operand from MI can be defined or used
820 // and no use operand can be defined.
821 for (auto &Op : MI.operands()) {
822 if (!Op.isReg())
823 continue;
824 RegisterRef RR = Op;
825 // For physical register we would need to check register aliases, etc.
826 // and we don't want to bother with that. It would be of little value
827 // before the actual register rewriting (from virtual to physical).
828 if (!RR.Reg.isVirtual())
829 return false;
830 // No redefs for any operand.
831 if (isRefInMap(RR, Defs, Exec_Then))
832 return false;
833 // For defs, there cannot be uses.
834 if (Op.isDef() && isRefInMap(RR, Uses, Exec_Then))
835 return false;
836 }
837 return true;
838}
839
840/// Check if the instruction accessing memory (TheI) can be moved to the
841/// location ToI.
842bool HexagonExpandCondsets::canMoveMemTo(MachineInstr &TheI, MachineInstr &ToI,
843 bool IsDown) {
844 bool IsLoad = TheI.mayLoad(), IsStore = TheI.mayStore();
845 if (!IsLoad && !IsStore)
846 return true;
847 if (HII->areMemAccessesTriviallyDisjoint(TheI, ToI))
848 return true;
849 if (TheI.hasUnmodeledSideEffects())
850 return false;
851
852 MachineBasicBlock::iterator StartI = IsDown ? TheI : ToI;
853 MachineBasicBlock::iterator EndI = IsDown ? ToI : TheI;
854 bool Ordered = TheI.hasOrderedMemoryRef();
855
856 // Search for aliased memory reference in (StartI, EndI).
857 for (MachineInstr &MI : llvm::make_range(std::next(StartI), EndI)) {
858 if (MI.hasUnmodeledSideEffects())
859 return false;
860 bool L = MI.mayLoad(), S = MI.mayStore();
861 if (!L && !S)
862 continue;
863 if (Ordered && MI.hasOrderedMemoryRef())
864 return false;
865
866 bool Conflict = (L && IsStore) || S;
867 if (Conflict)
868 return false;
869 }
870 return true;
871}
872
873/// Generate a predicated version of MI (where the condition is given via
874/// PredR and Cond) at the point indicated by Where.
875void HexagonExpandCondsets::predicateAt(const MachineOperand &DefOp,
878 const MachineOperand &PredOp, bool Cond,
879 std::set<Register> &UpdRegs) {
880 // The problem with updating live intervals is that we can move one def
881 // past another def. In particular, this can happen when moving an A2_tfrt
882 // over an A2_tfrf defining the same register. From the point of view of
883 // live intervals, these two instructions are two separate definitions,
884 // and each one starts another live segment. LiveIntervals's "handleMove"
885 // does not allow such moves, so we need to handle it ourselves. To avoid
886 // invalidating liveness data while we are using it, the move will be
887 // implemented in 4 steps: (1) add a clone of the instruction MI at the
888 // target location, (2) update liveness, (3) delete the old instruction,
889 // and (4) update liveness again.
890
891 MachineBasicBlock &B = *MI.getParent();
892 DebugLoc DL = Where->getDebugLoc(); // "Where" points to an instruction.
893 unsigned Opc = MI.getOpcode();
894 unsigned PredOpc = HII->getCondOpcode(Opc, !Cond);
895 MachineInstrBuilder MB = BuildMI(B, Where, DL, HII->get(PredOpc));
896 unsigned Ox = 0, NP = MI.getNumOperands();
897 // Skip all defs from MI first.
898 while (Ox < NP) {
899 MachineOperand &MO = MI.getOperand(Ox);
900 if (!MO.isReg() || !MO.isDef())
901 break;
902 Ox++;
903 }
904 // Add the new def, then the predicate register, then the rest of the
905 // operands.
906 MB.addReg(DefOp.getReg(), getRegState(DefOp), DefOp.getSubReg());
907 MB.addReg(PredOp.getReg(), PredOp.isUndef() ? RegState::Undef : 0,
908 PredOp.getSubReg());
909 while (Ox < NP) {
910 MachineOperand &MO = MI.getOperand(Ox);
911 if (!MO.isReg() || !MO.isImplicit())
912 MB.add(MO);
913 Ox++;
914 }
915 MB.cloneMemRefs(MI);
916
917 MachineInstr *NewI = MB;
918 NewI->clearKillInfo();
919 LIS->InsertMachineInstrInMaps(*NewI);
920
921 for (auto &Op : NewI->operands()) {
922 if (Op.isReg())
923 UpdRegs.insert(Op.getReg());
924 }
925}
926
927/// In the range [First, Last], rename all references to the "old" register RO
928/// to the "new" register RN, but only in instructions predicated on the given
929/// condition.
930void HexagonExpandCondsets::renameInRange(RegisterRef RO, RegisterRef RN,
931 unsigned PredR, bool Cond, MachineBasicBlock::iterator First,
934 for (MachineInstr &MI : llvm::make_range(First, End)) {
935 // Do not touch instructions that are not predicated, or are predicated
936 // on the opposite condition.
937 if (!HII->isPredicated(MI))
938 continue;
939 if (!MI.readsRegister(PredR) || (Cond != HII->isPredicatedTrue(MI)))
940 continue;
941
942 for (auto &Op : MI.operands()) {
943 if (!Op.isReg() || RO != RegisterRef(Op))
944 continue;
945 Op.setReg(RN.Reg);
946 Op.setSubReg(RN.Sub);
947 // In practice, this isn't supposed to see any defs.
948 assert(!Op.isDef() && "Not expecting a def");
949 }
950 }
951}
952
953/// For a given conditional copy, predicate the definition of the source of
954/// the copy under the given condition (using the same predicate register as
955/// the copy).
956bool HexagonExpandCondsets::predicate(MachineInstr &TfrI, bool Cond,
957 std::set<Register> &UpdRegs) {
958 // TfrI - A2_tfr[tf] Instruction (not A2_tfrsi).
959 unsigned Opc = TfrI.getOpcode();
960 (void)Opc;
961 assert(Opc == Hexagon::A2_tfrt || Opc == Hexagon::A2_tfrf);
962 LLVM_DEBUG(dbgs() << "\nattempt to predicate if-" << (Cond ? "true" : "false")
963 << ": " << TfrI);
964
965 MachineOperand &MD = TfrI.getOperand(0);
966 MachineOperand &MP = TfrI.getOperand(1);
967 MachineOperand &MS = TfrI.getOperand(2);
968 // The source operand should be a <kill>. This is not strictly necessary,
969 // but it makes things a lot simpler. Otherwise, we would need to rename
970 // some registers, which would complicate the transformation considerably.
971 if (!MS.isKill())
972 return false;
973 // Avoid predicating instructions that define a subregister if subregister
974 // liveness tracking is not enabled.
975 if (MD.getSubReg() && !MRI->shouldTrackSubRegLiveness(MD.getReg()))
976 return false;
977
978 RegisterRef RT(MS);
979 Register PredR = MP.getReg();
980 MachineInstr *DefI = getReachingDefForPred(RT, TfrI, PredR, Cond);
981 if (!DefI || !isPredicable(DefI))
982 return false;
983
984 LLVM_DEBUG(dbgs() << "Source def: " << *DefI);
985
986 // Collect the information about registers defined and used between the
987 // DefI and the TfrI.
988 // Map: reg -> bitmask of subregs
989 ReferenceMap Uses, Defs;
990 MachineBasicBlock::iterator DefIt = DefI, TfrIt = TfrI;
991
992 // Check if the predicate register is valid between DefI and TfrI.
993 // If it is, we can then ignore instructions predicated on the negated
994 // conditions when collecting def and use information.
995 bool PredValid = true;
996 for (MachineInstr &MI : llvm::make_range(std::next(DefIt), TfrIt)) {
997 if (!MI.modifiesRegister(PredR, nullptr))
998 continue;
999 PredValid = false;
1000 break;
1001 }
1002
1003 for (MachineInstr &MI : llvm::make_range(std::next(DefIt), TfrIt)) {
1004 // If this instruction is predicated on the same register, it could
1005 // potentially be ignored.
1006 // By default assume that the instruction executes on the same condition
1007 // as TfrI (Exec_Then), and also on the opposite one (Exec_Else).
1008 unsigned Exec = Exec_Then | Exec_Else;
1009 if (PredValid && HII->isPredicated(MI) && MI.readsRegister(PredR))
1010 Exec = (Cond == HII->isPredicatedTrue(MI)) ? Exec_Then : Exec_Else;
1011
1012 for (auto &Op : MI.operands()) {
1013 if (!Op.isReg())
1014 continue;
1015 // We don't want to deal with physical registers. The reason is that
1016 // they can be aliased with other physical registers. Aliased virtual
1017 // registers must share the same register number, and can only differ
1018 // in the subregisters, which we are keeping track of. Physical
1019 // registers ters no longer have subregisters---their super- and
1020 // subregisters are other physical registers, and we are not checking
1021 // that.
1022 RegisterRef RR = Op;
1023 if (!RR.Reg.isVirtual())
1024 return false;
1025
1026 ReferenceMap &Map = Op.isDef() ? Defs : Uses;
1027 if (Op.isDef() && Op.isUndef()) {
1028 assert(RR.Sub && "Expecting a subregister on <def,read-undef>");
1029 // If this is a <def,read-undef>, then it invalidates the non-written
1030 // part of the register. For the purpose of checking the validity of
1031 // the move, assume that it modifies the whole register.
1032 RR.Sub = 0;
1033 }
1034 addRefToMap(RR, Map, Exec);
1035 }
1036 }
1037
1038 // The situation:
1039 // RT = DefI
1040 // ...
1041 // RD = TfrI ..., RT
1042
1043 // If the register-in-the-middle (RT) is used or redefined between
1044 // DefI and TfrI, we may not be able proceed with this transformation.
1045 // We can ignore a def that will not execute together with TfrI, and a
1046 // use that will. If there is such a use (that does execute together with
1047 // TfrI), we will not be able to move DefI down. If there is a use that
1048 // executed if TfrI's condition is false, then RT must be available
1049 // unconditionally (cannot be predicated).
1050 // Essentially, we need to be able to rename RT to RD in this segment.
1051 if (isRefInMap(RT, Defs, Exec_Then) || isRefInMap(RT, Uses, Exec_Else))
1052 return false;
1053 RegisterRef RD = MD;
1054 // If the predicate register is defined between DefI and TfrI, the only
1055 // potential thing to do would be to move the DefI down to TfrI, and then
1056 // predicate. The reaching def (DefI) must be movable down to the location
1057 // of the TfrI.
1058 // If the target register of the TfrI (RD) is not used or defined between
1059 // DefI and TfrI, consider moving TfrI up to DefI.
1060 bool CanUp = canMoveOver(TfrI, Defs, Uses);
1061 bool CanDown = canMoveOver(*DefI, Defs, Uses);
1062 // The TfrI does not access memory, but DefI could. Check if it's safe
1063 // to move DefI down to TfrI.
1064 if (DefI->mayLoadOrStore()) {
1065 if (!canMoveMemTo(*DefI, TfrI, true))
1066 CanDown = false;
1067 }
1068
1069 LLVM_DEBUG(dbgs() << "Can move up: " << (CanUp ? "yes" : "no")
1070 << ", can move down: " << (CanDown ? "yes\n" : "no\n"));
1071 MachineBasicBlock::iterator PastDefIt = std::next(DefIt);
1072 if (CanUp)
1073 predicateAt(MD, *DefI, PastDefIt, MP, Cond, UpdRegs);
1074 else if (CanDown)
1075 predicateAt(MD, *DefI, TfrIt, MP, Cond, UpdRegs);
1076 else
1077 return false;
1078
1079 if (RT != RD) {
1080 renameInRange(RT, RD, PredR, Cond, PastDefIt, TfrIt);
1081 UpdRegs.insert(RT.Reg);
1082 }
1083
1084 removeInstr(TfrI);
1085 removeInstr(*DefI);
1086 return true;
1087}
1088
1089/// Predicate all cases of conditional copies in the specified block.
1090bool HexagonExpandCondsets::predicateInBlock(MachineBasicBlock &B,
1091 std::set<Register> &UpdRegs) {
1092 bool Changed = false;
1094 unsigned Opc = MI.getOpcode();
1095 if (Opc == Hexagon::A2_tfrt || Opc == Hexagon::A2_tfrf) {
1096 bool Done = predicate(MI, (Opc == Hexagon::A2_tfrt), UpdRegs);
1097 if (!Done) {
1098 // If we didn't predicate I, we may need to remove it in case it is
1099 // an "identity" copy, e.g. %1 = A2_tfrt %2, %1.
1100 if (RegisterRef(MI.getOperand(0)) == RegisterRef(MI.getOperand(2))) {
1101 for (auto &Op : MI.operands()) {
1102 if (Op.isReg())
1103 UpdRegs.insert(Op.getReg());
1104 }
1105 removeInstr(MI);
1106 }
1107 }
1108 Changed |= Done;
1109 }
1110 }
1111 return Changed;
1112}
1113
1114bool HexagonExpandCondsets::isIntReg(RegisterRef RR, unsigned &BW) {
1115 if (!RR.Reg.isVirtual())
1116 return false;
1117 const TargetRegisterClass *RC = MRI->getRegClass(RR.Reg);
1118 if (RC == &Hexagon::IntRegsRegClass) {
1119 BW = 32;
1120 return true;
1121 }
1122 if (RC == &Hexagon::DoubleRegsRegClass) {
1123 BW = (RR.Sub != 0) ? 32 : 64;
1124 return true;
1125 }
1126 return false;
1127}
1128
1129bool HexagonExpandCondsets::isIntraBlocks(LiveInterval &LI) {
1130 for (LiveRange::Segment &LR : LI) {
1131 // Range must start at a register...
1132 if (!LR.start.isRegister())
1133 return false;
1134 // ...and end in a register or in a dead slot.
1135 if (!LR.end.isRegister() && !LR.end.isDead())
1136 return false;
1137 }
1138 return true;
1139}
1140
1141bool HexagonExpandCondsets::coalesceRegisters(RegisterRef R1, RegisterRef R2) {
1142 if (CoaLimitActive) {
1143 if (CoaCounter >= CoaLimit)
1144 return false;
1145 CoaCounter++;
1146 }
1147 unsigned BW1, BW2;
1148 if (!isIntReg(R1, BW1) || !isIntReg(R2, BW2) || BW1 != BW2)
1149 return false;
1150 if (MRI->isLiveIn(R1.Reg))
1151 return false;
1152 if (MRI->isLiveIn(R2.Reg))
1153 return false;
1154
1155 LiveInterval &L1 = LIS->getInterval(R1.Reg);
1156 LiveInterval &L2 = LIS->getInterval(R2.Reg);
1157 if (L2.empty())
1158 return false;
1159 if (L1.hasSubRanges() || L2.hasSubRanges())
1160 return false;
1161 bool Overlap = L1.overlaps(L2);
1162
1163 LLVM_DEBUG(dbgs() << "compatible registers: ("
1164 << (Overlap ? "overlap" : "disjoint") << ")\n "
1165 << printReg(R1.Reg, TRI, R1.Sub) << " " << L1 << "\n "
1166 << printReg(R2.Reg, TRI, R2.Sub) << " " << L2 << "\n");
1167 if (R1.Sub || R2.Sub)
1168 return false;
1169 if (Overlap)
1170 return false;
1171
1172 // Coalescing could have a negative impact on scheduling, so try to limit
1173 // to some reasonable extent. Only consider coalescing segments, when one
1174 // of them does not cross basic block boundaries.
1175 if (!isIntraBlocks(L1) && !isIntraBlocks(L2))
1176 return false;
1177
1178 MRI->replaceRegWith(R2.Reg, R1.Reg);
1179
1180 // Move all live segments from L2 to L1.
1181 using ValueInfoMap = DenseMap<VNInfo *, VNInfo *>;
1182 ValueInfoMap VM;
1183 for (LiveRange::Segment &I : L2) {
1184 VNInfo *NewVN, *OldVN = I.valno;
1185 ValueInfoMap::iterator F = VM.find(OldVN);
1186 if (F == VM.end()) {
1187 NewVN = L1.getNextValue(I.valno->def, LIS->getVNInfoAllocator());
1188 VM.insert(std::make_pair(OldVN, NewVN));
1189 } else {
1190 NewVN = F->second;
1191 }
1192 L1.addSegment(LiveRange::Segment(I.start, I.end, NewVN));
1193 }
1194 while (!L2.empty())
1195 L2.removeSegment(*L2.begin());
1196 LIS->removeInterval(R2.Reg);
1197
1198 updateKillFlags(R1.Reg);
1199 LLVM_DEBUG(dbgs() << "coalesced: " << L1 << "\n");
1200 L1.verify();
1201
1202 return true;
1203}
1204
1205/// Attempt to coalesce one of the source registers to a MUX instruction with
1206/// the destination register. This could lead to having only one predicated
1207/// instruction in the end instead of two.
1208bool HexagonExpandCondsets::coalesceSegments(
1210 std::set<Register> &UpdRegs) {
1212 for (MachineInstr *MI : Condsets) {
1213 MachineOperand &S1 = MI->getOperand(2), &S2 = MI->getOperand(3);
1214 if (!S1.isReg() && !S2.isReg())
1215 continue;
1216 TwoRegs.push_back(MI);
1217 }
1218
1219 bool Changed = false;
1220 for (MachineInstr *CI : TwoRegs) {
1221 RegisterRef RD = CI->getOperand(0);
1222 RegisterRef RP = CI->getOperand(1);
1223 MachineOperand &S1 = CI->getOperand(2), &S2 = CI->getOperand(3);
1224 bool Done = false;
1225 // Consider this case:
1226 // %1 = instr1 ...
1227 // %2 = instr2 ...
1228 // %0 = C2_mux ..., %1, %2
1229 // If %0 was coalesced with %1, we could end up with the following
1230 // code:
1231 // %0 = instr1 ...
1232 // %2 = instr2 ...
1233 // %0 = A2_tfrf ..., %2
1234 // which will later become:
1235 // %0 = instr1 ...
1236 // %0 = instr2_cNotPt ...
1237 // i.e. there will be an unconditional definition (instr1) of %0
1238 // followed by a conditional one. The output dependency was there before
1239 // and it unavoidable, but if instr1 is predicable, we will no longer be
1240 // able to predicate it here.
1241 // To avoid this scenario, don't coalesce the destination register with
1242 // a source register that is defined by a predicable instruction.
1243 if (S1.isReg()) {
1244 RegisterRef RS = S1;
1245 MachineInstr *RDef = getReachingDefForPred(RS, CI, RP.Reg, true);
1246 if (!RDef || !HII->isPredicable(*RDef)) {
1247 Done = coalesceRegisters(RD, RegisterRef(S1));
1248 if (Done) {
1249 UpdRegs.insert(RD.Reg);
1250 UpdRegs.insert(S1.getReg());
1251 }
1252 }
1253 }
1254 if (!Done && S2.isReg()) {
1255 RegisterRef RS = S2;
1256 MachineInstr *RDef = getReachingDefForPred(RS, CI, RP.Reg, false);
1257 if (!RDef || !HII->isPredicable(*RDef)) {
1258 Done = coalesceRegisters(RD, RegisterRef(S2));
1259 if (Done) {
1260 UpdRegs.insert(RD.Reg);
1261 UpdRegs.insert(S2.getReg());
1262 }
1263 }
1264 }
1265 Changed |= Done;
1266 }
1267 return Changed;
1268}
1269
1270bool HexagonExpandCondsets::runOnMachineFunction(MachineFunction &MF) {
1271 if (skipFunction(MF.getFunction()))
1272 return false;
1273
1274 HII = static_cast<const HexagonInstrInfo*>(MF.getSubtarget().getInstrInfo());
1276 MDT = &getAnalysis<MachineDominatorTree>();
1277 LIS = &getAnalysis<LiveIntervals>();
1278 MRI = &MF.getRegInfo();
1279
1280 LLVM_DEBUG(LIS->print(dbgs() << "Before expand-condsets\n",
1281 MF.getFunction().getParent()));
1282
1283 bool Changed = false;
1284 std::set<Register> CoalUpd, PredUpd;
1285
1287 for (auto &B : MF) {
1288 for (auto &I : B) {
1289 if (isCondset(I))
1290 Condsets.push_back(&I);
1291 }
1292 }
1293
1294 // Try to coalesce the target of a mux with one of its sources.
1295 // This could eliminate a register copy in some circumstances.
1296 Changed |= coalesceSegments(Condsets, CoalUpd);
1297
1298 // Update kill flags on all source operands. This is done here because
1299 // at this moment (when expand-condsets runs), there are no kill flags
1300 // in the IR (they have been removed by live range analysis).
1301 // Updating them right before we split is the easiest, because splitting
1302 // adds definitions which would interfere with updating kills afterwards.
1303 std::set<Register> KillUpd;
1304 for (MachineInstr *MI : Condsets) {
1305 for (MachineOperand &Op : MI->operands()) {
1306 if (Op.isReg() && Op.isUse()) {
1307 if (!CoalUpd.count(Op.getReg()))
1308 KillUpd.insert(Op.getReg());
1309 }
1310 }
1311 }
1312 updateLiveness(KillUpd, false, true, false);
1313 LLVM_DEBUG(
1314 LIS->print(dbgs() << "After coalescing\n", MF.getFunction().getParent()));
1315
1316 // First, simply split all muxes into a pair of conditional transfers
1317 // and update the live intervals to reflect the new arrangement. The
1318 // goal is to update the kill flags, since predication will rely on
1319 // them.
1320 for (MachineInstr *MI : Condsets)
1321 Changed |= split(*MI, PredUpd);
1322 Condsets.clear(); // The contents of Condsets are invalid here anyway.
1323
1324 // Do not update live ranges after splitting. Recalculation of live
1325 // intervals removes kill flags, which were preserved by splitting on
1326 // the source operands of condsets. These kill flags are needed by
1327 // predication, and after splitting they are difficult to recalculate
1328 // (because of predicated defs), so make sure they are left untouched.
1329 // Predication does not use live intervals.
1330 LLVM_DEBUG(
1331 LIS->print(dbgs() << "After splitting\n", MF.getFunction().getParent()));
1332
1333 // Traverse all blocks and collapse predicable instructions feeding
1334 // conditional transfers into predicated instructions.
1335 // Walk over all the instructions again, so we may catch pre-existing
1336 // cases that were not created in the previous step.
1337 for (auto &B : MF)
1338 Changed |= predicateInBlock(B, PredUpd);
1339 LLVM_DEBUG(LIS->print(dbgs() << "After predicating\n",
1340 MF.getFunction().getParent()));
1341
1342 PredUpd.insert(CoalUpd.begin(), CoalUpd.end());
1343 updateLiveness(PredUpd, true, true, true);
1344
1345 if (Changed)
1346 distributeLiveIntervals(PredUpd);
1347
1348 LLVM_DEBUG({
1349 if (Changed)
1350 LIS->print(dbgs() << "After expand-condsets\n",
1351 MF.getFunction().getParent());
1352 });
1353
1354 return Changed;
1355}
1356
1357//===----------------------------------------------------------------------===//
1358// Public Constructor Functions
1359//===----------------------------------------------------------------------===//
1361 return new HexagonExpandCondsets();
1362}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
SmallVector< MachineOperand, 4 > Cond
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static Error split(StringRef Str, char Separator, std::pair< StringRef, StringRef > &Split)
Checked version of split, to ensure mandatory subparts.
Definition: DataLayout.cpp:235
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
bool End
Definition: ELF_riscv.cpp:464
Rewrite Partial Register Uses
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:26
static cl::opt< unsigned > OptCoaLimit("expand-condsets-coa-limit", cl::init(~0U), cl::Hidden, cl::desc("Max number of segment coalescings"))
expand condsets
static cl::opt< unsigned > OptTfrLimit("expand-condsets-tfr-limit", cl::init(~0U), cl::Hidden, cl::desc("Max number of mux expansions"))
expand Hexagon Expand Condsets
IRTranslator LLVM IR MI
A common definition of LaneBitmask for use in TableGen and CodeGen.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define R2(n)
static unsigned getReg(const MCDisassembler *D, unsigned RC, unsigned RegNo)
#define P(N)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
static void updateLiveness(MachineFunction &MF)
Helper function to update the liveness information for the callee-saved registers.
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
Definition: LiveInterval.h:998
A debug info location.
Definition: DebugLoc.h:33
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:652
A live range for subregisters.
Definition: LiveInterval.h:693
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
Register reg() const
Definition: LiveInterval.h:717
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:803
void verify(const MachineRegisterInfo *MRI=nullptr) const
Walks the interval and assert if any invariants fail to hold.
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:775
void computeSubRangeUndefs(SmallVectorImpl< SlotIndex > &Undefs, LaneBitmask LaneMask, const MachineRegisterInfo &MRI, const SlotIndexes &Indexes) const
For a given lane mask LaneMask, compute indexes at which the lane is marked undefined by subregister ...
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
bool empty() const
Definition: LiveInterval.h:382
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
Definition: LiveInterval.h:448
iterator end()
Definition: LiveInterval.h:216
iterator begin()
Definition: LiveInterval.h:215
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:331
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineInstrBuilder & add(const MachineOperand &MO) const
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & cloneMemRefs(const MachineInstr &OtherMI) const
Representation of each machine instruction.
Definition: MachineInstr.h:68
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:523
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:320
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:526
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore,...
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:648
void tieOperands(unsigned DefIdx, unsigned UseIdx)
Add a tie between the register operands at DefIdx and UseIdx.
bool hasOrderedMemoryRef() const
Return true if this instruction may have an ordered or volatile memory reference, or if the informati...
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:533
void clearKillInfo()
Clears kill flags on all operands.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool isImplicit() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineOperandType getType() const
getType - Returns the MachineOperandType for this operand.
Register getReg() const
getReg - Returns the register number.
@ MO_Immediate
Immediate operand.
@ MO_ConstantPoolIndex
Address of indexed Constant in Constant Pool.
@ MO_GlobalAddress
Address of a global value.
@ MO_BlockAddress
Address of a basic block.
@ MO_ExternalSymbol
Name of external global symbol.
@ MO_JumpTableIndex
Address of indexed Jump Table for switch.
@ MO_TargetIndex
Target-dependent index+offset operand.
@ MO_FPImmediate
Floating-point immediate operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:37
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
A vector that has set insertion semantics.
Definition: SetVector.h:51
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:152
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
SlotIndexes pass.
Definition: SlotIndexes.h:319
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Register getReg() const
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:119
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ Implicit
Not emitted register (e.g. carry, or temporary result).
@ Define
Register definition.
@ Undef
Value of the register doesn't matter.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
constexpr double e
Definition: MathExtras.h:31
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:361
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
@ Done
Definition: Threading.h:61
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2052
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:748
FunctionPass * createHexagonExpandCondsets()
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
void initializeHexagonExpandCondsetsPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
unsigned getRegState(const MachineOperand &RegOp)
Get all register state flags from machine operand RegOp.
char & HexagonExpandCondsetsID
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162