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

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