Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- HexagonISelDAGToDAG.cpp - A dag to dag inst selector for Hexagon --===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file defines an instruction selector for the Hexagon target.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "Hexagon.h"
14
#include "HexagonISelDAGToDAG.h"
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"
24
using namespace llvm;
25
26
#define DEBUG_TYPE "hexagon-isel"
27
28
static
29
cl::opt<bool>
30
EnableAddressRebalancing("isel-rebalance-addr", cl::Hidden, cl::init(true),
31
  cl::desc("Rebalance address calculation trees to improve "
32
          "instruction selection"));
33
34
// Rebalance only if this allows e.g. combining a GA with an offset or
35
// factoring out a shift.
36
static
37
cl::opt<bool>
38
RebalanceOnlyForOptimizations("rebalance-only-opt", cl::Hidden, cl::init(false),
39
  cl::desc("Rebalance address tree only if this allows optimizations"));
40
41
static
42
cl::opt<bool>
43
RebalanceOnlyImbalancedTrees("rebalance-only-imbal", cl::Hidden,
44
  cl::init(false), cl::desc("Rebalance address tree only if it is imbalanced"));
45
46
static cl::opt<bool> CheckSingleUse("hexagon-isel-su", cl::Hidden,
47
  cl::init(true), cl::desc("Enable checking of SDNode's single-use status"));
48
49
//===----------------------------------------------------------------------===//
50
// Instruction Selector Implementation
51
//===----------------------------------------------------------------------===//
52
53
#define GET_DAGISEL_BODY HexagonDAGToDAGISel
54
#include "HexagonGenDAGISel.inc"
55
56
/// createHexagonISelDag - This pass converts a legalized DAG into a
57
/// Hexagon-specific DAG, ready for instruction scheduling.
58
///
59
namespace llvm {
60
FunctionPass *createHexagonISelDag(HexagonTargetMachine &TM,
61
919
                                   CodeGenOpt::Level OptLevel) {
62
919
  return new HexagonDAGToDAGISel(TM, OptLevel);
63
919
}
64
}
65
66
179
void HexagonDAGToDAGISel::SelectIndexedLoad(LoadSDNode *LD, const SDLoc &dl) {
67
179
  SDValue Chain = LD->getChain();
68
179
  SDValue Base = LD->getBasePtr();
69
179
  SDValue Offset = LD->getOffset();
70
179
  int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
71
179
  EVT LoadedVT = LD->getMemoryVT();
72
179
  unsigned Opcode = 0;
73
179
74
179
  // Check for zero extended loads. Treat any-extend loads as zero extended
75
179
  // loads.
76
179
  ISD::LoadExtType ExtType = LD->getExtensionType();
77
179
  bool IsZeroExt = (ExtType == ISD::ZEXTLOAD || 
ExtType == ISD::EXTLOAD171
);
78
179
  bool IsValidInc = HII->isValidAutoIncImm(LoadedVT, Inc);
79
179
80
179
  assert(LoadedVT.isSimple());
81
179
  switch (LoadedVT.getSimpleVT().SimpleTy) {
82
179
  case MVT::i8:
83
13
    if (IsZeroExt)
84
12
      Opcode = IsValidInc ? Hexagon::L2_loadrub_pi : 
Hexagon::L2_loadrub_io0
;
85
1
    else
86
1
      Opcode = IsValidInc ? Hexagon::L2_loadrb_pi : 
Hexagon::L2_loadrb_io0
;
87
13
    break;
88
179
  case MVT::i16:
89
10
    if (IsZeroExt)
90
0
      Opcode = IsValidInc ? Hexagon::L2_loadruh_pi : Hexagon::L2_loadruh_io;
91
10
    else
92
10
      Opcode = IsValidInc ? Hexagon::L2_loadrh_pi : 
Hexagon::L2_loadrh_io0
;
93
10
    break;
94
179
  case MVT::i32:
95
53
  case MVT::f32:
96
53
  case MVT::v2i16:
97
53
  case MVT::v4i8:
98
53
    Opcode = IsValidInc ? Hexagon::L2_loadri_pi : 
Hexagon::L2_loadri_io0
;
99
53
    break;
100
53
  case MVT::i64:
101
31
  case MVT::f64:
102
31
  case MVT::v2i32:
103
31
  case MVT::v4i16:
104
31
  case MVT::v8i8:
105
31
    Opcode = IsValidInc ? Hexagon::L2_loadrd_pi : 
Hexagon::L2_loadrd_io0
;
106
31
    break;
107
72
  case MVT::v64i8:
108
72
  case MVT::v32i16:
109
72
  case MVT::v16i32:
110
72
  case MVT::v8i64:
111
72
  case MVT::v128i8:
112
72
  case MVT::v64i16:
113
72
  case MVT::v32i32:
114
72
  case MVT::v16i64:
115
72
    if (isAlignedMemNode(LD)) {
116
57
      if (LD->isNonTemporal())
117
0
        Opcode = IsValidInc ? Hexagon::V6_vL32b_nt_pi : Hexagon::V6_vL32b_nt_ai;
118
57
      else
119
57
        Opcode = IsValidInc ? Hexagon::V6_vL32b_pi : 
Hexagon::V6_vL32b_ai0
;
120
57
    } else {
121
15
      Opcode = IsValidInc ? Hexagon::V6_vL32Ub_pi : 
Hexagon::V6_vL32Ub_ai0
;
122
15
    }
123
72
    break;
124
72
  default:
125
0
    llvm_unreachable("Unexpected memory type in indexed load");
126
179
  }
127
179
128
179
  SDValue IncV = CurDAG->getTargetConstant(Inc, dl, MVT::i32);
129
179
  MachineMemOperand *MemOp = LD->getMemOperand();
130
179
131
179
  auto getExt64 = [this,ExtType] (MachineSDNode *N, const SDLoc &dl)
132
179
        -> MachineSDNode* {
133
16
    if (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD) {
134
0
      SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
135
0
      return CurDAG->getMachineNode(Hexagon::A4_combineir, dl, MVT::i64,
136
0
                                    Zero, SDValue(N, 0));
137
0
    }
138
16
    if (ExtType == ISD::SEXTLOAD)
139
0
      return CurDAG->getMachineNode(Hexagon::A2_sxtw, dl, MVT::i64,
140
0
                                    SDValue(N, 0));
141
16
    return N;
142
16
  };
143
179
144
179
  //                  Loaded value   Next address   Chain
145
179
  SDValue From[3] = { SDValue(LD,0), SDValue(LD,1), SDValue(LD,2) };
146
179
  SDValue To[3];
147
179
148
179
  EVT ValueVT = LD->getValueType(0);
149
179
  if (ValueVT == MVT::i64 && 
ExtType != ISD::NON_EXTLOAD16
) {
150
0
    // A load extending to i64 will actually produce i32, which will then
151
0
    // need to be extended to i64.
152
0
    assert(LoadedVT.getSizeInBits() <= 32);
153
0
    ValueVT = MVT::i32;
154
0
  }
155
179
156
179
  if (IsValidInc) {
157
179
    MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT,
158
179
                                              MVT::i32, MVT::Other, Base,
159
179
                                              IncV, Chain);
160
179
    CurDAG->setNodeMemRefs(L, {MemOp});
161
179
    To[1] = SDValue(L, 1); // Next address.
162
179
    To[2] = SDValue(L, 2); // Chain.
163
179
    // Handle special case for extension to i64.
164
179
    if (LD->getValueType(0) == MVT::i64)
165
16
      L = getExt64(L, dl);
166
179
    To[0] = SDValue(L, 0); // Loaded (extended) value.
167
179
  } else {
168
0
    SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
169
0
    MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT, MVT::Other,
170
0
                                              Base, Zero, Chain);
171
0
    CurDAG->setNodeMemRefs(L, {MemOp});
172
0
    To[2] = SDValue(L, 1); // Chain.
173
0
    MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,
174
0
                                              Base, IncV);
175
0
    To[1] = SDValue(A, 0); // Next address.
176
0
    // Handle special case for extension to i64.
177
0
    if (LD->getValueType(0) == MVT::i64)
178
0
      L = getExt64(L, dl);
179
0
    To[0] = SDValue(L, 0); // Loaded (extended) value.
180
0
  }
181
179
  ReplaceUses(From, To, 3);
182
179
  CurDAG->RemoveDeadNode(LD);
183
179
}
184
185
197
MachineSDNode *HexagonDAGToDAGISel::LoadInstrForLoadIntrinsic(SDNode *IntN) {
186
197
  if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
187
0
    return nullptr;
188
197
189
197
  SDLoc dl(IntN);
190
197
  unsigned IntNo = cast<ConstantSDNode>(IntN->getOperand(1))->getZExtValue();
191
197
192
197
  static std::map<unsigned,unsigned> LoadPciMap = {
193
197
    { Intrinsic::hexagon_circ_ldb,  Hexagon::L2_loadrb_pci  },
194
197
    { Intrinsic::hexagon_circ_ldub, Hexagon::L2_loadrub_pci },
195
197
    { Intrinsic::hexagon_circ_ldh,  Hexagon::L2_loadrh_pci  },
196
197
    { Intrinsic::hexagon_circ_lduh, Hexagon::L2_loadruh_pci },
197
197
    { Intrinsic::hexagon_circ_ldw,  Hexagon::L2_loadri_pci  },
198
197
    { Intrinsic::hexagon_circ_ldd,  Hexagon::L2_loadrd_pci  },
199
197
  };
200
197
  auto FLC = LoadPciMap.find(IntNo);
201
197
  if (FLC != LoadPciMap.end()) {
202
30
    EVT ValTy = (IntNo == Intrinsic::hexagon_circ_ldd) ? 
MVT::i6418
:
MVT::i3212
;
203
30
    EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
204
30
    // Operands: { Base, Increment, Modifier, Chain }
205
30
    auto Inc = cast<ConstantSDNode>(IntN->getOperand(5));
206
30
    SDValue I = CurDAG->getTargetConstant(Inc->getSExtValue(), dl, MVT::i32);
207
30
    MachineSDNode *Res = CurDAG->getMachineNode(FLC->second, dl, RTys,
208
30
          { IntN->getOperand(2), I, IntN->getOperand(4),
209
30
            IntN->getOperand(0) });
210
30
    return Res;
211
30
  }
212
167
213
167
  return nullptr;
214
167
}
215
216
SDNode *HexagonDAGToDAGISel::StoreInstrForLoadIntrinsic(MachineSDNode *LoadN,
217
30
      SDNode *IntN) {
218
30
  // The "LoadN" is just a machine load instruction. The intrinsic also
219
30
  // involves storing it. Generate an appropriate store to the location
220
30
  // given in the intrinsic's operand(3).
221
30
  uint64_t F = HII->get(LoadN->getMachineOpcode()).TSFlags;
222
30
  unsigned SizeBits = (F >> HexagonII::MemAccessSizePos) &
223
30
                      HexagonII::MemAccesSizeMask;
224
30
  unsigned Size = 1U << (SizeBits-1);
225
30
226
30
  SDLoc dl(IntN);
227
30
  MachinePointerInfo PI;
228
30
  SDValue TS;
229
30
  SDValue Loc = IntN->getOperand(3);
230
30
231
30
  if (Size >= 4)
232
22
    TS = CurDAG->getStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc, PI,
233
22
                          Size);
234
8
  else
235
8
    TS = CurDAG->getTruncStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc,
236
8
                               PI, MVT::getIntegerVT(Size * 8), Size);
237
30
238
30
  SDNode *StoreN;
239
30
  {
240
30
    HandleSDNode Handle(TS);
241
30
    SelectStore(TS.getNode());
242
30
    StoreN = Handle.getValue().getNode();
243
30
  }
244
30
245
30
  // Load's results are { Loaded value, Updated pointer, Chain }
246
30
  ReplaceUses(SDValue(IntN, 0), SDValue(LoadN, 1));
247
30
  ReplaceUses(SDValue(IntN, 1), SDValue(StoreN, 0));
248
30
  return StoreN;
