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