xref: /freebsd/contrib/llvm-project/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp (revision e1e636193db45630c7881246d25902e57c43d24e)
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"
92 #include "llvm/ADT/SmallVector.h"
93 #include "llvm/ADT/StringRef.h"
94 #include "llvm/CodeGen/LiveInterval.h"
95 #include "llvm/CodeGen/LiveIntervals.h"
96 #include "llvm/CodeGen/MachineBasicBlock.h"
97 #include "llvm/CodeGen/MachineDominators.h"
98 #include "llvm/CodeGen/MachineFunction.h"
99 #include "llvm/CodeGen/MachineFunctionPass.h"
100 #include "llvm/CodeGen/MachineInstr.h"
101 #include "llvm/CodeGen/MachineInstrBuilder.h"
102 #include "llvm/CodeGen/MachineOperand.h"
103 #include "llvm/CodeGen/MachineRegisterInfo.h"
104 #include "llvm/CodeGen/SlotIndexes.h"
105 #include "llvm/CodeGen/TargetRegisterInfo.h"
106 #include "llvm/CodeGen/TargetSubtargetInfo.h"
107 #include "llvm/IR/DebugLoc.h"
108 #include "llvm/IR/Function.h"
109 #include "llvm/InitializePasses.h"
110 #include "llvm/MC/LaneBitmask.h"
111 #include "llvm/Pass.h"
112 #include "llvm/Support/CommandLine.h"
113 #include "llvm/Support/Debug.h"
114 #include "llvm/Support/ErrorHandling.h"
115 #include "llvm/Support/raw_ostream.h"
116 #include <cassert>
117 #include <iterator>
118 #include <map>
119 #include <set>
120 #include <utility>
121 
122 #define DEBUG_TYPE "expand-condsets"
123 
124 using namespace llvm;
125 
126 static cl::opt<unsigned> OptTfrLimit("expand-condsets-tfr-limit",
127   cl::init(~0U), cl::Hidden, cl::desc("Max number of mux expansions"));
128 static cl::opt<unsigned> OptCoaLimit("expand-condsets-coa-limit",
129   cl::init(~0U), cl::Hidden, cl::desc("Max number of segment coalescings"));
130 
131 namespace llvm {
132 
133   void initializeHexagonExpandCondsetsPass(PassRegistry&);
134   FunctionPass *createHexagonExpandCondsets();
135 
136 } // end namespace llvm
137 
138 namespace {
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;
149       initializeHexagonExpandCondsetsPass(*PassRegistry::getPassRegistry());
150     }
151 
152     StringRef getPassName() const override { return "Hexagon Expand Condsets"; }
153 
154     void getAnalysisUsage(AnalysisUsage &AU) const override {
155       AU.addRequired<LiveIntervals>();
156       AU.addPreserved<LiveIntervals>();
157       AU.addPreserved<SlotIndexes>();
158       AU.addRequired<MachineDominatorTree>();
159       AU.addPreserved<MachineDominatorTree>();
160       MachineFunctionPass::getAnalysisUsage(AU);
161     }
162 
163     bool runOnMachineFunction(MachineFunction &MF) override;
164 
165   private:
166     const HexagonInstrInfo *HII = nullptr;
167     const TargetRegisterInfo *TRI = nullptr;
168     MachineDominatorTree *MDT;
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 
192       Register Reg;
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,
229                      MachineBasicBlock::iterator Where,
230                      const MachineOperand &PredOp, bool Cond,
231                      std::set<Register> &UpdRegs);
232     void renameInRange(RegisterRef RO, RegisterRef RN, unsigned PredR,
233         bool Cond, MachineBasicBlock::iterator First,
234         MachineBasicBlock::iterator Last);
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 
247 char HexagonExpandCondsets::ID = 0;
248 
249 namespace llvm {
250 
251   char &HexagonExpandCondsetsID = HexagonExpandCondsets::ID;
252 
253 } // end namespace llvm
254 
255 INITIALIZE_PASS_BEGIN(HexagonExpandCondsets, "expand-condsets",
256   "Hexagon Expand Condsets", false, false)
257 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
258 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
259 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
260 INITIALIZE_PASS_END(HexagonExpandCondsets, "expand-condsets",
261   "Hexagon Expand Condsets", false, false)
262 
263 unsigned 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 
277 bool 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 
291 LaneBitmask HexagonExpandCondsets::getLaneMask(Register Reg, unsigned Sub) {
292   assert(Reg.isVirtual());
293   return Sub != 0 ? TRI->getSubRegIndexLaneMask(Sub)
294                   : MRI->getMaxLaneMaskForVReg(Reg);
295 }
296 
297 void 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 
307 bool 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 
318 void 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 
369 void 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.
417   SetVector<MachineBasicBlock*> Defs;
418   SmallVector<SlotIndex,4> PredDefs;
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 
428   SmallVector<SlotIndex,8> Undefs;
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.
441   SmallVector<SlotIndex,4> ExtTo;
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 
529 void 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 
543 void HexagonExpandCondsets::recalculateLiveInterval(Register Reg) {
544   LIS->removeInterval(Reg);
545   LIS->createAndComputeVirtRegInterval(Reg);
546 }
547 
548 void HexagonExpandCondsets::removeInstr(MachineInstr &MI) {
549   LIS->RemoveMachineInstrFromMaps(MI);
550   MI.eraseFromParent();
551 }
552 
553 void 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 
579 void 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 
590     SmallVector<LiveInterval*> NewLIs;
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.
602 unsigned 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()) {
625     case MachineOperand::MO_Immediate:
626     case MachineOperand::MO_FPImmediate:
627     case MachineOperand::MO_ConstantPoolIndex:
628     case MachineOperand::MO_TargetIndex:
629     case MachineOperand::MO_JumpTableIndex:
630     case MachineOperand::MO_ExternalSymbol:
631     case MachineOperand::MO_GlobalAddress:
632     case MachineOperand::MO_BlockAddress:
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).
644 MachineInstr *HexagonExpandCondsets::genCondTfrFor(MachineOperand &SrcOp,
645       MachineBasicBlock::iterator At,
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;
661   MachineInstrBuilder MIB;
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.
684 bool 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();
698   MachineBasicBlock::iterator At = MI;
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 
744 bool 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.
768 MachineInstr *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.
817 bool 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.
843 bool 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.
876 void HexagonExpandCondsets::predicateAt(const MachineOperand &DefOp,
877                                         MachineInstr &MI,
878                                         MachineBasicBlock::iterator Where,
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.
931 void HexagonExpandCondsets::renameInRange(RegisterRef RO, RegisterRef RN,
932       unsigned PredR, bool Cond, MachineBasicBlock::iterator First,
933       MachineBasicBlock::iterator Last) {
934   MachineBasicBlock::iterator End = std::next(Last);
935   for (MachineInstr &MI : llvm::make_range(First, End)) {
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).
957 bool 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.
1091 bool HexagonExpandCondsets::predicateInBlock(MachineBasicBlock &B,
1092                                              std::set<Register> &UpdRegs) {
1093   bool Changed = false;
1094   for (MachineInstr &MI : llvm::make_early_inc_range(B)) {
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 
1115 bool 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 
1130 bool 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 
1142 bool 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.
1209 bool HexagonExpandCondsets::coalesceSegments(
1210     const SmallVectorImpl<MachineInstr *> &Condsets,
1211     std::set<Register> &UpdRegs) {
1212   SmallVector<MachineInstr*,16> TwoRegs;
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 
1271 bool HexagonExpandCondsets::runOnMachineFunction(MachineFunction &MF) {
1272   if (skipFunction(MF.getFunction()))
1273     return false;
1274 
1275   HII = static_cast<const HexagonInstrInfo*>(MF.getSubtarget().getInstrInfo());
1276   TRI = MF.getSubtarget().getRegisterInfo();
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 
1287   SmallVector<MachineInstr*,16> Condsets;
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 //===----------------------------------------------------------------------===//
1361 FunctionPass *llvm::createHexagonExpandCondsets() {
1362   return new HexagonExpandCondsets();
1363 }
1364