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