1//===-- Analysis.cpp - CodeGen LLVM IR Analysis Utilities -----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines several CodeGen-specific LLVM IR analysis utilities.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/CodeGen/Analysis.h"
14#include "llvm/Analysis/ValueTracking.h"
15#include "llvm/BinaryFormat/Dwarf.h"
16#include "llvm/CodeGen/MachineFunction.h"
17#include "llvm/CodeGen/TargetInstrInfo.h"
18#include "llvm/CodeGen/TargetLowering.h"
19#include "llvm/CodeGen/TargetSubtargetInfo.h"
20#include "llvm/IR/DataLayout.h"
21#include "llvm/IR/DerivedTypes.h"
22#include "llvm/IR/Function.h"
23#include "llvm/IR/Instructions.h"
24#include "llvm/IR/IntrinsicInst.h"
25#include "llvm/IR/Module.h"
26#include "llvm/Support/ErrorHandling.h"
27#include "llvm/Target/TargetLoweringObjectFile.h"
28#include "llvm/Target/TargetMachine.h"
29
30using namespace llvm;
31
32/// Compute the linearized index of a member in a nested aggregate/struct/array
33/// by recursing and accumulating CurIndex as long as there are indices in the
34/// index list.
35unsigned llvm::ComputeLinearIndex(Type *Ty,
36 const unsigned *Indices,
37 const unsigned *IndicesEnd,
38 unsigned CurIndex) {
39 // Base case: We're done.
40 if (Indices && Indices == IndicesEnd)
41 return CurIndex;
42
43 // Given a struct type, recursively traverse the elements.
44 if (StructType *STy = dyn_cast<StructType>(Val: Ty)) {
45 for (auto I : llvm::enumerate(First: STy->elements())) {
46 Type *ET = I.value();
47 if (Indices && *Indices == I.index())
48 return ComputeLinearIndex(Ty: ET, Indices: Indices + 1, IndicesEnd, CurIndex);
49 CurIndex = ComputeLinearIndex(Ty: ET, Indices: nullptr, IndicesEnd: nullptr, CurIndex);
50 }
51 assert(!Indices && "Unexpected out of bound");
52 return CurIndex;
53 }
54 // Given an array type, recursively traverse the elements.
55 else if (ArrayType *ATy = dyn_cast<ArrayType>(Val: Ty)) {
56 Type *EltTy = ATy->getElementType();
57 unsigned NumElts = ATy->getNumElements();
58 // Compute the Linear offset when jumping one element of the array
59 unsigned EltLinearOffset = ComputeLinearIndex(Ty: EltTy, Indices: nullptr, IndicesEnd: nullptr, CurIndex: 0);
60 if (Indices) {
61 assert(*Indices < NumElts && "Unexpected out of bound");
62 // If the indice is inside the array, compute the index to the requested
63 // elt and recurse inside the element with the end of the indices list
64 CurIndex += EltLinearOffset* *Indices;
65 return ComputeLinearIndex(Ty: EltTy, Indices: Indices+1, IndicesEnd, CurIndex);
66 }
67 CurIndex += EltLinearOffset*NumElts;
68 return CurIndex;
69 }
70 // We haven't found the type we're looking for, so keep searching.
71 return CurIndex + 1;
72}
73
74void llvm::ComputeValueTypes(const DataLayout &DL, Type *Ty,
75 SmallVectorImpl<Type *> &Types,
76 SmallVectorImpl<TypeSize> *Offsets,
77 TypeSize StartingOffset) {
78 assert((Ty->isScalableTy() == StartingOffset.isScalable() ||
79 StartingOffset.isZero()) &&
80 "Offset/TypeSize mismatch!");
81 // Given a struct type, recursively traverse the elements.
82 if (StructType *STy = dyn_cast<StructType>(Val: Ty)) {
83 // If the Offsets aren't needed, don't query the struct layout. This allows
84 // us to support structs with scalable vectors for operations that don't
85 // need offsets.
86 const StructLayout *SL = Offsets ? DL.getStructLayout(Ty: STy) : nullptr;
87 for (StructType::element_iterator EB = STy->element_begin(), EI = EB,
88 EE = STy->element_end();
89 EI != EE; ++EI) {
90 // Don't compute the element offset if we didn't get a StructLayout above.
91 TypeSize EltOffset =
92 SL ? SL->getElementOffset(Idx: EI - EB) : TypeSize::getZero();
93 ComputeValueTypes(DL, Ty: *EI, Types, Offsets, StartingOffset: StartingOffset + EltOffset);
94 }
95 return;
96 }
97 // Given an array type, recursively traverse the elements.
98 if (ArrayType *ATy = dyn_cast<ArrayType>(Val: Ty)) {
99 Type *EltTy = ATy->getElementType();
100 TypeSize EltSize = DL.getTypeAllocSize(Ty: EltTy);
101 for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
102 ComputeValueTypes(DL, Ty: EltTy, Types, Offsets,
103 StartingOffset: StartingOffset + i * EltSize);
104 return;
105 }
106 // Interpret void as zero return values.
107 if (Ty->isVoidTy())
108 return;
109 Types.push_back(Elt: Ty);
110 if (Offsets)
111 Offsets->push_back(Elt: StartingOffset);
112}
113
114/// ComputeValueVTs - Given an LLVM IR type, compute a sequence of
115/// EVTs that represent all the individual underlying
116/// non-aggregate types that comprise it.
117///
118/// If Offsets is non-null, it points to a vector to be filled in
119/// with the in-memory offsets of each of the individual values.
120///
121void llvm::ComputeValueVTs(const TargetLowering &TLI, const DataLayout &DL,
122 Type *Ty, SmallVectorImpl<EVT> &ValueVTs,
123 SmallVectorImpl<EVT> *MemVTs,
124 SmallVectorImpl<TypeSize> *Offsets,
125 TypeSize StartingOffset) {
126 SmallVector<Type *> Types;
127 ComputeValueTypes(DL, Ty, Types, Offsets, StartingOffset);
128 ValueVTs.reserve(N: Types.size());
129 if (MemVTs)
130 MemVTs->reserve(N: Types.size());
131 for (Type *Ty : Types) {
132 ValueVTs.push_back(Elt: TLI.getValueType(DL, Ty));
133 if (MemVTs)
134 MemVTs->push_back(Elt: TLI.getMemValueType(DL, Ty));
135 }
136}
137
138void llvm::ComputeValueVTs(const TargetLowering &TLI, const DataLayout &DL,
139 Type *Ty, SmallVectorImpl<EVT> &ValueVTs,
140 SmallVectorImpl<EVT> *MemVTs,
141 SmallVectorImpl<uint64_t> *FixedOffsets,
142 uint64_t StartingOffset) {
143 TypeSize Offset = TypeSize::getFixed(ExactSize: StartingOffset);
144 if (FixedOffsets) {
145 SmallVector<TypeSize, 4> Offsets;
146 ComputeValueVTs(TLI, DL, Ty, ValueVTs, MemVTs, Offsets: &Offsets, StartingOffset: Offset);
147 FixedOffsets->reserve(N: Offsets.size());
148 for (TypeSize Offset : Offsets)
149 FixedOffsets->push_back(Elt: Offset.getFixedValue());
150 } else {
151 ComputeValueVTs(TLI, DL, Ty, ValueVTs, MemVTs, Offsets: nullptr, StartingOffset: Offset);
152 }
153}
154
155void llvm::computeValueLLTs(const DataLayout &DL, Type &Ty,
156 SmallVectorImpl<LLT> &ValueLLTs,
157 SmallVectorImpl<TypeSize> *Offsets,
158 TypeSize StartingOffset) {
159 SmallVector<Type *> ValTys;
160 ComputeValueTypes(DL, Ty: &Ty, Types&: ValTys, Offsets, StartingOffset);
161 ValueLLTs.reserve(N: ValTys.size());
162 for (Type *ValTy : ValTys)
163 ValueLLTs.push_back(Elt: getLLTForType(Ty&: *ValTy, DL));
164}
165
166void llvm::computeValueLLTs(const DataLayout &DL, Type &Ty,
167 SmallVectorImpl<LLT> &ValueLLTs,
168 SmallVectorImpl<uint64_t> *FixedOffsets,
169 uint64_t FixedStartingOffset) {
170 TypeSize StartingOffset = TypeSize::getFixed(ExactSize: FixedStartingOffset);
171 if (FixedOffsets) {
172 SmallVector<TypeSize, 4> Offsets;
173 computeValueLLTs(DL, Ty, ValueLLTs, Offsets: &Offsets, StartingOffset);
174 FixedOffsets->reserve(N: Offsets.size());
175 for (TypeSize Offset : Offsets)
176 FixedOffsets->push_back(Elt: Offset.getFixedValue());
177 } else {
178 computeValueLLTs(DL, Ty, ValueLLTs, Offsets: nullptr, StartingOffset);
179 }
180}
181
182/// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V.
183GlobalValue *llvm::ExtractTypeInfo(Value *V) {
184 V = V->stripPointerCasts();
185 GlobalValue *GV = dyn_cast<GlobalValue>(Val: V);
186 GlobalVariable *Var = dyn_cast<GlobalVariable>(Val: V);
187
188 if (Var && Var->getName() == "llvm.eh.catch.all.value") {
189 assert(Var->hasInitializer() &&
190 "The EH catch-all value must have an initializer");
191 Value *Init = Var->getInitializer();
192 GV = dyn_cast<GlobalValue>(Val: Init);
193 if (!GV) V = cast<ConstantPointerNull>(Val: Init);
194 }
195
196 assert((GV || isa<ConstantPointerNull>(V)) &&
197 "TypeInfo must be a global variable or NULL");
198 return GV;
199}
200
201bool llvm::isExceptionPointerAndSelectorType(Type *Ty) {
202 auto *STy = dyn_cast<StructType>(Val: Ty);
203 if (!STy || STy->getNumElements() != 2)
204 return false;
205 Type *ExnTy = STy->getElementType(N: 0);
206 return (ExnTy->isPointerTy() || ExnTy->isIntegerTy()) &&
207 STy->getElementType(N: 1)->isIntegerTy();
208}
209
210/// getFCmpCondCode - Return the ISD condition code corresponding to
211/// the given LLVM IR floating-point condition code. This includes
212/// consideration of global floating-point math flags.
213///
214ISD::CondCode llvm::getFCmpCondCode(FCmpInst::Predicate Pred) {
215 switch (Pred) {
216 case FCmpInst::FCMP_FALSE: return ISD::SETFALSE;
217 case FCmpInst::FCMP_OEQ: return ISD::SETOEQ;
218 case FCmpInst::FCMP_OGT: return ISD::SETOGT;
219 case FCmpInst::FCMP_OGE: return ISD::SETOGE;
220 case FCmpInst::FCMP_OLT: return ISD::SETOLT;
221 case FCmpInst::FCMP_OLE: return ISD::SETOLE;
222 case FCmpInst::FCMP_ONE: return ISD::SETONE;
223 case FCmpInst::FCMP_ORD: return ISD::SETO;
224 case FCmpInst::FCMP_UNO: return ISD::SETUO;
225 case FCmpInst::FCMP_UEQ: return ISD::SETUEQ;
226 case FCmpInst::FCMP_UGT: return ISD::SETUGT;
227 case FCmpInst::FCMP_UGE: return ISD::SETUGE;
228 case FCmpInst::FCMP_ULT: return ISD::SETULT;
229 case FCmpInst::FCMP_ULE: return ISD::SETULE;
230 case FCmpInst::FCMP_UNE: return ISD::SETUNE;
231 case FCmpInst::FCMP_TRUE: return ISD::SETTRUE;
232 default: llvm_unreachable("Invalid FCmp predicate opcode!");
233 }
234}
235
236ISD::CondCode llvm::getFCmpCodeWithoutNaN(ISD::CondCode CC) {
237 switch (CC) {
238 case ISD::SETOEQ: case ISD::SETUEQ: return ISD::SETEQ;
239 case ISD::SETONE: case ISD::SETUNE: return ISD::SETNE;
240 case ISD::SETOLT: case ISD::SETULT: return ISD::SETLT;
241 case ISD::SETOLE: case ISD::SETULE: return ISD::SETLE;
242 case ISD::SETOGT: case ISD::SETUGT: return ISD::SETGT;
243 case ISD::SETOGE: case ISD::SETUGE: return ISD::SETGE;
244 default: return CC;
245 }
246}
247
248ISD::CondCode llvm::getICmpCondCode(ICmpInst::Predicate Pred) {
249 switch (Pred) {
250 case ICmpInst::ICMP_EQ: return ISD::SETEQ;
251 case ICmpInst::ICMP_NE: return ISD::SETNE;
252 case ICmpInst::ICMP_SLE: return ISD::SETLE;
253 case ICmpInst::ICMP_ULE: return ISD::SETULE;
254 case ICmpInst::ICMP_SGE: return ISD::SETGE;
255 case ICmpInst::ICMP_UGE: return ISD::SETUGE;
256 case ICmpInst::ICMP_SLT: return ISD::SETLT;
257 case ICmpInst::ICMP_ULT: return ISD::SETULT;
258 case ICmpInst::ICMP_SGT: return ISD::SETGT;
259 case ICmpInst::ICMP_UGT: return ISD::SETUGT;
260 default:
261 llvm_unreachable("Invalid ICmp predicate opcode!");
262 }
263}
264
265ICmpInst::Predicate llvm::getICmpCondCode(ISD::CondCode Pred) {
266 switch (Pred) {
267 case ISD::SETEQ:
268 return ICmpInst::ICMP_EQ;
269 case ISD::SETNE:
270 return ICmpInst::ICMP_NE;
271 case ISD::SETLE:
272 return ICmpInst::ICMP_SLE;
273 case ISD::SETULE:
274 return ICmpInst::ICMP_ULE;
275 case ISD::SETGE:
276 return ICmpInst::ICMP_SGE;
277 case ISD::SETUGE:
278 return ICmpInst::ICMP_UGE;
279 case ISD::SETLT:
280 return ICmpInst::ICMP_SLT;
281 case ISD::SETULT:
282 return ICmpInst::ICMP_ULT;
283 case ISD::SETGT:
284 return ICmpInst::ICMP_SGT;
285 case ISD::SETUGT:
286 return ICmpInst::ICMP_UGT;
287 default:
288 llvm_unreachable("Invalid ISD integer condition code!");
289 }
290}
291
292ISD::NodeType llvm::getAtomicRMWOpcode(AtomicRMWInst::BinOp Op) {
293 switch (Op) {
294 default:
295 llvm_unreachable("Unknown atomicrmw operation");
296 case AtomicRMWInst::Xchg:
297 return ISD::ATOMIC_SWAP;
298 case AtomicRMWInst::Add:
299 return ISD::ATOMIC_LOAD_ADD;
300 case AtomicRMWInst::Sub:
301 return ISD::ATOMIC_LOAD_SUB;
302 case AtomicRMWInst::And:
303 return ISD::ATOMIC_LOAD_AND;
304 case AtomicRMWInst::Nand:
305 return ISD::ATOMIC_LOAD_NAND;
306 case AtomicRMWInst::Or:
307 return ISD::ATOMIC_LOAD_OR;
308 case AtomicRMWInst::Xor:
309 return ISD::ATOMIC_LOAD_XOR;
310 case AtomicRMWInst::Max:
311 return ISD::ATOMIC_LOAD_MAX;
312 case AtomicRMWInst::Min:
313 return ISD::ATOMIC_LOAD_MIN;
314 case AtomicRMWInst::UMax:
315 return ISD::ATOMIC_LOAD_UMAX;
316 case AtomicRMWInst::UMin:
317 return ISD::ATOMIC_LOAD_UMIN;
318 case AtomicRMWInst::FAdd:
319 return ISD::ATOMIC_LOAD_FADD;
320 case AtomicRMWInst::FSub:
321 return ISD::ATOMIC_LOAD_FSUB;
322 case AtomicRMWInst::FMax:
323 return ISD::ATOMIC_LOAD_FMAX;
324 case AtomicRMWInst::FMin:
325 return ISD::ATOMIC_LOAD_FMIN;
326 case AtomicRMWInst::FMaximum:
327 return ISD::ATOMIC_LOAD_FMAXIMUM;
328 case AtomicRMWInst::FMinimum:
329 return ISD::ATOMIC_LOAD_FMINIMUM;
330 case AtomicRMWInst::FMaximumNum:
331 return ISD::ATOMIC_LOAD_FMAXIMUMNUM;
332 case AtomicRMWInst::FMinimumNum:
333 return ISD::ATOMIC_LOAD_FMINIMUMNUM;
334 case AtomicRMWInst::UIncWrap:
335 return ISD::ATOMIC_LOAD_UINC_WRAP;
336 case AtomicRMWInst::UDecWrap:
337 return ISD::ATOMIC_LOAD_UDEC_WRAP;
338 case AtomicRMWInst::USubCond:
339 return ISD::ATOMIC_LOAD_USUB_COND;
340 case AtomicRMWInst::USubSat:
341 return ISD::ATOMIC_LOAD_USUB_SAT;
342 }
343}
344
345static bool isNoopBitcast(Type *T1, Type *T2,
346 const TargetLoweringBase& TLI) {
347 return T1 == T2 || (T1->isPointerTy() && T2->isPointerTy()) ||
348 (isa<VectorType>(Val: T1) && isa<VectorType>(Val: T2) &&
349 TLI.isTypeLegal(VT: EVT::getEVT(Ty: T1)) && TLI.isTypeLegal(VT: EVT::getEVT(Ty: T2)));
350}
351
352/// Look through operations that will be free to find the earliest source of
353/// this value.
354///
355/// @param ValLoc If V has aggregate type, we will be interested in a particular
356/// scalar component. This records its address; the reverse of this list gives a
357/// sequence of indices appropriate for an extractvalue to locate the important
358/// value. This value is updated during the function and on exit will indicate
359/// similar information for the Value returned.
360///
361/// @param DataBits If this function looks through truncate instructions, this
362/// will record the smallest size attained.
363static const Value *getNoopInput(const Value *V,
364 SmallVectorImpl<unsigned> &ValLoc,
365 unsigned &DataBits,
366 const TargetLoweringBase &TLI,
367 const DataLayout &DL) {
368 while (true) {
369 // Try to look through V1; if V1 is not an instruction, it can't be looked
370 // through.
371 const Instruction *I = dyn_cast<Instruction>(Val: V);
372 if (!I || I->getNumOperands() == 0) return V;
373 const Value *NoopInput = nullptr;
374
375 Value *Op = I->getOperand(i: 0);
376 if (isa<BitCastInst>(Val: I)) {
377 // Look through truly no-op bitcasts.
378 if (isNoopBitcast(T1: Op->getType(), T2: I->getType(), TLI))
379 NoopInput = Op;
380 } else if (isa<GetElementPtrInst>(Val: I)) {
381 // Look through getelementptr
382 if (cast<GetElementPtrInst>(Val: I)->hasAllZeroIndices())
383 NoopInput = Op;
384 } else if (isa<IntToPtrInst>(Val: I)) {
385 // Look through inttoptr.
386 // Make sure this isn't a truncating or extending cast. We could
387 // support this eventually, but don't bother for now.
388 if (!isa<VectorType>(Val: I->getType()) &&
389 DL.getPointerSizeInBits() ==
390 cast<IntegerType>(Val: Op->getType())->getBitWidth())
391 NoopInput = Op;
392 } else if (isa<PtrToIntInst>(Val: I)) {
393 // Look through ptrtoint.
394 // Make sure this isn't a truncating or extending cast. We could
395 // support this eventually, but don't bother for now.
396 if (!isa<VectorType>(Val: I->getType()) &&
397 DL.getPointerSizeInBits() ==
398 cast<IntegerType>(Val: I->getType())->getBitWidth())
399 NoopInput = Op;
400 } else if (isa<TruncInst>(Val: I) &&
401 TLI.allowTruncateForTailCall(FromTy: Op->getType(), ToTy: I->getType())) {
402 DataBits =
403 std::min(a: (uint64_t)DataBits,
404 b: I->getType()->getPrimitiveSizeInBits().getFixedValue());
405 NoopInput = Op;
406 } else if (auto *CB = dyn_cast<CallBase>(Val: I)) {
407 const Value *ReturnedOp = CB->getReturnedArgOperand();
408 if (ReturnedOp && isNoopBitcast(T1: ReturnedOp->getType(), T2: I->getType(), TLI))
409 NoopInput = ReturnedOp;
410 } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Val: V)) {
411 // Value may come from either the aggregate or the scalar
412 ArrayRef<unsigned> InsertLoc = IVI->getIndices();
413 if (ValLoc.size() >= InsertLoc.size() &&
414 std::equal(first1: InsertLoc.begin(), last1: InsertLoc.end(), first2: ValLoc.rbegin())) {
415 // The type being inserted is a nested sub-type of the aggregate; we
416 // have to remove those initial indices to get the location we're
417 // interested in for the operand.
418 ValLoc.resize(N: ValLoc.size() - InsertLoc.size());
419 NoopInput = IVI->getInsertedValueOperand();
420 } else {
421 // The struct we're inserting into has the value we're interested in, no
422 // change of address.
423 NoopInput = Op;
424 }
425 } else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Val: V)) {
426 // The part we're interested in will inevitably be some sub-section of the
427 // previous aggregate. Combine the two paths to obtain the true address of
428 // our element.
429 ArrayRef<unsigned> ExtractLoc = EVI->getIndices();
430 ValLoc.append(in_start: ExtractLoc.rbegin(), in_end: ExtractLoc.rend());
431 NoopInput = Op;
432 }
433 // Terminate if we couldn't find anything to look through.
434 if (!NoopInput)
435 return V;
436
437 V = NoopInput;
438 }
439}
440
441/// Return true if this scalar return value only has bits discarded on its path
442/// from the "tail call" to the "ret". This includes the obvious noop
443/// instructions handled by getNoopInput above as well as free truncations (or
444/// extensions prior to the call).
445static bool slotOnlyDiscardsData(const Value *RetVal, const Value *CallVal,
446 SmallVectorImpl<unsigned> &RetIndices,
447 SmallVectorImpl<unsigned> &CallIndices,
448 bool AllowDifferingSizes,
449 const TargetLoweringBase &TLI,
450 const DataLayout &DL) {
451
452 // Trace the sub-value needed by the return value as far back up the graph as
453 // possible, in the hope that it will intersect with the value produced by the
454 // call. In the simple case with no "returned" attribute, the hope is actually
455 // that we end up back at the tail call instruction itself.
456 unsigned BitsRequired = UINT_MAX;
457 RetVal = getNoopInput(V: RetVal, ValLoc&: RetIndices, DataBits&: BitsRequired, TLI, DL);
458
459 // If this slot in the value returned is undef, it doesn't matter what the
460 // call puts there, it'll be fine.
461 if (isa<UndefValue>(Val: RetVal))
462 return true;
463
464 // Now do a similar search up through the graph to find where the value
465 // actually returned by the "tail call" comes from. In the simple case without
466 // a "returned" attribute, the search will be blocked immediately and the loop
467 // a Noop.
468 unsigned BitsProvided = UINT_MAX;
469 CallVal = getNoopInput(V: CallVal, ValLoc&: CallIndices, DataBits&: BitsProvided, TLI, DL);
470
471 // There's no hope if we can't actually trace them to (the same part of!) the
472 // same value.
473 if (CallVal != RetVal || CallIndices != RetIndices)
474 return false;
475
476 // However, intervening truncates may have made the call non-tail. Make sure
477 // all the bits that are needed by the "ret" have been provided by the "tail
478 // call". FIXME: with sufficiently cunning bit-tracking, we could look through
479 // extensions too.
480 if (BitsProvided < BitsRequired ||
481 (!AllowDifferingSizes && BitsProvided != BitsRequired))
482 return false;
483
484 return true;
485}
486
487/// For an aggregate type, determine whether a given index is within bounds or
488/// not.
489static bool indexReallyValid(Type *T, unsigned Idx) {
490 if (ArrayType *AT = dyn_cast<ArrayType>(Val: T))
491 return Idx < AT->getNumElements();
492
493 return Idx < cast<StructType>(Val: T)->getNumElements();
494}
495
496/// Move the given iterators to the next leaf type in depth first traversal.
497///
498/// Performs a depth-first traversal of the type as specified by its arguments,
499/// stopping at the next leaf node (which may be a legitimate scalar type or an
500/// empty struct or array).
501///
502/// @param SubTypes List of the partial components making up the type from
503/// outermost to innermost non-empty aggregate. The element currently
504/// represented is SubTypes.back()->getTypeAtIndex(Path.back() - 1).
505///
506/// @param Path Set of extractvalue indices leading from the outermost type
507/// (SubTypes[0]) to the leaf node currently represented.
508///
509/// @returns true if a new type was found, false otherwise. Calling this
510/// function again on a finished iterator will repeatedly return
511/// false. SubTypes.back()->getTypeAtIndex(Path.back()) is either an empty
512/// aggregate or a non-aggregate
513static bool advanceToNextLeafType(SmallVectorImpl<Type *> &SubTypes,
514 SmallVectorImpl<unsigned> &Path) {
515 // First march back up the tree until we can successfully increment one of the
516 // coordinates in Path.
517 while (!Path.empty() && !indexReallyValid(T: SubTypes.back(), Idx: Path.back() + 1)) {
518 Path.pop_back();
519 SubTypes.pop_back();
520 }
521
522 // If we reached the top, then the iterator is done.
523 if (Path.empty())
524 return false;
525
526 // We know there's *some* valid leaf now, so march back down the tree picking
527 // out the left-most element at each node.
528 ++Path.back();
529 Type *DeeperType =
530 ExtractValueInst::getIndexedType(Agg: SubTypes.back(), Idxs: Path.back());
531 while (DeeperType->isAggregateType()) {
532 if (!indexReallyValid(T: DeeperType, Idx: 0))
533 return true;
534
535 SubTypes.push_back(Elt: DeeperType);
536 Path.push_back(Elt: 0);
537
538 DeeperType = ExtractValueInst::getIndexedType(Agg: DeeperType, Idxs: 0);
539 }
540
541 return true;
542}
543
544/// Find the first non-empty, scalar-like type in Next and setup the iterator
545/// components.
546///
547/// Assuming Next is an aggregate of some kind, this function will traverse the
548/// tree from left to right (i.e. depth-first) looking for the first
549/// non-aggregate type which will play a role in function return.
550///
551/// For example, if Next was {[0 x i64], {{}, i32, {}}, i32} then we would setup
552/// Path as [1, 1] and SubTypes as [Next, {{}, i32, {}}] to represent the first
553/// i32 in that type.
554static bool firstRealType(Type *Next, SmallVectorImpl<Type *> &SubTypes,
555 SmallVectorImpl<unsigned> &Path) {
556 // First initialise the iterator components to the first "leaf" node
557 // (i.e. node with no valid sub-type at any index, so {} does count as a leaf
558 // despite nominally being an aggregate).
559 while (Type *FirstInner = ExtractValueInst::getIndexedType(Agg: Next, Idxs: 0)) {
560 SubTypes.push_back(Elt: Next);
561 Path.push_back(Elt: 0);
562 Next = FirstInner;
563 }
564
565 // If there's no Path now, Next was originally scalar already (or empty
566 // leaf). We're done.
567 if (Path.empty())
568 return true;
569
570 // Otherwise, use normal iteration to keep looking through the tree until we
571 // find a non-aggregate type.
572 while (ExtractValueInst::getIndexedType(Agg: SubTypes.back(), Idxs: Path.back())
573 ->isAggregateType()) {
574 if (!advanceToNextLeafType(SubTypes, Path))
575 return false;
576 }
577
578 return true;
579}
580
581/// Set the iterator data-structures to the next non-empty, non-aggregate
582/// subtype.
583static bool nextRealType(SmallVectorImpl<Type *> &SubTypes,
584 SmallVectorImpl<unsigned> &Path) {
585 do {
586 if (!advanceToNextLeafType(SubTypes, Path))
587 return false;
588
589 assert(!Path.empty() && "found a leaf but didn't set the path?");
590 } while (ExtractValueInst::getIndexedType(Agg: SubTypes.back(), Idxs: Path.back())
591 ->isAggregateType());
592
593 return true;
594}
595
596/// Resolve the DWARF version the way DwarfDebug does.
597/// FIXME: Share this resolution with DwarfDebug's, which has to match.
598static unsigned getDwarfVersion(const MachineFunction &MF) {
599 unsigned DwarfVersion = MF.getTarget().Options.MCOptions.DwarfVersion;
600 if (!DwarfVersion)
601 DwarfVersion = MF.getFunction().getParent()->getDwarfVersion();
602 if (!DwarfVersion)
603 DwarfVersion = dwarf::DWARF_VERSION;
604 return DwarfVersion;
605}
606
607bool llvm::canDescribeGlobalAddressInDebugInfo(const GlobalValue *GV,
608 const MachineFunction &MF) {
609 // Only definitions have an address a symbol reference can name.
610 if (GV->isDeclarationForLinker())
611 return false;
612 // A thread-local's address is not known until it is resolved against a
613 // thread's storage, which a plain symbol reference cannot express.
614 if (GV->isThreadLocal())
615 return false;
616 // Computing the address of a dllimport'd entity requires a load from the
617 // import address table, which a static symbol reference cannot express.
618 if (GV->hasDLLImportStorageClass())
619 return false;
620 // An ifunc resolves to whatever its resolver returns at load time, so the
621 // symbol's own address is not the value of the pointer.
622 if (isa<GlobalIFunc>(Val: GV))
623 return false;
624
625 const Module &M = *MF.getFunction().getParent();
626 const TargetMachine &TM = MF.getTarget();
627
628 // AsmPrinter may fold a GOT equivalent (an unnamed private constant
629 // holding the address of another global) into a GOT-relative
630 // relocation at its use and then never define the symbol. Whether
631 // that happens is only known once every use has been emitted, and a
632 // debug info reference does not count as a use, so it is not safe
633 // return true here.
634 if (TM.getObjFileLowering()->supportIndirectSymViaGOTPCRel())
635 if (const auto *GVar = dyn_cast<GlobalVariable>(Val: GV))
636 if (GVar->hasGlobalUnnamedAddr() && GVar->isConstant() &&
637 GVar->hasInitializer() && GVar->isDiscardableIfUnused() &&
638 isa<GlobalValue>(Val: GVar->getOperand(i_nocapture: 0)))
639 return false;
640
641 // CodeView has no way to name a symbol in a local variable's location, so
642 // choosing one here would leave the variable with no location at all.
643 if (M.getCodeViewFlag())
644 return false;
645
646 // Saying that the variable holds this address, rather than that it lives at
647 // it, needs DW_OP_stack_value, which DWARF 4 introduced. Nothing older can
648 // express the difference, so leave those versions to describe the variable by
649 // wherever the address is materialized instead. DwarfExpression refuses the
650 // same versions; deciding here only picks the better of the two fallbacks,
651 // while a materialized location is still available to fall back on.
652 if (getDwarfVersion(MF) < 4)
653 return false;
654
655 // On some targets a global does not live at its symbol's address; a base
656 // known only at run time has to be added to it. DwarfCompileUnit builds
657 // those addends for global variables, but they need a relocation, which a
658 // location list cannot carry, so a local pointing at such a global has to
659 // keep being described by whatever register holds the computed address.
660 if (M.getTargetTriple().isWasm() && TM.getRelocationModel() == Reloc::PIC_)
661 return false;
662 if (TM.getRelocationModel() == Reloc::RWPI ||
663 TM.getRelocationModel() == Reloc::ROPI_RWPI) {
664 // Only writable globals are addressed relative to the static base;
665 // read-only ones keep an absolute address. An alias may name either, so
666 // give up rather than chase it.
667 const auto *GO = dyn_cast<GlobalObject>(Val: GV);
668 if (!GO || !TM.getObjFileLowering()->getKindForGlobal(GO, TM).isReadOnly())
669 return false;
670 }
671
672 return true;
673}
674
675const GlobalValue *
676llvm::getDescribableGlobalAddress(const Constant *C, int64_t &Offset,
677 const MachineFunction &MF) {
678 Offset = 0;
679 if (!C->getType()->isPointerTy())
680 return nullptr;
681
682 // Non-inbounds offsets are stripped as well, which is the default. The
683 // inbounds flag constrains what the program may do with the pointer, not
684 // what its value is, and describing an address needs only the value.
685 int64_t GVOffset;
686 const auto *GV = dyn_cast<GlobalValue>(
687 Val: GetPointerBaseWithConstantOffset(Ptr: C, Offset&: GVOffset, DL: MF.getDataLayout()));
688 if (!GV || !canDescribeGlobalAddressInDebugInfo(GV, MF))
689 return nullptr;
690
691 Offset = GVOffset;
692 return GV;
693}
694
695bool llvm::canDescribeGlobalAddressInLocationList(const MachineFunction &MF) {
696 // A location list is emitted as plain bytes, which cannot carry the
697 // relocation a DW_OP_addr needs, so there the address has to be an index into
698 // the address pool. Before DWARF 5 that pool only exists under split DWARF.
699 return getDwarfVersion(MF) >= 5 ||
700 !MF.getTarget().Options.MCOptions.SplitDwarfFile.empty();
701}
702
703/// Test if the given instruction is in a position to be optimized
704/// with a tail-call. This roughly means that it's in a block with
705/// a return and there's nothing that needs to be scheduled
706/// between it and the return.
707///
708/// This function only tests target-independent requirements.
709bool llvm::isInTailCallPosition(const CallBase &Call, const TargetMachine &TM,
710 bool ReturnsFirstArg) {
711 const BasicBlock *ExitBB = Call.getParent();
712 const Instruction *Term = ExitBB->getTerminator();
713 const ReturnInst *Ret = dyn_cast<ReturnInst>(Val: Term);
714
715 // The block must end in a return statement or unreachable.
716 //
717 // FIXME: Decline tailcall if it's not guaranteed and if the block ends in
718 // an unreachable, for now. The way tailcall optimization is currently
719 // implemented means it will add an epilogue followed by a jump. That is
720 // not profitable. Also, if the callee is a special function (e.g.
721 // longjmp on x86), it can end up causing miscompilation that has not
722 // been fully understood.
723 if (!Ret && ((!TM.Options.GuaranteedTailCallOpt &&
724 Call.getCallingConv() != CallingConv::Tail &&
725 Call.getCallingConv() != CallingConv::SwiftTail) ||
726 !isa<UnreachableInst>(Val: Term)))
727 return false;
728
729 // If I will have a chain, make sure no other instruction that will have a
730 // chain interposes between I and the return.
731 // Check for all calls including speculatable functions.
732 for (BasicBlock::const_iterator BBI = std::prev(x: ExitBB->end(), n: 2);; --BBI) {
733 if (&*BBI == &Call)
734 break;
735 // Pseudo probe intrinsics do not block tail call optimization.
736 if (isa<PseudoProbeInst>(Val: BBI))
737 continue;
738 // A lifetime end, assume or noalias.decl intrinsic should not stop tail
739 // call optimization.
740 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val&: BBI))
741 if (II->getIntrinsicID() == Intrinsic::lifetime_end ||
742 II->getIntrinsicID() == Intrinsic::assume ||
743 II->getIntrinsicID() == Intrinsic::experimental_noalias_scope_decl ||
744 II->getIntrinsicID() == Intrinsic::fake_use)
745 continue;
746 if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() ||
747 !isSafeToSpeculativelyExecute(I: &*BBI))
748 return false;
749 }
750
751 const Function *F = ExitBB->getParent();
752 return returnTypeIsEligibleForTailCall(
753 F, I: &Call, Ret, TLI: *TM.getSubtargetImpl(*F)->getTargetLowering(),
754 ReturnsFirstArg);
755}
756
757bool llvm::attributesPermitTailCall(const Function *F, const Instruction *I,
758 const ReturnInst *Ret,
759 const TargetLoweringBase &TLI,
760 bool *AllowDifferingSizes) {
761 // ADS may be null, so don't write to it directly.
762 bool DummyADS;
763 bool &ADS = AllowDifferingSizes ? *AllowDifferingSizes : DummyADS;
764 ADS = true;
765
766 AttrBuilder CallerAttrs(F->getContext(), F->getAttributes().getRetAttrs());
767 AttrBuilder CalleeAttrs(F->getContext(),
768 cast<CallInst>(Val: I)->getAttributes().getRetAttrs());
769
770 // Following attributes are completely benign as far as calling convention
771 // goes, they shouldn't affect whether the call is a tail call.
772 for (const auto &Attr : {Attribute::Alignment, Attribute::Dereferenceable,
773 Attribute::DereferenceableOrNull, Attribute::NoAlias,
774 Attribute::NonNull, Attribute::NoUndef,
775 Attribute::Range, Attribute::NoFPClass}) {
776 CallerAttrs.removeAttribute(Val: Attr);
777 CalleeAttrs.removeAttribute(Val: Attr);
778 }
779
780 if (CallerAttrs.contains(A: Attribute::ZExt)) {
781 if (!CalleeAttrs.contains(A: Attribute::ZExt))
782 return false;
783
784 ADS = false;
785 CallerAttrs.removeAttribute(Val: Attribute::ZExt);
786 CalleeAttrs.removeAttribute(Val: Attribute::ZExt);
787 } else if (CallerAttrs.contains(A: Attribute::SExt)) {
788 if (!CalleeAttrs.contains(A: Attribute::SExt))
789 return false;
790
791 ADS = false;
792 CallerAttrs.removeAttribute(Val: Attribute::SExt);
793 CalleeAttrs.removeAttribute(Val: Attribute::SExt);
794 }
795
796 // Drop sext and zext return attributes if the result is not used.
797 // This enables tail calls for code like:
798 //
799 // define void @caller() {
800 // entry:
801 // %unused_result = tail call zeroext i1 @callee()
802 // br label %retlabel
803 // retlabel:
804 // ret void
805 // }
806 if (I->use_empty()) {
807 CalleeAttrs.removeAttribute(Val: Attribute::SExt);
808 CalleeAttrs.removeAttribute(Val: Attribute::ZExt);
809 }
810
811 // If they're still different, there's some facet we don't understand
812 // (currently only "inreg", but in future who knows). It may be OK but the
813 // only safe option is to reject the tail call.
814 return CallerAttrs == CalleeAttrs;
815}
816
817bool llvm::returnTypeIsEligibleForTailCall(const Function *F,
818 const Instruction *I,
819 const ReturnInst *Ret,
820 const TargetLoweringBase &TLI,
821 bool ReturnsFirstArg) {
822 // If the block ends with a void return or unreachable, it doesn't matter
823 // what the call's return type is.
824 if (!Ret || Ret->getNumOperands() == 0) return true;
825
826 // If the return value is undef, it doesn't matter what the call's
827 // return type is.
828 if (isa<UndefValue>(Val: Ret->getOperand(i_nocapture: 0))) return true;
829
830 // Make sure the attributes attached to each return are compatible.
831 bool AllowDifferingSizes;
832 if (!attributesPermitTailCall(F, I, Ret, TLI, AllowDifferingSizes: &AllowDifferingSizes))
833 return false;
834
835 // If the return value is the first argument of the call.
836 if (ReturnsFirstArg)
837 return true;
838
839 const Value *RetVal = Ret->getOperand(i_nocapture: 0), *CallVal = I;
840 SmallVector<unsigned, 4> RetPath, CallPath;
841 SmallVector<Type *, 4> RetSubTypes, CallSubTypes;
842
843 bool RetEmpty = !firstRealType(Next: RetVal->getType(), SubTypes&: RetSubTypes, Path&: RetPath);
844 bool CallEmpty = !firstRealType(Next: CallVal->getType(), SubTypes&: CallSubTypes, Path&: CallPath);
845
846 // Nothing's actually returned, it doesn't matter what the callee put there
847 // it's a valid tail call.
848 if (RetEmpty)
849 return true;
850
851 // Iterate pairwise through each of the value types making up the tail call
852 // and the corresponding return. For each one we want to know whether it's
853 // essentially going directly from the tail call to the ret, via operations
854 // that end up not generating any code.
855 //
856 // We allow a certain amount of covariance here. For example it's permitted
857 // for the tail call to define more bits than the ret actually cares about
858 // (e.g. via a truncate).
859 do {
860 if (CallEmpty) {
861 // We've exhausted the values produced by the tail call instruction, the
862 // rest are essentially undef. The type doesn't really matter, but we need
863 // *something*.
864 Type *SlotType =
865 ExtractValueInst::getIndexedType(Agg: RetSubTypes.back(), Idxs: RetPath.back());
866 CallVal = UndefValue::get(T: SlotType);
867 }
868
869 // The manipulations performed when we're looking through an insertvalue or
870 // an extractvalue would happen at the front of the RetPath list, so since
871 // we have to copy it anyway it's more efficient to create a reversed copy.
872 SmallVector<unsigned, 4> TmpRetPath(llvm::reverse(C&: RetPath));
873 SmallVector<unsigned, 4> TmpCallPath(llvm::reverse(C&: CallPath));
874
875 // Finally, we can check whether the value produced by the tail call at this
876 // index is compatible with the value we return.
877 if (!slotOnlyDiscardsData(RetVal, CallVal, RetIndices&: TmpRetPath, CallIndices&: TmpCallPath,
878 AllowDifferingSizes, TLI,
879 DL: F->getDataLayout()))
880 return false;
881
882 CallEmpty = !nextRealType(SubTypes&: CallSubTypes, Path&: CallPath);
883 } while(nextRealType(SubTypes&: RetSubTypes, Path&: RetPath));
884
885 return true;
886}
887
888bool llvm::funcReturnsFirstArgOfCall(const CallInst &CI) {
889 const ReturnInst *Ret = dyn_cast<ReturnInst>(Val: CI.getParent()->getTerminator());
890 Value *RetVal = Ret ? Ret->getReturnValue() : nullptr;
891 bool ReturnsFirstArg = false;
892 if (RetVal && ((RetVal == CI.getArgOperand(i: 0))))
893 ReturnsFirstArg = true;
894 return ReturnsFirstArg;
895}
896
897static void collectEHScopeMembers(
898 DenseMap<const MachineBasicBlock *, int> &EHScopeMembership, int EHScope,
899 const MachineBasicBlock *MBB) {
900 SmallVector<const MachineBasicBlock *, 16> Worklist = {MBB};
901 while (!Worklist.empty()) {
902 const MachineBasicBlock *Visiting = Worklist.pop_back_val();
903 // Don't follow blocks which start new scopes.
904 if (Visiting->isEHPad() && Visiting != MBB)
905 continue;
906
907 // Add this MBB to our scope.
908 auto P = EHScopeMembership.insert(KV: std::make_pair(x&: Visiting, y&: EHScope));
909
910 // Don't revisit blocks.
911 if (!P.second) {
912 assert(P.first->second == EHScope && "MBB is part of two scopes!");
913 continue;
914 }
915
916 // Returns are boundaries where scope transfer can occur, don't follow
917 // successors.
918 if (Visiting->isEHScopeReturnBlock())
919 continue;
920
921 append_range(C&: Worklist, R: Visiting->successors());
922 }
923}
924
925DenseMap<const MachineBasicBlock *, int>
926llvm::getEHScopeMembership(const MachineFunction &MF) {
927 DenseMap<const MachineBasicBlock *, int> EHScopeMembership;
928
929 // We don't have anything to do if there aren't any EH pads.
930 if (!MF.hasEHScopes())
931 return EHScopeMembership;
932
933 int EntryBBNumber = MF.front().getNumber();
934 bool IsSEH = isAsynchronousEHPersonality(
935 Pers: classifyEHPersonality(Pers: MF.getFunction().getPersonalityFn()));
936
937 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
938 SmallVector<const MachineBasicBlock *, 16> EHScopeBlocks;
939 SmallVector<const MachineBasicBlock *, 16> UnreachableBlocks;
940 SmallVector<const MachineBasicBlock *, 16> SEHCatchPads;
941 SmallVector<std::pair<const MachineBasicBlock *, int>, 16> CatchRetSuccessors;
942 for (const MachineBasicBlock &MBB : MF) {
943 if (MBB.isEHScopeEntry()) {
944 EHScopeBlocks.push_back(Elt: &MBB);
945 } else if (IsSEH && MBB.isEHPad()) {
946 SEHCatchPads.push_back(Elt: &MBB);
947 } else if (MBB.pred_empty()) {
948 UnreachableBlocks.push_back(Elt: &MBB);
949 }
950
951 MachineBasicBlock::const_iterator MBBI = MBB.getFirstTerminator();
952
953 // CatchPads are not scopes for SEH so do not consider CatchRet to
954 // transfer control to another scope.
955 if (MBBI == MBB.end() || MBBI->getOpcode() != TII->getCatchReturnOpcode())
956 continue;
957
958 // FIXME: SEH CatchPads are not necessarily in the parent function:
959 // they could be inside a finally block.
960 const MachineBasicBlock *Successor = MBBI->getOperand(i: 0).getMBB();
961 const MachineBasicBlock *SuccessorColor = MBBI->getOperand(i: 1).getMBB();
962 CatchRetSuccessors.push_back(
963 Elt: {Successor, IsSEH ? EntryBBNumber : SuccessorColor->getNumber()});
964 }
965
966 // We don't have anything to do if there aren't any EH pads.
967 if (EHScopeBlocks.empty())
968 return EHScopeMembership;
969
970 // Identify all the basic blocks reachable from the function entry.
971 collectEHScopeMembers(EHScopeMembership, EHScope: EntryBBNumber, MBB: &MF.front());
972 // All blocks not part of a scope are in the parent function.
973 for (const MachineBasicBlock *MBB : UnreachableBlocks)
974 collectEHScopeMembers(EHScopeMembership, EHScope: EntryBBNumber, MBB);
975 // Next, identify all the blocks inside the scopes.
976 for (const MachineBasicBlock *MBB : EHScopeBlocks)
977 collectEHScopeMembers(EHScopeMembership, EHScope: MBB->getNumber(), MBB);
978 // SEH CatchPads aren't really scopes, handle them separately.
979 for (const MachineBasicBlock *MBB : SEHCatchPads)
980 collectEHScopeMembers(EHScopeMembership, EHScope: EntryBBNumber, MBB);
981 // Finally, identify all the targets of a catchret.
982 for (std::pair<const MachineBasicBlock *, int> CatchRetPair :
983 CatchRetSuccessors)
984 collectEHScopeMembers(EHScopeMembership, EHScope: CatchRetPair.second,
985 MBB: CatchRetPair.first);
986
987 // Add any remaining blocks in the function to the unreachable set, which
988 // might not otherwise have been identified as unreachable (such as infinite
989 // loops).
990 for (const MachineBasicBlock &MBB : MF)
991 if (!EHScopeMembership.count(Val: &MBB))
992 collectEHScopeMembers(EHScopeMembership, EHScope: EntryBBNumber, MBB: &MBB);
993
994 return EHScopeMembership;
995}
996