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