1 //===--- HexagonBitSimplify.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 #define DEBUG_TYPE "hexbit" 11 12 #include "HexagonBitTracker.h" 13 #include "HexagonTargetMachine.h" 14 #include "llvm/ADT/BitVector.h" 15 #include "llvm/ADT/DenseMap.h" 16 #include "llvm/ADT/SmallVector.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/StringRef.h" 19 #include "llvm/CodeGen/MachineBasicBlock.h" 20 #include "llvm/CodeGen/MachineDominators.h" 21 #include "llvm/CodeGen/MachineFunction.h" 22 #include "llvm/CodeGen/MachineFunctionPass.h" 23 #include "llvm/CodeGen/MachineInstr.h" 24 #include "llvm/CodeGen/MachineInstrBuilder.h" 25 #include "llvm/CodeGen/MachineOperand.h" 26 #include "llvm/CodeGen/MachineRegisterInfo.h" 27 #include "llvm/CodeGen/Passes.h" 28 #include "llvm/IR/DebugLoc.h" 29 #include "llvm/MC/MCInstrDesc.h" 30 #include "llvm/Pass.h" 31 #include "llvm/Support/CommandLine.h" 32 #include "llvm/Support/Compiler.h" 33 #include "llvm/Support/Debug.h" 34 #include "llvm/Support/MathExtras.h" 35 #include "llvm/Support/raw_ostream.h" 36 #include "llvm/Target/TargetRegisterInfo.h" 37 #include <algorithm> 38 #include <cassert> 39 #include <cstdint> 40 #include <iterator> 41 #include <limits> 42 #include <utility> 43 #include <vector> 44 45 using namespace llvm; 46 47 static cl::opt<bool> PreserveTiedOps("hexbit-keep-tied", cl::Hidden, 48 cl::init(true), cl::desc("Preserve subregisters in tied operands")); 49 50 namespace llvm { 51 52 void initializeHexagonBitSimplifyPass(PassRegistry& Registry); 53 FunctionPass *createHexagonBitSimplify(); 54 55 } // end namespace llvm 56 57 namespace { 58 59 // Set of virtual registers, based on BitVector. 60 struct RegisterSet : private BitVector { 61 RegisterSet() = default; 62 explicit RegisterSet(unsigned s, bool t = false) : BitVector(s, t) {} 63 RegisterSet(const RegisterSet &RS) = default; 64 65 using BitVector::clear; 66 using BitVector::count; 67 68 unsigned find_first() const { 69 int First = BitVector::find_first(); 70 if (First < 0) 71 return 0; 72 return x2v(First); 73 } 74 75 unsigned find_next(unsigned Prev) const { 76 int Next = BitVector::find_next(v2x(Prev)); 77 if (Next < 0) 78 return 0; 79 return x2v(Next); 80 } 81 82 RegisterSet &insert(unsigned R) { 83 unsigned Idx = v2x(R); 84 ensure(Idx); 85 return static_cast<RegisterSet&>(BitVector::set(Idx)); 86 } 87 RegisterSet &remove(unsigned R) { 88 unsigned Idx = v2x(R); 89 if (Idx >= size()) 90 return *this; 91 return static_cast<RegisterSet&>(BitVector::reset(Idx)); 92 } 93 94 RegisterSet &insert(const RegisterSet &Rs) { 95 return static_cast<RegisterSet&>(BitVector::operator|=(Rs)); 96 } 97 RegisterSet &remove(const RegisterSet &Rs) { 98 return static_cast<RegisterSet&>(BitVector::reset(Rs)); 99 } 100 101 reference operator[](unsigned R) { 102 unsigned Idx = v2x(R); 103 ensure(Idx); 104 return BitVector::operator[](Idx); 105 } 106 bool operator[](unsigned R) const { 107 unsigned Idx = v2x(R); 108 assert(Idx < size()); 109 return BitVector::operator[](Idx); 110 } 111 bool has(unsigned R) const { 112 unsigned Idx = v2x(R); 113 if (Idx >= size()) 114 return false; 115 return BitVector::test(Idx); 116 } 117 118 bool empty() const { 119 return !BitVector::any(); 120 } 121 bool includes(const RegisterSet &Rs) const { 122 // A.BitVector::test(B) <=> A-B != {} 123 return !Rs.BitVector::test(*this); 124 } 125 bool intersects(const RegisterSet &Rs) const { 126 return BitVector::anyCommon(Rs); 127 } 128 129 private: 130 void ensure(unsigned Idx) { 131 if (size() <= Idx) 132 resize(std::max(Idx+1, 32U)); 133 } 134 135 static inline unsigned v2x(unsigned v) { 136 return TargetRegisterInfo::virtReg2Index(v); 137 } 138 139 static inline unsigned x2v(unsigned x) { 140 return TargetRegisterInfo::index2VirtReg(x); 141 } 142 }; 143 144 struct PrintRegSet { 145 PrintRegSet(const RegisterSet &S, const TargetRegisterInfo *RI) 146 : RS(S), TRI(RI) {} 147 148 friend raw_ostream &operator<< (raw_ostream &OS, 149 const PrintRegSet &P); 150 151 private: 152 const RegisterSet &RS; 153 const TargetRegisterInfo *TRI; 154 }; 155 156 raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) 157 LLVM_ATTRIBUTE_UNUSED; 158 raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) { 159 OS << '{'; 160 for (unsigned R = P.RS.find_first(); R; R = P.RS.find_next(R)) 161 OS << ' ' << PrintReg(R, P.TRI); 162 OS << " }"; 163 return OS; 164 } 165 166 class Transformation; 167 168 class HexagonBitSimplify : public MachineFunctionPass { 169 public: 170 static char ID; 171 172 HexagonBitSimplify() : MachineFunctionPass(ID), MDT(nullptr) { 173 initializeHexagonBitSimplifyPass(*PassRegistry::getPassRegistry()); 174 } 175 176 StringRef getPassName() const override { 177 return "Hexagon bit simplification"; 178 } 179 180 void getAnalysisUsage(AnalysisUsage &AU) const override { 181 AU.addRequired<MachineDominatorTree>(); 182 AU.addPreserved<MachineDominatorTree>(); 183 MachineFunctionPass::getAnalysisUsage(AU); 184 } 185 186 bool runOnMachineFunction(MachineFunction &MF) override; 187 188 static void getInstrDefs(const MachineInstr &MI, RegisterSet &Defs); 189 static void getInstrUses(const MachineInstr &MI, RegisterSet &Uses); 190 static bool isEqual(const BitTracker::RegisterCell &RC1, uint16_t B1, 191 const BitTracker::RegisterCell &RC2, uint16_t B2, uint16_t W); 192 static bool isZero(const BitTracker::RegisterCell &RC, uint16_t B, 193 uint16_t W); 194 static bool getConst(const BitTracker::RegisterCell &RC, uint16_t B, 195 uint16_t W, uint64_t &U); 196 static bool replaceReg(unsigned OldR, unsigned NewR, 197 MachineRegisterInfo &MRI); 198 static bool getSubregMask(const BitTracker::RegisterRef &RR, 199 unsigned &Begin, unsigned &Width, MachineRegisterInfo &MRI); 200 static bool replaceRegWithSub(unsigned OldR, unsigned NewR, 201 unsigned NewSR, MachineRegisterInfo &MRI); 202 static bool replaceSubWithSub(unsigned OldR, unsigned OldSR, 203 unsigned NewR, unsigned NewSR, MachineRegisterInfo &MRI); 204 static bool parseRegSequence(const MachineInstr &I, 205 BitTracker::RegisterRef &SL, BitTracker::RegisterRef &SH, 206 const MachineRegisterInfo &MRI); 207 208 static bool getUsedBitsInStore(unsigned Opc, BitVector &Bits, 209 uint16_t Begin); 210 static bool getUsedBits(unsigned Opc, unsigned OpN, BitVector &Bits, 211 uint16_t Begin, const HexagonInstrInfo &HII); 212 213 static const TargetRegisterClass *getFinalVRegClass( 214 const BitTracker::RegisterRef &RR, MachineRegisterInfo &MRI); 215 static bool isTransparentCopy(const BitTracker::RegisterRef &RD, 216 const BitTracker::RegisterRef &RS, MachineRegisterInfo &MRI); 217 218 private: 219 MachineDominatorTree *MDT; 220 221 bool visitBlock(MachineBasicBlock &B, Transformation &T, RegisterSet &AVs); 222 static bool hasTiedUse(unsigned Reg, MachineRegisterInfo &MRI, 223 unsigned NewSub = Hexagon::NoSubRegister); 224 }; 225 226 char HexagonBitSimplify::ID = 0; 227 typedef HexagonBitSimplify HBS; 228 229 // The purpose of this class is to provide a common facility to traverse 230 // the function top-down or bottom-up via the dominator tree, and keep 231 // track of the available registers. 232 class Transformation { 233 public: 234 bool TopDown; 235 236 Transformation(bool TD) : TopDown(TD) {} 237 virtual ~Transformation() = default; 238 239 virtual bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) = 0; 240 }; 241 242 } // end anonymous namespace 243 244 INITIALIZE_PASS_BEGIN(HexagonBitSimplify, "hexbit", 245 "Hexagon bit simplification", false, false) 246 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 247 INITIALIZE_PASS_END(HexagonBitSimplify, "hexbit", 248 "Hexagon bit simplification", false, false) 249 250 bool HexagonBitSimplify::visitBlock(MachineBasicBlock &B, Transformation &T, 251 RegisterSet &AVs) { 252 MachineDomTreeNode *N = MDT->getNode(&B); 253 typedef GraphTraits<MachineDomTreeNode*> GTN; 254 bool Changed = false; 255 256 if (T.TopDown) 257 Changed = T.processBlock(B, AVs); 258 259 RegisterSet Defs; 260 for (auto &I : B) 261 getInstrDefs(I, Defs); 262 RegisterSet NewAVs = AVs; 263 NewAVs.insert(Defs); 264 265 for (auto I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I) { 266 MachineBasicBlock *SB = (*I)->getBlock(); 267 Changed |= visitBlock(*SB, T, NewAVs); 268 } 269 if (!T.TopDown) 270 Changed |= T.processBlock(B, AVs); 271 272 return Changed; 273 } 274 275 // 276 // Utility functions: 277 // 278 void HexagonBitSimplify::getInstrDefs(const MachineInstr &MI, 279 RegisterSet &Defs) { 280 for (auto &Op : MI.operands()) { 281 if (!Op.isReg() || !Op.isDef()) 282 continue; 283 unsigned R = Op.getReg(); 284 if (!TargetRegisterInfo::isVirtualRegister(R)) 285 continue; 286 Defs.insert(R); 287 } 288 } 289 290 void HexagonBitSimplify::getInstrUses(const MachineInstr &MI, 291 RegisterSet &Uses) { 292 for (auto &Op : MI.operands()) { 293 if (!Op.isReg() || !Op.isUse()) 294 continue; 295 unsigned R = Op.getReg(); 296 if (!TargetRegisterInfo::isVirtualRegister(R)) 297 continue; 298 Uses.insert(R); 299 } 300 } 301 302 // Check if all the bits in range [B, E) in both cells are equal. 303 bool HexagonBitSimplify::isEqual(const BitTracker::RegisterCell &RC1, 304 uint16_t B1, const BitTracker::RegisterCell &RC2, uint16_t B2, 305 uint16_t W) { 306 for (uint16_t i = 0; i < W; ++i) { 307 // If RC1[i] is "bottom", it cannot be proven equal to RC2[i]. 308 if (RC1[B1+i].Type == BitTracker::BitValue::Ref && RC1[B1+i].RefI.Reg == 0) 309 return false; 310 // Same for RC2[i]. 311 if (RC2[B2+i].Type == BitTracker::BitValue::Ref && RC2[B2+i].RefI.Reg == 0) 312 return false; 313 if (RC1[B1+i] != RC2[B2+i]) 314 return false; 315 } 316 return true; 317 } 318 319 bool HexagonBitSimplify::isZero(const BitTracker::RegisterCell &RC, 320 uint16_t B, uint16_t W) { 321 assert(B < RC.width() && B+W <= RC.width()); 322 for (uint16_t i = B; i < B+W; ++i) 323 if (!RC[i].is(0)) 324 return false; 325 return true; 326 } 327 328 bool HexagonBitSimplify::getConst(const BitTracker::RegisterCell &RC, 329 uint16_t B, uint16_t W, uint64_t &U) { 330 assert(B < RC.width() && B+W <= RC.width()); 331 int64_t T = 0; 332 for (uint16_t i = B+W; i > B; --i) { 333 const BitTracker::BitValue &BV = RC[i-1]; 334 T <<= 1; 335 if (BV.is(1)) 336 T |= 1; 337 else if (!BV.is(0)) 338 return false; 339 } 340 U = T; 341 return true; 342 } 343 344 bool HexagonBitSimplify::replaceReg(unsigned OldR, unsigned NewR, 345 MachineRegisterInfo &MRI) { 346 if (!TargetRegisterInfo::isVirtualRegister(OldR) || 347 !TargetRegisterInfo::isVirtualRegister(NewR)) 348 return false; 349 auto Begin = MRI.use_begin(OldR), End = MRI.use_end(); 350 decltype(End) NextI; 351 for (auto I = Begin; I != End; I = NextI) { 352 NextI = std::next(I); 353 I->setReg(NewR); 354 } 355 return Begin != End; 356 } 357 358 bool HexagonBitSimplify::replaceRegWithSub(unsigned OldR, unsigned NewR, 359 unsigned NewSR, MachineRegisterInfo &MRI) { 360 if (!TargetRegisterInfo::isVirtualRegister(OldR) || 361 !TargetRegisterInfo::isVirtualRegister(NewR)) 362 return false; 363 if (hasTiedUse(OldR, MRI, NewSR)) 364 return false; 365 auto Begin = MRI.use_begin(OldR), End = MRI.use_end(); 366 decltype(End) NextI; 367 for (auto I = Begin; I != End; I = NextI) { 368 NextI = std::next(I); 369 I->setReg(NewR); 370 I->setSubReg(NewSR); 371 } 372 return Begin != End; 373 } 374 375 bool HexagonBitSimplify::replaceSubWithSub(unsigned OldR, unsigned OldSR, 376 unsigned NewR, unsigned NewSR, MachineRegisterInfo &MRI) { 377 if (!TargetRegisterInfo::isVirtualRegister(OldR) || 378 !TargetRegisterInfo::isVirtualRegister(NewR)) 379 return false; 380 if (OldSR != NewSR && hasTiedUse(OldR, MRI, NewSR)) 381 return false; 382 auto Begin = MRI.use_begin(OldR), End = MRI.use_end(); 383 decltype(End) NextI; 384 for (auto I = Begin; I != End; I = NextI) { 385 NextI = std::next(I); 386 if (I->getSubReg() != OldSR) 387 continue; 388 I->setReg(NewR); 389 I->setSubReg(NewSR); 390 } 391 return Begin != End; 392 } 393 394 // For a register ref (pair Reg:Sub), set Begin to the position of the LSB 395 // of Sub in Reg, and set Width to the size of Sub in bits. Return true, 396 // if this succeeded, otherwise return false. 397 bool HexagonBitSimplify::getSubregMask(const BitTracker::RegisterRef &RR, 398 unsigned &Begin, unsigned &Width, MachineRegisterInfo &MRI) { 399 const TargetRegisterClass *RC = MRI.getRegClass(RR.Reg); 400 if (RR.Sub == 0) { 401 Begin = 0; 402 Width = RC->getSize()*8; 403 return true; 404 } 405 406 Begin = 0; 407 408 switch (RC->getID()) { 409 case Hexagon::DoubleRegsRegClassID: 410 case Hexagon::VecDblRegsRegClassID: 411 case Hexagon::VecDblRegs128BRegClassID: 412 Width = RC->getSize()*8 / 2; 413 if (RR.Sub == Hexagon::isub_hi || RR.Sub == Hexagon::vsub_hi) 414 Begin = Width; 415 break; 416 default: 417 return false; 418 } 419 return true; 420 } 421 422 423 // For a REG_SEQUENCE, set SL to the low subregister and SH to the high 424 // subregister. 425 bool HexagonBitSimplify::parseRegSequence(const MachineInstr &I, 426 BitTracker::RegisterRef &SL, BitTracker::RegisterRef &SH, 427 const MachineRegisterInfo &MRI) { 428 assert(I.getOpcode() == TargetOpcode::REG_SEQUENCE); 429 unsigned Sub1 = I.getOperand(2).getImm(), Sub2 = I.getOperand(4).getImm(); 430 auto *DstRC = MRI.getRegClass(I.getOperand(0).getReg()); 431 auto &HRI = static_cast<const HexagonRegisterInfo&>( 432 *MRI.getTargetRegisterInfo()); 433 unsigned SubLo = HRI.getHexagonSubRegIndex(DstRC, Hexagon::ps_sub_lo); 434 unsigned SubHi = HRI.getHexagonSubRegIndex(DstRC, Hexagon::ps_sub_hi); 435 assert((Sub1 == SubLo && Sub2 == SubHi) || (Sub1 == SubHi && Sub2 == SubLo)); 436 if (Sub1 == SubLo && Sub2 == SubHi) { 437 SL = I.getOperand(1); 438 SH = I.getOperand(3); 439 return true; 440 } 441 if (Sub1 == SubHi && Sub2 == SubLo) { 442 SH = I.getOperand(1); 443 SL = I.getOperand(3); 444 return true; 445 } 446 return false; 447 } 448 449 // All stores (except 64-bit stores) take a 32-bit register as the source 450 // of the value to be stored. If the instruction stores into a location 451 // that is shorter than 32 bits, some bits of the source register are not 452 // used. For each store instruction, calculate the set of used bits in 453 // the source register, and set appropriate bits in Bits. Return true if 454 // the bits are calculated, false otherwise. 455 bool HexagonBitSimplify::getUsedBitsInStore(unsigned Opc, BitVector &Bits, 456 uint16_t Begin) { 457 using namespace Hexagon; 458 459 switch (Opc) { 460 // Store byte 461 case S2_storerb_io: // memb(Rs32+#s11:0)=Rt32 462 case S2_storerbnew_io: // memb(Rs32+#s11:0)=Nt8.new 463 case S2_pstorerbt_io: // if (Pv4) memb(Rs32+#u6:0)=Rt32 464 case S2_pstorerbf_io: // if (!Pv4) memb(Rs32+#u6:0)=Rt32 465 case S4_pstorerbtnew_io: // if (Pv4.new) memb(Rs32+#u6:0)=Rt32 466 case S4_pstorerbfnew_io: // if (!Pv4.new) memb(Rs32+#u6:0)=Rt32 467 case S2_pstorerbnewt_io: // if (Pv4) memb(Rs32+#u6:0)=Nt8.new 468 case S2_pstorerbnewf_io: // if (!Pv4) memb(Rs32+#u6:0)=Nt8.new 469 case S4_pstorerbnewtnew_io: // if (Pv4.new) memb(Rs32+#u6:0)=Nt8.new 470 case S4_pstorerbnewfnew_io: // if (!Pv4.new) memb(Rs32+#u6:0)=Nt8.new 471 case S2_storerb_pi: // memb(Rx32++#s4:0)=Rt32 472 case S2_storerbnew_pi: // memb(Rx32++#s4:0)=Nt8.new 473 case S2_pstorerbt_pi: // if (Pv4) memb(Rx32++#s4:0)=Rt32 474 case S2_pstorerbf_pi: // if (!Pv4) memb(Rx32++#s4:0)=Rt32 475 case S2_pstorerbtnew_pi: // if (Pv4.new) memb(Rx32++#s4:0)=Rt32 476 case S2_pstorerbfnew_pi: // if (!Pv4.new) memb(Rx32++#s4:0)=Rt32 477 case S2_pstorerbnewt_pi: // if (Pv4) memb(Rx32++#s4:0)=Nt8.new 478 case S2_pstorerbnewf_pi: // if (!Pv4) memb(Rx32++#s4:0)=Nt8.new 479 case S2_pstorerbnewtnew_pi: // if (Pv4.new) memb(Rx32++#s4:0)=Nt8.new 480 case S2_pstorerbnewfnew_pi: // if (!Pv4.new) memb(Rx32++#s4:0)=Nt8.new 481 case S4_storerb_ap: // memb(Re32=#U6)=Rt32 482 case S4_storerbnew_ap: // memb(Re32=#U6)=Nt8.new 483 case S2_storerb_pr: // memb(Rx32++Mu2)=Rt32 484 case S2_storerbnew_pr: // memb(Rx32++Mu2)=Nt8.new 485 case S4_storerb_ur: // memb(Ru32<<#u2+#U6)=Rt32 486 case S4_storerbnew_ur: // memb(Ru32<<#u2+#U6)=Nt8.new 487 case S2_storerb_pbr: // memb(Rx32++Mu2:brev)=Rt32 488 case S2_storerbnew_pbr: // memb(Rx32++Mu2:brev)=Nt8.new 489 case S2_storerb_pci: // memb(Rx32++#s4:0:circ(Mu2))=Rt32 490 case S2_storerbnew_pci: // memb(Rx32++#s4:0:circ(Mu2))=Nt8.new 491 case S2_storerb_pcr: // memb(Rx32++I:circ(Mu2))=Rt32 492 case S2_storerbnew_pcr: // memb(Rx32++I:circ(Mu2))=Nt8.new 493 case S4_storerb_rr: // memb(Rs32+Ru32<<#u2)=Rt32 494 case S4_storerbnew_rr: // memb(Rs32+Ru32<<#u2)=Nt8.new 495 case S4_pstorerbt_rr: // if (Pv4) memb(Rs32+Ru32<<#u2)=Rt32 496 case S4_pstorerbf_rr: // if (!Pv4) memb(Rs32+Ru32<<#u2)=Rt32 497 case S4_pstorerbtnew_rr: // if (Pv4.new) memb(Rs32+Ru32<<#u2)=Rt32 498 case S4_pstorerbfnew_rr: // if (!Pv4.new) memb(Rs32+Ru32<<#u2)=Rt32 499 case S4_pstorerbnewt_rr: // if (Pv4) memb(Rs32+Ru32<<#u2)=Nt8.new 500 case S4_pstorerbnewf_rr: // if (!Pv4) memb(Rs32+Ru32<<#u2)=Nt8.new 501 case S4_pstorerbnewtnew_rr: // if (Pv4.new) memb(Rs32+Ru32<<#u2)=Nt8.new 502 case S4_pstorerbnewfnew_rr: // if (!Pv4.new) memb(Rs32+Ru32<<#u2)=Nt8.new 503 case S2_storerbgp: // memb(gp+#u16:0)=Rt32 504 case S2_storerbnewgp: // memb(gp+#u16:0)=Nt8.new 505 case S4_pstorerbt_abs: // if (Pv4) memb(#u6)=Rt32 506 case S4_pstorerbf_abs: // if (!Pv4) memb(#u6)=Rt32 507 case S4_pstorerbtnew_abs: // if (Pv4.new) memb(#u6)=Rt32 508 case S4_pstorerbfnew_abs: // if (!Pv4.new) memb(#u6)=Rt32 509 case S4_pstorerbnewt_abs: // if (Pv4) memb(#u6)=Nt8.new 510 case S4_pstorerbnewf_abs: // if (!Pv4) memb(#u6)=Nt8.new 511 case S4_pstorerbnewtnew_abs: // if (Pv4.new) memb(#u6)=Nt8.new 512 case S4_pstorerbnewfnew_abs: // if (!Pv4.new) memb(#u6)=Nt8.new 513 Bits.set(Begin, Begin+8); 514 return true; 515 516 // Store low half 517 case S2_storerh_io: // memh(Rs32+#s11:1)=Rt32 518 case S2_storerhnew_io: // memh(Rs32+#s11:1)=Nt8.new 519 case S2_pstorerht_io: // if (Pv4) memh(Rs32+#u6:1)=Rt32 520 case S2_pstorerhf_io: // if (!Pv4) memh(Rs32+#u6:1)=Rt32 521 case S4_pstorerhtnew_io: // if (Pv4.new) memh(Rs32+#u6:1)=Rt32 522 case S4_pstorerhfnew_io: // if (!Pv4.new) memh(Rs32+#u6:1)=Rt32 523 case S2_pstorerhnewt_io: // if (Pv4) memh(Rs32+#u6:1)=Nt8.new 524 case S2_pstorerhnewf_io: // if (!Pv4) memh(Rs32+#u6:1)=Nt8.new 525 case S4_pstorerhnewtnew_io: // if (Pv4.new) memh(Rs32+#u6:1)=Nt8.new 526 case S4_pstorerhnewfnew_io: // if (!Pv4.new) memh(Rs32+#u6:1)=Nt8.new 527 case S2_storerh_pi: // memh(Rx32++#s4:1)=Rt32 528 case S2_storerhnew_pi: // memh(Rx32++#s4:1)=Nt8.new 529 case S2_pstorerht_pi: // if (Pv4) memh(Rx32++#s4:1)=Rt32 530 case S2_pstorerhf_pi: // if (!Pv4) memh(Rx32++#s4:1)=Rt32 531 case S2_pstorerhtnew_pi: // if (Pv4.new) memh(Rx32++#s4:1)=Rt32 532 case S2_pstorerhfnew_pi: // if (!Pv4.new) memh(Rx32++#s4:1)=Rt32 533 case S2_pstorerhnewt_pi: // if (Pv4) memh(Rx32++#s4:1)=Nt8.new 534 case S2_pstorerhnewf_pi: // if (!Pv4) memh(Rx32++#s4:1)=Nt8.new 535 case S2_pstorerhnewtnew_pi: // if (Pv4.new) memh(Rx32++#s4:1)=Nt8.new 536 case S2_pstorerhnewfnew_pi: // if (!Pv4.new) memh(Rx32++#s4:1)=Nt8.new 537 case S4_storerh_ap: // memh(Re32=#U6)=Rt32 538 case S4_storerhnew_ap: // memh(Re32=#U6)=Nt8.new 539 case S2_storerh_pr: // memh(Rx32++Mu2)=Rt32 540 case S2_storerhnew_pr: // memh(Rx32++Mu2)=Nt8.new 541 case S4_storerh_ur: // memh(Ru32<<#u2+#U6)=Rt32 542 case S4_storerhnew_ur: // memh(Ru32<<#u2+#U6)=Nt8.new 543 case S2_storerh_pbr: // memh(Rx32++Mu2:brev)=Rt32 544 case S2_storerhnew_pbr: // memh(Rx32++Mu2:brev)=Nt8.new 545 case S2_storerh_pci: // memh(Rx32++#s4:1:circ(Mu2))=Rt32 546 case S2_storerhnew_pci: // memh(Rx32++#s4:1:circ(Mu2))=Nt8.new 547 case S2_storerh_pcr: // memh(Rx32++I:circ(Mu2))=Rt32 548 case S2_storerhnew_pcr: // memh(Rx32++I:circ(Mu2))=Nt8.new 549 case S4_storerh_rr: // memh(Rs32+Ru32<<#u2)=Rt32 550 case S4_pstorerht_rr: // if (Pv4) memh(Rs32+Ru32<<#u2)=Rt32 551 case S4_pstorerhf_rr: // if (!Pv4) memh(Rs32+Ru32<<#u2)=Rt32 552 case S4_pstorerhtnew_rr: // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Rt32 553 case S4_pstorerhfnew_rr: // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Rt32 554 case S4_storerhnew_rr: // memh(Rs32+Ru32<<#u2)=Nt8.new 555 case S4_pstorerhnewt_rr: // if (Pv4) memh(Rs32+Ru32<<#u2)=Nt8.new 556 case S4_pstorerhnewf_rr: // if (!Pv4) memh(Rs32+Ru32<<#u2)=Nt8.new 557 case S4_pstorerhnewtnew_rr: // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Nt8.new 558 case S4_pstorerhnewfnew_rr: // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Nt8.new 559 case S2_storerhgp: // memh(gp+#u16:1)=Rt32 560 case S2_storerhnewgp: // memh(gp+#u16:1)=Nt8.new 561 case S4_pstorerht_abs: // if (Pv4) memh(#u6)=Rt32 562 case S4_pstorerhf_abs: // if (!Pv4) memh(#u6)=Rt32 563 case S4_pstorerhtnew_abs: // if (Pv4.new) memh(#u6)=Rt32 564 case S4_pstorerhfnew_abs: // if (!Pv4.new) memh(#u6)=Rt32 565 case S4_pstorerhnewt_abs: // if (Pv4) memh(#u6)=Nt8.new 566 case S4_pstorerhnewf_abs: // if (!Pv4) memh(#u6)=Nt8.new 567 case S4_pstorerhnewtnew_abs: // if (Pv4.new) memh(#u6)=Nt8.new 568 case S4_pstorerhnewfnew_abs: // if (!Pv4.new) memh(#u6)=Nt8.new 569 Bits.set(Begin, Begin+16); 570 return true; 571 572 // Store high half 573 case S2_storerf_io: // memh(Rs32+#s11:1)=Rt.H32 574 case S2_pstorerft_io: // if (Pv4) memh(Rs32+#u6:1)=Rt.H32 575 case S2_pstorerff_io: // if (!Pv4) memh(Rs32+#u6:1)=Rt.H32 576 case S4_pstorerftnew_io: // if (Pv4.new) memh(Rs32+#u6:1)=Rt.H32 577 case S4_pstorerffnew_io: // if (!Pv4.new) memh(Rs32+#u6:1)=Rt.H32 578 case S2_storerf_pi: // memh(Rx32++#s4:1)=Rt.H32 579 case S2_pstorerft_pi: // if (Pv4) memh(Rx32++#s4:1)=Rt.H32 580 case S2_pstorerff_pi: // if (!Pv4) memh(Rx32++#s4:1)=Rt.H32 581 case S2_pstorerftnew_pi: // if (Pv4.new) memh(Rx32++#s4:1)=Rt.H32 582 case S2_pstorerffnew_pi: // if (!Pv4.new) memh(Rx32++#s4:1)=Rt.H32 583 case S4_storerf_ap: // memh(Re32=#U6)=Rt.H32 584 case S2_storerf_pr: // memh(Rx32++Mu2)=Rt.H32 585 case S4_storerf_ur: // memh(Ru32<<#u2+#U6)=Rt.H32 586 case S2_storerf_pbr: // memh(Rx32++Mu2:brev)=Rt.H32 587 case S2_storerf_pci: // memh(Rx32++#s4:1:circ(Mu2))=Rt.H32 588 case S2_storerf_pcr: // memh(Rx32++I:circ(Mu2))=Rt.H32 589 case S4_storerf_rr: // memh(Rs32+Ru32<<#u2)=Rt.H32 590 case S4_pstorerft_rr: // if (Pv4) memh(Rs32+Ru32<<#u2)=Rt.H32 591 case S4_pstorerff_rr: // if (!Pv4) memh(Rs32+Ru32<<#u2)=Rt.H32 592 case S4_pstorerftnew_rr: // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Rt.H32 593 case S4_pstorerffnew_rr: // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Rt.H32 594 case S2_storerfgp: // memh(gp+#u16:1)=Rt.H32 595 case S4_pstorerft_abs: // if (Pv4) memh(#u6)=Rt.H32 596 case S4_pstorerff_abs: // if (!Pv4) memh(#u6)=Rt.H32 597 case S4_pstorerftnew_abs: // if (Pv4.new) memh(#u6)=Rt.H32 598 case S4_pstorerffnew_abs: // if (!Pv4.new) memh(#u6)=Rt.H32 599 Bits.set(Begin+16, Begin+32); 600 return true; 601 } 602 603 return false; 604 } 605 606 // For an instruction with opcode Opc, calculate the set of bits that it 607 // uses in a register in operand OpN. This only calculates the set of used 608 // bits for cases where it does not depend on any operands (as is the case 609 // in shifts, for example). For concrete instructions from a program, the 610 // operand may be a subregister of a larger register, while Bits would 611 // correspond to the larger register in its entirety. Because of that, 612 // the parameter Begin can be used to indicate which bit of Bits should be 613 // considered the LSB of of the operand. 614 bool HexagonBitSimplify::getUsedBits(unsigned Opc, unsigned OpN, 615 BitVector &Bits, uint16_t Begin, const HexagonInstrInfo &HII) { 616 using namespace Hexagon; 617 618 const MCInstrDesc &D = HII.get(Opc); 619 if (D.mayStore()) { 620 if (OpN == D.getNumOperands()-1) 621 return getUsedBitsInStore(Opc, Bits, Begin); 622 return false; 623 } 624 625 switch (Opc) { 626 // One register source. Used bits: R1[0-7]. 627 case A2_sxtb: 628 case A2_zxtb: 629 case A4_cmpbeqi: 630 case A4_cmpbgti: 631 case A4_cmpbgtui: 632 if (OpN == 1) { 633 Bits.set(Begin, Begin+8); 634 return true; 635 } 636 break; 637 638 // One register source. Used bits: R1[0-15]. 639 case A2_aslh: 640 case A2_sxth: 641 case A2_zxth: 642 case A4_cmpheqi: 643 case A4_cmphgti: 644 case A4_cmphgtui: 645 if (OpN == 1) { 646 Bits.set(Begin, Begin+16); 647 return true; 648 } 649 break; 650 651 // One register source. Used bits: R1[16-31]. 652 case A2_asrh: 653 if (OpN == 1) { 654 Bits.set(Begin+16, Begin+32); 655 return true; 656 } 657 break; 658 659 // Two register sources. Used bits: R1[0-7], R2[0-7]. 660 case A4_cmpbeq: 661 case A4_cmpbgt: 662 case A4_cmpbgtu: 663 if (OpN == 1) { 664 Bits.set(Begin, Begin+8); 665 return true; 666 } 667 break; 668 669 // Two register sources. Used bits: R1[0-15], R2[0-15]. 670 case A4_cmpheq: 671 case A4_cmphgt: 672 case A4_cmphgtu: 673 case A2_addh_h16_ll: 674 case A2_addh_h16_sat_ll: 675 case A2_addh_l16_ll: 676 case A2_addh_l16_sat_ll: 677 case A2_combine_ll: 678 case A2_subh_h16_ll: 679 case A2_subh_h16_sat_ll: 680 case A2_subh_l16_ll: 681 case A2_subh_l16_sat_ll: 682 case M2_mpy_acc_ll_s0: 683 case M2_mpy_acc_ll_s1: 684 case M2_mpy_acc_sat_ll_s0: 685 case M2_mpy_acc_sat_ll_s1: 686 case M2_mpy_ll_s0: 687 case M2_mpy_ll_s1: 688 case M2_mpy_nac_ll_s0: 689 case M2_mpy_nac_ll_s1: 690 case M2_mpy_nac_sat_ll_s0: 691 case M2_mpy_nac_sat_ll_s1: 692 case M2_mpy_rnd_ll_s0: 693 case M2_mpy_rnd_ll_s1: 694 case M2_mpy_sat_ll_s0: 695 case M2_mpy_sat_ll_s1: 696 case M2_mpy_sat_rnd_ll_s0: 697 case M2_mpy_sat_rnd_ll_s1: 698 case M2_mpyd_acc_ll_s0: 699 case M2_mpyd_acc_ll_s1: 700 case M2_mpyd_ll_s0: 701 case M2_mpyd_ll_s1: 702 case M2_mpyd_nac_ll_s0: 703 case M2_mpyd_nac_ll_s1: 704 case M2_mpyd_rnd_ll_s0: 705 case M2_mpyd_rnd_ll_s1: 706 case M2_mpyu_acc_ll_s0: 707 case M2_mpyu_acc_ll_s1: 708 case M2_mpyu_ll_s0: 709 case M2_mpyu_ll_s1: 710 case M2_mpyu_nac_ll_s0: 711 case M2_mpyu_nac_ll_s1: 712 case M2_mpyud_acc_ll_s0: 713 case M2_mpyud_acc_ll_s1: 714 case M2_mpyud_ll_s0: 715 case M2_mpyud_ll_s1: 716 case M2_mpyud_nac_ll_s0: 717 case M2_mpyud_nac_ll_s1: 718 if (OpN == 1 || OpN == 2) { 719 Bits.set(Begin, Begin+16); 720 return true; 721 } 722 break; 723 724 // Two register sources. Used bits: R1[0-15], R2[16-31]. 725 case A2_addh_h16_lh: 726 case A2_addh_h16_sat_lh: 727 case A2_combine_lh: 728 case A2_subh_h16_lh: 729 case A2_subh_h16_sat_lh: 730 case M2_mpy_acc_lh_s0: 731 case M2_mpy_acc_lh_s1: 732 case M2_mpy_acc_sat_lh_s0: 733 case M2_mpy_acc_sat_lh_s1: 734 case M2_mpy_lh_s0: 735 case M2_mpy_lh_s1: 736 case M2_mpy_nac_lh_s0: 737 case M2_mpy_nac_lh_s1: 738 case M2_mpy_nac_sat_lh_s0: 739 case M2_mpy_nac_sat_lh_s1: 740 case M2_mpy_rnd_lh_s0: 741 case M2_mpy_rnd_lh_s1: 742 case M2_mpy_sat_lh_s0: 743 case M2_mpy_sat_lh_s1: 744 case M2_mpy_sat_rnd_lh_s0: 745 case M2_mpy_sat_rnd_lh_s1: 746 case M2_mpyd_acc_lh_s0: 747 case M2_mpyd_acc_lh_s1: 748 case M2_mpyd_lh_s0: 749 case M2_mpyd_lh_s1: 750 case M2_mpyd_nac_lh_s0: 751 case M2_mpyd_nac_lh_s1: 752 case M2_mpyd_rnd_lh_s0: 753 case M2_mpyd_rnd_lh_s1: 754 case M2_mpyu_acc_lh_s0: 755 case M2_mpyu_acc_lh_s1: 756 case M2_mpyu_lh_s0: 757 case M2_mpyu_lh_s1: 758 case M2_mpyu_nac_lh_s0: 759 case M2_mpyu_nac_lh_s1: 760 case M2_mpyud_acc_lh_s0: 761 case M2_mpyud_acc_lh_s1: 762 case M2_mpyud_lh_s0: 763 case M2_mpyud_lh_s1: 764 case M2_mpyud_nac_lh_s0: 765 case M2_mpyud_nac_lh_s1: 766 // These four are actually LH. 767 case A2_addh_l16_hl: 768 case A2_addh_l16_sat_hl: 769 case A2_subh_l16_hl: 770 case A2_subh_l16_sat_hl: 771 if (OpN == 1) { 772 Bits.set(Begin, Begin+16); 773 return true; 774 } 775 if (OpN == 2) { 776 Bits.set(Begin+16, Begin+32); 777 return true; 778 } 779 break; 780 781 // Two register sources, used bits: R1[16-31], R2[0-15]. 782 case A2_addh_h16_hl: 783 case A2_addh_h16_sat_hl: 784 case A2_combine_hl: 785 case A2_subh_h16_hl: 786 case A2_subh_h16_sat_hl: 787 case M2_mpy_acc_hl_s0: 788 case M2_mpy_acc_hl_s1: 789 case M2_mpy_acc_sat_hl_s0: 790 case M2_mpy_acc_sat_hl_s1: 791 case M2_mpy_hl_s0: 792 case M2_mpy_hl_s1: 793 case M2_mpy_nac_hl_s0: 794 case M2_mpy_nac_hl_s1: 795 case M2_mpy_nac_sat_hl_s0: 796 case M2_mpy_nac_sat_hl_s1: 797 case M2_mpy_rnd_hl_s0: 798 case M2_mpy_rnd_hl_s1: 799 case M2_mpy_sat_hl_s0: 800 case M2_mpy_sat_hl_s1: 801 case M2_mpy_sat_rnd_hl_s0: 802 case M2_mpy_sat_rnd_hl_s1: 803 case M2_mpyd_acc_hl_s0: 804 case M2_mpyd_acc_hl_s1: 805 case M2_mpyd_hl_s0: 806 case M2_mpyd_hl_s1: 807 case M2_mpyd_nac_hl_s0: 808 case M2_mpyd_nac_hl_s1: 809 case M2_mpyd_rnd_hl_s0: 810 case M2_mpyd_rnd_hl_s1: 811 case M2_mpyu_acc_hl_s0: 812 case M2_mpyu_acc_hl_s1: 813 case M2_mpyu_hl_s0: 814 case M2_mpyu_hl_s1: 815 case M2_mpyu_nac_hl_s0: 816 case M2_mpyu_nac_hl_s1: 817 case M2_mpyud_acc_hl_s0: 818 case M2_mpyud_acc_hl_s1: 819 case M2_mpyud_hl_s0: 820 case M2_mpyud_hl_s1: 821 case M2_mpyud_nac_hl_s0: 822 case M2_mpyud_nac_hl_s1: 823 if (OpN == 1) { 824 Bits.set(Begin+16, Begin+32); 825 return true; 826 } 827 if (OpN == 2) { 828 Bits.set(Begin, Begin+16); 829 return true; 830 } 831 break; 832 833 // Two register sources, used bits: R1[16-31], R2[16-31]. 834 case A2_addh_h16_hh: 835 case A2_addh_h16_sat_hh: 836 case A2_combine_hh: 837 case A2_subh_h16_hh: 838 case A2_subh_h16_sat_hh: 839 case M2_mpy_acc_hh_s0: 840 case M2_mpy_acc_hh_s1: 841 case M2_mpy_acc_sat_hh_s0: 842 case M2_mpy_acc_sat_hh_s1: 843 case M2_mpy_hh_s0: 844 case M2_mpy_hh_s1: 845 case M2_mpy_nac_hh_s0: 846 case M2_mpy_nac_hh_s1: 847 case M2_mpy_nac_sat_hh_s0: 848 case M2_mpy_nac_sat_hh_s1: 849 case M2_mpy_rnd_hh_s0: 850 case M2_mpy_rnd_hh_s1: 851 case M2_mpy_sat_hh_s0: 852 case M2_mpy_sat_hh_s1: 853 case M2_mpy_sat_rnd_hh_s0: 854 case M2_mpy_sat_rnd_hh_s1: 855 case M2_mpyd_acc_hh_s0: 856 case M2_mpyd_acc_hh_s1: 857 case M2_mpyd_hh_s0: 858 case M2_mpyd_hh_s1: 859 case M2_mpyd_nac_hh_s0: 860 case M2_mpyd_nac_hh_s1: 861 case M2_mpyd_rnd_hh_s0: 862 case M2_mpyd_rnd_hh_s1: 863 case M2_mpyu_acc_hh_s0: 864 case M2_mpyu_acc_hh_s1: 865 case M2_mpyu_hh_s0: 866 case M2_mpyu_hh_s1: 867 case M2_mpyu_nac_hh_s0: 868 case M2_mpyu_nac_hh_s1: 869 case M2_mpyud_acc_hh_s0: 870 case M2_mpyud_acc_hh_s1: 871 case M2_mpyud_hh_s0: 872 case M2_mpyud_hh_s1: 873 case M2_mpyud_nac_hh_s0: 874 case M2_mpyud_nac_hh_s1: 875 if (OpN == 1 || OpN == 2) { 876 Bits.set(Begin+16, Begin+32); 877 return true; 878 } 879 break; 880 } 881 882 return false; 883 } 884 885 // Calculate the register class that matches Reg:Sub. For example, if 886 // vreg1 is a double register, then vreg1:isub_hi would match the "int" 887 // register class. 888 const TargetRegisterClass *HexagonBitSimplify::getFinalVRegClass( 889 const BitTracker::RegisterRef &RR, MachineRegisterInfo &MRI) { 890 if (!TargetRegisterInfo::isVirtualRegister(RR.Reg)) 891 return nullptr; 892 auto *RC = MRI.getRegClass(RR.Reg); 893 if (RR.Sub == 0) 894 return RC; 895 auto &HRI = static_cast<const HexagonRegisterInfo&>( 896 *MRI.getTargetRegisterInfo()); 897 898 auto VerifySR = [&HRI] (const TargetRegisterClass *RC, unsigned Sub) -> void { 899 (void)HRI; 900 assert(Sub == HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_lo) || 901 Sub == HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_hi)); 902 }; 903 904 switch (RC->getID()) { 905 case Hexagon::DoubleRegsRegClassID: 906 VerifySR(RC, RR.Sub); 907 return &Hexagon::IntRegsRegClass; 908 case Hexagon::VecDblRegsRegClassID: 909 VerifySR(RC, RR.Sub); 910 return &Hexagon::VectorRegsRegClass; 911 case Hexagon::VecDblRegs128BRegClassID: 912 VerifySR(RC, RR.Sub); 913 return &Hexagon::VectorRegs128BRegClass; 914 } 915 return nullptr; 916 } 917 918 // Check if RD could be replaced with RS at any possible use of RD. 919 // For example a predicate register cannot be replaced with a integer 920 // register, but a 64-bit register with a subregister can be replaced 921 // with a 32-bit register. 922 bool HexagonBitSimplify::isTransparentCopy(const BitTracker::RegisterRef &RD, 923 const BitTracker::RegisterRef &RS, MachineRegisterInfo &MRI) { 924 if (!TargetRegisterInfo::isVirtualRegister(RD.Reg) || 925 !TargetRegisterInfo::isVirtualRegister(RS.Reg)) 926 return false; 927 // Return false if one (or both) classes are nullptr. 928 auto *DRC = getFinalVRegClass(RD, MRI); 929 if (!DRC) 930 return false; 931 932 return DRC == getFinalVRegClass(RS, MRI); 933 } 934 935 bool HexagonBitSimplify::hasTiedUse(unsigned Reg, MachineRegisterInfo &MRI, 936 unsigned NewSub) { 937 if (!PreserveTiedOps) 938 return false; 939 return llvm::any_of(MRI.use_operands(Reg), 940 [NewSub] (const MachineOperand &Op) -> bool { 941 return Op.getSubReg() != NewSub && Op.isTied(); 942 }); 943 } 944 945 namespace { 946 947 class DeadCodeElimination { 948 public: 949 DeadCodeElimination(MachineFunction &mf, MachineDominatorTree &mdt) 950 : MF(mf), HII(*MF.getSubtarget<HexagonSubtarget>().getInstrInfo()), 951 MDT(mdt), MRI(mf.getRegInfo()) {} 952 953 bool run() { 954 return runOnNode(MDT.getRootNode()); 955 } 956 957 private: 958 bool isDead(unsigned R) const; 959 bool runOnNode(MachineDomTreeNode *N); 960 961 MachineFunction &MF; 962 const HexagonInstrInfo &HII; 963 MachineDominatorTree &MDT; 964 MachineRegisterInfo &MRI; 965 }; 966 967 } // end anonymous namespace 968 969 bool DeadCodeElimination::isDead(unsigned R) const { 970 for (auto I = MRI.use_begin(R), E = MRI.use_end(); I != E; ++I) { 971 MachineInstr *UseI = I->getParent(); 972 if (UseI->isDebugValue()) 973 continue; 974 if (UseI->isPHI()) { 975 assert(!UseI->getOperand(0).getSubReg()); 976 unsigned DR = UseI->getOperand(0).getReg(); 977 if (DR == R) 978 continue; 979 } 980 return false; 981 } 982 return true; 983 } 984 985 bool DeadCodeElimination::runOnNode(MachineDomTreeNode *N) { 986 bool Changed = false; 987 typedef GraphTraits<MachineDomTreeNode*> GTN; 988 for (auto I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I) 989 Changed |= runOnNode(*I); 990 991 MachineBasicBlock *B = N->getBlock(); 992 std::vector<MachineInstr*> Instrs; 993 for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) 994 Instrs.push_back(&*I); 995 996 for (auto MI : Instrs) { 997 unsigned Opc = MI->getOpcode(); 998 // Do not touch lifetime markers. This is why the target-independent DCE 999 // cannot be used. 1000 if (Opc == TargetOpcode::LIFETIME_START || 1001 Opc == TargetOpcode::LIFETIME_END) 1002 continue; 1003 bool Store = false; 1004 if (MI->isInlineAsm()) 1005 continue; 1006 // Delete PHIs if possible. 1007 if (!MI->isPHI() && !MI->isSafeToMove(nullptr, Store)) 1008 continue; 1009 1010 bool AllDead = true; 1011 SmallVector<unsigned,2> Regs; 1012 for (auto &Op : MI->operands()) { 1013 if (!Op.isReg() || !Op.isDef()) 1014 continue; 1015 unsigned R = Op.getReg(); 1016 if (!TargetRegisterInfo::isVirtualRegister(R) || !isDead(R)) { 1017 AllDead = false; 1018 break; 1019 } 1020 Regs.push_back(R); 1021 } 1022 if (!AllDead) 1023 continue; 1024 1025 B->erase(MI); 1026 for (unsigned i = 0, n = Regs.size(); i != n; ++i) 1027 MRI.markUsesInDebugValueAsUndef(Regs[i]); 1028 Changed = true; 1029 } 1030 1031 return Changed; 1032 } 1033 1034 namespace { 1035 1036 // Eliminate redundant instructions 1037 // 1038 // This transformation will identify instructions where the output register 1039 // is the same as one of its input registers. This only works on instructions 1040 // that define a single register (unlike post-increment loads, for example). 1041 // The equality check is actually more detailed: the code calculates which 1042 // bits of the output are used, and only compares these bits with the input 1043 // registers. 1044 // If the output matches an input, the instruction is replaced with COPY. 1045 // The copies will be removed by another transformation. 1046 class RedundantInstrElimination : public Transformation { 1047 public: 1048 RedundantInstrElimination(BitTracker &bt, const HexagonInstrInfo &hii, 1049 MachineRegisterInfo &mri) 1050 : Transformation(true), HII(hii), MRI(mri), BT(bt) {} 1051 1052 bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override; 1053 1054 private: 1055 bool isLossyShiftLeft(const MachineInstr &MI, unsigned OpN, 1056 unsigned &LostB, unsigned &LostE); 1057 bool isLossyShiftRight(const MachineInstr &MI, unsigned OpN, 1058 unsigned &LostB, unsigned &LostE); 1059 bool computeUsedBits(unsigned Reg, BitVector &Bits); 1060 bool computeUsedBits(const MachineInstr &MI, unsigned OpN, BitVector &Bits, 1061 uint16_t Begin); 1062 bool usedBitsEqual(BitTracker::RegisterRef RD, BitTracker::RegisterRef RS); 1063 1064 const HexagonInstrInfo &HII; 1065 MachineRegisterInfo &MRI; 1066 BitTracker &BT; 1067 }; 1068 1069 } // end anonymous namespace 1070 1071 // Check if the instruction is a lossy shift left, where the input being 1072 // shifted is the operand OpN of MI. If true, [LostB, LostE) is the range 1073 // of bit indices that are lost. 1074 bool RedundantInstrElimination::isLossyShiftLeft(const MachineInstr &MI, 1075 unsigned OpN, unsigned &LostB, unsigned &LostE) { 1076 using namespace Hexagon; 1077 1078 unsigned Opc = MI.getOpcode(); 1079 unsigned ImN, RegN, Width; 1080 switch (Opc) { 1081 case S2_asl_i_p: 1082 ImN = 2; 1083 RegN = 1; 1084 Width = 64; 1085 break; 1086 case S2_asl_i_p_acc: 1087 case S2_asl_i_p_and: 1088 case S2_asl_i_p_nac: 1089 case S2_asl_i_p_or: 1090 case S2_asl_i_p_xacc: 1091 ImN = 3; 1092 RegN = 2; 1093 Width = 64; 1094 break; 1095 case S2_asl_i_r: 1096 ImN = 2; 1097 RegN = 1; 1098 Width = 32; 1099 break; 1100 case S2_addasl_rrri: 1101 case S4_andi_asl_ri: 1102 case S4_ori_asl_ri: 1103 case S4_addi_asl_ri: 1104 case S4_subi_asl_ri: 1105 case S2_asl_i_r_acc: 1106 case S2_asl_i_r_and: 1107 case S2_asl_i_r_nac: 1108 case S2_asl_i_r_or: 1109 case S2_asl_i_r_sat: 1110 case S2_asl_i_r_xacc: 1111 ImN = 3; 1112 RegN = 2; 1113 Width = 32; 1114 break; 1115 default: 1116 return false; 1117 } 1118 1119 if (RegN != OpN) 1120 return false; 1121 1122 assert(MI.getOperand(ImN).isImm()); 1123 unsigned S = MI.getOperand(ImN).getImm(); 1124 if (S == 0) 1125 return false; 1126 LostB = Width-S; 1127 LostE = Width; 1128 return true; 1129 } 1130 1131 // Check if the instruction is a lossy shift right, where the input being 1132 // shifted is the operand OpN of MI. If true, [LostB, LostE) is the range 1133 // of bit indices that are lost. 1134 bool RedundantInstrElimination::isLossyShiftRight(const MachineInstr &MI, 1135 unsigned OpN, unsigned &LostB, unsigned &LostE) { 1136 using namespace Hexagon; 1137 1138 unsigned Opc = MI.getOpcode(); 1139 unsigned ImN, RegN; 1140 switch (Opc) { 1141 case S2_asr_i_p: 1142 case S2_lsr_i_p: 1143 ImN = 2; 1144 RegN = 1; 1145 break; 1146 case S2_asr_i_p_acc: 1147 case S2_asr_i_p_and: 1148 case S2_asr_i_p_nac: 1149 case S2_asr_i_p_or: 1150 case S2_lsr_i_p_acc: 1151 case S2_lsr_i_p_and: 1152 case S2_lsr_i_p_nac: 1153 case S2_lsr_i_p_or: 1154 case S2_lsr_i_p_xacc: 1155 ImN = 3; 1156 RegN = 2; 1157 break; 1158 case S2_asr_i_r: 1159 case S2_lsr_i_r: 1160 ImN = 2; 1161 RegN = 1; 1162 break; 1163 case S4_andi_lsr_ri: 1164 case S4_ori_lsr_ri: 1165 case S4_addi_lsr_ri: 1166 case S4_subi_lsr_ri: 1167 case S2_asr_i_r_acc: 1168 case S2_asr_i_r_and: 1169 case S2_asr_i_r_nac: 1170 case S2_asr_i_r_or: 1171 case S2_lsr_i_r_acc: 1172 case S2_lsr_i_r_and: 1173 case S2_lsr_i_r_nac: 1174 case S2_lsr_i_r_or: 1175 case S2_lsr_i_r_xacc: 1176 ImN = 3; 1177 RegN = 2; 1178 break; 1179 1180 default: 1181 return false; 1182 } 1183 1184 if (RegN != OpN) 1185 return false; 1186 1187 assert(MI.getOperand(ImN).isImm()); 1188 unsigned S = MI.getOperand(ImN).getImm(); 1189 LostB = 0; 1190 LostE = S; 1191 return true; 1192 } 1193 1194 // Calculate the bit vector that corresponds to the used bits of register Reg. 1195 // The vector Bits has the same size, as the size of Reg in bits. If the cal- 1196 // culation fails (i.e. the used bits are unknown), it returns false. Other- 1197 // wise, it returns true and sets the corresponding bits in Bits. 1198 bool RedundantInstrElimination::computeUsedBits(unsigned Reg, BitVector &Bits) { 1199 BitVector Used(Bits.size()); 1200 RegisterSet Visited; 1201 std::vector<unsigned> Pending; 1202 Pending.push_back(Reg); 1203 1204 for (unsigned i = 0; i < Pending.size(); ++i) { 1205 unsigned R = Pending[i]; 1206 if (Visited.has(R)) 1207 continue; 1208 Visited.insert(R); 1209 for (auto I = MRI.use_begin(R), E = MRI.use_end(); I != E; ++I) { 1210 BitTracker::RegisterRef UR = *I; 1211 unsigned B, W; 1212 if (!HBS::getSubregMask(UR, B, W, MRI)) 1213 return false; 1214 MachineInstr &UseI = *I->getParent(); 1215 if (UseI.isPHI() || UseI.isCopy()) { 1216 unsigned DefR = UseI.getOperand(0).getReg(); 1217 if (!TargetRegisterInfo::isVirtualRegister(DefR)) 1218 return false; 1219 Pending.push_back(DefR); 1220 } else { 1221 if (!computeUsedBits(UseI, I.getOperandNo(), Used, B)) 1222 return false; 1223 } 1224 } 1225 } 1226 Bits |= Used; 1227 return true; 1228 } 1229 1230 // Calculate the bits used by instruction MI in a register in operand OpN. 1231 // Return true/false if the calculation succeeds/fails. If is succeeds, set 1232 // used bits in Bits. This function does not reset any bits in Bits, so 1233 // subsequent calls over different instructions will result in the union 1234 // of the used bits in all these instructions. 1235 // The register in question may be used with a sub-register, whereas Bits 1236 // holds the bits for the entire register. To keep track of that, the 1237 // argument Begin indicates where in Bits is the lowest-significant bit 1238 // of the register used in operand OpN. For example, in instruction: 1239 // vreg1 = S2_lsr_i_r vreg2:isub_hi, 10 1240 // the operand 1 is a 32-bit register, which happens to be a subregister 1241 // of the 64-bit register vreg2, and that subregister starts at position 32. 1242 // In this case Begin=32, since Bits[32] would be the lowest-significant bit 1243 // of vreg2:isub_hi. 1244 bool RedundantInstrElimination::computeUsedBits(const MachineInstr &MI, 1245 unsigned OpN, BitVector &Bits, uint16_t Begin) { 1246 unsigned Opc = MI.getOpcode(); 1247 BitVector T(Bits.size()); 1248 bool GotBits = HBS::getUsedBits(Opc, OpN, T, Begin, HII); 1249 // Even if we don't have bits yet, we could still provide some information 1250 // if the instruction is a lossy shift: the lost bits will be marked as 1251 // not used. 1252 unsigned LB, LE; 1253 if (isLossyShiftLeft(MI, OpN, LB, LE) || isLossyShiftRight(MI, OpN, LB, LE)) { 1254 assert(MI.getOperand(OpN).isReg()); 1255 BitTracker::RegisterRef RR = MI.getOperand(OpN); 1256 const TargetRegisterClass *RC = HBS::getFinalVRegClass(RR, MRI); 1257 uint16_t Width = RC->getSize()*8; 1258 1259 if (!GotBits) 1260 T.set(Begin, Begin+Width); 1261 assert(LB <= LE && LB < Width && LE <= Width); 1262 T.reset(Begin+LB, Begin+LE); 1263 GotBits = true; 1264 } 1265 if (GotBits) 1266 Bits |= T; 1267 return GotBits; 1268 } 1269 1270 // Calculates the used bits in RD ("defined register"), and checks if these 1271 // bits in RS ("used register") and RD are identical. 1272 bool RedundantInstrElimination::usedBitsEqual(BitTracker::RegisterRef RD, 1273 BitTracker::RegisterRef RS) { 1274 const BitTracker::RegisterCell &DC = BT.lookup(RD.Reg); 1275 const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg); 1276 1277 unsigned DB, DW; 1278 if (!HBS::getSubregMask(RD, DB, DW, MRI)) 1279 return false; 1280 unsigned SB, SW; 1281 if (!HBS::getSubregMask(RS, SB, SW, MRI)) 1282 return false; 1283 if (SW != DW) 1284 return false; 1285 1286 BitVector Used(DC.width()); 1287 if (!computeUsedBits(RD.Reg, Used)) 1288 return false; 1289 1290 for (unsigned i = 0; i != DW; ++i) 1291 if (Used[i+DB] && DC[DB+i] != SC[SB+i]) 1292 return false; 1293 return true; 1294 } 1295 1296 bool RedundantInstrElimination::processBlock(MachineBasicBlock &B, 1297 const RegisterSet&) { 1298 if (!BT.reached(&B)) 1299 return false; 1300 bool Changed = false; 1301 1302 for (auto I = B.begin(), E = B.end(), NextI = I; I != E; ++I) { 1303 NextI = std::next(I); 1304 MachineInstr *MI = &*I; 1305 1306 if (MI->getOpcode() == TargetOpcode::COPY) 1307 continue; 1308 if (MI->hasUnmodeledSideEffects() || MI->isInlineAsm()) 1309 continue; 1310 unsigned NumD = MI->getDesc().getNumDefs(); 1311 if (NumD != 1) 1312 continue; 1313 1314 BitTracker::RegisterRef RD = MI->getOperand(0); 1315 if (!BT.has(RD.Reg)) 1316 continue; 1317 const BitTracker::RegisterCell &DC = BT.lookup(RD.Reg); 1318 auto At = MI->isPHI() ? B.getFirstNonPHI() 1319 : MachineBasicBlock::iterator(MI); 1320 1321 // Find a source operand that is equal to the result. 1322 for (auto &Op : MI->uses()) { 1323 if (!Op.isReg()) 1324 continue; 1325 BitTracker::RegisterRef RS = Op; 1326 if (!BT.has(RS.Reg)) 1327 continue; 1328 if (!HBS::isTransparentCopy(RD, RS, MRI)) 1329 continue; 1330 1331 unsigned BN, BW; 1332 if (!HBS::getSubregMask(RS, BN, BW, MRI)) 1333 continue; 1334 1335 const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg); 1336 if (!usedBitsEqual(RD, RS) && !HBS::isEqual(DC, 0, SC, BN, BW)) 1337 continue; 1338 1339 // If found, replace the instruction with a COPY. 1340 const DebugLoc &DL = MI->getDebugLoc(); 1341 const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI); 1342 unsigned NewR = MRI.createVirtualRegister(FRC); 1343 MachineInstr *CopyI = 1344 BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR) 1345 .addReg(RS.Reg, 0, RS.Sub); 1346 HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI); 1347 // This pass can create copies between registers that don't have the 1348 // exact same values. Updating the tracker has to involve updating 1349 // all dependent cells. Example: 1350 // vreg1 = inst vreg2 ; vreg1 != vreg2, but used bits are equal 1351 // 1352 // vreg3 = copy vreg2 ; <- inserted 1353 // ... = vreg3 ; <- replaced from vreg2 1354 // Indirectly, we can create a "copy" between vreg1 and vreg2 even 1355 // though their exact values do not match. 1356 BT.visit(*CopyI); 1357 Changed = true; 1358 break; 1359 } 1360 } 1361 1362 return Changed; 1363 } 1364 1365 namespace { 1366 1367 // Recognize instructions that produce constant values known at compile-time. 1368 // Replace them with register definitions that load these constants directly. 1369 class ConstGeneration : public Transformation { 1370 public: 1371 ConstGeneration(BitTracker &bt, const HexagonInstrInfo &hii, 1372 MachineRegisterInfo &mri) 1373 : Transformation(true), HII(hii), MRI(mri), BT(bt) {} 1374 1375 bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override; 1376 static bool isTfrConst(const MachineInstr &MI); 1377 1378 private: 1379 unsigned genTfrConst(const TargetRegisterClass *RC, int64_t C, 1380 MachineBasicBlock &B, MachineBasicBlock::iterator At, DebugLoc &DL); 1381 1382 const HexagonInstrInfo &HII; 1383 MachineRegisterInfo &MRI; 1384 BitTracker &BT; 1385 }; 1386 1387 } // end anonymous namespace 1388 1389 bool ConstGeneration::isTfrConst(const MachineInstr &MI) { 1390 unsigned Opc = MI.getOpcode(); 1391 switch (Opc) { 1392 case Hexagon::A2_combineii: 1393 case Hexagon::A4_combineii: 1394 case Hexagon::A2_tfrsi: 1395 case Hexagon::A2_tfrpi: 1396 case Hexagon::PS_true: 1397 case Hexagon::PS_false: 1398 case Hexagon::CONST32: 1399 case Hexagon::CONST64: 1400 return true; 1401 } 1402 return false; 1403 } 1404 1405 // Generate a transfer-immediate instruction that is appropriate for the 1406 // register class and the actual value being transferred. 1407 unsigned ConstGeneration::genTfrConst(const TargetRegisterClass *RC, int64_t C, 1408 MachineBasicBlock &B, MachineBasicBlock::iterator At, DebugLoc &DL) { 1409 unsigned Reg = MRI.createVirtualRegister(RC); 1410 if (RC == &Hexagon::IntRegsRegClass) { 1411 BuildMI(B, At, DL, HII.get(Hexagon::A2_tfrsi), Reg) 1412 .addImm(int32_t(C)); 1413 return Reg; 1414 } 1415 1416 if (RC == &Hexagon::DoubleRegsRegClass) { 1417 if (isInt<8>(C)) { 1418 BuildMI(B, At, DL, HII.get(Hexagon::A2_tfrpi), Reg) 1419 .addImm(C); 1420 return Reg; 1421 } 1422 1423 unsigned Lo = Lo_32(C), Hi = Hi_32(C); 1424 if (isInt<8>(Lo) || isInt<8>(Hi)) { 1425 unsigned Opc = isInt<8>(Lo) ? Hexagon::A2_combineii 1426 : Hexagon::A4_combineii; 1427 BuildMI(B, At, DL, HII.get(Opc), Reg) 1428 .addImm(int32_t(Hi)) 1429 .addImm(int32_t(Lo)); 1430 return Reg; 1431 } 1432 1433 BuildMI(B, At, DL, HII.get(Hexagon::CONST64), Reg) 1434 .addImm(C); 1435 return Reg; 1436 } 1437 1438 if (RC == &Hexagon::PredRegsRegClass) { 1439 unsigned Opc; 1440 if (C == 0) 1441 Opc = Hexagon::PS_false; 1442 else if ((C & 0xFF) == 0xFF) 1443 Opc = Hexagon::PS_true; 1444 else 1445 return 0; 1446 BuildMI(B, At, DL, HII.get(Opc), Reg); 1447 return Reg; 1448 } 1449 1450 return 0; 1451 } 1452 1453 bool ConstGeneration::processBlock(MachineBasicBlock &B, const RegisterSet&) { 1454 if (!BT.reached(&B)) 1455 return false; 1456 bool Changed = false; 1457 RegisterSet Defs; 1458 1459 for (auto I = B.begin(), E = B.end(); I != E; ++I) { 1460 if (isTfrConst(*I)) 1461 continue; 1462 Defs.clear(); 1463 HBS::getInstrDefs(*I, Defs); 1464 if (Defs.count() != 1) 1465 continue; 1466 unsigned DR = Defs.find_first(); 1467 if (!TargetRegisterInfo::isVirtualRegister(DR)) 1468 continue; 1469 uint64_t U; 1470 const BitTracker::RegisterCell &DRC = BT.lookup(DR); 1471 if (HBS::getConst(DRC, 0, DRC.width(), U)) { 1472 int64_t C = U; 1473 DebugLoc DL = I->getDebugLoc(); 1474 auto At = I->isPHI() ? B.getFirstNonPHI() : I; 1475 unsigned ImmReg = genTfrConst(MRI.getRegClass(DR), C, B, At, DL); 1476 if (ImmReg) { 1477 HBS::replaceReg(DR, ImmReg, MRI); 1478 BT.put(ImmReg, DRC); 1479 Changed = true; 1480 } 1481 } 1482 } 1483 return Changed; 1484 } 1485 1486 namespace { 1487 1488 // Identify pairs of available registers which hold identical values. 1489 // In such cases, only one of them needs to be calculated, the other one 1490 // will be defined as a copy of the first. 1491 class CopyGeneration : public Transformation { 1492 public: 1493 CopyGeneration(BitTracker &bt, const HexagonInstrInfo &hii, 1494 const HexagonRegisterInfo &hri, MachineRegisterInfo &mri) 1495 : Transformation(true), HII(hii), HRI(hri), MRI(mri), BT(bt) {} 1496 1497 bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override; 1498 1499 private: 1500 bool findMatch(const BitTracker::RegisterRef &Inp, 1501 BitTracker::RegisterRef &Out, const RegisterSet &AVs); 1502 1503 const HexagonInstrInfo &HII; 1504 const HexagonRegisterInfo &HRI; 1505 MachineRegisterInfo &MRI; 1506 BitTracker &BT; 1507 RegisterSet Forbidden; 1508 }; 1509 1510 // Eliminate register copies RD = RS, by replacing the uses of RD with 1511 // with uses of RS. 1512 class CopyPropagation : public Transformation { 1513 public: 1514 CopyPropagation(const HexagonRegisterInfo &hri, MachineRegisterInfo &mri) 1515 : Transformation(false), HRI(hri), MRI(mri) {} 1516 1517 bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override; 1518 1519 static bool isCopyReg(unsigned Opc, bool NoConv); 1520 1521 private: 1522 bool propagateRegCopy(MachineInstr &MI); 1523 1524 const HexagonRegisterInfo &HRI; 1525 MachineRegisterInfo &MRI; 1526 }; 1527 1528 } // end anonymous namespace 1529 1530 /// Check if there is a register in AVs that is identical to Inp. If so, 1531 /// set Out to the found register. The output may be a pair Reg:Sub. 1532 bool CopyGeneration::findMatch(const BitTracker::RegisterRef &Inp, 1533 BitTracker::RegisterRef &Out, const RegisterSet &AVs) { 1534 if (!BT.has(Inp.Reg)) 1535 return false; 1536 const BitTracker::RegisterCell &InpRC = BT.lookup(Inp.Reg); 1537 auto *FRC = HBS::getFinalVRegClass(Inp, MRI); 1538 unsigned B, W; 1539 if (!HBS::getSubregMask(Inp, B, W, MRI)) 1540 return false; 1541 1542 for (unsigned R = AVs.find_first(); R; R = AVs.find_next(R)) { 1543 if (!BT.has(R) || Forbidden[R]) 1544 continue; 1545 const BitTracker::RegisterCell &RC = BT.lookup(R); 1546 unsigned RW = RC.width(); 1547 if (W == RW) { 1548 if (FRC != MRI.getRegClass(R)) 1549 continue; 1550 if (!HBS::isTransparentCopy(R, Inp, MRI)) 1551 continue; 1552 if (!HBS::isEqual(InpRC, B, RC, 0, W)) 1553 continue; 1554 Out.Reg = R; 1555 Out.Sub = 0; 1556 return true; 1557 } 1558 // Check if there is a super-register, whose part (with a subregister) 1559 // is equal to the input. 1560 // Only do double registers for now. 1561 if (W*2 != RW) 1562 continue; 1563 if (MRI.getRegClass(R) != &Hexagon::DoubleRegsRegClass) 1564 continue; 1565 1566 if (HBS::isEqual(InpRC, B, RC, 0, W)) 1567 Out.Sub = Hexagon::isub_lo; 1568 else if (HBS::isEqual(InpRC, B, RC, W, W)) 1569 Out.Sub = Hexagon::isub_hi; 1570 else 1571 continue; 1572 Out.Reg = R; 1573 if (HBS::isTransparentCopy(Out, Inp, MRI)) 1574 return true; 1575 } 1576 return false; 1577 } 1578 1579 bool CopyGeneration::processBlock(MachineBasicBlock &B, 1580 const RegisterSet &AVs) { 1581 if (!BT.reached(&B)) 1582 return false; 1583 RegisterSet AVB(AVs); 1584 bool Changed = false; 1585 RegisterSet Defs; 1586 1587 for (auto I = B.begin(), E = B.end(), NextI = I; I != E; 1588 ++I, AVB.insert(Defs)) { 1589 NextI = std::next(I); 1590 Defs.clear(); 1591 HBS::getInstrDefs(*I, Defs); 1592 1593 unsigned Opc = I->getOpcode(); 1594 if (CopyPropagation::isCopyReg(Opc, false) || 1595 ConstGeneration::isTfrConst(*I)) 1596 continue; 1597 1598 DebugLoc DL = I->getDebugLoc(); 1599 auto At = I->isPHI() ? B.getFirstNonPHI() : I; 1600 1601 for (unsigned R = Defs.find_first(); R; R = Defs.find_next(R)) { 1602 BitTracker::RegisterRef MR; 1603 auto *FRC = HBS::getFinalVRegClass(R, MRI); 1604 1605 if (findMatch(R, MR, AVB)) { 1606 unsigned NewR = MRI.createVirtualRegister(FRC); 1607 BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR) 1608 .addReg(MR.Reg, 0, MR.Sub); 1609 BT.put(BitTracker::RegisterRef(NewR), BT.get(MR)); 1610 HBS::replaceReg(R, NewR, MRI); 1611 Forbidden.insert(R); 1612 continue; 1613 } 1614 1615 if (FRC == &Hexagon::DoubleRegsRegClass || 1616 FRC == &Hexagon::VecDblRegsRegClass || 1617 FRC == &Hexagon::VecDblRegs128BRegClass) { 1618 // Try to generate REG_SEQUENCE. 1619 unsigned SubLo = HRI.getHexagonSubRegIndex(FRC, Hexagon::ps_sub_lo); 1620 unsigned SubHi = HRI.getHexagonSubRegIndex(FRC, Hexagon::ps_sub_hi); 1621 BitTracker::RegisterRef TL = { R, SubLo }; 1622 BitTracker::RegisterRef TH = { R, SubHi }; 1623 BitTracker::RegisterRef ML, MH; 1624 if (findMatch(TL, ML, AVB) && findMatch(TH, MH, AVB)) { 1625 auto *FRC = HBS::getFinalVRegClass(R, MRI); 1626 unsigned NewR = MRI.createVirtualRegister(FRC); 1627 BuildMI(B, At, DL, HII.get(TargetOpcode::REG_SEQUENCE), NewR) 1628 .addReg(ML.Reg, 0, ML.Sub) 1629 .addImm(SubLo) 1630 .addReg(MH.Reg, 0, MH.Sub) 1631 .addImm(SubHi); 1632 BT.put(BitTracker::RegisterRef(NewR), BT.get(R)); 1633 HBS::replaceReg(R, NewR, MRI); 1634 Forbidden.insert(R); 1635 } 1636 } 1637 } 1638 } 1639 1640 return Changed; 1641 } 1642 1643 bool CopyPropagation::isCopyReg(unsigned Opc, bool NoConv) { 1644 switch (Opc) { 1645 case TargetOpcode::COPY: 1646 case TargetOpcode::REG_SEQUENCE: 1647 case Hexagon::A4_combineir: 1648 case Hexagon::A4_combineri: 1649 return true; 1650 case Hexagon::A2_tfr: 1651 case Hexagon::A2_tfrp: 1652 case Hexagon::A2_combinew: 1653 case Hexagon::V6_vcombine: 1654 case Hexagon::V6_vcombine_128B: 1655 return NoConv; 1656 default: 1657 break; 1658 } 1659 return false; 1660 } 1661 1662 bool CopyPropagation::propagateRegCopy(MachineInstr &MI) { 1663 bool Changed = false; 1664 unsigned Opc = MI.getOpcode(); 1665 BitTracker::RegisterRef RD = MI.getOperand(0); 1666 assert(MI.getOperand(0).getSubReg() == 0); 1667 1668 switch (Opc) { 1669 case TargetOpcode::COPY: 1670 case Hexagon::A2_tfr: 1671 case Hexagon::A2_tfrp: { 1672 BitTracker::RegisterRef RS = MI.getOperand(1); 1673 if (!HBS::isTransparentCopy(RD, RS, MRI)) 1674 break; 1675 if (RS.Sub != 0) 1676 Changed = HBS::replaceRegWithSub(RD.Reg, RS.Reg, RS.Sub, MRI); 1677 else 1678 Changed = HBS::replaceReg(RD.Reg, RS.Reg, MRI); 1679 break; 1680 } 1681 case TargetOpcode::REG_SEQUENCE: { 1682 BitTracker::RegisterRef SL, SH; 1683 if (HBS::parseRegSequence(MI, SL, SH, MRI)) { 1684 const TargetRegisterClass *RC = MRI.getRegClass(RD.Reg); 1685 unsigned SubLo = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_lo); 1686 unsigned SubHi = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_hi); 1687 Changed = HBS::replaceSubWithSub(RD.Reg, SubLo, SL.Reg, SL.Sub, MRI); 1688 Changed |= HBS::replaceSubWithSub(RD.Reg, SubHi, SH.Reg, SH.Sub, MRI); 1689 } 1690 break; 1691 } 1692 case Hexagon::A2_combinew: 1693 case Hexagon::V6_vcombine: 1694 case Hexagon::V6_vcombine_128B: { 1695 const TargetRegisterClass *RC = MRI.getRegClass(RD.Reg); 1696 unsigned SubLo = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_lo); 1697 unsigned SubHi = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_hi); 1698 BitTracker::RegisterRef RH = MI.getOperand(1), RL = MI.getOperand(2); 1699 Changed = HBS::replaceSubWithSub(RD.Reg, SubLo, RL.Reg, RL.Sub, MRI); 1700 Changed |= HBS::replaceSubWithSub(RD.Reg, SubHi, RH.Reg, RH.Sub, MRI); 1701 break; 1702 } 1703 case Hexagon::A4_combineir: 1704 case Hexagon::A4_combineri: { 1705 unsigned SrcX = (Opc == Hexagon::A4_combineir) ? 2 : 1; 1706 unsigned Sub = (Opc == Hexagon::A4_combineir) ? Hexagon::isub_lo 1707 : Hexagon::isub_hi; 1708 BitTracker::RegisterRef RS = MI.getOperand(SrcX); 1709 Changed = HBS::replaceSubWithSub(RD.Reg, Sub, RS.Reg, RS.Sub, MRI); 1710 break; 1711 } 1712 } 1713 return Changed; 1714 } 1715 1716 bool CopyPropagation::processBlock(MachineBasicBlock &B, const RegisterSet&) { 1717 std::vector<MachineInstr*> Instrs; 1718 for (auto I = B.rbegin(), E = B.rend(); I != E; ++I) 1719 Instrs.push_back(&*I); 1720 1721 bool Changed = false; 1722 for (auto I : Instrs) { 1723 unsigned Opc = I->getOpcode(); 1724 if (!CopyPropagation::isCopyReg(Opc, true)) 1725 continue; 1726 Changed |= propagateRegCopy(*I); 1727 } 1728 1729 return Changed; 1730 } 1731 1732 namespace { 1733 1734 // Recognize patterns that can be simplified and replace them with the 1735 // simpler forms. 1736 // This is by no means complete 1737 class BitSimplification : public Transformation { 1738 public: 1739 BitSimplification(BitTracker &bt, const HexagonInstrInfo &hii, 1740 const HexagonRegisterInfo &hri, MachineRegisterInfo &mri, 1741 MachineFunction &mf) 1742 : Transformation(true), HII(hii), HRI(hri), MRI(mri), MF(mf), BT(bt) {} 1743 1744 bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override; 1745 1746 private: 1747 struct RegHalf : public BitTracker::RegisterRef { 1748 bool Low; // Low/High halfword. 1749 }; 1750 1751 bool matchHalf(unsigned SelfR, const BitTracker::RegisterCell &RC, 1752 unsigned B, RegHalf &RH); 1753 bool validateReg(BitTracker::RegisterRef R, unsigned Opc, unsigned OpNum); 1754 1755 bool matchPackhl(unsigned SelfR, const BitTracker::RegisterCell &RC, 1756 BitTracker::RegisterRef &Rs, BitTracker::RegisterRef &Rt); 1757 unsigned getCombineOpcode(bool HLow, bool LLow); 1758 1759 bool genStoreUpperHalf(MachineInstr *MI); 1760 bool genStoreImmediate(MachineInstr *MI); 1761 bool genPackhl(MachineInstr *MI, BitTracker::RegisterRef RD, 1762 const BitTracker::RegisterCell &RC); 1763 bool genExtractHalf(MachineInstr *MI, BitTracker::RegisterRef RD, 1764 const BitTracker::RegisterCell &RC); 1765 bool genCombineHalf(MachineInstr *MI, BitTracker::RegisterRef RD, 1766 const BitTracker::RegisterCell &RC); 1767 bool genExtractLow(MachineInstr *MI, BitTracker::RegisterRef RD, 1768 const BitTracker::RegisterCell &RC); 1769 bool simplifyTstbit(MachineInstr *MI, BitTracker::RegisterRef RD, 1770 const BitTracker::RegisterCell &RC); 1771 1772 const HexagonInstrInfo &HII; 1773 const HexagonRegisterInfo &HRI; 1774 MachineRegisterInfo &MRI; 1775 MachineFunction &MF; 1776 BitTracker &BT; 1777 }; 1778 1779 } // end anonymous namespace 1780 1781 // Check if the bits [B..B+16) in register cell RC form a valid halfword, 1782 // i.e. [0..16), [16..32), etc. of some register. If so, return true and 1783 // set the information about the found register in RH. 1784 bool BitSimplification::matchHalf(unsigned SelfR, 1785 const BitTracker::RegisterCell &RC, unsigned B, RegHalf &RH) { 1786 // XXX This could be searching in the set of available registers, in case 1787 // the match is not exact. 1788 1789 // Match 16-bit chunks, where the RC[B..B+15] references exactly one 1790 // register and all the bits B..B+15 match between RC and the register. 1791 // This is meant to match "v1[0-15]", where v1 = { [0]:0 [1-15]:v1... }, 1792 // and RC = { [0]:0 [1-15]:v1[1-15]... }. 1793 bool Low = false; 1794 unsigned I = B; 1795 while (I < B+16 && RC[I].num()) 1796 I++; 1797 if (I == B+16) 1798 return false; 1799 1800 unsigned Reg = RC[I].RefI.Reg; 1801 unsigned P = RC[I].RefI.Pos; // The RefI.Pos will be advanced by I-B. 1802 if (P < I-B) 1803 return false; 1804 unsigned Pos = P - (I-B); 1805 1806 if (Reg == 0 || Reg == SelfR) // Don't match "self". 1807 return false; 1808 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1809 return false; 1810 if (!BT.has(Reg)) 1811 return false; 1812 1813 const BitTracker::RegisterCell &SC = BT.lookup(Reg); 1814 if (Pos+16 > SC.width()) 1815 return false; 1816 1817 for (unsigned i = 0; i < 16; ++i) { 1818 const BitTracker::BitValue &RV = RC[i+B]; 1819 if (RV.Type == BitTracker::BitValue::Ref) { 1820 if (RV.RefI.Reg != Reg) 1821 return false; 1822 if (RV.RefI.Pos != i+Pos) 1823 return false; 1824 continue; 1825 } 1826 if (RC[i+B] != SC[i+Pos]) 1827 return false; 1828 } 1829 1830 unsigned Sub = 0; 1831 switch (Pos) { 1832 case 0: 1833 Sub = Hexagon::isub_lo; 1834 Low = true; 1835 break; 1836 case 16: 1837 Sub = Hexagon::isub_lo; 1838 Low = false; 1839 break; 1840 case 32: 1841 Sub = Hexagon::isub_hi; 1842 Low = true; 1843 break; 1844 case 48: 1845 Sub = Hexagon::isub_hi; 1846 Low = false; 1847 break; 1848 default: 1849 return false; 1850 } 1851 1852 RH.Reg = Reg; 1853 RH.Sub = Sub; 1854 RH.Low = Low; 1855 // If the subregister is not valid with the register, set it to 0. 1856 if (!HBS::getFinalVRegClass(RH, MRI)) 1857 RH.Sub = 0; 1858 1859 return true; 1860 } 1861 1862 bool BitSimplification::validateReg(BitTracker::RegisterRef R, unsigned Opc, 1863 unsigned OpNum) { 1864 auto *OpRC = HII.getRegClass(HII.get(Opc), OpNum, &HRI, MF); 1865 auto *RRC = HBS::getFinalVRegClass(R, MRI); 1866 return OpRC->hasSubClassEq(RRC); 1867 } 1868 1869 // Check if RC matches the pattern of a S2_packhl. If so, return true and 1870 // set the inputs Rs and Rt. 1871 bool BitSimplification::matchPackhl(unsigned SelfR, 1872 const BitTracker::RegisterCell &RC, BitTracker::RegisterRef &Rs, 1873 BitTracker::RegisterRef &Rt) { 1874 RegHalf L1, H1, L2, H2; 1875 1876 if (!matchHalf(SelfR, RC, 0, L2) || !matchHalf(SelfR, RC, 16, L1)) 1877 return false; 1878 if (!matchHalf(SelfR, RC, 32, H2) || !matchHalf(SelfR, RC, 48, H1)) 1879 return false; 1880 1881 // Rs = H1.L1, Rt = H2.L2 1882 if (H1.Reg != L1.Reg || H1.Sub != L1.Sub || H1.Low || !L1.Low) 1883 return false; 1884 if (H2.Reg != L2.Reg || H2.Sub != L2.Sub || H2.Low || !L2.Low) 1885 return false; 1886 1887 Rs = H1; 1888 Rt = H2; 1889 return true; 1890 } 1891 1892 unsigned BitSimplification::getCombineOpcode(bool HLow, bool LLow) { 1893 return HLow ? LLow ? Hexagon::A2_combine_ll 1894 : Hexagon::A2_combine_lh 1895 : LLow ? Hexagon::A2_combine_hl 1896 : Hexagon::A2_combine_hh; 1897 } 1898 1899 // If MI stores the upper halfword of a register (potentially obtained via 1900 // shifts or extracts), replace it with a storerf instruction. This could 1901 // cause the "extraction" code to become dead. 1902 bool BitSimplification::genStoreUpperHalf(MachineInstr *MI) { 1903 unsigned Opc = MI->getOpcode(); 1904 if (Opc != Hexagon::S2_storerh_io) 1905 return false; 1906 1907 MachineOperand &ValOp = MI->getOperand(2); 1908 BitTracker::RegisterRef RS = ValOp; 1909 if (!BT.has(RS.Reg)) 1910 return false; 1911 const BitTracker::RegisterCell &RC = BT.lookup(RS.Reg); 1912 RegHalf H; 1913 if (!matchHalf(0, RC, 0, H)) 1914 return false; 1915 if (H.Low) 1916 return false; 1917 MI->setDesc(HII.get(Hexagon::S2_storerf_io)); 1918 ValOp.setReg(H.Reg); 1919 ValOp.setSubReg(H.Sub); 1920 return true; 1921 } 1922 1923 // If MI stores a value known at compile-time, and the value is within a range 1924 // that avoids using constant-extenders, replace it with a store-immediate. 1925 bool BitSimplification::genStoreImmediate(MachineInstr *MI) { 1926 unsigned Opc = MI->getOpcode(); 1927 unsigned Align = 0; 1928 switch (Opc) { 1929 case Hexagon::S2_storeri_io: 1930 Align++; 1931 case Hexagon::S2_storerh_io: 1932 Align++; 1933 case Hexagon::S2_storerb_io: 1934 break; 1935 default: 1936 return false; 1937 } 1938 1939 // Avoid stores to frame-indices (due to an unknown offset). 1940 if (!MI->getOperand(0).isReg()) 1941 return false; 1942 MachineOperand &OffOp = MI->getOperand(1); 1943 if (!OffOp.isImm()) 1944 return false; 1945 1946 int64_t Off = OffOp.getImm(); 1947 // Offset is u6:a. Sadly, there is no isShiftedUInt(n,x). 1948 if (!isUIntN(6+Align, Off) || (Off & ((1<<Align)-1))) 1949 return false; 1950 // Source register: 1951 BitTracker::RegisterRef RS = MI->getOperand(2); 1952 if (!BT.has(RS.Reg)) 1953 return false; 1954 const BitTracker::RegisterCell &RC = BT.lookup(RS.Reg); 1955 uint64_t U; 1956 if (!HBS::getConst(RC, 0, RC.width(), U)) 1957 return false; 1958 1959 // Only consider 8-bit values to avoid constant-extenders. 1960 int V; 1961 switch (Opc) { 1962 case Hexagon::S2_storerb_io: 1963 V = int8_t(U); 1964 break; 1965 case Hexagon::S2_storerh_io: 1966 V = int16_t(U); 1967 break; 1968 case Hexagon::S2_storeri_io: 1969 V = int32_t(U); 1970 break; 1971 } 1972 if (!isInt<8>(V)) 1973 return false; 1974 1975 MI->RemoveOperand(2); 1976 switch (Opc) { 1977 case Hexagon::S2_storerb_io: 1978 MI->setDesc(HII.get(Hexagon::S4_storeirb_io)); 1979 break; 1980 case Hexagon::S2_storerh_io: 1981 MI->setDesc(HII.get(Hexagon::S4_storeirh_io)); 1982 break; 1983 case Hexagon::S2_storeri_io: 1984 MI->setDesc(HII.get(Hexagon::S4_storeiri_io)); 1985 break; 1986 } 1987 MI->addOperand(MachineOperand::CreateImm(V)); 1988 return true; 1989 } 1990 1991 // If MI is equivalent o S2_packhl, generate the S2_packhl. MI could be the 1992 // last instruction in a sequence that results in something equivalent to 1993 // the pack-halfwords. The intent is to cause the entire sequence to become 1994 // dead. 1995 bool BitSimplification::genPackhl(MachineInstr *MI, 1996 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) { 1997 unsigned Opc = MI->getOpcode(); 1998 if (Opc == Hexagon::S2_packhl) 1999 return false; 2000 BitTracker::RegisterRef Rs, Rt; 2001 if (!matchPackhl(RD.Reg, RC, Rs, Rt)) 2002 return false; 2003 if (!validateReg(Rs, Hexagon::S2_packhl, 1) || 2004 !validateReg(Rt, Hexagon::S2_packhl, 2)) 2005 return false; 2006 2007 MachineBasicBlock &B = *MI->getParent(); 2008 unsigned NewR = MRI.createVirtualRegister(&Hexagon::DoubleRegsRegClass); 2009 DebugLoc DL = MI->getDebugLoc(); 2010 auto At = MI->isPHI() ? B.getFirstNonPHI() 2011 : MachineBasicBlock::iterator(MI); 2012 BuildMI(B, At, DL, HII.get(Hexagon::S2_packhl), NewR) 2013 .addReg(Rs.Reg, 0, Rs.Sub) 2014 .addReg(Rt.Reg, 0, Rt.Sub); 2015 HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI); 2016 BT.put(BitTracker::RegisterRef(NewR), RC); 2017 return true; 2018 } 2019 2020 // If MI produces halfword of the input in the low half of the output, 2021 // replace it with zero-extend or extractu. 2022 bool BitSimplification::genExtractHalf(MachineInstr *MI, 2023 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) { 2024 RegHalf L; 2025 // Check for halfword in low 16 bits, zeros elsewhere. 2026 if (!matchHalf(RD.Reg, RC, 0, L) || !HBS::isZero(RC, 16, 16)) 2027 return false; 2028 2029 unsigned Opc = MI->getOpcode(); 2030 MachineBasicBlock &B = *MI->getParent(); 2031 DebugLoc DL = MI->getDebugLoc(); 2032 2033 // Prefer zxth, since zxth can go in any slot, while extractu only in 2034 // slots 2 and 3. 2035 unsigned NewR = 0; 2036 auto At = MI->isPHI() ? B.getFirstNonPHI() 2037 : MachineBasicBlock::iterator(MI); 2038 if (L.Low && Opc != Hexagon::A2_zxth) { 2039 if (validateReg(L, Hexagon::A2_zxth, 1)) { 2040 NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass); 2041 BuildMI(B, At, DL, HII.get(Hexagon::A2_zxth), NewR) 2042 .addReg(L.Reg, 0, L.Sub); 2043 } 2044 } else if (!L.Low && Opc != Hexagon::S2_lsr_i_r) { 2045 if (validateReg(L, Hexagon::S2_lsr_i_r, 1)) { 2046 NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass); 2047 BuildMI(B, MI, DL, HII.get(Hexagon::S2_lsr_i_r), NewR) 2048 .addReg(L.Reg, 0, L.Sub) 2049 .addImm(16); 2050 } 2051 } 2052 if (NewR == 0) 2053 return false; 2054 HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI); 2055 BT.put(BitTracker::RegisterRef(NewR), RC); 2056 return true; 2057 } 2058 2059 // If MI is equivalent to a combine(.L/.H, .L/.H) replace with with the 2060 // combine. 2061 bool BitSimplification::genCombineHalf(MachineInstr *MI, 2062 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) { 2063 RegHalf L, H; 2064 // Check for combine h/l 2065 if (!matchHalf(RD.Reg, RC, 0, L) || !matchHalf(RD.Reg, RC, 16, H)) 2066 return false; 2067 // Do nothing if this is just a reg copy. 2068 if (L.Reg == H.Reg && L.Sub == H.Sub && !H.Low && L.Low) 2069 return false; 2070 2071 unsigned Opc = MI->getOpcode(); 2072 unsigned COpc = getCombineOpcode(H.Low, L.Low); 2073 if (COpc == Opc) 2074 return false; 2075 if (!validateReg(H, COpc, 1) || !validateReg(L, COpc, 2)) 2076 return false; 2077 2078 MachineBasicBlock &B = *MI->getParent(); 2079 DebugLoc DL = MI->getDebugLoc(); 2080 unsigned NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass); 2081 auto At = MI->isPHI() ? B.getFirstNonPHI() 2082 : MachineBasicBlock::iterator(MI); 2083 BuildMI(B, At, DL, HII.get(COpc), NewR) 2084 .addReg(H.Reg, 0, H.Sub) 2085 .addReg(L.Reg, 0, L.Sub); 2086 HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI); 2087 BT.put(BitTracker::RegisterRef(NewR), RC); 2088 return true; 2089 } 2090 2091 // If MI resets high bits of a register and keeps the lower ones, replace it 2092 // with zero-extend byte/half, and-immediate, or extractu, as appropriate. 2093 bool BitSimplification::genExtractLow(MachineInstr *MI, 2094 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) { 2095 unsigned Opc = MI->getOpcode(); 2096 switch (Opc) { 2097 case Hexagon::A2_zxtb: 2098 case Hexagon::A2_zxth: 2099 case Hexagon::S2_extractu: 2100 return false; 2101 } 2102 if (Opc == Hexagon::A2_andir && MI->getOperand(2).isImm()) { 2103 int32_t Imm = MI->getOperand(2).getImm(); 2104 if (isInt<10>(Imm)) 2105 return false; 2106 } 2107 2108 if (MI->hasUnmodeledSideEffects() || MI->isInlineAsm()) 2109 return false; 2110 unsigned W = RC.width(); 2111 while (W > 0 && RC[W-1].is(0)) 2112 W--; 2113 if (W == 0 || W == RC.width()) 2114 return false; 2115 unsigned NewOpc = (W == 8) ? Hexagon::A2_zxtb 2116 : (W == 16) ? Hexagon::A2_zxth 2117 : (W < 10) ? Hexagon::A2_andir 2118 : Hexagon::S2_extractu; 2119 MachineBasicBlock &B = *MI->getParent(); 2120 DebugLoc DL = MI->getDebugLoc(); 2121 2122 for (auto &Op : MI->uses()) { 2123 if (!Op.isReg()) 2124 continue; 2125 BitTracker::RegisterRef RS = Op; 2126 if (!BT.has(RS.Reg)) 2127 continue; 2128 const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg); 2129 unsigned BN, BW; 2130 if (!HBS::getSubregMask(RS, BN, BW, MRI)) 2131 continue; 2132 if (BW < W || !HBS::isEqual(RC, 0, SC, BN, W)) 2133 continue; 2134 if (!validateReg(RS, NewOpc, 1)) 2135 continue; 2136 2137 unsigned NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass); 2138 auto At = MI->isPHI() ? B.getFirstNonPHI() 2139 : MachineBasicBlock::iterator(MI); 2140 auto MIB = BuildMI(B, At, DL, HII.get(NewOpc), NewR) 2141 .addReg(RS.Reg, 0, RS.Sub); 2142 if (NewOpc == Hexagon::A2_andir) 2143 MIB.addImm((1 << W) - 1); 2144 else if (NewOpc == Hexagon::S2_extractu) 2145 MIB.addImm(W).addImm(0); 2146 HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI); 2147 BT.put(BitTracker::RegisterRef(NewR), RC); 2148 return true; 2149 } 2150 return false; 2151 } 2152 2153 // Check for tstbit simplification opportunity, where the bit being checked 2154 // can be tracked back to another register. For example: 2155 // vreg2 = S2_lsr_i_r vreg1, 5 2156 // vreg3 = S2_tstbit_i vreg2, 0 2157 // => 2158 // vreg3 = S2_tstbit_i vreg1, 5 2159 bool BitSimplification::simplifyTstbit(MachineInstr *MI, 2160 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) { 2161 unsigned Opc = MI->getOpcode(); 2162 if (Opc != Hexagon::S2_tstbit_i) 2163 return false; 2164 2165 unsigned BN = MI->getOperand(2).getImm(); 2166 BitTracker::RegisterRef RS = MI->getOperand(1); 2167 unsigned F, W; 2168 DebugLoc DL = MI->getDebugLoc(); 2169 if (!BT.has(RS.Reg) || !HBS::getSubregMask(RS, F, W, MRI)) 2170 return false; 2171 MachineBasicBlock &B = *MI->getParent(); 2172 auto At = MI->isPHI() ? B.getFirstNonPHI() 2173 : MachineBasicBlock::iterator(MI); 2174 2175 const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg); 2176 const BitTracker::BitValue &V = SC[F+BN]; 2177 if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg != RS.Reg) { 2178 const TargetRegisterClass *TC = MRI.getRegClass(V.RefI.Reg); 2179 // Need to map V.RefI.Reg to a 32-bit register, i.e. if it is 2180 // a double register, need to use a subregister and adjust bit 2181 // number. 2182 unsigned P = std::numeric_limits<unsigned>::max(); 2183 BitTracker::RegisterRef RR(V.RefI.Reg, 0); 2184 if (TC == &Hexagon::DoubleRegsRegClass) { 2185 P = V.RefI.Pos; 2186 RR.Sub = Hexagon::isub_lo; 2187 if (P >= 32) { 2188 P -= 32; 2189 RR.Sub = Hexagon::isub_hi; 2190 } 2191 } else if (TC == &Hexagon::IntRegsRegClass) { 2192 P = V.RefI.Pos; 2193 } 2194 if (P != std::numeric_limits<unsigned>::max()) { 2195 unsigned NewR = MRI.createVirtualRegister(&Hexagon::PredRegsRegClass); 2196 BuildMI(B, At, DL, HII.get(Hexagon::S2_tstbit_i), NewR) 2197 .addReg(RR.Reg, 0, RR.Sub) 2198 .addImm(P); 2199 HBS::replaceReg(RD.Reg, NewR, MRI); 2200 BT.put(NewR, RC); 2201 return true; 2202 } 2203 } else if (V.is(0) || V.is(1)) { 2204 unsigned NewR = MRI.createVirtualRegister(&Hexagon::PredRegsRegClass); 2205 unsigned NewOpc = V.is(0) ? Hexagon::PS_false : Hexagon::PS_true; 2206 BuildMI(B, At, DL, HII.get(NewOpc), NewR); 2207 HBS::replaceReg(RD.Reg, NewR, MRI); 2208 return true; 2209 } 2210 2211 return false; 2212 } 2213 2214 bool BitSimplification::processBlock(MachineBasicBlock &B, 2215 const RegisterSet &AVs) { 2216 if (!BT.reached(&B)) 2217 return false; 2218 bool Changed = false; 2219 RegisterSet AVB = AVs; 2220 RegisterSet Defs; 2221 2222 for (auto I = B.begin(), E = B.end(); I != E; ++I, AVB.insert(Defs)) { 2223 MachineInstr *MI = &*I; 2224 Defs.clear(); 2225 HBS::getInstrDefs(*MI, Defs); 2226 2227 unsigned Opc = MI->getOpcode(); 2228 if (Opc == TargetOpcode::COPY || Opc == TargetOpcode::REG_SEQUENCE) 2229 continue; 2230 2231 if (MI->mayStore()) { 2232 bool T = genStoreUpperHalf(MI); 2233 T = T || genStoreImmediate(MI); 2234 Changed |= T; 2235 continue; 2236 } 2237 2238 if (Defs.count() != 1) 2239 continue; 2240 const MachineOperand &Op0 = MI->getOperand(0); 2241 if (!Op0.isReg() || !Op0.isDef()) 2242 continue; 2243 BitTracker::RegisterRef RD = Op0; 2244 if (!BT.has(RD.Reg)) 2245 continue; 2246 const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI); 2247 const BitTracker::RegisterCell &RC = BT.lookup(RD.Reg); 2248 2249 if (FRC->getID() == Hexagon::DoubleRegsRegClassID) { 2250 bool T = genPackhl(MI, RD, RC); 2251 Changed |= T; 2252 continue; 2253 } 2254 2255 if (FRC->getID() == Hexagon::IntRegsRegClassID) { 2256 bool T = genExtractHalf(MI, RD, RC); 2257 T = T || genCombineHalf(MI, RD, RC); 2258 T = T || genExtractLow(MI, RD, RC); 2259 Changed |= T; 2260 continue; 2261 } 2262 2263 if (FRC->getID() == Hexagon::PredRegsRegClassID) { 2264 bool T = simplifyTstbit(MI, RD, RC); 2265 Changed |= T; 2266 continue; 2267 } 2268 } 2269 return Changed; 2270 } 2271 2272 bool HexagonBitSimplify::runOnMachineFunction(MachineFunction &MF) { 2273 if (skipFunction(*MF.getFunction())) 2274 return false; 2275 2276 auto &HST = MF.getSubtarget<HexagonSubtarget>(); 2277 auto &HRI = *HST.getRegisterInfo(); 2278 auto &HII = *HST.getInstrInfo(); 2279 2280 MDT = &getAnalysis<MachineDominatorTree>(); 2281 MachineRegisterInfo &MRI = MF.getRegInfo(); 2282 bool Changed; 2283 2284 Changed = DeadCodeElimination(MF, *MDT).run(); 2285 2286 const HexagonEvaluator HE(HRI, MRI, HII, MF); 2287 BitTracker BT(HE, MF); 2288 DEBUG(BT.trace(true)); 2289 BT.run(); 2290 2291 MachineBasicBlock &Entry = MF.front(); 2292 2293 RegisterSet AIG; // Available registers for IG. 2294 ConstGeneration ImmG(BT, HII, MRI); 2295 Changed |= visitBlock(Entry, ImmG, AIG); 2296 2297 RegisterSet ARE; // Available registers for RIE. 2298 RedundantInstrElimination RIE(BT, HII, MRI); 2299 bool Ried = visitBlock(Entry, RIE, ARE); 2300 if (Ried) { 2301 Changed = true; 2302 BT.run(); 2303 } 2304 2305 RegisterSet ACG; // Available registers for CG. 2306 CopyGeneration CopyG(BT, HII, HRI, MRI); 2307 Changed |= visitBlock(Entry, CopyG, ACG); 2308 2309 RegisterSet ACP; // Available registers for CP. 2310 CopyPropagation CopyP(HRI, MRI); 2311 Changed |= visitBlock(Entry, CopyP, ACP); 2312 2313 Changed = DeadCodeElimination(MF, *MDT).run() || Changed; 2314 2315 BT.run(); 2316 RegisterSet ABS; // Available registers for BS. 2317 BitSimplification BitS(BT, HII, HRI, MRI, MF); 2318 Changed |= visitBlock(Entry, BitS, ABS); 2319 2320 Changed = DeadCodeElimination(MF, *MDT).run() || Changed; 2321 2322 if (Changed) { 2323 for (auto &B : MF) 2324 for (auto &I : B) 2325 I.clearKillInfo(); 2326 DeadCodeElimination(MF, *MDT).run(); 2327 } 2328 return Changed; 2329 } 2330 2331 // Recognize loops where the code at the end of the loop matches the code 2332 // before the entry of the loop, and the matching code is such that is can 2333 // be simplified. This pass relies on the bit simplification above and only 2334 // prepares code in a way that can be handled by the bit simplifcation. 2335 // 2336 // This is the motivating testcase (and explanation): 2337 // 2338 // { 2339 // loop0(.LBB0_2, r1) // %for.body.preheader 2340 // r5:4 = memd(r0++#8) 2341 // } 2342 // { 2343 // r3 = lsr(r4, #16) 2344 // r7:6 = combine(r5, r5) 2345 // } 2346 // { 2347 // r3 = insert(r5, #16, #16) 2348 // r7:6 = vlsrw(r7:6, #16) 2349 // } 2350 // .LBB0_2: 2351 // { 2352 // memh(r2+#4) = r5 2353 // memh(r2+#6) = r6 # R6 is really R5.H 2354 // } 2355 // { 2356 // r2 = add(r2, #8) 2357 // memh(r2+#0) = r4 2358 // memh(r2+#2) = r3 # R3 is really R4.H 2359 // } 2360 // { 2361 // r5:4 = memd(r0++#8) 2362 // } 2363 // { # "Shuffling" code that sets up R3 and R6 2364 // r3 = lsr(r4, #16) # so that their halves can be stored in the 2365 // r7:6 = combine(r5, r5) # next iteration. This could be folded into 2366 // } # the stores if the code was at the beginning 2367 // { # of the loop iteration. Since the same code 2368 // r3 = insert(r5, #16, #16) # precedes the loop, it can actually be moved 2369 // r7:6 = vlsrw(r7:6, #16) # there. 2370 // }:endloop0 2371 // 2372 // 2373 // The outcome: 2374 // 2375 // { 2376 // loop0(.LBB0_2, r1) 2377 // r5:4 = memd(r0++#8) 2378 // } 2379 // .LBB0_2: 2380 // { 2381 // memh(r2+#4) = r5 2382 // memh(r2+#6) = r5.h 2383 // } 2384 // { 2385 // r2 = add(r2, #8) 2386 // memh(r2+#0) = r4 2387 // memh(r2+#2) = r4.h 2388 // } 2389 // { 2390 // r5:4 = memd(r0++#8) 2391 // }:endloop0 2392 2393 namespace llvm { 2394 2395 FunctionPass *createHexagonLoopRescheduling(); 2396 void initializeHexagonLoopReschedulingPass(PassRegistry&); 2397 2398 } // end namespace llvm 2399 2400 namespace { 2401 2402 class HexagonLoopRescheduling : public MachineFunctionPass { 2403 public: 2404 static char ID; 2405 2406 HexagonLoopRescheduling() : MachineFunctionPass(ID), 2407 HII(nullptr), HRI(nullptr), MRI(nullptr), BTP(nullptr) { 2408 initializeHexagonLoopReschedulingPass(*PassRegistry::getPassRegistry()); 2409 } 2410 2411 bool runOnMachineFunction(MachineFunction &MF) override; 2412 2413 private: 2414 const HexagonInstrInfo *HII; 2415 const HexagonRegisterInfo *HRI; 2416 MachineRegisterInfo *MRI; 2417 BitTracker *BTP; 2418 2419 struct LoopCand { 2420 LoopCand(MachineBasicBlock *lb, MachineBasicBlock *pb, 2421 MachineBasicBlock *eb) : LB(lb), PB(pb), EB(eb) {} 2422 MachineBasicBlock *LB, *PB, *EB; 2423 }; 2424 typedef std::vector<MachineInstr*> InstrList; 2425 struct InstrGroup { 2426 BitTracker::RegisterRef Inp, Out; 2427 InstrList Ins; 2428 }; 2429 struct PhiInfo { 2430 PhiInfo(MachineInstr &P, MachineBasicBlock &B); 2431 unsigned DefR; 2432 BitTracker::RegisterRef LR, PR; // Loop Register, Preheader Register 2433 MachineBasicBlock *LB, *PB; // Loop Block, Preheader Block 2434 }; 2435 2436 static unsigned getDefReg(const MachineInstr *MI); 2437 bool isConst(unsigned Reg) const; 2438 bool isBitShuffle(const MachineInstr *MI, unsigned DefR) const; 2439 bool isStoreInput(const MachineInstr *MI, unsigned DefR) const; 2440 bool isShuffleOf(unsigned OutR, unsigned InpR) const; 2441 bool isSameShuffle(unsigned OutR1, unsigned InpR1, unsigned OutR2, 2442 unsigned &InpR2) const; 2443 void moveGroup(InstrGroup &G, MachineBasicBlock &LB, MachineBasicBlock &PB, 2444 MachineBasicBlock::iterator At, unsigned OldPhiR, unsigned NewPredR); 2445 bool processLoop(LoopCand &C); 2446 }; 2447 2448 } // end anonymous namespace 2449 2450 char HexagonLoopRescheduling::ID = 0; 2451 2452 INITIALIZE_PASS(HexagonLoopRescheduling, "hexagon-loop-resched", 2453 "Hexagon Loop Rescheduling", false, false) 2454 2455 HexagonLoopRescheduling::PhiInfo::PhiInfo(MachineInstr &P, 2456 MachineBasicBlock &B) { 2457 DefR = HexagonLoopRescheduling::getDefReg(&P); 2458 LB = &B; 2459 PB = nullptr; 2460 for (unsigned i = 1, n = P.getNumOperands(); i < n; i += 2) { 2461 const MachineOperand &OpB = P.getOperand(i+1); 2462 if (OpB.getMBB() == &B) { 2463 LR = P.getOperand(i); 2464 continue; 2465 } 2466 PB = OpB.getMBB(); 2467 PR = P.getOperand(i); 2468 } 2469 } 2470 2471 unsigned HexagonLoopRescheduling::getDefReg(const MachineInstr *MI) { 2472 RegisterSet Defs; 2473 HBS::getInstrDefs(*MI, Defs); 2474 if (Defs.count() != 1) 2475 return 0; 2476 return Defs.find_first(); 2477 } 2478 2479 bool HexagonLoopRescheduling::isConst(unsigned Reg) const { 2480 if (!BTP->has(Reg)) 2481 return false; 2482 const BitTracker::RegisterCell &RC = BTP->lookup(Reg); 2483 for (unsigned i = 0, w = RC.width(); i < w; ++i) { 2484 const BitTracker::BitValue &V = RC[i]; 2485 if (!V.is(0) && !V.is(1)) 2486 return false; 2487 } 2488 return true; 2489 } 2490 2491 bool HexagonLoopRescheduling::isBitShuffle(const MachineInstr *MI, 2492 unsigned DefR) const { 2493 unsigned Opc = MI->getOpcode(); 2494 switch (Opc) { 2495 case TargetOpcode::COPY: 2496 case Hexagon::S2_lsr_i_r: 2497 case Hexagon::S2_asr_i_r: 2498 case Hexagon::S2_asl_i_r: 2499 case Hexagon::S2_lsr_i_p: 2500 case Hexagon::S2_asr_i_p: 2501 case Hexagon::S2_asl_i_p: 2502 case Hexagon::S2_insert: 2503 case Hexagon::A2_or: 2504 case Hexagon::A2_orp: 2505 case Hexagon::A2_and: 2506 case Hexagon::A2_andp: 2507 case Hexagon::A2_combinew: 2508 case Hexagon::A4_combineri: 2509 case Hexagon::A4_combineir: 2510 case Hexagon::A2_combineii: 2511 case Hexagon::A4_combineii: 2512 case Hexagon::A2_combine_ll: 2513 case Hexagon::A2_combine_lh: 2514 case Hexagon::A2_combine_hl: 2515 case Hexagon::A2_combine_hh: 2516 return true; 2517 } 2518 return false; 2519 } 2520 2521 bool HexagonLoopRescheduling::isStoreInput(const MachineInstr *MI, 2522 unsigned InpR) const { 2523 for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) { 2524 const MachineOperand &Op = MI->getOperand(i); 2525 if (!Op.isReg()) 2526 continue; 2527 if (Op.getReg() == InpR) 2528 return i == n-1; 2529 } 2530 return false; 2531 } 2532 2533 bool HexagonLoopRescheduling::isShuffleOf(unsigned OutR, unsigned InpR) const { 2534 if (!BTP->has(OutR) || !BTP->has(InpR)) 2535 return false; 2536 const BitTracker::RegisterCell &OutC = BTP->lookup(OutR); 2537 for (unsigned i = 0, w = OutC.width(); i < w; ++i) { 2538 const BitTracker::BitValue &V = OutC[i]; 2539 if (V.Type != BitTracker::BitValue::Ref) 2540 continue; 2541 if (V.RefI.Reg != InpR) 2542 return false; 2543 } 2544 return true; 2545 } 2546 2547 bool HexagonLoopRescheduling::isSameShuffle(unsigned OutR1, unsigned InpR1, 2548 unsigned OutR2, unsigned &InpR2) const { 2549 if (!BTP->has(OutR1) || !BTP->has(InpR1) || !BTP->has(OutR2)) 2550 return false; 2551 const BitTracker::RegisterCell &OutC1 = BTP->lookup(OutR1); 2552 const BitTracker::RegisterCell &OutC2 = BTP->lookup(OutR2); 2553 unsigned W = OutC1.width(); 2554 unsigned MatchR = 0; 2555 if (W != OutC2.width()) 2556 return false; 2557 for (unsigned i = 0; i < W; ++i) { 2558 const BitTracker::BitValue &V1 = OutC1[i], &V2 = OutC2[i]; 2559 if (V1.Type != V2.Type || V1.Type == BitTracker::BitValue::One) 2560 return false; 2561 if (V1.Type != BitTracker::BitValue::Ref) 2562 continue; 2563 if (V1.RefI.Pos != V2.RefI.Pos) 2564 return false; 2565 if (V1.RefI.Reg != InpR1) 2566 return false; 2567 if (V2.RefI.Reg == 0 || V2.RefI.Reg == OutR2) 2568 return false; 2569 if (!MatchR) 2570 MatchR = V2.RefI.Reg; 2571 else if (V2.RefI.Reg != MatchR) 2572 return false; 2573 } 2574 InpR2 = MatchR; 2575 return true; 2576 } 2577 2578 void HexagonLoopRescheduling::moveGroup(InstrGroup &G, MachineBasicBlock &LB, 2579 MachineBasicBlock &PB, MachineBasicBlock::iterator At, unsigned OldPhiR, 2580 unsigned NewPredR) { 2581 DenseMap<unsigned,unsigned> RegMap; 2582 2583 const TargetRegisterClass *PhiRC = MRI->getRegClass(NewPredR); 2584 unsigned PhiR = MRI->createVirtualRegister(PhiRC); 2585 BuildMI(LB, At, At->getDebugLoc(), HII->get(TargetOpcode::PHI), PhiR) 2586 .addReg(NewPredR) 2587 .addMBB(&PB) 2588 .addReg(G.Inp.Reg) 2589 .addMBB(&LB); 2590 RegMap.insert(std::make_pair(G.Inp.Reg, PhiR)); 2591 2592 for (unsigned i = G.Ins.size(); i > 0; --i) { 2593 const MachineInstr *SI = G.Ins[i-1]; 2594 unsigned DR = getDefReg(SI); 2595 const TargetRegisterClass *RC = MRI->getRegClass(DR); 2596 unsigned NewDR = MRI->createVirtualRegister(RC); 2597 DebugLoc DL = SI->getDebugLoc(); 2598 2599 auto MIB = BuildMI(LB, At, DL, HII->get(SI->getOpcode()), NewDR); 2600 for (unsigned j = 0, m = SI->getNumOperands(); j < m; ++j) { 2601 const MachineOperand &Op = SI->getOperand(j); 2602 if (!Op.isReg()) { 2603 MIB.add(Op); 2604 continue; 2605 } 2606 if (!Op.isUse()) 2607 continue; 2608 unsigned UseR = RegMap[Op.getReg()]; 2609 MIB.addReg(UseR, 0, Op.getSubReg()); 2610 } 2611 RegMap.insert(std::make_pair(DR, NewDR)); 2612 } 2613 2614 HBS::replaceReg(OldPhiR, RegMap[G.Out.Reg], *MRI); 2615 } 2616 2617 bool HexagonLoopRescheduling::processLoop(LoopCand &C) { 2618 DEBUG(dbgs() << "Processing loop in BB#" << C.LB->getNumber() << "\n"); 2619 std::vector<PhiInfo> Phis; 2620 for (auto &I : *C.LB) { 2621 if (!I.isPHI()) 2622 break; 2623 unsigned PR = getDefReg(&I); 2624 if (isConst(PR)) 2625 continue; 2626 bool BadUse = false, GoodUse = false; 2627 for (auto UI = MRI->use_begin(PR), UE = MRI->use_end(); UI != UE; ++UI) { 2628 MachineInstr *UseI = UI->getParent(); 2629 if (UseI->getParent() != C.LB) { 2630 BadUse = true; 2631 break; 2632 } 2633 if (isBitShuffle(UseI, PR) || isStoreInput(UseI, PR)) 2634 GoodUse = true; 2635 } 2636 if (BadUse || !GoodUse) 2637 continue; 2638 2639 Phis.push_back(PhiInfo(I, *C.LB)); 2640 } 2641 2642 DEBUG({ 2643 dbgs() << "Phis: {"; 2644 for (auto &I : Phis) { 2645 dbgs() << ' ' << PrintReg(I.DefR, HRI) << "=phi(" 2646 << PrintReg(I.PR.Reg, HRI, I.PR.Sub) << ":b" << I.PB->getNumber() 2647 << ',' << PrintReg(I.LR.Reg, HRI, I.LR.Sub) << ":b" 2648 << I.LB->getNumber() << ')'; 2649 } 2650 dbgs() << " }\n"; 2651 }); 2652 2653 if (Phis.empty()) 2654 return false; 2655 2656 bool Changed = false; 2657 InstrList ShufIns; 2658 2659 // Go backwards in the block: for each bit shuffling instruction, check 2660 // if that instruction could potentially be moved to the front of the loop: 2661 // the output of the loop cannot be used in a non-shuffling instruction 2662 // in this loop. 2663 for (auto I = C.LB->rbegin(), E = C.LB->rend(); I != E; ++I) { 2664 if (I->isTerminator()) 2665 continue; 2666 if (I->isPHI()) 2667 break; 2668 2669 RegisterSet Defs; 2670 HBS::getInstrDefs(*I, Defs); 2671 if (Defs.count() != 1) 2672 continue; 2673 unsigned DefR = Defs.find_first(); 2674 if (!TargetRegisterInfo::isVirtualRegister(DefR)) 2675 continue; 2676 if (!isBitShuffle(&*I, DefR)) 2677 continue; 2678 2679 bool BadUse = false; 2680 for (auto UI = MRI->use_begin(DefR), UE = MRI->use_end(); UI != UE; ++UI) { 2681 MachineInstr *UseI = UI->getParent(); 2682 if (UseI->getParent() == C.LB) { 2683 if (UseI->isPHI()) { 2684 // If the use is in a phi node in this loop, then it should be 2685 // the value corresponding to the back edge. 2686 unsigned Idx = UI.getOperandNo(); 2687 if (UseI->getOperand(Idx+1).getMBB() != C.LB) 2688 BadUse = true; 2689 } else { 2690 auto F = find(ShufIns, UseI); 2691 if (F == ShufIns.end()) 2692 BadUse = true; 2693 } 2694 } else { 2695 // There is a use outside of the loop, but there is no epilog block 2696 // suitable for a copy-out. 2697 if (C.EB == nullptr) 2698 BadUse = true; 2699 } 2700 if (BadUse) 2701 break; 2702 } 2703 2704 if (BadUse) 2705 continue; 2706 ShufIns.push_back(&*I); 2707 } 2708 2709 // Partition the list of shuffling instructions into instruction groups, 2710 // where each group has to be moved as a whole (i.e. a group is a chain of 2711 // dependent instructions). A group produces a single live output register, 2712 // which is meant to be the input of the loop phi node (although this is 2713 // not checked here yet). It also uses a single register as its input, 2714 // which is some value produced in the loop body. After moving the group 2715 // to the beginning of the loop, that input register would need to be 2716 // the loop-carried register (through a phi node) instead of the (currently 2717 // loop-carried) output register. 2718 typedef std::vector<InstrGroup> InstrGroupList; 2719 InstrGroupList Groups; 2720 2721 for (unsigned i = 0, n = ShufIns.size(); i < n; ++i) { 2722 MachineInstr *SI = ShufIns[i]; 2723 if (SI == nullptr) 2724 continue; 2725 2726 InstrGroup G; 2727 G.Ins.push_back(SI); 2728 G.Out.Reg = getDefReg(SI); 2729 RegisterSet Inputs; 2730 HBS::getInstrUses(*SI, Inputs); 2731 2732 for (unsigned j = i+1; j < n; ++j) { 2733 MachineInstr *MI = ShufIns[j]; 2734 if (MI == nullptr) 2735 continue; 2736 RegisterSet Defs; 2737 HBS::getInstrDefs(*MI, Defs); 2738 // If this instruction does not define any pending inputs, skip it. 2739 if (!Defs.intersects(Inputs)) 2740 continue; 2741 // Otherwise, add it to the current group and remove the inputs that 2742 // are defined by MI. 2743 G.Ins.push_back(MI); 2744 Inputs.remove(Defs); 2745 // Then add all registers used by MI. 2746 HBS::getInstrUses(*MI, Inputs); 2747 ShufIns[j] = nullptr; 2748 } 2749 2750 // Only add a group if it requires at most one register. 2751 if (Inputs.count() > 1) 2752 continue; 2753 auto LoopInpEq = [G] (const PhiInfo &P) -> bool { 2754 return G.Out.Reg == P.LR.Reg; 2755 }; 2756 if (llvm::find_if(Phis, LoopInpEq) == Phis.end()) 2757 continue; 2758 2759 G.Inp.Reg = Inputs.find_first(); 2760 Groups.push_back(G); 2761 } 2762 2763 DEBUG({ 2764 for (unsigned i = 0, n = Groups.size(); i < n; ++i) { 2765 InstrGroup &G = Groups[i]; 2766 dbgs() << "Group[" << i << "] inp: " 2767 << PrintReg(G.Inp.Reg, HRI, G.Inp.Sub) 2768 << " out: " << PrintReg(G.Out.Reg, HRI, G.Out.Sub) << "\n"; 2769 for (unsigned j = 0, m = G.Ins.size(); j < m; ++j) 2770 dbgs() << " " << *G.Ins[j]; 2771 } 2772 }); 2773 2774 for (unsigned i = 0, n = Groups.size(); i < n; ++i) { 2775 InstrGroup &G = Groups[i]; 2776 if (!isShuffleOf(G.Out.Reg, G.Inp.Reg)) 2777 continue; 2778 auto LoopInpEq = [G] (const PhiInfo &P) -> bool { 2779 return G.Out.Reg == P.LR.Reg; 2780 }; 2781 auto F = llvm::find_if(Phis, LoopInpEq); 2782 if (F == Phis.end()) 2783 continue; 2784 unsigned PrehR = 0; 2785 if (!isSameShuffle(G.Out.Reg, G.Inp.Reg, F->PR.Reg, PrehR)) { 2786 const MachineInstr *DefPrehR = MRI->getVRegDef(F->PR.Reg); 2787 unsigned Opc = DefPrehR->getOpcode(); 2788 if (Opc != Hexagon::A2_tfrsi && Opc != Hexagon::A2_tfrpi) 2789 continue; 2790 if (!DefPrehR->getOperand(1).isImm()) 2791 continue; 2792 if (DefPrehR->getOperand(1).getImm() != 0) 2793 continue; 2794 const TargetRegisterClass *RC = MRI->getRegClass(G.Inp.Reg); 2795 if (RC != MRI->getRegClass(F->PR.Reg)) { 2796 PrehR = MRI->createVirtualRegister(RC); 2797 unsigned TfrI = (RC == &Hexagon::IntRegsRegClass) ? Hexagon::A2_tfrsi 2798 : Hexagon::A2_tfrpi; 2799 auto T = C.PB->getFirstTerminator(); 2800 DebugLoc DL = (T != C.PB->end()) ? T->getDebugLoc() : DebugLoc(); 2801 BuildMI(*C.PB, T, DL, HII->get(TfrI), PrehR) 2802 .addImm(0); 2803 } else { 2804 PrehR = F->PR.Reg; 2805 } 2806 } 2807 // isSameShuffle could match with PrehR being of a wider class than 2808 // G.Inp.Reg, for example if G shuffles the low 32 bits of its input, 2809 // it would match for the input being a 32-bit register, and PrehR 2810 // being a 64-bit register (where the low 32 bits match). This could 2811 // be handled, but for now skip these cases. 2812 if (MRI->getRegClass(PrehR) != MRI->getRegClass(G.Inp.Reg)) 2813 continue; 2814 moveGroup(G, *F->LB, *F->PB, F->LB->getFirstNonPHI(), F->DefR, PrehR); 2815 Changed = true; 2816 } 2817 2818 return Changed; 2819 } 2820 2821 bool HexagonLoopRescheduling::runOnMachineFunction(MachineFunction &MF) { 2822 if (skipFunction(*MF.getFunction())) 2823 return false; 2824 2825 auto &HST = MF.getSubtarget<HexagonSubtarget>(); 2826 HII = HST.getInstrInfo(); 2827 HRI = HST.getRegisterInfo(); 2828 MRI = &MF.getRegInfo(); 2829 const HexagonEvaluator HE(*HRI, *MRI, *HII, MF); 2830 BitTracker BT(HE, MF); 2831 DEBUG(BT.trace(true)); 2832 BT.run(); 2833 BTP = &BT; 2834 2835 std::vector<LoopCand> Cand; 2836 2837 for (auto &B : MF) { 2838 if (B.pred_size() != 2 || B.succ_size() != 2) 2839 continue; 2840 MachineBasicBlock *PB = nullptr; 2841 bool IsLoop = false; 2842 for (auto PI = B.pred_begin(), PE = B.pred_end(); PI != PE; ++PI) { 2843 if (*PI != &B) 2844 PB = *PI; 2845 else 2846 IsLoop = true; 2847 } 2848 if (!IsLoop) 2849 continue; 2850 2851 MachineBasicBlock *EB = nullptr; 2852 for (auto SI = B.succ_begin(), SE = B.succ_end(); SI != SE; ++SI) { 2853 if (*SI == &B) 2854 continue; 2855 // Set EP to the epilog block, if it has only 1 predecessor (i.e. the 2856 // edge from B to EP is non-critical. 2857 if ((*SI)->pred_size() == 1) 2858 EB = *SI; 2859 break; 2860 } 2861 2862 Cand.push_back(LoopCand(&B, PB, EB)); 2863 } 2864 2865 bool Changed = false; 2866 for (auto &C : Cand) 2867 Changed |= processLoop(C); 2868 2869 return Changed; 2870 } 2871 2872 //===----------------------------------------------------------------------===// 2873 // Public Constructor Functions 2874 //===----------------------------------------------------------------------===// 2875 2876 FunctionPass *llvm::createHexagonLoopRescheduling() { 2877 return new HexagonLoopRescheduling(); 2878 } 2879 2880 FunctionPass *llvm::createHexagonBitSimplify() { 2881 return new HexagonBitSimplify(); 2882 } 2883