1 //===- HexagonConstPropagation.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 "hcp" 11 12 #include "HexagonInstrInfo.h" 13 #include "HexagonRegisterInfo.h" 14 #include "HexagonSubtarget.h" 15 #include "llvm/ADT/APFloat.h" 16 #include "llvm/ADT/APInt.h" 17 #include "llvm/ADT/PostOrderIterator.h" 18 #include "llvm/ADT/SetVector.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/StringRef.h" 21 #include "llvm/CodeGen/MachineBasicBlock.h" 22 #include "llvm/CodeGen/MachineFunction.h" 23 #include "llvm/CodeGen/MachineFunctionPass.h" 24 #include "llvm/CodeGen/MachineInstr.h" 25 #include "llvm/CodeGen/MachineInstrBuilder.h" 26 #include "llvm/CodeGen/MachineOperand.h" 27 #include "llvm/CodeGen/MachineRegisterInfo.h" 28 #include "llvm/CodeGen/TargetRegisterInfo.h" 29 #include "llvm/CodeGen/TargetSubtargetInfo.h" 30 #include "llvm/IR/Constants.h" 31 #include "llvm/IR/Type.h" 32 #include "llvm/Pass.h" 33 #include "llvm/Support/Casting.h" 34 #include "llvm/Support/Compiler.h" 35 #include "llvm/Support/Debug.h" 36 #include "llvm/Support/ErrorHandling.h" 37 #include "llvm/Support/MathExtras.h" 38 #include "llvm/Support/raw_ostream.h" 39 #include <cassert> 40 #include <cstdint> 41 #include <cstring> 42 #include <iterator> 43 #include <map> 44 #include <queue> 45 #include <set> 46 #include <utility> 47 #include <vector> 48 49 using namespace llvm; 50 51 namespace { 52 53 // Properties of a value that are tracked by the propagation. 54 // A property that is marked as present (i.e. bit is set) dentes that the 55 // value is known (proven) to have this property. Not all combinations 56 // of bits make sense, for example Zero and NonZero are mutually exclusive, 57 // but on the other hand, Zero implies Finite. In this case, whenever 58 // the Zero property is present, Finite should also be present. 59 class ConstantProperties { 60 public: 61 enum { 62 Unknown = 0x0000, 63 Zero = 0x0001, 64 NonZero = 0x0002, 65 Finite = 0x0004, 66 Infinity = 0x0008, 67 NaN = 0x0010, 68 SignedZero = 0x0020, 69 NumericProperties = (Zero|NonZero|Finite|Infinity|NaN|SignedZero), 70 PosOrZero = 0x0100, 71 NegOrZero = 0x0200, 72 SignProperties = (PosOrZero|NegOrZero), 73 Everything = (NumericProperties|SignProperties) 74 }; 75 76 // For a given constant, deduce the set of trackable properties that this 77 // constant has. 78 static uint32_t deduce(const Constant *C); 79 }; 80 81 // A representation of a register as it can appear in a MachineOperand, 82 // i.e. a pair register:subregister. 83 struct Register { 84 unsigned Reg, SubReg; 85 86 explicit Register(unsigned R, unsigned SR = 0) : Reg(R), SubReg(SR) {} 87 explicit Register(const MachineOperand &MO) 88 : Reg(MO.getReg()), SubReg(MO.getSubReg()) {} 89 90 void print(const TargetRegisterInfo *TRI = nullptr) const { 91 dbgs() << printReg(Reg, TRI, SubReg); 92 } 93 94 bool operator== (const Register &R) const { 95 return (Reg == R.Reg) && (SubReg == R.SubReg); 96 } 97 }; 98 99 // Lattice cell, based on that was described in the W-Z paper on constant 100 // propagation. 101 // Latice cell will be allowed to hold multiple constant values. While 102 // multiple values would normally indicate "bottom", we can still derive 103 // some useful information from them. For example, comparison X > 0 104 // could be folded if all the values in the cell associated with X are 105 // positive. 106 class LatticeCell { 107 private: 108 enum { Normal, Top, Bottom }; 109 110 static const unsigned MaxCellSize = 4; 111 112 unsigned Kind:2; 113 unsigned Size:3; 114 unsigned IsSpecial:1; 115 unsigned :0; 116 117 public: 118 union { 119 uint32_t Properties; 120 const Constant *Value; 121 const Constant *Values[MaxCellSize]; 122 }; 123 124 LatticeCell() : Kind(Top), Size(0), IsSpecial(false) { 125 for (unsigned i = 0; i < MaxCellSize; ++i) 126 Values[i] = nullptr; 127 } 128 129 bool meet(const LatticeCell &L); 130 bool add(const Constant *C); 131 bool add(uint32_t Property); 132 uint32_t properties() const; 133 unsigned size() const { return Size; } 134 135 LatticeCell &operator= (const LatticeCell &L) { 136 if (this != &L) { 137 // This memcpy also copies Properties (when L.Size == 0). 138 uint32_t N = L.IsSpecial ? sizeof L.Properties 139 : L.Size*sizeof(const Constant*); 140 memcpy(Values, L.Values, N); 141 Kind = L.Kind; 142 Size = L.Size; 143 IsSpecial = L.IsSpecial; 144 } 145 return *this; 146 } 147 148 bool isSingle() const { return size() == 1; } 149 bool isProperty() const { return IsSpecial; } 150 bool isTop() const { return Kind == Top; } 151 bool isBottom() const { return Kind == Bottom; } 152 153 bool setBottom() { 154 bool Changed = (Kind != Bottom); 155 Kind = Bottom; 156 Size = 0; 157 IsSpecial = false; 158 return Changed; 159 } 160 161 void print(raw_ostream &os) const; 162 163 private: 164 void setProperty() { 165 IsSpecial = true; 166 Size = 0; 167 Kind = Normal; 168 } 169 170 bool convertToProperty(); 171 }; 172 173 #ifndef NDEBUG 174 raw_ostream &operator<< (raw_ostream &os, const LatticeCell &L) { 175 L.print(os); 176 return os; 177 } 178 #endif 179 180 class MachineConstEvaluator; 181 182 class MachineConstPropagator { 183 public: 184 MachineConstPropagator(MachineConstEvaluator &E) : MCE(E) { 185 Bottom.setBottom(); 186 } 187 188 // Mapping: vreg -> cell 189 // The keys are registers _without_ subregisters. This won't allow 190 // definitions in the form of "vreg:subreg = ...". Such definitions 191 // would be questionable from the point of view of SSA, since the "vreg" 192 // could not be initialized in its entirety (specifically, an instruction 193 // defining the "other part" of "vreg" would also count as a definition 194 // of "vreg", which would violate the SSA). 195 // If a value of a pair vreg:subreg needs to be obtained, the cell for 196 // "vreg" needs to be looked up, and then the value of subregister "subreg" 197 // needs to be evaluated. 198 class CellMap { 199 public: 200 CellMap() { 201 assert(Top.isTop()); 202 Bottom.setBottom(); 203 } 204 205 void clear() { Map.clear(); } 206 207 bool has(unsigned R) const { 208 // All non-virtual registers are considered "bottom". 209 if (!TargetRegisterInfo::isVirtualRegister(R)) 210 return true; 211 MapType::const_iterator F = Map.find(R); 212 return F != Map.end(); 213 } 214 215 const LatticeCell &get(unsigned R) const { 216 if (!TargetRegisterInfo::isVirtualRegister(R)) 217 return Bottom; 218 MapType::const_iterator F = Map.find(R); 219 if (F != Map.end()) 220 return F->second; 221 return Top; 222 } 223 224 // Invalidates any const references. 225 void update(unsigned R, const LatticeCell &L) { 226 Map[R] = L; 227 } 228 229 void print(raw_ostream &os, const TargetRegisterInfo &TRI) const; 230 231 private: 232 using MapType = std::map<unsigned, LatticeCell>; 233 234 MapType Map; 235 // To avoid creating "top" entries, return a const reference to 236 // this cell in "get". Also, have a "Bottom" cell to return from 237 // get when a value of a physical register is requested. 238 LatticeCell Top, Bottom; 239 240 public: 241 using const_iterator = MapType::const_iterator; 242 243 const_iterator begin() const { return Map.begin(); } 244 const_iterator end() const { return Map.end(); } 245 }; 246 247 bool run(MachineFunction &MF); 248 249 private: 250 void visitPHI(const MachineInstr &PN); 251 void visitNonBranch(const MachineInstr &MI); 252 void visitBranchesFrom(const MachineInstr &BrI); 253 void visitUsesOf(unsigned R); 254 bool computeBlockSuccessors(const MachineBasicBlock *MB, 255 SetVector<const MachineBasicBlock*> &Targets); 256 void removeCFGEdge(MachineBasicBlock *From, MachineBasicBlock *To); 257 258 void propagate(MachineFunction &MF); 259 bool rewrite(MachineFunction &MF); 260 261 MachineRegisterInfo *MRI; 262 MachineConstEvaluator &MCE; 263 264 using CFGEdge = std::pair<unsigned, unsigned>; 265 using SetOfCFGEdge = std::set<CFGEdge>; 266 using SetOfInstr = std::set<const MachineInstr *>; 267 using QueueOfCFGEdge = std::queue<CFGEdge>; 268 269 LatticeCell Bottom; 270 CellMap Cells; 271 SetOfCFGEdge EdgeExec; 272 SetOfInstr InstrExec; 273 QueueOfCFGEdge FlowQ; 274 }; 275 276 // The "evaluator/rewriter" of machine instructions. This is an abstract 277 // base class that provides the interface that the propagator will use, 278 // as well as some helper functions that are target-independent. 279 class MachineConstEvaluator { 280 public: 281 MachineConstEvaluator(MachineFunction &Fn) 282 : TRI(*Fn.getSubtarget().getRegisterInfo()), 283 MF(Fn), CX(Fn.getFunction().getContext()) {} 284 virtual ~MachineConstEvaluator() = default; 285 286 // The required interface: 287 // - A set of three "evaluate" functions. Each returns "true" if the 288 // computation succeeded, "false" otherwise. 289 // (1) Given an instruction MI, and the map with input values "Inputs", 290 // compute the set of output values "Outputs". An example of when 291 // the computation can "fail" is if MI is not an instruction that 292 // is recognized by the evaluator. 293 // (2) Given a register R (as reg:subreg), compute the cell that 294 // corresponds to the "subreg" part of the given register. 295 // (3) Given a branch instruction BrI, compute the set of target blocks. 296 // If the branch can fall-through, add null (0) to the list of 297 // possible targets. 298 // - A function "rewrite", that given the cell map after propagation, 299 // could rewrite instruction MI in a more beneficial form. Return 300 // "true" if a change has been made, "false" otherwise. 301 using CellMap = MachineConstPropagator::CellMap; 302 virtual bool evaluate(const MachineInstr &MI, const CellMap &Inputs, 303 CellMap &Outputs) = 0; 304 virtual bool evaluate(const Register &R, const LatticeCell &SrcC, 305 LatticeCell &Result) = 0; 306 virtual bool evaluate(const MachineInstr &BrI, const CellMap &Inputs, 307 SetVector<const MachineBasicBlock*> &Targets, 308 bool &CanFallThru) = 0; 309 virtual bool rewrite(MachineInstr &MI, const CellMap &Inputs) = 0; 310 311 const TargetRegisterInfo &TRI; 312 313 protected: 314 MachineFunction &MF; 315 LLVMContext &CX; 316 317 struct Comparison { 318 enum { 319 Unk = 0x00, 320 EQ = 0x01, 321 NE = 0x02, 322 L = 0x04, // Less-than property. 323 G = 0x08, // Greater-than property. 324 U = 0x40, // Unsigned property. 325 LTs = L, 326 LEs = L | EQ, 327 GTs = G, 328 GEs = G | EQ, 329 LTu = L | U, 330 LEu = L | EQ | U, 331 GTu = G | U, 332 GEu = G | EQ | U 333 }; 334 335 static uint32_t negate(uint32_t Cmp) { 336 if (Cmp == EQ) 337 return NE; 338 if (Cmp == NE) 339 return EQ; 340 assert((Cmp & (L|G)) != (L|G)); 341 return Cmp ^ (L|G); 342 } 343 }; 344 345 // Helper functions. 346 347 bool getCell(const Register &R, const CellMap &Inputs, LatticeCell &RC); 348 bool constToInt(const Constant *C, APInt &Val) const; 349 bool constToFloat(const Constant *C, APFloat &Val) const; 350 const ConstantInt *intToConst(const APInt &Val) const; 351 352 // Compares. 353 bool evaluateCMPrr(uint32_t Cmp, const Register &R1, const Register &R2, 354 const CellMap &Inputs, bool &Result); 355 bool evaluateCMPri(uint32_t Cmp, const Register &R1, const APInt &A2, 356 const CellMap &Inputs, bool &Result); 357 bool evaluateCMPrp(uint32_t Cmp, const Register &R1, uint64_t Props2, 358 const CellMap &Inputs, bool &Result); 359 bool evaluateCMPii(uint32_t Cmp, const APInt &A1, const APInt &A2, 360 bool &Result); 361 bool evaluateCMPpi(uint32_t Cmp, uint32_t Props, const APInt &A2, 362 bool &Result); 363 bool evaluateCMPpp(uint32_t Cmp, uint32_t Props1, uint32_t Props2, 364 bool &Result); 365 366 bool evaluateCOPY(const Register &R1, const CellMap &Inputs, 367 LatticeCell &Result); 368 369 // Logical operations. 370 bool evaluateANDrr(const Register &R1, const Register &R2, 371 const CellMap &Inputs, LatticeCell &Result); 372 bool evaluateANDri(const Register &R1, const APInt &A2, 373 const CellMap &Inputs, LatticeCell &Result); 374 bool evaluateANDii(const APInt &A1, const APInt &A2, APInt &Result); 375 bool evaluateORrr(const Register &R1, const Register &R2, 376 const CellMap &Inputs, LatticeCell &Result); 377 bool evaluateORri(const Register &R1, const APInt &A2, 378 const CellMap &Inputs, LatticeCell &Result); 379 bool evaluateORii(const APInt &A1, const APInt &A2, APInt &Result); 380 bool evaluateXORrr(const Register &R1, const Register &R2, 381 const CellMap &Inputs, LatticeCell &Result); 382 bool evaluateXORri(const Register &R1, const APInt &A2, 383 const CellMap &Inputs, LatticeCell &Result); 384 bool evaluateXORii(const APInt &A1, const APInt &A2, APInt &Result); 385 386 // Extensions. 387 bool evaluateZEXTr(const Register &R1, unsigned Width, unsigned Bits, 388 const CellMap &Inputs, LatticeCell &Result); 389 bool evaluateZEXTi(const APInt &A1, unsigned Width, unsigned Bits, 390 APInt &Result); 391 bool evaluateSEXTr(const Register &R1, unsigned Width, unsigned Bits, 392 const CellMap &Inputs, LatticeCell &Result); 393 bool evaluateSEXTi(const APInt &A1, unsigned Width, unsigned Bits, 394 APInt &Result); 395 396 // Leading/trailing bits. 397 bool evaluateCLBr(const Register &R1, bool Zeros, bool Ones, 398 const CellMap &Inputs, LatticeCell &Result); 399 bool evaluateCLBi(const APInt &A1, bool Zeros, bool Ones, APInt &Result); 400 bool evaluateCTBr(const Register &R1, bool Zeros, bool Ones, 401 const CellMap &Inputs, LatticeCell &Result); 402 bool evaluateCTBi(const APInt &A1, bool Zeros, bool Ones, APInt &Result); 403 404 // Bitfield extract. 405 bool evaluateEXTRACTr(const Register &R1, unsigned Width, unsigned Bits, 406 unsigned Offset, bool Signed, const CellMap &Inputs, 407 LatticeCell &Result); 408 bool evaluateEXTRACTi(const APInt &A1, unsigned Bits, unsigned Offset, 409 bool Signed, APInt &Result); 410 // Vector operations. 411 bool evaluateSplatr(const Register &R1, unsigned Bits, unsigned Count, 412 const CellMap &Inputs, LatticeCell &Result); 413 bool evaluateSplati(const APInt &A1, unsigned Bits, unsigned Count, 414 APInt &Result); 415 }; 416 417 } // end anonymous namespace 418 419 uint32_t ConstantProperties::deduce(const Constant *C) { 420 if (isa<ConstantInt>(C)) { 421 const ConstantInt *CI = cast<ConstantInt>(C); 422 if (CI->isZero()) 423 return Zero | PosOrZero | NegOrZero | Finite; 424 uint32_t Props = (NonZero | Finite); 425 if (CI->isNegative()) 426 return Props | NegOrZero; 427 return Props | PosOrZero; 428 } 429 430 if (isa<ConstantFP>(C)) { 431 const ConstantFP *CF = cast<ConstantFP>(C); 432 uint32_t Props = CF->isNegative() ? (NegOrZero|NonZero) 433 : PosOrZero; 434 if (CF->isZero()) 435 return (Props & ~NumericProperties) | (Zero|Finite); 436 Props = (Props & ~NumericProperties) | NonZero; 437 if (CF->isNaN()) 438 return (Props & ~NumericProperties) | NaN; 439 const APFloat &Val = CF->getValueAPF(); 440 if (Val.isInfinity()) 441 return (Props & ~NumericProperties) | Infinity; 442 Props |= Finite; 443 return Props; 444 } 445 446 return Unknown; 447 } 448 449 // Convert a cell from a set of specific values to a cell that tracks 450 // properties. 451 bool LatticeCell::convertToProperty() { 452 if (isProperty()) 453 return false; 454 // Corner case: converting a fresh (top) cell to "special". 455 // This can happen, when adding a property to a top cell. 456 uint32_t Everything = ConstantProperties::Everything; 457 uint32_t Ps = !isTop() ? properties() 458 : Everything; 459 if (Ps != ConstantProperties::Unknown) { 460 Properties = Ps; 461 setProperty(); 462 } else { 463 setBottom(); 464 } 465 return true; 466 } 467 468 #ifndef NDEBUG 469 void LatticeCell::print(raw_ostream &os) const { 470 if (isProperty()) { 471 os << "{ "; 472 uint32_t Ps = properties(); 473 if (Ps & ConstantProperties::Zero) 474 os << "zero "; 475 if (Ps & ConstantProperties::NonZero) 476 os << "nonzero "; 477 if (Ps & ConstantProperties::Finite) 478 os << "finite "; 479 if (Ps & ConstantProperties::Infinity) 480 os << "infinity "; 481 if (Ps & ConstantProperties::NaN) 482 os << "nan "; 483 if (Ps & ConstantProperties::PosOrZero) 484 os << "poz "; 485 if (Ps & ConstantProperties::NegOrZero) 486 os << "nez "; 487 os << '}'; 488 return; 489 } 490 491 os << "{ "; 492 if (isBottom()) { 493 os << "bottom"; 494 } else if (isTop()) { 495 os << "top"; 496 } else { 497 for (unsigned i = 0; i < size(); ++i) { 498 const Constant *C = Values[i]; 499 if (i != 0) 500 os << ", "; 501 C->print(os); 502 } 503 } 504 os << " }"; 505 } 506 #endif 507 508 // "Meet" operation on two cells. This is the key of the propagation 509 // algorithm. 510 bool LatticeCell::meet(const LatticeCell &L) { 511 bool Changed = false; 512 if (L.isBottom()) 513 Changed = setBottom(); 514 if (isBottom() || L.isTop()) 515 return Changed; 516 if (isTop()) { 517 *this = L; 518 // L can be neither Top nor Bottom, so *this must have changed. 519 return true; 520 } 521 522 // Top/bottom cases covered. Need to integrate L's set into ours. 523 if (L.isProperty()) 524 return add(L.properties()); 525 for (unsigned i = 0; i < L.size(); ++i) { 526 const Constant *LC = L.Values[i]; 527 Changed |= add(LC); 528 } 529 return Changed; 530 } 531 532 // Add a new constant to the cell. This is actually where the cell update 533 // happens. If a cell has room for more constants, the new constant is added. 534 // Otherwise, the cell is converted to a "property" cell (i.e. a cell that 535 // will track properties of the associated values, and not the values 536 // themselves. Care is taken to handle special cases, like "bottom", etc. 537 bool LatticeCell::add(const Constant *LC) { 538 assert(LC); 539 if (isBottom()) 540 return false; 541 542 if (!isProperty()) { 543 // Cell is not special. Try to add the constant here first, 544 // if there is room. 545 unsigned Index = 0; 546 while (Index < Size) { 547 const Constant *C = Values[Index]; 548 // If the constant is already here, no change is needed. 549 if (C == LC) 550 return false; 551 Index++; 552 } 553 if (Index < MaxCellSize) { 554 Values[Index] = LC; 555 Kind = Normal; 556 Size++; 557 return true; 558 } 559 } 560 561 bool Changed = false; 562 563 // This cell is special, or is not special, but is full. After this 564 // it will be special. 565 Changed = convertToProperty(); 566 uint32_t Ps = properties(); 567 uint32_t NewPs = Ps & ConstantProperties::deduce(LC); 568 if (NewPs == ConstantProperties::Unknown) { 569 setBottom(); 570 return true; 571 } 572 if (Ps != NewPs) { 573 Properties = NewPs; 574 Changed = true; 575 } 576 return Changed; 577 } 578 579 // Add a property to the cell. This will force the cell to become a property- 580 // tracking cell. 581 bool LatticeCell::add(uint32_t Property) { 582 bool Changed = convertToProperty(); 583 uint32_t Ps = properties(); 584 if (Ps == (Ps & Property)) 585 return Changed; 586 Properties = Property & Ps; 587 return true; 588 } 589 590 // Return the properties of the values in the cell. This is valid for any 591 // cell, and does not alter the cell itself. 592 uint32_t LatticeCell::properties() const { 593 if (isProperty()) 594 return Properties; 595 assert(!isTop() && "Should not call this for a top cell"); 596 if (isBottom()) 597 return ConstantProperties::Unknown; 598 599 assert(size() > 0 && "Empty cell"); 600 uint32_t Ps = ConstantProperties::deduce(Values[0]); 601 for (unsigned i = 1; i < size(); ++i) { 602 if (Ps == ConstantProperties::Unknown) 603 break; 604 Ps &= ConstantProperties::deduce(Values[i]); 605 } 606 return Ps; 607 } 608 609 #ifndef NDEBUG 610 void MachineConstPropagator::CellMap::print(raw_ostream &os, 611 const TargetRegisterInfo &TRI) const { 612 for (auto &I : Map) 613 dbgs() << " " << printReg(I.first, &TRI) << " -> " << I.second << '\n'; 614 } 615 #endif 616 617 void MachineConstPropagator::visitPHI(const MachineInstr &PN) { 618 const MachineBasicBlock *MB = PN.getParent(); 619 unsigned MBN = MB->getNumber(); 620 LLVM_DEBUG(dbgs() << "Visiting FI(" << printMBBReference(*MB) << "): " << PN); 621 622 const MachineOperand &MD = PN.getOperand(0); 623 Register DefR(MD); 624 assert(TargetRegisterInfo::isVirtualRegister(DefR.Reg)); 625 626 bool Changed = false; 627 628 // If the def has a sub-register, set the corresponding cell to "bottom". 629 if (DefR.SubReg) { 630 Bottomize: 631 const LatticeCell &T = Cells.get(DefR.Reg); 632 Changed = !T.isBottom(); 633 Cells.update(DefR.Reg, Bottom); 634 if (Changed) 635 visitUsesOf(DefR.Reg); 636 return; 637 } 638 639 LatticeCell DefC = Cells.get(DefR.Reg); 640 641 for (unsigned i = 1, n = PN.getNumOperands(); i < n; i += 2) { 642 const MachineBasicBlock *PB = PN.getOperand(i+1).getMBB(); 643 unsigned PBN = PB->getNumber(); 644 if (!EdgeExec.count(CFGEdge(PBN, MBN))) { 645 LLVM_DEBUG(dbgs() << " edge " << printMBBReference(*PB) << "->" 646 << printMBBReference(*MB) << " not executable\n"); 647 continue; 648 } 649 const MachineOperand &SO = PN.getOperand(i); 650 Register UseR(SO); 651 // If the input is not a virtual register, we don't really know what 652 // value it holds. 653 if (!TargetRegisterInfo::isVirtualRegister(UseR.Reg)) 654 goto Bottomize; 655 // If there is no cell for an input register, it means top. 656 if (!Cells.has(UseR.Reg)) 657 continue; 658 659 LatticeCell SrcC; 660 bool Eval = MCE.evaluate(UseR, Cells.get(UseR.Reg), SrcC); 661 LLVM_DEBUG(dbgs() << " edge from " << printMBBReference(*PB) << ": " 662 << printReg(UseR.Reg, &MCE.TRI, UseR.SubReg) << SrcC 663 << '\n'); 664 Changed |= Eval ? DefC.meet(SrcC) 665 : DefC.setBottom(); 666 Cells.update(DefR.Reg, DefC); 667 if (DefC.isBottom()) 668 break; 669 } 670 if (Changed) 671 visitUsesOf(DefR.Reg); 672 } 673 674 void MachineConstPropagator::visitNonBranch(const MachineInstr &MI) { 675 LLVM_DEBUG(dbgs() << "Visiting MI(" << printMBBReference(*MI.getParent()) 676 << "): " << MI); 677 CellMap Outputs; 678 bool Eval = MCE.evaluate(MI, Cells, Outputs); 679 LLVM_DEBUG({ 680 if (Eval) { 681 dbgs() << " outputs:"; 682 for (auto &I : Outputs) 683 dbgs() << ' ' << I.second; 684 dbgs() << '\n'; 685 } 686 }); 687 688 // Update outputs. If the value was not computed, set all the 689 // def cells to bottom. 690 for (const MachineOperand &MO : MI.operands()) { 691 if (!MO.isReg() || !MO.isDef()) 692 continue; 693 Register DefR(MO); 694 // Only track virtual registers. 695 if (!TargetRegisterInfo::isVirtualRegister(DefR.Reg)) 696 continue; 697 bool Changed = false; 698 // If the evaluation failed, set cells for all output registers to bottom. 699 if (!Eval) { 700 const LatticeCell &T = Cells.get(DefR.Reg); 701 Changed = !T.isBottom(); 702 Cells.update(DefR.Reg, Bottom); 703 } else { 704 // Find the corresponding cell in the computed outputs. 705 // If it's not there, go on to the next def. 706 if (!Outputs.has(DefR.Reg)) 707 continue; 708 LatticeCell RC = Cells.get(DefR.Reg); 709 Changed = RC.meet(Outputs.get(DefR.Reg)); 710 Cells.update(DefR.Reg, RC); 711 } 712 if (Changed) 713 visitUsesOf(DefR.Reg); 714 } 715 } 716 717 // Starting at a given branch, visit remaining branches in the block. 718 // Traverse over the subsequent branches for as long as the preceding one 719 // can fall through. Add all the possible targets to the flow work queue, 720 // including the potential fall-through to the layout-successor block. 721 void MachineConstPropagator::visitBranchesFrom(const MachineInstr &BrI) { 722 const MachineBasicBlock &B = *BrI.getParent(); 723 unsigned MBN = B.getNumber(); 724 MachineBasicBlock::const_iterator It = BrI.getIterator(); 725 MachineBasicBlock::const_iterator End = B.end(); 726 727 SetVector<const MachineBasicBlock*> Targets; 728 bool EvalOk = true, FallsThru = true; 729 while (It != End) { 730 const MachineInstr &MI = *It; 731 InstrExec.insert(&MI); 732 LLVM_DEBUG(dbgs() << "Visiting " << (EvalOk ? "BR" : "br") << "(" 733 << printMBBReference(B) << "): " << MI); 734 // Do not evaluate subsequent branches if the evaluation of any of the 735 // previous branches failed. Keep iterating over the branches only 736 // to mark them as executable. 737 EvalOk = EvalOk && MCE.evaluate(MI, Cells, Targets, FallsThru); 738 if (!EvalOk) 739 FallsThru = true; 740 if (!FallsThru) 741 break; 742 ++It; 743 } 744 745 if (EvalOk) { 746 // Need to add all CFG successors that lead to EH landing pads. 747 // There won't be explicit branches to these blocks, but they must 748 // be processed. 749 for (const MachineBasicBlock *SB : B.successors()) { 750 if (SB->isEHPad()) 751 Targets.insert(SB); 752 } 753 if (FallsThru) { 754 const MachineFunction &MF = *B.getParent(); 755 MachineFunction::const_iterator BI = B.getIterator(); 756 MachineFunction::const_iterator Next = std::next(BI); 757 if (Next != MF.end()) 758 Targets.insert(&*Next); 759 } 760 } else { 761 // If the evaluation of the branches failed, make "Targets" to be the 762 // set of all successors of the block from the CFG. 763 // If the evaluation succeeded for all visited branches, then if the 764 // last one set "FallsThru", then add an edge to the layout successor 765 // to the targets. 766 Targets.clear(); 767 LLVM_DEBUG(dbgs() << " failed to evaluate a branch...adding all CFG " 768 "successors\n"); 769 for (const MachineBasicBlock *SB : B.successors()) 770 Targets.insert(SB); 771 } 772 773 for (const MachineBasicBlock *TB : Targets) { 774 unsigned TBN = TB->getNumber(); 775 LLVM_DEBUG(dbgs() << " pushing edge " << printMBBReference(B) << " -> " 776 << printMBBReference(*TB) << "\n"); 777 FlowQ.push(CFGEdge(MBN, TBN)); 778 } 779 } 780 781 void MachineConstPropagator::visitUsesOf(unsigned Reg) { 782 LLVM_DEBUG(dbgs() << "Visiting uses of " << printReg(Reg, &MCE.TRI) 783 << Cells.get(Reg) << '\n'); 784 for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) { 785 // Do not process non-executable instructions. They can become exceutable 786 // later (via a flow-edge in the work queue). In such case, the instruc- 787 // tion will be visited at that time. 788 if (!InstrExec.count(&MI)) 789 continue; 790 if (MI.isPHI()) 791 visitPHI(MI); 792 else if (!MI.isBranch()) 793 visitNonBranch(MI); 794 else 795 visitBranchesFrom(MI); 796 } 797 } 798 799 bool MachineConstPropagator::computeBlockSuccessors(const MachineBasicBlock *MB, 800 SetVector<const MachineBasicBlock*> &Targets) { 801 MachineBasicBlock::const_iterator FirstBr = MB->end(); 802 for (const MachineInstr &MI : *MB) { 803 if (MI.isDebugInstr()) 804 continue; 805 if (MI.isBranch()) { 806 FirstBr = MI.getIterator(); 807 break; 808 } 809 } 810 811 Targets.clear(); 812 MachineBasicBlock::const_iterator End = MB->end(); 813 814 bool DoNext = true; 815 for (MachineBasicBlock::const_iterator I = FirstBr; I != End; ++I) { 816 const MachineInstr &MI = *I; 817 // Can there be debug instructions between branches? 818 if (MI.isDebugInstr()) 819 continue; 820 if (!InstrExec.count(&MI)) 821 continue; 822 bool Eval = MCE.evaluate(MI, Cells, Targets, DoNext); 823 if (!Eval) 824 return false; 825 if (!DoNext) 826 break; 827 } 828 // If the last branch could fall-through, add block's layout successor. 829 if (DoNext) { 830 MachineFunction::const_iterator BI = MB->getIterator(); 831 MachineFunction::const_iterator NextI = std::next(BI); 832 if (NextI != MB->getParent()->end()) 833 Targets.insert(&*NextI); 834 } 835 836 // Add all the EH landing pads. 837 for (const MachineBasicBlock *SB : MB->successors()) 838 if (SB->isEHPad()) 839 Targets.insert(SB); 840 841 return true; 842 } 843 844 void MachineConstPropagator::removeCFGEdge(MachineBasicBlock *From, 845 MachineBasicBlock *To) { 846 // First, remove the CFG successor/predecessor information. 847 From->removeSuccessor(To); 848 // Remove all corresponding PHI operands in the To block. 849 for (auto I = To->begin(), E = To->getFirstNonPHI(); I != E; ++I) { 850 MachineInstr *PN = &*I; 851 // reg0 = PHI reg1, bb2, reg3, bb4, ... 852 int N = PN->getNumOperands()-2; 853 while (N > 0) { 854 if (PN->getOperand(N+1).getMBB() == From) { 855 PN->RemoveOperand(N+1); 856 PN->RemoveOperand(N); 857 } 858 N -= 2; 859 } 860 } 861 } 862 863 void MachineConstPropagator::propagate(MachineFunction &MF) { 864 MachineBasicBlock *Entry = GraphTraits<MachineFunction*>::getEntryNode(&MF); 865 unsigned EntryNum = Entry->getNumber(); 866 867 // Start with a fake edge, just to process the entry node. 868 FlowQ.push(CFGEdge(EntryNum, EntryNum)); 869 870 while (!FlowQ.empty()) { 871 CFGEdge Edge = FlowQ.front(); 872 FlowQ.pop(); 873 874 LLVM_DEBUG( 875 dbgs() << "Picked edge " 876 << printMBBReference(*MF.getBlockNumbered(Edge.first)) << "->" 877 << printMBBReference(*MF.getBlockNumbered(Edge.second)) << '\n'); 878 if (Edge.first != EntryNum) 879 if (EdgeExec.count(Edge)) 880 continue; 881 EdgeExec.insert(Edge); 882 MachineBasicBlock *SB = MF.getBlockNumbered(Edge.second); 883 884 // Process the block in three stages: 885 // - visit all PHI nodes, 886 // - visit all non-branch instructions, 887 // - visit block branches. 888 MachineBasicBlock::const_iterator It = SB->begin(), End = SB->end(); 889 890 // Visit PHI nodes in the successor block. 891 while (It != End && It->isPHI()) { 892 InstrExec.insert(&*It); 893 visitPHI(*It); 894 ++It; 895 } 896 897 // If the successor block just became executable, visit all instructions. 898 // To see if this is the first time we're visiting it, check the first 899 // non-debug instruction to see if it is executable. 900 while (It != End && It->isDebugInstr()) 901 ++It; 902 assert(It == End || !It->isPHI()); 903 // If this block has been visited, go on to the next one. 904 if (It != End && InstrExec.count(&*It)) 905 continue; 906 // For now, scan all non-branch instructions. Branches require different 907 // processing. 908 while (It != End && !It->isBranch()) { 909 if (!It->isDebugInstr()) { 910 InstrExec.insert(&*It); 911 visitNonBranch(*It); 912 } 913 ++It; 914 } 915 916 // Time to process the end of the block. This is different from 917 // processing regular (non-branch) instructions, because there can 918 // be multiple branches in a block, and they can cause the block to 919 // terminate early. 920 if (It != End) { 921 visitBranchesFrom(*It); 922 } else { 923 // If the block didn't have a branch, add all successor edges to the 924 // work queue. (There should really be only one successor in such case.) 925 unsigned SBN = SB->getNumber(); 926 for (const MachineBasicBlock *SSB : SB->successors()) 927 FlowQ.push(CFGEdge(SBN, SSB->getNumber())); 928 } 929 } // while (FlowQ) 930 931 LLVM_DEBUG({ 932 dbgs() << "Cells after propagation:\n"; 933 Cells.print(dbgs(), MCE.TRI); 934 dbgs() << "Dead CFG edges:\n"; 935 for (const MachineBasicBlock &B : MF) { 936 unsigned BN = B.getNumber(); 937 for (const MachineBasicBlock *SB : B.successors()) { 938 unsigned SN = SB->getNumber(); 939 if (!EdgeExec.count(CFGEdge(BN, SN))) 940 dbgs() << " " << printMBBReference(B) << " -> " 941 << printMBBReference(*SB) << '\n'; 942 } 943 } 944 }); 945 } 946 947 bool MachineConstPropagator::rewrite(MachineFunction &MF) { 948 bool Changed = false; 949 // Rewrite all instructions based on the collected cell information. 950 // 951 // Traverse the instructions in a post-order, so that rewriting an 952 // instruction can make changes "downstream" in terms of control-flow 953 // without affecting the rewriting process. (We should not change 954 // instructions that have not yet been visited by the rewriter.) 955 // The reason for this is that the rewriter can introduce new vregs, 956 // and replace uses of old vregs (which had corresponding cells 957 // computed during propagation) with these new vregs (which at this 958 // point would not have any cells, and would appear to be "top"). 959 // If an attempt was made to evaluate an instruction with a fresh 960 // "top" vreg, it would cause an error (abend) in the evaluator. 961 962 // Collect the post-order-traversal block ordering. The subsequent 963 // traversal/rewrite will update block successors, so it's safer 964 // if the visiting order it computed ahead of time. 965 std::vector<MachineBasicBlock*> POT; 966 for (MachineBasicBlock *B : post_order(&MF)) 967 if (!B->empty()) 968 POT.push_back(B); 969 970 for (MachineBasicBlock *B : POT) { 971 // Walk the block backwards (which usually begin with the branches). 972 // If any branch is rewritten, we may need to update the successor 973 // information for this block. Unless the block's successors can be 974 // precisely determined (which may not be the case for indirect 975 // branches), we cannot modify any branch. 976 977 // Compute the successor information. 978 SetVector<const MachineBasicBlock*> Targets; 979 bool HaveTargets = computeBlockSuccessors(B, Targets); 980 // Rewrite the executable instructions. Skip branches if we don't 981 // have block successor information. 982 for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) { 983 MachineInstr &MI = *I; 984 if (InstrExec.count(&MI)) { 985 if (MI.isBranch() && !HaveTargets) 986 continue; 987 Changed |= MCE.rewrite(MI, Cells); 988 } 989 } 990 // The rewriting could rewrite PHI nodes to non-PHI nodes, causing 991 // regular instructions to appear in between PHI nodes. Bring all 992 // the PHI nodes to the beginning of the block. 993 for (auto I = B->begin(), E = B->end(); I != E; ++I) { 994 if (I->isPHI()) 995 continue; 996 // I is not PHI. Find the next PHI node P. 997 auto P = I; 998 while (++P != E) 999 if (P->isPHI()) 1000 break; 1001 // Not found. 1002 if (P == E) 1003 break; 1004 // Splice P right before I. 1005 B->splice(I, B, P); 1006 // Reset I to point at the just spliced PHI node. 1007 --I; 1008 } 1009 // Update the block successor information: remove unnecessary successors. 1010 if (HaveTargets) { 1011 SmallVector<MachineBasicBlock*,2> ToRemove; 1012 for (MachineBasicBlock *SB : B->successors()) { 1013 if (!Targets.count(SB)) 1014 ToRemove.push_back(const_cast<MachineBasicBlock*>(SB)); 1015 Targets.remove(SB); 1016 } 1017 for (unsigned i = 0, n = ToRemove.size(); i < n; ++i) 1018 removeCFGEdge(B, ToRemove[i]); 1019 // If there are any blocks left in the computed targets, it means that 1020 // we think that the block could go somewhere, but the CFG does not. 1021 // This could legitimately happen in blocks that have non-returning 1022 // calls---we would think that the execution can continue, but the 1023 // CFG will not have a successor edge. 1024 } 1025 } 1026 // Need to do some final post-processing. 1027 // If a branch was not executable, it will not get rewritten, but should 1028 // be removed (or replaced with something equivalent to a A2_nop). We can't 1029 // erase instructions during rewriting, so this needs to be delayed until 1030 // now. 1031 for (MachineBasicBlock &B : MF) { 1032 MachineBasicBlock::iterator I = B.begin(), E = B.end(); 1033 while (I != E) { 1034 auto Next = std::next(I); 1035 if (I->isBranch() && !InstrExec.count(&*I)) 1036 B.erase(I); 1037 I = Next; 1038 } 1039 } 1040 return Changed; 1041 } 1042 1043 // This is the constant propagation algorithm as described by Wegman-Zadeck. 1044 // Most of the terminology comes from there. 1045 bool MachineConstPropagator::run(MachineFunction &MF) { 1046 LLVM_DEBUG(MF.print(dbgs() << "Starting MachineConstPropagator\n", nullptr)); 1047 1048 MRI = &MF.getRegInfo(); 1049 1050 Cells.clear(); 1051 EdgeExec.clear(); 1052 InstrExec.clear(); 1053 assert(FlowQ.empty()); 1054 1055 propagate(MF); 1056 bool Changed = rewrite(MF); 1057 1058 LLVM_DEBUG({ 1059 dbgs() << "End of MachineConstPropagator (Changed=" << Changed << ")\n"; 1060 if (Changed) 1061 MF.print(dbgs(), nullptr); 1062 }); 1063 return Changed; 1064 } 1065 1066 // -------------------------------------------------------------------- 1067 // Machine const evaluator. 1068 1069 bool MachineConstEvaluator::getCell(const Register &R, const CellMap &Inputs, 1070 LatticeCell &RC) { 1071 if (!TargetRegisterInfo::isVirtualRegister(R.Reg)) 1072 return false; 1073 const LatticeCell &L = Inputs.get(R.Reg); 1074 if (!R.SubReg) { 1075 RC = L; 1076 return !RC.isBottom(); 1077 } 1078 bool Eval = evaluate(R, L, RC); 1079 return Eval && !RC.isBottom(); 1080 } 1081 1082 bool MachineConstEvaluator::constToInt(const Constant *C, 1083 APInt &Val) const { 1084 const ConstantInt *CI = dyn_cast<ConstantInt>(C); 1085 if (!CI) 1086 return false; 1087 Val = CI->getValue(); 1088 return true; 1089 } 1090 1091 const ConstantInt *MachineConstEvaluator::intToConst(const APInt &Val) const { 1092 return ConstantInt::get(CX, Val); 1093 } 1094 1095 bool MachineConstEvaluator::evaluateCMPrr(uint32_t Cmp, const Register &R1, 1096 const Register &R2, const CellMap &Inputs, bool &Result) { 1097 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg)); 1098 LatticeCell LS1, LS2; 1099 if (!getCell(R1, Inputs, LS1) || !getCell(R2, Inputs, LS2)) 1100 return false; 1101 1102 bool IsProp1 = LS1.isProperty(); 1103 bool IsProp2 = LS2.isProperty(); 1104 if (IsProp1) { 1105 uint32_t Prop1 = LS1.properties(); 1106 if (IsProp2) 1107 return evaluateCMPpp(Cmp, Prop1, LS2.properties(), Result); 1108 uint32_t NegCmp = Comparison::negate(Cmp); 1109 return evaluateCMPrp(NegCmp, R2, Prop1, Inputs, Result); 1110 } 1111 if (IsProp2) { 1112 uint32_t Prop2 = LS2.properties(); 1113 return evaluateCMPrp(Cmp, R1, Prop2, Inputs, Result); 1114 } 1115 1116 APInt A; 1117 bool IsTrue = true, IsFalse = true; 1118 for (unsigned i = 0; i < LS2.size(); ++i) { 1119 bool Res; 1120 bool Computed = constToInt(LS2.Values[i], A) && 1121 evaluateCMPri(Cmp, R1, A, Inputs, Res); 1122 if (!Computed) 1123 return false; 1124 IsTrue &= Res; 1125 IsFalse &= !Res; 1126 } 1127 assert(!IsTrue || !IsFalse); 1128 // The actual logical value of the comparison is same as IsTrue. 1129 Result = IsTrue; 1130 // Return true if the result was proven to be true or proven to be false. 1131 return IsTrue || IsFalse; 1132 } 1133 1134 bool MachineConstEvaluator::evaluateCMPri(uint32_t Cmp, const Register &R1, 1135 const APInt &A2, const CellMap &Inputs, bool &Result) { 1136 assert(Inputs.has(R1.Reg)); 1137 LatticeCell LS; 1138 if (!getCell(R1, Inputs, LS)) 1139 return false; 1140 if (LS.isProperty()) 1141 return evaluateCMPpi(Cmp, LS.properties(), A2, Result); 1142 1143 APInt A; 1144 bool IsTrue = true, IsFalse = true; 1145 for (unsigned i = 0; i < LS.size(); ++i) { 1146 bool Res; 1147 bool Computed = constToInt(LS.Values[i], A) && 1148 evaluateCMPii(Cmp, A, A2, Res); 1149 if (!Computed) 1150 return false; 1151 IsTrue &= Res; 1152 IsFalse &= !Res; 1153 } 1154 assert(!IsTrue || !IsFalse); 1155 // The actual logical value of the comparison is same as IsTrue. 1156 Result = IsTrue; 1157 // Return true if the result was proven to be true or proven to be false. 1158 return IsTrue || IsFalse; 1159 } 1160 1161 bool MachineConstEvaluator::evaluateCMPrp(uint32_t Cmp, const Register &R1, 1162 uint64_t Props2, const CellMap &Inputs, bool &Result) { 1163 assert(Inputs.has(R1.Reg)); 1164 LatticeCell LS; 1165 if (!getCell(R1, Inputs, LS)) 1166 return false; 1167 if (LS.isProperty()) 1168 return evaluateCMPpp(Cmp, LS.properties(), Props2, Result); 1169 1170 APInt A; 1171 uint32_t NegCmp = Comparison::negate(Cmp); 1172 bool IsTrue = true, IsFalse = true; 1173 for (unsigned i = 0; i < LS.size(); ++i) { 1174 bool Res; 1175 bool Computed = constToInt(LS.Values[i], A) && 1176 evaluateCMPpi(NegCmp, Props2, A, Res); 1177 if (!Computed) 1178 return false; 1179 IsTrue &= Res; 1180 IsFalse &= !Res; 1181 } 1182 assert(!IsTrue || !IsFalse); 1183 Result = IsTrue; 1184 return IsTrue || IsFalse; 1185 } 1186 1187 bool MachineConstEvaluator::evaluateCMPii(uint32_t Cmp, const APInt &A1, 1188 const APInt &A2, bool &Result) { 1189 // NE is a special kind of comparison (not composed of smaller properties). 1190 if (Cmp == Comparison::NE) { 1191 Result = !APInt::isSameValue(A1, A2); 1192 return true; 1193 } 1194 if (Cmp == Comparison::EQ) { 1195 Result = APInt::isSameValue(A1, A2); 1196 return true; 1197 } 1198 if (Cmp & Comparison::EQ) { 1199 if (APInt::isSameValue(A1, A2)) 1200 return (Result = true); 1201 } 1202 assert((Cmp & (Comparison::L | Comparison::G)) && "Malformed comparison"); 1203 Result = false; 1204 1205 unsigned W1 = A1.getBitWidth(); 1206 unsigned W2 = A2.getBitWidth(); 1207 unsigned MaxW = (W1 >= W2) ? W1 : W2; 1208 if (Cmp & Comparison::U) { 1209 const APInt Zx1 = A1.zextOrSelf(MaxW); 1210 const APInt Zx2 = A2.zextOrSelf(MaxW); 1211 if (Cmp & Comparison::L) 1212 Result = Zx1.ult(Zx2); 1213 else if (Cmp & Comparison::G) 1214 Result = Zx2.ult(Zx1); 1215 return true; 1216 } 1217 1218 // Signed comparison. 1219 const APInt Sx1 = A1.sextOrSelf(MaxW); 1220 const APInt Sx2 = A2.sextOrSelf(MaxW); 1221 if (Cmp & Comparison::L) 1222 Result = Sx1.slt(Sx2); 1223 else if (Cmp & Comparison::G) 1224 Result = Sx2.slt(Sx1); 1225 return true; 1226 } 1227 1228 bool MachineConstEvaluator::evaluateCMPpi(uint32_t Cmp, uint32_t Props, 1229 const APInt &A2, bool &Result) { 1230 if (Props == ConstantProperties::Unknown) 1231 return false; 1232 1233 // Should never see NaN here, but check for it for completeness. 1234 if (Props & ConstantProperties::NaN) 1235 return false; 1236 // Infinity could theoretically be compared to a number, but the 1237 // presence of infinity here would be very suspicious. If we don't 1238 // know for sure that the number is finite, bail out. 1239 if (!(Props & ConstantProperties::Finite)) 1240 return false; 1241 1242 // Let X be a number that has properties Props. 1243 1244 if (Cmp & Comparison::U) { 1245 // In case of unsigned comparisons, we can only compare against 0. 1246 if (A2 == 0) { 1247 // Any x!=0 will be considered >0 in an unsigned comparison. 1248 if (Props & ConstantProperties::Zero) 1249 Result = (Cmp & Comparison::EQ); 1250 else if (Props & ConstantProperties::NonZero) 1251 Result = (Cmp & Comparison::G) || (Cmp == Comparison::NE); 1252 else 1253 return false; 1254 return true; 1255 } 1256 // A2 is not zero. The only handled case is if X = 0. 1257 if (Props & ConstantProperties::Zero) { 1258 Result = (Cmp & Comparison::L) || (Cmp == Comparison::NE); 1259 return true; 1260 } 1261 return false; 1262 } 1263 1264 // Signed comparisons are different. 1265 if (Props & ConstantProperties::Zero) { 1266 if (A2 == 0) 1267 Result = (Cmp & Comparison::EQ); 1268 else 1269 Result = (Cmp == Comparison::NE) || 1270 ((Cmp & Comparison::L) && !A2.isNegative()) || 1271 ((Cmp & Comparison::G) && A2.isNegative()); 1272 return true; 1273 } 1274 if (Props & ConstantProperties::PosOrZero) { 1275 // X >= 0 and !(A2 < 0) => cannot compare 1276 if (!A2.isNegative()) 1277 return false; 1278 // X >= 0 and A2 < 0 1279 Result = (Cmp & Comparison::G) || (Cmp == Comparison::NE); 1280 return true; 1281 } 1282 if (Props & ConstantProperties::NegOrZero) { 1283 // X <= 0 and Src1 < 0 => cannot compare 1284 if (A2 == 0 || A2.isNegative()) 1285 return false; 1286 // X <= 0 and A2 > 0 1287 Result = (Cmp & Comparison::L) || (Cmp == Comparison::NE); 1288 return true; 1289 } 1290 1291 return false; 1292 } 1293 1294 bool MachineConstEvaluator::evaluateCMPpp(uint32_t Cmp, uint32_t Props1, 1295 uint32_t Props2, bool &Result) { 1296 using P = ConstantProperties; 1297 1298 if ((Props1 & P::NaN) && (Props2 & P::NaN)) 1299 return false; 1300 if (!(Props1 & P::Finite) || !(Props2 & P::Finite)) 1301 return false; 1302 1303 bool Zero1 = (Props1 & P::Zero), Zero2 = (Props2 & P::Zero); 1304 bool NonZero1 = (Props1 & P::NonZero), NonZero2 = (Props2 & P::NonZero); 1305 if (Zero1 && Zero2) { 1306 Result = (Cmp & Comparison::EQ); 1307 return true; 1308 } 1309 if (Cmp == Comparison::NE) { 1310 if ((Zero1 && NonZero2) || (NonZero1 && Zero2)) 1311 return (Result = true); 1312 return false; 1313 } 1314 1315 if (Cmp & Comparison::U) { 1316 // In unsigned comparisons, we can only compare against a known zero, 1317 // or a known non-zero. 1318 if (Zero1 && NonZero2) { 1319 Result = (Cmp & Comparison::L); 1320 return true; 1321 } 1322 if (NonZero1 && Zero2) { 1323 Result = (Cmp & Comparison::G); 1324 return true; 1325 } 1326 return false; 1327 } 1328 1329 // Signed comparison. The comparison is not NE. 1330 bool Poz1 = (Props1 & P::PosOrZero), Poz2 = (Props2 & P::PosOrZero); 1331 bool Nez1 = (Props1 & P::NegOrZero), Nez2 = (Props2 & P::NegOrZero); 1332 if (Nez1 && Poz2) { 1333 if (NonZero1 || NonZero2) { 1334 Result = (Cmp & Comparison::L); 1335 return true; 1336 } 1337 // Either (or both) could be zero. Can only say that X <= Y. 1338 if ((Cmp & Comparison::EQ) && (Cmp & Comparison::L)) 1339 return (Result = true); 1340 } 1341 if (Poz1 && Nez2) { 1342 if (NonZero1 || NonZero2) { 1343 Result = (Cmp & Comparison::G); 1344 return true; 1345 } 1346 // Either (or both) could be zero. Can only say that X >= Y. 1347 if ((Cmp & Comparison::EQ) && (Cmp & Comparison::G)) 1348 return (Result = true); 1349 } 1350 1351 return false; 1352 } 1353 1354 bool MachineConstEvaluator::evaluateCOPY(const Register &R1, 1355 const CellMap &Inputs, LatticeCell &Result) { 1356 return getCell(R1, Inputs, Result); 1357 } 1358 1359 bool MachineConstEvaluator::evaluateANDrr(const Register &R1, 1360 const Register &R2, const CellMap &Inputs, LatticeCell &Result) { 1361 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg)); 1362 const LatticeCell &L1 = Inputs.get(R2.Reg); 1363 const LatticeCell &L2 = Inputs.get(R2.Reg); 1364 // If both sources are bottom, exit. Otherwise try to evaluate ANDri 1365 // with the non-bottom argument passed as the immediate. This is to 1366 // catch cases of ANDing with 0. 1367 if (L2.isBottom()) { 1368 if (L1.isBottom()) 1369 return false; 1370 return evaluateANDrr(R2, R1, Inputs, Result); 1371 } 1372 LatticeCell LS2; 1373 if (!evaluate(R2, L2, LS2)) 1374 return false; 1375 if (LS2.isBottom() || LS2.isProperty()) 1376 return false; 1377 1378 APInt A; 1379 for (unsigned i = 0; i < LS2.size(); ++i) { 1380 LatticeCell RC; 1381 bool Eval = constToInt(LS2.Values[i], A) && 1382 evaluateANDri(R1, A, Inputs, RC); 1383 if (!Eval) 1384 return false; 1385 Result.meet(RC); 1386 } 1387 return !Result.isBottom(); 1388 } 1389 1390 bool MachineConstEvaluator::evaluateANDri(const Register &R1, 1391 const APInt &A2, const CellMap &Inputs, LatticeCell &Result) { 1392 assert(Inputs.has(R1.Reg)); 1393 if (A2 == -1) 1394 return getCell(R1, Inputs, Result); 1395 if (A2 == 0) { 1396 LatticeCell RC; 1397 RC.add(intToConst(A2)); 1398 // Overwrite Result. 1399 Result = RC; 1400 return true; 1401 } 1402 LatticeCell LS1; 1403 if (!getCell(R1, Inputs, LS1)) 1404 return false; 1405 if (LS1.isBottom() || LS1.isProperty()) 1406 return false; 1407 1408 APInt A, ResA; 1409 for (unsigned i = 0; i < LS1.size(); ++i) { 1410 bool Eval = constToInt(LS1.Values[i], A) && 1411 evaluateANDii(A, A2, ResA); 1412 if (!Eval) 1413 return false; 1414 const Constant *C = intToConst(ResA); 1415 Result.add(C); 1416 } 1417 return !Result.isBottom(); 1418 } 1419 1420 bool MachineConstEvaluator::evaluateANDii(const APInt &A1, 1421 const APInt &A2, APInt &Result) { 1422 Result = A1 & A2; 1423 return true; 1424 } 1425 1426 bool MachineConstEvaluator::evaluateORrr(const Register &R1, 1427 const Register &R2, const CellMap &Inputs, LatticeCell &Result) { 1428 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg)); 1429 const LatticeCell &L1 = Inputs.get(R2.Reg); 1430 const LatticeCell &L2 = Inputs.get(R2.Reg); 1431 // If both sources are bottom, exit. Otherwise try to evaluate ORri 1432 // with the non-bottom argument passed as the immediate. This is to 1433 // catch cases of ORing with -1. 1434 if (L2.isBottom()) { 1435 if (L1.isBottom()) 1436 return false; 1437 return evaluateORrr(R2, R1, Inputs, Result); 1438 } 1439 LatticeCell LS2; 1440 if (!evaluate(R2, L2, LS2)) 1441 return false; 1442 if (LS2.isBottom() || LS2.isProperty()) 1443 return false; 1444 1445 APInt A; 1446 for (unsigned i = 0; i < LS2.size(); ++i) { 1447 LatticeCell RC; 1448 bool Eval = constToInt(LS2.Values[i], A) && 1449 evaluateORri(R1, A, Inputs, RC); 1450 if (!Eval) 1451 return false; 1452 Result.meet(RC); 1453 } 1454 return !Result.isBottom(); 1455 } 1456 1457 bool MachineConstEvaluator::evaluateORri(const Register &R1, 1458 const APInt &A2, const CellMap &Inputs, LatticeCell &Result) { 1459 assert(Inputs.has(R1.Reg)); 1460 if (A2 == 0) 1461 return getCell(R1, Inputs, Result); 1462 if (A2 == -1) { 1463 LatticeCell RC; 1464 RC.add(intToConst(A2)); 1465 // Overwrite Result. 1466 Result = RC; 1467 return true; 1468 } 1469 LatticeCell LS1; 1470 if (!getCell(R1, Inputs, LS1)) 1471 return false; 1472 if (LS1.isBottom() || LS1.isProperty()) 1473 return false; 1474 1475 APInt A, ResA; 1476 for (unsigned i = 0; i < LS1.size(); ++i) { 1477 bool Eval = constToInt(LS1.Values[i], A) && 1478 evaluateORii(A, A2, ResA); 1479 if (!Eval) 1480 return false; 1481 const Constant *C = intToConst(ResA); 1482 Result.add(C); 1483 } 1484 return !Result.isBottom(); 1485 } 1486 1487 bool MachineConstEvaluator::evaluateORii(const APInt &A1, 1488 const APInt &A2, APInt &Result) { 1489 Result = A1 | A2; 1490 return true; 1491 } 1492 1493 bool MachineConstEvaluator::evaluateXORrr(const Register &R1, 1494 const Register &R2, const CellMap &Inputs, LatticeCell &Result) { 1495 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg)); 1496 LatticeCell LS1, LS2; 1497 if (!getCell(R1, Inputs, LS1) || !getCell(R2, Inputs, LS2)) 1498 return false; 1499 if (LS1.isProperty()) { 1500 if (LS1.properties() & ConstantProperties::Zero) 1501 return !(Result = LS2).isBottom(); 1502 return false; 1503 } 1504 if (LS2.isProperty()) { 1505 if (LS2.properties() & ConstantProperties::Zero) 1506 return !(Result = LS1).isBottom(); 1507 return false; 1508 } 1509 1510 APInt A; 1511 for (unsigned i = 0; i < LS2.size(); ++i) { 1512 LatticeCell RC; 1513 bool Eval = constToInt(LS2.Values[i], A) && 1514 evaluateXORri(R1, A, Inputs, RC); 1515 if (!Eval) 1516 return false; 1517 Result.meet(RC); 1518 } 1519 return !Result.isBottom(); 1520 } 1521 1522 bool MachineConstEvaluator::evaluateXORri(const Register &R1, 1523 const APInt &A2, const CellMap &Inputs, LatticeCell &Result) { 1524 assert(Inputs.has(R1.Reg)); 1525 LatticeCell LS1; 1526 if (!getCell(R1, Inputs, LS1)) 1527 return false; 1528 if (LS1.isProperty()) { 1529 if (LS1.properties() & ConstantProperties::Zero) { 1530 const Constant *C = intToConst(A2); 1531 Result.add(C); 1532 return !Result.isBottom(); 1533 } 1534 return false; 1535 } 1536 1537 APInt A, XA; 1538 for (unsigned i = 0; i < LS1.size(); ++i) { 1539 bool Eval = constToInt(LS1.Values[i], A) && 1540 evaluateXORii(A, A2, XA); 1541 if (!Eval) 1542 return false; 1543 const Constant *C = intToConst(XA); 1544 Result.add(C); 1545 } 1546 return !Result.isBottom(); 1547 } 1548 1549 bool MachineConstEvaluator::evaluateXORii(const APInt &A1, 1550 const APInt &A2, APInt &Result) { 1551 Result = A1 ^ A2; 1552 return true; 1553 } 1554 1555 bool MachineConstEvaluator::evaluateZEXTr(const Register &R1, unsigned Width, 1556 unsigned Bits, const CellMap &Inputs, LatticeCell &Result) { 1557 assert(Inputs.has(R1.Reg)); 1558 LatticeCell LS1; 1559 if (!getCell(R1, Inputs, LS1)) 1560 return false; 1561 if (LS1.isProperty()) 1562 return false; 1563 1564 APInt A, XA; 1565 for (unsigned i = 0; i < LS1.size(); ++i) { 1566 bool Eval = constToInt(LS1.Values[i], A) && 1567 evaluateZEXTi(A, Width, Bits, XA); 1568 if (!Eval) 1569 return false; 1570 const Constant *C = intToConst(XA); 1571 Result.add(C); 1572 } 1573 return true; 1574 } 1575 1576 bool MachineConstEvaluator::evaluateZEXTi(const APInt &A1, unsigned Width, 1577 unsigned Bits, APInt &Result) { 1578 unsigned BW = A1.getBitWidth(); 1579 (void)BW; 1580 assert(Width >= Bits && BW >= Bits); 1581 APInt Mask = APInt::getLowBitsSet(Width, Bits); 1582 Result = A1.zextOrTrunc(Width) & Mask; 1583 return true; 1584 } 1585 1586 bool MachineConstEvaluator::evaluateSEXTr(const Register &R1, unsigned Width, 1587 unsigned Bits, const CellMap &Inputs, LatticeCell &Result) { 1588 assert(Inputs.has(R1.Reg)); 1589 LatticeCell LS1; 1590 if (!getCell(R1, Inputs, LS1)) 1591 return false; 1592 if (LS1.isBottom() || LS1.isProperty()) 1593 return false; 1594 1595 APInt A, XA; 1596 for (unsigned i = 0; i < LS1.size(); ++i) { 1597 bool Eval = constToInt(LS1.Values[i], A) && 1598 evaluateSEXTi(A, Width, Bits, XA); 1599 if (!Eval) 1600 return false; 1601 const Constant *C = intToConst(XA); 1602 Result.add(C); 1603 } 1604 return true; 1605 } 1606 1607 bool MachineConstEvaluator::evaluateSEXTi(const APInt &A1, unsigned Width, 1608 unsigned Bits, APInt &Result) { 1609 unsigned BW = A1.getBitWidth(); 1610 assert(Width >= Bits && BW >= Bits); 1611 // Special case to make things faster for smaller source widths. 1612 // Sign extension of 0 bits generates 0 as a result. This is consistent 1613 // with what the HW does. 1614 if (Bits == 0) { 1615 Result = APInt(Width, 0); 1616 return true; 1617 } 1618 // In C, shifts by 64 invoke undefined behavior: handle that case in APInt. 1619 if (BW <= 64 && Bits != 0) { 1620 int64_t V = A1.getSExtValue(); 1621 switch (Bits) { 1622 case 8: 1623 V = static_cast<int8_t>(V); 1624 break; 1625 case 16: 1626 V = static_cast<int16_t>(V); 1627 break; 1628 case 32: 1629 V = static_cast<int32_t>(V); 1630 break; 1631 default: 1632 // Shift left to lose all bits except lower "Bits" bits, then shift 1633 // the value back, replicating what was a sign bit after the first 1634 // shift. 1635 V = (V << (64-Bits)) >> (64-Bits); 1636 break; 1637 } 1638 // V is a 64-bit sign-extended value. Convert it to APInt of desired 1639 // width. 1640 Result = APInt(Width, V, true); 1641 return true; 1642 } 1643 // Slow case: the value doesn't fit in int64_t. 1644 if (Bits < BW) 1645 Result = A1.trunc(Bits).sext(Width); 1646 else // Bits == BW 1647 Result = A1.sext(Width); 1648 return true; 1649 } 1650 1651 bool MachineConstEvaluator::evaluateCLBr(const Register &R1, bool Zeros, 1652 bool Ones, const CellMap &Inputs, LatticeCell &Result) { 1653 assert(Inputs.has(R1.Reg)); 1654 LatticeCell LS1; 1655 if (!getCell(R1, Inputs, LS1)) 1656 return false; 1657 if (LS1.isBottom() || LS1.isProperty()) 1658 return false; 1659 1660 APInt A, CA; 1661 for (unsigned i = 0; i < LS1.size(); ++i) { 1662 bool Eval = constToInt(LS1.Values[i], A) && 1663 evaluateCLBi(A, Zeros, Ones, CA); 1664 if (!Eval) 1665 return false; 1666 const Constant *C = intToConst(CA); 1667 Result.add(C); 1668 } 1669 return true; 1670 } 1671 1672 bool MachineConstEvaluator::evaluateCLBi(const APInt &A1, bool Zeros, 1673 bool Ones, APInt &Result) { 1674 unsigned BW = A1.getBitWidth(); 1675 if (!Zeros && !Ones) 1676 return false; 1677 unsigned Count = 0; 1678 if (Zeros && (Count == 0)) 1679 Count = A1.countLeadingZeros(); 1680 if (Ones && (Count == 0)) 1681 Count = A1.countLeadingOnes(); 1682 Result = APInt(BW, static_cast<uint64_t>(Count), false); 1683 return true; 1684 } 1685 1686 bool MachineConstEvaluator::evaluateCTBr(const Register &R1, bool Zeros, 1687 bool Ones, const CellMap &Inputs, LatticeCell &Result) { 1688 assert(Inputs.has(R1.Reg)); 1689 LatticeCell LS1; 1690 if (!getCell(R1, Inputs, LS1)) 1691 return false; 1692 if (LS1.isBottom() || LS1.isProperty()) 1693 return false; 1694 1695 APInt A, CA; 1696 for (unsigned i = 0; i < LS1.size(); ++i) { 1697 bool Eval = constToInt(LS1.Values[i], A) && 1698 evaluateCTBi(A, Zeros, Ones, CA); 1699 if (!Eval) 1700 return false; 1701 const Constant *C = intToConst(CA); 1702 Result.add(C); 1703 } 1704 return true; 1705 } 1706 1707 bool MachineConstEvaluator::evaluateCTBi(const APInt &A1, bool Zeros, 1708 bool Ones, APInt &Result) { 1709 unsigned BW = A1.getBitWidth(); 1710 if (!Zeros && !Ones) 1711 return false; 1712 unsigned Count = 0; 1713 if (Zeros && (Count == 0)) 1714 Count = A1.countTrailingZeros(); 1715 if (Ones && (Count == 0)) 1716 Count = A1.countTrailingOnes(); 1717 Result = APInt(BW, static_cast<uint64_t>(Count), false); 1718 return true; 1719 } 1720 1721 bool MachineConstEvaluator::evaluateEXTRACTr(const Register &R1, 1722 unsigned Width, unsigned Bits, unsigned Offset, bool Signed, 1723 const CellMap &Inputs, LatticeCell &Result) { 1724 assert(Inputs.has(R1.Reg)); 1725 assert(Bits+Offset <= Width); 1726 LatticeCell LS1; 1727 if (!getCell(R1, Inputs, LS1)) 1728 return false; 1729 if (LS1.isBottom()) 1730 return false; 1731 if (LS1.isProperty()) { 1732 uint32_t Ps = LS1.properties(); 1733 if (Ps & ConstantProperties::Zero) { 1734 const Constant *C = intToConst(APInt(Width, 0, false)); 1735 Result.add(C); 1736 return true; 1737 } 1738 return false; 1739 } 1740 1741 APInt A, CA; 1742 for (unsigned i = 0; i < LS1.size(); ++i) { 1743 bool Eval = constToInt(LS1.Values[i], A) && 1744 evaluateEXTRACTi(A, Bits, Offset, Signed, CA); 1745 if (!Eval) 1746 return false; 1747 const Constant *C = intToConst(CA); 1748 Result.add(C); 1749 } 1750 return true; 1751 } 1752 1753 bool MachineConstEvaluator::evaluateEXTRACTi(const APInt &A1, unsigned Bits, 1754 unsigned Offset, bool Signed, APInt &Result) { 1755 unsigned BW = A1.getBitWidth(); 1756 assert(Bits+Offset <= BW); 1757 // Extracting 0 bits generates 0 as a result (as indicated by the HW people). 1758 if (Bits == 0) { 1759 Result = APInt(BW, 0); 1760 return true; 1761 } 1762 if (BW <= 64) { 1763 int64_t V = A1.getZExtValue(); 1764 V <<= (64-Bits-Offset); 1765 if (Signed) 1766 V >>= (64-Bits); 1767 else 1768 V = static_cast<uint64_t>(V) >> (64-Bits); 1769 Result = APInt(BW, V, Signed); 1770 return true; 1771 } 1772 if (Signed) 1773 Result = A1.shl(BW-Bits-Offset).ashr(BW-Bits); 1774 else 1775 Result = A1.shl(BW-Bits-Offset).lshr(BW-Bits); 1776 return true; 1777 } 1778 1779 bool MachineConstEvaluator::evaluateSplatr(const Register &R1, 1780 unsigned Bits, unsigned Count, const CellMap &Inputs, 1781 LatticeCell &Result) { 1782 assert(Inputs.has(R1.Reg)); 1783 LatticeCell LS1; 1784 if (!getCell(R1, Inputs, LS1)) 1785 return false; 1786 if (LS1.isBottom() || LS1.isProperty()) 1787 return false; 1788 1789 APInt A, SA; 1790 for (unsigned i = 0; i < LS1.size(); ++i) { 1791 bool Eval = constToInt(LS1.Values[i], A) && 1792 evaluateSplati(A, Bits, Count, SA); 1793 if (!Eval) 1794 return false; 1795 const Constant *C = intToConst(SA); 1796 Result.add(C); 1797 } 1798 return true; 1799 } 1800 1801 bool MachineConstEvaluator::evaluateSplati(const APInt &A1, unsigned Bits, 1802 unsigned Count, APInt &Result) { 1803 assert(Count > 0); 1804 unsigned BW = A1.getBitWidth(), SW = Count*Bits; 1805 APInt LoBits = (Bits < BW) ? A1.trunc(Bits) : A1.zextOrSelf(Bits); 1806 if (Count > 1) 1807 LoBits = LoBits.zext(SW); 1808 1809 APInt Res(SW, 0, false); 1810 for (unsigned i = 0; i < Count; ++i) { 1811 Res <<= Bits; 1812 Res |= LoBits; 1813 } 1814 Result = Res; 1815 return true; 1816 } 1817 1818 // ---------------------------------------------------------------------- 1819 // Hexagon-specific code. 1820 1821 namespace llvm { 1822 1823 FunctionPass *createHexagonConstPropagationPass(); 1824 void initializeHexagonConstPropagationPass(PassRegistry &Registry); 1825 1826 } // end namespace llvm 1827 1828 namespace { 1829 1830 class HexagonConstEvaluator : public MachineConstEvaluator { 1831 public: 1832 HexagonConstEvaluator(MachineFunction &Fn); 1833 1834 bool evaluate(const MachineInstr &MI, const CellMap &Inputs, 1835 CellMap &Outputs) override; 1836 bool evaluate(const Register &R, const LatticeCell &SrcC, 1837 LatticeCell &Result) override; 1838 bool evaluate(const MachineInstr &BrI, const CellMap &Inputs, 1839 SetVector<const MachineBasicBlock*> &Targets, bool &FallsThru) 1840 override; 1841 bool rewrite(MachineInstr &MI, const CellMap &Inputs) override; 1842 1843 private: 1844 unsigned getRegBitWidth(unsigned Reg) const; 1845 1846 static uint32_t getCmp(unsigned Opc); 1847 static APInt getCmpImm(unsigned Opc, unsigned OpX, 1848 const MachineOperand &MO); 1849 void replaceWithNop(MachineInstr &MI); 1850 1851 bool evaluateHexRSEQ32(Register RL, Register RH, const CellMap &Inputs, 1852 LatticeCell &Result); 1853 bool evaluateHexCompare(const MachineInstr &MI, const CellMap &Inputs, 1854 CellMap &Outputs); 1855 // This is suitable to be called for compare-and-jump instructions. 1856 bool evaluateHexCompare2(uint32_t Cmp, const MachineOperand &Src1, 1857 const MachineOperand &Src2, const CellMap &Inputs, bool &Result); 1858 bool evaluateHexLogical(const MachineInstr &MI, const CellMap &Inputs, 1859 CellMap &Outputs); 1860 bool evaluateHexCondMove(const MachineInstr &MI, const CellMap &Inputs, 1861 CellMap &Outputs); 1862 bool evaluateHexExt(const MachineInstr &MI, const CellMap &Inputs, 1863 CellMap &Outputs); 1864 bool evaluateHexVector1(const MachineInstr &MI, const CellMap &Inputs, 1865 CellMap &Outputs); 1866 bool evaluateHexVector2(const MachineInstr &MI, const CellMap &Inputs, 1867 CellMap &Outputs); 1868 1869 void replaceAllRegUsesWith(unsigned FromReg, unsigned ToReg); 1870 bool rewriteHexBranch(MachineInstr &BrI, const CellMap &Inputs); 1871 bool rewriteHexConstDefs(MachineInstr &MI, const CellMap &Inputs, 1872 bool &AllDefs); 1873 bool rewriteHexConstUses(MachineInstr &MI, const CellMap &Inputs); 1874 1875 MachineRegisterInfo *MRI; 1876 const HexagonInstrInfo &HII; 1877 const HexagonRegisterInfo &HRI; 1878 }; 1879 1880 class HexagonConstPropagation : public MachineFunctionPass { 1881 public: 1882 static char ID; 1883 1884 HexagonConstPropagation() : MachineFunctionPass(ID) {} 1885 1886 StringRef getPassName() const override { 1887 return "Hexagon Constant Propagation"; 1888 } 1889 1890 bool runOnMachineFunction(MachineFunction &MF) override { 1891 const Function &F = MF.getFunction(); 1892 if (skipFunction(F)) 1893 return false; 1894 1895 HexagonConstEvaluator HCE(MF); 1896 return MachineConstPropagator(HCE).run(MF); 1897 } 1898 }; 1899 1900 } // end anonymous namespace 1901 1902 char HexagonConstPropagation::ID = 0; 1903 1904 INITIALIZE_PASS(HexagonConstPropagation, "hexagon-constp", 1905 "Hexagon Constant Propagation", false, false) 1906 1907 HexagonConstEvaluator::HexagonConstEvaluator(MachineFunction &Fn) 1908 : MachineConstEvaluator(Fn), 1909 HII(*Fn.getSubtarget<HexagonSubtarget>().getInstrInfo()), 1910 HRI(*Fn.getSubtarget<HexagonSubtarget>().getRegisterInfo()) { 1911 MRI = &Fn.getRegInfo(); 1912 } 1913 1914 bool HexagonConstEvaluator::evaluate(const MachineInstr &MI, 1915 const CellMap &Inputs, CellMap &Outputs) { 1916 if (MI.isCall()) 1917 return false; 1918 if (MI.getNumOperands() == 0 || !MI.getOperand(0).isReg()) 1919 return false; 1920 const MachineOperand &MD = MI.getOperand(0); 1921 if (!MD.isDef()) 1922 return false; 1923 1924 unsigned Opc = MI.getOpcode(); 1925 Register DefR(MD); 1926 assert(!DefR.SubReg); 1927 if (!TargetRegisterInfo::isVirtualRegister(DefR.Reg)) 1928 return false; 1929 1930 if (MI.isCopy()) { 1931 LatticeCell RC; 1932 Register SrcR(MI.getOperand(1)); 1933 bool Eval = evaluateCOPY(SrcR, Inputs, RC); 1934 if (!Eval) 1935 return false; 1936 Outputs.update(DefR.Reg, RC); 1937 return true; 1938 } 1939 if (MI.isRegSequence()) { 1940 unsigned Sub1 = MI.getOperand(2).getImm(); 1941 unsigned Sub2 = MI.getOperand(4).getImm(); 1942 const TargetRegisterClass &DefRC = *MRI->getRegClass(DefR.Reg); 1943 unsigned SubLo = HRI.getHexagonSubRegIndex(DefRC, Hexagon::ps_sub_lo); 1944 unsigned SubHi = HRI.getHexagonSubRegIndex(DefRC, Hexagon::ps_sub_hi); 1945 if (Sub1 != SubLo && Sub1 != SubHi) 1946 return false; 1947 if (Sub2 != SubLo && Sub2 != SubHi) 1948 return false; 1949 assert(Sub1 != Sub2); 1950 bool LoIs1 = (Sub1 == SubLo); 1951 const MachineOperand &OpLo = LoIs1 ? MI.getOperand(1) : MI.getOperand(3); 1952 const MachineOperand &OpHi = LoIs1 ? MI.getOperand(3) : MI.getOperand(1); 1953 LatticeCell RC; 1954 Register SrcRL(OpLo), SrcRH(OpHi); 1955 bool Eval = evaluateHexRSEQ32(SrcRL, SrcRH, Inputs, RC); 1956 if (!Eval) 1957 return false; 1958 Outputs.update(DefR.Reg, RC); 1959 return true; 1960 } 1961 if (MI.isCompare()) { 1962 bool Eval = evaluateHexCompare(MI, Inputs, Outputs); 1963 return Eval; 1964 } 1965 1966 switch (Opc) { 1967 default: 1968 return false; 1969 case Hexagon::A2_tfrsi: 1970 case Hexagon::A2_tfrpi: 1971 case Hexagon::CONST32: 1972 case Hexagon::CONST64: 1973 { 1974 const MachineOperand &VO = MI.getOperand(1); 1975 // The operand of CONST32 can be a blockaddress, e.g. 1976 // %0 = CONST32 <blockaddress(@eat, %l)> 1977 // Do this check for all instructions for safety. 1978 if (!VO.isImm()) 1979 return false; 1980 int64_t V = MI.getOperand(1).getImm(); 1981 unsigned W = getRegBitWidth(DefR.Reg); 1982 if (W != 32 && W != 64) 1983 return false; 1984 IntegerType *Ty = (W == 32) ? Type::getInt32Ty(CX) 1985 : Type::getInt64Ty(CX); 1986 const ConstantInt *CI = ConstantInt::get(Ty, V, true); 1987 LatticeCell RC = Outputs.get(DefR.Reg); 1988 RC.add(CI); 1989 Outputs.update(DefR.Reg, RC); 1990 break; 1991 } 1992 1993 case Hexagon::PS_true: 1994 case Hexagon::PS_false: 1995 { 1996 LatticeCell RC = Outputs.get(DefR.Reg); 1997 bool NonZero = (Opc == Hexagon::PS_true); 1998 uint32_t P = NonZero ? ConstantProperties::NonZero 1999 : ConstantProperties::Zero; 2000 RC.add(P); 2001 Outputs.update(DefR.Reg, RC); 2002 break; 2003 } 2004 2005 case Hexagon::A2_and: 2006 case Hexagon::A2_andir: 2007 case Hexagon::A2_andp: 2008 case Hexagon::A2_or: 2009 case Hexagon::A2_orir: 2010 case Hexagon::A2_orp: 2011 case Hexagon::A2_xor: 2012 case Hexagon::A2_xorp: 2013 { 2014 bool Eval = evaluateHexLogical(MI, Inputs, Outputs); 2015 if (!Eval) 2016 return false; 2017 break; 2018 } 2019 2020 case Hexagon::A2_combineii: // combine(#s8Ext, #s8) 2021 case Hexagon::A4_combineii: // combine(#s8, #u6Ext) 2022 { 2023 if (!MI.getOperand(1).isImm() || !MI.getOperand(2).isImm()) 2024 return false; 2025 uint64_t Hi = MI.getOperand(1).getImm(); 2026 uint64_t Lo = MI.getOperand(2).getImm(); 2027 uint64_t Res = (Hi << 32) | (Lo & 0xFFFFFFFF); 2028 IntegerType *Ty = Type::getInt64Ty(CX); 2029 const ConstantInt *CI = ConstantInt::get(Ty, Res, false); 2030 LatticeCell RC = Outputs.get(DefR.Reg); 2031 RC.add(CI); 2032 Outputs.update(DefR.Reg, RC); 2033 break; 2034 } 2035 2036 case Hexagon::S2_setbit_i: 2037 { 2038 int64_t B = MI.getOperand(2).getImm(); 2039 assert(B >=0 && B < 32); 2040 APInt A(32, (1ull << B), false); 2041 Register R(MI.getOperand(1)); 2042 LatticeCell RC = Outputs.get(DefR.Reg); 2043 bool Eval = evaluateORri(R, A, Inputs, RC); 2044 if (!Eval) 2045 return false; 2046 Outputs.update(DefR.Reg, RC); 2047 break; 2048 } 2049 2050 case Hexagon::C2_mux: 2051 case Hexagon::C2_muxir: 2052 case Hexagon::C2_muxri: 2053 case Hexagon::C2_muxii: 2054 { 2055 bool Eval = evaluateHexCondMove(MI, Inputs, Outputs); 2056 if (!Eval) 2057 return false; 2058 break; 2059 } 2060 2061 case Hexagon::A2_sxtb: 2062 case Hexagon::A2_sxth: 2063 case Hexagon::A2_sxtw: 2064 case Hexagon::A2_zxtb: 2065 case Hexagon::A2_zxth: 2066 { 2067 bool Eval = evaluateHexExt(MI, Inputs, Outputs); 2068 if (!Eval) 2069 return false; 2070 break; 2071 } 2072 2073 case Hexagon::S2_ct0: 2074 case Hexagon::S2_ct0p: 2075 case Hexagon::S2_ct1: 2076 case Hexagon::S2_ct1p: 2077 { 2078 using namespace Hexagon; 2079 2080 bool Ones = (Opc == S2_ct1) || (Opc == S2_ct1p); 2081 Register R1(MI.getOperand(1)); 2082 assert(Inputs.has(R1.Reg)); 2083 LatticeCell T; 2084 bool Eval = evaluateCTBr(R1, !Ones, Ones, Inputs, T); 2085 if (!Eval) 2086 return false; 2087 // All of these instructions return a 32-bit value. The evaluate 2088 // will generate the same type as the operand, so truncate the 2089 // result if necessary. 2090 APInt C; 2091 LatticeCell RC = Outputs.get(DefR.Reg); 2092 for (unsigned i = 0; i < T.size(); ++i) { 2093 const Constant *CI = T.Values[i]; 2094 if (constToInt(CI, C) && C.getBitWidth() > 32) 2095 CI = intToConst(C.trunc(32)); 2096 RC.add(CI); 2097 } 2098 Outputs.update(DefR.Reg, RC); 2099 break; 2100 } 2101 2102 case Hexagon::S2_cl0: 2103 case Hexagon::S2_cl0p: 2104 case Hexagon::S2_cl1: 2105 case Hexagon::S2_cl1p: 2106 case Hexagon::S2_clb: 2107 case Hexagon::S2_clbp: 2108 { 2109 using namespace Hexagon; 2110 2111 bool OnlyZeros = (Opc == S2_cl0) || (Opc == S2_cl0p); 2112 bool OnlyOnes = (Opc == S2_cl1) || (Opc == S2_cl1p); 2113 Register R1(MI.getOperand(1)); 2114 assert(Inputs.has(R1.Reg)); 2115 LatticeCell T; 2116 bool Eval = evaluateCLBr(R1, !OnlyOnes, !OnlyZeros, Inputs, T); 2117 if (!Eval) 2118 return false; 2119 // All of these instructions return a 32-bit value. The evaluate 2120 // will generate the same type as the operand, so truncate the 2121 // result if necessary. 2122 APInt C; 2123 LatticeCell RC = Outputs.get(DefR.Reg); 2124 for (unsigned i = 0; i < T.size(); ++i) { 2125 const Constant *CI = T.Values[i]; 2126 if (constToInt(CI, C) && C.getBitWidth() > 32) 2127 CI = intToConst(C.trunc(32)); 2128 RC.add(CI); 2129 } 2130 Outputs.update(DefR.Reg, RC); 2131 break; 2132 } 2133 2134 case Hexagon::S4_extract: 2135 case Hexagon::S4_extractp: 2136 case Hexagon::S2_extractu: 2137 case Hexagon::S2_extractup: 2138 { 2139 bool Signed = (Opc == Hexagon::S4_extract) || 2140 (Opc == Hexagon::S4_extractp); 2141 Register R1(MI.getOperand(1)); 2142 unsigned BW = getRegBitWidth(R1.Reg); 2143 unsigned Bits = MI.getOperand(2).getImm(); 2144 unsigned Offset = MI.getOperand(3).getImm(); 2145 LatticeCell RC = Outputs.get(DefR.Reg); 2146 if (Offset >= BW) { 2147 APInt Zero(BW, 0, false); 2148 RC.add(intToConst(Zero)); 2149 break; 2150 } 2151 if (Offset+Bits > BW) { 2152 // If the requested bitfield extends beyond the most significant bit, 2153 // the extra bits are treated as 0s. To emulate this behavior, reduce 2154 // the number of requested bits, and make the extract unsigned. 2155 Bits = BW-Offset; 2156 Signed = false; 2157 } 2158 bool Eval = evaluateEXTRACTr(R1, BW, Bits, Offset, Signed, Inputs, RC); 2159 if (!Eval) 2160 return false; 2161 Outputs.update(DefR.Reg, RC); 2162 break; 2163 } 2164 2165 case Hexagon::S2_vsplatrb: 2166 case Hexagon::S2_vsplatrh: 2167 // vabsh, vabsh:sat 2168 // vabsw, vabsw:sat 2169 // vconj:sat 2170 // vrndwh, vrndwh:sat 2171 // vsathb, vsathub, vsatwuh 2172 // vsxtbh, vsxthw 2173 // vtrunehb, vtrunohb 2174 // vzxtbh, vzxthw 2175 { 2176 bool Eval = evaluateHexVector1(MI, Inputs, Outputs); 2177 if (!Eval) 2178 return false; 2179 break; 2180 } 2181 2182 // TODO: 2183 // A2_vaddh 2184 // A2_vaddhs 2185 // A2_vaddw 2186 // A2_vaddws 2187 } 2188 2189 return true; 2190 } 2191 2192 bool HexagonConstEvaluator::evaluate(const Register &R, 2193 const LatticeCell &Input, LatticeCell &Result) { 2194 if (!R.SubReg) { 2195 Result = Input; 2196 return true; 2197 } 2198 const TargetRegisterClass *RC = MRI->getRegClass(R.Reg); 2199 if (RC != &Hexagon::DoubleRegsRegClass) 2200 return false; 2201 if (R.SubReg != Hexagon::isub_lo && R.SubReg != Hexagon::isub_hi) 2202 return false; 2203 2204 assert(!Input.isTop()); 2205 if (Input.isBottom()) 2206 return false; 2207 2208 using P = ConstantProperties; 2209 2210 if (Input.isProperty()) { 2211 uint32_t Ps = Input.properties(); 2212 if (Ps & (P::Zero|P::NaN)) { 2213 uint32_t Ns = (Ps & (P::Zero|P::NaN|P::SignProperties)); 2214 Result.add(Ns); 2215 return true; 2216 } 2217 if (R.SubReg == Hexagon::isub_hi) { 2218 uint32_t Ns = (Ps & P::SignProperties); 2219 Result.add(Ns); 2220 return true; 2221 } 2222 return false; 2223 } 2224 2225 // The Input cell contains some known values. Pick the word corresponding 2226 // to the subregister. 2227 APInt A; 2228 for (unsigned i = 0; i < Input.size(); ++i) { 2229 const Constant *C = Input.Values[i]; 2230 if (!constToInt(C, A)) 2231 return false; 2232 if (!A.isIntN(64)) 2233 return false; 2234 uint64_t U = A.getZExtValue(); 2235 if (R.SubReg == Hexagon::isub_hi) 2236 U >>= 32; 2237 U &= 0xFFFFFFFFULL; 2238 uint32_t U32 = Lo_32(U); 2239 int32_t V32; 2240 memcpy(&V32, &U32, sizeof V32); 2241 IntegerType *Ty = Type::getInt32Ty(CX); 2242 const ConstantInt *C32 = ConstantInt::get(Ty, static_cast<int64_t>(V32)); 2243 Result.add(C32); 2244 } 2245 return true; 2246 } 2247 2248 bool HexagonConstEvaluator::evaluate(const MachineInstr &BrI, 2249 const CellMap &Inputs, SetVector<const MachineBasicBlock*> &Targets, 2250 bool &FallsThru) { 2251 // We need to evaluate one branch at a time. TII::analyzeBranch checks 2252 // all the branches in a basic block at once, so we cannot use it. 2253 unsigned Opc = BrI.getOpcode(); 2254 bool SimpleBranch = false; 2255 bool Negated = false; 2256 switch (Opc) { 2257 case Hexagon::J2_jumpf: 2258 case Hexagon::J2_jumpfnew: 2259 case Hexagon::J2_jumpfnewpt: 2260 Negated = true; 2261 LLVM_FALLTHROUGH; 2262 case Hexagon::J2_jumpt: 2263 case Hexagon::J2_jumptnew: 2264 case Hexagon::J2_jumptnewpt: 2265 // Simple branch: if([!]Pn) jump ... 2266 // i.e. Op0 = predicate, Op1 = branch target. 2267 SimpleBranch = true; 2268 break; 2269 case Hexagon::J2_jump: 2270 Targets.insert(BrI.getOperand(0).getMBB()); 2271 FallsThru = false; 2272 return true; 2273 default: 2274 Undetermined: 2275 // If the branch is of unknown type, assume that all successors are 2276 // executable. 2277 FallsThru = !BrI.isUnconditionalBranch(); 2278 return false; 2279 } 2280 2281 if (SimpleBranch) { 2282 const MachineOperand &MD = BrI.getOperand(0); 2283 Register PR(MD); 2284 // If the condition operand has a subregister, this is not something 2285 // we currently recognize. 2286 if (PR.SubReg) 2287 goto Undetermined; 2288 assert(Inputs.has(PR.Reg)); 2289 const LatticeCell &PredC = Inputs.get(PR.Reg); 2290 if (PredC.isBottom()) 2291 goto Undetermined; 2292 2293 uint32_t Props = PredC.properties(); 2294 bool CTrue = false, CFalse = false; 2295 if (Props & ConstantProperties::Zero) 2296 CFalse = true; 2297 else if (Props & ConstantProperties::NonZero) 2298 CTrue = true; 2299 // If the condition is not known to be either, bail out. 2300 if (!CTrue && !CFalse) 2301 goto Undetermined; 2302 2303 const MachineBasicBlock *BranchTarget = BrI.getOperand(1).getMBB(); 2304 2305 FallsThru = false; 2306 if ((!Negated && CTrue) || (Negated && CFalse)) 2307 Targets.insert(BranchTarget); 2308 else if ((!Negated && CFalse) || (Negated && CTrue)) 2309 FallsThru = true; 2310 else 2311 goto Undetermined; 2312 } 2313 2314 return true; 2315 } 2316 2317 bool HexagonConstEvaluator::rewrite(MachineInstr &MI, const CellMap &Inputs) { 2318 if (MI.isBranch()) 2319 return rewriteHexBranch(MI, Inputs); 2320 2321 unsigned Opc = MI.getOpcode(); 2322 switch (Opc) { 2323 default: 2324 break; 2325 case Hexagon::A2_tfrsi: 2326 case Hexagon::A2_tfrpi: 2327 case Hexagon::CONST32: 2328 case Hexagon::CONST64: 2329 case Hexagon::PS_true: 2330 case Hexagon::PS_false: 2331 return false; 2332 } 2333 2334 unsigned NumOp = MI.getNumOperands(); 2335 if (NumOp == 0) 2336 return false; 2337 2338 bool AllDefs, Changed; 2339 Changed = rewriteHexConstDefs(MI, Inputs, AllDefs); 2340 // If not all defs have been rewritten (i.e. the instruction defines 2341 // a register that is not compile-time constant), then try to rewrite 2342 // register operands that are known to be constant with immediates. 2343 if (!AllDefs) 2344 Changed |= rewriteHexConstUses(MI, Inputs); 2345 2346 return Changed; 2347 } 2348 2349 unsigned HexagonConstEvaluator::getRegBitWidth(unsigned Reg) const { 2350 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 2351 if (Hexagon::IntRegsRegClass.hasSubClassEq(RC)) 2352 return 32; 2353 if (Hexagon::DoubleRegsRegClass.hasSubClassEq(RC)) 2354 return 64; 2355 if (Hexagon::PredRegsRegClass.hasSubClassEq(RC)) 2356 return 8; 2357 llvm_unreachable("Invalid register"); 2358 return 0; 2359 } 2360 2361 uint32_t HexagonConstEvaluator::getCmp(unsigned Opc) { 2362 switch (Opc) { 2363 case Hexagon::C2_cmpeq: 2364 case Hexagon::C2_cmpeqp: 2365 case Hexagon::A4_cmpbeq: 2366 case Hexagon::A4_cmpheq: 2367 case Hexagon::A4_cmpbeqi: 2368 case Hexagon::A4_cmpheqi: 2369 case Hexagon::C2_cmpeqi: 2370 case Hexagon::J4_cmpeqn1_t_jumpnv_nt: 2371 case Hexagon::J4_cmpeqn1_t_jumpnv_t: 2372 case Hexagon::J4_cmpeqi_t_jumpnv_nt: 2373 case Hexagon::J4_cmpeqi_t_jumpnv_t: 2374 case Hexagon::J4_cmpeq_t_jumpnv_nt: 2375 case Hexagon::J4_cmpeq_t_jumpnv_t: 2376 return Comparison::EQ; 2377 2378 case Hexagon::C4_cmpneq: 2379 case Hexagon::C4_cmpneqi: 2380 case Hexagon::J4_cmpeqn1_f_jumpnv_nt: 2381 case Hexagon::J4_cmpeqn1_f_jumpnv_t: 2382 case Hexagon::J4_cmpeqi_f_jumpnv_nt: 2383 case Hexagon::J4_cmpeqi_f_jumpnv_t: 2384 case Hexagon::J4_cmpeq_f_jumpnv_nt: 2385 case Hexagon::J4_cmpeq_f_jumpnv_t: 2386 return Comparison::NE; 2387 2388 case Hexagon::C2_cmpgt: 2389 case Hexagon::C2_cmpgtp: 2390 case Hexagon::A4_cmpbgt: 2391 case Hexagon::A4_cmphgt: 2392 case Hexagon::A4_cmpbgti: 2393 case Hexagon::A4_cmphgti: 2394 case Hexagon::C2_cmpgti: 2395 case Hexagon::J4_cmpgtn1_t_jumpnv_nt: 2396 case Hexagon::J4_cmpgtn1_t_jumpnv_t: 2397 case Hexagon::J4_cmpgti_t_jumpnv_nt: 2398 case Hexagon::J4_cmpgti_t_jumpnv_t: 2399 case Hexagon::J4_cmpgt_t_jumpnv_nt: 2400 case Hexagon::J4_cmpgt_t_jumpnv_t: 2401 return Comparison::GTs; 2402 2403 case Hexagon::C4_cmplte: 2404 case Hexagon::C4_cmpltei: 2405 case Hexagon::J4_cmpgtn1_f_jumpnv_nt: 2406 case Hexagon::J4_cmpgtn1_f_jumpnv_t: 2407 case Hexagon::J4_cmpgti_f_jumpnv_nt: 2408 case Hexagon::J4_cmpgti_f_jumpnv_t: 2409 case Hexagon::J4_cmpgt_f_jumpnv_nt: 2410 case Hexagon::J4_cmpgt_f_jumpnv_t: 2411 return Comparison::LEs; 2412 2413 case Hexagon::C2_cmpgtu: 2414 case Hexagon::C2_cmpgtup: 2415 case Hexagon::A4_cmpbgtu: 2416 case Hexagon::A4_cmpbgtui: 2417 case Hexagon::A4_cmphgtu: 2418 case Hexagon::A4_cmphgtui: 2419 case Hexagon::C2_cmpgtui: 2420 case Hexagon::J4_cmpgtui_t_jumpnv_nt: 2421 case Hexagon::J4_cmpgtui_t_jumpnv_t: 2422 case Hexagon::J4_cmpgtu_t_jumpnv_nt: 2423 case Hexagon::J4_cmpgtu_t_jumpnv_t: 2424 return Comparison::GTu; 2425 2426 case Hexagon::J4_cmpltu_f_jumpnv_nt: 2427 case Hexagon::J4_cmpltu_f_jumpnv_t: 2428 return Comparison::GEu; 2429 2430 case Hexagon::J4_cmpltu_t_jumpnv_nt: 2431 case Hexagon::J4_cmpltu_t_jumpnv_t: 2432 return Comparison::LTu; 2433 2434 case Hexagon::J4_cmplt_f_jumpnv_nt: 2435 case Hexagon::J4_cmplt_f_jumpnv_t: 2436 return Comparison::GEs; 2437 2438 case Hexagon::C4_cmplteu: 2439 case Hexagon::C4_cmplteui: 2440 case Hexagon::J4_cmpgtui_f_jumpnv_nt: 2441 case Hexagon::J4_cmpgtui_f_jumpnv_t: 2442 case Hexagon::J4_cmpgtu_f_jumpnv_nt: 2443 case Hexagon::J4_cmpgtu_f_jumpnv_t: 2444 return Comparison::LEu; 2445 2446 case Hexagon::J4_cmplt_t_jumpnv_nt: 2447 case Hexagon::J4_cmplt_t_jumpnv_t: 2448 return Comparison::LTs; 2449 2450 default: 2451 break; 2452 } 2453 return Comparison::Unk; 2454 } 2455 2456 APInt HexagonConstEvaluator::getCmpImm(unsigned Opc, unsigned OpX, 2457 const MachineOperand &MO) { 2458 bool Signed = false; 2459 switch (Opc) { 2460 case Hexagon::A4_cmpbgtui: // u7 2461 case Hexagon::A4_cmphgtui: // u7 2462 break; 2463 case Hexagon::A4_cmpheqi: // s8 2464 case Hexagon::C4_cmpneqi: // s8 2465 Signed = true; 2466 break; 2467 case Hexagon::A4_cmpbeqi: // u8 2468 break; 2469 case Hexagon::C2_cmpgtui: // u9 2470 case Hexagon::C4_cmplteui: // u9 2471 break; 2472 case Hexagon::C2_cmpeqi: // s10 2473 case Hexagon::C2_cmpgti: // s10 2474 case Hexagon::C4_cmpltei: // s10 2475 Signed = true; 2476 break; 2477 case Hexagon::J4_cmpeqi_f_jumpnv_nt: // u5 2478 case Hexagon::J4_cmpeqi_f_jumpnv_t: // u5 2479 case Hexagon::J4_cmpeqi_t_jumpnv_nt: // u5 2480 case Hexagon::J4_cmpeqi_t_jumpnv_t: // u5 2481 case Hexagon::J4_cmpgti_f_jumpnv_nt: // u5 2482 case Hexagon::J4_cmpgti_f_jumpnv_t: // u5 2483 case Hexagon::J4_cmpgti_t_jumpnv_nt: // u5 2484 case Hexagon::J4_cmpgti_t_jumpnv_t: // u5 2485 case Hexagon::J4_cmpgtui_f_jumpnv_nt: // u5 2486 case Hexagon::J4_cmpgtui_f_jumpnv_t: // u5 2487 case Hexagon::J4_cmpgtui_t_jumpnv_nt: // u5 2488 case Hexagon::J4_cmpgtui_t_jumpnv_t: // u5 2489 break; 2490 default: 2491 llvm_unreachable("Unhandled instruction"); 2492 break; 2493 } 2494 2495 uint64_t Val = MO.getImm(); 2496 return APInt(32, Val, Signed); 2497 } 2498 2499 void HexagonConstEvaluator::replaceWithNop(MachineInstr &MI) { 2500 MI.setDesc(HII.get(Hexagon::A2_nop)); 2501 while (MI.getNumOperands() > 0) 2502 MI.RemoveOperand(0); 2503 } 2504 2505 bool HexagonConstEvaluator::evaluateHexRSEQ32(Register RL, Register RH, 2506 const CellMap &Inputs, LatticeCell &Result) { 2507 assert(Inputs.has(RL.Reg) && Inputs.has(RH.Reg)); 2508 LatticeCell LSL, LSH; 2509 if (!getCell(RL, Inputs, LSL) || !getCell(RH, Inputs, LSH)) 2510 return false; 2511 if (LSL.isProperty() || LSH.isProperty()) 2512 return false; 2513 2514 unsigned LN = LSL.size(), HN = LSH.size(); 2515 SmallVector<APInt,4> LoVs(LN), HiVs(HN); 2516 for (unsigned i = 0; i < LN; ++i) { 2517 bool Eval = constToInt(LSL.Values[i], LoVs[i]); 2518 if (!Eval) 2519 return false; 2520 assert(LoVs[i].getBitWidth() == 32); 2521 } 2522 for (unsigned i = 0; i < HN; ++i) { 2523 bool Eval = constToInt(LSH.Values[i], HiVs[i]); 2524 if (!Eval) 2525 return false; 2526 assert(HiVs[i].getBitWidth() == 32); 2527 } 2528 2529 for (unsigned i = 0; i < HiVs.size(); ++i) { 2530 APInt HV = HiVs[i].zextOrSelf(64) << 32; 2531 for (unsigned j = 0; j < LoVs.size(); ++j) { 2532 APInt LV = LoVs[j].zextOrSelf(64); 2533 const Constant *C = intToConst(HV | LV); 2534 Result.add(C); 2535 if (Result.isBottom()) 2536 return false; 2537 } 2538 } 2539 return !Result.isBottom(); 2540 } 2541 2542 bool HexagonConstEvaluator::evaluateHexCompare(const MachineInstr &MI, 2543 const CellMap &Inputs, CellMap &Outputs) { 2544 unsigned Opc = MI.getOpcode(); 2545 bool Classic = false; 2546 switch (Opc) { 2547 case Hexagon::C2_cmpeq: 2548 case Hexagon::C2_cmpeqp: 2549 case Hexagon::C2_cmpgt: 2550 case Hexagon::C2_cmpgtp: 2551 case Hexagon::C2_cmpgtu: 2552 case Hexagon::C2_cmpgtup: 2553 case Hexagon::C2_cmpeqi: 2554 case Hexagon::C2_cmpgti: 2555 case Hexagon::C2_cmpgtui: 2556 // Classic compare: Dst0 = CMP Src1, Src2 2557 Classic = true; 2558 break; 2559 default: 2560 // Not handling other compare instructions now. 2561 return false; 2562 } 2563 2564 if (Classic) { 2565 const MachineOperand &Src1 = MI.getOperand(1); 2566 const MachineOperand &Src2 = MI.getOperand(2); 2567 2568 bool Result; 2569 unsigned Opc = MI.getOpcode(); 2570 bool Computed = evaluateHexCompare2(Opc, Src1, Src2, Inputs, Result); 2571 if (Computed) { 2572 // Only create a zero/non-zero cell. At this time there isn't really 2573 // much need for specific values. 2574 Register DefR(MI.getOperand(0)); 2575 LatticeCell L = Outputs.get(DefR.Reg); 2576 uint32_t P = Result ? ConstantProperties::NonZero 2577 : ConstantProperties::Zero; 2578 L.add(P); 2579 Outputs.update(DefR.Reg, L); 2580 return true; 2581 } 2582 } 2583 2584 return false; 2585 } 2586 2587 bool HexagonConstEvaluator::evaluateHexCompare2(unsigned Opc, 2588 const MachineOperand &Src1, const MachineOperand &Src2, 2589 const CellMap &Inputs, bool &Result) { 2590 uint32_t Cmp = getCmp(Opc); 2591 bool Reg1 = Src1.isReg(), Reg2 = Src2.isReg(); 2592 bool Imm1 = Src1.isImm(), Imm2 = Src2.isImm(); 2593 if (Reg1) { 2594 Register R1(Src1); 2595 if (Reg2) { 2596 Register R2(Src2); 2597 return evaluateCMPrr(Cmp, R1, R2, Inputs, Result); 2598 } else if (Imm2) { 2599 APInt A2 = getCmpImm(Opc, 2, Src2); 2600 return evaluateCMPri(Cmp, R1, A2, Inputs, Result); 2601 } 2602 } else if (Imm1) { 2603 APInt A1 = getCmpImm(Opc, 1, Src1); 2604 if (Reg2) { 2605 Register R2(Src2); 2606 uint32_t NegCmp = Comparison::negate(Cmp); 2607 return evaluateCMPri(NegCmp, R2, A1, Inputs, Result); 2608 } else if (Imm2) { 2609 APInt A2 = getCmpImm(Opc, 2, Src2); 2610 return evaluateCMPii(Cmp, A1, A2, Result); 2611 } 2612 } 2613 // Unknown kind of comparison. 2614 return false; 2615 } 2616 2617 bool HexagonConstEvaluator::evaluateHexLogical(const MachineInstr &MI, 2618 const CellMap &Inputs, CellMap &Outputs) { 2619 unsigned Opc = MI.getOpcode(); 2620 if (MI.getNumOperands() != 3) 2621 return false; 2622 const MachineOperand &Src1 = MI.getOperand(1); 2623 const MachineOperand &Src2 = MI.getOperand(2); 2624 Register R1(Src1); 2625 bool Eval = false; 2626 LatticeCell RC; 2627 switch (Opc) { 2628 default: 2629 return false; 2630 case Hexagon::A2_and: 2631 case Hexagon::A2_andp: 2632 Eval = evaluateANDrr(R1, Register(Src2), Inputs, RC); 2633 break; 2634 case Hexagon::A2_andir: { 2635 if (!Src2.isImm()) 2636 return false; 2637 APInt A(32, Src2.getImm(), true); 2638 Eval = evaluateANDri(R1, A, Inputs, RC); 2639 break; 2640 } 2641 case Hexagon::A2_or: 2642 case Hexagon::A2_orp: 2643 Eval = evaluateORrr(R1, Register(Src2), Inputs, RC); 2644 break; 2645 case Hexagon::A2_orir: { 2646 if (!Src2.isImm()) 2647 return false; 2648 APInt A(32, Src2.getImm(), true); 2649 Eval = evaluateORri(R1, A, Inputs, RC); 2650 break; 2651 } 2652 case Hexagon::A2_xor: 2653 case Hexagon::A2_xorp: 2654 Eval = evaluateXORrr(R1, Register(Src2), Inputs, RC); 2655 break; 2656 } 2657 if (Eval) { 2658 Register DefR(MI.getOperand(0)); 2659 Outputs.update(DefR.Reg, RC); 2660 } 2661 return Eval; 2662 } 2663 2664 bool HexagonConstEvaluator::evaluateHexCondMove(const MachineInstr &MI, 2665 const CellMap &Inputs, CellMap &Outputs) { 2666 // Dst0 = Cond1 ? Src2 : Src3 2667 Register CR(MI.getOperand(1)); 2668 assert(Inputs.has(CR.Reg)); 2669 LatticeCell LS; 2670 if (!getCell(CR, Inputs, LS)) 2671 return false; 2672 uint32_t Ps = LS.properties(); 2673 unsigned TakeOp; 2674 if (Ps & ConstantProperties::Zero) 2675 TakeOp = 3; 2676 else if (Ps & ConstantProperties::NonZero) 2677 TakeOp = 2; 2678 else 2679 return false; 2680 2681 const MachineOperand &ValOp = MI.getOperand(TakeOp); 2682 Register DefR(MI.getOperand(0)); 2683 LatticeCell RC = Outputs.get(DefR.Reg); 2684 2685 if (ValOp.isImm()) { 2686 int64_t V = ValOp.getImm(); 2687 unsigned W = getRegBitWidth(DefR.Reg); 2688 APInt A(W, V, true); 2689 const Constant *C = intToConst(A); 2690 RC.add(C); 2691 Outputs.update(DefR.Reg, RC); 2692 return true; 2693 } 2694 if (ValOp.isReg()) { 2695 Register R(ValOp); 2696 const LatticeCell &LR = Inputs.get(R.Reg); 2697 LatticeCell LSR; 2698 if (!evaluate(R, LR, LSR)) 2699 return false; 2700 RC.meet(LSR); 2701 Outputs.update(DefR.Reg, RC); 2702 return true; 2703 } 2704 return false; 2705 } 2706 2707 bool HexagonConstEvaluator::evaluateHexExt(const MachineInstr &MI, 2708 const CellMap &Inputs, CellMap &Outputs) { 2709 // Dst0 = ext R1 2710 Register R1(MI.getOperand(1)); 2711 assert(Inputs.has(R1.Reg)); 2712 2713 unsigned Opc = MI.getOpcode(); 2714 unsigned Bits; 2715 switch (Opc) { 2716 case Hexagon::A2_sxtb: 2717 case Hexagon::A2_zxtb: 2718 Bits = 8; 2719 break; 2720 case Hexagon::A2_sxth: 2721 case Hexagon::A2_zxth: 2722 Bits = 16; 2723 break; 2724 case Hexagon::A2_sxtw: 2725 Bits = 32; 2726 break; 2727 } 2728 2729 bool Signed = false; 2730 switch (Opc) { 2731 case Hexagon::A2_sxtb: 2732 case Hexagon::A2_sxth: 2733 case Hexagon::A2_sxtw: 2734 Signed = true; 2735 break; 2736 } 2737 2738 Register DefR(MI.getOperand(0)); 2739 unsigned BW = getRegBitWidth(DefR.Reg); 2740 LatticeCell RC = Outputs.get(DefR.Reg); 2741 bool Eval = Signed ? evaluateSEXTr(R1, BW, Bits, Inputs, RC) 2742 : evaluateZEXTr(R1, BW, Bits, Inputs, RC); 2743 if (!Eval) 2744 return false; 2745 Outputs.update(DefR.Reg, RC); 2746 return true; 2747 } 2748 2749 bool HexagonConstEvaluator::evaluateHexVector1(const MachineInstr &MI, 2750 const CellMap &Inputs, CellMap &Outputs) { 2751 // DefR = op R1 2752 Register DefR(MI.getOperand(0)); 2753 Register R1(MI.getOperand(1)); 2754 assert(Inputs.has(R1.Reg)); 2755 LatticeCell RC = Outputs.get(DefR.Reg); 2756 bool Eval; 2757 2758 unsigned Opc = MI.getOpcode(); 2759 switch (Opc) { 2760 case Hexagon::S2_vsplatrb: 2761 // Rd = 4 times Rs:0..7 2762 Eval = evaluateSplatr(R1, 8, 4, Inputs, RC); 2763 break; 2764 case Hexagon::S2_vsplatrh: 2765 // Rdd = 4 times Rs:0..15 2766 Eval = evaluateSplatr(R1, 16, 4, Inputs, RC); 2767 break; 2768 default: 2769 return false; 2770 } 2771 2772 if (!Eval) 2773 return false; 2774 Outputs.update(DefR.Reg, RC); 2775 return true; 2776 } 2777 2778 bool HexagonConstEvaluator::rewriteHexConstDefs(MachineInstr &MI, 2779 const CellMap &Inputs, bool &AllDefs) { 2780 AllDefs = false; 2781 2782 // Some diagnostics. 2783 // LLVM_DEBUG({...}) gets confused with all this code as an argument. 2784 #ifndef NDEBUG 2785 bool Debugging = DebugFlag && isCurrentDebugType(DEBUG_TYPE); 2786 if (Debugging) { 2787 bool Const = true, HasUse = false; 2788 for (const MachineOperand &MO : MI.operands()) { 2789 if (!MO.isReg() || !MO.isUse() || MO.isImplicit()) 2790 continue; 2791 Register R(MO); 2792 if (!TargetRegisterInfo::isVirtualRegister(R.Reg)) 2793 continue; 2794 HasUse = true; 2795 // PHIs can legitimately have "top" cells after propagation. 2796 if (!MI.isPHI() && !Inputs.has(R.Reg)) { 2797 dbgs() << "Top " << printReg(R.Reg, &HRI, R.SubReg) 2798 << " in MI: " << MI; 2799 continue; 2800 } 2801 const LatticeCell &L = Inputs.get(R.Reg); 2802 Const &= L.isSingle(); 2803 if (!Const) 2804 break; 2805 } 2806 if (HasUse && Const) { 2807 if (!MI.isCopy()) { 2808 dbgs() << "CONST: " << MI; 2809 for (const MachineOperand &MO : MI.operands()) { 2810 if (!MO.isReg() || !MO.isUse() || MO.isImplicit()) 2811 continue; 2812 unsigned R = MO.getReg(); 2813 dbgs() << printReg(R, &TRI) << ": " << Inputs.get(R) << "\n"; 2814 } 2815 } 2816 } 2817 } 2818 #endif 2819 2820 // Avoid generating TFRIs for register transfers---this will keep the 2821 // coalescing opportunities. 2822 if (MI.isCopy()) 2823 return false; 2824 2825 // Collect all virtual register-def operands. 2826 SmallVector<unsigned,2> DefRegs; 2827 for (const MachineOperand &MO : MI.operands()) { 2828 if (!MO.isReg() || !MO.isDef()) 2829 continue; 2830 unsigned R = MO.getReg(); 2831 if (!TargetRegisterInfo::isVirtualRegister(R)) 2832 continue; 2833 assert(!MO.getSubReg()); 2834 assert(Inputs.has(R)); 2835 DefRegs.push_back(R); 2836 } 2837 2838 MachineBasicBlock &B = *MI.getParent(); 2839 const DebugLoc &DL = MI.getDebugLoc(); 2840 unsigned ChangedNum = 0; 2841 #ifndef NDEBUG 2842 SmallVector<const MachineInstr*,4> NewInstrs; 2843 #endif 2844 2845 // For each defined register, if it is a constant, create an instruction 2846 // NewR = const 2847 // and replace all uses of the defined register with NewR. 2848 for (unsigned i = 0, n = DefRegs.size(); i < n; ++i) { 2849 unsigned R = DefRegs[i]; 2850 const LatticeCell &L = Inputs.get(R); 2851 if (L.isBottom()) 2852 continue; 2853 const TargetRegisterClass *RC = MRI->getRegClass(R); 2854 MachineBasicBlock::iterator At = MI.getIterator(); 2855 2856 if (!L.isSingle()) { 2857 // If this a zero/non-zero cell, we can fold a definition 2858 // of a predicate register. 2859 using P = ConstantProperties; 2860 2861 uint64_t Ps = L.properties(); 2862 if (!(Ps & (P::Zero|P::NonZero))) 2863 continue; 2864 const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass; 2865 if (RC != PredRC) 2866 continue; 2867 const MCInstrDesc *NewD = (Ps & P::Zero) ? 2868 &HII.get(Hexagon::PS_false) : 2869 &HII.get(Hexagon::PS_true); 2870 unsigned NewR = MRI->createVirtualRegister(PredRC); 2871 const MachineInstrBuilder &MIB = BuildMI(B, At, DL, *NewD, NewR); 2872 (void)MIB; 2873 #ifndef NDEBUG 2874 NewInstrs.push_back(&*MIB); 2875 #endif 2876 replaceAllRegUsesWith(R, NewR); 2877 } else { 2878 // This cell has a single value. 2879 APInt A; 2880 if (!constToInt(L.Value, A) || !A.isSignedIntN(64)) 2881 continue; 2882 const TargetRegisterClass *NewRC; 2883 const MCInstrDesc *NewD; 2884 2885 unsigned W = getRegBitWidth(R); 2886 int64_t V = A.getSExtValue(); 2887 assert(W == 32 || W == 64); 2888 if (W == 32) 2889 NewRC = &Hexagon::IntRegsRegClass; 2890 else 2891 NewRC = &Hexagon::DoubleRegsRegClass; 2892 unsigned NewR = MRI->createVirtualRegister(NewRC); 2893 const MachineInstr *NewMI; 2894 2895 if (W == 32) { 2896 NewD = &HII.get(Hexagon::A2_tfrsi); 2897 NewMI = BuildMI(B, At, DL, *NewD, NewR) 2898 .addImm(V); 2899 } else { 2900 if (A.isSignedIntN(8)) { 2901 NewD = &HII.get(Hexagon::A2_tfrpi); 2902 NewMI = BuildMI(B, At, DL, *NewD, NewR) 2903 .addImm(V); 2904 } else { 2905 int32_t Hi = V >> 32; 2906 int32_t Lo = V & 0xFFFFFFFFLL; 2907 if (isInt<8>(Hi) && isInt<8>(Lo)) { 2908 NewD = &HII.get(Hexagon::A2_combineii); 2909 NewMI = BuildMI(B, At, DL, *NewD, NewR) 2910 .addImm(Hi) 2911 .addImm(Lo); 2912 } else { 2913 NewD = &HII.get(Hexagon::CONST64); 2914 NewMI = BuildMI(B, At, DL, *NewD, NewR) 2915 .addImm(V); 2916 } 2917 } 2918 } 2919 (void)NewMI; 2920 #ifndef NDEBUG 2921 NewInstrs.push_back(NewMI); 2922 #endif 2923 replaceAllRegUsesWith(R, NewR); 2924 } 2925 ChangedNum++; 2926 } 2927 2928 LLVM_DEBUG({ 2929 if (!NewInstrs.empty()) { 2930 MachineFunction &MF = *MI.getParent()->getParent(); 2931 dbgs() << "In function: " << MF.getName() << "\n"; 2932 dbgs() << "Rewrite: for " << MI << " created " << *NewInstrs[0]; 2933 for (unsigned i = 1; i < NewInstrs.size(); ++i) 2934 dbgs() << " " << *NewInstrs[i]; 2935 } 2936 }); 2937 2938 AllDefs = (ChangedNum == DefRegs.size()); 2939 return ChangedNum > 0; 2940 } 2941 2942 bool HexagonConstEvaluator::rewriteHexConstUses(MachineInstr &MI, 2943 const CellMap &Inputs) { 2944 bool Changed = false; 2945 unsigned Opc = MI.getOpcode(); 2946 MachineBasicBlock &B = *MI.getParent(); 2947 const DebugLoc &DL = MI.getDebugLoc(); 2948 MachineBasicBlock::iterator At = MI.getIterator(); 2949 MachineInstr *NewMI = nullptr; 2950 2951 switch (Opc) { 2952 case Hexagon::M2_maci: 2953 // Convert DefR += mpyi(R2, R3) 2954 // to DefR += mpyi(R, #imm), 2955 // or DefR -= mpyi(R, #imm). 2956 { 2957 Register DefR(MI.getOperand(0)); 2958 assert(!DefR.SubReg); 2959 Register R2(MI.getOperand(2)); 2960 Register R3(MI.getOperand(3)); 2961 assert(Inputs.has(R2.Reg) && Inputs.has(R3.Reg)); 2962 LatticeCell LS2, LS3; 2963 // It is enough to get one of the input cells, since we will only try 2964 // to replace one argument---whichever happens to be a single constant. 2965 bool HasC2 = getCell(R2, Inputs, LS2), HasC3 = getCell(R3, Inputs, LS3); 2966 if (!HasC2 && !HasC3) 2967 return false; 2968 bool Zero = ((HasC2 && (LS2.properties() & ConstantProperties::Zero)) || 2969 (HasC3 && (LS3.properties() & ConstantProperties::Zero))); 2970 // If one of the operands is zero, eliminate the multiplication. 2971 if (Zero) { 2972 // DefR == R1 (tied operands). 2973 MachineOperand &Acc = MI.getOperand(1); 2974 Register R1(Acc); 2975 unsigned NewR = R1.Reg; 2976 if (R1.SubReg) { 2977 // Generate COPY. FIXME: Replace with the register:subregister. 2978 const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg); 2979 NewR = MRI->createVirtualRegister(RC); 2980 NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR) 2981 .addReg(R1.Reg, getRegState(Acc), R1.SubReg); 2982 } 2983 replaceAllRegUsesWith(DefR.Reg, NewR); 2984 MRI->clearKillFlags(NewR); 2985 Changed = true; 2986 break; 2987 } 2988 2989 bool Swap = false; 2990 if (!LS3.isSingle()) { 2991 if (!LS2.isSingle()) 2992 return false; 2993 Swap = true; 2994 } 2995 const LatticeCell &LI = Swap ? LS2 : LS3; 2996 const MachineOperand &OpR2 = Swap ? MI.getOperand(3) 2997 : MI.getOperand(2); 2998 // LI is single here. 2999 APInt A; 3000 if (!constToInt(LI.Value, A) || !A.isSignedIntN(8)) 3001 return false; 3002 int64_t V = A.getSExtValue(); 3003 const MCInstrDesc &D = (V >= 0) ? HII.get(Hexagon::M2_macsip) 3004 : HII.get(Hexagon::M2_macsin); 3005 if (V < 0) 3006 V = -V; 3007 const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg); 3008 unsigned NewR = MRI->createVirtualRegister(RC); 3009 const MachineOperand &Src1 = MI.getOperand(1); 3010 NewMI = BuildMI(B, At, DL, D, NewR) 3011 .addReg(Src1.getReg(), getRegState(Src1), Src1.getSubReg()) 3012 .addReg(OpR2.getReg(), getRegState(OpR2), OpR2.getSubReg()) 3013 .addImm(V); 3014 replaceAllRegUsesWith(DefR.Reg, NewR); 3015 Changed = true; 3016 break; 3017 } 3018 3019 case Hexagon::A2_and: 3020 { 3021 Register R1(MI.getOperand(1)); 3022 Register R2(MI.getOperand(2)); 3023 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg)); 3024 LatticeCell LS1, LS2; 3025 unsigned CopyOf = 0; 3026 // Check if any of the operands is -1 (i.e. all bits set). 3027 if (getCell(R1, Inputs, LS1) && LS1.isSingle()) { 3028 APInt M1; 3029 if (constToInt(LS1.Value, M1) && !~M1) 3030 CopyOf = 2; 3031 } 3032 else if (getCell(R2, Inputs, LS2) && LS2.isSingle()) { 3033 APInt M1; 3034 if (constToInt(LS2.Value, M1) && !~M1) 3035 CopyOf = 1; 3036 } 3037 if (!CopyOf) 3038 return false; 3039 MachineOperand &SO = MI.getOperand(CopyOf); 3040 Register SR(SO); 3041 Register DefR(MI.getOperand(0)); 3042 unsigned NewR = SR.Reg; 3043 if (SR.SubReg) { 3044 const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg); 3045 NewR = MRI->createVirtualRegister(RC); 3046 NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR) 3047 .addReg(SR.Reg, getRegState(SO), SR.SubReg); 3048 } 3049 replaceAllRegUsesWith(DefR.Reg, NewR); 3050 MRI->clearKillFlags(NewR); 3051 Changed = true; 3052 } 3053 break; 3054 3055 case Hexagon::A2_or: 3056 { 3057 Register R1(MI.getOperand(1)); 3058 Register R2(MI.getOperand(2)); 3059 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg)); 3060 LatticeCell LS1, LS2; 3061 unsigned CopyOf = 0; 3062 3063 using P = ConstantProperties; 3064 3065 if (getCell(R1, Inputs, LS1) && (LS1.properties() & P::Zero)) 3066 CopyOf = 2; 3067 else if (getCell(R2, Inputs, LS2) && (LS2.properties() & P::Zero)) 3068 CopyOf = 1; 3069 if (!CopyOf) 3070 return false; 3071 MachineOperand &SO = MI.getOperand(CopyOf); 3072 Register SR(SO); 3073 Register DefR(MI.getOperand(0)); 3074 unsigned NewR = SR.Reg; 3075 if (SR.SubReg) { 3076 const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg); 3077 NewR = MRI->createVirtualRegister(RC); 3078 NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR) 3079 .addReg(SR.Reg, getRegState(SO), SR.SubReg); 3080 } 3081 replaceAllRegUsesWith(DefR.Reg, NewR); 3082 MRI->clearKillFlags(NewR); 3083 Changed = true; 3084 } 3085 break; 3086 } 3087 3088 if (NewMI) { 3089 // clear all the kill flags of this new instruction. 3090 for (MachineOperand &MO : NewMI->operands()) 3091 if (MO.isReg() && MO.isUse()) 3092 MO.setIsKill(false); 3093 } 3094 3095 LLVM_DEBUG({ 3096 if (NewMI) { 3097 dbgs() << "Rewrite: for " << MI; 3098 if (NewMI != &MI) 3099 dbgs() << " created " << *NewMI; 3100 else 3101 dbgs() << " modified the instruction itself and created:" << *NewMI; 3102 } 3103 }); 3104 3105 return Changed; 3106 } 3107 3108 void HexagonConstEvaluator::replaceAllRegUsesWith(unsigned FromReg, 3109 unsigned ToReg) { 3110 assert(TargetRegisterInfo::isVirtualRegister(FromReg)); 3111 assert(TargetRegisterInfo::isVirtualRegister(ToReg)); 3112 for (auto I = MRI->use_begin(FromReg), E = MRI->use_end(); I != E;) { 3113 MachineOperand &O = *I; 3114 ++I; 3115 O.setReg(ToReg); 3116 } 3117 } 3118 3119 bool HexagonConstEvaluator::rewriteHexBranch(MachineInstr &BrI, 3120 const CellMap &Inputs) { 3121 MachineBasicBlock &B = *BrI.getParent(); 3122 unsigned NumOp = BrI.getNumOperands(); 3123 if (!NumOp) 3124 return false; 3125 3126 bool FallsThru; 3127 SetVector<const MachineBasicBlock*> Targets; 3128 bool Eval = evaluate(BrI, Inputs, Targets, FallsThru); 3129 unsigned NumTargets = Targets.size(); 3130 if (!Eval || NumTargets > 1 || (NumTargets == 1 && FallsThru)) 3131 return false; 3132 if (BrI.getOpcode() == Hexagon::J2_jump) 3133 return false; 3134 3135 LLVM_DEBUG(dbgs() << "Rewrite(" << printMBBReference(B) << "):" << BrI); 3136 bool Rewritten = false; 3137 if (NumTargets > 0) { 3138 assert(!FallsThru && "This should have been checked before"); 3139 // MIB.addMBB needs non-const pointer. 3140 MachineBasicBlock *TargetB = const_cast<MachineBasicBlock*>(Targets[0]); 3141 bool Moot = B.isLayoutSuccessor(TargetB); 3142 if (!Moot) { 3143 // If we build a branch here, we must make sure that it won't be 3144 // erased as "non-executable". We can't mark any new instructions 3145 // as executable here, so we need to overwrite the BrI, which we 3146 // know is executable. 3147 const MCInstrDesc &JD = HII.get(Hexagon::J2_jump); 3148 auto NI = BuildMI(B, BrI.getIterator(), BrI.getDebugLoc(), JD) 3149 .addMBB(TargetB); 3150 BrI.setDesc(JD); 3151 while (BrI.getNumOperands() > 0) 3152 BrI.RemoveOperand(0); 3153 // This ensures that all implicit operands (e.g. implicit-def %r31, etc) 3154 // are present in the rewritten branch. 3155 for (auto &Op : NI->operands()) 3156 BrI.addOperand(Op); 3157 NI->eraseFromParent(); 3158 Rewritten = true; 3159 } 3160 } 3161 3162 // Do not erase instructions. A newly created instruction could get 3163 // the same address as an instruction marked as executable during the 3164 // propagation. 3165 if (!Rewritten) 3166 replaceWithNop(BrI); 3167 return true; 3168 } 3169 3170 FunctionPass *llvm::createHexagonConstPropagationPass() { 3171 return new HexagonConstPropagation(); 3172 } 3173