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