249
30
}
250
251
2.88k
bool HexagonDAGToDAGISel::tryLoadOfLoadIntrinsic(LoadSDNode *N) {
252
2.88k
  // The intrinsics for load circ/brev perform two operations:
253
2.88k
  // 1. Load a value V from the specified location, using the addressing
254
2.88k
  //    mode corresponding to the intrinsic.
255
2.88k
  // 2. Store V into a specified location. This location is typically a
256
2.88k
  //    local, temporary object.
257
2.88k
  // In many cases, the program using these intrinsics will immediately
258
2.88k
  // load V again from the local object. In those cases, when certain
259
2.88k
  // conditions are met, the last load can be removed.
260
2.88k
  // This function identifies and optimizes this pattern. If the pattern
261
2.88k
  // cannot be optimized, it returns nullptr, which will cause the load
262
2.88k
  // to be selected separately from the intrinsic (which will be handled
263
2.88k
  // in SelectIntrinsicWChain).
264
2.88k
265
2.88k
  SDValue Ch = N->getOperand(0);
266
2.88k
  SDValue Loc = N->getOperand(1);
267
2.88k
268
2.88k
  // Assume that the load and the intrinsic are connected directly with a
269
2.88k
  // chain:
270
2.88k
  //   t1: i32,ch = int.load ..., ..., ..., Loc, ...    // <-- C
271
2.88k
  //   t2: i32,ch = load t1:1, Loc, ...
272
2.88k
  SDNode *C = Ch.getNode();
273
2.88k
274
2.88k
  if (C->getOpcode() != ISD::INTRINSIC_W_CHAIN)
275
2.84k
    return false;
276
38
277
38
  // The second load can only be eliminated if its extension type matches
278
38
  // that of the load instruction corresponding to the intrinsic. The user
279
38
  // can provide an address of an unsigned variable to store the result of
280
38
  // a sign-extending intrinsic into (or the other way around).
281
38
  ISD::LoadExtType IntExt;
282
38
  switch (cast<ConstantSDNode>(C->getOperand(1))->getZExtValue()) {
283
38
    case Intrinsic::hexagon_circ_ldub:
284
4
    case Intrinsic::hexagon_circ_lduh:
285
4
      IntExt = ISD::ZEXTLOAD;
286
4
      break;
287
28
    case Intrinsic::hexagon_circ_ldw:
288
28
    case Intrinsic::hexagon_circ_ldd:
289
28
      IntExt = ISD::NON_EXTLOAD;
290
28
      break;
291
28
    default:
292
6
      IntExt = ISD::SEXTLOAD;
293
6
      break;
294
38
  }
295
38
  if (N->getExtensionType() != IntExt)
296
4
    return false;
297
34
298
34
  // Make sure the target location for the loaded value in the load intrinsic
299
34
  // is the location from which LD (or N) is loading.
300
34
  if (C->getNumOperands() < 4 || Loc.getNode() != C->getOperand(3).getNode())
301
8
    return false;
302
26
303
26
  if (MachineSDNode *L = LoadInstrForLoadIntrinsic(C)) {
304
26
    SDNode *S = StoreInstrForLoadIntrinsic(L, C);
305
26
    SDValue F[] = { SDValue(N,0), SDValue(N,1), SDValue(C,0), SDValue(C,1) };
306
26
    SDValue T[] = { SDValue(L,0), SDValue(S,0), SDValue(L,1), SDValue(S,0) };
307
26
    ReplaceUses(F, T, array_lengthof(T));
308
26
    // This transformation will leave the intrinsic dead. If it remains in
309
26
    // the DAG, the selection code will see it again, but without the load,
310
26
    // and it will generate a store that is normally required for it.
311
26
    CurDAG->RemoveDeadNode(C);
312
26
    return true;
313
26
  }
314
0
  return false;
315
0
}
316
317
// Convert the bit-reverse load intrinsic to appropriate target instruction.
318
167
bool HexagonDAGToDAGISel::SelectBrevLdIntrinsic(SDNode *IntN) {
319
167
  if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
320
0
    return false;
321
167
322
167
  const SDLoc &dl(IntN);
323
167
  unsigned IntNo = cast<ConstantSDNode>(IntN->getOperand(1))->getZExtValue();
324
167
325
167
  static const std::map<unsigned, unsigned> LoadBrevMap = {
326
167
    { Intrinsic::hexagon_L2_loadrb_pbr, Hexagon::L2_loadrb_pbr },
327
167
    { Intrinsic::hexagon_L2_loadrub_pbr, Hexagon::L2_loadrub_pbr },
328
167
    { Intrinsic::hexagon_L2_loadrh_pbr, Hexagon::L2_loadrh_pbr },
329
167
    { Intrinsic::hexagon_L2_loadruh_pbr, Hexagon::L2_loadruh_pbr },
330
167
    { Intrinsic::hexagon_L2_loadri_pbr, Hexagon::L2_loadri_pbr },
331
167
    { Intrinsic::hexagon_L2_loadrd_pbr, Hexagon::L2_loadrd_pbr }
332
167
  };
333
167
  auto FLI = LoadBrevMap.find(IntNo);
334
167
  if (FLI != LoadBrevMap.end()) {
335
12
    EVT ValTy =
336
12
        (IntNo == Intrinsic::hexagon_L2_loadrd_pbr) ? 
MVT::i642
:
MVT::i3210
;
337
12
    EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
338
12
    // Operands of Intrinsic: {chain, enum ID of intrinsic, baseptr,
339
12
    // modifier}.
340
12
    // Operands of target instruction: { Base, Modifier, Chain }.
341
12
    MachineSDNode *Res = CurDAG->getMachineNode(
342
12
        FLI->second, dl, RTys,
343
12
        {IntN->getOperand(2), IntN->getOperand(3), IntN->getOperand(0)});
344
12
345
12
    MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(IntN)->getMemOperand();
346
12
    CurDAG->setNodeMemRefs(Res, {MemOp});
347
12
348
12
    ReplaceUses(SDValue(IntN, 0), SDValue(Res, 0));
349
12
    ReplaceUses(SDValue(IntN, 1), SDValue(Res, 1));
350
12
    ReplaceUses(SDValue(IntN, 2), SDValue(Res, 2));
351
12
    CurDAG->RemoveDeadNode(IntN);
352
12
    return true;
353
12
  }
354
155
  return false;
355
155
}
356
357
/// Generate a machine instruction node for the new circlar buffer intrinsics.
358
/// The new versions use a CSx register instead of the K field.
359
155
bool HexagonDAGToDAGISel::SelectNewCircIntrinsic(SDNode *IntN) {
360
155
  if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
361
0
    return false;
362
155
363
155
  SDLoc DL(IntN);
364
155
  unsigned IntNo = cast<ConstantSDNode>(IntN->getOperand(1))->getZExtValue();
365
155
  SmallVector<SDValue, 7> Ops;
366
155
367
155
  static std::map<unsigned,unsigned> LoadNPcMap = {
368
155
    { Intrinsic::hexagon_L2_loadrub_pci, Hexagon::PS_loadrub_pci },
369
155
    { Intrinsic::hexagon_L2_loadrb_pci, Hexagon::PS_loadrb_pci },
370
155
    { Intrinsic::hexagon_L2_loadruh_pci, Hexagon::PS_loadruh_pci },
371
155
    { Intrinsic::hexagon_L2_loadrh_pci, Hexagon::PS_loadrh_pci },
372
155
    { Intrinsic::hexagon_L2_loadri_pci, Hexagon::PS_loadri_pci },
373
155
    { Intrinsic::hexagon_L2_loadrd_pci, Hexagon::PS_loadrd_pci },
374
155
    { Intrinsic::hexagon_L2_loadrub_pcr, Hexagon::PS_loadrub_pcr },
375
155
    { Intrinsic::hexagon_L2_loadrb_pcr, Hexagon::PS_loadrb_pcr },
376
155
    { Intrinsic::hexagon_L2_loadruh_pcr, Hexagon::PS_loadruh_pcr },
377
155
    { Intrinsic::hexagon_L2_loadrh_pcr, Hexagon::PS_loadrh_pcr },
378
155
    { Intrinsic::hexagon_L2_loadri_pcr, Hexagon::PS_loadri_pcr },
379
155
    { Intrinsic::hexagon_L2_loadrd_pcr, Hexagon::PS_loadrd_pcr }
380
155
  };
381
155
  auto FLI = LoadNPcMap.find (IntNo);
382
155
  if (FLI != LoadNPcMap.end()) {
383
12
    EVT ValTy = MVT::i32;
384
12
    if (IntNo == Intrinsic::hexagon_L2_loadrd_pci ||
385
12
        
IntNo == Intrinsic::hexagon_L2_loadrd_pcr11
)
386
2
      ValTy = MVT::i64;
387
12
    EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
388
12
    // Handle load.*_pci case which has 6 operands.
389
12
    if (IntN->getNumOperands() == 6) {
390
6
      auto Inc = cast<ConstantSDNode>(IntN->getOperand(3));
391
6
      SDValue I = CurDAG->getTargetConstant(Inc->getSExtValue(), DL, MVT::i32);
392
6
      // Operands: { Base, Increment, Modifier, Start, Chain }.
393
6
      Ops = { IntN->getOperand(2), I, IntN->getOperand(4), IntN->getOperand(5),
394
6
              IntN->getOperand(0) };
395
6
    } else
396
6
      // Handle load.*_pcr case which has 5 operands.
397
6
      // Operands: { Base, Modifier, Start, Chain }.
398
6
      Ops = { IntN->getOperand(2), IntN->getOperand(3), IntN->getOperand(4),
399
6
              IntN->getOperand(0) };
400
12
    MachineSDNode *Res = CurDAG->getMachineNode(FLI->second, DL, RTys, Ops);
401
12
    ReplaceUses(SDValue(IntN, 0), SDValue(Res, 0));
402
12
    ReplaceUses(SDValue(IntN, 1), SDValue(Res, 1));
403
12
    ReplaceUses(SDValue(IntN, 2), SDValue(Res, 2));
404
12
    CurDAG->RemoveDeadNode(IntN);
405
12
    return true;
406
12
  }
407
143
408
143
  static std::map<unsigned,unsigned> StoreNPcMap = {
409
143
    { Intrinsic::hexagon_S2_storerb_pci, Hexagon::PS_storerb_pci },
410
143
    { Intrinsic::hexagon_S2_storerh_pci, Hexagon::PS_storerh_pci },
411
143
    { Intrinsic::hexagon_S2_storerf_pci, Hexagon::PS_storerf_pci },
412
143
    { Intrinsic::hexagon_S2_storeri_pci, Hexagon::PS_storeri_pci },
413
143
    { Intrinsic::hexagon_S2_storerd_pci, Hexagon::PS_storerd_pci },
414
143
    { Intrinsic::hexagon_S2_storerb_pcr, Hexagon::PS_storerb_pcr },
415
143
    { Intrinsic::hexagon_S2_storerh_pcr, Hexagon::PS_storerh_pcr },
416
143
    { Intrinsic::hexagon_S2_storerf_pcr, Hexagon::PS_storerf_pcr },
417
143
    { Intrinsic::hexagon_S2_storeri_pcr, Hexagon::PS_storeri_pcr },
418
143
    { Intrinsic::hexagon_S2_storerd_pcr, Hexagon::PS_storerd_pcr }
419
143
  };
420
143
  auto FSI = StoreNPcMap.find (IntNo);
421
143
  if (FSI != StoreNPcMap.end()) {
422
10
    EVT RTys[] = { MVT::i32, MVT::Other };
423
10
    // Handle store.*_pci case which has 7 operands.
424
10
    if (IntN->getNumOperands() == 7) {
425
5
      auto Inc = cast<ConstantSDNode>(IntN->getOperand(3));
426
5
      SDValue I = CurDAG->getTargetConstant(Inc->getSExtValue(), DL, MVT::i32);
427
5
      // Operands: { Base, Increment, Modifier, Value, Start, Chain }.
428
5
      Ops = { IntN->getOperand(2), I, IntN->getOperand(4), IntN->getOperand(5),
429
5
              IntN->getOperand(6), IntN->getOperand(0) };
430
5
    } else
431
5
      // Handle store.*_pcr case which has 6 operands.
432
5
      // Operands: { Base, Modifier, Value, Start, Chain }.
433
5
      Ops = { IntN->getOperand(2), IntN->getOperand(3), IntN->getOperand(4),
434
5
              IntN->getOperand(5), IntN->getOperand(0) };
435
10
    MachineSDNode *Res = CurDAG->getMachineNode(FSI->second, DL, RTys, Ops);
436
10
    ReplaceUses(SDValue(IntN, 0), SDValue(Res, 0));
437
10
    ReplaceUses(SDValue(IntN, 1), SDValue(Res, 1));
438
10
    CurDAG->RemoveDeadNode(IntN);
439
10
    return true;
440
10
  }
441
133
442
133
  return false;
443
133
}
444
445
3.06k
void HexagonDAGToDAGISel::SelectLoad(SDNode *N) {
446
3.06k
  SDLoc dl(N);
447
3.06k
  LoadSDNode *LD = cast<LoadSDNode>(N);
448
3.06k
449
3.06k
  // Handle indexed loads.
450
3.06k
  ISD::MemIndexedMode AM = LD->getAddressingMode();
451
3.06k
  if (AM != ISD::UNINDEXED) {
452
179
    SelectIndexedLoad(LD, dl);
453
179
    return;
454
179
  }
455
2.88k
456
2.88k
  // Handle patterns using circ/brev load intrinsics.
457
2.88k
  if (tryLoadOfLoadIntrinsic(LD))
458
26
    return;
459
2.85k
460
2.85k
  SelectCode(LD);
461
2.85k
}
462
463
101
void HexagonDAGToDAGISel::SelectIndexedStore(StoreSDNode *ST, const SDLoc &dl) {
464
101
  SDValue Chain = ST->getChain();
465
101
  SDValue Base = ST->getBasePtr();
466
101
  SDValue Offset = ST->getOffset();
467
101
  SDValue Value = ST->getValue();
468
101
  // Get the constant value.
469
101
  int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
470
101
  EVT StoredVT = ST->getMemoryVT();
471
101
  EVT ValueVT = Value.getValueType();
472
101
473
101
  bool IsValidInc = HII->isValidAutoIncImm(StoredVT, Inc);
474
101
  unsigned Opcode = 0;
475
101
476
101
  assert(StoredVT.isSimple());
477
101
  switch (StoredVT.getSimpleVT().SimpleTy) {
478
101
  case MVT::i8:
479
20
    Opcode = IsValidInc ? Hexagon::S2_storerb_pi : 
Hexagon::S2_storerb_io0
;
480
20
    break;
481
101
  case MVT::i16:
482
7
    Opcode = IsValidInc ? Hexagon::S2_storerh_pi : 
Hexagon::S2_storerh_io0
;
483
7
    break;
484
101
  case MVT::i32:
485
37
  case MVT::f32:
486
37
  case MVT::v2i16:
487
37
  case MVT::v4i8:
488
37
    Opcode = IsValidInc ? Hexagon::S2_storeri_pi : 
Hexagon::S2_storeri_io0
;
489
37
    break;
490
37
  case MVT::i64:
491
8
  case MVT::f64:
492
8
  case MVT::v2i32:
493
8
  case MVT::v4i16:
494
8
  case MVT::v8i8:
495
8
    Opcode = IsValidInc ? Hexagon::S2_storerd_pi : 
Hexagon::S2_storerd_io0
;
496
8
    break;
497
29
  case MVT::v64i8:
498
29
  case MVT::v32i16:
499
29
  case MVT::v16i32:
500
29
  case MVT::v8i64:
501
29
  case MVT::v128i8:
502
29
  case MVT::v64i16:
503
29
  case MVT::v32i32:
504
29
  case MVT::v16i64:
505
29
    if (isAlignedMemNode(ST)) {
506
25
      if (ST->isNonTemporal())
507
0
        Opcode = IsValidInc ? Hexagon::V6_vS32b_nt_pi : Hexagon::V6_vS32b_nt_ai;
508
25
      else
509
25
        Opcode = IsValidInc ? Hexagon::V6_vS32b_pi : 
Hexagon::V6_vS32b_ai0
;
510
25
    } else {
511
4
      Opcode = IsValidInc ? Hexagon::V6_vS32Ub_pi : 
Hexagon::V6_vS32Ub_ai0
;
512
4
    }
513
29
    break;
514
29
  default:
515
0
    llvm_unreachable("Unexpected memory type in indexed store");
516
101
  }
517
101
518
101
  if (ST->isTruncatingStore() && 
ValueVT.getSizeInBits() == 6428
) {
519
1
    assert(StoredVT.getSizeInBits() < 64 && "Not a truncating store");
520
1
    Value = CurDAG->getTargetExtractSubreg(Hexagon::isub_lo,
521
1
                                           dl, MVT::i32, Value);
522
1
  }
523
101
524
101
  SDValue IncV = CurDAG->getTargetConstant(Inc, dl, MVT::i32);
525
101
  MachineMemOperand *MemOp = ST->getMemOperand();
526
101
527
101
  //                  Next address   Chain
528
101
  SDValue From[2] = { SDValue(ST,0), SDValue(ST,1) };
529
101
  SDValue To[2];
530
101
531
101
  if (IsValidInc) {
532
101
    // Build post increment store.
533
101
    SDValue Ops[] = { Base, IncV, Value, Chain };
534
101
    MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::i32, MVT::Other,
535
101
                                              Ops);
536
101
    CurDAG->setNodeMemRefs(S, {MemOp});
537
101
    To[0] = SDValue(S, 0);
538
101
    To[1] = SDValue(S, 1);
539
101
  } else {
540
0
    SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
541
0
    SDValue Ops[] = { Base, Zero, Value, Chain };
542
0
    MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::Other, Ops);
543
0
    CurDAG->setNodeMemRefs(S, {MemOp});
544
0
    To[1] = SDValue(S, 0);
545
0
    MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,
546
0
                                              Base, IncV);
547
0
    To[0] = SDValue(A, 0);
548
0
  }
549
101
550
101
  ReplaceUses(From, To, 2);
551
101
  CurDAG->RemoveDeadNode(ST);
