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