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