552
101
}
553
554
2.83k
void HexagonDAGToDAGISel::SelectStore(SDNode *N) {
555
2.83k
  SDLoc dl(N);
556
2.83k
  StoreSDNode *ST = cast<StoreSDNode>(N);
557
2.83k
558
2.83k
  // Handle indexed stores.
559
2.83k
  ISD::MemIndexedMode AM = ST->getAddressingMode();
560
2.83k
  if (AM != ISD::UNINDEXED) {
561
101
    SelectIndexedStore(ST, dl);
562
101
    return;
563
101
  }
564
2.73k
565
2.73k
  SelectCode(ST);
566
2.73k
}
567
568
108
void HexagonDAGToDAGISel::SelectSHL(SDNode *N) {
569
108
  SDLoc dl(N);
570
108
  SDValue Shl_0 = N->getOperand(0);
571
108
  SDValue Shl_1 = N->getOperand(1);
572
108
573
108
  auto Default = [this,N] () -> void { SelectCode(N); };
574
108
575
108
  if (N->getValueType(0) != MVT::i32 || 
Shl_1.getOpcode() != ISD::Constant101
)
576
21
    return Default();
577
87
578
87
  // RHS is const.
579
87
  int32_t ShlConst = cast<ConstantSDNode>(Shl_1)->getSExtValue();
580
87
581
87
  if (Shl_0.getOpcode() == ISD::MUL) {
582
2
    SDValue Mul_0 = Shl_0.getOperand(0); // Val
583
2
    SDValue Mul_1 = Shl_0.getOperand(1); // Const
584
2
    // RHS of mul is const.
585
2
    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Mul_1)) {
586
0
      int32_t ValConst = C->getSExtValue() << ShlConst;
587
0
      if (isInt<9>(ValConst)) {
588
0
        SDValue Val = CurDAG->getTargetConstant(ValConst, dl, MVT::i32);
589
0
        SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,
590
0
                                                MVT::i32, Mul_0, Val);
591
0
        ReplaceNode(N, Result);
592
0
        return;
593
0
      }
594
2
    }
595
2
    return Default();
596
2
  }
597
85
598
85
  if (Shl_0.getOpcode() == ISD::SUB) {
599
3
    SDValue Sub_0 = Shl_0.getOperand(0); // Const 0
600
3
    SDValue Sub_1 = Shl_0.getOperand(1); // Val
601
3
    if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Sub_0)) {
602
0
      if (C1->getSExtValue() != 0 || Sub_1.getOpcode() != ISD::SHL)
603
0
        return Default();
604
0
      SDValue Shl2_0 = Sub_1.getOperand(0); // Val
605
0
      SDValue Shl2_1 = Sub_1.getOperand(1); // Const
606
0
      if (ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(Shl2_1)) {
607
0
        int32_t ValConst = 1 << (ShlConst + C2->getSExtValue());
608
0
        if (isInt<9>(-ValConst)) {
609
0
          SDValue Val = CurDAG->getTargetConstant(-ValConst, dl, MVT::i32);
610
0
          SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,
611
0
                                                  MVT::i32, Shl2_0, Val);
612
0
          ReplaceNode(N, Result);
613
0
          return;
614
0
        }
615
85
      }
616
0
    }
617
3
  }
618
85
619
85
  return Default();
620
85
}
621
622
//
623
// Handling intrinsics for circular load and bitreverse load.
624
//
625
171
void HexagonDAGToDAGISel::SelectIntrinsicWChain(SDNode *N) {
626
171
  if (MachineSDNode *L = LoadInstrForLoadIntrinsic(N)) {
627
4
    StoreInstrForLoadIntrinsic(L, N);
628
4
    CurDAG->RemoveDeadNode(N);
629
4
    return;
630
4
  }
631
167
632
167
  // Handle bit-reverse load intrinsics.
633
167
  if (SelectBrevLdIntrinsic(N))
634
12
    return;
635
155
636
155
  if (SelectNewCircIntrinsic(N))
637
22
    return;
638
133
639
133
  unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue();
640
133
  if (IntNo == Intrinsic::hexagon_V6_vgathermw ||
641
133
      
IntNo == Intrinsic::hexagon_V6_vgathermw_128B131
||
642
133
      
IntNo == Intrinsic::hexagon_V6_vgathermh130
||
643
133
      
IntNo == Intrinsic::hexagon_V6_vgathermh_128B126
||
644
133
      
IntNo == Intrinsic::hexagon_V6_vgathermhw125
||
645
133
      
IntNo == Intrinsic::hexagon_V6_vgathermhw_128B124
) {
646
10
    SelectV65Gather(N);
647
10
    return;
648
10
  }
649
123
  if (IntNo == Intrinsic::hexagon_V6_vgathermwq ||
650
123
      
IntNo == Intrinsic::hexagon_V6_vgathermwq_128B122
||
651
123
      
IntNo == Intrinsic::hexagon_V6_vgathermhq121
||
652
123
      
IntNo == Intrinsic::hexagon_V6_vgathermhq_128B120
||
653
123
      
IntNo == Intrinsic::hexagon_V6_vgathermhwq119
||
654
123
      
IntNo == Intrinsic::hexagon_V6_vgathermhwq_128B118
) {
655
6
    SelectV65GatherPred(N);
656
6
    return;
657
6
  }
658
117
659
117
  SelectCode(N);
660
117
}
661
662
3.76k
void HexagonDAGToDAGISel::SelectIntrinsicWOChain(SDNode *N) {
663
3.76k
  unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue();
664
3.76k
  unsigned Bits;
665
3.76k
  switch (IID) {
666
3.76k
  case Intrinsic::hexagon_S2_vsplatrb:
667
10
    Bits = 8;
668
10
    break;
669
3.76k
  case Intrinsic::hexagon_S2_vsplatrh:
670
3
    Bits = 16;
671
3
    break;
672
3.76k
  case Intrinsic::hexagon_V6_vaddcarry:
673
4
  case Intrinsic::hexagon_V6_vaddcarry_128B:
674
4
  case Intrinsic::hexagon_V6_vsubcarry:
675
4
  case Intrinsic::hexagon_V6_vsubcarry_128B:
676
4
    SelectHVXDualOutput(N);
677
4
    return;
678
3.74k
  default:
679
3.74k
    SelectCode(N);
680
3.74k
    return;
681
13
  }
682
13
683
13
  SDValue V = N->getOperand(1);
684
13
  SDValue U;
685
13
  if (keepsLowBits(V, Bits, U)) {
686
4
    SDValue R = CurDAG->getNode(N->getOpcode(), SDLoc(N), N->getValueType(0),
687
4
                                N->getOperand(0), U);
688
4
    ReplaceNode(N, R.getNode());
689
4
    SelectCode(R.getNode());
690
4
    return;
691
4
  }
692
9
  SelectCode(N);
693
9
}
694
695
//
696
// Map floating point constant values.
697
//
698
32
void HexagonDAGToDAGISel::SelectConstantFP(SDNode *N) {
699
32
  SDLoc dl(N);
700
32
  ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N);
701
32
  APInt A = CN->getValueAPF().bitcastToAPInt();
702
32
  if (N->getValueType(0) == MVT::f32) {
703
26
    SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i32);
704
26
    ReplaceNode(N, CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::f32, V));
705
26
    return;
706
26
  }
707
6
  if (N->getValueType(0) == MVT::f64) {
708
6
    SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i64);
709
6
    ReplaceNode(N, CurDAG->getMachineNode(Hexagon::CONST64, dl, MVT::f64, V));
710
6
    return;
711
6
  }
712
0
713
0
  SelectCode(N);
714
0
}
715
716
//
717
// Map boolean values.
718
//
719
1.18k
void HexagonDAGToDAGISel::SelectConstant(SDNode *N) {
720
1.18k
  if (N->getValueType(0) == MVT::i1) {
721
17
    assert(!(cast<ConstantSDNode>(N)->getZExtValue() >> 1));
722
17
    unsigned Opc = (cast<ConstantSDNode>(N)->getSExtValue() != 0)
723
17
                      ? 
Hexagon::PS_true7
724
17
                      : 
Hexagon::PS_false10
;
725
17
    ReplaceNode(N, CurDAG->getMachineNode(Opc, SDLoc(N), MVT::i1));
726
17
    return;
727
17
  }
728
1.16k
729
1.16k
  SelectCode(N);
730
1.16k
}
731
732
169
void HexagonDAGToDAGISel::SelectFrameIndex(SDNode *N) {
733
169
  MachineFrameInfo &MFI = MF->getFrameInfo();
734
169
  const HexagonFrameLowering *HFI = HST->getFrameLowering();
735
169
  int FX = cast<FrameIndexSDNode>(N)->getIndex();
736
169
  unsigned StkA = HFI->getStackAlignment();
737
169
  unsigned MaxA = MFI.getMaxAlignment();
738
169
  SDValue FI = CurDAG->getTargetFrameIndex(FX, MVT::i32);
739
169
  SDLoc DL(N);
740
169
  SDValue Zero = CurDAG->getTargetConstant(0, DL, MVT::i32);
741
169
  SDNode *R = nullptr;
742
169
743
169
  // Use PS_fi when:
744
169
  // - the object is fixed, or
745
169
  // - there are no objects with higher-than-default alignment, or
746
169
  // - there are no dynamically allocated objects.
747
169
  // Otherwise, use PS_fia.
748
169
  if (FX < 0 || 
MaxA <= StkA164
||
!MFI.hasVarSizedObjects()72
) {
749
168
    R = CurDAG->getMachineNode(Hexagon::PS_fi, DL, MVT::i32, FI, Zero);
750
168
  } else {
751
1
    auto &HMFI = *MF->getInfo<HexagonMachineFunctionInfo>();
752
1
    unsigned AR = HMFI.getStackAlignBaseVReg();
753
1
    SDValue CH = CurDAG->getEntryNode();
754
1
    SDValue Ops[] = { CurDAG->getCopyFromReg(CH, DL, AR, MVT::i32), FI, Zero };
755
1
    R = CurDAG->getMachineNode(Hexagon::PS_fia, DL, MVT::i32, Ops);
756
1
  }
757
169
758
169
  ReplaceNode(N, R);
759
169
}
760
761
4
void HexagonDAGToDAGISel::SelectAddSubCarry(SDNode *N) {
762
4
  unsigned OpcCarry = N->getOpcode() == HexagonISD::ADDC ? 
Hexagon::A4_addp_c2
763
4
                                                         : 
Hexagon::A4_subp_c2
;
764
4
  SDNode *C = CurDAG->getMachineNode(OpcCarry, SDLoc(N), N->getVTList(),
765
4
                                     { N->getOperand(0), N->getOperand(1),
766
4
                                       N->getOperand(2) });
767
4
  ReplaceNode(N, C);
768
4
}
769
770
3
void HexagonDAGToDAGISel::SelectVAlign(SDNode *N) {
771
3
  MVT ResTy = N->getValueType(0).getSimpleVT();
772
3
  if (HST->isHVXVectorType(ResTy, true))
773
3
    return SelectHvxVAlign(N);
774
0
775
0
  const SDLoc &dl(N);
776
0
  unsigned VecLen = ResTy.getSizeInBits();
777
0
  if (VecLen == 32) {
778
0
    SDValue Ops[] = {
779
0
      CurDAG->getTargetConstant(Hexagon::DoubleRegsRegClassID, dl, MVT::i32),
780
0
      N->getOperand(0),
781
0
      CurDAG->getTargetConstant(Hexagon::isub_hi, dl, MVT::i32),
782
0
      N->getOperand(1),
783
0
      CurDAG->getTargetConstant(Hexagon::isub_lo, dl, MVT::i32)
784
0
    };
785
0
    SDNode *R = CurDAG->getMachineNode(TargetOpcode::REG_SEQUENCE, dl,
786
0
                                       MVT::i64, Ops);
787
0
788
0
    // Shift right by "(Addr & 0x3) * 8" bytes.
789
0
    SDValue M0 = CurDAG->getTargetConstant(0x18, dl, MVT::i32);
790
0
    SDValue M1 = CurDAG->getTargetConstant(0x03, dl, MVT::i32);
791
0
    SDNode *C = CurDAG->getMachineNode(Hexagon::S4_andi_asl_ri, dl, MVT::i32,
792
0
                                       M0, N->getOperand(2), M1);
793
0
    SDNode *S = CurDAG->getMachineNode(Hexagon::S2_lsr_r_p, dl, MVT::i64,
794
0
                                       SDValue(R, 0), SDValue(C, 0));
795
0
    SDValue E = CurDAG->getTargetExtractSubreg(Hexagon::isub_lo, dl, ResTy,
796
0
                                               SDValue(S, 0));
797
0
    ReplaceNode(N, E.getNode());
798
0
  } else {
799
0
    assert(VecLen == 64);
800
0
    SDNode *Pu = CurDAG->getMachineNode(Hexagon::C2_tfrrp, dl, MVT::v8i1,
801
0
                                        N->getOperand(2));
802
0
    SDNode *VA = CurDAG->getMachineNode(Hexagon::S2_valignrb, dl, ResTy,
803
0
                                        N->getOperand(0), N->getOperand(1),
804
0
                                        SDValue(Pu,0));
805
0
    ReplaceNode(N, VA);
806
0
  }
807
0
}
808
809
0
void HexagonDAGToDAGISel::SelectVAlignAddr(SDNode *N) {
810
0
  const SDLoc &dl(N);
811
0
  SDValue A = N->getOperand(1);
812
0
  int Mask = -cast<ConstantSDNode>(A.getNode())->getSExtValue();
813
0
  assert(isPowerOf2_32(-Mask));
814
0
815
0
  SDValue M = CurDAG->getTargetConstant(Mask, dl, MVT::i32);
816
0
  SDNode *AA = CurDAG->getMachineNode(Hexagon::A2_andir, dl, MVT::i32,
817
0
                                      N->getOperand(0), M);
818
0
  ReplaceNode(N, AA);
819
0
}
820
821
// Handle these nodes here to avoid having to write patterns for all
822
// combinations of input/output types. In all cases, the resulting
823
// instruction is the same.
824
1
void HexagonDAGToDAGISel::SelectTypecast(SDNode *N) {
825
1
  SDValue Op = N->getOperand(0);
826
1
  MVT OpTy = Op.getValueType().getSimpleVT();
827
1
  SDNode *T = CurDAG->MorphNodeTo(N, N->getOpcode(),
828
1
                                  CurDAG->getVTList(OpTy), {Op});
829
1
  ReplaceNode(T, Op.getNode());
830
1
}
831
832
5
void HexagonDAGToDAGISel::SelectP2D(SDNode *N) {
833
5
  MVT ResTy = N->getValueType(0).getSimpleVT();
834
5
  SDNode *T = CurDAG->getMachineNode(Hexagon::C2_mask, SDLoc(N), ResTy,
835
5
                                     N->getOperand(0));
836
5
  ReplaceNode(N, T);
837
5
}
838
839
3
void HexagonDAGToDAGISel::SelectD2P(SDNode *N) {
840
3
  const SDLoc &dl(N);
841
3
  MVT ResTy = N->getValueType(0).getSimpleVT();
842
3
  SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
843
3
  SDNode *T = CurDAG->getMachineNode(Hexagon::A4_vcmpbgtui, dl, ResTy,
844
3
                                     N->getOperand(0), Zero);
845
3
  ReplaceNode(N, T);
846
3
}
847
848
4
void HexagonDAGToDAGISel::SelectV2Q(SDNode *N) {
849
4
  const SDLoc &dl(N);
850
4
  MVT ResTy = N->getValueType(0).getSimpleVT();
851
4
  // The argument to V2Q should be a single vector.
852
4
  MVT OpTy = N->getOperand(0).getValueType().getSimpleVT(); (void)OpTy;
853
4
  assert(HST->getVectorLength() * 8 == OpTy.getSizeInBits());
854
4
855
4
  SDValue C = CurDAG->getTargetConstant(-1, dl, MVT::i32);
856
4
  SDNode *R = CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::i32, C);
