22 #include "llvm/IR/IntrinsicsHexagon.h"
27 #define DEBUG_TYPE "hexagon-isel"
32 cl::desc(
"Rebalance address calculation trees to improve "
33 "instruction selection"));
40 cl::desc(
"Rebalance address tree only if this allows optimizations"));
45 cl::init(
false),
cl::desc(
"Rebalance address tree only if it is imbalanced"));
54 #define GET_DAGISEL_BODY HexagonDAGToDAGISel
55 #include "HexagonGenDAGISel.inc"
70 int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
71 EVT LoadedVT =
LD->getMemoryVT();
84 Opcode = IsValidInc ? Hexagon::L2_loadrub_pi : Hexagon::L2_loadrub_io;
86 Opcode = IsValidInc ? Hexagon::L2_loadrb_pi : Hexagon::L2_loadrb_io;
90 Opcode = IsValidInc ? Hexagon::L2_loadruh_pi : Hexagon::L2_loadruh_io;
92 Opcode = IsValidInc ? Hexagon::L2_loadrh_pi : Hexagon::L2_loadrh_io;
98 Opcode = IsValidInc ? Hexagon::L2_loadri_pi : Hexagon::L2_loadri_io;
105 Opcode = IsValidInc ? Hexagon::L2_loadrd_pi : Hexagon::L2_loadrd_io;
115 if (isAlignedMemNode(
LD)) {
116 if (
LD->isNonTemporal())
117 Opcode = IsValidInc ? Hexagon::V6_vL32b_nt_pi : Hexagon::V6_vL32b_nt_ai;
119 Opcode = IsValidInc ? Hexagon::V6_vL32b_pi : Hexagon::V6_vL32b_ai;
121 Opcode = IsValidInc ? Hexagon::V6_vL32Ub_pi : Hexagon::V6_vL32Ub_ai;
148 EVT ValueVT =
LD->getValueType(0);
190 unsigned IntNo = cast<ConstantSDNode>(IntN->
getOperand(1))->getZExtValue();
192 static std::map<unsigned,unsigned> LoadPciMap = {
193 { Intrinsic::hexagon_circ_ldb, Hexagon::L2_loadrb_pci },
194 { Intrinsic::hexagon_circ_ldub, Hexagon::L2_loadrub_pci },
195 { Intrinsic::hexagon_circ_ldh, Hexagon::L2_loadrh_pci },
196 { Intrinsic::hexagon_circ_lduh, Hexagon::L2_loadruh_pci },
197 { Intrinsic::hexagon_circ_ldw, Hexagon::L2_loadri_pci },
198 { Intrinsic::hexagon_circ_ldd, Hexagon::L2_loadrd_pci },
200 auto FLC = LoadPciMap.find(IntNo);
201 if (FLC != LoadPciMap.end()) {
205 auto Inc = cast<ConstantSDNode>(IntN->
getOperand(5));
208 { IntN->getOperand(2), I, IntN->getOperand(4),
209 IntN->getOperand(0) });
224 unsigned Size = 1U << (SizeBits-1);
282 switch (cast<ConstantSDNode>(
C->getOperand(1))->getZExtValue()) {
283 case Intrinsic::hexagon_circ_ldub:
284 case Intrinsic::hexagon_circ_lduh:
287 case Intrinsic::hexagon_circ_ldw:
288 case Intrinsic::hexagon_circ_ldd:
295 if (
N->getExtensionType() != IntExt)
322 const SDLoc &dl(IntN);
323 unsigned IntNo = cast<ConstantSDNode>(IntN->
getOperand(1))->getZExtValue();
325 static const std::map<unsigned, unsigned> LoadBrevMap = {
326 { Intrinsic::hexagon_L2_loadrb_pbr, Hexagon::L2_loadrb_pbr },
327 { Intrinsic::hexagon_L2_loadrub_pbr, Hexagon::L2_loadrub_pbr },
328 { Intrinsic::hexagon_L2_loadrh_pbr, Hexagon::L2_loadrh_pbr },
329 { Intrinsic::hexagon_L2_loadruh_pbr, Hexagon::L2_loadruh_pbr },
330 { Intrinsic::hexagon_L2_loadri_pbr, Hexagon::L2_loadri_pbr },
331 { Intrinsic::hexagon_L2_loadrd_pbr, Hexagon::L2_loadrd_pbr }
333 auto FLI = LoadBrevMap.find(IntNo);
334 if (FLI != LoadBrevMap.end()) {
342 FLI->second, dl, RTys,
359 bool HexagonDAGToDAGISel::SelectNewCircIntrinsic(
SDNode *IntN) {
364 unsigned IntNo = cast<ConstantSDNode>(IntN->
getOperand(1))->getZExtValue();
367 static std::map<unsigned,unsigned> LoadNPcMap = {
368 { Intrinsic::hexagon_L2_loadrub_pci, Hexagon::PS_loadrub_pci },
369 { Intrinsic::hexagon_L2_loadrb_pci, Hexagon::PS_loadrb_pci },
370 { Intrinsic::hexagon_L2_loadruh_pci, Hexagon::PS_loadruh_pci },
371 { Intrinsic::hexagon_L2_loadrh_pci, Hexagon::PS_loadrh_pci },
372 { Intrinsic::hexagon_L2_loadri_pci, Hexagon::PS_loadri_pci },
373 { Intrinsic::hexagon_L2_loadrd_pci, Hexagon::PS_loadrd_pci },
374 { Intrinsic::hexagon_L2_loadrub_pcr, Hexagon::PS_loadrub_pcr },
375 { Intrinsic::hexagon_L2_loadrb_pcr, Hexagon::PS_loadrb_pcr },
376 { Intrinsic::hexagon_L2_loadruh_pcr, Hexagon::PS_loadruh_pcr },
377 { Intrinsic::hexagon_L2_loadrh_pcr, Hexagon::PS_loadrh_pcr },
378 { Intrinsic::hexagon_L2_loadri_pcr, Hexagon::PS_loadri_pcr },
379 { Intrinsic::hexagon_L2_loadrd_pcr, Hexagon::PS_loadrd_pcr }
381 auto FLI = LoadNPcMap.find (IntNo);
382 if (FLI != LoadNPcMap.end()) {
384 if (IntNo == Intrinsic::hexagon_L2_loadrd_pci ||
385 IntNo == Intrinsic::hexagon_L2_loadrd_pcr)
390 auto Inc = cast<ConstantSDNode>(IntN->
getOperand(3));
408 static std::map<unsigned,unsigned> StoreNPcMap = {
409 { Intrinsic::hexagon_S2_storerb_pci, Hexagon::PS_storerb_pci },
410 { Intrinsic::hexagon_S2_storerh_pci, Hexagon::PS_storerh_pci },
411 { Intrinsic::hexagon_S2_storerf_pci, Hexagon::PS_storerf_pci },
412 { Intrinsic::hexagon_S2_storeri_pci, Hexagon::PS_storeri_pci },
413 { Intrinsic::hexagon_S2_storerd_pci, Hexagon::PS_storerd_pci },
414 { Intrinsic::hexagon_S2_storerb_pcr, Hexagon::PS_storerb_pcr },
415 { Intrinsic::hexagon_S2_storerh_pcr, Hexagon::PS_storerh_pcr },
416 { Intrinsic::hexagon_S2_storerf_pcr, Hexagon::PS_storerf_pcr },
417 { Intrinsic::hexagon_S2_storeri_pcr, Hexagon::PS_storeri_pcr },
418 { Intrinsic::hexagon_S2_storerd_pcr, Hexagon::PS_storerd_pcr }
420 auto FSI = StoreNPcMap.find (IntNo);
421 if (FSI != StoreNPcMap.end()) {
425 auto Inc = cast<ConstantSDNode>(IntN->
getOperand(3));
469 int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
470 EVT StoredVT =
ST->getMemoryVT();
479 Opcode = IsValidInc ? Hexagon::S2_storerb_pi : Hexagon::S2_storerb_io;
482 Opcode = IsValidInc ? Hexagon::S2_storerh_pi : Hexagon::S2_storerh_io;
488 Opcode = IsValidInc ? Hexagon::S2_storeri_pi : Hexagon::S2_storeri_io;
495 Opcode = IsValidInc ? Hexagon::S2_storerd_pi : Hexagon::S2_storerd_io;
505 if (isAlignedMemNode(
ST)) {
506 if (
ST->isNonTemporal())
507 Opcode = IsValidInc ? Hexagon::V6_vS32b_nt_pi : Hexagon::V6_vS32b_nt_ai;
509 Opcode = IsValidInc ? Hexagon::V6_vS32b_pi : Hexagon::V6_vS32b_ai;
511 Opcode = IsValidInc ? Hexagon::V6_vS32Ub_pi : Hexagon::V6_vS32Ub_ai;
573 auto Default = [
this,
N] () ->
void { SelectCode(
N); };
579 int32_t ShlConst = cast<ConstantSDNode>(Shl_1)->getSExtValue();
586 int32_t ValConst =
C->getSExtValue() << ShlConst;
587 if (isInt<9>(ValConst)) {
607 int32_t ValConst = 1 << (ShlConst + C2->getSExtValue());
608 if (isInt<9>(-ValConst)) {
639 unsigned IntNo = cast<ConstantSDNode>(
N->getOperand(1))->getZExtValue();
640 if (IntNo == Intrinsic::hexagon_V6_vgathermw ||
641 IntNo == Intrinsic::hexagon_V6_vgathermw_128B ||
642 IntNo == Intrinsic::hexagon_V6_vgathermh ||
643 IntNo == Intrinsic::hexagon_V6_vgathermh_128B ||
644 IntNo == Intrinsic::hexagon_V6_vgathermhw ||
645 IntNo == Intrinsic::hexagon_V6_vgathermhw_128B) {
649 if (IntNo == Intrinsic::hexagon_V6_vgathermwq ||
650 IntNo == Intrinsic::hexagon_V6_vgathermwq_128B ||
651 IntNo == Intrinsic::hexagon_V6_vgathermhq ||
652 IntNo == Intrinsic::hexagon_V6_vgathermhq_128B ||
653 IntNo == Intrinsic::hexagon_V6_vgathermhwq ||
654 IntNo == Intrinsic::hexagon_V6_vgathermhwq_128B) {
663 unsigned IID = cast<ConstantSDNode>(
N->getOperand(0))->getZExtValue();
666 case Intrinsic::hexagon_S2_vsplatrb:
669 case Intrinsic::hexagon_S2_vsplatrh:
672 case Intrinsic::hexagon_V6_vaddcarry:
673 case Intrinsic::hexagon_V6_vaddcarry_128B:
674 case Intrinsic::hexagon_V6_vsubcarry:
675 case Intrinsic::hexagon_V6_vsubcarry_128B:
685 if (keepsLowBits(V,
Bits, U)) {
687 N->getOperand(0), U);
689 SelectCode(R.getNode());
700 auto *CN = cast<ConstantFPSDNode>(
N);
701 APInt A = CN->getValueAPF().bitcastToAPInt();
720 if (
N->getValueType(0) ==
MVT::i1) {
721 assert(!(cast<ConstantSDNode>(
N)->getZExtValue() >> 1));
722 unsigned Opc = (cast<ConstantSDNode>(
N)->getSExtValue() != 0)
735 int FX = cast<FrameIndexSDNode>(
N)->getIndex();
763 : Hexagon::A4_subp_c;
765 { N->getOperand(0), N->getOperand(1),
771 MVT ResTy =
N->getValueType(0).getSimpleVT();
773 return SelectHvxVAlign(
N);
794 M0,
N->getOperand(2),
M1);
797 N->getOperand(2),
M1);
811 N->getOperand(0),
N->getOperand(1),
820 int Mask = -cast<ConstantSDNode>(A.getNode())->getSExtValue();
825 N->getOperand(0),
M);
834 MVT OpTy =
Op.getValueType().getSimpleVT();
841 MVT ResTy =
N->getValueType(0).getSimpleVT();
849 MVT ResTy =
N->getValueType(0).getSimpleVT();
852 N->getOperand(0), Zero);
858 MVT ResTy =
N->getValueType(0).getSimpleVT();
860 MVT OpTy =
N->getOperand(0).getValueType().getSimpleVT(); (void)OpTy;
872 MVT ResTy =
N->getValueType(0).getSimpleVT();
884 if (
N->isMachineOpcode())
885 return N->setNodeId(-1);
887 switch (
N->getOpcode()) {
909 switch (
N->getOpcode()) {
920 std::vector<SDValue> &OutOps) {
923 switch (ConstraintID) {
930 OutOps.push_back(Res);
932 OutOps.push_back(Inp);
973 SDValue LDBasePtr = cast<MemSDNode>(SYNode)->getBasePtr();
974 SDValue STBasePtr = cast<MemSDNode>(UUse)->getBasePtr();
975 if (LDBasePtr == STBasePtr)
984 void HexagonDAGToDAGISel::ppSimplifyOrSelect0(std::vector<SDNode*> &&Nodes) {
987 for (
auto I : Nodes) {
991 auto IsZero = [] (
const SDValue &V) ->
bool {
996 auto IsSelect0 = [IsZero] (
const SDValue &
Op) ->
bool {
999 return IsZero(
Op.getOperand(1)) || IsZero(
Op.getOperand(2));
1002 SDValue N0 =
I->getOperand(0), N1 =
I->getOperand(1);
1003 EVT VT =
I->getValueType(0);
1004 bool SelN0 = IsSelect0(N0);
1005 SDValue SOp = SelN0 ? N0 : N1;
1006 SDValue VOp = SelN0 ? N1 : N0;
1017 }
else if (IsZero(SX)) {
1032 void HexagonDAGToDAGISel::ppAddrReorderAddShl(std::vector<SDNode*> &&Nodes) {
1035 for (
auto I : Nodes) {
1067 if (EV % (1 << CV) != 0)
1069 unsigned DV = EV / (1 << CV);
1096 void HexagonDAGToDAGISel::ppAddrRewriteAndSrl(std::vector<SDNode*> &&Nodes) {
1100 unsigned Opc =
N->getOpcode();
1118 ConstantSDNode *SN = dyn_cast<ConstantSDNode>(
S.getOperand(1).getNode());
1137 if (TZ +
M1 + LZ != 32)
1161 void HexagonDAGToDAGISel::ppHoistZextI1(std::vector<SDNode*> &&Nodes) {
1165 unsigned Opc =
N->getOpcode();
1172 for (
auto I =
N->use_begin(),
E =
N->use_end();
I !=
E; ++
I) {
1186 unsigned I1N =
I.getOperandNo();
1190 EVT BVT = Ops[I1N].getValueType();
1197 if (isa<MachineSDNode>(U)) {
1206 If0 = DAG.
getNode(UseOpc, dl, UVT, Ops);
1208 If1 = DAG.
getNode(UseOpc, dl, UVT, Ops);
1226 auto getNodes = [
this] () -> std::vector<SDNode*> {
1227 std::vector<SDNode*>
T;
1236 ppSimplifyOrSelect0(getNodes());
1244 ppAddrReorderAddShl(getNodes());
1259 ppAddrRewriteAndSrl(getNodes());
1263 ppHoistZextI1(getNodes());
1266 dbgs() <<
"Preprocessed (Hexagon) selection DAG:";
1271 rebalanceAddressTrees();
1274 dbgs() <<
"Address tree balanced selection DAG:";
1283 if (!HFI.needsAligna(*
MF))
1295 void HexagonDAGToDAGISel::updateAligna() {
1297 if (!HFI.needsAligna(*
MF))
1299 auto *AlignaI =
const_cast<MachineInstr*
>(HFI.getAlignaInstr(*
MF));
1300 assert(AlignaI !=
nullptr);
1302 if (AlignaI->getOperand(1).getImm() < MaxA)
1303 AlignaI->getOperand(1).setImm(MaxA);
1312 int FX = cast<FrameIndexSDNode>(
N)->getIndex();
1345 EVT T =
N.getValueType();
1346 if (!
T.isInteger() ||
T.getSizeInBits() != 32 || !isa<ConstantSDNode>(
N))
1348 int32_t V = cast<const ConstantSDNode>(
N)->getZExtValue();
1355 switch (
N.getOpcode()) {
1359 int32_t V = cast<const ConstantSDNode>(
N)->getZExtValue();
1368 if (Alignment >
Align(8))
1370 R =
N.getOperand(0);
1374 if (Alignment >
Align(1))
1380 if (Alignment >
Align(4) ||
1395 bool UseGP,
Align Alignment) {
1396 switch (
N.getOpcode()) {
1406 if (!
isAligned(Alignment, Const->getZExtValue()))
1413 N.getValueType(), NewOff);
1426 R =
N.getOperand(0);
1430 R =
N.getOperand(0);
1460 unsigned Opc =
N.getOpcode();
1466 ?
N.getOperand(0).getValueType()
1467 : cast<VTSDNode>(
N.getOperand(1))->getVT();
1468 unsigned SW =
T.getSizeInBits();
1470 R =
N.getOperand(0);
1489 auto *
S = dyn_cast<ConstantSDNode>(
N.getOperand(1));
1490 if (!
S ||
S->getZExtValue() != 32)
1498 EVT RT = R.getValueType();
1516 bool HexagonDAGToDAGISel::keepsLowBits(
const SDValue &Val,
unsigned NumBits,
1525 if (
T.isInteger() &&
T.getSizeInBits() == NumBits) {
1536 if (
T->getVT().getSizeInBits() == NumBits) {
1546 if (
C->getZExtValue() ==
Mask) {
1552 if (
C->getZExtValue() ==
Mask) {
1564 if ((
C->getZExtValue() &
Mask) == 0) {
1570 if ((
C->getZExtValue() &
Mask) == 0) {
1583 bool HexagonDAGToDAGISel::isAlignedMemNode(
const MemSDNode *
N)
const {
1584 return N->getAlign().value() >=
N->getMemoryVT().getStoreSize();
1587 bool HexagonDAGToDAGISel::isSmallStackStore(
const StoreSDNode *
N)
const {
1589 switch (
N->getMemoryVT().getStoreSize()) {
1591 return StackSize <= 56;
1593 return StackSize <= 120;
1595 return StackSize <= 248;
1602 bool HexagonDAGToDAGISel::isPositiveHalfWord(
const SDNode *
N)
const {
1608 const VTSDNode *VN = dyn_cast<const VTSDNode>(
N->getOperand(1));
1614 bool HexagonDAGToDAGISel::hasOneUse(
const SDNode *
N)
const {
1622 switch (
N->getOpcode()) {
1629 return isa<ConstantSDNode>(
N->getOperand(1).getNode());
1636 int HexagonDAGToDAGISel::getWeight(
SDNode *
N) {
1639 assert(RootWeights.count(
N) &&
"Cannot get weight of unseen root!");
1640 assert(RootWeights[
N] != -1 &&
"Cannot get weight of unvisited root!");
1641 assert(RootWeights[
N] != -2 &&
"Cannot get weight of RAWU'd root!");
1642 return RootWeights[
N];
1645 int HexagonDAGToDAGISel::getHeight(
SDNode *
N) {
1648 assert(RootWeights.count(
N) && RootWeights[
N] >= 0 &&
1649 "Cannot query height of unvisited/RAUW'd node!");
1650 return RootHeights[
N];
1654 struct WeightedLeaf {
1661 WeightedLeaf(
SDValue Value,
int Weight,
int InsertionOrder) :
1662 Value(
Value), Weight(Weight), InsertionOrder(InsertionOrder) {
1663 assert(Weight >= 0 &&
"Weight must be >= 0");
1666 static bool Compare(
const WeightedLeaf &A,
const WeightedLeaf &
B) {
1667 assert(
A.Value.getNode() &&
B.Value.getNode());
1668 return A.Weight ==
B.Weight ?
1669 (
A.InsertionOrder >
B.InsertionOrder) :
1670 (
A.Weight >
B.Weight);
1677 class LeafPrioQueue {
1680 WeightedLeaf ConstElt;
1685 return (!HaveConst && Q.empty());
1689 return Q.size() + HaveConst;
1696 const WeightedLeaf &top() {
1702 WeightedLeaf pop() {
1711 void push(WeightedLeaf L,
bool SeparateConst=
true) {
1712 if (!HaveConst && SeparateConst && isa<ConstantSDNode>(L.Value)) {
1714 cast<ConstantSDNode>(L.Value)->getSExtValue() == 1)
1717 cast<ConstantSDNode>(L.Value)->getSExtValue() == 0)
1730 void pushToBottom(WeightedLeaf L) {
1737 WeightedLeaf findSHL(
uint64_t MaxAmount);
1739 WeightedLeaf findMULbyConst();
1741 LeafPrioQueue(
unsigned Opcode) :
1742 HaveConst(
false), Opcode(Opcode) { }
1746 WeightedLeaf LeafPrioQueue::findSHL(
uint64_t MaxAmount) {
1750 for (
int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
1751 const WeightedLeaf &L = Q[Pos];
1757 if (!
Result.Value.getNode() ||
Result.Weight > L.Weight ||
1758 (
Result.Weight == L.Weight &&
Result.InsertionOrder > L.InsertionOrder))
1765 if (
Result.Value.getNode()) {
1766 Q.
erase(&Q[ResultPos]);
1773 WeightedLeaf LeafPrioQueue::findMULbyConst() {
1777 for (
int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
1778 const WeightedLeaf &L = Q[Pos];
1784 if (!
Result.Value.getNode() ||
Result.Weight > L.Weight ||
1785 (
Result.Weight == L.Weight &&
Result.InsertionOrder > L.InsertionOrder))
1792 if (
Result.Value.getNode()) {
1793 Q.
erase(&Q[ResultPos]);
1801 uint64_t MulFactor = 1ull <<
N->getConstantOperandVal(1);
1803 N->getOperand(1).getValueType());
1809 unsigned MaxFactor = 0;
1810 for (
int i = 0;
i < 2; ++
i) {
1814 const APInt &CInt =
C->getAPIntValue();
1833 for (
int i = 0;
i < 2; ++
i)
1834 if (isa<ConstantSDNode>(Ops[
i].getNode()) &&
1837 return (NewConst == 1);
1846 SDValue HexagonDAGToDAGISel::factorOutPowerOf2(
SDValue V,
unsigned Power) {
1849 for (
int i=0;
i < 2; ++
i) {
1850 if (isa<ConstantSDNode>(Ops[
i].getNode()) &&
1862 if (ShiftAmount == Power)
1876 unsigned HexagonDAGToDAGISel::getUsesInFunction(
const Value *V) {
1877 if (GAUsesInFunction.count(V))
1878 return GAUsesInFunction[V];
1883 if (isa<Instruction>(U) &&
1888 GAUsesInFunction[V] =
Result;
1898 SDValue HexagonDAGToDAGISel::balanceSubTree(
SDNode *
N,
bool TopLevel) {
1899 assert(RootWeights.count(
N) &&
"Cannot balance non-root node.");
1900 assert(RootWeights[
N] != -2 &&
"This node was RAUW'd!");
1904 if (RootWeights[
N] != -1)
1918 Weight = getWeight(balanceSubTree(Op0N).getNode());
1921 Weight = getWeight(Op0N);
1923 SDNode *Op1N =
N->getOperand(1).getNode();
1925 Weight += getWeight(balanceSubTree(Op1N).getNode());
1928 Weight += getWeight(Op1N);
1930 RootWeights[
N] = Weight;
1931 RootHeights[
N] =
std::max(getHeight(
N->getOperand(0).getNode()),
1932 getHeight(
N->getOperand(1).getNode())) + 1;
1934 LLVM_DEBUG(
dbgs() <<
"--> No need to balance root (Weight=" << Weight
1935 <<
" Height=" << RootHeights[
N] <<
"): ");
1944 unsigned NOpcode =
N->getOpcode();
1946 LeafPrioQueue Leaves(NOpcode);
1954 bool CanFactorize =
false;
1955 WeightedLeaf Mul1, Mul2;
1956 unsigned MaxPowerOf2 = 0;
1961 bool HaveTopLevelShift =
false;
1967 HaveTopLevelShift =
true;
1971 int InsertionOrder = 0;
1973 bool Imbalanced =
false;
1974 int CurrentWeight = 0;
1975 while (!Worklist.empty()) {
1981 int Weight = RootWeights[Child.
getNode()];
1983 Child = balanceSubTree(Child.
getNode());
1985 Weight = getWeight(Child.
getNode());
1986 }
else if (Weight == -2) {
1991 return balanceSubTree(
N, TopLevel);
1994 NodeHeights[Child] = 1;
1995 CurrentWeight += Weight;
1998 if (TopLevel && !CanFactorize && !HaveTopLevelShift &&
2004 if (!Mul1.Value.getNode()) {
2005 Mul1 = WeightedLeaf(Child, Weight, InsertionOrder++);
2006 MaxPowerOf2 = PowerOf2;
2008 Mul2 = WeightedLeaf(Child, Weight, InsertionOrder++);
2009 MaxPowerOf2 =
std::min(MaxPowerOf2, PowerOf2);
2012 if (MaxPowerOf2 > 3)
2015 CanFactorize =
true;
2018 Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
2021 int Weight = getWeight(Child.
getNode());
2023 NodeHeights[Child] = getHeight(Child.
getNode());
2024 CurrentWeight += Weight;
2027 GA = WeightedLeaf(Child, Weight, InsertionOrder++);
2029 Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
2033 unsigned ChildOpcode = Child.
getOpcode();
2034 assert(ChildOpcode == NOpcode ||
2040 Op1 = getMultiplierForSHL(Child.
getNode());
2045 assert(!NodeHeights.
count(Child) &&
"Parent visited before children?");
2047 Worklist.push_back(Child);
2048 Worklist.push_back(Op1);
2055 NodeHeights[Child] =
std::max(NodeHeights[Op1],
2062 <<
" weight=" << CurrentWeight
2063 <<
" imbalanced=" << Imbalanced <<
"\n");
2069 LLVM_DEBUG(
dbgs() <<
"--> Found common factor for two MUL children!\n");
2070 int Weight = Mul1.Weight + Mul2.Weight;
2071 int Height =
std::max(NodeHeights[Mul1.Value], NodeHeights[Mul2.Value]) + 1;
2072 SDValue Mul1Factored = factorOutPowerOf2(Mul1.Value, MaxPowerOf2);
2073 SDValue Mul2Factored = factorOutPowerOf2(Mul2.Value, MaxPowerOf2);
2075 Mul1Factored, Mul2Factored);
2077 Mul1.Value.getValueType());
2080 NodeHeights[
New] = Height;
2081 Leaves.push(WeightedLeaf(New, Weight, Mul1.InsertionOrder));
2082 }
else if (Mul1.Value.getNode()) {
2086 if (Mul2.Value.getNode())
2088 CanFactorize =
false;
2094 bool CombinedGA =
false;
2095 if (NOpcode ==
ISD::ADD && GA.Value.getNode() && Leaves.hasConst() &&
2096 GA.Value.hasOneUse() &&
N->use_size() < 3) {
2098 cast<GlobalAddressSDNode>(GA.Value.getOperand(0));
2101 if (getUsesInFunction(GANode->
getGlobal()) == 1 &&
Offset->hasOneUse() &&
2104 <<
Offset->getSExtValue() <<
"): ");
2112 GA.Value.getValueType(), NewTGA);
2113 GA.Weight += Leaves.top().Weight;
2115 NodeHeights[GA.Value] = getHeight(GA.Value.getNode());
2124 RootWeights[
N] = CurrentWeight;
2125 RootHeights[
N] = NodeHeights[
SDValue(
N, 0)];
2131 if (NOpcode ==
ISD::ADD && GA.Value.getNode()) {
2132 WeightedLeaf
SHL = Leaves.findSHL(31);
2133 if (
SHL.Value.getNode()) {
2134 int Height =
std::max(NodeHeights[GA.Value], NodeHeights[
SHL.Value]) + 1;
2136 GA.Value.getValueType(),
2137 GA.Value,
SHL.Value);
2138 GA.Weight =
SHL.Weight;
2139 NodeHeights[GA.Value] = Height;
2143 if (GA.Value.getNode())
2148 if (TopLevel && !CanFactorize && Leaves.hasConst()) {
2150 Leaves.pushToBottom(Leaves.pop());
2157 while (Leaves.size() > 1) {
2158 WeightedLeaf L0 = Leaves.pop();
2162 WeightedLeaf L1 = Leaves.findMULbyConst();
2163 if (!L1.Value.getNode())
2166 assert(L0.Weight <= L1.Weight &&
"Priority queue is broken!");
2169 int V0Weight = L0.Weight;
2171 int V1Weight = L1.Weight;
2174 if ((RootWeights.count(V0.
getNode()) && RootWeights[V0.
getNode()] == -2) ||
2175 (RootWeights.count(V1.
getNode()) && RootWeights[V1.
getNode()] == -2)) {
2177 return balanceSubTree(
N, TopLevel);
2182 EVT VT =
N->getValueType(0);
2192 "Children must have been visited before re-combining them!");
2193 int Height =
std::max(NodeHeights[V0], NodeHeights[V1]) + 1;
2205 NodeHeights[NewNode] = Height;
2207 int Weight = V0Weight + V1Weight;
2208 Leaves.push(WeightedLeaf(NewNode, Weight, L0.InsertionOrder));
2211 <<
",Height=" << Height <<
"):\n");
2215 assert(Leaves.size() == 1);
2216 SDValue NewRoot = Leaves.top().Value;
2219 int Height = NodeHeights[NewRoot];
2242 RootWeights[
N] = -2;
2247 RootWeights[NewRoot.
getNode()] = Leaves.top().Weight;
2248 RootHeights[NewRoot.
getNode()] = Height;
2253 void HexagonDAGToDAGISel::rebalanceAddressTrees() {
2264 if (RootWeights.count(
BasePtr.getNode()))
2267 LLVM_DEBUG(
dbgs() <<
"** Rebalancing address calculation in node: ");
2273 Worklist.push_back(
BasePtr.getOperand(0).getNode());
2274 Worklist.push_back(
BasePtr.getOperand(1).getNode());
2276 while (!Worklist.empty()) {
2278 unsigned Opcode =
N->getOpcode();
2283 Worklist.push_back(
N->getOperand(0).getNode());
2284 Worklist.push_back(
N->getOperand(1).getNode());
2287 if (
N->hasOneUse() && Opcode ==
N->use_begin()->getOpcode())
2291 if (RootWeights.count(
N))
2294 RootWeights[
N] = -1;
2298 RootWeights[
BasePtr.getNode()] = -1;
2303 NewBasePtr,
N->getOperand(2));
2306 NewBasePtr,
N->getOperand(3));
2313 GAUsesInFunction.clear();
2314 RootHeights.clear();
2315 RootWeights.clear();