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