857
4
  SDNode *T = CurDAG->getMachineNode(Hexagon::V6_vandvrt, dl, ResTy,
858
4
                                     N->getOperand(0), SDValue(R,0));
859
4
  ReplaceNode(N, T);
860
4
}
861
862
5
void HexagonDAGToDAGISel::SelectQ2V(SDNode *N) {
863
5
  const SDLoc &dl(N);
864
5
  MVT ResTy = N->getValueType(0).getSimpleVT();
865
5
  // The result of V2Q should be a single vector.
866
5
  assert(HST->getVectorLength() * 8 == ResTy.getSizeInBits());
867
5
868
5
  SDValue C = CurDAG->getTargetConstant(-1, dl, MVT::i32);
869
5
  SDNode *R = CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::i32, C);
870
5
  SDNode *T = CurDAG->getMachineNode(Hexagon::V6_vandqrt, dl, ResTy,
871
5
                                     N->getOperand(0), SDValue(R,0));
872
5
  ReplaceNode(N, T);
873
5
}
874
875
80.5k
void HexagonDAGToDAGISel::Select(SDNode *N) {
876
80.5k
  if (N->isMachineOpcode())
877
642
    return N->setNodeId(-1);  // Already selected.
878
79.9k
879
79.9k
  switch (N->getOpcode()) {
880
79.9k
  
case ISD::Constant: return SelectConstant(N)1.18k
;
881
79.9k
  
case ISD::ConstantFP: return SelectConstantFP(N)32
;
882
79.9k
  
case ISD::FrameIndex: return SelectFrameIndex(N)169
;
883
79.9k
  
case ISD::SHL: return SelectSHL(N)108
;
884
79.9k
  
case ISD::LOAD: return SelectLoad(N)3.06k
;
885
79.9k
  
case ISD::STORE: return SelectStore(N)2.80k
;
886
79.9k
  
case ISD::INTRINSIC_W_CHAIN: return SelectIntrinsicWChain(N)171
;
887
79.9k
  
case ISD::INTRINSIC_WO_CHAIN: return SelectIntrinsicWOChain(N)3.76k
;
888
79.9k
889
79.9k
  case HexagonISD::ADDC:
890
4
  case HexagonISD::SUBC:          return SelectAddSubCarry(N);
891
4
  
case HexagonISD::VALIGN: return SelectVAlign(N)3
;
892
4
  
case HexagonISD::VALIGNADDR: return SelectVAlignAddr(N)0
;
893
4
  
case HexagonISD::TYPECAST: return SelectTypecast(N)1
;
894
5
  case HexagonISD::P2D:           return SelectP2D(N);
895
4
  
case HexagonISD::D2P: return SelectD2P(N)3
;
896
5
  case HexagonISD::Q2V:           return SelectQ2V(N);
897
4
  case HexagonISD::V2Q:           return SelectV2Q(N);
898
68.6k
  }
899
68.6k
900
68.6k
  if (HST->useHVXOps()) {
901
23.5k
    switch (N->getOpcode()) {
902
23.5k
    
case ISD::VECTOR_SHUFFLE: return SelectHvxShuffle(N)1.02k
;
903
23.5k
    
case HexagonISD::VROR: return SelectHvxRor(N)150
;
904
67.4k
    }
905
67.4k
  }
906
67.4k
907
67.4k
  SelectCode(N);
908
67.4k
}
909
910
bool HexagonDAGToDAGISel::
911
SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
912
9
                             std::vector<SDValue> &OutOps) {
913
9
  SDValue Inp = Op, Res;
914
9
915
9
  switch (ConstraintID) {
916
9
  default:
917
0
    return true;
918
9
  case InlineAsm::Constraint_i:
919
9
  case InlineAsm::Constraint_o: // Offsetable.
920
9
  case InlineAsm::Constraint_v: // Not offsetable.
921
9
  case InlineAsm::Constraint_m: // Memory.
922
9
    if (SelectAddrFI(Inp, Res))
923
3
      OutOps.push_back(Res);
924
6
    else
925
6
      OutOps.push_back(Inp);
926
9
    break;
927
9
  }
928
9
929
9
  OutOps.push_back(CurDAG->getTargetConstant(0, SDLoc(Op), MVT::i32));
930
9
  return false;
931
9
}
932
933
934
77
static bool isMemOPCandidate(SDNode *I, SDNode *U) {
935
77
  // I is an operand of U. Check if U is an arithmetic (binary) operation
936
77
  // usable in a memop, where the other operand is a loaded value, and the
937
77
  // result of U is stored in the same location.
938
77
939
77
  if (!U->hasOneUse())
940
37
    return false;
941
40
  unsigned Opc = U->getOpcode();
942
40
  switch (Opc) {
943
40
    case ISD::ADD:
944
40
    case ISD::SUB:
945
40
    case ISD::AND:
946
40
    case ISD::OR:
947
40
      break;
948
40
    default:
949
0
      return false;
950
40
  }
951
40
952
40
  SDValue S0 = U->getOperand(0);
953
40
  SDValue S1 = U->getOperand(1);
954
40
  SDValue SY = (S0.getNode() == I) ? 
S138
:
S02
;
955
40
956
40
  SDNode *UUse = *U->use_begin();
957
40
  if (UUse->getNumValues() != 1)
958
3
    return false;
959
37
960
37
  // Check if one of the inputs to U is a load instruction and the output
961
37
  // is used by a store instruction. If so and they also have the same
962
37
  // base pointer, then don't preoprocess this node sequence as it
963
37
  // can be matched to a memop.
964
37
  SDNode *SYNode = SY.getNode();
965
37
  if (UUse->getOpcode() == ISD::STORE && 
SYNode->getOpcode() == ISD::LOAD2
) {
966
2
    SDValue LDBasePtr = cast<MemSDNode>(SYNode)->getBasePtr();
967
2
    SDValue STBasePtr = cast<MemSDNode>(UUse)->getBasePtr();
968
2
    if (LDBasePtr == STBasePtr)
969
2
      return true;
970
35
  }
971
35
  return false;
972
35
}
973
974
975
// Transform: (or (select c x 0) z)  ->  (select c (or x z) z)
976
//            (or (select c 0 y) z)  ->  (select c z (or y z))
977
6.63k
void HexagonDAGToDAGISel::ppSimplifyOrSelect0(std::vector<SDNode*> &&Nodes) {
978
6.63k
  SelectionDAG &DAG = *CurDAG;
979
6.63k
980
96.3k
  for (auto I : Nodes) {
981
96.3k
    if (I->getOpcode() != ISD::OR)
982
95.8k
      continue;
983
501
984
501
    auto IsZero = [] (const SDValue &V) -> bool {
985
101
      if (ConstantSDNode *SC = dyn_cast<ConstantSDNode>(V.getNode()))
986
59
        return SC->isNullValue();
987
42
      return false;
988
42
    };
989
501
    auto IsSelect0 = [IsZero] (const SDValue &Op) -> bool {
990
501
      if (Op.getOpcode() != ISD::SELECT)
991
469
        return false;
992
32
      return IsZero(Op.getOperand(1)) || 
IsZero(Op.getOperand(2))31
;
993
32
    };
994
501
995
501
    SDValue N0 = I->getOperand(0), N1 = I->getOperand(1);
996
501
    EVT VT = I->getValueType(0);
997
501
    bool SelN0 = IsSelect0(N0);
998
501
    SDValue SOp = SelN0 ? 
N017
:
N1484
;
999
501
    SDValue VOp = SelN0 ? 
N117
:
N0484
;
1000
501
1001
501
    if (SOp.getOpcode() == ISD::SELECT && 
SOp.getNode()->hasOneUse()28
) {
1002
28
      SDValue SC = SOp.getOperand(0);
1003
28
      SDValue SX = SOp.getOperand(1);
1004
28
      SDValue SY = SOp.getOperand(2);
1005
28
      SDLoc DLS = SOp;
1006
28
      if (IsZero(SY)) {
1007
18
        SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SX, VOp);
1008
18
        SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, NewOr, VOp);
1009
18
        DAG.ReplaceAllUsesWith(I, NewSel.getNode());
1010
18
      } else 
if (10
IsZero(SX)10
) {
1011
2
        SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SY, VOp);
1012
2
        SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, VOp, NewOr);
1013
2
        DAG.ReplaceAllUsesWith(I, NewSel.getNode());
1014
2
      }
1015
28
    }
1016
501
  }
1017
6.63k
}
1018
1019
// Transform: (store ch val (add x (add (shl y c) e)))
1020
//        to: (store ch val (add x (shl (add y d) c))),
1021
// where e = (shl d c) for some integer d.
1022
// The purpose of this is to enable generation of loads/stores with
1023
// shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
1024
// value c must be 0, 1 or 2.
1025
6.63k
void HexagonDAGToDAGISel::ppAddrReorderAddShl(std::vector<SDNode*> &&Nodes) {
1026
6.63k
  SelectionDAG &DAG = *CurDAG;
1027
6.63k
1028
96.3k
  for (auto I : Nodes) {
1029
96.3k
    if (I->getOpcode() != ISD::STORE)
1030
93.5k
      continue;
1031
2.80k
1032
2.80k
    // I matched: (store ch val Off)
1033
2.80k
    SDValue Off = I->getOperand(2);
1034
2.80k
    // Off needs to match: (add x (add (shl y c) (shl d c))))
1035
2.80k
    if (Off.getOpcode() != ISD::ADD)
1036
2.20k
      continue;
1037
608
    // Off matched: (add x T0)
1038
608
    SDValue T0 = Off.getOperand(1);
1039
608
    // T0 needs to match: (add T1 T2):
1040
608
    if (T0.getOpcode() != ISD::ADD)
1041
605
      continue;
1042
3
    // T0 matched: (add T1 T2)
1043
3
    SDValue T1 = T0.getOperand(0);
1044
3
    SDValue T2 = T0.getOperand(1);
1045
3
    // T1 needs to match: (shl y c)
1046
3
    if (T1.getOpcode() != ISD::SHL)
1047
0
      continue;
1048
3
    SDValue C = T1.getOperand(1);
1049
3
    ConstantSDNode *CN = dyn_cast<ConstantSDNode>(C.getNode());
1050
3
    if (CN == nullptr)
1051
0
      continue;
1052
3
    unsigned CV = CN->getZExtValue();
1053
3
    if (CV > 2)
1054
0
      continue;
1055
3
    // T2 needs to match e, where e = (shl d c) for some d.
1056
3
    ConstantSDNode *EN = dyn_cast<ConstantSDNode>(T2.getNode());
1057
3
    if (EN == nullptr)
1058
0
      continue;
1059
3
    unsigned EV = EN->getZExtValue();
1060
3
    if (EV % (1 << CV) != 0)
1061
0
      continue;
1062
3
    unsigned DV = EV / (1 << CV);
1063
3
1064
3
    // Replace T0 with: (shl (add y d) c)
1065
3
    SDLoc DL = SDLoc(I);
1066
3
    EVT VT = T0.getValueType();
1067
3
    SDValue D = DAG.getConstant(DV, DL, VT);
1068
3
    // NewAdd = (add y d)
1069
3
    SDValue NewAdd = DAG.getNode(ISD::ADD, DL, VT, T1.getOperand(0), D);
1070
3
    // NewShl = (shl NewAdd c)
1071
3
    SDValue NewShl = DAG.getNode(ISD::SHL, DL, VT, NewAdd, C);
1072
3
    ReplaceNode(T0.getNode(), NewShl.getNode());
1073
3
  }
1074
6.63k
}
1075
1076
// Transform: (load ch (add x (and (srl y c) Mask)))
1077
//        to: (load ch (add x (shl (srl y d) d-c)))
1078
// where
1079
// Mask = 00..0 111..1 0.0
1080
//          |     |     +-- d-c 0s, and d-c is 0, 1 or 2.
1081
//          |     +-------- 1s
1082
//          +-------------- at most c 0s
1083
// Motivating example:
1084
// DAG combiner optimizes (add x (shl (srl y 5) 2))
1085
//                     to (add x (and (srl y 3) 1FFFFFFC))
1086
// which results in a constant-extended and(##...,lsr). This transformation
1087
// undoes this simplification for cases where the shl can be folded into
1088
// an addressing mode.
1089
6.63k
void HexagonDAGToDAGISel::ppAddrRewriteAndSrl(std::vector<SDNode*> &&Nodes) {
1090
6.63k
  SelectionDAG &DAG = *CurDAG;
1091
6.63k
1092
96.3k
  for (SDNode *N : Nodes) {
1093
96.3k
    unsigned Opc = N->getOpcode();
1094
96.3k
    if (Opc != ISD::LOAD && 
Opc != ISD::STORE93.1k
)
1095
90.3k
      continue;
1096
5.98k
    SDValue Addr = Opc == ISD::LOAD ? 
N->getOperand(1)3.17k
:
N->getOperand(2)2.80k
;
1097
5.98k
    // Addr must match: (add x T0)
1098
5.98k
    if (Addr.getOpcode() != ISD::ADD)
1099
4.61k
      continue;
1100
1.37k
    SDValue T0 = Addr.getOperand(1);
1101
1.37k
    // T0 must match: (and T1 Mask)
1102
1.37k
    if (T0.getOpcode() != ISD::AND)
1103
1.36k
      continue;
1104
5
1105
5
    // We have an AND.
1106
5
    //
1107
5
    // Check the first operand. It must be: (srl y c).
1108
5
    SDValue S = T0.getOperand(0);
1109
5
    if (S.getOpcode() != ISD::SRL)
1110
2
      continue;
1111
3
    ConstantSDNode *SN = dyn_cast<ConstantSDNode>(S.getOperand(1).getNode());
1112
3
    if (SN == nullptr)
1113
0
      continue;
1114
3
    if (SN->getAPIntValue().getBitWidth() != 32)
1115
0
      continue;
1116
3
    uint32_t CV = SN->getZExtValue();
1117
3
1118
3
    // Check the second operand: the supposed mask.
1119
3
    ConstantSDNode *MN = dyn_cast<ConstantSDNode>(T0.getOperand(1).getNode());
1120
3
    if (MN == nullptr)
1121
0
      continue;
1122
3
    if (MN->getAPIntValue().getBitWidth() != 32)
1123
0
      continue;
1124
3
    uint32_t Mask = MN->getZExtValue();
1125
3
    // Examine the mask.
1126
3
    uint32_t TZ = countTrailingZeros(Mask);
1127
3
    uint32_t M1 = countTrailingOnes(Mask >> TZ);
1128
3
    uint32_t LZ = countLeadingZeros(Mask);
1129
3
    // Trailing zeros + middle ones + leading zeros must equal the width.
1130
3
    if (TZ + M1 + LZ != 32)
1131
0
      continue;
1132
3
    // The number of trailing zeros will be encoded in the addressing mode.
1133
3
    if (TZ > 2)
1134
0
      continue;
1135
3
    // The number of leading zeros must be at most c.
1136
3
    if (LZ > CV)
1137
0
      continue;
1138
3
1139
3
    // All looks good.
1140
3
    SDValue Y = S.getOperand(0);
1141
3
    EVT VT = Addr.getValueType();
1142
3
    SDLoc dl(S);
1143
3
    // TZ = D-C, so D = TZ+C.
1144
3
    SDValue D = DAG.getConstant(TZ+CV, dl, VT);
1145
3
    SDValue DC = DAG.getConstant(TZ, dl, VT);
1146
3
    SDValue NewSrl = DAG.getNode(ISD::SRL, dl, VT, Y, D);
1147
3
    SDValue NewShl = DAG.getNode(ISD::SHL, dl, VT, NewSrl, DC);
1148
3
    ReplaceNode(T0.getNode(), NewShl.getNode());
1149
3
  }
1150
6.63k
}
1151
1152
// Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
1153
//                                                  (op ... 1 ...))
1154
6.63k
void HexagonDAGToDAGISel::ppHoistZextI1(std::vector<SDNode*> &&Nodes) {
1155
6.63k
  SelectionDAG &DAG = *CurDAG;
1156
6.63k
1157
96.3k
  for (SDNode *N : Nodes) {
1158
96.3k
    unsigned Opc = N->getOpcode();
1159
96.3k
    if (Opc != ISD::ZERO_EXTEND)
1160
96.1k
      continue;
1161
193
    SDValue OpI1 = N->getOperand(0);
1162
193
    EVT OpVT = OpI1.getValueType();
1163
193
    if (!OpVT.isSimple() || OpVT.getSimpleVT() != MVT::i1)
1164
83
      continue;
1165
257
    
for (auto I = N->use_begin(), E = N->use_end(); 110
I != E;
++I147
) {
1166
147
      SDNode *U = *I;
1167
147
      if (U->getNumValues() != 1)
1168
63
        continue;
1169
84
      EVT UVT = U->getValueType(0);
1170
84
      if (!UVT.isSimple() || !UVT.isInteger() || 
UVT.getSimpleVT() == MVT::i178
)
1171
7
        continue;
1172
77
      if (isMemOPCandidate(N, U))
1173
2
        continue;
1174
75
1175
75
      // Potentially simplifiable operation.
1176
75
      unsigned I1N = I.getOperandNo();
1177
75
      SmallVector<SDValue,2> Ops(U->getNumOperands());
1178
230
      for (unsigned i = 0, n = U->getNumOperands(); i != n; 
++i155
)
1179
155
        Ops[i] = U->getOperand(i);
1180
75
      EVT BVT = Ops[I1N].getValueType();
1181
75
1182
75
      SDLoc dl(U);
1183
75
      SDValue C0 = DAG.getConstant(0, dl, BVT);
1184
75
      SDValue C1 = DAG.getConstant(1, dl, BVT);
1185
75
      SDValue If0, If1;
1186
75
1187
75
      if (isa<MachineSDNode>(U)) {
1188
0
        unsigned UseOpc = U->getMachineOpcode();
1189
0
        Ops[I1N] = C0;
1190
0
        If0 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);
1191
0
        Ops[I1N] = C1;
1192
0
        If1 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);
1193
75
      } else {
1194
75
        unsigned UseOpc = U->getOpcode();
1195
75
        Ops[I1N] = C0;
1196
75
        If0 = DAG.getNode(UseOpc, dl, UVT, Ops);
1197
75
        Ops[I1N] = C1;
1198
75
        If1 = DAG.getNode(UseOpc, dl, UVT, Ops);
1199
75
      }
1200
75
      SDValue Sel = DAG.getNode(ISD::SELECT, dl, UVT, OpI1, If1, If0);
1201
75
      DAG.ReplaceAllUsesWith(U, Sel.getNode());
1202
75
    }
