121 #define DEBUG_TYPE "expand-condsets"
123 using namespace llvm;
151 StringRef getPassName()
const override {
return "Hexagon Expand Condsets"; }
170 bool CoaLimitActive =
false;
171 bool TfrLimitActive =
false;
174 unsigned CoaCounter = 0;
175 unsigned TfrCounter = 0;
180 Sub(
Op.getSubReg()) {}
181 RegisterRef(
unsigned R = 0,
unsigned S = 0) :
Reg(
R), Sub(
S) {}
184 return Reg == RR.Reg && Sub == RR.Sub;
188 return Reg < RR.Reg || (
Reg == RR.Reg && Sub < RR.Sub);
196 enum { Sub_Low = 0x1, Sub_High = 0x2, Sub_None = (Sub_Low | Sub_High) };
197 enum { Exec_Then = 0x10, Exec_Else = 0x20 };
199 unsigned getMaskForSub(
unsigned Sub);
203 void addRefToMap(RegisterRef RR, ReferenceMap &Map,
unsigned Exec);
204 bool isRefInMap(RegisterRef, ReferenceMap &Map,
unsigned Exec);
211 void updateLiveness(
const std::set<Register> &RegSet,
bool Recalc,
212 bool UpdateKills,
bool UpdateDeads);
213 void distributeLiveIntervals(
const std::set<Register> &Regs);
219 bool ReadUndef,
bool ImpUse);
230 std::set<Register> &UpdRegs);
231 void renameInRange(RegisterRef RO, RegisterRef
RN,
unsigned PredR,
237 bool isIntReg(RegisterRef RR,
unsigned &BW);
239 bool coalesceRegisters(RegisterRef R1, RegisterRef
R2);
241 std::set<Register> &UpdRegs);
255 "Hexagon Expand Condsets",
false,
false)
262 unsigned HexagonExpandCondsets::getMaskForSub(
unsigned Sub) {
264 case Hexagon::isub_lo:
265 case Hexagon::vsub_lo:
267 case Hexagon::isub_hi:
268 case Hexagon::vsub_hi:
270 case Hexagon::NoSubRegister:
277 unsigned Opc =
MI.getOpcode();
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:
296 void HexagonExpandCondsets::addRefToMap(RegisterRef RR, ReferenceMap &Map,
298 unsigned Mask = getMaskForSub(RR.Sub) |
Exec;
299 ReferenceMap::iterator
F =
Map.find(RR.Reg);
301 Map.insert(std::make_pair(RR.Reg,
Mask));
306 bool HexagonExpandCondsets::isRefInMap(RegisterRef RR, ReferenceMap &Map,
308 ReferenceMap::iterator
F =
Map.find(RR.Reg);
311 unsigned Mask = getMaskForSub(RR.Sub) |
Exec;
312 if (
Mask &
F->second)
317 void HexagonExpandCondsets::updateKillFlags(
Register Reg) {
321 for (
unsigned i = 0,
e =
MI->getNumOperands();
i !=
e; ++
i) {
323 if (!
Op.isReg() || !
Op.isUse() ||
Op.getReg() !=
Reg ||
324 MI->isRegTiedToDefOperand(
i))
327 if ((SLM & LM) == SLM) {
338 if (!
I->end.isRegister())
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))
348 bool WholeReg =
true;
352 return F !=
S.end() &&
I->end ==
F->end;
358 KillAt(
I->end,
S.LaneMask);
376 if (!
Op.isReg() || !
Op.isDef())
377 return {
false,
false };
380 return {
false,
false };
383 return {
A.any(),
A == SLM };
396 if (
D != Dest && MDT->dominates(
D, Dest))
401 for (
unsigned i = 0;
i < Work.size(); ++
i) {
407 for (
auto *
P :
B->predecessors())
418 for (
auto &Seg : Range) {
419 if (!Seg.start.isRegister())
421 MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
423 if (HII->isPredicated(*DefI))
424 PredDefs.push_back(Seg.start);
431 for (
auto &
SI : PredDefs) {
433 auto P =
Range.extendInBlock(Undefs, LIS->getMBBStartIdx(
BB),
SI);
434 if (
P.first !=
nullptr ||
P.second)
441 for (
auto &
SI : PredDefs) {
445 if (
BB->pred_empty())
457 if (Dominate(Defs,
BB))
462 LIS->extendToIndices(Range, ExtTo, Undefs);
471 std::set<RegisterRef> DefRegs;
472 for (
auto &Seg : Range) {
473 if (!Seg.start.isRegister())
475 MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
477 auto P = IsRegDef(
Op);
478 if (
P.second && Seg.end.isDead()) {
480 }
else if (
P.first) {
489 for (
auto &Seg : Range) {
490 if (!Seg.start.isRegister() || !
Range.liveAt(Seg.start.getPrevSlot()))
492 MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
493 if (!HII->isPredicated(*DefI))
498 std::map<RegisterRef,unsigned> ImpUses;
501 if (!
Op.isReg() || !DefRegs.count(
Op))
507 ImpUses.insert({
Op,
i});
521 for (
auto [R, DefIdx] : ImpUses) {
528 void HexagonExpandCondsets::updateDeadFlags(
Register Reg) {
532 updateDeadsInRange(
Reg,
S.LaneMask,
S);
533 LIS->shrinkToUses(
S,
Reg);
536 LIS->constructMainRangeFromSubranges(LI);
542 void HexagonExpandCondsets::recalculateLiveInterval(
Register Reg) {
543 LIS->removeInterval(
Reg);
544 LIS->createAndComputeVirtRegInterval(
Reg);
548 LIS->RemoveMachineInstrFromMaps(
MI);
549 MI.eraseFromParent();
553 bool Recalc,
bool UpdateKills,
555 UpdateKills |= UpdateDeads;
557 if (!
R.isVirtual()) {
565 recalculateLiveInterval(R);
574 LIS->getInterval(R).verify();
578 void HexagonExpandCondsets::distributeLiveIntervals(
579 const std::set<Register> &Regs) {
585 unsigned NumComp = EQC.Classify(LI);
591 for (
unsigned I = 1;
I < NumComp; ++
I) {
593 NewLIs.push_back(&LIS->createEmptyInterval(NewR));
595 EQC.Distribute(LI, NewLIs.begin(), *
MRI);
601 unsigned HexagonExpandCondsets::getCondTfrOpcode(
const MachineOperand &SO,
606 if (RS.Reg.isVirtual()) {
608 assert(
VC->begin() !=
VC->end() &&
"Empty register class");
609 PhysR = *
VC->begin();
617 return IfTrue ? Hexagon::A2_tfrt : Hexagon::A2_tfrf;
619 return IfTrue ? Hexagon::A2_tfrpt : Hexagon::A2_tfrpf;
632 return IfTrue ? Hexagon::C2_cmoveit : Hexagon::C2_cmoveif;
646 bool PredSense,
bool ReadUndef,
bool ImpUse) {
657 unsigned Opc = getCondTfrOpcode(
SrcOp, PredSense);
664 if (RegisterRef(
SrcOp) == RegisterRef(DstR, DstSR))
665 SrcState &= ~RegState
::Kill;
667 .
addReg(DstR, DstState, DstSR)
672 .
addReg(DstR, DstState, DstSR)
684 std::set<Register> &UpdRegs) {
685 if (TfrLimitActive) {
686 if (TfrCounter >= TfrLimit)
700 for (
auto &
Op :
MI.operands()) {
702 UpdRegs.insert(
Op.getReg());
711 if (
ST.isReg() && SF.
isReg()) {
713 if (RT == RegisterRef(SF)) {
716 MI.setDesc(HII->get(TargetOpcode::COPY));
718 while (
MI.getNumOperands() > 1)
719 MI.removeOperand(
MI.getNumOperands()-1);
730 genCondTfrFor(
ST, At, DR, DSR, MP,
true, ReadUndef,
false);
732 genCondTfrFor(SF, At, DR, DSR, MP,
false, ReadUndef,
true);
733 LIS->InsertMachineInstrInMaps(*TfrT);
734 LIS->InsertMachineInstrInMaps(*TfrF);
744 if (HII->isPredicated(*
MI) || !HII->isPredicable(*
MI))
746 if (
MI->hasUnmodeledSideEffects() ||
MI->mayStore())
750 for (
auto &
Op :
MI->operands()) {
751 if (!
Op.isReg() || !
Op.isDef())
757 for (
auto &Mo :
MI->memoperands()) {
758 if (Mo->isVolatile() || Mo->isAtomic())
767 MachineInstr *HexagonExpandCondsets::getReachingDefForPred(RegisterRef RD,
774 bool PredValid =
true;
780 if (PredValid && HII->isPredicated(*
MI)) {
781 if (
MI->readsRegister(PredR) && (
Cond != HII->isPredicatedTrue(*
MI)))
787 for (
auto &
Op :
MI->operands()) {
788 if (!
Op.isReg() || !
Op.isDef())
791 if (RR.Reg == PredR) {
795 if (RR.Reg != RD.Reg)
800 if (RR.Sub == RD.Sub)
802 if (RR.Sub == 0 || RD.Sub == 0)
816 bool HexagonExpandCondsets::canMoveOver(
MachineInstr &
MI, ReferenceMap &Defs,
817 ReferenceMap &
Uses) {
821 for (
auto &
Op :
MI.operands()) {
828 if (!RR.Reg.isVirtual())
831 if (isRefInMap(RR, Defs, Exec_Then))
834 if (
Op.isDef() && isRefInMap(RR,
Uses, Exec_Then))
845 if (!IsLoad && !IsStore)
847 if (HII->areMemAccessesTriviallyDisjoint(TheI, ToI))
858 if (
MI.hasUnmodeledSideEffects())
860 bool L =
MI.mayLoad(),
S =
MI.mayStore();
863 if (Ordered &&
MI.hasOrderedMemoryRef())
866 bool Conflict = (L && IsStore) ||
S;
875 void HexagonExpandCondsets::predicateAt(
const MachineOperand &DefOp,
879 std::set<Register> &UpdRegs) {
893 unsigned Opc =
MI.getOpcode();
894 unsigned PredOpc = HII->getCondOpcode(Opc, !
Cond);
896 unsigned Ox = 0, NP =
MI.getNumOperands();
919 LIS->InsertMachineInstrInMaps(*NewI);
923 UpdRegs.insert(
Op.getReg());
930 void HexagonExpandCondsets::renameInRange(RegisterRef RO, RegisterRef
RN,
937 if (!HII->isPredicated(
MI))
939 if (!
MI.readsRegister(PredR) || (
Cond != HII->isPredicatedTrue(
MI)))
942 for (
auto &
Op :
MI.operands()) {
943 if (!
Op.isReg() || RO != RegisterRef(
Op))
946 Op.setSubReg(
RN.Sub);
948 assert(!
Op.isDef() &&
"Not expecting a def");
957 std::set<Register> &UpdRegs) {
961 assert(Opc == Hexagon::A2_tfrt || Opc == Hexagon::A2_tfrf);
981 if (!DefI || !isPredicable(DefI))
989 ReferenceMap
Uses, Defs;
995 bool PredValid =
true;
997 if (!
MI.modifiesRegister(PredR,
nullptr))
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;
1012 for (
auto &
Op :
MI.operands()) {
1022 RegisterRef RR =
Op;
1023 if (!RR.Reg.isVirtual())
1026 ReferenceMap &
Map =
Op.isDef() ? Defs :
Uses;
1027 if (
Op.isDef() &&
Op.isUndef()) {
1028 assert(RR.Sub &&
"Expecting a subregister on <def,read-undef>");
1034 addRefToMap(RR, Map, Exec);
1051 if (isRefInMap(RT, Defs, Exec_Then) || isRefInMap(RT,
Uses, Exec_Else))
1053 RegisterRef RD = MD;
1060 bool CanUp = canMoveOver(TfrI, Defs,
Uses);
1061 bool CanDown = canMoveOver(*DefI, Defs,
Uses);
1065 if (!canMoveMemTo(*DefI, TfrI,
true))
1070 <<
", can move down: " << (CanDown ?
"yes\n" :
"no\n"));
1073 predicateAt(MD, *DefI, PastDefIt, MP,
Cond, UpdRegs);
1075 predicateAt(MD, *DefI, TfrIt, MP,
Cond, UpdRegs);
1080 renameInRange(RT, RD, PredR,
Cond, PastDefIt, TfrIt);
1081 UpdRegs.insert(RT.Reg);
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);
1100 if (RegisterRef(
MI.getOperand(0)) == RegisterRef(
MI.getOperand(2))) {
1101 for (
auto &
Op :
MI.operands()) {
1103 UpdRegs.insert(
Op.getReg());
1115 if (!RR.Reg.isVirtual())
1118 if (RC == &Hexagon::IntRegsRegClass) {
1122 if (RC == &Hexagon::DoubleRegsRegClass) {
1123 BW = (RR.Sub != 0) ? 32 : 64;
1129 bool HexagonExpandCondsets::isIntraBlocks(
LiveInterval &LI) {
1132 if (!LR.start.isRegister())
1135 if (!LR.end.isRegister() && !LR.end.isDead())
1141 bool HexagonExpandCondsets::coalesceRegisters(RegisterRef R1, RegisterRef
R2) {
1142 if (CoaLimitActive) {
1143 if (CoaCounter >= CoaLimit)
1164 << (Overlap ?
"overlap" :
"disjoint") <<
")\n "
1165 <<
printReg(R1.Reg,
TRI, R1.Sub) <<
" " << L1 <<
"\n "
1167 if (R1.Sub ||
R2.Sub)
1175 if (!isIntraBlocks(L1) && !isIntraBlocks(
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));
1195 L2.removeSegment(*
L2.begin());
1196 LIS->removeInterval(
R2.Reg);
1198 updateKillFlags(R1.Reg);
1208 bool HexagonExpandCondsets::coalesceSegments(
1210 std::set<Register> &UpdRegs) {
1214 if (!S1.
isReg() && !S2.isReg())
1216 TwoRegs.push_back(
MI);
1219 bool Changed =
false;
1221 RegisterRef RD = CI->getOperand(0);
1222 RegisterRef
RP = CI->getOperand(1);
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));
1249 UpdRegs.insert(RD.Reg);
1250 UpdRegs.insert(S1.
getReg());
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));
1260 UpdRegs.insert(RD.Reg);
1261 UpdRegs.insert(S2.getReg());
1270 bool HexagonExpandCondsets::runOnMachineFunction(
MachineFunction &MF) {
1276 MDT = &getAnalysis<MachineDominatorTree>();
1277 LIS = &getAnalysis<LiveIntervals>();
1283 bool Changed =
false;
1284 std::set<Register> CoalUpd, PredUpd;
1287 for (
auto &
B : MF) {
1296 Changed |= coalesceSegments(
Condsets, CoalUpd);
1303 std::set<Register> KillUpd;
1306 if (
Op.isReg() &&
Op.isUse()) {
1307 if (!CoalUpd.count(
Op.getReg()))
1308 KillUpd.insert(
Op.getReg());
1314 LIS->print(
dbgs() <<
"After coalescing\n", MF.getFunction().getParent()));
1321 Changed |=
split(*
MI, PredUpd);
1331 LIS->print(
dbgs() <<
"After splitting\n", MF.getFunction().getParent()));
1338 Changed |= predicateInBlock(
B, PredUpd);
1340 MF.getFunction().getParent()));
1342 PredUpd.insert(CoalUpd.begin(), CoalUpd.end());
1346 distributeLiveIntervals(PredUpd);
1350 LIS->print(
dbgs() <<
"After expand-condsets\n",
1351 MF.getFunction().getParent());
1361 return new HexagonExpandCondsets();