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