1 //===-- HexagonISelDAGToDAG.cpp - A dag to dag inst selector for Hexagon --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines an instruction selector for the Hexagon target.
12 //===----------------------------------------------------------------------===//
15 #include "HexagonISelLowering.h"
16 #include "HexagonMachineFunctionInfo.h"
17 #include "HexagonTargetMachine.h"
18 #include "llvm/CodeGen/FunctionLoweringInfo.h"
19 #include "llvm/CodeGen/MachineInstrBuilder.h"
20 #include "llvm/CodeGen/SelectionDAGISel.h"
21 #include "llvm/IR/Intrinsics.h"
22 #include "llvm/Support/CommandLine.h"
23 #include "llvm/Support/Debug.h"
26 #define DEBUG_TYPE "hexagon-isel"
30 EnableAddressRebalancing("isel-rebalance-addr", cl::Hidden, cl::init(true),
31 cl::desc("Rebalance address calculation trees to improve "
32 "instruction selection"));
34 // Rebalance only if this allows e.g. combining a GA with an offset or
35 // factoring out a shift.
38 RebalanceOnlyForOptimizations("rebalance-only-opt", cl::Hidden, cl::init(false),
39 cl::desc("Rebalance address tree only if this allows optimizations"));
43 RebalanceOnlyImbalancedTrees("rebalance-only-imbal", cl::Hidden,
44 cl::init(false), cl::desc("Rebalance address tree only if it is imbalanced"));
46 //===----------------------------------------------------------------------===//
47 // Instruction Selector Implementation
48 //===----------------------------------------------------------------------===//
50 //===--------------------------------------------------------------------===//
51 /// HexagonDAGToDAGISel - Hexagon specific code to select Hexagon machine
52 /// instructions for SelectionDAG operations.
55 class HexagonDAGToDAGISel : public SelectionDAGISel {
56 const HexagonSubtarget *HST;
57 const HexagonInstrInfo *HII;
58 const HexagonRegisterInfo *HRI;
60 explicit HexagonDAGToDAGISel(HexagonTargetMachine &tm,
61 CodeGenOpt::Level OptLevel)
62 : SelectionDAGISel(tm, OptLevel), HST(nullptr), HII(nullptr),
65 bool runOnMachineFunction(MachineFunction &MF) override {
66 // Reset the subtarget each time through.
67 HST = &MF.getSubtarget<HexagonSubtarget>();
68 HII = HST->getInstrInfo();
69 HRI = HST->getRegisterInfo();
70 SelectionDAGISel::runOnMachineFunction(MF);
74 void PreprocessISelDAG() override;
75 void EmitFunctionEntryCode() override;
77 void Select(SDNode *N) override;
79 // Complex Pattern Selectors.
80 inline bool SelectAddrGA(SDValue &N, SDValue &R);
81 inline bool SelectAddrGP(SDValue &N, SDValue &R);
82 bool SelectGlobalAddress(SDValue &N, SDValue &R, bool UseGP);
83 bool SelectAddrFI(SDValue &N, SDValue &R);
85 StringRef getPassName() const override {
86 return "Hexagon DAG->DAG Pattern Instruction Selection";
89 // Generate a machine instruction node corresponding to the circ/brev
91 MachineSDNode *LoadInstrForLoadIntrinsic(SDNode *IntN);
92 // Given the circ/brev load intrinsic and the already generated machine
93 // instruction, generate the appropriate store (that is a part of the
94 // intrinsic's functionality).
95 SDNode *StoreInstrForLoadIntrinsic(MachineSDNode *LoadN, SDNode *IntN);
97 void SelectFrameIndex(SDNode *N);
98 /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
99 /// inline asm expressions.
100 bool SelectInlineAsmMemoryOperand(const SDValue &Op,
101 unsigned ConstraintID,
102 std::vector<SDValue> &OutOps) override;
103 bool tryLoadOfLoadIntrinsic(LoadSDNode *N);
104 void SelectLoad(SDNode *N);
105 void SelectIndexedLoad(LoadSDNode *LD, const SDLoc &dl);
106 void SelectIndexedStore(StoreSDNode *ST, const SDLoc &dl);
107 void SelectStore(SDNode *N);
108 void SelectSHL(SDNode *N);
109 void SelectMul(SDNode *N);
110 void SelectZeroExtend(SDNode *N);
111 void SelectIntrinsicWChain(SDNode *N);
112 void SelectIntrinsicWOChain(SDNode *N);
113 void SelectConstant(SDNode *N);
114 void SelectConstantFP(SDNode *N);
115 void SelectBitcast(SDNode *N);
117 // Include the pieces autogenerated from the target description.
118 #include "HexagonGenDAGISel.inc"
121 bool isValueExtension(const SDValue &Val, unsigned FromBits, SDValue &Src);
122 bool isOrEquivalentToAdd(const SDNode *N) const;
123 bool isAlignedMemNode(const MemSDNode *N) const;
124 bool isPositiveHalfWord(const SDNode *N) const;
126 SmallDenseMap<SDNode *,int> RootWeights;
127 SmallDenseMap<SDNode *,int> RootHeights;
128 SmallDenseMap<const Value *,int> GAUsesInFunction;
129 int getWeight(SDNode *N);
130 int getHeight(SDNode *N);
131 SDValue getMultiplierForSHL(SDNode *N);
132 SDValue factorOutPowerOf2(SDValue V, unsigned Power);
133 unsigned getUsesInFunction(const Value *V);
134 SDValue balanceSubTree(SDNode *N, bool Factorize = false);
135 void rebalanceAddressTrees();
136 }; // end HexagonDAGToDAGISel
137 } // end anonymous namespace
140 /// createHexagonISelDag - This pass converts a legalized DAG into a
141 /// Hexagon-specific DAG, ready for instruction scheduling.
144 FunctionPass *createHexagonISelDag(HexagonTargetMachine &TM,
145 CodeGenOpt::Level OptLevel) {
146 return new HexagonDAGToDAGISel(TM, OptLevel);
150 // Intrinsics that return a a predicate.
151 static bool doesIntrinsicReturnPredicate(unsigned ID) {
155 case Intrinsic::hexagon_C2_cmpeq:
156 case Intrinsic::hexagon_C2_cmpgt:
157 case Intrinsic::hexagon_C2_cmpgtu:
158 case Intrinsic::hexagon_C2_cmpgtup:
159 case Intrinsic::hexagon_C2_cmpgtp:
160 case Intrinsic::hexagon_C2_cmpeqp:
161 case Intrinsic::hexagon_C2_bitsset:
162 case Intrinsic::hexagon_C2_bitsclr:
163 case Intrinsic::hexagon_C2_cmpeqi:
164 case Intrinsic::hexagon_C2_cmpgti:
165 case Intrinsic::hexagon_C2_cmpgtui:
166 case Intrinsic::hexagon_C2_cmpgei:
167 case Intrinsic::hexagon_C2_cmpgeui:
168 case Intrinsic::hexagon_C2_cmplt:
169 case Intrinsic::hexagon_C2_cmpltu:
170 case Intrinsic::hexagon_C2_bitsclri:
171 case Intrinsic::hexagon_C2_and:
172 case Intrinsic::hexagon_C2_or:
173 case Intrinsic::hexagon_C2_xor:
174 case Intrinsic::hexagon_C2_andn:
175 case Intrinsic::hexagon_C2_not:
176 case Intrinsic::hexagon_C2_orn:
177 case Intrinsic::hexagon_C2_pxfer_map:
178 case Intrinsic::hexagon_C2_any8:
179 case Intrinsic::hexagon_C2_all8:
180 case Intrinsic::hexagon_A2_vcmpbeq:
181 case Intrinsic::hexagon_A2_vcmpbgtu:
182 case Intrinsic::hexagon_A2_vcmpheq:
183 case Intrinsic::hexagon_A2_vcmphgt:
184 case Intrinsic::hexagon_A2_vcmphgtu:
185 case Intrinsic::hexagon_A2_vcmpweq:
186 case Intrinsic::hexagon_A2_vcmpwgt:
187 case Intrinsic::hexagon_A2_vcmpwgtu:
188 case Intrinsic::hexagon_C2_tfrrp:
189 case Intrinsic::hexagon_S2_tstbit_i:
190 case Intrinsic::hexagon_S2_tstbit_r:
195 void HexagonDAGToDAGISel::SelectIndexedLoad(LoadSDNode *LD, const SDLoc &dl) {
196 SDValue Chain = LD->getChain();
197 SDValue Base = LD->getBasePtr();
198 SDValue Offset = LD->getOffset();
199 int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
200 EVT LoadedVT = LD->getMemoryVT();
203 // Check for zero extended loads. Treat any-extend loads as zero extended
205 ISD::LoadExtType ExtType = LD->getExtensionType();
206 bool IsZeroExt = (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD);
207 bool IsValidInc = HII->isValidAutoIncImm(LoadedVT, Inc);
209 assert(LoadedVT.isSimple());
210 switch (LoadedVT.getSimpleVT().SimpleTy) {
213 Opcode = IsValidInc ? Hexagon::L2_loadrub_pi : Hexagon::L2_loadrub_io;
215 Opcode = IsValidInc ? Hexagon::L2_loadrb_pi : Hexagon::L2_loadrb_io;
219 Opcode = IsValidInc ? Hexagon::L2_loadruh_pi : Hexagon::L2_loadruh_io;
221 Opcode = IsValidInc ? Hexagon::L2_loadrh_pi : Hexagon::L2_loadrh_io;
224 Opcode = IsValidInc ? Hexagon::L2_loadri_pi : Hexagon::L2_loadri_io;
227 Opcode = IsValidInc ? Hexagon::L2_loadrd_pi : Hexagon::L2_loadrd_io;
234 if (isAlignedMemNode(LD))
235 Opcode = IsValidInc ? Hexagon::V6_vL32b_pi : Hexagon::V6_vL32b_ai;
237 Opcode = IsValidInc ? Hexagon::V6_vL32Ub_pi : Hexagon::V6_vL32Ub_ai;
244 if (isAlignedMemNode(LD))
245 Opcode = IsValidInc ? Hexagon::V6_vL32b_pi_128B
246 : Hexagon::V6_vL32b_ai_128B;
248 Opcode = IsValidInc ? Hexagon::V6_vL32Ub_pi_128B
249 : Hexagon::V6_vL32Ub_ai_128B;
252 llvm_unreachable("Unexpected memory type in indexed load");
255 SDValue IncV = CurDAG->getTargetConstant(Inc, dl, MVT::i32);
256 MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
257 MemOp[0] = LD->getMemOperand();
259 auto getExt64 = [this,ExtType] (MachineSDNode *N, const SDLoc &dl)
261 if (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD) {
262 SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
263 return CurDAG->getMachineNode(Hexagon::A4_combineir, dl, MVT::i64,
264 Zero, SDValue(N, 0));
266 if (ExtType == ISD::SEXTLOAD)
267 return CurDAG->getMachineNode(Hexagon::A2_sxtw, dl, MVT::i64,
272 // Loaded value Next address Chain
273 SDValue From[3] = { SDValue(LD,0), SDValue(LD,1), SDValue(LD,2) };
276 EVT ValueVT = LD->getValueType(0);
277 if (ValueVT == MVT::i64 && ExtType != ISD::NON_EXTLOAD) {
278 // A load extending to i64 will actually produce i32, which will then
279 // need to be extended to i64.
280 assert(LoadedVT.getSizeInBits() <= 32);
285 MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT,
286 MVT::i32, MVT::Other, Base,
288 L->setMemRefs(MemOp, MemOp+1);
289 To[1] = SDValue(L, 1); // Next address.
290 To[2] = SDValue(L, 2); // Chain.
291 // Handle special case for extension to i64.
292 if (LD->getValueType(0) == MVT::i64)
294 To[0] = SDValue(L, 0); // Loaded (extended) value.
296 SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
297 MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT, MVT::Other,
299 L->setMemRefs(MemOp, MemOp+1);
300 To[2] = SDValue(L, 1); // Chain.
301 MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,
303 To[1] = SDValue(A, 0); // Next address.
304 // Handle special case for extension to i64.
305 if (LD->getValueType(0) == MVT::i64)
307 To[0] = SDValue(L, 0); // Loaded (extended) value.
309 ReplaceUses(From, To, 3);
310 CurDAG->RemoveDeadNode(LD);
314 MachineSDNode *HexagonDAGToDAGISel::LoadInstrForLoadIntrinsic(SDNode *IntN) {
315 if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
319 unsigned IntNo = cast<ConstantSDNode>(IntN->getOperand(1))->getZExtValue();
321 static std::map<unsigned,unsigned> LoadPciMap = {
322 { Intrinsic::hexagon_circ_ldb, Hexagon::L2_loadrb_pci },
323 { Intrinsic::hexagon_circ_ldub, Hexagon::L2_loadrub_pci },
324 { Intrinsic::hexagon_circ_ldh, Hexagon::L2_loadrh_pci },
325 { Intrinsic::hexagon_circ_lduh, Hexagon::L2_loadruh_pci },
326 { Intrinsic::hexagon_circ_ldw, Hexagon::L2_loadri_pci },
327 { Intrinsic::hexagon_circ_ldd, Hexagon::L2_loadrd_pci },
329 auto FLC = LoadPciMap.find(IntNo);
330 if (FLC != LoadPciMap.end()) {
331 SDNode *Mod = CurDAG->getMachineNode(Hexagon::A2_tfrrcr, dl, MVT::i32,
332 IntN->getOperand(4));
333 EVT ValTy = (IntNo == Intrinsic::hexagon_circ_ldd) ? MVT::i64 : MVT::i32;
334 EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
335 // Operands: { Base, Increment, Modifier, Chain }
336 auto Inc = cast<ConstantSDNode>(IntN->getOperand(5));
337 SDValue I = CurDAG->getTargetConstant(Inc->getSExtValue(), dl, MVT::i32);
338 MachineSDNode *Res = CurDAG->getMachineNode(FLC->second, dl, RTys,
339 { IntN->getOperand(2), I, SDValue(Mod,0), IntN->getOperand(0) });
343 static std::map<unsigned,unsigned> LoadPbrMap = {
344 { Intrinsic::hexagon_brev_ldb, Hexagon::L2_loadrb_pbr },
345 { Intrinsic::hexagon_brev_ldub, Hexagon::L2_loadrub_pbr },
346 { Intrinsic::hexagon_brev_ldh, Hexagon::L2_loadrh_pbr },
347 { Intrinsic::hexagon_brev_lduh, Hexagon::L2_loadruh_pbr },
348 { Intrinsic::hexagon_brev_ldw, Hexagon::L2_loadri_pbr },
349 { Intrinsic::hexagon_brev_ldd, Hexagon::L2_loadrd_pbr },
351 auto FLB = LoadPbrMap.find(IntNo);
352 if (FLB != LoadPbrMap.end()) {
353 SDNode *Mod = CurDAG->getMachineNode(Hexagon::A2_tfrrcr, dl, MVT::i32,
354 IntN->getOperand(4));
355 EVT ValTy = (IntNo == Intrinsic::hexagon_brev_ldd) ? MVT::i64 : MVT::i32;
356 EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
357 // Operands: { Base, Modifier, Chain }
358 MachineSDNode *Res = CurDAG->getMachineNode(FLB->second, dl, RTys,
359 { IntN->getOperand(2), SDValue(Mod,0), IntN->getOperand(0) });
366 SDNode *HexagonDAGToDAGISel::StoreInstrForLoadIntrinsic(MachineSDNode *LoadN,
368 // The "LoadN" is just a machine load instruction. The intrinsic also
369 // involves storing it. Generate an appropriate store to the location
370 // given in the intrinsic's operand(3).
371 uint64_t F = HII->get(LoadN->getMachineOpcode()).TSFlags;
372 unsigned SizeBits = (F >> HexagonII::MemAccessSizePos) &
373 HexagonII::MemAccesSizeMask;
374 unsigned Size = 1U << (SizeBits-1);
377 MachinePointerInfo PI;
379 SDValue Loc = IntN->getOperand(3);
382 TS = CurDAG->getStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc, PI,
385 TS = CurDAG->getTruncStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc,
386 PI, MVT::getIntegerVT(Size * 8), Size);
390 HandleSDNode Handle(TS);
391 SelectStore(TS.getNode());
392 StoreN = Handle.getValue().getNode();
395 // Load's results are { Loaded value, Updated pointer, Chain }
396 ReplaceUses(SDValue(IntN, 0), SDValue(LoadN, 1));
397 ReplaceUses(SDValue(IntN, 1), SDValue(StoreN, 0));
401 bool HexagonDAGToDAGISel::tryLoadOfLoadIntrinsic(LoadSDNode *N) {
402 // The intrinsics for load circ/brev perform two operations:
403 // 1. Load a value V from the specified location, using the addressing
404 // mode corresponding to the intrinsic.
405 // 2. Store V into a specified location. This location is typically a
406 // local, temporary object.
407 // In many cases, the program using these intrinsics will immediately
408 // load V again from the local object. In those cases, when certain
409 // conditions are met, the last load can be removed.
410 // This function identifies and optimizes this pattern. If the pattern
411 // cannot be optimized, it returns nullptr, which will cause the load
412 // to be selected separately from the intrinsic (which will be handled
413 // in SelectIntrinsicWChain).
415 SDValue Ch = N->getOperand(0);
416 SDValue Loc = N->getOperand(1);
418 // Assume that the load and the intrinsic are connected directly with a
420 // t1: i32,ch = int.load ..., ..., ..., Loc, ... // <-- C
421 // t2: i32,ch = load t1:1, Loc, ...
422 SDNode *C = Ch.getNode();
424 if (C->getOpcode() != ISD::INTRINSIC_W_CHAIN)
427 // The second load can only be eliminated if its extension type matches
428 // that of the load instruction corresponding to the intrinsic. The user
429 // can provide an address of an unsigned variable to store the result of
430 // a sign-extending intrinsic into (or the other way around).
431 ISD::LoadExtType IntExt;
432 switch (cast<ConstantSDNode>(C->getOperand(1))->getZExtValue()) {
433 case Intrinsic::hexagon_brev_ldub:
434 case Intrinsic::hexagon_brev_lduh:
435 case Intrinsic::hexagon_circ_ldub:
436 case Intrinsic::hexagon_circ_lduh:
437 IntExt = ISD::ZEXTLOAD;
439 case Intrinsic::hexagon_brev_ldw:
440 case Intrinsic::hexagon_brev_ldd:
441 case Intrinsic::hexagon_circ_ldw:
442 case Intrinsic::hexagon_circ_ldd:
443 IntExt = ISD::NON_EXTLOAD;
446 IntExt = ISD::SEXTLOAD;
449 if (N->getExtensionType() != IntExt)
452 // Make sure the target location for the loaded value in the load intrinsic
453 // is the location from which LD (or N) is loading.
454 if (C->getNumOperands() < 4 || Loc.getNode() != C->getOperand(3).getNode())
457 if (MachineSDNode *L = LoadInstrForLoadIntrinsic(C)) {
458 SDNode *S = StoreInstrForLoadIntrinsic(L, C);
459 SDValue F[] = { SDValue(N,0), SDValue(N,1), SDValue(C,0), SDValue(C,1) };
460 SDValue T[] = { SDValue(L,0), SDValue(S,0), SDValue(L,1), SDValue(S,0) };
461 ReplaceUses(F, T, array_lengthof(T));
462 // This transformation will leave the intrinsic dead. If it remains in
463 // the DAG, the selection code will see it again, but without the load,
464 // and it will generate a store that is normally required for it.
465 CurDAG->RemoveDeadNode(C);
472 void HexagonDAGToDAGISel::SelectLoad(SDNode *N) {
474 LoadSDNode *LD = cast<LoadSDNode>(N);
475 ISD::MemIndexedMode AM = LD->getAddressingMode();
477 // Handle indexed loads.
478 if (AM != ISD::UNINDEXED) {
479 SelectIndexedLoad(LD, dl);
483 // Handle patterns using circ/brev load intrinsics.
484 if (tryLoadOfLoadIntrinsic(LD))
490 void HexagonDAGToDAGISel::SelectIndexedStore(StoreSDNode *ST, const SDLoc &dl) {
491 SDValue Chain = ST->getChain();
492 SDValue Base = ST->getBasePtr();
493 SDValue Offset = ST->getOffset();
494 SDValue Value = ST->getValue();
495 // Get the constant value.
496 int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
497 EVT StoredVT = ST->getMemoryVT();
498 EVT ValueVT = Value.getValueType();
500 bool IsValidInc = HII->isValidAutoIncImm(StoredVT, Inc);
503 assert(StoredVT.isSimple());
504 switch (StoredVT.getSimpleVT().SimpleTy) {
506 Opcode = IsValidInc ? Hexagon::S2_storerb_pi : Hexagon::S2_storerb_io;
509 Opcode = IsValidInc ? Hexagon::S2_storerh_pi : Hexagon::S2_storerh_io;
512 Opcode = IsValidInc ? Hexagon::S2_storeri_pi : Hexagon::S2_storeri_io;
515 Opcode = IsValidInc ? Hexagon::S2_storerd_pi : Hexagon::S2_storerd_io;
522 if (isAlignedMemNode(ST))
523 Opcode = IsValidInc ? Hexagon::V6_vS32b_pi : Hexagon::V6_vS32b_ai;
525 Opcode = IsValidInc ? Hexagon::V6_vS32Ub_pi : Hexagon::V6_vS32Ub_ai;
532 if (isAlignedMemNode(ST))
533 Opcode = IsValidInc ? Hexagon::V6_vS32b_pi_128B
534 : Hexagon::V6_vS32b_ai_128B;
536 Opcode = IsValidInc ? Hexagon::V6_vS32Ub_pi_128B
537 : Hexagon::V6_vS32Ub_ai_128B;
540 llvm_unreachable("Unexpected memory type in indexed store");
543 if (ST->isTruncatingStore() && ValueVT.getSizeInBits() == 64) {
544 assert(StoredVT.getSizeInBits() < 64 && "Not a truncating store");
545 Value = CurDAG->getTargetExtractSubreg(Hexagon::isub_lo,
546 dl, MVT::i32, Value);
549 SDValue IncV = CurDAG->getTargetConstant(Inc, dl, MVT::i32);
550 MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
551 MemOp[0] = ST->getMemOperand();
553 // Next address Chain
554 SDValue From[2] = { SDValue(ST,0), SDValue(ST,1) };
558 // Build post increment store.
559 SDValue Ops[] = { Base, IncV, Value, Chain };
560 MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::i32, MVT::Other,
562 S->setMemRefs(MemOp, MemOp + 1);
563 To[0] = SDValue(S, 0);
564 To[1] = SDValue(S, 1);
566 SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
567 SDValue Ops[] = { Base, Zero, Value, Chain };
568 MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::Other, Ops);
569 S->setMemRefs(MemOp, MemOp + 1);
570 To[1] = SDValue(S, 0);
571 MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,
573 To[0] = SDValue(A, 0);
576 ReplaceUses(From, To, 2);
577 CurDAG->RemoveDeadNode(ST);
580 void HexagonDAGToDAGISel::SelectStore(SDNode *N) {
582 StoreSDNode *ST = cast<StoreSDNode>(N);
583 ISD::MemIndexedMode AM = ST->getAddressingMode();
585 // Handle indexed stores.
586 if (AM != ISD::UNINDEXED) {
587 SelectIndexedStore(ST, dl);
594 void HexagonDAGToDAGISel::SelectMul(SDNode *N) {
597 // %conv.i = sext i32 %tmp1 to i64
598 // %conv2.i = sext i32 %add to i64
599 // %mul.i = mul nsw i64 %conv2.i, %conv.i
601 // --- match with the following ---
603 // %mul.i = mpy (%tmp1, %add)
606 if (N->getValueType(0) == MVT::i64) {
607 // Shifting a i64 signed multiply.
608 SDValue MulOp0 = N->getOperand(0);
609 SDValue MulOp1 = N->getOperand(1);
614 // Handle sign_extend and sextload.
615 if (MulOp0.getOpcode() == ISD::SIGN_EXTEND) {
616 SDValue Sext0 = MulOp0.getOperand(0);
617 if (Sext0.getNode()->getValueType(0) != MVT::i32) {
622 } else if (MulOp0.getOpcode() == ISD::LOAD) {
623 LoadSDNode *LD = cast<LoadSDNode>(MulOp0.getNode());
624 if (LD->getMemoryVT() != MVT::i32 ||
625 LD->getExtensionType() != ISD::SEXTLOAD ||
626 LD->getAddressingMode() != ISD::UNINDEXED) {
630 SDValue Chain = LD->getChain();
631 SDValue TargetConst0 = CurDAG->getTargetConstant(0, dl, MVT::i32);
632 OP0 = SDValue(CurDAG->getMachineNode(Hexagon::L2_loadri_io, dl, MVT::i32,
634 LD->getBasePtr(), TargetConst0,
641 // Same goes for the second operand.
642 if (MulOp1.getOpcode() == ISD::SIGN_EXTEND) {
643 SDValue Sext1 = MulOp1.getOperand(0);
644 if (Sext1.getNode()->getValueType(0) != MVT::i32) {
649 } else if (MulOp1.getOpcode() == ISD::LOAD) {
650 LoadSDNode *LD = cast<LoadSDNode>(MulOp1.getNode());
651 if (LD->getMemoryVT() != MVT::i32 ||
652 LD->getExtensionType() != ISD::SEXTLOAD ||
653 LD->getAddressingMode() != ISD::UNINDEXED) {
657 SDValue Chain = LD->getChain();
658 SDValue TargetConst0 = CurDAG->getTargetConstant(0, dl, MVT::i32);
659 OP1 = SDValue(CurDAG->getMachineNode(Hexagon::L2_loadri_io, dl, MVT::i32,
661 LD->getBasePtr(), TargetConst0,
668 // Generate a mpy instruction.
669 SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_dpmpyss_s0, dl,
671 ReplaceNode(N, Result);
678 void HexagonDAGToDAGISel::SelectSHL(SDNode *N) {
680 SDValue Shl_0 = N->getOperand(0);
681 SDValue Shl_1 = N->getOperand(1);
683 auto Default = [this,N] () -> void { SelectCode(N); };
685 if (N->getValueType(0) != MVT::i32 || Shl_1.getOpcode() != ISD::Constant)
689 int32_t ShlConst = cast<ConstantSDNode>(Shl_1)->getSExtValue();
691 if (Shl_0.getOpcode() == ISD::MUL) {
692 SDValue Mul_0 = Shl_0.getOperand(0); // Val
693 SDValue Mul_1 = Shl_0.getOperand(1); // Const
694 // RHS of mul is const.
695 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Mul_1)) {
696 int32_t ValConst = C->getSExtValue() << ShlConst;
697 if (isInt<9>(ValConst)) {
698 SDValue Val = CurDAG->getTargetConstant(ValConst, dl, MVT::i32);
699 SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,
700 MVT::i32, Mul_0, Val);
701 ReplaceNode(N, Result);
708 if (Shl_0.getOpcode() == ISD::SUB) {
709 SDValue Sub_0 = Shl_0.getOperand(0); // Const 0
710 SDValue Sub_1 = Shl_0.getOperand(1); // Val
711 if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Sub_0)) {
712 if (C1->getSExtValue() != 0 || Sub_1.getOpcode() != ISD::SHL)
714 SDValue Shl2_0 = Sub_1.getOperand(0); // Val
715 SDValue Shl2_1 = Sub_1.getOperand(1); // Const
716 if (ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(Shl2_1)) {
717 int32_t ValConst = 1 << (ShlConst + C2->getSExtValue());
718 if (isInt<9>(-ValConst)) {
719 SDValue Val = CurDAG->getTargetConstant(-ValConst, dl, MVT::i32);
720 SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,
721 MVT::i32, Shl2_0, Val);
722 ReplaceNode(N, Result);
734 // If there is an zero_extend followed an intrinsic in DAG (this means - the
735 // result of the intrinsic is predicate); convert the zero_extend to
736 // transfer instruction.
738 // Zero extend -> transfer is lowered here. Otherwise, zero_extend will be
739 // converted into a MUX as predicate registers defined as 1 bit in the
740 // compiler. Architecture defines them as 8-bit registers.
741 // We want to preserve all the lower 8-bits and, not just 1 LSB bit.
743 void HexagonDAGToDAGISel::SelectZeroExtend(SDNode *N) {
746 SDValue Op0 = N->getOperand(0);
747 EVT OpVT = Op0.getValueType();
748 unsigned OpBW = OpVT.getSizeInBits();
750 // Special handling for zero-extending a vector of booleans.
751 if (OpVT.isVector() && OpVT.getVectorElementType() == MVT::i1 && OpBW <= 64) {
752 SDNode *Mask = CurDAG->getMachineNode(Hexagon::C2_mask, dl, MVT::i64, Op0);
753 unsigned NE = OpVT.getVectorNumElements();
754 EVT ExVT = N->getValueType(0);
755 unsigned ES = ExVT.getScalarSizeInBits();
756 uint64_t MV = 0, Bit = 1;
757 for (unsigned i = 0; i < NE; ++i) {
761 SDValue Ones = CurDAG->getTargetConstant(MV, dl, MVT::i64);
762 SDNode *OnesReg = CurDAG->getMachineNode(Hexagon::CONST64, dl,
764 if (ExVT.getSizeInBits() == 32) {
765 SDNode *And = CurDAG->getMachineNode(Hexagon::A2_andp, dl, MVT::i64,
766 SDValue(Mask,0), SDValue(OnesReg,0));
767 SDValue SubR = CurDAG->getTargetConstant(Hexagon::isub_lo, dl, MVT::i32);
768 ReplaceNode(N, CurDAG->getMachineNode(Hexagon::EXTRACT_SUBREG, dl, ExVT,
769 SDValue(And, 0), SubR));
773 CurDAG->getMachineNode(Hexagon::A2_andp, dl, ExVT,
774 SDValue(Mask, 0), SDValue(OnesReg, 0)));
778 SDNode *Int = N->getOperand(0).getNode();
779 if ((Int->getOpcode() == ISD::INTRINSIC_WO_CHAIN)) {
780 unsigned ID = cast<ConstantSDNode>(Int->getOperand(0))->getZExtValue();
781 if (doesIntrinsicReturnPredicate(ID)) {
782 // Now we need to differentiate target data types.
783 if (N->getValueType(0) == MVT::i64) {
784 // Convert the zero_extend to Rs = Pd followed by A2_combinew(0,Rs).
785 SDValue TargetConst0 = CurDAG->getTargetConstant(0, dl, MVT::i32);
786 SDNode *Result_1 = CurDAG->getMachineNode(Hexagon::C2_tfrpr, dl,
787 MVT::i32, SDValue(Int, 0));
788 SDNode *Result_2 = CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl,
789 MVT::i32, TargetConst0);
790 SDNode *Result_3 = CurDAG->getMachineNode(Hexagon::A2_combinew, dl,
791 MVT::i64, MVT::Other,
792 SDValue(Result_2, 0),
793 SDValue(Result_1, 0));
794 ReplaceNode(N, Result_3);
797 if (N->getValueType(0) == MVT::i32) {
798 // Convert the zero_extend to Rs = Pd
799 SDNode* RsPd = CurDAG->getMachineNode(Hexagon::C2_tfrpr, dl,
800 MVT::i32, SDValue(Int, 0));
801 ReplaceNode(N, RsPd);
804 llvm_unreachable("Unexpected value type");
812 // Handling intrinsics for circular load and bitreverse load.
814 void HexagonDAGToDAGISel::SelectIntrinsicWChain(SDNode *N) {
815 if (MachineSDNode *L = LoadInstrForLoadIntrinsic(N)) {
816 StoreInstrForLoadIntrinsic(L, N);
817 CurDAG->RemoveDeadNode(N);
823 void HexagonDAGToDAGISel::SelectIntrinsicWOChain(SDNode *N) {
824 unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue();
827 case Intrinsic::hexagon_S2_vsplatrb:
830 case Intrinsic::hexagon_S2_vsplatrh:
838 SDValue V = N->getOperand(1);
840 if (isValueExtension(V, Bits, U)) {
841 SDValue R = CurDAG->getNode(N->getOpcode(), SDLoc(N), N->getValueType(0),
842 N->getOperand(0), U);
843 ReplaceNode(N, R.getNode());
844 SelectCode(R.getNode());
851 // Map floating point constant values.
853 void HexagonDAGToDAGISel::SelectConstantFP(SDNode *N) {
855 ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N);
856 APInt A = CN->getValueAPF().bitcastToAPInt();
857 if (N->getValueType(0) == MVT::f32) {
858 SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i32);
859 ReplaceNode(N, CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::f32, V));
862 if (N->getValueType(0) == MVT::f64) {
863 SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i64);
864 ReplaceNode(N, CurDAG->getMachineNode(Hexagon::CONST64, dl, MVT::f64, V));
872 // Map boolean values.
874 void HexagonDAGToDAGISel::SelectConstant(SDNode *N) {
875 if (N->getValueType(0) == MVT::i1) {
876 assert(!(cast<ConstantSDNode>(N)->getZExtValue() >> 1));
877 unsigned Opc = (cast<ConstantSDNode>(N)->getSExtValue() != 0)
880 ReplaceNode(N, CurDAG->getMachineNode(Opc, SDLoc(N), MVT::i1));
888 void HexagonDAGToDAGISel::SelectFrameIndex(SDNode *N) {
889 MachineFrameInfo &MFI = MF->getFrameInfo();
890 const HexagonFrameLowering *HFI = HST->getFrameLowering();
891 int FX = cast<FrameIndexSDNode>(N)->getIndex();
892 unsigned StkA = HFI->getStackAlignment();
893 unsigned MaxA = MFI.getMaxAlignment();
894 SDValue FI = CurDAG->getTargetFrameIndex(FX, MVT::i32);
896 SDValue Zero = CurDAG->getTargetConstant(0, DL, MVT::i32);
900 // - the object is fixed, or
901 // - there are no objects with higher-than-default alignment, or
902 // - there are no dynamically allocated objects.
903 // Otherwise, use PS_fia.
904 if (FX < 0 || MaxA <= StkA || !MFI.hasVarSizedObjects()) {
905 R = CurDAG->getMachineNode(Hexagon::PS_fi, DL, MVT::i32, FI, Zero);
907 auto &HMFI = *MF->getInfo<HexagonMachineFunctionInfo>();
908 unsigned AR = HMFI.getStackAlignBaseVReg();
909 SDValue CH = CurDAG->getEntryNode();
910 SDValue Ops[] = { CurDAG->getCopyFromReg(CH, DL, AR, MVT::i32), FI, Zero };
911 R = CurDAG->getMachineNode(Hexagon::PS_fia, DL, MVT::i32, Ops);
918 void HexagonDAGToDAGISel::SelectBitcast(SDNode *N) {
919 EVT SVT = N->getOperand(0).getValueType();
920 EVT DVT = N->getValueType(0);
921 if (!SVT.isVector() || !DVT.isVector() ||
922 SVT.getVectorElementType() == MVT::i1 ||
923 DVT.getVectorElementType() == MVT::i1 ||
924 SVT.getSizeInBits() != DVT.getSizeInBits()) {
929 CurDAG->ReplaceAllUsesOfValueWith(SDValue(N,0), N->getOperand(0));
930 CurDAG->RemoveDeadNode(N);
934 void HexagonDAGToDAGISel::Select(SDNode *N) {
935 if (N->isMachineOpcode()) {
937 return; // Already selected.
940 switch (N->getOpcode()) {
945 case ISD::ConstantFP:
949 case ISD::FrameIndex:
973 case ISD::ZERO_EXTEND:
977 case ISD::INTRINSIC_W_CHAIN:
978 SelectIntrinsicWChain(N);
981 case ISD::INTRINSIC_WO_CHAIN:
982 SelectIntrinsicWOChain(N);
989 bool HexagonDAGToDAGISel::
990 SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
991 std::vector<SDValue> &OutOps) {
992 SDValue Inp = Op, Res;
994 switch (ConstraintID) {
997 case InlineAsm::Constraint_i:
998 case InlineAsm::Constraint_o: // Offsetable.
999 case InlineAsm::Constraint_v: // Not offsetable.
1000 case InlineAsm::Constraint_m: // Memory.
1001 if (SelectAddrFI(Inp, Res))
1002 OutOps.push_back(Res);
1004 OutOps.push_back(Inp);
1008 OutOps.push_back(CurDAG->getTargetConstant(0, SDLoc(Op), MVT::i32));
1013 void HexagonDAGToDAGISel::PreprocessISelDAG() {
1014 SelectionDAG &DAG = *CurDAG;
1015 std::vector<SDNode*> Nodes;
1016 for (SDNode &Node : DAG.allnodes())
1017 Nodes.push_back(&Node);
1019 // Simplify: (or (select c x 0) z) -> (select c (or x z) z)
1020 // (or (select c 0 y) z) -> (select c z (or y z))
1021 // This may not be the right thing for all targets, so do it here.
1022 for (auto I : Nodes) {
1023 if (I->getOpcode() != ISD::OR)
1026 auto IsZero = [] (const SDValue &V) -> bool {
1027 if (ConstantSDNode *SC = dyn_cast<ConstantSDNode>(V.getNode()))
1028 return SC->isNullValue();
1031 auto IsSelect0 = [IsZero] (const SDValue &Op) -> bool {
1032 if (Op.getOpcode() != ISD::SELECT)
1034 return IsZero(Op.getOperand(1)) || IsZero(Op.getOperand(2));
1037 SDValue N0 = I->getOperand(0), N1 = I->getOperand(1);
1038 EVT VT = I->getValueType(0);
1039 bool SelN0 = IsSelect0(N0);
1040 SDValue SOp = SelN0 ? N0 : N1;
1041 SDValue VOp = SelN0 ? N1 : N0;
1043 if (SOp.getOpcode() == ISD::SELECT && SOp.getNode()->hasOneUse()) {
1044 SDValue SC = SOp.getOperand(0);
1045 SDValue SX = SOp.getOperand(1);
1046 SDValue SY = SOp.getOperand(2);
1049 SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SX, VOp);
1050 SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, NewOr, VOp);
1051 DAG.ReplaceAllUsesWith(I, NewSel.getNode());
1052 } else if (IsZero(SX)) {
1053 SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SY, VOp);
1054 SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, VOp, NewOr);
1055 DAG.ReplaceAllUsesWith(I, NewSel.getNode());
1060 // Transform: (store ch addr (add x (add (shl y c) e)))
1061 // to: (store ch addr (add x (shl (add y d) c))),
1062 // where e = (shl d c) for some integer d.
1063 // The purpose of this is to enable generation of loads/stores with
1064 // shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
1065 // value c must be 0, 1 or 2.
1066 for (auto I : Nodes) {
1067 if (I->getOpcode() != ISD::STORE)
1070 // I matched: (store ch addr Off)
1071 SDValue Off = I->getOperand(2);
1072 // Off needs to match: (add x (add (shl y c) (shl d c))))
1073 if (Off.getOpcode() != ISD::ADD)
1075 // Off matched: (add x T0)
1076 SDValue T0 = Off.getOperand(1);
1077 // T0 needs to match: (add T1 T2):
1078 if (T0.getOpcode() != ISD::ADD)
1080 // T0 matched: (add T1 T2)
1081 SDValue T1 = T0.getOperand(0);
1082 SDValue T2 = T0.getOperand(1);
1083 // T1 needs to match: (shl y c)
1084 if (T1.getOpcode() != ISD::SHL)
1086 SDValue C = T1.getOperand(1);
1087 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(C.getNode());
1090 unsigned CV = CN->getZExtValue();
1093 // T2 needs to match e, where e = (shl d c) for some d.
1094 ConstantSDNode *EN = dyn_cast<ConstantSDNode>(T2.getNode());
1097 unsigned EV = EN->getZExtValue();
1098 if (EV % (1 << CV) != 0)
1100 unsigned DV = EV / (1 << CV);
1102 // Replace T0 with: (shl (add y d) c)
1103 SDLoc DL = SDLoc(I);
1104 EVT VT = T0.getValueType();
1105 SDValue D = DAG.getConstant(DV, DL, VT);
1106 // NewAdd = (add y d)
1107 SDValue NewAdd = DAG.getNode(ISD::ADD, DL, VT, T1.getOperand(0), D);
1108 // NewShl = (shl NewAdd c)
1109 SDValue NewShl = DAG.getNode(ISD::SHL, DL, VT, NewAdd, C);
1110 ReplaceNode(T0.getNode(), NewShl.getNode());
1113 if (EnableAddressRebalancing) {
1114 rebalanceAddressTrees();
1117 dbgs() << "************* SelectionDAG after preprocessing: ***********\n";
1119 dbgs() << "************* End SelectionDAG after preprocessing ********\n";
1124 void HexagonDAGToDAGISel::EmitFunctionEntryCode() {
1125 auto &HST = static_cast<const HexagonSubtarget&>(MF->getSubtarget());
1126 auto &HFI = *HST.getFrameLowering();
1127 if (!HFI.needsAligna(*MF))
1130 MachineFrameInfo &MFI = MF->getFrameInfo();
1131 MachineBasicBlock *EntryBB = &MF->front();
1132 unsigned AR = FuncInfo->CreateReg(MVT::i32);
1133 unsigned MaxA = MFI.getMaxAlignment();
1134 BuildMI(EntryBB, DebugLoc(), HII->get(Hexagon::PS_aligna), AR)
1136 MF->getInfo<HexagonMachineFunctionInfo>()->setStackAlignBaseVReg(AR);
1139 // Match a frame index that can be used in an addressing mode.
1140 bool HexagonDAGToDAGISel::SelectAddrFI(SDValue& N, SDValue &R) {
1141 if (N.getOpcode() != ISD::FrameIndex)
1143 auto &HFI = *HST->getFrameLowering();
1144 MachineFrameInfo &MFI = MF->getFrameInfo();
1145 int FX = cast<FrameIndexSDNode>(N)->getIndex();
1146 if (!MFI.isFixedObjectIndex(FX) && HFI.needsAligna(*MF))
1148 R = CurDAG->getTargetFrameIndex(FX, MVT::i32);
1152 inline bool HexagonDAGToDAGISel::SelectAddrGA(SDValue &N, SDValue &R) {
1153 return SelectGlobalAddress(N, R, false);
1156 inline bool HexagonDAGToDAGISel::SelectAddrGP(SDValue &N, SDValue &R) {
1157 return SelectGlobalAddress(N, R, true);
1160 bool HexagonDAGToDAGISel::SelectGlobalAddress(SDValue &N, SDValue &R,
1162 switch (N.getOpcode()) {
1164 SDValue N0 = N.getOperand(0);
1165 SDValue N1 = N.getOperand(1);
1166 unsigned GAOpc = N0.getOpcode();
1167 if (UseGP && GAOpc != HexagonISD::CONST32_GP)
1169 if (!UseGP && GAOpc != HexagonISD::CONST32)
1171 if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(N1)) {
1172 SDValue Addr = N0.getOperand(0);
1173 if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Addr)) {
1174 if (GA->getOpcode() == ISD::TargetGlobalAddress) {
1175 uint64_t NewOff = GA->getOffset() + (uint64_t)Const->getSExtValue();
1176 R = CurDAG->getTargetGlobalAddress(GA->getGlobal(), SDLoc(Const),
1177 N.getValueType(), NewOff);
1184 case HexagonISD::CONST32:
1185 // The operand(0) of CONST32 is TargetGlobalAddress, which is what we
1186 // want in the instruction.
1188 R = N.getOperand(0);
1190 case HexagonISD::CONST32_GP:
1192 R = N.getOperand(0);
1201 bool HexagonDAGToDAGISel::isValueExtension(const SDValue &Val,
1202 unsigned FromBits, SDValue &Src) {
1203 unsigned Opc = Val.getOpcode();
1205 case ISD::SIGN_EXTEND:
1206 case ISD::ZERO_EXTEND:
1207 case ISD::ANY_EXTEND: {
1208 SDValue const &Op0 = Val.getOperand(0);
1209 EVT T = Op0.getValueType();
1210 if (T.isInteger() && T.getSizeInBits() == FromBits) {
1216 case ISD::SIGN_EXTEND_INREG:
1217 case ISD::AssertSext:
1218 case ISD::AssertZext:
1219 if (Val.getOperand(0).getValueType().isInteger()) {
1220 VTSDNode *T = cast<VTSDNode>(Val.getOperand(1));
1221 if (T->getVT().getSizeInBits() == FromBits) {
1222 Src = Val.getOperand(0);
1228 // Check if this is an AND with "FromBits" of lower bits set to 1.
1229 uint64_t FromMask = (1 << FromBits) - 1;
1230 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
1231 if (C->getZExtValue() == FromMask) {
1232 Src = Val.getOperand(1);
1236 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
1237 if (C->getZExtValue() == FromMask) {
1238 Src = Val.getOperand(0);
1246 // OR/XOR with the lower "FromBits" bits set to 0.
1247 uint64_t FromMask = (1 << FromBits) - 1;
1248 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
1249 if ((C->getZExtValue() & FromMask) == 0) {
1250 Src = Val.getOperand(1);
1254 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
1255 if ((C->getZExtValue() & FromMask) == 0) {
1256 Src = Val.getOperand(0);
1268 bool HexagonDAGToDAGISel::isOrEquivalentToAdd(const SDNode *N) const {
1269 assert(N->getOpcode() == ISD::OR);
1270 auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
1273 // Detect when "or" is used to add an offset to a stack object.
1274 if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) {
1275 MachineFrameInfo &MFI = MF->getFrameInfo();
1276 unsigned A = MFI.getObjectAlignment(FN->getIndex());
1277 assert(isPowerOf2_32(A));
1278 int32_t Off = C->getSExtValue();
1279 // If the alleged offset fits in the zero bits guaranteed by
1280 // the alignment, then this or is really an add.
1281 return (Off >= 0) && (((A-1) & Off) == unsigned(Off));
1286 bool HexagonDAGToDAGISel::isAlignedMemNode(const MemSDNode *N) const {
1287 return N->getAlignment() >= N->getMemoryVT().getStoreSize();
1290 // Return true when the given node fits in a positive half word.
1291 bool HexagonDAGToDAGISel::isPositiveHalfWord(const SDNode *N) const {
1292 if (const ConstantSDNode *CN = dyn_cast<const ConstantSDNode>(N)) {
1293 int64_t V = CN->getSExtValue();
1294 return V > 0 && isInt<16>(V);
1296 if (N->getOpcode() == ISD::SIGN_EXTEND_INREG) {
1297 const VTSDNode *VN = dyn_cast<const VTSDNode>(N->getOperand(1));
1298 return VN->getVT().getSizeInBits() <= 16;
1303 ////////////////////////////////////////////////////////////////////////////////
1304 // Rebalancing of address calculation trees
1306 static bool isOpcodeHandled(const SDNode *N) {
1307 switch (N->getOpcode()) {
1312 // We only handle constant shifts because these can be easily flattened
1313 // into multiplications by 2^Op1.
1314 return isa<ConstantSDNode>(N->getOperand(1).getNode());
1320 /// \brief Return the weight of an SDNode
1321 int HexagonDAGToDAGISel::getWeight(SDNode *N) {
1322 if (!isOpcodeHandled(N))
1324 assert(RootWeights.count(N) && "Cannot get weight of unseen root!");
1325 assert(RootWeights[N] != -1 && "Cannot get weight of unvisited root!");
1326 assert(RootWeights[N] != -2 && "Cannot get weight of RAWU'd root!");
1327 return RootWeights[N];
1330 int HexagonDAGToDAGISel::getHeight(SDNode *N) {
1331 if (!isOpcodeHandled(N))
1333 assert(RootWeights.count(N) && RootWeights[N] >= 0 &&
1334 "Cannot query height of unvisited/RAUW'd node!");
1335 return RootHeights[N];
1339 struct WeightedLeaf {
1344 WeightedLeaf() : Value(SDValue()) { }
1346 WeightedLeaf(SDValue Value, int Weight, int InsertionOrder) :
1347 Value(Value), Weight(Weight), InsertionOrder(InsertionOrder) {
1348 assert(Weight >= 0 && "Weight must be >= 0");
1351 static bool Compare(const WeightedLeaf &A, const WeightedLeaf &B) {
1352 assert(A.Value.getNode() && B.Value.getNode());
1353 return A.Weight == B.Weight ?
1354 (A.InsertionOrder > B.InsertionOrder) :
1355 (A.Weight > B.Weight);
1359 /// A specialized priority queue for WeigthedLeaves. It automatically folds
1360 /// constants and allows removal of non-top elements while maintaining the
1362 class LeafPrioQueue {
1363 SmallVector<WeightedLeaf, 8> Q;
1365 WeightedLeaf ConstElt;
1370 return (!HaveConst && Q.empty());
1374 return Q.size() + HaveConst;
1381 const WeightedLeaf &top() {
1387 WeightedLeaf pop() {
1392 std::pop_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1393 return Q.pop_back_val();
1396 void push(WeightedLeaf L, bool SeparateConst=true) {
1397 if (!HaveConst && SeparateConst && isa<ConstantSDNode>(L.Value)) {
1398 if (Opcode == ISD::MUL &&
1399 cast<ConstantSDNode>(L.Value)->getSExtValue() == 1)
1401 if (Opcode == ISD::ADD &&
1402 cast<ConstantSDNode>(L.Value)->getSExtValue() == 0)
1409 std::push_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1413 /// Push L to the bottom of the queue regardless of its weight. If L is
1414 /// constant, it will not be folded with other constants in the queue.
1415 void pushToBottom(WeightedLeaf L) {
1420 /// Search for a SHL(x, [<=MaxAmount]) subtree in the queue, return the one of
1421 /// lowest weight and remove it from the queue.
1422 WeightedLeaf findSHL(uint64_t MaxAmount);
1424 WeightedLeaf findMULbyConst();
1426 LeafPrioQueue(unsigned Opcode) :
1427 HaveConst(false), Opcode(Opcode) { }
1429 } // end anonymous namespace
1431 WeightedLeaf LeafPrioQueue::findSHL(uint64_t MaxAmount) {
1433 WeightedLeaf Result;
1435 for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
1436 const WeightedLeaf &L = Q[Pos];
1437 const SDValue &Val = L.Value;
1438 if (Val.getOpcode() != ISD::SHL ||
1439 !isa<ConstantSDNode>(Val.getOperand(1)) ||
1440 Val.getConstantOperandVal(1) > MaxAmount)
1442 if (!Result.Value.getNode() || Result.Weight > L.Weight ||
1443 (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))
1450 if (Result.Value.getNode()) {
1451 Q.erase(&Q[ResultPos]);
1452 std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1458 WeightedLeaf LeafPrioQueue::findMULbyConst() {
1460 WeightedLeaf Result;
1462 for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
1463 const WeightedLeaf &L = Q[Pos];
1464 const SDValue &Val = L.Value;
1465 if (Val.getOpcode() != ISD::MUL ||
1466 !isa<ConstantSDNode>(Val.getOperand(1)) ||
1467 Val.getConstantOperandVal(1) > 127)
1469 if (!Result.Value.getNode() || Result.Weight > L.Weight ||
1470 (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))
1477 if (Result.Value.getNode()) {
1478 Q.erase(&Q[ResultPos]);
1479 std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1485 SDValue HexagonDAGToDAGISel::getMultiplierForSHL(SDNode *N) {
1486 uint64_t MulFactor = 1ull << N->getConstantOperandVal(1);
1487 return CurDAG->getConstant(MulFactor, SDLoc(N),
1488 N->getOperand(1).getValueType());
1491 /// @returns the value x for which 2^x is a factor of Val
1492 static unsigned getPowerOf2Factor(SDValue Val) {
1493 if (Val.getOpcode() == ISD::MUL) {
1494 unsigned MaxFactor = 0;
1495 for (int i = 0; i < 2; ++i) {
1496 ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(i));
1499 const APInt &CInt = C->getAPIntValue();
1500 if (CInt.getBoolValue())
1501 MaxFactor = CInt.countTrailingZeros();
1505 if (Val.getOpcode() == ISD::SHL) {
1506 if (!isa<ConstantSDNode>(Val.getOperand(1).getNode()))
1508 return (unsigned) Val.getConstantOperandVal(1);
1514 /// @returns true if V>>Amount will eliminate V's operation on its child
1515 static bool willShiftRightEliminate(SDValue V, unsigned Amount) {
1516 if (V.getOpcode() == ISD::MUL) {
1517 SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };
1518 for (int i = 0; i < 2; ++i)
1519 if (isa<ConstantSDNode>(Ops[i].getNode()) &&
1520 V.getConstantOperandVal(i) % (1ULL << Amount) == 0) {
1521 uint64_t NewConst = V.getConstantOperandVal(i) >> Amount;
1522 return (NewConst == 1);
1524 } else if (V.getOpcode() == ISD::SHL) {
1525 return (Amount == V.getConstantOperandVal(1));
1531 SDValue HexagonDAGToDAGISel::factorOutPowerOf2(SDValue V, unsigned Power) {
1532 SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };
1533 if (V.getOpcode() == ISD::MUL) {
1534 for (int i=0; i < 2; ++i) {
1535 if (isa<ConstantSDNode>(Ops[i].getNode()) &&
1536 V.getConstantOperandVal(i) % ((uint64_t)1 << Power) == 0) {
1537 uint64_t NewConst = V.getConstantOperandVal(i) >> Power;
1540 Ops[i] = CurDAG->getConstant(NewConst,
1541 SDLoc(V), V.getValueType());
1545 } else if (V.getOpcode() == ISD::SHL) {
1546 uint64_t ShiftAmount = V.getConstantOperandVal(1);
1547 if (ShiftAmount == Power)
1549 Ops[1] = CurDAG->getConstant(ShiftAmount - Power,
1550 SDLoc(V), V.getValueType());
1553 return CurDAG->getNode(V.getOpcode(), SDLoc(V), V.getValueType(), Ops);
1556 static bool isTargetConstant(const SDValue &V) {
1557 return V.getOpcode() == HexagonISD::CONST32 ||
1558 V.getOpcode() == HexagonISD::CONST32_GP;
1561 unsigned HexagonDAGToDAGISel::getUsesInFunction(const Value *V) {
1562 if (GAUsesInFunction.count(V))
1563 return GAUsesInFunction[V];
1565 unsigned Result = 0;
1566 const Function *CurF = CurDAG->getMachineFunction().getFunction();
1567 for (const User *U : V->users()) {
1568 if (isa<Instruction>(U) &&
1569 cast<Instruction>(U)->getParent()->getParent() == CurF)
1573 GAUsesInFunction[V] = Result;
1578 /// Note - After calling this, N may be dead. It may have been replaced by a
1579 /// new node, so always use the returned value in place of N.
1581 /// @returns The SDValue taking the place of N (which could be N if it is
1583 SDValue HexagonDAGToDAGISel::balanceSubTree(SDNode *N, bool TopLevel) {
1584 assert(RootWeights.count(N) && "Cannot balance non-root node.");
1585 assert(RootWeights[N] != -2 && "This node was RAUW'd!");
1586 assert(!TopLevel || N->getOpcode() == ISD::ADD);
1588 // Return early if this node was already visited
1589 if (RootWeights[N] != -1)
1590 return SDValue(N, 0);
1592 assert(isOpcodeHandled(N));
1594 SDValue Op0 = N->getOperand(0);
1595 SDValue Op1 = N->getOperand(1);
1597 // Return early if the operands will remain unchanged or are all roots
1598 if ((!isOpcodeHandled(Op0.getNode()) || RootWeights.count(Op0.getNode())) &&
1599 (!isOpcodeHandled(Op1.getNode()) || RootWeights.count(Op1.getNode()))) {
1600 SDNode *Op0N = Op0.getNode();
1602 if (isOpcodeHandled(Op0N) && RootWeights[Op0N] == -1) {
1603 Weight = getWeight(balanceSubTree(Op0N).getNode());
1604 // Weight = calculateWeight(Op0N);
1606 Weight = getWeight(Op0N);
1608 SDNode *Op1N = N->getOperand(1).getNode(); // Op1 may have been RAUWd
1609 if (isOpcodeHandled(Op1N) && RootWeights[Op1N] == -1) {
1610 Weight += getWeight(balanceSubTree(Op1N).getNode());
1611 // Weight += calculateWeight(Op1N);
1613 Weight += getWeight(Op1N);
1615 RootWeights[N] = Weight;
1616 RootHeights[N] = std::max(getHeight(N->getOperand(0).getNode()),
1617 getHeight(N->getOperand(1).getNode())) + 1;
1619 DEBUG(dbgs() << "--> No need to balance root (Weight=" << Weight
1620 << " Height=" << RootHeights[N] << "): ");
1623 return SDValue(N, 0);
1626 DEBUG(dbgs() << "** Balancing root node: ");
1629 unsigned NOpcode = N->getOpcode();
1631 LeafPrioQueue Leaves(NOpcode);
1632 SmallVector<SDValue, 4> Worklist;
1633 Worklist.push_back(SDValue(N, 0));
1635 // SHL nodes will be converted to MUL nodes
1636 if (NOpcode == ISD::SHL)
1639 bool CanFactorize = false;
1640 WeightedLeaf Mul1, Mul2;
1641 unsigned MaxPowerOf2 = 0;
1644 // Do not try to factor out a shift if there is already a shift at the tip of
1646 bool HaveTopLevelShift = false;
1648 ((isOpcodeHandled(Op0.getNode()) && Op0.getOpcode() == ISD::SHL &&
1649 Op0.getConstantOperandVal(1) < 4) ||
1650 (isOpcodeHandled(Op1.getNode()) && Op1.getOpcode() == ISD::SHL &&
1651 Op1.getConstantOperandVal(1) < 4)))
1652 HaveTopLevelShift = true;
1654 // Flatten the subtree into an ordered list of leaves; at the same time
1655 // determine whether the tree is already balanced.
1656 int InsertionOrder = 0;
1657 SmallDenseMap<SDValue, int> NodeHeights;
1658 bool Imbalanced = false;
1659 int CurrentWeight = 0;
1660 while (!Worklist.empty()) {
1661 SDValue Child = Worklist.pop_back_val();
1663 if (Child.getNode() != N && RootWeights.count(Child.getNode())) {
1664 // CASE 1: Child is a root note
1666 int Weight = RootWeights[Child.getNode()];
1668 Child = balanceSubTree(Child.getNode());
1669 // calculateWeight(Child.getNode());
1670 Weight = getWeight(Child.getNode());
1671 } else if (Weight == -2) {
1672 // Whoops, this node was RAUWd by one of the balanceSubTree calls we
1673 // made. Our worklist isn't up to date anymore.
1674 // Restart the whole process.
1675 DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");
1676 return balanceSubTree(N, TopLevel);
1679 NodeHeights[Child] = 1;
1680 CurrentWeight += Weight;
1683 if (TopLevel && !CanFactorize && !HaveTopLevelShift &&
1684 (Child.getOpcode() == ISD::MUL || Child.getOpcode() == ISD::SHL) &&
1685 Child.hasOneUse() && (PowerOf2 = getPowerOf2Factor(Child))) {
1686 // Try to identify two factorizable MUL/SHL children greedily. Leave
1687 // them out of the priority queue for now so we can deal with them
1689 if (!Mul1.Value.getNode()) {
1690 Mul1 = WeightedLeaf(Child, Weight, InsertionOrder++);
1691 MaxPowerOf2 = PowerOf2;
1693 Mul2 = WeightedLeaf(Child, Weight, InsertionOrder++);
1694 MaxPowerOf2 = std::min(MaxPowerOf2, PowerOf2);
1696 // Our addressing modes can only shift by a maximum of 3
1697 if (MaxPowerOf2 > 3)
1700 CanFactorize = true;
1703 Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
1704 } else if (!isOpcodeHandled(Child.getNode())) {
1705 // CASE 2: Child is an unhandled kind of node (e.g. constant)
1706 int Weight = getWeight(Child.getNode());
1708 NodeHeights[Child] = getHeight(Child.getNode());
1709 CurrentWeight += Weight;
1711 if (isTargetConstant(Child) && !GA.Value.getNode())
1712 GA = WeightedLeaf(Child, Weight, InsertionOrder++);
1714 Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
1716 // CASE 3: Child is a subtree of same opcode
1717 // Visit children first, then flatten.
1718 unsigned ChildOpcode = Child.getOpcode();
1719 assert(ChildOpcode == NOpcode ||
1720 (NOpcode == ISD::MUL && ChildOpcode == ISD::SHL));
1722 // Convert SHL to MUL
1724 if (ChildOpcode == ISD::SHL)
1725 Op1 = getMultiplierForSHL(Child.getNode());
1727 Op1 = Child->getOperand(1);
1729 if (!NodeHeights.count(Op1) || !NodeHeights.count(Child->getOperand(0))) {
1730 assert(!NodeHeights.count(Child) && "Parent visited before children?");
1731 // Visit children first, then re-visit this node
1732 Worklist.push_back(Child);
1733 Worklist.push_back(Op1);
1734 Worklist.push_back(Child->getOperand(0));
1736 // Back at this node after visiting the children
1737 if (std::abs(NodeHeights[Op1] - NodeHeights[Child->getOperand(0)]) > 1)
1740 NodeHeights[Child] = std::max(NodeHeights[Op1],
1741 NodeHeights[Child->getOperand(0)]) + 1;
1746 DEBUG(dbgs() << "--> Current height=" << NodeHeights[SDValue(N, 0)]
1747 << " weight=" << CurrentWeight << " imbalanced="
1748 << Imbalanced << "\n");
1750 // Transform MUL(x, C * 2^Y) + SHL(z, Y) -> SHL(ADD(MUL(x, C), z), Y)
1751 // This factors out a shift in order to match memw(a<<Y+b).
1752 if (CanFactorize && (willShiftRightEliminate(Mul1.Value, MaxPowerOf2) ||
1753 willShiftRightEliminate(Mul2.Value, MaxPowerOf2))) {
1754 DEBUG(dbgs() << "--> Found common factor for two MUL children!\n");
1755 int Weight = Mul1.Weight + Mul2.Weight;
1756 int Height = std::max(NodeHeights[Mul1.Value], NodeHeights[Mul2.Value]) + 1;
1757 SDValue Mul1Factored = factorOutPowerOf2(Mul1.Value, MaxPowerOf2);
1758 SDValue Mul2Factored = factorOutPowerOf2(Mul2.Value, MaxPowerOf2);
1759 SDValue Sum = CurDAG->getNode(ISD::ADD, SDLoc(N), Mul1.Value.getValueType(),
1760 Mul1Factored, Mul2Factored);
1761 SDValue Const = CurDAG->getConstant(MaxPowerOf2, SDLoc(N),
1762 Mul1.Value.getValueType());
1763 SDValue New = CurDAG->getNode(ISD::SHL, SDLoc(N), Mul1.Value.getValueType(),
1765 NodeHeights[New] = Height;
1766 Leaves.push(WeightedLeaf(New, Weight, Mul1.InsertionOrder));
1767 } else if (Mul1.Value.getNode()) {
1768 // We failed to factorize two MULs, so now the Muls are left outside the
1769 // queue... add them back.
1771 if (Mul2.Value.getNode())
1773 CanFactorize = false;
1776 // Combine GA + Constant -> GA+Offset, but only if GA is not used elsewhere
1777 // and the root node itself is not used more than twice. This reduces the
1778 // amount of additional constant extenders introduced by this optimization.
1779 bool CombinedGA = false;
1780 if (NOpcode == ISD::ADD && GA.Value.getNode() && Leaves.hasConst() &&
1781 GA.Value.hasOneUse() && N->use_size() < 3) {
1782 GlobalAddressSDNode *GANode =
1783 cast<GlobalAddressSDNode>(GA.Value.getOperand(0));
1784 ConstantSDNode *Offset = cast<ConstantSDNode>(Leaves.top().Value);
1786 if (getUsesInFunction(GANode->getGlobal()) == 1 && Offset->hasOneUse() &&
1787 getTargetLowering()->isOffsetFoldingLegal(GANode)) {
1788 DEBUG(dbgs() << "--> Combining GA and offset (" << Offset->getSExtValue()
1790 DEBUG(GANode->dump());
1793 CurDAG->getTargetGlobalAddress(GANode->getGlobal(), SDLoc(GA.Value),
1794 GANode->getValueType(0),
1795 GANode->getOffset() + (uint64_t)Offset->getSExtValue());
1796 GA.Value = CurDAG->getNode(GA.Value.getOpcode(), SDLoc(GA.Value),
1797 GA.Value.getValueType(), NewTGA);
1798 GA.Weight += Leaves.top().Weight;
1800 NodeHeights[GA.Value] = getHeight(GA.Value.getNode());
1803 Leaves.pop(); // Remove the offset constant from the queue
1807 if ((RebalanceOnlyForOptimizations && !CanFactorize && !CombinedGA) ||
1808 (RebalanceOnlyImbalancedTrees && !Imbalanced)) {
1809 RootWeights[N] = CurrentWeight;
1810 RootHeights[N] = NodeHeights[SDValue(N, 0)];
1812 return SDValue(N, 0);
1815 // Combine GA + SHL(x, C<=31) so we will match Rx=add(#u8,asl(Rx,#U5))
1816 if (NOpcode == ISD::ADD && GA.Value.getNode()) {
1817 WeightedLeaf SHL = Leaves.findSHL(31);
1818 if (SHL.Value.getNode()) {
1819 int Height = std::max(NodeHeights[GA.Value], NodeHeights[SHL.Value]) + 1;
1820 GA.Value = CurDAG->getNode(ISD::ADD, SDLoc(GA.Value),
1821 GA.Value.getValueType(),
1822 GA.Value, SHL.Value);
1823 GA.Weight = SHL.Weight; // Specifically ignore the GA weight here
1824 NodeHeights[GA.Value] = Height;
1828 if (GA.Value.getNode())
1831 // If this is the top level and we haven't factored out a shift, we should try
1832 // to move a constant to the bottom to match addressing modes like memw(rX+C)
1833 if (TopLevel && !CanFactorize && Leaves.hasConst()) {
1834 DEBUG(dbgs() << "--> Pushing constant to tip of tree.");
1835 Leaves.pushToBottom(Leaves.pop());
1838 const DataLayout &DL = CurDAG->getDataLayout();
1839 const TargetLowering &TLI = *getTargetLowering();
1841 // Rebuild the tree using Huffman's algorithm
1842 while (Leaves.size() > 1) {
1843 WeightedLeaf L0 = Leaves.pop();
1845 // See whether we can grab a MUL to form an add(Rx,mpyi(Ry,#u6)),
1846 // otherwise just get the next leaf
1847 WeightedLeaf L1 = Leaves.findMULbyConst();
1848 if (!L1.Value.getNode())
1851 assert(L0.Weight <= L1.Weight && "Priority queue is broken!");
1853 SDValue V0 = L0.Value;
1854 int V0Weight = L0.Weight;
1855 SDValue V1 = L1.Value;
1856 int V1Weight = L1.Weight;
1858 // Make sure that none of these nodes have been RAUW'd
1859 if ((RootWeights.count(V0.getNode()) && RootWeights[V0.getNode()] == -2) ||
1860 (RootWeights.count(V1.getNode()) && RootWeights[V1.getNode()] == -2)) {
1861 DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");
1862 return balanceSubTree(N, TopLevel);
1865 ConstantSDNode *V0C = dyn_cast<ConstantSDNode>(V0);
1866 ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(V1);
1867 EVT VT = N->getValueType(0);
1872 std::swap(V0C, V1C);
1875 // Calculate height of this node
1876 assert(NodeHeights.count(V0) && NodeHeights.count(V1) &&
1877 "Children must have been visited before re-combining them!");
1878 int Height = std::max(NodeHeights[V0], NodeHeights[V1]) + 1;
1880 // Rebuild this node (and restore SHL from MUL if needed)
1881 if (V1C && NOpcode == ISD::MUL && V1C->getAPIntValue().isPowerOf2())
1882 NewNode = CurDAG->getNode(
1883 ISD::SHL, SDLoc(V0), VT, V0,
1884 CurDAG->getConstant(
1885 V1C->getAPIntValue().logBase2(), SDLoc(N),
1886 TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
1888 NewNode = CurDAG->getNode(NOpcode, SDLoc(N), VT, V0, V1);
1890 NodeHeights[NewNode] = Height;
1892 int Weight = V0Weight + V1Weight;
1893 Leaves.push(WeightedLeaf(NewNode, Weight, L0.InsertionOrder));
1895 DEBUG(dbgs() << "--> Built new node (Weight=" << Weight << ",Height="
1896 << Height << "):\n");
1897 DEBUG(NewNode.dump());
1900 assert(Leaves.size() == 1);
1901 SDValue NewRoot = Leaves.top().Value;
1903 assert(NodeHeights.count(NewRoot));
1904 int Height = NodeHeights[NewRoot];
1906 // Restore SHL if we earlier converted it to a MUL
1907 if (NewRoot.getOpcode() == ISD::MUL) {
1908 ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(NewRoot.getOperand(1));
1909 if (V1C && V1C->getAPIntValue().isPowerOf2()) {
1910 EVT VT = NewRoot.getValueType();
1911 SDValue V0 = NewRoot.getOperand(0);
1912 NewRoot = CurDAG->getNode(
1913 ISD::SHL, SDLoc(NewRoot), VT, V0,
1914 CurDAG->getConstant(
1915 V1C->getAPIntValue().logBase2(), SDLoc(NewRoot),
1916 TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
1920 if (N != NewRoot.getNode()) {
1921 DEBUG(dbgs() << "--> Root is now: ");
1922 DEBUG(NewRoot.dump());
1924 // Replace all uses of old root by new root
1925 CurDAG->ReplaceAllUsesWith(N, NewRoot.getNode());
1926 // Mark that we have RAUW'd N
1927 RootWeights[N] = -2;
1929 DEBUG(dbgs() << "--> Root unchanged.\n");
1932 RootWeights[NewRoot.getNode()] = Leaves.top().Weight;
1933 RootHeights[NewRoot.getNode()] = Height;
1938 void HexagonDAGToDAGISel::rebalanceAddressTrees() {
1939 for (auto I = CurDAG->allnodes_begin(), E = CurDAG->allnodes_end(); I != E;) {
1941 if (N->getOpcode() != ISD::LOAD && N->getOpcode() != ISD::STORE)
1944 SDValue BasePtr = cast<MemSDNode>(N)->getBasePtr();
1945 if (BasePtr.getOpcode() != ISD::ADD)
1948 // We've already processed this node
1949 if (RootWeights.count(BasePtr.getNode()))
1952 DEBUG(dbgs() << "** Rebalancing address calculation in node: ");
1956 SmallVector<SDNode *, 4> Worklist;
1958 Worklist.push_back(BasePtr.getOperand(0).getNode());
1959 Worklist.push_back(BasePtr.getOperand(1).getNode());
1961 while (!Worklist.empty()) {
1962 SDNode *N = Worklist.pop_back_val();
1963 unsigned Opcode = N->getOpcode();
1965 if (!isOpcodeHandled(N))
1968 Worklist.push_back(N->getOperand(0).getNode());
1969 Worklist.push_back(N->getOperand(1).getNode());
1971 // Not a root if it has only one use and same opcode as its parent
1972 if (N->hasOneUse() && Opcode == N->use_begin()->getOpcode())
1975 // This root node has already been processed
1976 if (RootWeights.count(N))
1979 RootWeights[N] = -1;
1982 // Balance node itself
1983 RootWeights[BasePtr.getNode()] = -1;
1984 SDValue NewBasePtr = balanceSubTree(BasePtr.getNode(), /*TopLevel=*/ true);
1986 if (N->getOpcode() == ISD::LOAD)
1987 N = CurDAG->UpdateNodeOperands(N, N->getOperand(0),
1988 NewBasePtr, N->getOperand(2));
1990 N = CurDAG->UpdateNodeOperands(N, N->getOperand(0), N->getOperand(1),
1991 NewBasePtr, N->getOperand(3));
1993 DEBUG(dbgs() << "--> Final node: ");
1997 CurDAG->RemoveDeadNodes();
1998 GAUsesInFunction.clear();
1999 RootHeights.clear();
2000 RootWeights.clear();