Lines Matching +full:higher +full:- +full:end
1 //===- HexagonConstExtenders.cpp ------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
28 #define DEBUG_TYPE "hexagon-cext-opt"
33 "hexagon-cext-threshold", cl::init(3), cl::Hidden,
37 ReplaceLimit("hexagon-cext-limit", cl::init(0), cl::Hidden,
47 int32_t U = (V & -A) + O; in adjustUp()
53 int32_t U = (V & -A) + O; in adjustDown()
54 return U <= V ? U : U-A; in adjustDown()
74 if (Offset >= A.Offset && (Offset - A.Offset) % A.Align == 0) { in intersect()
80 Max = -1; in intersect()
84 std::tie(Min, Max, Align) = std::make_tuple(0, -1, 1); in intersect()
97 Min = (INT_MIN-D < Min) ? Min+D : INT_MIN; in extendBy()
99 Max = (INT_MAX-D > Max) ? Max+D : INT_MAX; in extendBy()
106 return Min <= V && V <= Max && (V-Offset) % Align == 0; in contains()
167 Node *rotateLeft(Node *Lower, Node *Higher);
168 Node *rotateRight(Node *Lower, Node *Higher);
170 return N != nullptr ? N->Height : 0; in height()
174 N->Height = 1 + std::max(height(N->Left), height(N->Right)); in update()
175 if (N->Left) in update()
176 N->MaxEnd = std::max(N->MaxEnd, N->Left->MaxEnd); in update()
177 if (N->Right) in update()
178 N->MaxEnd = std::max(N->MaxEnd, N->Right->MaxEnd); in update()
183 int32_t Balance = height(N->Right) - height(N->Left); in rebalance()
184 if (Balance < -1) in rebalance()
185 return rotateRight(N->Left, N); in rebalance()
187 return rotateLeft(N->Right, N); in rebalance()
198 if (B->end() == It) { in Loc()
199 Pos = -1; in Loc()
201 assert(It->getParent() == B); in Loc()
202 Pos = std::distance(B->begin(), It); in Loc()
207 return Block->getNumber() < A.Block->getNumber(); in operator <()
208 if (A.Pos == -1) in operator <()
210 return Pos != -1 && Pos < A.Pos; in operator <()
227 return "Hexagon constant-extender optimization"; in getPassName()
292 // ##Val - Rs
320 unsigned OpNum = -1u;
332 return UseMI->getOperand(OpNum); in getOp()
335 return UseMI->getOperand(OpNum); in getOp()
401 void assignInits(const ExtRoot &ER, unsigned Begin, unsigned End,
469 OS << "## " << (P.Ex.Neg ? "- " : "+ "); in operator <<()
494 assert(ED.OpNum != -1u); in operator <<()
495 const MachineBasicBlock &MBB = *ED.getOp().getParent()->getParent(); in operator <<()
522 OS << "gad:" << ER.V.GV->getName(); in operator <<()
560 OS << " " << PrintInit(Q.first, P.HRI) << " -> {"; in operator <<()
570 INITIALIZE_PASS_BEGIN(HexagonConstExtenders, "hexagon-cext-opt",
571 "Hexagon constant-extender optimization", false, false)
573 INITIALIZE_PASS_END(HexagonConstExtenders, "hexagon-cext-opt",
574 "Hexagon constant-extender optimization", false, false)
589 dbgs() << " Height: " << N->Height << '\n'; in dump()
590 dbgs() << " Count: " << N->Count << '\n'; in dump()
591 dbgs() << " MaxEnd: " << N->MaxEnd << '\n'; in dump()
592 dbgs() << " Range: " << N->Range << '\n'; in dump()
593 dbgs() << " Left: " << N->Left << '\n'; in dump()
594 dbgs() << " Right: " << N->Right << "\n\n"; in dump()
596 if (N->Left) in dump()
597 dump(N->Left); in dump()
598 if (N->Right) in dump()
599 dump(N->Right); in dump()
606 order(N->Left, Seq); in order()
608 order(N->Right, Seq); in order()
613 if (N == nullptr || N->MaxEnd < P) in nodesWith()
615 nodesWith(N->Left, P, CheckA, Seq); in nodesWith()
616 if (N->Range.Min <= P) { in nodesWith()
617 if ((CheckA && N->Range.contains(P)) || (!CheckA && P <= N->Range.Max)) in nodesWith()
619 nodesWith(N->Right, P, CheckA, Seq); in nodesWith()
627 if (N->Range == R) { in add()
628 N->Count++; in add()
632 if (R < N->Range) in add()
633 N->Left = add(N->Left, R); in add()
635 N->Right = add(N->Right, R); in add()
643 assert(N->Range != D->Range && "N and D should not be equal"); in remove()
644 if (D->Range < N->Range) in remove()
645 N->Left = remove(N->Left, D); in remove()
647 N->Right = remove(N->Right, D); in remove()
653 if (N->Left == nullptr || N->Right == nullptr) in remove()
654 return (N->Left == nullptr) ? N->Right : N->Left; in remove()
656 // Find the rightmost child of N->Left, remove it and plug it in place in remove()
658 Node *M = N->Left; in remove()
659 while (M->Right) in remove()
660 M = M->Right; in remove()
661 M->Left = remove(N->Left, M); in remove()
662 M->Right = N->Right; in remove()
666 RangeTree::Node *RangeTree::rotateLeft(Node *Lower, Node *Higher) { in rotateLeft() argument
667 assert(Higher->Right == Lower); in rotateLeft()
668 // The Lower node is on the right from Higher. Make sure that Lower's in rotateLeft()
671 if (height(Lower->Left) > height(Lower->Right)) in rotateLeft()
672 Lower = rotateRight(Lower->Left, Lower); in rotateLeft()
673 assert(height(Lower->Left) <= height(Lower->Right)); in rotateLeft()
674 Higher->Right = Lower->Left; in rotateLeft()
675 update(Higher); in rotateLeft()
676 Lower->Left = Higher; in rotateLeft()
681 RangeTree::Node *RangeTree::rotateRight(Node *Lower, Node *Higher) { in rotateRight() argument
682 assert(Higher->Left == Lower); in rotateRight()
683 // The Lower node is on the left from Higher. Make sure that Lower's in rotateRight()
686 if (height(Lower->Left) < height(Lower->Right)) in rotateRight()
687 Lower = rotateLeft(Lower->Right, Lower); in rotateRight()
688 assert(height(Lower->Left) >= height(Lower->Right)); in rotateRight()
689 Higher->Left = Lower->Right; in rotateRight()
690 update(Higher); in rotateRight()
691 Lower->Right = Higher; in rotateRight()
729 const APFloat &ThisF = V.CFP->getValueAPF(); in operator <()
730 const APFloat &OtherF = ER.V.CFP->getValueAPF(); in operator <()
740 assert(!V.GV->getName().empty() && !ER.V.GV->getName().empty()); in operator <()
741 return V.GV->getName() < ER.V.GV->getName(); in operator <()
743 const BasicBlock *ThisB = V.BA->getBasicBlock(); in operator <()
744 const BasicBlock *OtherB = ER.V.BA->getBasicBlock(); in operator <()
745 assert(ThisB->getParent() == OtherB->getParent()); in operator <()
746 const Function &F = *ThisB->getParent(); in operator <()
747 return std::distance(F.begin(), ThisB->getIterator()) < in operator <()
748 std::distance(F.begin(), OtherB->getIterator()); in operator <()
875 const MCInstrDesc &D = HII->get(ExtOpc); in getRegOffOpcode()
998 case Hexagon::M2_accii: return Hexagon::M2_acci; // T -> T in getDirectRegReplacement()
1000 case Hexagon::M2_macsip: return Hexagon::M2_maci; // T -> T in getDirectRegReplacement()
1004 case Hexagon::M2_naccii: return Hexagon::M2_nacci; // T -> T in getDirectRegReplacement()
1006 case Hexagon::M4_mpyri_addr: return Hexagon::M4_mpyrr_addr; // _ -> T in getDirectRegReplacement()
1007 case Hexagon::M4_mpyrr_addi: return Hexagon::M4_mpyrr_addr; // _ -> T in getDirectRegReplacement()
1008 case Hexagon::S4_addaddi: return Hexagon::M2_acci; // _ -> T in getDirectRegReplacement()
1009 case Hexagon::S4_addi_asl_ri: return Hexagon::S2_asl_i_r_acc; // T -> T in getDirectRegReplacement()
1010 case Hexagon::S4_addi_lsr_ri: return Hexagon::S2_lsr_i_r_acc; // T -> T in getDirectRegReplacement()
1011 case Hexagon::S4_andi_asl_ri: return Hexagon::S2_asl_i_r_and; // T -> T in getDirectRegReplacement()
1012 case Hexagon::S4_andi_lsr_ri: return Hexagon::S2_lsr_i_r_and; // T -> T in getDirectRegReplacement()
1013 case Hexagon::S4_ori_asl_ri: return Hexagon::S2_asl_i_r_or; // T -> T in getDirectRegReplacement()
1014 case Hexagon::S4_ori_lsr_ri: return Hexagon::S2_lsr_i_r_or; // T -> T in getDirectRegReplacement()
1015 case Hexagon::S4_subaddi: return Hexagon::M2_subacc; // _ -> T in getDirectRegReplacement()
1016 case Hexagon::S4_subi_asl_ri: return Hexagon::S2_asl_i_r_nac; // T -> T in getDirectRegReplacement()
1017 case Hexagon::S4_subi_lsr_ri: return Hexagon::S2_lsr_i_r_nac; // T -> T in getDirectRegReplacement()
1019 // Store-immediates: in getDirectRegReplacement()
1048 // Rc, where Rc-Rb belongs to [Min+1, Max+1].
1051 // Instructions that are constant-extended may be replaced with something in getOffsetRange()
1053 if (!isRegOffOpcode(Opc) || HII->isConstExtended(MI)) in getOffsetRange()
1060 OffsetRange R = { -(1<<15)+1, (1<<15)-1, 1 }; in getOffsetRange()
1065 if (HII->isPostIncrement(MI)) in getOffsetRange()
1068 const MCInstrDesc &D = HII->get(Opc); in getOffsetRange()
1072 if (!HII->getBaseAndOffsetPosition(MI, BaseP, OffP) || in getOffsetRange()
1082 int32_t Min = -alignDown((1<<S)-1, A); in getOffsetRange()
1084 // The range will be shifted by Off. To prefer non-negative offsets, in getOffsetRange()
1087 int32_t Max = Off >= 0 ? 0 : -Off; in getOffsetRange()
1101 // The only way that there can be a non-zero range available is if in getOffsetRange()
1104 unsigned IdxOpc = getRegOffOpcode(ED.UseMI->getOpcode()); in getOffsetRange()
1109 return { -32767, 32767, 1 }; in getOffsetRange()
1111 return { -511, 511, 1 }; in getOffsetRange()
1114 if (!ED.UseMI->mayLoad() && !ED.UseMI->mayStore()) in getOffsetRange()
1116 const MCInstrDesc &D = HII->get(IdxOpc); in getOffsetRange()
1122 int32_t Min = -alignDown((1<<S)-1, A); in getOffsetRange()
1123 int32_t Max = 0; // Force non-negative offsets. in getOffsetRange()
1131 for (const MachineOperand &Op : MRI->use_operands(Rd.Reg)) { in getOffsetRange()
1134 // precludes any non-trivial range. in getOffsetRange()
1158 unsigned AM = HII->getAddrMode(MI); in recordExtender()
1164 ED.Rd = MI.getOperand(OpNum-1); in recordExtender()
1168 // Store-immediates are treated as non-memory operations, since in recordExtender()
1172 ED.Expr.Rs = MI.getOperand(OpNum-1); in recordExtender()
1175 ED.Expr.Rs = MI.getOperand(OpNum-2); in recordExtender()
1176 ED.Expr.S = MI.getOperand(OpNum-1).getImm(); in recordExtender()
1198 ED.Expr.Rs = MI.getOperand(OpNum-1); in recordExtender()
1203 ED.Expr.Rs = MI.getOperand(OpNum-1); in recordExtender()
1205 case Hexagon::A2_subri: // (Rd: ## - Rs<<0) in recordExtender()
1210 case Hexagon::S4_subaddi: // (__: ## - Rs<<0) in recordExtender()
1224 if (ER.V.GV->getName().empty()) in recordExtender()
1228 if (ER.V.BA->getFunction() != &(MI.getMF()->getFunction())) in recordExtender()
1234 if (!HII->isConstExtended(MI)) in collectInstr()
1237 // Skip some non-convertible instructions. in collectInstr()
1240 case Hexagon::M2_macsin: // There is no Rx -= mpyi(Rs,Rt). in collectInstr()
1247 recordExtender(MI, HII->getCExtOpNum(MI)); in collectInstr()
1254 if (MBB.getNumber() == -1) in collect()
1261 void HCE::assignInits(const ExtRoot &ER, unsigned Begin, unsigned End, in assignInits() argument
1263 // Basic correctness: make sure that all extenders in the range [Begin..End) in assignInits()
1265 for (unsigned I = Begin; I != End; ++I) in assignInits()
1271 // (here, Off = required_value - P). in assignInits()
1272 std::vector<OffsetRange> Ranges(End-Begin); in assignInits()
1278 for (unsigned I = Begin; I != End; ++I) { in assignInits()
1285 Ranges[I-Begin] = getOffsetRange(ED.Rd).shift(EV.Offset); in assignInits()
1287 // has a 16-bit signed offset. This means that A2_tfrsi not only has a in assignInits()
1290 if (ED.UseMI->getOpcode() == Hexagon::A2_tfrsi) { in assignInits()
1291 int32_t D = alignDown(32767, Ranges[I-Begin].Align); // XXX hardcoded in assignInits()
1292 Ranges[I-Begin].extendBy(-D).extendBy(D); in assignInits()
1296 // Visit all non-def extenders. For each one, determine the offset range in assignInits()
1298 for (unsigned I = Begin; I != End; ++I) { in assignInits()
1305 Ranges[I-Begin].intersect(Dev.shift(EV.Offset)); in assignInits()
1310 // [Begin..End) that this range corresponds to. in assignInits()
1312 for (unsigned I = Begin; I != End; ++I) in assignInits()
1313 RangeMap[Ranges[I-Begin]].insert(I); in assignInits()
1317 for (unsigned I = Begin; I != End; ++I) in assignInits()
1318 dbgs() << " " << I << ". " << Ranges[I-Begin] << '\n'; in assignInits()
1321 dbgs() << " " << P.first << " ->"; in assignInits()
1346 if (N->Range.Align <= Align || N->Range.Offset < Offset) in assignInits()
1348 if ((N->Range.Offset - Offset) % Align != 0) in assignInits()
1350 Align = N->Range.Align; in assignInits()
1351 Offset = N->Range.Offset; in assignInits()
1358 // but with a higher alignment, also consider the more-highly-aligned in assignInits()
1362 const OffsetRange &R = N->Range; in assignInits()
1373 // Build the assignment map: candidate C -> { list of extender indexes }. in assignInits()
1375 // - pick the candidate that covers the maximum number of extenders, in assignInits()
1376 // - add the candidate to the map, in assignInits()
1377 // - remove the extenders from the pool. in assignInits()
1381 for (auto It = CandSet.begin(), Et = CandSet.end(); It != Et; ) { in assignInits()
1383 unsigned N = std::accumulate(V.begin(), V.end(), 0u, in assignInits()
1385 return Acc + N->Count; in assignInits()
1399 int32_t Best = BestIt->first; in assignInits()
1402 for (unsigned I : RangeMap[N->Range]) in assignInits()
1411 // descriptor's subexpression is non-trivial: it can be the entire in assignInits()
1425 if (F == IMap.end()) in assignInits()
1431 // (to be used by frame index elimination), while non-stack expressions in assignInits()
1440 // 0. [-756,267]a1+0 in assignInits()
1441 // 1. [-756,267]a1+0 in assignInits()
1444 // [-756,267]a1+0 -> 0 1 in assignInits()
1445 // [201,65735]a1+0 -> 2 in assignInits()
1447 // [imm:0 off:267, ## + __ << 0] -> { 2 } in assignInits()
1448 // [imm:0 off:267, ## + SS#1 << 0] -> { 0 1 } in assignInits()
1451 // [imm:0 off:267, ## + __ << 0] -> { 2 0 1 } in assignInits()
1452 // [imm:0 off:267, ## + SS#1 << 0] -> { } in assignInits()
1464 bool IsStack = any_of(F->second, [this](unsigned I) { in assignInits()
1473 F->second.insert(P.second.begin(), P.second.end()); in assignInits()
1494 MachineBasicBlock *DomB = ED0.UseMI->getParent(); in calculatePlacement()
1499 MachineBasicBlock *MBB = ED.UseMI->getParent(); in calculatePlacement()
1501 DomB = MDT->findNearestCommonDominator(DomB, MBB); in calculatePlacement()
1509 const MachineInstr *DefI = Rs.isVReg() ? MRI->getVRegDef(Rs.Reg) : nullptr; in calculatePlacement()
1513 assert(!DefI || MDT->dominates(DefI->getParent(), DomB)); in calculatePlacement()
1519 MachineBasicBlock::iterator End = DomB->end(); in calculatePlacement() local
1520 for (It = DomB->begin(); It != End; ++It) in calculatePlacement()
1523 assert(It != End && "Should have found a ref in DomB"); in calculatePlacement()
1526 It = DomB->getFirstTerminator(); in calculatePlacement()
1533 llvm::Register DefR = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass); in insertInitializer()
1536 DebugLoc dl = DefL.Block->findDebugLoc(DefL.At); in insertInitializer()
1547 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::PS_fi), DefR) in insertInitializer()
1554 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_tfrsi), DefR) in insertInitializer()
1559 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_subri), DefR) in insertInitializer()
1564 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_addi), DefR) in insertInitializer()
1569 if (HST->useCompound()) { in insertInitializer()
1573 InitI = BuildMI(MBB, At, dl, HII->get(NewOpc), DefR) in insertInitializer()
1581 llvm::Register TmpR = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass); in insertInitializer()
1582 BuildMI(MBB, At, dl, HII->get(Hexagon::S2_asl_i_r), TmpR) in insertInitializer()
1586 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_subri), DefR) in insertInitializer()
1590 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_addi), DefR) in insertInitializer()
1620 BuildMI(MBB, At, dl, HII->get(RegOpc)) in replaceInstrExact()
1627 BuildMI(MBB, At, dl, HII->get(RegOpc)) in replaceInstrExact()
1641 BuildMI(MBB, At, dl, HII->get(NewOpc)) in replaceInstrExact()
1650 MachineInstrBuilder MIB = BuildMI(MBB, At, dl, HII->get(RegOpc)); in replaceInstrExact()
1670 // BaseImmOffset (io) -> BaseRegOffset (rr) in replaceInstrExact()
1671 // BaseLongOffset (ur) -> BaseRegOffset (rr) in replaceInstrExact()
1673 unsigned AM = HII->getAddrMode(MI); in replaceInstrExact()
1675 RegOpc = HII->changeAddrMode_io_rr(ExtOpc); in replaceInstrExact()
1680 RegOpc = HII->changeAddrMode_ur_rr(ExtOpc); in replaceInstrExact()
1686 if (RegOpc == -1u) { in replaceInstrExact()
1687 dbgs() << "\nExtOpc: " << HII->getName(ExtOpc) << " has no rr version\n"; in replaceInstrExact()
1693 HII->getBaseAndOffsetPosition(MI, BaseP, OffP); in replaceInstrExact()
1696 MachineInstrBuilder MIB = BuildMI(MBB, At, dl, HII->get(RegOpc)); in replaceInstrExact()
1701 if (HII->isPredicated(MI)) in replaceInstrExact()
1735 // the addi's 16-bit argument was included, so now we need to make it such in replaceInstrExpr()
1738 // result, but if Diff is outside of the 16-bit range, some adjustment in replaceInstrExpr()
1744 int32_t D = isInt<16>(Diff) ? Diff : (Diff > 0 ? 32767 : -32768); in replaceInstrExpr()
1752 D &= ~(A-1); in replaceInstrExpr()
1754 BuildMI(MBB, At, dl, HII->get(IdxOpc)) in replaceInstrExpr()
1758 Diff -= D; in replaceInstrExpr()
1761 // "Diff" is a difference in the "opposite direction", i.e. Ext - DefV, in replaceInstrExpr()
1762 // not DefV - Ext, as the getOffsetRange would calculate. in replaceInstrExpr()
1764 if (!Uses.contains(-Diff)) in replaceInstrExpr()
1765 dbgs() << "Diff: " << -Diff << " out of range " << Uses in replaceInstrExpr()
1767 assert(Uses.contains(-Diff)); in replaceInstrExpr()
1787 BuildMI(MBB, At, dl, HII->get(TargetOpcode::COPY)) in replaceInstrExpr()
1811 BuildMI(MBB, At, dl, HII->get(NewOpc)) in replaceInstrExpr()
1822 MachineInstrBuilder MIB = BuildMI(MBB, At, dl, HII->get(IdxOpc)); in replaceInstrExpr()
1828 if (HII->isPredicated(MI)) in replaceInstrExpr()
1861 int32_t Diff = EV.Offset - DefV.Offset; in replaceInstr()
1870 unsigned AM = HII->getAddrMode(MI); in replaceInstr()
1881 for (MachineOperand &Op : MRI->use_operands(ED.Rd.Reg)) { in replaceInstr()
1898 assert(P.first->getNumOperands() > J+1 && in replaceInstr()
1899 P.first->getOperand(J+1).isImm()); in replaceInstr()
1900 MachineOperand &ImmOp = P.first->getOperand(J+1); in replaceInstr()
1903 // If it was an absolute-set instruction, the "set" part has been removed. in replaceInstr()
1909 MRI->replaceRegWith(ED.Rd.Reg, ExtR.Reg); in replaceInstr()
1946 assert(HII->isPredicated(MI)); in getPredicateOp()
1949 MRI->getRegClass(Op.getReg()) != &Hexagon::PredRegsRegClass) in getPredicateOp()
1964 return MI.getOperand(MI.getNumExplicitOperands()-1); in getStoredValueOp()
1978 HII = HST->getInstrInfo(); in runOnMachineFunction()
1979 HRI = HST->getRegisterInfo(); in runOnMachineFunction()
1996 const MachineBasicBlock *BA = MA->getParent(); in runOnMachineFunction()
1997 const MachineBasicBlock *BB = MB->getParent(); in runOnMachineFunction()
1998 assert(BA->getNumber() != -1 && BB->getNumber() != -1); in runOnMachineFunction()
2000 return BA->getNumber() < BB->getNumber(); in runOnMachineFunction()
2001 return MDT->dominates(MA, MB); in runOnMachineFunction()