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