1203
110
  }
1204
6.63k
}
1205
1206
6.63k
void HexagonDAGToDAGISel::PreprocessISelDAG() {
1207
6.63k
  // Repack all nodes before calling each preprocessing function,
1208
6.63k
  // because each of them can modify the set of nodes.
1209
26.5k
  auto getNodes = [this] () -> std::vector<SDNode*> {
1210
26.5k
    std::vector<SDNode*> T;
1211
26.5k
    T.reserve(CurDAG->allnodes_size());
1212
26.5k
    for (SDNode &N : CurDAG->allnodes())
1213
385k
      T.push_back(&N);
1214
26.5k
    return T;
1215
26.5k
  };
1216
6.63k
1217
6.63k
  // Transform: (or (select c x 0) z)  ->  (select c (or x z) z)
1218
6.63k
  //            (or (select c 0 y) z)  ->  (select c z (or y z))
1219
6.63k
  ppSimplifyOrSelect0(getNodes());
1220
6.63k
1221
6.63k
  // Transform: (store ch val (add x (add (shl y c) e)))
1222
6.63k
  //        to: (store ch val (add x (shl (add y d) c))),
1223
6.63k
  // where e = (shl d c) for some integer d.
1224
6.63k
  // The purpose of this is to enable generation of loads/stores with
1225
6.63k
  // shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
1226
6.63k
  // value c must be 0, 1 or 2.
1227
6.63k
  ppAddrReorderAddShl(getNodes());
1228
6.63k
1229
6.63k
  // Transform: (load ch (add x (and (srl y c) Mask)))
1230
6.63k
  //        to: (load ch (add x (shl (srl y d) d-c)))
1231
6.63k
  // where
1232
6.63k
  // Mask = 00..0 111..1 0.0
1233
6.63k
  //          |     |     +-- d-c 0s, and d-c is 0, 1 or 2.
1234
6.63k
  //          |     +-------- 1s
1235
6.63k
  //          +-------------- at most c 0s
1236
6.63k
  // Motivating example:
1237
6.63k
  // DAG combiner optimizes (add x (shl (srl y 5) 2))
1238
6.63k
  //                     to (add x (and (srl y 3) 1FFFFFFC))
1239
6.63k
  // which results in a constant-extended and(##...,lsr). This transformation
1240
6.63k
  // undoes this simplification for cases where the shl can be folded into
1241
6.63k
  // an addressing mode.
1242
6.63k
  ppAddrRewriteAndSrl(getNodes());
1243
6.63k
1244
6.63k
  // Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
1245
6.63k
  //                                                  (op ... 1 ...))
1246
6.63k
  ppHoistZextI1(getNodes());
1247
6.63k
1248
6.63k
  DEBUG_WITH_TYPE("isel", {
1249
6.63k
    dbgs() << "Preprocessed (Hexagon) selection DAG:";
1250
6.63k
    CurDAG->dump();
1251
6.63k
  });
1252
6.63k
1253
6.63k
  if (EnableAddressRebalancing) {
1254
6.63k
    rebalanceAddressTrees();
1255
6.63k
1256
6.63k
    DEBUG_WITH_TYPE("isel", {
1257
6.63k
      dbgs() << "Address tree balanced selection DAG:";
1258
6.63k
      CurDAG->dump();
1259
6.63k
    });
1260
6.63k
  }
1261
6.63k
}
1262
1263
4.97k
void HexagonDAGToDAGISel::EmitFunctionEntryCode() {
1264
4.97k
  auto &HST = static_cast<const HexagonSubtarget&>(MF->getSubtarget());
1265
4.97k
  auto &HFI = *HST.getFrameLowering();
1266
4.97k
  if (!HFI.needsAligna(*MF))
1267
4.96k
    return;
1268
2
1269
2
  MachineFrameInfo &MFI = MF->getFrameInfo();
1270
2
  MachineBasicBlock *EntryBB = &MF->front();
1271
2
  unsigned AR = FuncInfo->CreateReg(MVT::i32);
1272
2
  unsigned MaxA = MFI.getMaxAlignment();
1273
2
  BuildMI(EntryBB, DebugLoc(), HII->get(Hexagon::PS_aligna), AR)
1274
2
      .addImm(MaxA);
1275
2
  MF->getInfo<HexagonMachineFunctionInfo>()->setStackAlignBaseVReg(AR);
1276
2
}
1277
1278
// Match a frame index that can be used in an addressing mode.
1279
3.61k
bool HexagonDAGToDAGISel::SelectAddrFI(SDValue &N, SDValue &R) {
1280
3.61k
  if (N.getOpcode() != ISD::FrameIndex)
1281
2.67k
    return false;
1282
944
  auto &HFI = *HST->getFrameLowering();
1283
944
  MachineFrameInfo &MFI = MF->getFrameInfo();
1284
944
  int FX = cast<FrameIndexSDNode>(N)->getIndex();
1285
944
  if (!MFI.isFixedObjectIndex(FX) && 
HFI.needsAligna(*MF)920
)
1286
0
    return false;
1287
944
  R = CurDAG->getTargetFrameIndex(FX, MVT::i32);
1288
944
  return true;
1289
944
}
1290
1291
0
inline bool HexagonDAGToDAGISel::SelectAddrGA(SDValue &N, SDValue &R) {
1292
0
  return SelectGlobalAddress(N, R, false, 0);
1293
0
}
1294
1295
3.14k
inline bool HexagonDAGToDAGISel::SelectAddrGP(SDValue &N, SDValue &R) {
1296
3.14k
  return SelectGlobalAddress(N, R, true, 0);
1297
3.14k
}
1298
1299
6.69k
inline bool HexagonDAGToDAGISel::SelectAnyImm(SDValue &N, SDValue &R) {
1300
6.69k
  return SelectAnyImmediate(N, R, 0);
1301
6.69k
}
1302
1303
678
inline bool HexagonDAGToDAGISel::SelectAnyImm0(SDValue &N, SDValue &R) {
1304
678
  return SelectAnyImmediate(N, R, 0);
1305
678
}
1306
376
inline bool HexagonDAGToDAGISel::SelectAnyImm1(SDValue &N, SDValue &R) {
1307
376
  return SelectAnyImmediate(N, R, 1);
1308
376
}
1309
2.35k
inline bool HexagonDAGToDAGISel::SelectAnyImm2(SDValue &N, SDValue &R) {
1310
2.35k
  return SelectAnyImmediate(N, R, 2);
1311
2.35k
}
1312
617
inline bool HexagonDAGToDAGISel::SelectAnyImm3(SDValue &N, SDValue &R) {
1313
617
  return SelectAnyImmediate(N, R, 3);
1314
617
}
1315
1316
2.43k
inline bool HexagonDAGToDAGISel::SelectAnyInt(SDValue &N, SDValue &R) {
1317
2.43k
  EVT T = N.getValueType();
1318
2.43k
  if (!T.isInteger() || T.getSizeInBits() != 32 || !isa<ConstantSDNode>(N))
1319
1.67k
    return false;
1320
758
  R = N;
1321
758
  return true;
1322
758
}
1323
1324
bool HexagonDAGToDAGISel::SelectAnyImmediate(SDValue &N, SDValue &R,
1325
10.7k
                                             uint32_t LogAlign) {
1326
10.7k
  auto IsAligned = [LogAlign] (uint64_t V) -> bool {
1327
2.69k
    return alignTo(V, (uint64_t)1 << LogAlign) == V;
1328
2.69k
  };
1329
10.7k
1330
10.7k
  switch (N.getOpcode()) {
1331
10.7k
  case ISD::Constant: {
1332
2.69k
    if (N.getValueType() != MVT::i32)
1333
0
      return false;
1334
2.69k
    int32_t V = cast<const ConstantSDNode>(N)->getZExtValue();
1335
2.69k
    if (!IsAligned(V))
1336
1
      return false;
1337
2.69k
    R = CurDAG->getTargetConstant(V, SDLoc(N), N.getValueType());
1338
2.69k
    return true;
1339
2.69k
  }
1340
2.69k
  case HexagonISD::JT:
1341
4
  case HexagonISD::CP:
1342
4
    // These are assumed to always be aligned at least 8-byte boundary.
1343
4
    if (LogAlign > 3)
1344
0
      return false;
1345
4
    R = N.getOperand(0);
1346
4
    return true;
1347
4
  case ISD::ExternalSymbol:
1348
0
    // Symbols may be aligned at any boundary.
1349
0
    if (LogAlign > 0)
1350
0
      return false;
1351
0
    R = N;
1352
0
    return true;
1353
0
  case ISD::BlockAddress:
1354
0
    // Block address is always aligned at least 4-byte boundary.
1355
0
    if (LogAlign > 2 || !IsAligned(cast<BlockAddressSDNode>(N)->getOffset()))
1356
0
      return false;
1357
0
    R = N;
1358
0
    return true;
1359
8.01k
  }
1360
8.01k
1361
8.01k
  if (SelectGlobalAddress(N, R, false, LogAlign) ||
1362
8.01k
      
SelectGlobalAddress(N, R, true, LogAlign)7.42k
)
1363
618
    return true;
1364
7.40k
1365
7.40k
  return false;
1366
7.40k
}
1367
1368
bool HexagonDAGToDAGISel::SelectGlobalAddress(SDValue &N, SDValue &R,
1369
18.5k
                                              bool UseGP, uint32_t LogAlign) {
1370
18.5k
  auto IsAligned = [LogAlign] (uint64_t V) -> bool {
1371
66
    return alignTo(V, (uint64_t)1 << LogAlign) == V;
1372
66
  };
1373
18.5k
1374
18.5k
  switch (N.getOpcode()) {
1375
18.5k
  case ISD::ADD: {
1376
4.03k
    SDValue N0 = N.getOperand(0);
1377
4.03k
    SDValue N1 = N.getOperand(1);
1378
4.03k
    unsigned GAOpc = N0.getOpcode();
1379
4.03k
    if (UseGP && 
GAOpc != HexagonISD::CONST32_GP2.45k
)
1380
2.45k
      return false;
1381
1.58k
    if (!UseGP && GAOpc != HexagonISD::CONST32)
1382
1.51k
      return false;
1383
66
    if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(N1)) {
1384
66
      SDValue Addr = N0.getOperand(0);
1385
66
      // For the purpose of alignment, sextvalue and zextvalue are the same.
1386
66
      if (!IsAligned(Const->getZExtValue()))
1387
0
        return false;
1388
66
      if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Addr)) {
1389
66
        if (GA->getOpcode() == ISD::TargetGlobalAddress) {
1390
66
          uint64_t NewOff = GA->getOffset() + (uint64_t)Const->getSExtValue();
1391
66
          R = CurDAG->getTargetGlobalAddress(GA->getGlobal(), SDLoc(Const),
1392
66
                                             N.getValueType(), NewOff);
1393
66
          return true;
1394
66
        }
1395
0
      }
1396
66
    }
1397
0
    break;
1398
0
  }
1399
903
  case HexagonISD::CP:
1400
903
  case HexagonISD::JT:
1401
903
  case HexagonISD::CONST32:
1402
903
    // The operand(0) of CONST32 is TargetGlobalAddress, which is what we
