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