lib/Target/Hexagon/HexagonGenMux.cpp

   1 //===- HexagonGenMux.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 // During instruction selection, MUX instructions are generated for
  10 // conditional assignments. Since such assignments often present an
  11 // opportunity to predicate instructions, HexagonExpandCondsets
  12 // expands MUXes into pairs of conditional transfers, and then proceeds
  13 // with predication of the producers/consumers of the registers involved.
  14 // This happens after exiting from the SSA form, but before the machine
  15 // instruction scheduler. After the scheduler and after the register
  16 // allocation there can be cases of pairs of conditional transfers
  17 // resulting from a MUX where neither of them was further predicated. If
  18 // these transfers are now placed far enough from the instruction defining
  19 // the predicate register, they cannot use the .new form. In such cases it
  20 // is better to collapse them back to a single MUX instruction.
  21
  22 #define DEBUG_TYPE "hexmux"
  23
  24 #include "HexagonInstrInfo.h"
  25 #include "HexagonRegisterInfo.h"
  26 #include "HexagonSubtarget.h"
  27 #include "llvm/ADT/BitVector.h"
  28 #include "llvm/ADT/DenseMap.h"
  29 #include "llvm/ADT/SmallVector.h"
  30 #include "llvm/ADT/StringRef.h"
  31 #include "llvm/CodeGen/LivePhysRegs.h"
  32 #include "llvm/CodeGen/MachineBasicBlock.h"
  33 #include "llvm/CodeGen/MachineFunction.h"
  34 #include "llvm/CodeGen/MachineFunctionPass.h"
  35 #include "llvm/CodeGen/MachineInstr.h"
  36 #include "llvm/CodeGen/MachineInstrBuilder.h"
  37 #include "llvm/CodeGen/MachineOperand.h"
  38 #include "llvm/IR/DebugLoc.h"
  39 #include "llvm/MC/MCInstrDesc.h"
  40 #include "llvm/MC/MCRegisterInfo.h"
  41 #include "llvm/Pass.h"
  42 #include "llvm/Support/CommandLine.h"
  43 #include "llvm/Support/MathExtras.h"
  44 #include <algorithm>
  45 #include <cassert>
  46 #include <iterator>
  47 #include <limits>
  48 #include <utility>
  49
  50 using namespace llvm;
  51
  52 namespace llvm {
  53
  54   FunctionPass *createHexagonGenMux();
  55   void initializeHexagonGenMuxPass(PassRegistry& Registry);
  56
  57 } // end namespace llvm
  58
  59 // Initialize this to 0 to always prefer generating mux by default.
  60 static cl::opt<unsigned> MinPredDist("hexagon-gen-mux-threshold", cl::Hidden,
  61   cl::init(0), cl::desc("Minimum distance between predicate definition and "
  62   "farther of the two predicated uses"));
  63
  64 namespace {
  65
  66   class HexagonGenMux : public MachineFunctionPass {
  67   public:
  68     static char ID;
  69
  70     HexagonGenMux() : MachineFunctionPass(ID) {}
  71
  72     StringRef getPassName() const override {
  73       return "Hexagon generate mux instructions";
  74     }
  75
  76     void getAnalysisUsage(AnalysisUsage &AU) const override {
  77       MachineFunctionPass::getAnalysisUsage(AU);
  78     }
  79
  80     bool runOnMachineFunction(MachineFunction &MF) override;
  81
  82     MachineFunctionProperties getRequiredProperties() const override {
  83       return MachineFunctionProperties().set(
  84           MachineFunctionProperties::Property::NoVRegs);
  85     }
  86
  87   private:
  88     const HexagonInstrInfo *HII = nullptr;
  89     const HexagonRegisterInfo *HRI = nullptr;
  90
  91     struct CondsetInfo {
  92       unsigned PredR = 0;
  93       unsigned TrueX = std::numeric_limits<unsigned>::max();
  94       unsigned FalseX = std::numeric_limits<unsigned>::max();
  95
  96       CondsetInfo() = default;
  97     };
  98
  99     struct DefUseInfo {
 100       BitVector Defs, Uses;
 101
 102       DefUseInfo() = default;
 103       DefUseInfo(const BitVector &D, const BitVector &U) : Defs(D), Uses(U) {}
 104     };
 105
 106     struct MuxInfo {
 107       MachineBasicBlock::iterator At;
 108       unsigned DefR, PredR;
 109       MachineOperand *SrcT, *SrcF;
 110       MachineInstr *Def1, *Def2;
 111
 112       MuxInfo(MachineBasicBlock::iterator It, unsigned DR, unsigned PR,
 113               MachineOperand *TOp, MachineOperand *FOp, MachineInstr &D1,
 114               MachineInstr &D2)
 115           : At(It), DefR(DR), PredR(PR), SrcT(TOp), SrcF(FOp), Def1(&D1),
 116             Def2(&D2) {}
 117     };
 118
 119     using InstrIndexMap = DenseMap<MachineInstr *, unsigned>;
 120     using DefUseInfoMap = DenseMap<unsigned, DefUseInfo>;
 121     using MuxInfoList = SmallVector<MuxInfo, 4>;
 122
 123     bool isRegPair(unsigned Reg) const {
 124       return Hexagon::DoubleRegsRegClass.contains(Reg);
 125     }
 126
 127     void getSubRegs(unsigned Reg, BitVector &SRs) const;
 128     void expandReg(unsigned Reg, BitVector &Set) const;
 129     void getDefsUses(const MachineInstr *MI, BitVector &Defs,
 130           BitVector &Uses) const;
 131     void buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X,
 132           DefUseInfoMap &DUM);
 133     bool isCondTransfer(unsigned Opc) const;
 134     unsigned getMuxOpcode(const MachineOperand &Src1,
 135           const MachineOperand &Src2) const;
 136     bool genMuxInBlock(MachineBasicBlock &B);
 137   };
 138
 139 } // end anonymous namespace
 140
 141 char HexagonGenMux::ID = 0;
 142
 143 INITIALIZE_PASS(HexagonGenMux, "hexagon-gen-mux",
 144   "Hexagon generate mux instructions", false, false)
 145
 146 void HexagonGenMux::getSubRegs(unsigned Reg, BitVector &SRs) const {
 147   for (MCSubRegIterator I(Reg, HRI); I.isValid(); ++I)
 148     SRs[*I] = true;
 149 }
 150
 151 void HexagonGenMux::expandReg(unsigned Reg, BitVector &Set) const {
 152   if (isRegPair(Reg))
 153     getSubRegs(Reg, Set);
 154   else
 155     Set[Reg] = true;
 156 }
 157
 158 void HexagonGenMux::getDefsUses(const MachineInstr *MI, BitVector &Defs,
 159       BitVector &Uses) const {
 160   // First, get the implicit defs and uses for this instruction.
 161   unsigned Opc = MI->getOpcode();
 162   const MCInstrDesc &D = HII->get(Opc);
 163   if (const MCPhysReg *R = D.ImplicitDefs)
 164     while (*R)
 165       expandReg(*R++, Defs);
 166   if (const MCPhysReg *R = D.ImplicitUses)
 167     while (*R)
 168       expandReg(*R++, Uses);
 169
 170   // Look over all operands, and collect explicit defs and uses.
 171   for (const MachineOperand &MO : MI->operands()) {
 172     if (!MO.isReg() || MO.isImplicit())
 173       continue;
 174     Register R = MO.getReg();
 175     BitVector &Set = MO.isDef() ? Defs : Uses;
 176     expandReg(R, Set);
 177   }
 178 }
 179
 180 void HexagonGenMux::buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X,
 181       DefUseInfoMap &DUM) {
 182   unsigned Index = 0;
 183   unsigned NR = HRI->getNumRegs();
 184   BitVector Defs(NR), Uses(NR);
 185
 186   for (MachineBasicBlock::iterator I = B.begin(), E = B.end(); I != E; ++I) {
 187     MachineInstr *MI = &*I;
 188     I2X.insert(std::make_pair(MI, Index));
 189     Defs.reset();
 190     Uses.reset();
 191     getDefsUses(MI, Defs, Uses);
 192     DUM.insert(std::make_pair(Index, DefUseInfo(Defs, Uses)));
 193     Index++;
 194   }
 195 }
 196
 197 bool HexagonGenMux::isCondTransfer(unsigned Opc) const {
 198   switch (Opc) {
 199     case Hexagon::A2_tfrt:
 200     case Hexagon::A2_tfrf:
 201     case Hexagon::C2_cmoveit:
 202     case Hexagon::C2_cmoveif:
 203       return true;
 204   }
 205   return false;
 206 }
 207
 208 unsigned HexagonGenMux::getMuxOpcode(const MachineOperand &Src1,
 209       const MachineOperand &Src2) const {
 210   bool IsReg1 = Src1.isReg(), IsReg2 = Src2.isReg();
 211   if (IsReg1)
 212     return IsReg2 ? Hexagon::C2_mux : Hexagon::C2_muxir;
 213   if (IsReg2)
 214     return Hexagon::C2_muxri;
 215
 216   // Neither is a register. The first source is extendable, but the second
 217   // is not (s8).
 218   if (Src2.isImm() && isInt<8>(Src2.getImm()))
 219     return Hexagon::C2_muxii;
 220
 221   return 0;
 222 }
 223
 224 bool HexagonGenMux::genMuxInBlock(MachineBasicBlock &B) {
 225   bool Changed = false;
 226   InstrIndexMap I2X;
 227   DefUseInfoMap DUM;
 228   buildMaps(B, I2X, DUM);
 229
 230   using CondsetMap = DenseMap<unsigned, CondsetInfo>;
 231
 232   CondsetMap CM;
 233   MuxInfoList ML;
 234
 235   MachineBasicBlock::iterator NextI, End = B.end();
 236   for (MachineBasicBlock::iterator I = B.begin(); I != End; I = NextI) {
 237     MachineInstr *MI = &*I;
 238     NextI = std::next(I);
 239     unsigned Opc = MI->getOpcode();
 240     if (!isCondTransfer(Opc))
 241       continue;
 242     Register DR = MI->getOperand(0).getReg();
 243     if (isRegPair(DR))
 244       continue;
 245     MachineOperand &PredOp = MI->getOperand(1);
 246     if (PredOp.isUndef())
 247       continue;
 248
 249     Register PR = PredOp.getReg();
 250     unsigned Idx = I2X.lookup(MI);
 251     CondsetMap::iterator F = CM.find(DR);
 252     bool IfTrue = HII->isPredicatedTrue(Opc);
 253
 254     // If there is no record of a conditional transfer for this register,
 255     // or the predicate register differs, create a new record for it.
 256     if (F != CM.end() && F->second.PredR != PR) {
 257       CM.erase(F);
 258       F = CM.end();
 259     }
 260     if (F == CM.end()) {
 261       auto It = CM.insert(std::make_pair(DR, CondsetInfo()));
 262       F = It.first;
 263       F->second.PredR = PR;
 264     }
 265     CondsetInfo &CI = F->second;
 266     if (IfTrue)
 267       CI.TrueX = Idx;
 268     else
 269       CI.FalseX = Idx;
 270     if (CI.TrueX == std::numeric_limits<unsigned>::max() ||
 271         CI.FalseX == std::numeric_limits<unsigned>::max())
 272       continue;
 273
 274     // There is now a complete definition of DR, i.e. we have the predicate
 275     // register, the definition if-true, and definition if-false.
 276
 277     // First, check if the definitions are far enough from the definition
 278     // of the predicate register.
 279     unsigned MinX = std::min(CI.TrueX, CI.FalseX);
 280     unsigned MaxX = std::max(CI.TrueX, CI.FalseX);
 281     // Specifically, check if the predicate definition is within a prescribed
 282     // distance from the farther of the two predicated instructions.
 283     unsigned SearchX = (MaxX >= MinPredDist) ? MaxX-MinPredDist : 0;
 284     bool NearDef = false;
 285     for (unsigned X = SearchX; X < MaxX; ++X) {
 286       const DefUseInfo &DU = DUM.lookup(X);
 287       if (!DU.Defs[PR])
 288         continue;
 289       NearDef = true;
 290       break;
 291     }
 292     if (NearDef)
 293       continue;
 294
 295     // The predicate register is not defined in the last few instructions.
 296     // Check if the conversion to MUX is possible (either "up", i.e. at the
 297     // place of the earlier partial definition, or "down", where the later
 298     // definition is located). Examine all defs and uses between these two
 299     // definitions.
 300     // SR1, SR2 - source registers from the first and the second definition.
 301     MachineBasicBlock::iterator It1 = B.begin(), It2 = B.begin();
 302     std::advance(It1, MinX);
 303     std::advance(It2, MaxX);
 304     MachineInstr &Def1 = *It1, &Def2 = *It2;
 305     MachineOperand *Src1 = &Def1.getOperand(2), *Src2 = &Def2.getOperand(2);
 306     Register SR1 = Src1->isReg() ? Src1->getReg() : Register();
 307     Register SR2 = Src2->isReg() ? Src2->getReg() : Register();
 308     bool Failure = false, CanUp = true, CanDown = true;
 309     for (unsigned X = MinX+1; X < MaxX; X++) {
 310       const DefUseInfo &DU = DUM.lookup(X);
 311       if (DU.Defs[PR] || DU.Defs[DR] || DU.Uses[DR]) {
 312         Failure = true;
 313         break;
 314       }
 315       if (CanDown && DU.Defs[SR1])
 316         CanDown = false;
 317       if (CanUp && DU.Defs[SR2])
 318         CanUp = false;
 319     }
 320     if (Failure || (!CanUp && !CanDown))
 321       continue;
 322
 323     MachineOperand *SrcT = (MinX == CI.TrueX) ? Src1 : Src2;
 324     MachineOperand *SrcF = (MinX == CI.FalseX) ? Src1 : Src2;
 325     // Prefer "down", since this will move the MUX farther away from the
 326     // predicate definition.
 327     MachineBasicBlock::iterator At = CanDown ? Def2 : Def1;
 328     ML.push_back(MuxInfo(At, DR, PR, SrcT, SrcF, Def1, Def2));
 329   }
 330
 331   for (MuxInfo &MX : ML) {
 332     unsigned MxOpc = getMuxOpcode(*MX.SrcT, *MX.SrcF);
 333     if (!MxOpc)
 334       continue;
 335     MachineBasicBlock &B = *MX.At->getParent();
 336     const DebugLoc &DL = B.findDebugLoc(MX.At);
 337     auto NewMux = BuildMI(B, MX.At, DL, HII->get(MxOpc), MX.DefR)
 338                       .addReg(MX.PredR)
 339                       .add(*MX.SrcT)
 340                       .add(*MX.SrcF);
 341     NewMux->clearKillInfo();
 342     B.erase(MX.Def1);
 343     B.erase(MX.Def2);
 344     Changed = true;
 345   }
 346
 347   // Fix up kill flags.
 348
 349   LivePhysRegs LPR(*HRI);
 350   LPR.addLiveOuts(B);
 351   auto IsLive = [&LPR,this] (unsigned Reg) -> bool {
 352     for (MCSubRegIterator S(Reg, HRI, true); S.isValid(); ++S)
 353       if (LPR.contains(*S))
 354         return true;
 355     return false;
 356   };
 357   for (auto I = B.rbegin(), E = B.rend(); I != E; ++I) {
 358     if (I->isDebugInstr())
 359       continue;
 360     // This isn't 100% accurate, but it's safe.
 361     // It won't detect (as a kill) a case like this
 362     //   r0 = add r0, 1    <-- r0 should be "killed"
 363     //   ... = r0
 364     for (MachineOperand &Op : I->operands()) {
 365       if (!Op.isReg() || !Op.isUse())
 366         continue;
 367       assert(Op.getSubReg() == 0 && "Should have physical registers only");
 368       bool Live = IsLive(Op.getReg());
 369       Op.setIsKill(!Live);
 370     }
 371     LPR.stepBackward(*I);
 372   }
 373
 374   return Changed;
 375 }
 376
 377 bool HexagonGenMux::runOnMachineFunction(MachineFunction &MF) {
 378   if (skipFunction(MF.getFunction()))
 379     return false;
 380   HII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
 381   HRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
 382   bool Changed = false;
 383   for (auto &I : MF)
 384     Changed |= genMuxInBlock(I);
 385   return Changed;
 386 }
 387
 388 FunctionPass *llvm::createHexagonGenMux() {
 389   return new HexagonGenMux();
 390 }