1403
903
    // want in the instruction.
1404
903
    if (!UseGP)
1405
527
      R = N.getOperand(0);
1406
903
    return !UseGP;
1407
903
  case HexagonISD::CONST32_GP:
1408
484
    if (UseGP)
1409
459
      R = N.getOperand(0);
1410
484
    return UseGP;
1411
13.1k
  default:
1412
13.1k
    return false;
1413
0
  }
1414
0
1415
0
  return false;
1416
0
}
1417
1418
211
bool HexagonDAGToDAGISel::DetectUseSxtw(SDValue &N, SDValue &R) {
1419
211
  // This (complex pattern) function is meant to detect a sign-extension
1420
211
  // i32->i64 on a per-operand basis. This would allow writing single
1421
211
  // patterns that would cover a number of combinations of different ways
1422
211
  // a sign-extensions could be written. For example:
1423
211
  //   (mul (DetectUseSxtw x) (DetectUseSxtw y)) -> (M2_dpmpyss_s0 x y)
1424
211
  // could match either one of these:
1425
211
  //   (mul (sext x) (sext_inreg y))
1426
211
  //   (mul (sext-load *p) (sext_inreg y))
1427
211
  //   (mul (sext_inreg x) (sext y))
1428
211
  // etc.
1429
211
  //
1430
211
  // The returned value will have type i64 and its low word will
1431
211
  // contain the value being extended. The high bits are not specified.
1432
211
  // The returned type is i64 because the original type of N was i64,
1433
211
  // but the users of this function should only use the low-word of the
1434
211
  // result, e.g.
1435
211
  //  (mul sxtw:x, sxtw:y) -> (M2_dpmpyss_s0 (LoReg sxtw:x), (LoReg sxtw:y))
1436
211
1437
211
  if (N.getValueType() != MVT::i64)
1438
0
    return false;
1439
211
  unsigned Opc = N.getOpcode();
1440
211
  switch (Opc) {
1441
211
    case ISD::SIGN_EXTEND:
1442
72
    case ISD::SIGN_EXTEND_INREG: {
1443
72
      // sext_inreg has the source type as a separate operand.
1444
72
      EVT T = Opc == ISD::SIGN_EXTEND
1445
72
                ? 
N.getOperand(0).getValueType()51
1446
72
                : 
cast<VTSDNode>(N.getOperand(1))->getVT()21
;
1447
72
      unsigned SW = T.getSizeInBits();
1448
72
      if (SW == 32)
1449
67
        R = N.getOperand(0);
1450
5
      else if (SW < 32)
1451
5
        R = N;
1452
0
      else
1453
0
        return false;
1454
72
      break;
1455
72
    }
1456
72
    case ISD::LOAD: {
1457
6
      LoadSDNode *L = cast<LoadSDNode>(N);
1458
6
      if (L->getExtensionType() != ISD::SEXTLOAD)
1459
4
        return false;
1460
2
      // All extending loads extend to i32, so even if the value in
1461
2
      // memory is shorter than 32 bits, it will be i32 after the load.
1462
2
      if (L->getMemoryVT().getSizeInBits() > 32)
1463
0
        return false;
1464
2
      R = N;
1465
2
      break;
1466
2
    }
1467
3
    case ISD::SRA: {
1468
3
      auto *S = dyn_cast<ConstantSDNode>(N.getOperand(1));
1469
3
      if (!S || S->getZExtValue() != 32)
1470
0
        return false;
1471
3
      R = N;
1472
3
      break;
1473
3
    }
1474
130
    default:
1475
130
      return false;
1476
77
  }
1477
77
  EVT RT = R.getValueType();
1478
77
  if (RT == MVT::i64)
1479
26
    return true;
1480
51
  assert(RT == MVT::i32);
1481
51
  // This is only to produce a value of type i64. Do not rely on the
1482
51
  // high bits produced by this.
1483
51
  const SDLoc &dl(N);
1484
51
  SDValue Ops[] = {
1485
51
    CurDAG->getTargetConstant(Hexagon::DoubleRegsRegClassID, dl, MVT::i32),
1486
51
    R, CurDAG->getTargetConstant(Hexagon::isub_hi, dl, MVT::i32),
1487
51
    R, CurDAG->getTargetConstant(Hexagon::isub_lo, dl, MVT::i32)
1488
51
  };
1489
51
  SDNode *T = CurDAG->getMachineNode(TargetOpcode::REG_SEQUENCE, dl,
1490
51
                                     MVT::i64, Ops);
1491
51
  R = SDValue(T, 0);
1492
51
  return true;
1493
51
}
1494
1495
bool HexagonDAGToDAGISel::keepsLowBits(const SDValue &Val, unsigned NumBits,
1496
13
      SDValue &Src) {
1497
13
  unsigned Opc = Val.getOpcode();
1498
13
  switch (Opc) {
1499
13
  case ISD::SIGN_EXTEND:
1500
0
  case ISD::ZERO_EXTEND:
1501
0
  case ISD::ANY_EXTEND: {
1502
0
    const SDValue &Op0 = Val.getOperand(0);
1503
0
    EVT T = Op0.getValueType();
1504
0
    if (T.isInteger() && T.getSizeInBits() == NumBits) {
1505
0
      Src = Op0;
1506
0
      return true;
1507
0
    }
1508
0
    break;
1509
0
  }
1510
1
  case ISD::SIGN_EXTEND_INREG:
1511
1
  case ISD::AssertSext:
1512
1
  case ISD::AssertZext:
1513
1
    if (Val.getOperand(0).getValueType().isInteger()) {
1514
1
      VTSDNode *T = cast<VTSDNode>(Val.getOperand(1));
1515
1
      if (T->getVT().getSizeInBits() == NumBits) {
1516
1
        Src = Val.getOperand(0);
1517
1
        return true;
1518
1
      }
1519
0
    }
1520
0
    break;
1521
3
  case ISD::AND: {
1522
3
    // Check if this is an AND with NumBits of lower bits set to 1.
1523
3
    uint64_t Mask = (1 << NumBits) - 1;
1524
3
    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
1525
0
      if (C->getZExtValue() == Mask) {
1526
0
        Src = Val.getOperand(1);
1527
0
        return true;
1528
0
      }
1529
3
    }
1530
3
    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
1531
3
      if (C->getZExtValue() == Mask) {
1532
3
        Src = Val.getOperand(0);
1533
3
        return true;
1534
3
      }
1535
0
    }
1536
0
    break;
1537
0
  }
1538
0
  case ISD::OR:
1539
0
  case ISD::XOR: {
1540
0
    // OR/XOR with the lower NumBits bits set to 0.
1541
0
    uint64_t Mask = (1 << NumBits) - 1;
1542
0
    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
1543
0
      if ((C->getZExtValue() & Mask) == 0) {
1544
0
        Src = Val.getOperand(1);
1545
0
        return true;
1546
0
      }
1547
0
    }
1548
0
    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
1549
0
      if ((C->getZExtValue() & Mask) == 0) {
1550
0
        Src = Val.getOperand(0);
1551
0
        return true;
1552
0
      }
1553
0
    }
1554
0
    break;
1555
0
  }
1556
9
  default:
1557
9
    break;
1558
9
  }
1559
9
  return false;
1560
9
}
1561
1562
2.17k
bool HexagonDAGToDAGISel::isAlignedMemNode(const MemSDNode *N) const {
1563
2.17k
  return N->getAlignment() >= N->getMemoryVT().getStoreSize();
1564
2.17k
}
1565
1566
2.74k
bool HexagonDAGToDAGISel::isSmallStackStore(const StoreSDNode *N) const {
1567
2.74k
  unsigned StackSize = MF->getFrameInfo().estimateStackSize(*MF);
1568
2.74k
  switch (N->getMemoryVT().getStoreSize()) {
1569
2.74k
    case 1:
1570
307
      return StackSize <= 56;   // 1*2^6 - 8
1571
2.74k
    case 2:
1572
213
      return StackSize <= 120;  // 2*2^6 - 8
1573
2.74k
    case 4:
1574
2.22k
      return StackSize <= 248;  // 4*2^6 - 8
1575
2.74k
    default:
1576
0
      return false;
1577
2.74k
  }
1578
2.74k
}
1579
1580
// Return true when the given node fits in a positive half word.
1581
2
bool HexagonDAGToDAGISel::isPositiveHalfWord(const SDNode *N) const {
1582
2
  if (const ConstantSDNode *CN = dyn_cast<const ConstantSDNode>(N)) {
1583
1
    int64_t V = CN->getSExtValue();
1584
1
    return V > 0 && 
isInt<16>(V)0
;
1585
1
  }
1586
1
  if (N->getOpcode() == ISD::SIGN_EXTEND_INREG) {
1587
1
    const VTSDNode *VN = dyn_cast<const VTSDNode>(N->getOperand(1));
1588
1
    return VN->getVT().getSizeInBits() <= 16;
1589
1
  }
1590
0
  return false;
1591
0
}
1592
1593
1.59k
bool HexagonDAGToDAGISel::hasOneUse(const SDNode *N) const {
1594
1.59k
  return !CheckSingleUse || N->hasOneUse();
1595
1.59k
}
1596
1597
////////////////////////////////////////////////////////////////////////////////
1598
// Rebalancing of address calculation trees
1599
1600
14.8k
static bool isOpcodeHandled(const SDNode *N) {
1601
14.8k
  switch (N->getOpcode()) {
1602
14.8k
    case ISD::ADD:
1603
1.13k
    case ISD::MUL:
1604
1.13k
      return true;
1605
1.13k
    case ISD::SHL:
1606
995
      // We only handle constant shifts because these can be easily flattened
1607
995
      // into multiplications by 2^Op1.
1608
995
      return isa<ConstantSDNode>(N->getOperand(1).getNode());
1609
12.7k
    default:
1610
12.7k
      return false;
1611
14.8k
  }
1612
14.8k
}
1613
1614
/// Return the weight of an SDNode
1615
2.82k
int HexagonDAGToDAGISel::getWeight(SDNode *N) {
1616
2.82k
  if (!isOpcodeHandled(N))
1617
2.48k
    return 1;
1618
346
  assert(RootWeights.count(N) && "Cannot get weight of unseen root!");
1619
346
  assert(RootWeights[N] != -1 && "Cannot get weight of unvisited root!");
1620
346
  assert(RootWeights[N] != -2 && "Cannot get weight of RAWU'd root!");
1621
346
  return RootWeights[N];
1622
346
}
1623
1624
2.80k
int HexagonDAGToDAGISel::getHeight(SDNode *N) {
1625
2.80k
  if (!isOpcodeHandled(N))
1626
2.48k
    return 0;
1627
327
  assert(RootWeights.count(N) && RootWeights[N] >= 0 &&
1628
327
      "Cannot query height of unvisited/RAUW'd node!");
1629
327
  return RootHeights[N];
1630
327
}
1631
1632
namespace {
1633
struct WeightedLeaf {
1634
  SDValue Value;
1635
  int Weight;
1636
  int InsertionOrder;
1637
1638
255
  WeightedLeaf() : Value(SDValue()) { }
1639
1640
  WeightedLeaf(SDValue Value, int Weight, int InsertionOrder) :
1641
217
    Value(Value), Weight(Weight), InsertionOrder(InsertionOrder) {
1642
217
    assert(Weight >= 0 && "Weight must be >= 0");
1643
217
  }
1644
1645
184
  static bool Compare(const WeightedLeaf &A, const WeightedLeaf &B) {
1646
184
    assert(A.Value.getNode() && B.Value.getNode());
1647
184
    return A.Weight == B.Weight ?
1648
50
            (A.InsertionOrder > B.InsertionOrder) :
1649
184
            
(A.Weight > B.Weight)134
;
1650
184
  }
1651
};
1652
1653
/// A specialized priority queue for WeigthedLeaves. It automatically folds
1654
/// constants and allows removal of non-top elements while maintaining the
1655
/// priority order.
1656
class LeafPrioQueue {
1657
  SmallVector<WeightedLeaf, 8> Q;
1658
  bool HaveConst;
1659
  WeightedLeaf ConstElt;
1660
  unsigned Opcode;
1661
1662
public:
1663
0
  bool empty() {
1664
0
    return (!HaveConst && Q.empty());
1665
0
  }
1666
1667
128
  size_t size() {
1668
128
    return Q.size() + HaveConst;
1669
128
  }
1670
1671
35
  bool hasConst() {
1672
35
    return HaveConst;
1673
35
  }
1674
1675
84
  const WeightedLeaf &top() {
1676
84
    if (HaveConst)
1677
0
      return ConstElt;
1678
84
    return Q.front();
1679
84
  }
1680
1681
201
  WeightedLeaf pop() {
1682
201
    if (HaveConst) {
1683
29
      HaveConst = false;
1684
29
      return ConstElt;
1685
29
    }
1686
172
    std::pop_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1687
172
    return Q.pop_back_val();
1688
172
  }
1689
1690
244
  void push(WeightedLeaf L, bool SeparateConst=true) {
1691
244
    if (!HaveConst && 
SeparateConst237
&&
isa<ConstantSDNode>(L.Value)208
) {
1692
29
      if (Opcode == ISD::MUL &&
1693
29
          
cast<ConstantSDNode>(L.Value)->getSExtValue() == 10
)
1694
0
        return;
1695
29
      if (Opcode == ISD::ADD &&
1696
29
          cast<ConstantSDNode>(L.Value)->getSExtValue() == 0)
1697
0
        return;
1698
29
1699
29
      HaveConst = true;
1700
29
      ConstElt = L;
1701
215
    } else {
1702
215
      Q.push_back(L);
1703
215
      std::push_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1704
215
    }
1705
244
  }
1706
1707
  /// Push L to the bottom of the queue regardless of its weight. If L is
1708
  /// constant, it will not be folded with other constants in the queue.
1709
29
  void pushToBottom(WeightedLeaf L) {
1710
29
    L.Weight = 1000;
1711
29
    push(L, false);
1712
29
  }
1713
1714
  /// Search for a SHL(x, [<=MaxAmount]) subtree in the queue, return the one of
1715
  /// lowest weight and remove it from the queue.
1716
  WeightedLeaf findSHL(uint64_t MaxAmount);
1717
1718
  WeightedLeaf findMULbyConst();
1719
1720
  LeafPrioQueue(unsigned Opcode) :
1721
42
    HaveConst(false), Opcode(Opcode) { }
1722
};
1723
} // end anonymous namespace
1724
1725
1
WeightedLeaf LeafPrioQueue::findSHL(uint64_t MaxAmount) {
1726
1
  int ResultPos;
1727
1
  WeightedLeaf Result;
1728
1
1729
2
  for (int Pos = 0, End = Q.size(); Pos != End; 
++Pos1
) {
1730
1
    const WeightedLeaf &L = Q[Pos];
1731
1
    const SDValue &Val = L.Value;
1732
1
    if (Val.getOpcode() != ISD::SHL ||
1733
1
        !isa<ConstantSDNode>(Val.getOperand(1)) ||
1734
1
        Val.getConstantOperandVal(1) > MaxAmount)
1735
0
      continue;
1736
1
    if (!Result.Value.getNode() || 
Result.Weight > L.Weight0
||
1737
1
        
(0
Result.Weight == L.Weight0
&&
Result.InsertionOrder > L.InsertionOrder0
))
1738
1
    {
1739
1
      Result = L;
1740
1
      ResultPos = Pos;
1741
1
    }
1742
1
  }
1743
1
1744
1
  if (Result.Value.getNode()) {
1745
1
    Q.erase(&Q[ResultPos]);
1746
1
    std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1747
1
  }
1748
1
1749
1
  return Result;
1750
1
}
1751
1752
86
WeightedLeaf LeafPrioQueue::findMULbyConst() {
1753
86
  int ResultPos;
1754
86
  WeightedLeaf Result;
1755
86
1756
221
  for (int Pos = 0, End = Q.size(); Pos != End; 
++Pos135
) {
1757
135
    const WeightedLeaf &L = Q[Pos];
1758
135
    const SDValue &Val = L.Value;
1759
135
    if (Val.getOpcode() != ISD::MUL ||
1760
135
        
!isa<ConstantSDNode>(Val.getOperand(1))12
||
1761
135
        
Val.getConstantOperandVal(1) > 1270
)
1762
135
      continue;
1763
0
    if (!Result.Value.getNode() || Result.Weight > L.Weight ||
1764
0
        (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))
1765
0
    {
1766
0
      Result = L;
1767
0
      ResultPos = Pos;
1768
0
    }
1769
0
  }
1770
86
1771
86
  if (Result.Value.getNode()) {
1772
0
    Q.erase(&Q[ResultPos]);
1773
0
    std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1774
0
  }
1775
86
1776
86
  return Result;
1777
86
}
1778
1779
0
SDValue HexagonDAGToDAGISel::getMultiplierForSHL(SDNode *N) {
1780
0
  uint64_t MulFactor = 1ull << N->getConstantOperandVal(1);
1781
0
  return CurDAG->getConstant(MulFactor, SDLoc(N),
1782
0
                             N->getOperand(1).getValueType());
1783
0
}
1784
1785
/// @returns the value x for which 2^x is a factor of Val
1786
11
static unsigned getPowerOf2Factor(SDValue Val) {
1787
11
  if (Val.getOpcode() == ISD::MUL) {
1788
3
    unsigned MaxFactor = 0;
1789
9
    for (int i = 0; i < 2; 
++i6
) {
1790
6
      ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(i));
1791
6
      if (!C)
1792
5
        continue;
1793
1
      const APInt &CInt = C->getAPIntValue();
1794
1
      if (CInt.getBoolValue())
1795
1
        MaxFactor = CInt.countTrailingZeros();
1796
1
    }
1797
3
    return MaxFactor;
1798
3
  }
