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