1	//===- FastISel.cpp - Implementation of the FastISel class ----------------===//
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 contains the implementation of the FastISel class.
10	//
11	// "Fast" instruction selection is designed to emit very poor code quickly.
12	// Also, it is not designed to be able to do much lowering, so most illegal
13	// types (e.g. i64 on 32-bit targets) and operations are not supported. It is
14	// also not intended to be able to do much optimization, except in a few cases
15	// where doing optimizations reduces overall compile time. For example, folding
16	// constants into immediate fields is often done, because it's cheap and it
17	// reduces the number of instructions later phases have to examine.
18	//
19	// "Fast" instruction selection is able to fail gracefully and transfer
20	// control to the SelectionDAG selector for operations that it doesn't
21	// support. In many cases, this allows us to avoid duplicating a lot of
22	// the complicated lowering logic that SelectionDAG currently has.
23	//
24	// The intended use for "fast" instruction selection is "-O0" mode
25	// compilation, where the quality of the generated code is irrelevant when
26	// weighed against the speed at which the code can be generated. Also,
27	// at -O0, the LLVM optimizers are not running, and this makes the
28	// compile time of codegen a much higher portion of the overall compile
29	// time. Despite its limitations, "fast" instruction selection is able to
30	// handle enough code on its own to provide noticeable overall speedups
31	// in -O0 compiles.
32	//
33	// Basic operations are supported in a target-independent way, by reading
34	// the same instruction descriptions that the SelectionDAG selector reads,
35	// and identifying simple arithmetic operations that can be directly selected
36	// from simple operators. More complicated operations currently require
37	// target-specific code.
38	//
39	//===----------------------------------------------------------------------===//
40
41	#include "llvm/CodeGen/FastISel.h"
42	#include "llvm/ADT/APFloat.h"
43	#include "llvm/ADT/APSInt.h"
44	#include "llvm/ADT/DenseMap.h"
45	#include "llvm/ADT/SmallPtrSet.h"
46	#include "llvm/ADT/SmallString.h"
47	#include "llvm/ADT/SmallVector.h"
48	#include "llvm/ADT/Statistic.h"
49	#include "llvm/Analysis/BranchProbabilityInfo.h"
50	#include "llvm/Analysis/TargetLibraryInfo.h"
51	#include "llvm/CodeGen/Analysis.h"
52	#include "llvm/CodeGen/FunctionLoweringInfo.h"
53	#include "llvm/CodeGen/ISDOpcodes.h"
54	#include "llvm/CodeGen/MachineBasicBlock.h"
55	#include "llvm/CodeGen/MachineFrameInfo.h"
56	#include "llvm/CodeGen/MachineInstr.h"
57	#include "llvm/CodeGen/MachineInstrBuilder.h"
58	#include "llvm/CodeGen/MachineMemOperand.h"
59	#include "llvm/CodeGen/MachineModuleInfo.h"
60	#include "llvm/CodeGen/MachineOperand.h"
61	#include "llvm/CodeGen/MachineRegisterInfo.h"
62	#include "llvm/CodeGen/StackMaps.h"
63	#include "llvm/CodeGen/TargetInstrInfo.h"
64	#include "llvm/CodeGen/TargetLowering.h"
65	#include "llvm/CodeGen/TargetSubtargetInfo.h"
66	#include "llvm/CodeGen/ValueTypes.h"
67	#include "llvm/CodeGenTypes/MachineValueType.h"
68	#include "llvm/IR/Argument.h"
69	#include "llvm/IR/Attributes.h"
70	#include "llvm/IR/BasicBlock.h"
71	#include "llvm/IR/CallingConv.h"
72	#include "llvm/IR/Constant.h"
73	#include "llvm/IR/Constants.h"
74	#include "llvm/IR/DataLayout.h"
75	#include "llvm/IR/DebugLoc.h"
76	#include "llvm/IR/DerivedTypes.h"
77	#include "llvm/IR/DiagnosticInfo.h"
78	#include "llvm/IR/Function.h"
79	#include "llvm/IR/GetElementPtrTypeIterator.h"
80	#include "llvm/IR/GlobalValue.h"
81	#include "llvm/IR/InlineAsm.h"
82	#include "llvm/IR/InstrTypes.h"
83	#include "llvm/IR/Instruction.h"
84	#include "llvm/IR/Instructions.h"
85	#include "llvm/IR/IntrinsicInst.h"
86	#include "llvm/IR/LLVMContext.h"
87	#include "llvm/IR/Mangler.h"
88	#include "llvm/IR/Metadata.h"
89	#include "llvm/IR/Operator.h"
90	#include "llvm/IR/PatternMatch.h"
91	#include "llvm/IR/Type.h"
92	#include "llvm/IR/User.h"
93	#include "llvm/IR/Value.h"
94	#include "llvm/MC/MCContext.h"
95	#include "llvm/MC/MCInstrDesc.h"
96	#include "llvm/Support/Casting.h"
97	#include "llvm/Support/Debug.h"
98	#include "llvm/Support/ErrorHandling.h"
99	#include "llvm/Support/MathExtras.h"
100	#include "llvm/Support/raw_ostream.h"
101	#include "llvm/Target/TargetMachine.h"
102	#include "llvm/Target/TargetOptions.h"
103	#include <algorithm>
104	#include <cassert>
105	#include <cstdint>
106	#include <iterator>
107	#include <optional>
108	#include <utility>
109
110	using namespace llvm;
111	using namespace PatternMatch;
112
113	#define DEBUG_TYPE "isel"
114
115	STATISTIC(NumFastIselSuccessIndependent, "Number of insts selected by "
116	"target-independent selector");
117	STATISTIC(NumFastIselSuccessTarget, "Number of insts selected by "
118	"target-specific selector");
119	STATISTIC(NumFastIselDead, "Number of dead insts removed on failure");
120
121	/// Set the current block to which generated machine instructions will be
122	/// appended.
123	void FastISel::startNewBlock() {
124	assert(LocalValueMap.empty() &&
125	"local values should be cleared after finishing a BB");
126
127	// Instructions are appended to FuncInfo.MBB. If the basic block already
128	// contains labels or copies, use the last instruction as the last local
129	// value.
130	EmitStartPt = nullptr;
131	if (!FuncInfo.MBB->empty())
132	EmitStartPt = &FuncInfo.MBB->back();
133	LastLocalValue = EmitStartPt;
134	}
135
136	void FastISel::finishBasicBlock() { flushLocalValueMap(); }
137
138	bool FastISel::lowerArguments() {
139	if (!FuncInfo.CanLowerReturn)
140	// Fallback to SDISel argument lowering code to deal with sret pointer
141	// parameter.
142	return false;
143
144	if (!fastLowerArguments())
145	return false;
146
147	// Enter arguments into ValueMap for uses in non-entry BBs.
148	for (Function::const_arg_iterator I = FuncInfo.Fn->arg_begin(),
149	E = FuncInfo.Fn->arg_end();
150	I != E; ++I) {
151	DenseMap<const Value *, Register>::iterator VI = LocalValueMap.find(Val: &*I);
152	assert(VI != LocalValueMap.end() && "Missed an argument?");
153	FuncInfo.ValueMap[&*I] = VI->second;
154	}
155	return true;
156	}
157
158	/// Return the defined register if this instruction defines exactly one
159	/// virtual register and uses no other virtual registers. Otherwise return 0.
160	static Register findLocalRegDef(MachineInstr &MI) {
161	Register RegDef;
162	for (const MachineOperand &MO : MI.operands()) {
163	if (!MO.isReg())
164	continue;
165	if (MO.isDef()) {
166	if (RegDef)
167	return Register();
168	RegDef = MO.getReg();
169	} else if (MO.getReg().isVirtual()) {
170	// This is another use of a vreg. Don't delete it.
171	return Register();
172	}
173	}
174	return RegDef;
175	}
176
177	static bool isRegUsedByPhiNodes(Register DefReg,
178	FunctionLoweringInfo &FuncInfo) {
179	for (auto &P : FuncInfo.PHINodesToUpdate)
180	if (P.second == DefReg)
181	return true;
182	return false;
183	}
184
185	void FastISel::flushLocalValueMap() {
186	// If FastISel bails out, it could leave local value instructions behind
187	// that aren't used for anything. Detect and erase those.
188	if (LastLocalValue != EmitStartPt) {
189	// Save the first instruction after local values, for later.
190	MachineBasicBlock::iterator FirstNonValue(LastLocalValue);
191	++FirstNonValue;
192
193	MachineBasicBlock::reverse_iterator RE =
194	EmitStartPt ? MachineBasicBlock::reverse_iterator(EmitStartPt)
195	: FuncInfo.MBB->rend();
196	MachineBasicBlock::reverse_iterator RI(LastLocalValue);
197	for (MachineInstr &LocalMI :
198	llvm::make_early_inc_range(Range: llvm::make_range(x: RI, y: RE))) {
199	Register DefReg = findLocalRegDef(MI&: LocalMI);
200	if (!DefReg)
201	continue;
202	if (FuncInfo.RegsWithFixups.count(V: DefReg))
203	continue;
204	bool UsedByPHI = isRegUsedByPhiNodes(DefReg, FuncInfo);
205	if (!UsedByPHI && MRI.use_nodbg_empty(RegNo: DefReg)) {
206	if (EmitStartPt == &LocalMI)
207	EmitStartPt = EmitStartPt->getPrevNode();
208	LLVM_DEBUG(dbgs() << "removing dead local value materialization"
209	<< LocalMI);
210	LocalMI.eraseFromParent();
211	}
212	}
213
214	if (FirstNonValue != FuncInfo.MBB->end()) {
215	// See if there are any local value instructions left. If so, we want to
216	// make sure the first one has a debug location; if it doesn't, use the
217	// first non-value instruction's debug location.
218
219	// If EmitStartPt is non-null, this block had copies at the top before
220	// FastISel started doing anything; it points to the last one, so the
221	// first local value instruction is the one after EmitStartPt.
222	// If EmitStartPt is null, the first local value instruction is at the
223	// top of the block.
224	MachineBasicBlock::iterator FirstLocalValue =
225	EmitStartPt ? ++MachineBasicBlock::iterator(EmitStartPt)
226	: FuncInfo.MBB->begin();
227	if (FirstLocalValue != FirstNonValue && !FirstLocalValue->getDebugLoc())
228	FirstLocalValue->setDebugLoc(FirstNonValue->getDebugLoc());
229	}
230	}
231
232	LocalValueMap.clear();
233	LastLocalValue = EmitStartPt;
234	recomputeInsertPt();
235	SavedInsertPt = FuncInfo.InsertPt;
236	}
237
238	Register FastISel::getRegForValue(const Value *V) {
239	EVT RealVT = TLI.getValueType(DL, Ty: V->getType(), /*AllowUnknown=*/true);
240	// Don't handle non-simple values in FastISel.
241	if (!RealVT.isSimple())
242	return Register();
243
244	// Ignore illegal types. We must do this before looking up the value
245	// in ValueMap because Arguments are given virtual registers regardless
246	// of whether FastISel can handle them.
247	MVT VT = RealVT.getSimpleVT();
248	if (!TLI.isTypeLegal(VT)) {
249	// Handle integer promotions, though, because they're common and easy.
250	if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)
251	VT = TLI.getTypeToTransformTo(Context&: V->getContext(), VT).getSimpleVT();
252	else
253	return Register();
254	}
255
256	// Look up the value to see if we already have a register for it.
257	Register Reg = lookUpRegForValue(V);
258	if (Reg)
259	return Reg;
260
261	// In bottom-up mode, just create the virtual register which will be used
262	// to hold the value. It will be materialized later.
263	if (isa<Instruction>(Val: V) &&
264	(!isa<AllocaInst>(Val: V) ||
265	!FuncInfo.StaticAllocaMap.count(Val: cast<AllocaInst>(Val: V))))
266	return FuncInfo.InitializeRegForValue(V);
267
268	SavePoint SaveInsertPt = enterLocalValueArea();
269
270	// Materialize the value in a register. Emit any instructions in the
271	// local value area.
272	Reg = materializeRegForValue(V, VT);
273
274	leaveLocalValueArea(Old: SaveInsertPt);
275
276	return Reg;
277	}
278
279	Register FastISel::materializeConstant(const Value *V, MVT VT) {
280	Register Reg;
281	if (const auto *CI = dyn_cast<ConstantInt>(Val: V)) {
282	if (CI->getValue().getActiveBits() <= 64)
283	Reg = fastEmit_i(VT, RetVT: VT, Opcode: ISD::Constant, Imm: CI->getZExtValue());
284	} else if (isa<AllocaInst>(Val: V))
285	Reg = fastMaterializeAlloca(C: cast<AllocaInst>(Val: V));
286	else if (isa<ConstantPointerNull>(Val: V))
287	// Translate this as an integer zero so that it can be
288	// local-CSE'd with actual integer zeros.
289	Reg =
290	getRegForValue(V: Constant::getNullValue(Ty: DL.getIntPtrType(V->getType())));
291	else if (const auto *CF = dyn_cast<ConstantFP>(Val: V)) {
292	if (CF->isNullValue())
293	Reg = fastMaterializeFloatZero(CF);
294	else
295	// Try to emit the constant directly.
296	Reg = fastEmit_f(VT, RetVT: VT, Opcode: ISD::ConstantFP, FPImm: CF);
297
298	if (!Reg) {
299	// Try to emit the constant by using an integer constant with a cast.
300	const APFloat &Flt = CF->getValueAPF();
301	EVT IntVT = TLI.getPointerTy(DL);
302	uint32_t IntBitWidth = IntVT.getSizeInBits();
303	APSInt SIntVal(IntBitWidth, /*isUnsigned=*/false);
304	bool isExact;
305	(void)Flt.convertToInteger(Result&: SIntVal, RM: APFloat::rmTowardZero, IsExact: &isExact);
306	if (isExact) {
307	Register IntegerReg =
308	getRegForValue(V: ConstantInt::get(Context&: V->getContext(), V: SIntVal));
309	if (IntegerReg)
310	Reg = fastEmit_r(VT: IntVT.getSimpleVT(), RetVT: VT, Opcode: ISD::SINT_TO_FP,
311	Op0: IntegerReg);
312	}
313	}
314	} else if (const auto *Op = dyn_cast<Operator>(Val: V)) {
315	if (!selectOperator(I: Op, Opcode: Op->getOpcode()))
316	if (!isa<Instruction>(Val: Op) ||
317	!fastSelectInstruction(I: cast<Instruction>(Val: Op)))
318	return 0;
319	Reg = lookUpRegForValue(V: Op);
320	} else if (isa<UndefValue>(Val: V)) {
321	Reg = createResultReg(RC: TLI.getRegClassFor(VT));
322	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD,
323	MCID: TII.get(Opcode: TargetOpcode::IMPLICIT_DEF), DestReg: Reg);
324	}
325	return Reg;
326	}
327
328	/// Helper for getRegForValue. This function is called when the value isn't
329	/// already available in a register and must be materialized with new
330	/// instructions.
331	Register FastISel::materializeRegForValue(const Value *V, MVT VT) {
332	Register Reg;
333	// Give the target-specific code a try first.
334	if (isa<Constant>(Val: V))
335	Reg = fastMaterializeConstant(C: cast<Constant>(Val: V));
336
337	// If target-specific code couldn't or didn't want to handle the value, then
338	// give target-independent code a try.
339	if (!Reg)
340	Reg = materializeConstant(V, VT);
341
342	// Don't cache constant materializations in the general ValueMap.
343	// To do so would require tracking what uses they dominate.
344	if (Reg) {
345	LocalValueMap[V] = Reg;
346	LastLocalValue = MRI.getVRegDef(Reg);
347	}
348	return Reg;
349	}
350
351	Register FastISel::lookUpRegForValue(const Value *V) {
352	// Look up the value to see if we already have a register for it. We
353	// cache values defined by Instructions across blocks, and other values
354	// only locally. This is because Instructions already have the SSA
355	// def-dominates-use requirement enforced.
356	DenseMap<const Value *, Register>::iterator I = FuncInfo.ValueMap.find(Val: V);
357	if (I != FuncInfo.ValueMap.end())
358	return I->second;
359	return LocalValueMap[V];
360	}
361
362	void FastISel::updateValueMap(const Value *I, Register Reg, unsigned NumRegs) {
363	if (!isa<Instruction>(Val: I)) {
364	LocalValueMap[I] = Reg;
365	return;
366	}
367
368	Register &AssignedReg = FuncInfo.ValueMap[I];
369	if (!AssignedReg)
370	// Use the new register.
371	AssignedReg = Reg;
372	else if (Reg != AssignedReg) {
373	// Arrange for uses of AssignedReg to be replaced by uses of Reg.
374	for (unsigned i = 0; i < NumRegs; i++) {
375	FuncInfo.RegFixups[AssignedReg + i] = Reg + i;
376	FuncInfo.RegsWithFixups.insert(V: Reg + i);
377	}
378
379	AssignedReg = Reg;
380	}
381	}
382
383	Register FastISel::getRegForGEPIndex(const Value *Idx) {
384	Register IdxN = getRegForValue(V: Idx);
385	if (!IdxN)
386	// Unhandled operand. Halt "fast" selection and bail.
387	return Register();
388
389	// If the index is smaller or larger than intptr_t, truncate or extend it.
390	MVT PtrVT = TLI.getPointerTy(DL);
391	EVT IdxVT = EVT::getEVT(Ty: Idx->getType(), /*HandleUnknown=*/false);
392	if (IdxVT.bitsLT(VT: PtrVT)) {
393	IdxN = fastEmit_r(VT: IdxVT.getSimpleVT(), RetVT: PtrVT, Opcode: ISD::SIGN_EXTEND, Op0: IdxN);
394	} else if (IdxVT.bitsGT(VT: PtrVT)) {
395	IdxN =
396	fastEmit_r(VT: IdxVT.getSimpleVT(), RetVT: PtrVT, Opcode: ISD::TRUNCATE, Op0: IdxN);
397	}
398	return IdxN;
399	}
400
401	void FastISel::recomputeInsertPt() {
402	if (getLastLocalValue()) {
403	FuncInfo.InsertPt = getLastLocalValue();
404	FuncInfo.MBB = FuncInfo.InsertPt->getParent();
405	++FuncInfo.InsertPt;
406	} else
407	FuncInfo.InsertPt = FuncInfo.MBB->getFirstNonPHI();
408	}
409
410	void FastISel::removeDeadCode(MachineBasicBlock::iterator I,
411	MachineBasicBlock::iterator E) {
412	assert(I.isValid() && E.isValid() && std::distance(I, E) > 0 &&
413	"Invalid iterator!");
414	while (I != E) {
415	if (SavedInsertPt == I)
416	SavedInsertPt = E;
417	if (EmitStartPt == I)
418	EmitStartPt = E.isValid() ? &*E : nullptr;
419	if (LastLocalValue == I)
420	LastLocalValue = E.isValid() ? &*E : nullptr;
421
422	MachineInstr *Dead = &*I;
423	++I;
424	Dead->eraseFromParent();
425	++NumFastIselDead;
426	}
427	recomputeInsertPt();
428	}
429
430	FastISel::SavePoint FastISel::enterLocalValueArea() {
431	SavePoint OldInsertPt = FuncInfo.InsertPt;
432	recomputeInsertPt();
433	return OldInsertPt;
434	}
435
436	void FastISel::leaveLocalValueArea(SavePoint OldInsertPt) {
437	if (FuncInfo.InsertPt != FuncInfo.MBB->begin())
438	LastLocalValue = &*std::prev(x: FuncInfo.InsertPt);
439
440	// Restore the previous insert position.
441	FuncInfo.InsertPt = OldInsertPt;
442	}
443
444	bool FastISel::selectBinaryOp(const User *I, unsigned ISDOpcode) {
445	EVT VT = EVT::getEVT(Ty: I->getType(), /*HandleUnknown=*/true);
446	if (VT == MVT::Other || !VT.isSimple())
447	// Unhandled type. Halt "fast" selection and bail.
448	return false;
449
450	// We only handle legal types. For example, on x86-32 the instruction
451	// selector contains all of the 64-bit instructions from x86-64,
452	// under the assumption that i64 won't be used if the target doesn't
453	// support it.
454	if (!TLI.isTypeLegal(VT)) {
455	// MVT::i1 is special. Allow AND, OR, or XOR because they
456	// don't require additional zeroing, which makes them easy.
457	if (VT == MVT::i1 && ISD::isBitwiseLogicOp(Opcode: ISDOpcode))
458	VT = TLI.getTypeToTransformTo(Context&: I->getContext(), VT);
459	else
460	return false;
461	}
462
463	// Check if the first operand is a constant, and handle it as "ri". At -O0,
464	// we don't have anything that canonicalizes operand order.
465	if (const auto *CI = dyn_cast<ConstantInt>(Val: I->getOperand(i: 0)))
466	if (isa<Instruction>(Val: I) && cast<Instruction>(Val: I)->isCommutative()) {
467	Register Op1 = getRegForValue(V: I->getOperand(i: 1));
468	if (!Op1)
469	return false;
470
471	Register ResultReg =
472	fastEmit_ri_(VT: VT.getSimpleVT(), Opcode: ISDOpcode, Op0: Op1, Imm: CI->getZExtValue(),
473	ImmType: VT.getSimpleVT());
474	if (!ResultReg)
475	return false;
476
477	// We successfully emitted code for the given LLVM Instruction.
478	updateValueMap(I, Reg: ResultReg);
479	return true;
480	}
481
482	Register Op0 = getRegForValue(V: I->getOperand(i: 0));
483	if (!Op0) // Unhandled operand. Halt "fast" selection and bail.
484	return false;
485
486	// Check if the second operand is a constant and handle it appropriately.
487	if (const auto *CI = dyn_cast<ConstantInt>(Val: I->getOperand(i: 1))) {
488	uint64_t Imm = CI->getSExtValue();
489
490	// Transform "sdiv exact X, 8" -> "sra X, 3".
491	if (ISDOpcode == ISD::SDIV && isa<BinaryOperator>(Val: I) &&
492	cast<BinaryOperator>(Val: I)->isExact() && isPowerOf2_64(Value: Imm)) {
493	Imm = Log2_64(Value: Imm);
494	ISDOpcode = ISD::SRA;
495	}
496
497	// Transform "urem x, pow2" -> "and x, pow2-1".
498	if (ISDOpcode == ISD::UREM && isa<BinaryOperator>(Val: I) &&
499	isPowerOf2_64(Value: Imm)) {
500	--Imm;
501	ISDOpcode = ISD::AND;
502	}
503
504	Register ResultReg = fastEmit_ri_(VT: VT.getSimpleVT(), Opcode: ISDOpcode, Op0, Imm,
505	ImmType: VT.getSimpleVT());
506	if (!ResultReg)
507	return false;
508
509	// We successfully emitted code for the given LLVM Instruction.
510	updateValueMap(I, Reg: ResultReg);
511	return true;
512	}
513
514	Register Op1 = getRegForValue(V: I->getOperand(i: 1));
515	if (!Op1) // Unhandled operand. Halt "fast" selection and bail.
516	return false;
517
518	// Now we have both operands in registers. Emit the instruction.
519	Register ResultReg = fastEmit_rr(VT: VT.getSimpleVT(), RetVT: VT.getSimpleVT(),
520	Opcode: ISDOpcode, Op0, Op1);
521	if (!ResultReg)
522	// Target-specific code wasn't able to find a machine opcode for
523	// the given ISD opcode and type. Halt "fast" selection and bail.
524	return false;
525
526	// We successfully emitted code for the given LLVM Instruction.
527	updateValueMap(I, Reg: ResultReg);
528	return true;
529	}
530
531	bool FastISel::selectGetElementPtr(const User *I) {
532	Register N = getRegForValue(V: I->getOperand(i: 0));
533	if (!N) // Unhandled operand. Halt "fast" selection and bail.
534	return false;
535
536	// FIXME: The code below does not handle vector GEPs. Halt "fast" selection
537	// and bail.
538	if (isa<VectorType>(Val: I->getType()))
539	return false;
540
541	// Keep a running tab of the total offset to coalesce multiple N = N + Offset
542	// into a single N = N + TotalOffset.
543	uint64_t TotalOffs = 0;
544	// FIXME: What's a good SWAG number for MaxOffs?
545	uint64_t MaxOffs = 2048;
546	MVT VT = TLI.getPointerTy(DL);
547	for (gep_type_iterator GTI = gep_type_begin(GEP: I), E = gep_type_end(GEP: I);
548	GTI != E; ++GTI) {
549	const Value *Idx = GTI.getOperand();
550	if (StructType *StTy = GTI.getStructTypeOrNull()) {
551	uint64_t Field = cast<ConstantInt>(Val: Idx)->getZExtValue();
552	if (Field) {
553	// N = N + Offset
554	TotalOffs += DL.getStructLayout(Ty: StTy)->getElementOffset(Idx: Field);
555	if (TotalOffs >= MaxOffs) {
556	N = fastEmit_ri_(VT, Opcode: ISD::ADD, Op0: N, Imm: TotalOffs, ImmType: VT);
557	if (!N) // Unhandled operand. Halt "fast" selection and bail.
558	return false;
559	TotalOffs = 0;
560	}
561	}
562	} else {
563	// If this is a constant subscript, handle it quickly.
564	if (const auto *CI = dyn_cast<ConstantInt>(Val: Idx)) {
565	if (CI->isZero())
566	continue;
567	// N = N + Offset
568	uint64_t IdxN = CI->getValue().sextOrTrunc(width: 64).getSExtValue();
569	TotalOffs += GTI.getSequentialElementStride(DL) * IdxN;
570	if (TotalOffs >= MaxOffs) {
571	N = fastEmit_ri_(VT, Opcode: ISD::ADD, Op0: N, Imm: TotalOffs, ImmType: VT);
572	if (!N) // Unhandled operand. Halt "fast" selection and bail.
573	return false;
574	TotalOffs = 0;
575	}
576	continue;
577	}
578	if (TotalOffs) {
579	N = fastEmit_ri_(VT, Opcode: ISD::ADD, Op0: N, Imm: TotalOffs, ImmType: VT);
580	if (!N) // Unhandled operand. Halt "fast" selection and bail.
581	return false;
582	TotalOffs = 0;
583	}
584
585	// N = N + Idx * ElementSize;
586	uint64_t ElementSize = GTI.getSequentialElementStride(DL);
587	Register IdxN = getRegForGEPIndex(Idx);
588	if (!IdxN) // Unhandled operand. Halt "fast" selection and bail.
589	return false;
590
591	if (ElementSize != 1) {
592	IdxN = fastEmit_ri_(VT, Opcode: ISD::MUL, Op0: IdxN, Imm: ElementSize, ImmType: VT);
593	if (!IdxN) // Unhandled operand. Halt "fast" selection and bail.
594	return false;
595	}
596	N = fastEmit_rr(VT, RetVT: VT, Opcode: ISD::ADD, Op0: N, Op1: IdxN);
597	if (!N) // Unhandled operand. Halt "fast" selection and bail.
598	return false;
599	}
600	}
601	if (TotalOffs) {
602	N = fastEmit_ri_(VT, Opcode: ISD::ADD, Op0: N, Imm: TotalOffs, ImmType: VT);
603	if (!N) // Unhandled operand. Halt "fast" selection and bail.
604	return false;
605	}
606
607	// We successfully emitted code for the given LLVM Instruction.
608	updateValueMap(I, Reg: N);
609	return true;
610	}
611
612	bool FastISel::addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops,
613	const CallInst *CI, unsigned StartIdx) {
614	for (unsigned i = StartIdx, e = CI->arg_size(); i != e; ++i) {
615	Value *Val = CI->getArgOperand(i);
616	// Check for constants and encode them with a StackMaps::ConstantOp prefix.
617	if (const auto *C = dyn_cast<ConstantInt>(Val)) {
618	Ops.push_back(Elt: MachineOperand::CreateImm(Val: StackMaps::ConstantOp));
619	Ops.push_back(Elt: MachineOperand::CreateImm(Val: C->getSExtValue()));
620	} else if (isa<ConstantPointerNull>(Val)) {
621	Ops.push_back(Elt: MachineOperand::CreateImm(Val: StackMaps::ConstantOp));
622	Ops.push_back(Elt: MachineOperand::CreateImm(Val: 0));
623	} else if (auto *AI = dyn_cast<AllocaInst>(Val)) {
624	// Values coming from a stack location also require a special encoding,
625	// but that is added later on by the target specific frame index
626	// elimination implementation.
627	auto SI = FuncInfo.StaticAllocaMap.find(Val: AI);
628	if (SI != FuncInfo.StaticAllocaMap.end())
629	Ops.push_back(Elt: MachineOperand::CreateFI(Idx: SI->second));
630	else
631	return false;
632	} else {
633	Register Reg = getRegForValue(V: Val);
634	if (!Reg)
635	return false;
636	Ops.push_back(Elt: MachineOperand::CreateReg(Reg, /*isDef=*/false));
637	}
638	}
639	return true;
640	}
641
642	bool FastISel::selectStackmap(const CallInst *I) {
643	// void @llvm.experimental.stackmap(i64 <id>, i32 <numShadowBytes>,
644	// [live variables...])
645	assert(I->getCalledFunction()->getReturnType()->isVoidTy() &&
646	"Stackmap cannot return a value.");
647
648	// The stackmap intrinsic only records the live variables (the arguments
649	// passed to it) and emits NOPS (if requested). Unlike the patchpoint
650	// intrinsic, this won't be lowered to a function call. This means we don't
651	// have to worry about calling conventions and target-specific lowering code.
652	// Instead we perform the call lowering right here.
653	//
654	// CALLSEQ_START(0, 0...)
655	// STACKMAP(id, nbytes, ...)
656	// CALLSEQ_END(0, 0)
657	//
658	SmallVector<MachineOperand, 32> Ops;
659
660	// Add the <id> and <numBytes> constants.
661	assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
662	"Expected a constant integer.");
663	const auto *ID = cast<ConstantInt>(Val: I->getOperand(i_nocapture: PatchPointOpers::IDPos));
664	Ops.push_back(Elt: MachineOperand::CreateImm(Val: ID->getZExtValue()));
665
666	assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
667	"Expected a constant integer.");
668	const auto *NumBytes =
669	cast<ConstantInt>(Val: I->getOperand(i_nocapture: PatchPointOpers::NBytesPos));
670	Ops.push_back(Elt: MachineOperand::CreateImm(Val: NumBytes->getZExtValue()));
671
672	// Push live variables for the stack map (skipping the first two arguments
673	// <id> and <numBytes>).
674	if (!addStackMapLiveVars(Ops, CI: I, StartIdx: 2))
675	return false;
676
677	// We are not adding any register mask info here, because the stackmap doesn't
678	// clobber anything.
679
680	// Add scratch registers as implicit def and early clobber.
681	CallingConv::ID CC = I->getCallingConv();
682	const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
683	for (unsigned i = 0; ScratchRegs[i]; ++i)
684	Ops.push_back(Elt: MachineOperand::CreateReg(
685	Reg: ScratchRegs[i], /*isDef=*/true, /*isImp=*/true, /*isKill=*/false,
686	/*isDead=*/false, /*isUndef=*/false, /*isEarlyClobber=*/true));
687
688	// Issue CALLSEQ_START
689	unsigned AdjStackDown = TII.getCallFrameSetupOpcode();
690	auto Builder =
691	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: TII.get(Opcode: AdjStackDown));
692	const MCInstrDesc &MCID = Builder.getInstr()->getDesc();
693	for (unsigned I = 0, E = MCID.getNumOperands(); I < E; ++I)
694	Builder.addImm(Val: 0);
695
696	// Issue STACKMAP.
697	MachineInstrBuilder MIB = BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD,
698	MCID: TII.get(Opcode: TargetOpcode::STACKMAP));
699	for (auto const &MO : Ops)
700	MIB.add(MO);
701
702	// Issue CALLSEQ_END
703	unsigned AdjStackUp = TII.getCallFrameDestroyOpcode();
704	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: TII.get(Opcode: AdjStackUp))
705	.addImm(Val: 0)
706	.addImm(Val: 0);
707
708	// Inform the Frame Information that we have a stackmap in this function.
709	FuncInfo.MF->getFrameInfo().setHasStackMap();
710
711	return true;
712	}
713
714	/// Lower an argument list according to the target calling convention.
715	///
716	/// This is a helper for lowering intrinsics that follow a target calling
717	/// convention or require stack pointer adjustment. Only a subset of the
718	/// intrinsic's operands need to participate in the calling convention.
719	bool FastISel::lowerCallOperands(const CallInst *CI, unsigned ArgIdx,
720	unsigned NumArgs, const Value *Callee,
721	bool ForceRetVoidTy, CallLoweringInfo &CLI) {
722	ArgListTy Args;
723	Args.reserve(n: NumArgs);
724
725	// Populate the argument list.
726	for (unsigned ArgI = ArgIdx, ArgE = ArgIdx + NumArgs; ArgI != ArgE; ++ArgI) {
727	Value *V = CI->getOperand(i_nocapture: ArgI);
728
729	assert(!V->getType()->isEmptyTy() && "Empty type passed to intrinsic.");
730
731	ArgListEntry Entry;
732	Entry.Val = V;
733	Entry.Ty = V->getType();
734	Entry.setAttributes(Call: CI, ArgIdx: ArgI);
735	Args.push_back(x: Entry);
736	}
737
738	Type *RetTy = ForceRetVoidTy ? Type::getVoidTy(C&: CI->getType()->getContext())
739	: CI->getType();
740	CLI.setCallee(CC: CI->getCallingConv(), ResultTy: RetTy, Target: Callee, ArgsList: std::move(Args), FixedArgs: NumArgs);
741
742	return lowerCallTo(CLI);
743	}
744
745	FastISel::CallLoweringInfo &FastISel::CallLoweringInfo::setCallee(
746	const DataLayout &DL, MCContext &Ctx, CallingConv::ID CC, Type *ResultTy,
747	StringRef Target, ArgListTy &&ArgsList, unsigned FixedArgs) {
748	SmallString<32> MangledName;
749	Mangler::getNameWithPrefix(OutName&: MangledName, GVName: Target, DL);
750	MCSymbol *Sym = Ctx.getOrCreateSymbol(Name: MangledName);
751	return setCallee(CC, ResultTy, Target: Sym, ArgsList: std::move(ArgsList), FixedArgs);
752	}
753
754	bool FastISel::selectPatchpoint(const CallInst *I) {
755	// void|i64 @llvm.experimental.patchpoint.void|i64(i64 <id>,
756	// i32 <numBytes>,
757	// i8* <target>,
758	// i32 <numArgs>,
759	// [Args...],
760	// [live variables...])
761	CallingConv::ID CC = I->getCallingConv();
762	bool IsAnyRegCC = CC == CallingConv::AnyReg;
763	bool HasDef = !I->getType()->isVoidTy();
764	Value *Callee = I->getOperand(i_nocapture: PatchPointOpers::TargetPos)->stripPointerCasts();
765
766	// Get the real number of arguments participating in the call <numArgs>
767	assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NArgPos)) &&
768	"Expected a constant integer.");
769	const auto *NumArgsVal =
770	cast<ConstantInt>(Val: I->getOperand(i_nocapture: PatchPointOpers::NArgPos));
771	unsigned NumArgs = NumArgsVal->getZExtValue();
772
773	// Skip the four meta args: <id>, <numNopBytes>, <target>, <numArgs>
774	// This includes all meta-operands up to but not including CC.
775	unsigned NumMetaOpers = PatchPointOpers::CCPos;
776	assert(I->arg_size() >= NumMetaOpers + NumArgs &&
777	"Not enough arguments provided to the patchpoint intrinsic");
778
779	// For AnyRegCC the arguments are lowered later on manually.
780	unsigned NumCallArgs = IsAnyRegCC ? 0 : NumArgs;
781	CallLoweringInfo CLI;
782	CLI.setIsPatchPoint();
783	if (!lowerCallOperands(CI: I, ArgIdx: NumMetaOpers, NumArgs: NumCallArgs, Callee, ForceRetVoidTy: IsAnyRegCC, CLI))
784	return false;
785
786	assert(CLI.Call && "No call instruction specified.");
787
788	SmallVector<MachineOperand, 32> Ops;
789
790	// Add an explicit result reg if we use the anyreg calling convention.
791	if (IsAnyRegCC && HasDef) {
792	assert(CLI.NumResultRegs == 0 && "Unexpected result register.");
793	CLI.ResultReg = createResultReg(RC: TLI.getRegClassFor(MVT::VT: i64));
794	CLI.NumResultRegs = 1;
795	Ops.push_back(Elt: MachineOperand::CreateReg(Reg: CLI.ResultReg, /*isDef=*/true));
796	}
797
798	// Add the <id> and <numBytes> constants.
799	assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
800	"Expected a constant integer.");
801	const auto *ID = cast<ConstantInt>(Val: I->getOperand(i_nocapture: PatchPointOpers::IDPos));
802	Ops.push_back(Elt: MachineOperand::CreateImm(Val: ID->getZExtValue()));
803
804	assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
805	"Expected a constant integer.");
806	const auto *NumBytes =
807	cast<ConstantInt>(Val: I->getOperand(i_nocapture: PatchPointOpers::NBytesPos));
808	Ops.push_back(Elt: MachineOperand::CreateImm(Val: NumBytes->getZExtValue()));
809
810	// Add the call target.
811	if (const auto *C = dyn_cast<IntToPtrInst>(Val: Callee)) {
812	uint64_t CalleeConstAddr =
813	cast<ConstantInt>(Val: C->getOperand(i_nocapture: 0))->getZExtValue();
814	Ops.push_back(Elt: MachineOperand::CreateImm(Val: CalleeConstAddr));
815	} else if (const auto *C = dyn_cast<ConstantExpr>(Val: Callee)) {
816	if (C->getOpcode() == Instruction::IntToPtr) {
817	uint64_t CalleeConstAddr =
818	cast<ConstantInt>(Val: C->getOperand(i_nocapture: 0))->getZExtValue();
819	Ops.push_back(Elt: MachineOperand::CreateImm(Val: CalleeConstAddr));
820	} else
821	llvm_unreachable("Unsupported ConstantExpr.");
822	} else if (const auto *GV = dyn_cast<GlobalValue>(Val: Callee)) {
823	Ops.push_back(Elt: MachineOperand::CreateGA(GV, Offset: 0));
824	} else if (isa<ConstantPointerNull>(Val: Callee))
825	Ops.push_back(Elt: MachineOperand::CreateImm(Val: 0));
826	else
827	llvm_unreachable("Unsupported callee address.");
828
829	// Adjust <numArgs> to account for any arguments that have been passed on
830	// the stack instead.
831	unsigned NumCallRegArgs = IsAnyRegCC ? NumArgs : CLI.OutRegs.size();
832	Ops.push_back(Elt: MachineOperand::CreateImm(Val: NumCallRegArgs));
833
834	// Add the calling convention
835	Ops.push_back(Elt: MachineOperand::CreateImm(Val: (unsigned)CC));
836
837	// Add the arguments we omitted previously. The register allocator should
838	// place these in any free register.
839	if (IsAnyRegCC) {
840	for (unsigned i = NumMetaOpers, e = NumMetaOpers + NumArgs; i != e; ++i) {
841	Register Reg = getRegForValue(V: I->getArgOperand(i));
842	if (!Reg)
843	return false;
844	Ops.push_back(Elt: MachineOperand::CreateReg(Reg, /*isDef=*/false));
845	}
846	}
847
848	// Push the arguments from the call instruction.
849	for (auto Reg : CLI.OutRegs)
850	Ops.push_back(Elt: MachineOperand::CreateReg(Reg, /*isDef=*/false));
851
852	// Push live variables for the stack map.
853	if (!addStackMapLiveVars(Ops, CI: I, StartIdx: NumMetaOpers + NumArgs))
854	return false;
855
856	// Push the register mask info.
857	Ops.push_back(Elt: MachineOperand::CreateRegMask(
858	Mask: TRI.getCallPreservedMask(MF: *FuncInfo.MF, CC)));
859
860	// Add scratch registers as implicit def and early clobber.
861	const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
862	for (unsigned i = 0; ScratchRegs[i]; ++i)
863	Ops.push_back(Elt: MachineOperand::CreateReg(
864	Reg: ScratchRegs[i], /*isDef=*/true, /*isImp=*/true, /*isKill=*/false,
865	/*isDead=*/false, /*isUndef=*/false, /*isEarlyClobber=*/true));
866
867	// Add implicit defs (return values).
868	for (auto Reg : CLI.InRegs)
869	Ops.push_back(Elt: MachineOperand::CreateReg(Reg, /*isDef=*/true,
870	/*isImp=*/true));
871
872	// Insert the patchpoint instruction before the call generated by the target.
873	MachineInstrBuilder MIB = BuildMI(BB&: *FuncInfo.MBB, I: CLI.Call, MIMD,
874	MCID: TII.get(Opcode: TargetOpcode::PATCHPOINT));
875
876	for (auto &MO : Ops)
877	MIB.add(MO);
878
879	MIB->setPhysRegsDeadExcept(UsedRegs: CLI.InRegs, TRI);
880
881	// Delete the original call instruction.
882	CLI.Call->eraseFromParent();
883
884	// Inform the Frame Information that we have a patchpoint in this function.
885	FuncInfo.MF->getFrameInfo().setHasPatchPoint();
886
887	if (CLI.NumResultRegs)
888	updateValueMap(I, Reg: CLI.ResultReg, NumRegs: CLI.NumResultRegs);
889	return true;
890	}
891
892	bool FastISel::selectXRayCustomEvent(const CallInst *I) {
893	const auto &Triple = TM.getTargetTriple();
894	if (Triple.isAArch64(PointerWidth: 64) && Triple.getArch() != Triple::x86_64)
895	return true; // don't do anything to this instruction.
896	SmallVector<MachineOperand, 8> Ops;
897	Ops.push_back(Elt: MachineOperand::CreateReg(Reg: getRegForValue(V: I->getArgOperand(i: 0)),
898	/*isDef=*/false));
899	Ops.push_back(Elt: MachineOperand::CreateReg(Reg: getRegForValue(V: I->getArgOperand(i: 1)),
900	/*isDef=*/false));
901	MachineInstrBuilder MIB =
902	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD,
903	MCID: TII.get(Opcode: TargetOpcode::PATCHABLE_EVENT_CALL));
904	for (auto &MO : Ops)
905	MIB.add(MO);
906
907	// Insert the Patchable Event Call instruction, that gets lowered properly.
908	return true;
909	}
910
911	bool FastISel::selectXRayTypedEvent(const CallInst *I) {
912	const auto &Triple = TM.getTargetTriple();
913	if (Triple.isAArch64(PointerWidth: 64) && Triple.getArch() != Triple::x86_64)
914	return true; // don't do anything to this instruction.
915	SmallVector<MachineOperand, 8> Ops;
916	Ops.push_back(Elt: MachineOperand::CreateReg(Reg: getRegForValue(V: I->getArgOperand(i: 0)),
917	/*isDef=*/false));
918	Ops.push_back(Elt: MachineOperand::CreateReg(Reg: getRegForValue(V: I->getArgOperand(i: 1)),
919	/*isDef=*/false));
920	Ops.push_back(Elt: MachineOperand::CreateReg(Reg: getRegForValue(V: I->getArgOperand(i: 2)),
921	/*isDef=*/false));
922	MachineInstrBuilder MIB =
923	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD,
924	MCID: TII.get(Opcode: TargetOpcode::PATCHABLE_TYPED_EVENT_CALL));
925	for (auto &MO : Ops)
926	MIB.add(MO);
927
928	// Insert the Patchable Typed Event Call instruction, that gets lowered properly.
929	return true;
930	}
931
932	/// Returns an AttributeList representing the attributes applied to the return
933	/// value of the given call.
934	static AttributeList getReturnAttrs(FastISel::CallLoweringInfo &CLI) {
935	SmallVector<Attribute::AttrKind, 2> Attrs;
936	if (CLI.RetSExt)
937	Attrs.push_back(Attribute::Elt: SExt);
938	if (CLI.RetZExt)
939	Attrs.push_back(Attribute::Elt: ZExt);
940	if (CLI.IsInReg)
941	Attrs.push_back(Attribute::Elt: InReg);
942
943	return AttributeList::get(C&: CLI.RetTy->getContext(), Index: AttributeList::ReturnIndex,
944	Kinds: Attrs);
945	}
946
947	bool FastISel::lowerCallTo(const CallInst *CI, const char *SymName,
948	unsigned NumArgs) {
949	MCContext &Ctx = MF->getContext();
950	SmallString<32> MangledName;
951	Mangler::getNameWithPrefix(OutName&: MangledName, GVName: SymName, DL);
952	MCSymbol *Sym = Ctx.getOrCreateSymbol(Name: MangledName);
953	return lowerCallTo(CI, Symbol: Sym, NumArgs);
954	}
955
956	bool FastISel::lowerCallTo(const CallInst *CI, MCSymbol *Symbol,
957	unsigned NumArgs) {
958	FunctionType *FTy = CI->getFunctionType();
959	Type *RetTy = CI->getType();
960
961	ArgListTy Args;
962	Args.reserve(n: NumArgs);
963
964	// Populate the argument list.
965	// Attributes for args start at offset 1, after the return attribute.
966	for (unsigned ArgI = 0; ArgI != NumArgs; ++ArgI) {
967	Value *V = CI->getOperand(i_nocapture: ArgI);
968
969	assert(!V->getType()->isEmptyTy() && "Empty type passed to intrinsic.");
970
971	ArgListEntry Entry;
972	Entry.Val = V;
973	Entry.Ty = V->getType();
974	Entry.setAttributes(Call: CI, ArgIdx: ArgI);
975	Args.push_back(x: Entry);
976	}
977	TLI.markLibCallAttributes(MF, CC: CI->getCallingConv(), Args);
978
979	CallLoweringInfo CLI;
980	CLI.setCallee(ResultTy: RetTy, FuncTy: FTy, Target: Symbol, ArgsList: std::move(Args), Call: *CI, FixedArgs: NumArgs);
981
982	return lowerCallTo(CLI);
983	}
984
985	bool FastISel::lowerCallTo(CallLoweringInfo &CLI) {
986	// Handle the incoming return values from the call.
987	CLI.clearIns();
988	SmallVector<EVT, 4> RetTys;
989	ComputeValueVTs(TLI, DL, Ty: CLI.RetTy, ValueVTs&: RetTys);
990
991	SmallVector<ISD::OutputArg, 4> Outs;
992	GetReturnInfo(CC: CLI.CallConv, ReturnType: CLI.RetTy, attr: getReturnAttrs(CLI), Outs, TLI, DL);
993
994	bool CanLowerReturn = TLI.CanLowerReturn(
995	CLI.CallConv, *FuncInfo.MF, CLI.IsVarArg, Outs, CLI.RetTy->getContext());
996
997	// FIXME: sret demotion isn't supported yet - bail out.
998	if (!CanLowerReturn)
999	return false;
1000
1001	for (EVT VT : RetTys) {
1002	MVT RegisterVT = TLI.getRegisterType(Context&: CLI.RetTy->getContext(), VT);
1003	unsigned NumRegs = TLI.getNumRegisters(Context&: CLI.RetTy->getContext(), VT);
1004	for (unsigned i = 0; i != NumRegs; ++i) {
1005	ISD::InputArg MyFlags;
1006	MyFlags.VT = RegisterVT;
1007	MyFlags.ArgVT = VT;
1008	MyFlags.Used = CLI.IsReturnValueUsed;
1009	if (CLI.RetSExt)
1010	MyFlags.Flags.setSExt();
1011	if (CLI.RetZExt)
1012	MyFlags.Flags.setZExt();
1013	if (CLI.IsInReg)
1014	MyFlags.Flags.setInReg();
1015	CLI.Ins.push_back(Elt: MyFlags);
1016	}
1017	}
1018
1019	// Handle all of the outgoing arguments.
1020	CLI.clearOuts();
1021	for (auto &Arg : CLI.getArgs()) {
1022	Type *FinalType = Arg.Ty;
1023	if (Arg.IsByVal)
1024	FinalType = Arg.IndirectType;
1025	bool NeedsRegBlock = TLI.functionArgumentNeedsConsecutiveRegisters(
1026	Ty: FinalType, CallConv: CLI.CallConv, isVarArg: CLI.IsVarArg, DL);
1027
1028	ISD::ArgFlagsTy Flags;
1029	if (Arg.IsZExt)
1030	Flags.setZExt();
1031	if (Arg.IsSExt)
1032	Flags.setSExt();
1033	if (Arg.IsInReg)
1034	Flags.setInReg();
1035	if (Arg.IsSRet)
1036	Flags.setSRet();
1037	if (Arg.IsSwiftSelf)
1038	Flags.setSwiftSelf();
1039	if (Arg.IsSwiftAsync)
1040	Flags.setSwiftAsync();
1041	if (Arg.IsSwiftError)
1042	Flags.setSwiftError();
1043	if (Arg.IsCFGuardTarget)
1044	Flags.setCFGuardTarget();
1045	if (Arg.IsByVal)
1046	Flags.setByVal();
1047	if (Arg.IsInAlloca) {
1048	Flags.setInAlloca();
1049	// Set the byval flag for CCAssignFn callbacks that don't know about
1050	// inalloca. This way we can know how many bytes we should've allocated
1051	// and how many bytes a callee cleanup function will pop. If we port
1052	// inalloca to more targets, we'll have to add custom inalloca handling in
1053	// the various CC lowering callbacks.
1054	Flags.setByVal();
1055	}
1056	if (Arg.IsPreallocated) {
1057	Flags.setPreallocated();
1058	// Set the byval flag for CCAssignFn callbacks that don't know about
1059	// preallocated. This way we can know how many bytes we should've
1060	// allocated and how many bytes a callee cleanup function will pop. If we
1061	// port preallocated to more targets, we'll have to add custom
1062	// preallocated handling in the various CC lowering callbacks.
1063	Flags.setByVal();
1064	}
1065	MaybeAlign MemAlign = Arg.Alignment;
1066	if (Arg.IsByVal || Arg.IsInAlloca || Arg.IsPreallocated) {
1067	unsigned FrameSize = DL.getTypeAllocSize(Ty: Arg.IndirectType);
1068
1069	// For ByVal, alignment should come from FE. BE will guess if this info
1070	// is not there, but there are cases it cannot get right.
1071	if (!MemAlign)
1072	MemAlign = Align(TLI.getByValTypeAlignment(Ty: Arg.IndirectType, DL));
1073	Flags.setByValSize(FrameSize);
1074	} else if (!MemAlign) {
1075	MemAlign = DL.getABITypeAlign(Ty: Arg.Ty);
1076	}
1077	Flags.setMemAlign(*MemAlign);
1078	if (Arg.IsNest)
1079	Flags.setNest();
1080	if (NeedsRegBlock)
1081	Flags.setInConsecutiveRegs();
1082	Flags.setOrigAlign(DL.getABITypeAlign(Ty: Arg.Ty));
1083	CLI.OutVals.push_back(Elt: Arg.Val);
1084	CLI.OutFlags.push_back(Elt: Flags);
1085	}
1086
1087	if (!fastLowerCall(CLI))
1088	return false;
1089
1090	// Set all unused physreg defs as dead.
1091	assert(CLI.Call && "No call instruction specified.");
1092	CLI.Call->setPhysRegsDeadExcept(UsedRegs: CLI.InRegs, TRI);
1093
1094	if (CLI.NumResultRegs && CLI.CB)
1095	updateValueMap(I: CLI.CB, Reg: CLI.ResultReg, NumRegs: CLI.NumResultRegs);
1096
1097	// Set labels for heapallocsite call.
1098	if (CLI.CB)
1099	if (MDNode *MD = CLI.CB->getMetadata(Kind: "heapallocsite"))
1100	CLI.Call->setHeapAllocMarker(MF&: *MF, MD);
1101
1102	return true;
1103	}
1104
1105	bool FastISel::lowerCall(const CallInst *CI) {
1106	FunctionType *FuncTy = CI->getFunctionType();
1107	Type *RetTy = CI->getType();
1108
1109	ArgListTy Args;
1110	ArgListEntry Entry;
1111	Args.reserve(n: CI->arg_size());
1112
1113	for (auto i = CI->arg_begin(), e = CI->arg_end(); i != e; ++i) {
1114	Value *V = *i;
1115
1116	// Skip empty types
1117	if (V->getType()->isEmptyTy())
1118	continue;
1119
1120	Entry.Val = V;
1121	Entry.Ty = V->getType();
1122
1123	// Skip the first return-type Attribute to get to params.
1124	Entry.setAttributes(Call: CI, ArgIdx: i - CI->arg_begin());
1125	Args.push_back(x: Entry);
1126	}
1127
1128	// Check if target-independent constraints permit a tail call here.
1129	// Target-dependent constraints are checked within fastLowerCall.
1130	bool IsTailCall = CI->isTailCall();
1131	if (IsTailCall && !isInTailCallPosition(Call: *CI, TM))
1132	IsTailCall = false;
1133	if (IsTailCall && !CI->isMustTailCall() &&
1134	MF->getFunction().getFnAttribute(Kind: "disable-tail-calls").getValueAsBool())
1135	IsTailCall = false;
1136
1137	CallLoweringInfo CLI;
1138	CLI.setCallee(ResultTy: RetTy, FuncTy, Target: CI->getCalledOperand(), ArgsList: std::move(Args), Call: *CI)
1139	.setTailCall(IsTailCall);
1140
1141	diagnoseDontCall(CI: *CI);
1142
1143	return lowerCallTo(CLI);
1144	}
1145
1146	bool FastISel::selectCall(const User *I) {
1147	const CallInst *Call = cast<CallInst>(Val: I);
1148
1149	// Handle simple inline asms.
1150	if (const InlineAsm *IA = dyn_cast<InlineAsm>(Val: Call->getCalledOperand())) {
1151	// Don't attempt to handle constraints.
1152	if (!IA->getConstraintString().empty())
1153	return false;
1154
1155	unsigned ExtraInfo = 0;
1156	if (IA->hasSideEffects())
1157	ExtraInfo |= InlineAsm::Extra_HasSideEffects;
1158	if (IA->isAlignStack())
1159	ExtraInfo |= InlineAsm::Extra_IsAlignStack;
1160	if (Call->isConvergent())
1161	ExtraInfo |= InlineAsm::Extra_IsConvergent;
1162	ExtraInfo |= IA->getDialect() * InlineAsm::Extra_AsmDialect;
1163
1164	MachineInstrBuilder MIB = BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD,
1165	MCID: TII.get(Opcode: TargetOpcode::INLINEASM));
1166	MIB.addExternalSymbol(FnName: IA->getAsmString().c_str());
1167	MIB.addImm(Val: ExtraInfo);
1168
1169	const MDNode *SrcLoc = Call->getMetadata(Kind: "srcloc");
1170	if (SrcLoc)
1171	MIB.addMetadata(MD: SrcLoc);
1172
1173	return true;
1174	}
1175
1176	// Handle intrinsic function calls.
1177	if (const auto *II = dyn_cast<IntrinsicInst>(Val: Call))
1178	return selectIntrinsicCall(II);
1179
1180	return lowerCall(CI: Call);
1181	}
1182
1183	void FastISel::handleDbgInfo(const Instruction *II) {
1184	if (!II->hasDbgValues())
1185	return;
1186
1187	// Clear any metadata.
1188	MIMD = MIMetadata();
1189
1190	// Reverse order of debug records, because fast-isel walks through backwards.
1191	for (DPValue &DPV : llvm::reverse(C: II->getDbgValueRange())) {
1192	flushLocalValueMap();
1193	recomputeInsertPt();
1194
1195	Value *V = nullptr;
1196	if (!DPV.hasArgList())
1197	V = DPV.getVariableLocationOp(OpIdx: 0);
1198
1199	bool Res = false;
1200	if (DPV.getType() == DPValue::LocationType::Value ||
1201	DPV.getType() == DPValue::LocationType::Assign) {
1202	Res = lowerDbgValue(V, Expr: DPV.getExpression(), Var: DPV.getVariable(),
1203	DL: DPV.getDebugLoc());
1204	} else {
1205	assert(DPV.getType() == DPValue::LocationType::Declare);
1206	if (FuncInfo.PreprocessedDPVDeclares.contains(Ptr: &DPV))
1207	continue;
1208	Res = lowerDbgDeclare(V, Expr: DPV.getExpression(), Var: DPV.getVariable(),
1209	DL: DPV.getDebugLoc());
1210	}
1211
1212	if (!Res)
1213	LLVM_DEBUG(dbgs() << "Dropping debug-info for " << DPV << "\n";);
1214	}
1215	}
1216
1217	bool FastISel::lowerDbgValue(const Value *V, DIExpression *Expr,
1218	DILocalVariable *Var, const DebugLoc &DL) {
1219	// This form of DBG_VALUE is target-independent.
1220	const MCInstrDesc &II = TII.get(Opcode: TargetOpcode::DBG_VALUE);
1221	if (!V || isa<UndefValue>(Val: V)) {
1222	// DI is either undef or cannot produce a valid DBG_VALUE, so produce an
1223	// undef DBG_VALUE to terminate any prior location.
1224	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, DL, MCID: II, IsIndirect: false, Reg: 0U, Variable: Var, Expr);
1225	return true;
1226	}
1227	if (const auto *CI = dyn_cast<ConstantInt>(Val: V)) {
1228	// See if there's an expression to constant-fold.
1229	if (Expr)
1230	std::tie(args&: Expr, args&: CI) = Expr->constantFold(CI);
1231	if (CI->getBitWidth() > 64)
1232	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD: DL, MCID: II)
1233	.addCImm(Val: CI)
1234	.addImm(Val: 0U)
1235	.addMetadata(MD: Var)
1236	.addMetadata(MD: Expr);
1237	else
1238	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD: DL, MCID: II)
1239	.addImm(Val: CI->getZExtValue())
1240	.addImm(Val: 0U)
1241	.addMetadata(MD: Var)
1242	.addMetadata(MD: Expr);
1243	return true;
1244	}
1245	if (const auto *CF = dyn_cast<ConstantFP>(Val: V)) {
1246	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD: DL, MCID: II)
1247	.addFPImm(Val: CF)
1248	.addImm(Val: 0U)
1249	.addMetadata(MD: Var)
1250	.addMetadata(MD: Expr);
1251	return true;
1252	}
1253	if (const auto *Arg = dyn_cast<Argument>(Val: V);
1254	Arg && Expr && Expr->isEntryValue()) {
1255	// As per the Verifier, this case is only valid for swift async Args.
1256	assert(Arg->hasAttribute(Attribute::AttrKind::SwiftAsync));
1257
1258	Register Reg = getRegForValue(V: Arg);
1259	for (auto [PhysReg, VirtReg] : FuncInfo.RegInfo->liveins())
1260	if (Reg == VirtReg || Reg == PhysReg) {
1261	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, DL, MCID: II, IsIndirect: false /*IsIndirect*/,
1262	Reg: PhysReg, Variable: Var, Expr);
1263	return true;
1264	}
1265
1266	LLVM_DEBUG(dbgs() << "Dropping dbg.value: expression is entry_value but "
1267	"couldn't find a physical register\n");
1268	return false;
1269	}
1270	if (auto SI = FuncInfo.StaticAllocaMap.find(Val: dyn_cast<AllocaInst>(Val: V));
1271	SI != FuncInfo.StaticAllocaMap.end()) {
1272	MachineOperand FrameIndexOp = MachineOperand::CreateFI(Idx: SI->second);
1273	bool IsIndirect = false;
1274	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, DL, MCID: II, IsIndirect, MOs: FrameIndexOp,
1275	Variable: Var, Expr);
1276	return true;
1277	}
1278	if (Register Reg = lookUpRegForValue(V)) {
1279	// FIXME: This does not handle register-indirect values at offset 0.
1280	if (!FuncInfo.MF->useDebugInstrRef()) {
1281	bool IsIndirect = false;
1282	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, DL, MCID: II, IsIndirect, Reg, Variable: Var,
1283	Expr);
1284	return true;
1285	}
1286	// If using instruction referencing, produce this as a DBG_INSTR_REF,
1287	// to be later patched up by finalizeDebugInstrRefs.
1288	SmallVector<MachineOperand, 1> MOs({MachineOperand::CreateReg(
1289	/* Reg */ Reg, /* isDef */ false, /* isImp */ false,
1290	/* isKill */ false, /* isDead */ false,
1291	/* isUndef */ false, /* isEarlyClobber */ false,
1292	/* SubReg */ 0, /* isDebug */ true)});
1293	SmallVector<uint64_t, 2> Ops({dwarf::DW_OP_LLVM_arg, 0});
1294	auto *NewExpr = DIExpression::prependOpcodes(Expr, Ops);
1295	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, DL,
1296	MCID: TII.get(Opcode: TargetOpcode::DBG_INSTR_REF), /*IsIndirect*/ false, MOs,
1297	Variable: Var, Expr: NewExpr);
1298	return true;
1299	}
1300	return false;
1301	}
1302
1303	bool FastISel::lowerDbgDeclare(const Value *Address, DIExpression *Expr,
1304	DILocalVariable *Var, const DebugLoc &DL) {
1305	if (!Address || isa<UndefValue>(Val: Address)) {
1306	LLVM_DEBUG(dbgs() << "Dropping debug info (bad/undef address)\n");
1307	return false;
1308	}
1309
1310	std::optional<MachineOperand> Op;
1311	if (Register Reg = lookUpRegForValue(V: Address))
1312	Op = MachineOperand::CreateReg(Reg, isDef: false);
1313
1314	// If we have a VLA that has a "use" in a metadata node that's then used
1315	// here but it has no other uses, then we have a problem. E.g.,
1316	//
1317	// int foo (const int *x) {
1318	// char a[*x];
1319	// return 0;
1320	// }
1321	//
1322	// If we assign 'a' a vreg and fast isel later on has to use the selection
1323	// DAG isel, it will want to copy the value to the vreg. However, there are
1324	// no uses, which goes counter to what selection DAG isel expects.
1325	if (!Op && !Address->use_empty() && isa<Instruction>(Val: Address) &&
1326	(!isa<AllocaInst>(Val: Address) ||
1327	!FuncInfo.StaticAllocaMap.count(Val: cast<AllocaInst>(Val: Address))))
1328	Op = MachineOperand::CreateReg(Reg: FuncInfo.InitializeRegForValue(V: Address),
1329	isDef: false);
1330
1331	if (Op) {
1332	assert(Var->isValidLocationForIntrinsic(DL) &&
1333	"Expected inlined-at fields to agree");
1334	if (FuncInfo.MF->useDebugInstrRef() && Op->isReg()) {
1335	// If using instruction referencing, produce this as a DBG_INSTR_REF,
1336	// to be later patched up by finalizeDebugInstrRefs. Tack a deref onto
1337	// the expression, we don't have an "indirect" flag in DBG_INSTR_REF.
1338	SmallVector<uint64_t, 3> Ops(
1339	{dwarf::DW_OP_LLVM_arg, 0, dwarf::DW_OP_deref});
1340	auto *NewExpr = DIExpression::prependOpcodes(Expr, Ops);
1341	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, DL,
1342	MCID: TII.get(Opcode: TargetOpcode::DBG_INSTR_REF), /*IsIndirect*/ false, MOs: *Op,
1343	Variable: Var, Expr: NewExpr);
1344	return true;
1345	}
1346
1347	// A dbg.declare describes the address of a source variable, so lower it
1348	// into an indirect DBG_VALUE.
1349	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, DL,
1350	MCID: TII.get(Opcode: TargetOpcode::DBG_VALUE), /*IsIndirect*/ true, MOs: *Op, Variable: Var,
1351	Expr);
1352	return true;
1353	}
1354
1355	// We can't yet handle anything else here because it would require
1356	// generating code, thus altering codegen because of debug info.
1357	LLVM_DEBUG(
1358	dbgs() << "Dropping debug info (no materialized reg for address)\n");
1359	return false;
1360	}
1361
1362	bool FastISel::selectIntrinsicCall(const IntrinsicInst *II) {
1363	switch (II->getIntrinsicID()) {
1364	default:
1365	break;
1366	// At -O0 we don't care about the lifetime intrinsics.
1367	case Intrinsic::lifetime_start:
1368	case Intrinsic::lifetime_end:
1369	// The donothing intrinsic does, well, nothing.
1370	case Intrinsic::donothing:
1371	// Neither does the sideeffect intrinsic.
1372	case Intrinsic::sideeffect:
1373	// Neither does the assume intrinsic; it's also OK not to codegen its operand.
1374	case Intrinsic::assume:
1375	// Neither does the llvm.experimental.noalias.scope.decl intrinsic
1376	case Intrinsic::experimental_noalias_scope_decl:
1377	return true;
1378	case Intrinsic::dbg_declare: {
1379	const DbgDeclareInst *DI = cast<DbgDeclareInst>(Val: II);
1380	assert(DI->getVariable() && "Missing variable");
1381	if (!FuncInfo.MF->getMMI().hasDebugInfo()) {
1382	LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI
1383	<< " (!hasDebugInfo)\n");
1384	return true;
1385	}
1386
1387	if (FuncInfo.PreprocessedDbgDeclares.contains(Ptr: DI))
1388	return true;
1389
1390	const Value *Address = DI->getAddress();
1391	if (!lowerDbgDeclare(Address, Expr: DI->getExpression(), Var: DI->getVariable(),
1392	DL: MIMD.getDL()))
1393	LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI);
1394
1395	return true;
1396	}
1397	case Intrinsic::dbg_assign:
1398	// A dbg.assign is a dbg.value with more information, typically produced
1399	// during optimisation. If one reaches fastisel then something odd has
1400	// happened (such as an optimised function being always-inlined into an
1401	// optnone function). We will not be using the extra information in the
1402	// dbg.assign in that case, just use its dbg.value fields.
1403	LLVM_FALLTHROUGH;
1404	case Intrinsic::dbg_value: {
1405	// This form of DBG_VALUE is target-independent.
1406	const DbgValueInst *DI = cast<DbgValueInst>(Val: II);
1407	const Value *V = DI->getValue();
1408	DIExpression *Expr = DI->getExpression();
1409	DILocalVariable *Var = DI->getVariable();
1410	if (DI->hasArgList())
1411	// Signal that we don't have a location for this.
1412	V = nullptr;
1413
1414	assert(Var->isValidLocationForIntrinsic(MIMD.getDL()) &&
1415	"Expected inlined-at fields to agree");
1416
1417	if (!lowerDbgValue(V, Expr, Var, DL: MIMD.getDL()))
1418	LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
1419
1420	return true;
1421	}
1422	case Intrinsic::dbg_label: {
1423	const DbgLabelInst *DI = cast<DbgLabelInst>(Val: II);
1424	assert(DI->getLabel() && "Missing label");
1425	if (!FuncInfo.MF->getMMI().hasDebugInfo()) {
1426	LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
1427	return true;
1428	}
1429
1430	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD,
1431	MCID: TII.get(Opcode: TargetOpcode::DBG_LABEL)).addMetadata(MD: DI->getLabel());
1432	return true;
1433	}
1434	case Intrinsic::objectsize:
1435	llvm_unreachable("llvm.objectsize.* should have been lowered already");
1436
1437	case Intrinsic::is_constant:
1438	llvm_unreachable("llvm.is.constant.* should have been lowered already");
1439
1440	case Intrinsic::launder_invariant_group:
1441	case Intrinsic::strip_invariant_group:
1442	case Intrinsic::expect: {
1443	Register ResultReg = getRegForValue(V: II->getArgOperand(i: 0));
1444	if (!ResultReg)
1445	return false;
1446	updateValueMap(I: II, Reg: ResultReg);
1447	return true;
1448	}
1449	case Intrinsic::experimental_stackmap:
1450	return selectStackmap(I: II);
1451	case Intrinsic::experimental_patchpoint_void:
1452	case Intrinsic::experimental_patchpoint_i64:
1453	return selectPatchpoint(I: II);
1454
1455	case Intrinsic::xray_customevent:
1456	return selectXRayCustomEvent(I: II);
1457	case Intrinsic::xray_typedevent:
1458	return selectXRayTypedEvent(I: II);
1459	}
1460
1461	return fastLowerIntrinsicCall(II);
1462	}
1463
1464	bool FastISel::selectCast(const User *I, unsigned Opcode) {
1465	EVT SrcVT = TLI.getValueType(DL, Ty: I->getOperand(i: 0)->getType());
1466	EVT DstVT = TLI.getValueType(DL, Ty: I->getType());
1467
1468	if (SrcVT == MVT::Other || !SrcVT.isSimple() || DstVT == MVT::Other ||
1469	!DstVT.isSimple())
1470	// Unhandled type. Halt "fast" selection and bail.
1471	return false;
1472
1473	// Check if the destination type is legal.
1474	if (!TLI.isTypeLegal(VT: DstVT))
1475	return false;
1476
1477	// Check if the source operand is legal.
1478	if (!TLI.isTypeLegal(VT: SrcVT))
1479	return false;
1480
1481	Register InputReg = getRegForValue(V: I->getOperand(i: 0));
1482	if (!InputReg)
1483	// Unhandled operand. Halt "fast" selection and bail.
1484	return false;
1485
1486	Register ResultReg = fastEmit_r(VT: SrcVT.getSimpleVT(), RetVT: DstVT.getSimpleVT(),
1487	Opcode, Op0: InputReg);
1488	if (!ResultReg)
1489	return false;
1490
1491	updateValueMap(I, Reg: ResultReg);
1492	return true;
1493	}
1494
1495	bool FastISel::selectBitCast(const User *I) {
1496	EVT SrcEVT = TLI.getValueType(DL, Ty: I->getOperand(i: 0)->getType());
1497	EVT DstEVT = TLI.getValueType(DL, Ty: I->getType());
1498	if (SrcEVT == MVT::Other || DstEVT == MVT::Other ||
1499	!TLI.isTypeLegal(VT: SrcEVT) || !TLI.isTypeLegal(VT: DstEVT))
1500	// Unhandled type. Halt "fast" selection and bail.
1501	return false;
1502
1503	MVT SrcVT = SrcEVT.getSimpleVT();
1504	MVT DstVT = DstEVT.getSimpleVT();
1505	Register Op0 = getRegForValue(V: I->getOperand(i: 0));
1506	if (!Op0) // Unhandled operand. Halt "fast" selection and bail.
1507	return false;
1508
1509	// If the bitcast doesn't change the type, just use the operand value.
1510	if (SrcVT == DstVT) {
1511	updateValueMap(I, Reg: Op0);
1512	return true;
1513	}
1514
1515	// Otherwise, select a BITCAST opcode.
1516	Register ResultReg = fastEmit_r(VT: SrcVT, RetVT: DstVT, Opcode: ISD::BITCAST, Op0);
1517	if (!ResultReg)
1518	return false;
1519
1520	updateValueMap(I, Reg: ResultReg);
1521	return true;
1522	}
1523
1524	bool FastISel::selectFreeze(const User *I) {
1525	Register Reg = getRegForValue(V: I->getOperand(i: 0));
1526	if (!Reg)
1527	// Unhandled operand.
1528	return false;
1529
1530	EVT ETy = TLI.getValueType(DL, Ty: I->getOperand(i: 0)->getType());
1531	if (ETy == MVT::Other || !TLI.isTypeLegal(VT: ETy))
1532	// Unhandled type, bail out.
1533	return false;
1534
1535	MVT Ty = ETy.getSimpleVT();
1536	const TargetRegisterClass *TyRegClass = TLI.getRegClassFor(VT: Ty);
1537	Register ResultReg = createResultReg(RC: TyRegClass);
1538	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD,
1539	MCID: TII.get(Opcode: TargetOpcode::COPY), DestReg: ResultReg).addReg(RegNo: Reg);
1540
1541	updateValueMap(I, Reg: ResultReg);
1542	return true;
1543	}
1544
1545	// Remove local value instructions starting from the instruction after
1546	// SavedLastLocalValue to the current function insert point.
1547	void FastISel::removeDeadLocalValueCode(MachineInstr *SavedLastLocalValue)
1548	{
1549	MachineInstr *CurLastLocalValue = getLastLocalValue();
1550	if (CurLastLocalValue != SavedLastLocalValue) {
1551	// Find the first local value instruction to be deleted.
1552	// This is the instruction after SavedLastLocalValue if it is non-NULL.
1553	// Otherwise it's the first instruction in the block.
1554	MachineBasicBlock::iterator FirstDeadInst(SavedLastLocalValue);
1555	if (SavedLastLocalValue)
1556	++FirstDeadInst;
1557	else
1558	FirstDeadInst = FuncInfo.MBB->getFirstNonPHI();
1559	setLastLocalValue(SavedLastLocalValue);
1560	removeDeadCode(I: FirstDeadInst, E: FuncInfo.InsertPt);
1561	}
1562	}
1563
1564	bool FastISel::selectInstruction(const Instruction *I) {
1565	// Flush the local value map before starting each instruction.
1566	// This improves locality and debugging, and can reduce spills.
1567	// Reuse of values across IR instructions is relatively uncommon.
1568	flushLocalValueMap();
1569
1570	MachineInstr *SavedLastLocalValue = getLastLocalValue();
1571	// Just before the terminator instruction, insert instructions to
1572	// feed PHI nodes in successor blocks.
1573	if (I->isTerminator()) {
1574	if (!handlePHINodesInSuccessorBlocks(LLVMBB: I->getParent())) {
1575	// PHI node handling may have generated local value instructions,
1576	// even though it failed to handle all PHI nodes.
1577	// We remove these instructions because SelectionDAGISel will generate
1578	// them again.
1579	removeDeadLocalValueCode(SavedLastLocalValue);
1580	return false;
1581	}
1582	}
1583
1584	// FastISel does not handle any operand bundles except OB_funclet.
1585	if (auto *Call = dyn_cast<CallBase>(Val: I))
1586	for (unsigned i = 0, e = Call->getNumOperandBundles(); i != e; ++i)
1587	if (Call->getOperandBundleAt(Index: i).getTagID() != LLVMContext::OB_funclet)
1588	return false;
1589
1590	MIMD = MIMetadata(*I);
1591
1592	SavedInsertPt = FuncInfo.InsertPt;
1593
1594	if (const auto *Call = dyn_cast<CallInst>(Val: I)) {
1595	const Function *F = Call->getCalledFunction();
1596	LibFunc Func;
1597
1598	// As a special case, don't handle calls to builtin library functions that
1599	// may be translated directly to target instructions.
1600	if (F && !F->hasLocalLinkage() && F->hasName() &&
1601	LibInfo->getLibFunc(funcName: F->getName(), F&: Func) &&
1602	LibInfo->hasOptimizedCodeGen(F: Func))
1603	return false;
1604
1605	// Don't handle Intrinsic::trap if a trap function is specified.
1606	if (F && F->getIntrinsicID() == Intrinsic::trap &&
1607	Call->hasFnAttr(Kind: "trap-func-name"))
1608	return false;
1609	}
1610
1611	// First, try doing target-independent selection.
1612	if (!SkipTargetIndependentISel) {
1613	if (selectOperator(I, Opcode: I->getOpcode())) {
1614	++NumFastIselSuccessIndependent;
1615	MIMD = {};
1616	return true;
1617	}
1618	// Remove dead code.
1619	recomputeInsertPt();
1620	if (SavedInsertPt != FuncInfo.InsertPt)
1621	removeDeadCode(I: FuncInfo.InsertPt, E: SavedInsertPt);
1622	SavedInsertPt = FuncInfo.InsertPt;
1623	}
1624	// Next, try calling the target to attempt to handle the instruction.
1625	if (fastSelectInstruction(I)) {
1626	++NumFastIselSuccessTarget;
1627	MIMD = {};
1628	return true;
1629	}
1630	// Remove dead code.
1631	recomputeInsertPt();
1632	if (SavedInsertPt != FuncInfo.InsertPt)
1633	removeDeadCode(I: FuncInfo.InsertPt, E: SavedInsertPt);
1634
1635	MIMD = {};
1636	// Undo phi node updates, because they will be added again by SelectionDAG.
1637	if (I->isTerminator()) {
1638	// PHI node handling may have generated local value instructions.
1639	// We remove them because SelectionDAGISel will generate them again.
1640	removeDeadLocalValueCode(SavedLastLocalValue);
1641	FuncInfo.PHINodesToUpdate.resize(new_size: FuncInfo.OrigNumPHINodesToUpdate);
1642	}
1643	return false;
1644	}
1645
1646	/// Emit an unconditional branch to the given block, unless it is the immediate
1647	/// (fall-through) successor, and update the CFG.
1648	void FastISel::fastEmitBranch(MachineBasicBlock *MSucc,
1649	const DebugLoc &DbgLoc) {
1650	if (FuncInfo.MBB->getBasicBlock()->sizeWithoutDebug() > 1 &&
1651	FuncInfo.MBB->isLayoutSuccessor(MBB: MSucc)) {
1652	// For more accurate line information if this is the only non-debug
1653	// instruction in the block then emit it, otherwise we have the
1654	// unconditional fall-through case, which needs no instructions.
1655	} else {
1656	// The unconditional branch case.
1657	TII.insertBranch(MBB&: *FuncInfo.MBB, TBB: MSucc, FBB: nullptr,
1658	Cond: SmallVector<MachineOperand, 0>(), DL: DbgLoc);
1659	}
1660	if (FuncInfo.BPI) {
1661	auto BranchProbability = FuncInfo.BPI->getEdgeProbability(
1662	Src: FuncInfo.MBB->getBasicBlock(), Dst: MSucc->getBasicBlock());
1663	FuncInfo.MBB->addSuccessor(Succ: MSucc, Prob: BranchProbability);
1664	} else
1665	FuncInfo.MBB->addSuccessorWithoutProb(Succ: MSucc);
1666	}
1667
1668	void FastISel::finishCondBranch(const BasicBlock *BranchBB,
1669	MachineBasicBlock *TrueMBB,
1670	MachineBasicBlock *FalseMBB) {
1671	// Add TrueMBB as successor unless it is equal to the FalseMBB: This can
1672	// happen in degenerate IR and MachineIR forbids to have a block twice in the
1673	// successor/predecessor lists.
1674	if (TrueMBB != FalseMBB) {
1675	if (FuncInfo.BPI) {
1676	auto BranchProbability =
1677	FuncInfo.BPI->getEdgeProbability(Src: BranchBB, Dst: TrueMBB->getBasicBlock());
1678	FuncInfo.MBB->addSuccessor(Succ: TrueMBB, Prob: BranchProbability);
1679	} else
1680	FuncInfo.MBB->addSuccessorWithoutProb(Succ: TrueMBB);
1681	}
1682
1683	fastEmitBranch(MSucc: FalseMBB, DbgLoc: MIMD.getDL());
1684	}
1685
1686	/// Emit an FNeg operation.
1687	bool FastISel::selectFNeg(const User *I, const Value *In) {
1688	Register OpReg = getRegForValue(V: In);
1689	if (!OpReg)
1690	return false;
1691
1692	// If the target has ISD::FNEG, use it.
1693	EVT VT = TLI.getValueType(DL, Ty: I->getType());
1694	Register ResultReg = fastEmit_r(VT: VT.getSimpleVT(), RetVT: VT.getSimpleVT(), Opcode: ISD::FNEG,
1695	Op0: OpReg);
1696	if (ResultReg) {
1697	updateValueMap(I, Reg: ResultReg);
1698	return true;
1699	}
1700
1701	// Bitcast the value to integer, twiddle the sign bit with xor,
1702	// and then bitcast it back to floating-point.
1703	if (VT.getSizeInBits() > 64)
1704	return false;
1705	EVT IntVT = EVT::getIntegerVT(Context&: I->getContext(), BitWidth: VT.getSizeInBits());
1706	if (!TLI.isTypeLegal(VT: IntVT))
1707	return false;
1708
1709	Register IntReg = fastEmit_r(VT: VT.getSimpleVT(), RetVT: IntVT.getSimpleVT(),
1710	Opcode: ISD::BITCAST, Op0: OpReg);
1711	if (!IntReg)
1712	return false;
1713
1714	Register IntResultReg = fastEmit_ri_(
1715	VT: IntVT.getSimpleVT(), Opcode: ISD::XOR, Op0: IntReg,
1716	UINT64_C(1) << (VT.getSizeInBits() - 1), ImmType: IntVT.getSimpleVT());
1717	if (!IntResultReg)
1718	return false;
1719
1720	ResultReg = fastEmit_r(VT: IntVT.getSimpleVT(), RetVT: VT.getSimpleVT(), Opcode: ISD::BITCAST,
1721	Op0: IntResultReg);
1722	if (!ResultReg)
1723	return false;
1724
1725	updateValueMap(I, Reg: ResultReg);
1726	return true;
1727	}
1728
1729	bool FastISel::selectExtractValue(const User *U) {
1730	const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Val: U);
1731	if (!EVI)
1732	return false;
1733
1734	// Make sure we only try to handle extracts with a legal result. But also
1735	// allow i1 because it's easy.
1736	EVT RealVT = TLI.getValueType(DL, Ty: EVI->getType(), /*AllowUnknown=*/true);
1737	if (!RealVT.isSimple())
1738	return false;
1739	MVT VT = RealVT.getSimpleVT();
1740	if (!TLI.isTypeLegal(VT) && VT != MVT::i1)
1741	return false;
1742
1743	const Value *Op0 = EVI->getOperand(i_nocapture: 0);
1744	Type *AggTy = Op0->getType();
1745
1746	// Get the base result register.
1747	unsigned ResultReg;
1748	DenseMap<const Value *, Register>::iterator I = FuncInfo.ValueMap.find(Val: Op0);
1749	if (I != FuncInfo.ValueMap.end())
1750	ResultReg = I->second;
1751	else if (isa<Instruction>(Val: Op0))
1752	ResultReg = FuncInfo.InitializeRegForValue(V: Op0);
1753	else
1754	return false; // fast-isel can't handle aggregate constants at the moment
1755
1756	// Get the actual result register, which is an offset from the base register.
1757	unsigned VTIndex = ComputeLinearIndex(Ty: AggTy, Indices: EVI->getIndices());
1758
1759	SmallVector<EVT, 4> AggValueVTs;
1760	ComputeValueVTs(TLI, DL, Ty: AggTy, ValueVTs&: AggValueVTs);
1761
1762	for (unsigned i = 0; i < VTIndex; i++)
1763	ResultReg += TLI.getNumRegisters(Context&: FuncInfo.Fn->getContext(), VT: AggValueVTs[i]);
1764
1765	updateValueMap(I: EVI, Reg: ResultReg);
1766	return true;
1767	}
1768
1769	bool FastISel::selectOperator(const User *I, unsigned Opcode) {
1770	switch (Opcode) {
1771	case Instruction::Add:
1772	return selectBinaryOp(I, ISDOpcode: ISD::ADD);
1773	case Instruction::FAdd:
1774	return selectBinaryOp(I, ISDOpcode: ISD::FADD);
1775	case Instruction::Sub:
1776	return selectBinaryOp(I, ISDOpcode: ISD::SUB);
1777	case Instruction::FSub:
1778	return selectBinaryOp(I, ISDOpcode: ISD::FSUB);
1779	case Instruction::Mul:
1780	return selectBinaryOp(I, ISDOpcode: ISD::MUL);
1781	case Instruction::FMul:
1782	return selectBinaryOp(I, ISDOpcode: ISD::FMUL);
1783	case Instruction::SDiv:
1784	return selectBinaryOp(I, ISDOpcode: ISD::SDIV);
1785	case Instruction::UDiv:
1786	return selectBinaryOp(I, ISDOpcode: ISD::UDIV);
1787	case Instruction::FDiv:
1788	return selectBinaryOp(I, ISDOpcode: ISD::FDIV);
1789	case Instruction::SRem:
1790	return selectBinaryOp(I, ISDOpcode: ISD::SREM);
1791	case Instruction::URem:
1792	return selectBinaryOp(I, ISDOpcode: ISD::UREM);
1793	case Instruction::FRem:
1794	return selectBinaryOp(I, ISDOpcode: ISD::FREM);
1795	case Instruction::Shl:
1796	return selectBinaryOp(I, ISDOpcode: ISD::SHL);
1797	case Instruction::LShr:
1798	return selectBinaryOp(I, ISDOpcode: ISD::SRL);
1799	case Instruction::AShr:
1800	return selectBinaryOp(I, ISDOpcode: ISD::SRA);
1801	case Instruction::And:
1802	return selectBinaryOp(I, ISDOpcode: ISD::AND);
1803	case Instruction::Or:
1804	return selectBinaryOp(I, ISDOpcode: ISD::OR);
1805	case Instruction::Xor:
1806	return selectBinaryOp(I, ISDOpcode: ISD::XOR);
1807
1808	case Instruction::FNeg:
1809	return selectFNeg(I, In: I->getOperand(i: 0));
1810
1811	case Instruction::GetElementPtr:
1812	return selectGetElementPtr(I);
1813
1814	case Instruction::Br: {
1815	const BranchInst *BI = cast<BranchInst>(Val: I);
1816
1817	if (BI->isUnconditional()) {
1818	const BasicBlock *LLVMSucc = BI->getSuccessor(i: 0);
1819	MachineBasicBlock *MSucc = FuncInfo.MBBMap[LLVMSucc];
1820	fastEmitBranch(MSucc, DbgLoc: BI->getDebugLoc());
1821	return true;
1822	}
1823
1824	// Conditional branches are not handed yet.
1825	// Halt "fast" selection and bail.
1826	return false;
1827	}
1828
1829	case Instruction::Unreachable:
1830	if (TM.Options.TrapUnreachable)
1831	return fastEmit_(MVT::VT: Other, MVT::RetVT: Other, Opcode: ISD::TRAP) != 0;
1832	else
1833	return true;
1834
1835	case Instruction::Alloca:
1836	// FunctionLowering has the static-sized case covered.
1837	if (FuncInfo.StaticAllocaMap.count(Val: cast<AllocaInst>(Val: I)))
1838	return true;
1839
1840	// Dynamic-sized alloca is not handled yet.
1841	return false;
1842
1843	case Instruction::Call:
1844	// On AIX, normal call lowering uses the DAG-ISEL path currently so that the
1845	// callee of the direct function call instruction will be mapped to the
1846	// symbol for the function's entry point, which is distinct from the
1847	// function descriptor symbol. The latter is the symbol whose XCOFF symbol
1848	// name is the C-linkage name of the source level function.
1849	// But fast isel still has the ability to do selection for intrinsics.
1850	if (TM.getTargetTriple().isOSAIX() && !isa<IntrinsicInst>(Val: I))
1851	return false;
1852	return selectCall(I);
1853
1854	case Instruction::BitCast:
1855	return selectBitCast(I);
1856
1857	case Instruction::FPToSI:
1858	return selectCast(I, Opcode: ISD::FP_TO_SINT);
1859	case Instruction::ZExt:
1860	return selectCast(I, Opcode: ISD::ZERO_EXTEND);
1861	case Instruction::SExt:
1862	return selectCast(I, Opcode: ISD::SIGN_EXTEND);
1863	case Instruction::Trunc:
1864	return selectCast(I, Opcode: ISD::TRUNCATE);
1865	case Instruction::SIToFP:
1866	return selectCast(I, Opcode: ISD::SINT_TO_FP);
1867
1868	case Instruction::IntToPtr: // Deliberate fall-through.
1869	case Instruction::PtrToInt: {
1870	EVT SrcVT = TLI.getValueType(DL, Ty: I->getOperand(i: 0)->getType());
1871	EVT DstVT = TLI.getValueType(DL, Ty: I->getType());
1872	if (DstVT.bitsGT(VT: SrcVT))
1873	return selectCast(I, Opcode: ISD::ZERO_EXTEND);
1874	if (DstVT.bitsLT(VT: SrcVT))
1875	return selectCast(I, Opcode: ISD::TRUNCATE);
1876	Register Reg = getRegForValue(V: I->getOperand(i: 0));
1877	if (!Reg)
1878	return false;
1879	updateValueMap(I, Reg);
1880	return true;
1881	}
1882
1883	case Instruction::ExtractValue:
1884	return selectExtractValue(U: I);
1885
1886	case Instruction::Freeze:
1887	return selectFreeze(I);
1888
1889	case Instruction::PHI:
1890	llvm_unreachable("FastISel shouldn't visit PHI nodes!");
1891
1892	default:
1893	// Unhandled instruction. Halt "fast" selection and bail.
1894	return false;
1895	}
1896	}
1897
1898	FastISel::FastISel(FunctionLoweringInfo &FuncInfo,
1899	const TargetLibraryInfo *LibInfo,
1900	bool SkipTargetIndependentISel)
1901	: FuncInfo(FuncInfo), MF(FuncInfo.MF), MRI(FuncInfo.MF->getRegInfo()),
1902	MFI(FuncInfo.MF->getFrameInfo()), MCP(*FuncInfo.MF->getConstantPool()),
1903	TM(FuncInfo.MF->getTarget()), DL(MF->getDataLayout()),
1904	TII(*MF->getSubtarget().getInstrInfo()),
1905	TLI(*MF->getSubtarget().getTargetLowering()),
1906	TRI(*MF->getSubtarget().getRegisterInfo()), LibInfo(LibInfo),
1907	SkipTargetIndependentISel(SkipTargetIndependentISel) {}
1908
1909	FastISel::~FastISel() = default;
1910
1911	bool FastISel::fastLowerArguments() { return false; }
1912
1913	bool FastISel::fastLowerCall(CallLoweringInfo & /*CLI*/) { return false; }
1914
1915	bool FastISel::fastLowerIntrinsicCall(const IntrinsicInst * /*II*/) {
1916	return false;
1917	}
1918
1919	unsigned FastISel::fastEmit_(MVT, MVT, unsigned) { return 0; }
1920
1921	unsigned FastISel::fastEmit_r(MVT, MVT, unsigned, unsigned /*Op0*/) {
1922	return 0;
1923	}
1924
1925	unsigned FastISel::fastEmit_rr(MVT, MVT, unsigned, unsigned /*Op0*/,
1926	unsigned /*Op1*/) {
1927	return 0;
1928	}
1929
1930	unsigned FastISel::fastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
1931	return 0;
1932	}
1933
1934	unsigned FastISel::fastEmit_f(MVT, MVT, unsigned,
1935	const ConstantFP * /*FPImm*/) {
1936	return 0;
1937	}
1938
1939	unsigned FastISel::fastEmit_ri(MVT, MVT, unsigned, unsigned /*Op0*/,
1940	uint64_t /*Imm*/) {
1941	return 0;
1942	}
1943
1944	/// This method is a wrapper of fastEmit_ri. It first tries to emit an
1945	/// instruction with an immediate operand using fastEmit_ri.
1946	/// If that fails, it materializes the immediate into a register and try
1947	/// fastEmit_rr instead.
1948	Register FastISel::fastEmit_ri_(MVT VT, unsigned Opcode, unsigned Op0,
1949	uint64_t Imm, MVT ImmType) {
1950	// If this is a multiply by a power of two, emit this as a shift left.
1951	if (Opcode == ISD::MUL && isPowerOf2_64(Value: Imm)) {
1952	Opcode = ISD::SHL;
1953	Imm = Log2_64(Value: Imm);
1954	} else if (Opcode == ISD::UDIV && isPowerOf2_64(Value: Imm)) {
1955	// div x, 8 -> srl x, 3
1956	Opcode = ISD::SRL;
1957	Imm = Log2_64(Value: Imm);
1958	}
1959
1960	// Horrible hack (to be removed), check to make sure shift amounts are
1961	// in-range.
1962	if ((Opcode == ISD::SHL || Opcode == ISD::SRA || Opcode == ISD::SRL) &&
1963	Imm >= VT.getSizeInBits())
1964	return 0;
1965
1966	// First check if immediate type is legal. If not, we can't use the ri form.
1967	Register ResultReg = fastEmit_ri(VT, VT, Opcode, Op0, Imm);
1968	if (ResultReg)
1969	return ResultReg;
1970	Register MaterialReg = fastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
1971	if (!MaterialReg) {
1972	// This is a bit ugly/slow, but failing here means falling out of
1973	// fast-isel, which would be very slow.
1974	IntegerType *ITy =
1975	IntegerType::get(C&: FuncInfo.Fn->getContext(), NumBits: VT.getSizeInBits());
1976	MaterialReg = getRegForValue(V: ConstantInt::get(Ty: ITy, V: Imm));
1977	if (!MaterialReg)
1978	return 0;
1979	}
1980	return fastEmit_rr(VT, VT, Opcode, Op0, MaterialReg);
1981	}
1982
1983	Register FastISel::createResultReg(const TargetRegisterClass *RC) {
1984	return MRI.createVirtualRegister(RegClass: RC);
1985	}
1986
1987	Register FastISel::constrainOperandRegClass(const MCInstrDesc &II, Register Op,
1988	unsigned OpNum) {
1989	if (Op.isVirtual()) {
1990	const TargetRegisterClass *RegClass =
1991	TII.getRegClass(MCID: II, OpNum, TRI: &TRI, MF: *FuncInfo.MF);
1992	if (!MRI.constrainRegClass(Reg: Op, RC: RegClass)) {
1993	// If it's not legal to COPY between the register classes, something
1994	// has gone very wrong before we got here.
1995	Register NewOp = createResultReg(RC: RegClass);
1996	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD,
1997	MCID: TII.get(Opcode: TargetOpcode::COPY), DestReg: NewOp).addReg(RegNo: Op);
1998	return NewOp;
1999	}
2000	}
2001	return Op;
2002	}
2003
2004	Register FastISel::fastEmitInst_(unsigned MachineInstOpcode,
2005	const TargetRegisterClass *RC) {
2006	Register ResultReg = createResultReg(RC);
2007	const MCInstrDesc &II = TII.get(Opcode: MachineInstOpcode);
2008
2009	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II, DestReg: ResultReg);
2010	return ResultReg;
2011	}
2012
2013	Register FastISel::fastEmitInst_r(unsigned MachineInstOpcode,
2014	const TargetRegisterClass *RC, unsigned Op0) {
2015	const MCInstrDesc &II = TII.get(Opcode: MachineInstOpcode);
2016
2017	Register ResultReg = createResultReg(RC);
2018	Op0 = constrainOperandRegClass(II, Op: Op0, OpNum: II.getNumDefs());
2019
2020	if (II.getNumDefs() >= 1)
2021	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II, DestReg: ResultReg)
2022	.addReg(RegNo: Op0);
2023	else {
2024	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II)
2025	.addReg(RegNo: Op0);
2026	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: TII.get(Opcode: TargetOpcode::COPY),
2027	DestReg: ResultReg)
2028	.addReg(RegNo: II.implicit_defs()[0]);
2029	}
2030
2031	return ResultReg;
2032	}
2033
2034	Register FastISel::fastEmitInst_rr(unsigned MachineInstOpcode,
2035	const TargetRegisterClass *RC, unsigned Op0,
2036	unsigned Op1) {
2037	const MCInstrDesc &II = TII.get(Opcode: MachineInstOpcode);
2038
2039	Register ResultReg = createResultReg(RC);
2040	Op0 = constrainOperandRegClass(II, Op: Op0, OpNum: II.getNumDefs());
2041	Op1 = constrainOperandRegClass(II, Op: Op1, OpNum: II.getNumDefs() + 1);
2042
2043	if (II.getNumDefs() >= 1)
2044	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II, DestReg: ResultReg)
2045	.addReg(RegNo: Op0)
2046	.addReg(RegNo: Op1);
2047	else {
2048	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II)
2049	.addReg(RegNo: Op0)
2050	.addReg(RegNo: Op1);
2051	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: TII.get(Opcode: TargetOpcode::COPY),
2052	DestReg: ResultReg)
2053	.addReg(RegNo: II.implicit_defs()[0]);
2054	}
2055	return ResultReg;
2056	}
2057
2058	Register FastISel::fastEmitInst_rrr(unsigned MachineInstOpcode,
2059	const TargetRegisterClass *RC, unsigned Op0,
2060	unsigned Op1, unsigned Op2) {
2061	const MCInstrDesc &II = TII.get(Opcode: MachineInstOpcode);
2062
2063	Register ResultReg = createResultReg(RC);
2064	Op0 = constrainOperandRegClass(II, Op: Op0, OpNum: II.getNumDefs());
2065	Op1 = constrainOperandRegClass(II, Op: Op1, OpNum: II.getNumDefs() + 1);
2066	Op2 = constrainOperandRegClass(II, Op: Op2, OpNum: II.getNumDefs() + 2);
2067
2068	if (II.getNumDefs() >= 1)
2069	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II, DestReg: ResultReg)
2070	.addReg(RegNo: Op0)
2071	.addReg(RegNo: Op1)
2072	.addReg(RegNo: Op2);
2073	else {
2074	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II)
2075	.addReg(RegNo: Op0)
2076	.addReg(RegNo: Op1)
2077	.addReg(RegNo: Op2);
2078	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: TII.get(Opcode: TargetOpcode::COPY),
2079	DestReg: ResultReg)
2080	.addReg(RegNo: II.implicit_defs()[0]);
2081	}
2082	return ResultReg;
2083	}
2084
2085	Register FastISel::fastEmitInst_ri(unsigned MachineInstOpcode,
2086	const TargetRegisterClass *RC, unsigned Op0,
2087	uint64_t Imm) {
2088	const MCInstrDesc &II = TII.get(Opcode: MachineInstOpcode);
2089
2090	Register ResultReg = createResultReg(RC);
2091	Op0 = constrainOperandRegClass(II, Op: Op0, OpNum: II.getNumDefs());
2092
2093	if (II.getNumDefs() >= 1)
2094	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II, DestReg: ResultReg)
2095	.addReg(RegNo: Op0)
2096	.addImm(Val: Imm);
2097	else {
2098	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II)
2099	.addReg(RegNo: Op0)
2100	.addImm(Val: Imm);
2101	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: TII.get(Opcode: TargetOpcode::COPY),
2102	DestReg: ResultReg)
2103	.addReg(RegNo: II.implicit_defs()[0]);
2104	}
2105	return ResultReg;
2106	}
2107
2108	Register FastISel::fastEmitInst_rii(unsigned MachineInstOpcode,
2109	const TargetRegisterClass *RC, unsigned Op0,
2110	uint64_t Imm1, uint64_t Imm2) {
2111	const MCInstrDesc &II = TII.get(Opcode: MachineInstOpcode);
2112
2113	Register ResultReg = createResultReg(RC);
2114	Op0 = constrainOperandRegClass(II, Op: Op0, OpNum: II.getNumDefs());
2115
2116	if (II.getNumDefs() >= 1)
2117	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II, DestReg: ResultReg)
2118	.addReg(RegNo: Op0)
2119	.addImm(Val: Imm1)
2120	.addImm(Val: Imm2);
2121	else {
2122	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II)
2123	.addReg(RegNo: Op0)
2124	.addImm(Val: Imm1)
2125	.addImm(Val: Imm2);
2126	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: TII.get(Opcode: TargetOpcode::COPY),
2127	DestReg: ResultReg)
2128	.addReg(RegNo: II.implicit_defs()[0]);
2129	}
2130	return ResultReg;
2131	}
2132
2133	Register FastISel::fastEmitInst_f(unsigned MachineInstOpcode,
2134	const TargetRegisterClass *RC,
2135	const ConstantFP *FPImm) {
2136	const MCInstrDesc &II = TII.get(Opcode: MachineInstOpcode);
2137
2138	Register ResultReg = createResultReg(RC);
2139
2140	if (II.getNumDefs() >= 1)
2141	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II, DestReg: ResultReg)
2142	.addFPImm(Val: FPImm);
2143	else {
2144	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II)
2145	.addFPImm(Val: FPImm);
2146	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: TII.get(Opcode: TargetOpcode::COPY),
2147	DestReg: ResultReg)
2148	.addReg(RegNo: II.implicit_defs()[0]);
2149	}
2150	return ResultReg;
2151	}
2152
2153	Register FastISel::fastEmitInst_rri(unsigned MachineInstOpcode,
2154	const TargetRegisterClass *RC, unsigned Op0,
2155	unsigned Op1, uint64_t Imm) {
2156	const MCInstrDesc &II = TII.get(Opcode: MachineInstOpcode);
2157
2158	Register ResultReg = createResultReg(RC);
2159	Op0 = constrainOperandRegClass(II, Op: Op0, OpNum: II.getNumDefs());
2160	Op1 = constrainOperandRegClass(II, Op: Op1, OpNum: II.getNumDefs() + 1);
2161
2162	if (II.getNumDefs() >= 1)
2163	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II, DestReg: ResultReg)
2164	.addReg(RegNo: Op0)
2165	.addReg(RegNo: Op1)
2166	.addImm(Val: Imm);
2167	else {
2168	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II)
2169	.addReg(RegNo: Op0)
2170	.addReg(RegNo: Op1)
2171	.addImm(Val: Imm);
2172	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: TII.get(Opcode: TargetOpcode::COPY),
2173	DestReg: ResultReg)
2174	.addReg(RegNo: II.implicit_defs()[0]);
2175	}
2176	return ResultReg;
2177	}
2178
2179	Register FastISel::fastEmitInst_i(unsigned MachineInstOpcode,
2180	const TargetRegisterClass *RC, uint64_t Imm) {
2181	Register ResultReg = createResultReg(RC);
2182	const MCInstrDesc &II = TII.get(Opcode: MachineInstOpcode);
2183
2184	if (II.getNumDefs() >= 1)
2185	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II, DestReg: ResultReg)
2186	.addImm(Val: Imm);
2187	else {
2188	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: II).addImm(Val: Imm);
2189	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: TII.get(Opcode: TargetOpcode::COPY),
2190	DestReg: ResultReg)
2191	.addReg(RegNo: II.implicit_defs()[0]);
2192	}
2193	return ResultReg;
2194	}
2195
2196	Register FastISel::fastEmitInst_extractsubreg(MVT RetVT, unsigned Op0,
2197	uint32_t Idx) {
2198	Register ResultReg = createResultReg(RC: TLI.getRegClassFor(VT: RetVT));
2199	assert(Register::isVirtualRegister(Op0) &&
2200	"Cannot yet extract from physregs");
2201	const TargetRegisterClass *RC = MRI.getRegClass(Reg: Op0);
2202	MRI.constrainRegClass(Reg: Op0, RC: TRI.getSubClassWithSubReg(RC, Idx));
2203	BuildMI(BB&: *FuncInfo.MBB, I: FuncInfo.InsertPt, MIMD, MCID: TII.get(Opcode: TargetOpcode::COPY),
2204	DestReg: ResultReg).addReg(RegNo: Op0, flags: 0, SubReg: Idx);
2205	return ResultReg;
2206	}
2207
2208	/// Emit MachineInstrs to compute the value of Op with all but the least
2209	/// significant bit set to zero.
2210	Register FastISel::fastEmitZExtFromI1(MVT VT, unsigned Op0) {
2211	return fastEmit_ri(VT, VT, ISD::AND, Op0, 1);
2212	}
2213
2214	/// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
2215	/// Emit code to ensure constants are copied into registers when needed.
2216	/// Remember the virtual registers that need to be added to the Machine PHI
2217	/// nodes as input. We cannot just directly add them, because expansion
2218	/// might result in multiple MBB's for one BB. As such, the start of the
2219	/// BB might correspond to a different MBB than the end.
2220	bool FastISel::handlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) {
2221	SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled;
2222	FuncInfo.OrigNumPHINodesToUpdate = FuncInfo.PHINodesToUpdate.size();
2223
2224	// Check successor nodes' PHI nodes that expect a constant to be available
2225	// from this block.
2226	for (const BasicBlock *SuccBB : successors(BB: LLVMBB)) {
2227	if (!isa<PHINode>(Val: SuccBB->begin()))
2228	continue;
2229	MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
2230
2231	// If this terminator has multiple identical successors (common for
2232	// switches), only handle each succ once.
2233	if (!SuccsHandled.insert(Ptr: SuccMBB).second)
2234	continue;
2235
2236	MachineBasicBlock::iterator MBBI = SuccMBB->begin();
2237
2238	// At this point we know that there is a 1-1 correspondence between LLVM PHI
2239	// nodes and Machine PHI nodes, but the incoming operands have not been
2240	// emitted yet.
2241	for (const PHINode &PN : SuccBB->phis()) {
2242	// Ignore dead phi's.
2243	if (PN.use_empty())
2244	continue;
2245
2246	// Only handle legal types. Two interesting things to note here. First,
2247	// by bailing out early, we may leave behind some dead instructions,
2248	// since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its
2249	// own moves. Second, this check is necessary because FastISel doesn't
2250	// use CreateRegs to create registers, so it always creates
2251	// exactly one register for each non-void instruction.
2252	EVT VT = TLI.getValueType(DL, Ty: PN.getType(), /*AllowUnknown=*/true);
2253	if (VT == MVT::Other || !TLI.isTypeLegal(VT)) {
2254	// Handle integer promotions, though, because they're common and easy.
2255	if (!(VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)) {
2256	FuncInfo.PHINodesToUpdate.resize(new_size: FuncInfo.OrigNumPHINodesToUpdate);
2257	return false;
2258	}
2259	}
2260
2261	const Value *PHIOp = PN.getIncomingValueForBlock(BB: LLVMBB);
2262
2263	// Set the DebugLoc for the copy. Use the location of the operand if
2264	// there is one; otherwise no location, flushLocalValueMap will fix it.
2265	MIMD = {};
2266	if (const auto *Inst = dyn_cast<Instruction>(Val: PHIOp))
2267	MIMD = MIMetadata(*Inst);
2268
2269	Register Reg = getRegForValue(V: PHIOp);
2270	if (!Reg) {
2271	FuncInfo.PHINodesToUpdate.resize(new_size: FuncInfo.OrigNumPHINodesToUpdate);
2272	return false;
2273	}
2274	FuncInfo.PHINodesToUpdate.push_back(x: std::make_pair(x: &*MBBI++, y&: Reg));
2275	MIMD = {};
2276	}
2277	}
2278
2279	return true;
2280	}
2281
2282	bool FastISel::tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst) {
2283	assert(LI->hasOneUse() &&
2284	"tryToFoldLoad expected a LoadInst with a single use");
2285	// We know that the load has a single use, but don't know what it is. If it
2286	// isn't one of the folded instructions, then we can't succeed here. Handle
2287	// this by scanning the single-use users of the load until we get to FoldInst.
2288	unsigned MaxUsers = 6; // Don't scan down huge single-use chains of instrs.
2289
2290	const Instruction *TheUser = LI->user_back();
2291	while (TheUser != FoldInst && // Scan up until we find FoldInst.
2292	// Stay in the right block.
2293	TheUser->getParent() == FoldInst->getParent() &&
2294	--MaxUsers) { // Don't scan too far.
2295	// If there are multiple or no uses of this instruction, then bail out.
2296	if (!TheUser->hasOneUse())
2297	return false;
2298
2299	TheUser = TheUser->user_back();
2300	}
2301
2302	// If we didn't find the fold instruction, then we failed to collapse the
2303	// sequence.
2304	if (TheUser != FoldInst)
2305	return false;
2306
2307	// Don't try to fold volatile loads. Target has to deal with alignment
2308	// constraints.
2309	if (LI->isVolatile())
2310	return false;
2311
2312	// Figure out which vreg this is going into. If there is no assigned vreg yet
2313	// then there actually was no reference to it. Perhaps the load is referenced
2314	// by a dead instruction.
2315	Register LoadReg = getRegForValue(V: LI);
2316	if (!LoadReg)
2317	return false;
2318
2319	// We can't fold if this vreg has no uses or more than one use. Multiple uses
2320	// may mean that the instruction got lowered to multiple MIs, or the use of
2321	// the loaded value ended up being multiple operands of the result.
2322	if (!MRI.hasOneUse(RegNo: LoadReg))
2323	return false;
2324
2325	// If the register has fixups, there may be additional uses through a
2326	// different alias of the register.
2327	if (FuncInfo.RegsWithFixups.contains(V: LoadReg))
2328	return false;
2329
2330	MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(RegNo: LoadReg);
2331	MachineInstr *User = RI->getParent();
2332
2333	// Set the insertion point properly. Folding the load can cause generation of
2334	// other random instructions (like sign extends) for addressing modes; make
2335	// sure they get inserted in a logical place before the new instruction.
2336	FuncInfo.InsertPt = User;
2337	FuncInfo.MBB = User->getParent();
2338
2339	// Ask the target to try folding the load.
2340	return tryToFoldLoadIntoMI(User, RI.getOperandNo(), LI);
2341	}
2342
2343	bool FastISel::canFoldAddIntoGEP(const User *GEP, const Value *Add) {
2344	// Must be an add.
2345	if (!isa<AddOperator>(Val: Add))
2346	return false;
2347	// Type size needs to match.
2348	if (DL.getTypeSizeInBits(Ty: GEP->getType()) !=
2349	DL.getTypeSizeInBits(Ty: Add->getType()))
2350	return false;
2351	// Must be in the same basic block.
2352	if (isa<Instruction>(Val: Add) &&
2353	FuncInfo.MBBMap[cast<Instruction>(Val: Add)->getParent()] != FuncInfo.MBB)
2354	return false;
2355	// Must have a constant operand.
2356	return isa<ConstantInt>(Val: cast<AddOperator>(Val: Add)->getOperand(i_nocapture: 1));
2357	}
2358
2359	MachineMemOperand *
2360	FastISel::createMachineMemOperandFor(const Instruction *I) const {
2361	const Value *Ptr;
2362	Type *ValTy;
2363	MaybeAlign Alignment;
2364	MachineMemOperand::Flags Flags;
2365	bool IsVolatile;
2366
2367	if (const auto *LI = dyn_cast<LoadInst>(Val: I)) {
2368	Alignment = LI->getAlign();
2369	IsVolatile = LI->isVolatile();
2370	Flags = MachineMemOperand::MOLoad;
2371	Ptr = LI->getPointerOperand();
2372	ValTy = LI->getType();
2373	} else if (const auto *SI = dyn_cast<StoreInst>(Val: I)) {
2374	Alignment = SI->getAlign();
2375	IsVolatile = SI->isVolatile();
2376	Flags = MachineMemOperand::MOStore;
2377	Ptr = SI->getPointerOperand();
2378	ValTy = SI->getValueOperand()->getType();
2379	} else
2380	return nullptr;
2381
2382	bool IsNonTemporal = I->hasMetadata(KindID: LLVMContext::MD_nontemporal);
2383	bool IsInvariant = I->hasMetadata(KindID: LLVMContext::MD_invariant_load);
2384	bool IsDereferenceable = I->hasMetadata(KindID: LLVMContext::MD_dereferenceable);
2385	const MDNode *Ranges = I->getMetadata(KindID: LLVMContext::MD_range);
2386
2387	AAMDNodes AAInfo = I->getAAMetadata();
2388
2389	if (!Alignment) // Ensure that codegen never sees alignment 0.
2390	Alignment = DL.getABITypeAlign(Ty: ValTy);
2391
2392	unsigned Size = DL.getTypeStoreSize(Ty: ValTy);
2393
2394	if (IsVolatile)
2395	Flags |= MachineMemOperand::MOVolatile;
2396	if (IsNonTemporal)
2397	Flags |= MachineMemOperand::MONonTemporal;
2398	if (IsDereferenceable)
2399	Flags |= MachineMemOperand::MODereferenceable;
2400	if (IsInvariant)
2401	Flags |= MachineMemOperand::MOInvariant;
2402
2403	return FuncInfo.MF->getMachineMemOperand(PtrInfo: MachinePointerInfo(Ptr), f: Flags, s: Size,
2404	base_alignment: *Alignment, AAInfo, Ranges);
2405	}
2406
2407	CmpInst::Predicate FastISel::optimizeCmpPredicate(const CmpInst *CI) const {
2408	// If both operands are the same, then try to optimize or fold the cmp.
2409	CmpInst::Predicate Predicate = CI->getPredicate();
2410	if (CI->getOperand(i_nocapture: 0) != CI->getOperand(i_nocapture: 1))
2411	return Predicate;
2412
2413	switch (Predicate) {
2414	default: llvm_unreachable("Invalid predicate!");
2415	case CmpInst::FCMP_FALSE: Predicate = CmpInst::FCMP_FALSE; break;
2416	case CmpInst::FCMP_OEQ: Predicate = CmpInst::FCMP_ORD; break;
2417	case CmpInst::FCMP_OGT: Predicate = CmpInst::FCMP_FALSE; break;
2418	case CmpInst::FCMP_OGE: Predicate = CmpInst::FCMP_ORD; break;
2419	case CmpInst::FCMP_OLT: Predicate = CmpInst::FCMP_FALSE; break;
2420	case CmpInst::FCMP_OLE: Predicate = CmpInst::FCMP_ORD; break;
2421	case CmpInst::FCMP_ONE: Predicate = CmpInst::FCMP_FALSE; break;
2422	case CmpInst::FCMP_ORD: Predicate = CmpInst::FCMP_ORD; break;
2423	case CmpInst::FCMP_UNO: Predicate = CmpInst::FCMP_UNO; break;
2424	case CmpInst::FCMP_UEQ: Predicate = CmpInst::FCMP_TRUE; break;
2425	case CmpInst::FCMP_UGT: Predicate = CmpInst::FCMP_UNO; break;
2426	case CmpInst::FCMP_UGE: Predicate = CmpInst::FCMP_TRUE; break;
2427	case CmpInst::FCMP_ULT: Predicate = CmpInst::FCMP_UNO; break;
2428	case CmpInst::FCMP_ULE: Predicate = CmpInst::FCMP_TRUE; break;
2429	case CmpInst::FCMP_UNE: Predicate = CmpInst::FCMP_UNO; break;
2430	case CmpInst::FCMP_TRUE: Predicate = CmpInst::FCMP_TRUE; break;
2431
2432	case CmpInst::ICMP_EQ: Predicate = CmpInst::FCMP_TRUE; break;
2433	case CmpInst::ICMP_NE: Predicate = CmpInst::FCMP_FALSE; break;
2434	case CmpInst::ICMP_UGT: Predicate = CmpInst::FCMP_FALSE; break;
2435	case CmpInst::ICMP_UGE: Predicate = CmpInst::FCMP_TRUE; break;
2436	case CmpInst::ICMP_ULT: Predicate = CmpInst::FCMP_FALSE; break;
2437	case CmpInst::ICMP_ULE: Predicate = CmpInst::FCMP_TRUE; break;
2438	case CmpInst::ICMP_SGT: Predicate = CmpInst::FCMP_FALSE; break;
2439	case CmpInst::ICMP_SGE: Predicate = CmpInst::FCMP_TRUE; break;
2440	case CmpInst::ICMP_SLT: Predicate = CmpInst::FCMP_FALSE; break;
2441	case CmpInst::ICMP_SLE: Predicate = CmpInst::FCMP_TRUE; break;
2442	}
2443
2444	return Predicate;
2445	}
2446