1799
8
  if (Val.getOpcode() == ISD::SHL) {
1800
8
    if (!isa<ConstantSDNode>(Val.getOperand(1).getNode()))
1801
0
      return 0;
1802
8
    return (unsigned) Val.getConstantOperandVal(1);
1803
8
  }
1804
0
1805
0
  return 0;
1806
0
}
1807
1808
/// @returns true if V>>Amount will eliminate V's operation on its child
1809
2
static bool willShiftRightEliminate(SDValue V, unsigned Amount) {
1810
2
  if (V.getOpcode() == ISD::MUL) {
1811
1
    SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };
1812
2
    for (int i = 0; i < 2; 
++i1
)
1813
2
      if (isa<ConstantSDNode>(Ops[i].getNode()) &&
1814
2
          
V.getConstantOperandVal(i) % (1ULL << Amount) == 01
) {
1815
1
        uint64_t NewConst = V.getConstantOperandVal(i) >> Amount;
1816
1
        return (NewConst == 1);
1817
1
      }
1818
1
  } else if (V.getOpcode() == ISD::SHL) {
1819
1
    return (Amount == V.getConstantOperandVal(1));
1820
1
  }
1821
0
1822
0
  return false;
1823
0
}
1824
1825
2
SDValue HexagonDAGToDAGISel::factorOutPowerOf2(SDValue V, unsigned Power) {
1826
2
  SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };
1827
2
  if (V.getOpcode() == ISD::MUL) {
1828
2
    for (int i=0; i < 2; 
++i1
) {
1829
2
      if (isa<ConstantSDNode>(Ops[i].getNode()) &&
1830
2
          
V.getConstantOperandVal(i) % ((uint64_t)1 << Power) == 01
) {
1831
1
        uint64_t NewConst = V.getConstantOperandVal(i) >> Power;
1832
1
        if (NewConst == 1)
1833
0
          return Ops[!i];
1834
1
        Ops[i] = CurDAG->getConstant(NewConst,
1835
1
                                     SDLoc(V), V.getValueType());
1836
1
        break;
1837
1
      }
1838
2
    }
1839
1
  } else if (V.getOpcode() == ISD::SHL) {
1840
1
    uint64_t ShiftAmount = V.getConstantOperandVal(1);
1841
1
    if (ShiftAmount == Power)
1842
1
      return Ops[0];
1843
0
    Ops[1] = CurDAG->getConstant(ShiftAmount - Power,
1844
0
                                 SDLoc(V), V.getValueType());
1845
0
  }
1846
2
1847
2
  
