contrib/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp

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