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