return CurDAG->getNode(V.getOpcode(), SDLoc(V), V.getValueType(), Ops)1
;
1848
2
}
1849
1850
99
static bool isTargetConstant(const SDValue &V) {
1851
99
  return V.getOpcode() == HexagonISD::CONST32 ||
1852
99
         
V.getOpcode() == HexagonISD::CONST32_GP98
;
1853
99
}
1854
1855
0
unsigned HexagonDAGToDAGISel::getUsesInFunction(const Value *V) {
1856
0
  if (GAUsesInFunction.count(V))
1857
0
    return GAUsesInFunction[V];
1858
0
1859
0
  unsigned Result = 0;
1860
0
  const Function &CurF = CurDAG->getMachineFunction().getFunction();
1861
0
  for (const User *U : V->users()) {
1862
0
    if (isa<Instruction>(U) &&
1863
0
        cast<Instruction>(U)->getParent()->getParent() == &CurF)
1864
0
      ++Result;
1865
0
  }
1866
0
1867
0
  GAUsesInFunction[V] = Result;
1868
0
1869
0
  return Result;
1870
0
}
1871
1872
/// Note - After calling this, N may be dead. It may have been replaced by a
1873
/// new node, so always use the returned value in place of N.
1874
///
1875
/// @returns The SDValue taking the place of N (which could be N if it is
1876
/// unchanged)
1877
1.39k
SDValue HexagonDAGToDAGISel::balanceSubTree(SDNode *N, bool TopLevel) {
1878
1.39k
  assert(RootWeights.count(N) && "Cannot balance non-root node.");
1879
1.39k
  assert(RootWeights[N] != -2 && "This node was RAUW'd!");
1880
1.39k
  assert(!TopLevel || N->getOpcode() == ISD::ADD);
1881
1.39k
1882
1.39k
  // Return early if this node was already visited
1883
1.39k
  if (RootWeights[N] != -1)
1884
0
    return SDValue(N, 0);
1885
1.39k
1886
1.39k
  assert(isOpcodeHandled(N));
1887
1.39k
1888
1.39k
  SDValue Op0 = N->getOperand(0);
1889
1.39k
  SDValue Op1 = N->getOperand(1);
1890
1.39k
1891
1.39k
  // Return early if the operands will remain unchanged or are all roots
1892
1.39k
  if ((!isOpcodeHandled(Op0.getNode()) || 
RootWeights.count(Op0.getNode())237
) &&
1893
1.39k
      
(1.35k
!isOpcodeHandled(Op1.getNode())1.35k
||
RootWeights.count(Op1.getNode())132
)) {
1894
1.35k
    SDNode *Op0N = Op0.getNode();
1895
1.35k
    int Weight;
1896
1.35k
    if (isOpcodeHandled(Op0N) && 
RootWeights[Op0N] == -1200
) {
1897
104
      Weight = getWeight(balanceSubTree(Op0N).getNode());
1898
104
      // Weight = calculateWeight(Op0N);
1899
104
    } else
1900
1.25k
      Weight = getWeight(Op0N);
1901
1.35k
1902
1.35k
    SDNode *Op1N = N->getOperand(1).getNode(); // Op1 may have been RAUWd
1903
1.35k
    if (isOpcodeHandled(Op1N) && 
RootWeights[Op1N] == -1127
) {
1904
111
      Weight += getWeight(balanceSubTree(Op1N).getNode());
1905
111
      // Weight += calculateWeight(Op1N);
1906
111
    } else
1907
1.24k
      Weight += getWeight(Op1N);
1908
1.35k
1909
1.35k
    RootWeights[N] = Weight;
1910
1.35k
    RootHeights[N] = std::max(getHeight(N->getOperand(0).getNode()),
1911
1.35k
                              getHeight(N->getOperand(1).getNode())) + 1;
1912
1.35k
1913
1.35k
    LLVM_DEBUG(dbgs() << "--> No need to balance root (Weight=" << Weight
1914
1.35k
                      << " Height=" << RootHeights[N] << "): ");
1915
1.35k
    LLVM_DEBUG(N->dump(CurDAG));
1916
1.35k
1917
1.35k
    return SDValue(N, 0);
1918
1.35k
  }
1919
42
1920
42
  LLVM_DEBUG(dbgs() << "** Balancing root node: ");
1921
42
  LLVM_DEBUG(N->dump(CurDAG));
1922
42
1923
42
  unsigned NOpcode = N->getOpcode();
1924
42
1925
42
  LeafPrioQueue Leaves(NOpcode);
1926
42
  SmallVector<SDValue, 4> Worklist;
1927
42
  Worklist.push_back(SDValue(N, 0));
1928
42
1929
42
  // SHL nodes will be converted to MUL nodes
1930
42
  if (NOpcode == ISD::SHL)
1931
0
    NOpcode = ISD::MUL;
1932
42
1933
42
  bool CanFactorize = false;
1934
42
  WeightedLeaf Mul1, Mul2;
1935
42
  unsigned MaxPowerOf2 = 0;
1936
42
  WeightedLeaf GA;
1937
42
1938
42
  // Do not try to factor out a shift if there is already a shift at the tip of
1939
42
  // the tree.
1940
42
  bool HaveTopLevelShift = false;
1941
42
  if (TopLevel &&
1942
42
      
(35
(35
isOpcodeHandled(Op0.getNode())35
&&
Op0.getOpcode() == ISD::SHL30
&&
1943
35
                        
Op0.getConstantOperandVal(1) < 40
) ||
1944
35
       (isOpcodeHandled(Op1.getNode()) && 
Op1.getOpcode() == ISD::SHL5
&&
1945
35
                        
Op1.getConstantOperandVal(1) < 40
)))
1946
0
    HaveTopLevelShift = true;
1947
42
1948
42
  // Flatten the subtree into an ordered list of leaves; at the same time
1949
42
  // determine whether the tree is already balanced.
1950
42
  int InsertionOrder = 0;
1951
42
  SmallDenseMap<SDValue, int> NodeHeights;
1952
42
  bool Imbalanced = false;
1953
42
  int CurrentWeight = 0;
1954
348
  while (!Worklist.empty()) {
1955
306
    SDValue Child = Worklist.pop_back_val();
1956
306
1957
306
    if (Child.getNode() != N && 
RootWeights.count(Child.getNode())222
) {
1958
31
      // CASE 1: Child is a root note
1959
31
1960
31
      int Weight = RootWeights[Child.getNode()];
1961
31
      if (Weight == -1) {
1962
19
        Child = balanceSubTree(Child.getNode());
1963
19
        // calculateWeight(Child.getNode());
1964
19
        Weight = getWeight(Child.getNode());
1965
19
      } else 
if (12
Weight == -212
) {
1966
0
        // Whoops, this node was RAUWd by one of the balanceSubTree calls we
1967
0
        // made. Our worklist isn't up to date anymore.
1968
0
        // Restart the whole process.
1969
0
        LLVM_DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");
1970
0
        return balanceSubTree(N, TopLevel);
1971
0
      }
1972
31
1973
31
      NodeHeights[Child] = 1;
1974
31
      CurrentWeight += Weight;
1975
31
1976
31
      unsigned PowerOf2;
1977
31
      if (TopLevel && 
!CanFactorize27
&&
!HaveTopLevelShift27
&&
1978
31
          
(27
Child.getOpcode() == ISD::MUL27
||
Child.getOpcode() == ISD::SHL24
) &&
1979
31
          
Child.hasOneUse()21
&&
(PowerOf2 = getPowerOf2Factor(Child))11
) {
1980
9
        // Try to identify two factorizable MUL/SHL children greedily. Leave
1981
9
        // them out of the priority queue for now so we can deal with them
1982
9
        // after.
1983
9
        if (!Mul1.Value.getNode()) {
1984
8
          Mul1 = WeightedLeaf(Child, Weight, InsertionOrder++);
1985
8
          MaxPowerOf2 = PowerOf2;
1986
8
        } else {
1987
1
          Mul2 = WeightedLeaf(Child, Weight, InsertionOrder++);
1988
1
          MaxPowerOf2 = std::min(MaxPowerOf2, PowerOf2);
1989
1
1990
1
          // Our addressing modes can only shift by a maximum of 3
1991
1
          if (MaxPowerOf2 > 3)
1992
0
            MaxPowerOf2 = 3;
1993
1
1994
1
          CanFactorize = true;
1995
1
        }
1996
9
      } else
1997
22
        Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
1998
275
    } else if (!isOpcodeHandled(Child.getNode())) {
1999
99
      // CASE 2: Child is an unhandled kind of node (e.g. constant)
2000
99
      int Weight = getWeight(Child.getNode());
2001
99
2002
99
      NodeHeights[Child] = getHeight(Child.getNode());
2003
99
      CurrentWeight += Weight;
2004
99
2005
99
      if (isTargetConstant(Child) && 
!GA.Value.getNode()1
)
2006
1
        GA = WeightedLeaf(Child, Weight, InsertionOrder++);
2007
98
      else
2008
98
        Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
2009
176
    } else {
2010
176
      // CASE 3: Child is a subtree of same opcode
2011
176
      // Visit children first, then flatten.
2012
176
      unsigned ChildOpcode = Child.getOpcode();
2013
176
      assert(ChildOpcode == NOpcode ||
2014
176
             (NOpcode == ISD::MUL && ChildOpcode == ISD::SHL));
2015
176
2016
176
      // Convert SHL to MUL
2017
176
      SDValue Op1;
2018
176
      if (ChildOpcode == ISD::SHL)
2019
0
        Op1 = getMultiplierForSHL(Child.getNode());
2020
176
      else
2021
176
        Op1 = Child->getOperand(1);
2022
176
2023
176
      if (!NodeHeights.count(Op1) || 
!NodeHeights.count(Child->getOperand(0))88
) {
2024
88
        assert(!NodeHeights.count(Child) && "Parent visited before children?");
2025
88
        // Visit children first, then re-visit this node
2026
88
        Worklist.push_back(Child);
2027
88
        Worklist.push_back(Op1);
2028
88
        Worklist.push_back(Child->getOperand(0));
2029
88
      } else {
2030
88
        // Back at this node after visiting the children
2031
88
        if (std::abs(NodeHeights[Op1] - NodeHeights[Child->getOperand(0)]) > 1)
2032
28
          Imbalanced = true;
2033
88
2034
88
        NodeHeights[Child] = std::max(NodeHeights[Op1],
2035
88
                                      NodeHeights[Child->getOperand(0)]) + 1;
2036
88
      }
2037
176
    }
2038
306
  }
2039
42
2040
42
  LLVM_DEBUG(dbgs() << "--> Current height=" << NodeHeights[SDValue(N, 0)]
2041
42
                    << " weight=" << CurrentWeight
2042
42
                    << " imbalanced=" << Imbalanced << "\n");
2043
42
2044
42
  // Transform MUL(x, C * 2^Y) + SHL(z, Y) -> SHL(ADD(MUL(x, C), z), Y)
2045
42
  //  This factors out a shift in order to match memw(a<<Y+b).
2046
42
  if (CanFactorize && 
(1
willShiftRightEliminate(Mul1.Value, MaxPowerOf2)1
||
2047
1
                       willShiftRightEliminate(Mul2.Value, MaxPowerOf2))) {
2048
1
    LLVM_DEBUG(dbgs() << "--> Found common factor for two MUL children!\n");
2049
1
    int Weight = Mul1.Weight + Mul2.Weight;
2050
1
    int Height = std::max(NodeHeights[Mul1.Value], NodeHeights[Mul2.Value]) + 1;
2051
1
    SDValue Mul1Factored = factorOutPowerOf2(Mul1.Value, MaxPowerOf2);
2052
1
    SDValue Mul2Factored = factorOutPowerOf2(Mul2.Value, MaxPowerOf2);
2053
1
    SDValue Sum = CurDAG->getNode(ISD::ADD, SDLoc(N), Mul1.Value.getValueType(),
2054
1
                                  Mul1Factored, Mul2Factored);
2055
1
    SDValue Const = CurDAG->getConstant(MaxPowerOf2, SDLoc(N),
2056
1
                                        Mul1.Value.getValueType());
2057
1
    SDValue New = CurDAG->getNode(ISD::SHL, SDLoc(N), Mul1.Value.getValueType(),
2058
1
                                  Sum, Const);
2059
1
    NodeHeights[New] = Height;
2060
1
    Leaves.push(WeightedLeaf(New, Weight, Mul1.InsertionOrder));
2061
41
  } else if (Mul1.Value.getNode()) {
2062
7
    // We failed to factorize two MULs, so now the Muls are left outside the
2063
7
    // queue... add them back.
2064
7
    Leaves.push(Mul1);
2065
7
    if (Mul2.Value.getNode())
2066
0
      Leaves.push(Mul2);
2067
7
    CanFactorize = false;
2068
7
  }
2069
42
2070
42
  // Combine GA + Constant -> GA+Offset, but only if GA is not used elsewhere
2071
42
  // and the root node itself is not used more than twice. This reduces the
2072
42
  // amount of additional constant extenders introduced by this optimization.
2073
42
  bool CombinedGA = false;
2074
42
  if (NOpcode == ISD::ADD && GA.Value.getNode() && 
Leaves.hasConst()1
&&
2075
42
      
GA.Value.hasOneUse()0
&&
N->use_size() < 30
) {
2076
0
    GlobalAddressSDNode *GANode =
2077
0
      cast<GlobalAddressSDNode>(GA.Value.getOperand(0));
2078
0
    ConstantSDNode *Offset = cast<ConstantSDNode>(Leaves.top().Value);
2079
0
2080
0
    if (getUsesInFunction(GANode->getGlobal()) == 1 && Offset->hasOneUse() &&
2081
0
        getTargetLowering()->isOffsetFoldingLegal(GANode)) {
2082
0
      LLVM_DEBUG(dbgs() << "--> Combining GA and offset ("
2083
0
                        << Offset->getSExtValue() << "): ");
2084
0
      LLVM_DEBUG(GANode->dump(CurDAG));
2085
0
2086
0
      SDValue NewTGA =
2087
0
        CurDAG->getTargetGlobalAddress(GANode->getGlobal(), SDLoc(GA.Value),
2088
0
            GANode->getValueType(0),
2089
0
            GANode->getOffset() + (uint64_t)Offset->getSExtValue());
2090
0
      GA.Value = CurDAG->getNode(GA.Value.getOpcode(), SDLoc(GA.Value),
2091
0
          GA.Value.getValueType(), NewTGA);
2092
0
      GA.Weight += Leaves.top().Weight;
2093
0
2094
0
      NodeHeights[GA.Value] = getHeight(GA.Value.getNode());
2095
0
      CombinedGA = true;
2096
0
2097
0
      Leaves.pop(); // Remove the offset constant from the queue
2098
0
    }
2099
0
  }
2100
42
2101
42
  if ((RebalanceOnlyForOptimizations && 
!CanFactorize0
&&
!CombinedGA0
) ||
2102
42
      (RebalanceOnlyImbalancedTrees && 
!Imbalanced0
)) {
2103
0
    RootWeights[N] = CurrentWeight;
2104
0
    RootHeights[N] = NodeHeights[SDValue(N, 0)];
2105
0
2106
0
    return SDValue(N, 0);
2107
0
  }
2108
42
2109
42
  // Combine GA + SHL(x, C<=31) so we will match Rx=add(#u8,asl(Rx,#U5))
2110
42
  if (NOpcode == ISD::ADD && GA.Value.getNode()) {
2111
1
    WeightedLeaf SHL = Leaves.findSHL(31);
2112
1
    if (SHL.Value.getNode()) {
2113
1
      int Height = std::max(NodeHeights[GA.Value], NodeHeights[SHL.Value]) + 1;
2114
1
      GA.Value = CurDAG->getNode(ISD::ADD, SDLoc(GA.Value),
2115
1
                                 GA.Value.getValueType(),
2116
1
                                 GA.Value, SHL.Value);
2117
1
      GA.Weight = SHL.Weight; // Specifically ignore the GA weight here
2118
1
      NodeHeights[GA.Value] = Height;
2119
1
    }
2120
1
  }
2121
42
2122
42
  if (GA.Value.getNode())
2123
1
    Leaves.push(GA);
2124
42
2125
42
  // If this is the top level and we haven't factored out a shift, we should try
2126
42
  // to move a constant to the bottom to match addressing modes like memw(rX+C)
2127
42
  if (TopLevel && 
!CanFactorize35
&&
Leaves.hasConst()34
) {
2128
29
    LLVM_DEBUG(dbgs() << "--> Pushing constant to tip of tree.");
2129
29
    Leaves.pushToBottom(Leaves.pop());
2130
29
  }
2131
42
2132
42
  const DataLayout &DL = CurDAG->getDataLayout();
2133
42
  const TargetLowering &TLI = *getTargetLowering();
2134
42
2135
42
  // Rebuild the tree using Huffman's algorithm
2136
128
  while (Leaves.size() > 1) {
2137
86
    WeightedLeaf L0 = Leaves.pop();
2138
86
2139
86
    // See whether we can grab a MUL to form an add(Rx,mpyi(Ry,#u6)),
2140
86
    // otherwise just get the next leaf
2141
86
    WeightedLeaf L1 = Leaves.findMULbyConst();
2142
86
    if (!L1.Value.getNode())
2143
86
      L1 = Leaves.pop();
2144
86
2145
86
    assert(L0.Weight <= L1.Weight && "Priority queue is broken!");
2146
86
2147
86
    SDValue V0 = L0.Value;
2148
86
    int V0Weight = L0.Weight;
2149
86
    SDValue V1 = L1.Value;
2150
86
    int V1Weight = L1.Weight;
2151
86
2152
86
    // Make sure that none of these nodes have been RAUW'd
2153
86
    if ((RootWeights.count(V0.getNode()) && 
RootWeights[V0.getNode()] == -27
) ||
2154
86
        (RootWeights.count(V1.getNode()) && 
RootWeights[V1.getNode()] == -223
)) {
2155
0
      LLVM_DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");
2156
0
      return balanceSubTree(N, TopLevel);
2157
0
    }
2158
86
2159
86
    ConstantSDNode *V0C = dyn_cast<ConstantSDNode>(V0);
2160
86
    ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(V1);
2161
86
    EVT VT = N->getValueType(0);
2162
86
    SDValue NewNode;
2163
86
2164
86
    if (V0C && 
!V1C0
) {
2165
0
      std::swap(V0, V1);
2166
0
      std::swap(V0C, V1C);
2167
0
    }
2168
86
2169
86
    // Calculate height of this node
2170
86
    assert(NodeHeights.count(V0) && NodeHeights.count(V1) &&
2171
86
           "Children must have been visited before re-combining them!");
2172
86
    int Height = std::max(NodeHeights[V0], NodeHeights[V1]) + 1;
2173
86
2174
86
    // Rebuild this node (and restore SHL from MUL if needed)
2175
86
    if (V1C && 
NOpcode == ISD::MUL29
&&
V1C->getAPIntValue().isPowerOf2()0
)
2176
0
      NewNode = CurDAG->getNode(
2177
0
          ISD::SHL, SDLoc(V0), VT, V0,
2178
0
          CurDAG->getConstant(
2179
0
              V1C->getAPIntValue().logBase2(), SDLoc(N),
2180
0
              TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
2181
86
    else
2182
86
      NewNode = CurDAG->getNode(NOpcode, SDLoc(N), VT, V0, V1);
2183
86
2184
86
    NodeHeights[NewNode] = Height;
2185
86
2186
86
    int Weight = V0Weight + V1Weight;
2187
86
    Leaves.push(WeightedLeaf(NewNode, Weight, L0.InsertionOrder));
2188
86
2189
86
    LLVM_DEBUG(dbgs() << "--> Built new node (Weight=" << Weight
2190
86
                      << ",Height=" << Height << "):\n");
2191
86
    LLVM_DEBUG(NewNode.dump());
2192
86
  }
2193
42
2194
42
  assert(Leaves.size() == 1);
2195
42
  SDValue NewRoot = Leaves.top().Value;
2196
42
2197
42
  assert(NodeHeights.count(NewRoot));
2198
42
  int Height = NodeHeights[NewRoot];
2199
42
2200
42
  // Restore SHL if we earlier converted it to a MUL
2201
42
  if (NewRoot.getOpcode() == ISD::MUL) {
2202
0
    ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(NewRoot.getOperand(1));
2203
0
    if (V1C && V1C->getAPIntValue().isPowerOf2()) {
2204
0
      EVT VT = NewRoot.getValueType();
2205
0
      SDValue V0 = NewRoot.getOperand(0);
2206
0
      NewRoot = CurDAG->getNode(
2207
0
          ISD::SHL, SDLoc(NewRoot), VT, V0,
2208
0
          CurDAG->getConstant(
2209
0
              V1C->getAPIntValue().logBase2(), SDLoc(NewRoot),
2210
0
              TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
2211
0
    }
2212
0
  }
2213
42
2214
42
  if (N != NewRoot.getNode()) {
2215
25
    LLVM_DEBUG(dbgs() << "--> Root is now: ");
2216
25
    LLVM_DEBUG(NewRoot.dump());
2217
25
2218
25
    // Replace all uses of old root by new root
2219
25
    CurDAG->ReplaceAllUsesWith(N, NewRoot.getNode());
2220
25
    // Mark that we have RAUW'd N
2221
25
    RootWeights[N] = -2;
2222
25
  } else {
2223
17
    LLVM_DEBUG(dbgs() << "--> Root unchanged.\n");
2224
17
  }
2225
42
2226
42
  RootWeights[NewRoot.getNode()] = Leaves.top().Weight;
2227
42
  RootHeights[NewRoot.getNode()] = Height;
2228
42
2229
42
  return NewRoot;
2230
42
}
2231
2232
6.63k
void HexagonDAGToDAGISel::rebalanceAddressTrees() {
2233
103k
  for (auto I = CurDAG->allnodes_begin(), E = CurDAG->allnodes_end(); I != E;) {
2234
96.5k
    SDNode *N = &*I++;
2235
96.5k
    if (N->getOpcode() != ISD::LOAD && 
N->getOpcode() != ISD::STORE93.3k
)
2236
90.5k
      continue;
2237
5.98k
2238
5.98k
    SDValue BasePtr = cast<MemSDNode>(N)->getBasePtr();
2239
5.98k
    if (BasePtr.getOpcode() != ISD::ADD)
2240
4.61k
      continue;
2241
1.37k
2242
1.37k
    // We've already processed this node
2243
1.37k
    if (RootWeights.count(BasePtr.getNode()))
2244
208
      continue;
2245
1.16k
2246
1.16k
    LLVM_DEBUG(dbgs() << "** Rebalancing address calculation in node: ");
2247
1.16k
    LLVM_DEBUG(N->dump(CurDAG));
2248
1.16k
2249
1.16k
    // FindRoots
2250
1.16k
    SmallVector<SDNode *, 4> Worklist;
2251
1.16k
2252
1.16k
    Worklist.push_back(BasePtr.getOperand(0).getNode());
2253
1.16k
    Worklist.push_back(BasePtr.getOperand(1).getNode());
2254
1.16k
2255
4.58k
    while (!Worklist.empty()) {
2256
3.42k
      SDNode *N = Worklist.pop_back_val();
2257
3.42k
      unsigned Opcode = N->getOpcode();
2258
3.42k
2259
3.42k
      if (!isOpcodeHandled(N))
2260
2.87k
        continue;
2261
551
2262
551
      Worklist.push_back(N->getOperand(0).getNode());
2263
551
      Worklist.push_back(N->getOperand(1).getNode());
2264
551
2265
551
      // Not a root if it has only one use and same opcode as its parent
2266
551
      if (N->hasOneUse() && 
Opcode == N->use_begin()->getOpcode()335
)
2267
64
        continue;
2268
487
2269
487
      // This root node has already been processed
2270
487
      if (RootWeights.count(N))
2271
249
        continue;
2272
238
2273
238
      RootWeights[N] = -1;
2274
238
    }
2275
1.16k
2276
1.16k
    // Balance node itself
2277
1.16k
    RootWeights[BasePtr.getNode()] = -1;
2278
1.16k
    SDValue NewBasePtr = balanceSubTree(BasePtr.getNode(), /*TopLevel=*/ true);
2279
1.16k
2280
1.16k
    if (N->getOpcode() == ISD::LOAD)
2281
746
      N = CurDAG->UpdateNodeOperands(N, N->getOperand(0),
2282
746
            NewBasePtr, N->getOperand(2));
2283
416
    else
2284
416
      N = CurDAG->UpdateNodeOperands(N, N->getOperand(0), N->getOperand(1),
2285
416
            NewBasePtr, N->getOperand(3));
2286
1.16k
2287
1.16k
    LLVM_DEBUG(dbgs() << "--> Final node: ");
2288
1.16k
    LLVM_DEBUG(N->dump(CurDAG));
2289
1.16k
  }
2290
6.63k
2291
6.63k
  CurDAG->RemoveDeadNodes();
2292
6.63k
  GAUsesInFunction.clear();
2293
6.63k
  RootHeights.clear();
2294
6.63k
  RootWeights.clear();
2295
6.63k
}