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
292static bool isNoopBitcast(Type *T1, Type *T2,
293 const TargetLoweringBase& TLI) {
294 return T1 == T2 || (T1->isPointerTy() && T2->isPointerTy()) ||
295 (isa<VectorType>(Val: T1) && isa<VectorType>(Val: T2) &&
296 TLI.isTypeLegal(VT: EVT::getEVT(Ty: T1)) && TLI.isTypeLegal(VT: EVT::getEVT(Ty: T2)));
297}
298
299/// Look through operations that will be free to find the earliest source of
300/// this value.
301///
302/// @param ValLoc If V has aggregate type, we will be interested in a particular
303/// scalar component. This records its address; the reverse of this list gives a
304/// sequence of indices appropriate for an extractvalue to locate the important
305/// value. This value is updated during the function and on exit will indicate
306/// similar information for the Value returned.
307///
308/// @param DataBits If this function looks through truncate instructions, this
309/// will record the smallest size attained.
310static const Value *getNoopInput(const Value *V,
311 SmallVectorImpl<unsigned> &ValLoc,
312 unsigned &DataBits,
313 const TargetLoweringBase &TLI,
314 const DataLayout &DL) {
315 while (true) {
316 // Try to look through V1; if V1 is not an instruction, it can't be looked
317 // through.
318 const Instruction *I = dyn_cast<Instruction>(Val: V);
319 if (!I || I->getNumOperands() == 0) return V;
320 const Value *NoopInput = nullptr;
321
322 Value *Op = I->getOperand(i: 0);
323 if (isa<BitCastInst>(Val: I)) {
324 // Look through truly no-op bitcasts.
325 if (isNoopBitcast(T1: Op->getType(), T2: I->getType(), TLI))
326 NoopInput = Op;
327 } else if (isa<GetElementPtrInst>(Val: I)) {
328 // Look through getelementptr
329 if (cast<GetElementPtrInst>(Val: I)->hasAllZeroIndices())
330 NoopInput = Op;
331 } else if (isa<IntToPtrInst>(Val: I)) {
332 // Look through inttoptr.
333 // Make sure this isn't a truncating or extending cast. We could
334 // support this eventually, but don't bother for now.
335 if (!isa<VectorType>(Val: I->getType()) &&
336 DL.getPointerSizeInBits() ==
337 cast<IntegerType>(Val: Op->getType())->getBitWidth())
338 NoopInput = Op;
339 } else if (isa<PtrToIntInst>(Val: I)) {
340 // Look through ptrtoint.
341 // Make sure this isn't a truncating or extending cast. We could
342 // support this eventually, but don't bother for now.
343 if (!isa<VectorType>(Val: I->getType()) &&
344 DL.getPointerSizeInBits() ==
345 cast<IntegerType>(Val: I->getType())->getBitWidth())
346 NoopInput = Op;
347 } else if (isa<TruncInst>(Val: I) &&
348 TLI.allowTruncateForTailCall(FromTy: Op->getType(), ToTy: I->getType())) {
349 DataBits =
350 std::min(a: (uint64_t)DataBits,
351 b: I->getType()->getPrimitiveSizeInBits().getFixedValue());
352 NoopInput = Op;
353 } else if (auto *CB = dyn_cast<CallBase>(Val: I)) {
354 const Value *ReturnedOp = CB->getReturnedArgOperand();
355 if (ReturnedOp && isNoopBitcast(T1: ReturnedOp->getType(), T2: I->getType(), TLI))
356 NoopInput = ReturnedOp;
357 } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Val: V)) {
358 // Value may come from either the aggregate or the scalar
359 ArrayRef<unsigned> InsertLoc = IVI->getIndices();
360 if (ValLoc.size() >= InsertLoc.size() &&
361 std::equal(first1: InsertLoc.begin(), last1: InsertLoc.end(), first2: ValLoc.rbegin())) {
362 // The type being inserted is a nested sub-type of the aggregate; we
363 // have to remove those initial indices to get the location we're
364 // interested in for the operand.
365 ValLoc.resize(N: ValLoc.size() - InsertLoc.size());
366 NoopInput = IVI->getInsertedValueOperand();
367 } else {
368 // The struct we're inserting into has the value we're interested in, no
369 // change of address.
370 NoopInput = Op;
371 }
372 } else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Val: V)) {
373 // The part we're interested in will inevitably be some sub-section of the
374 // previous aggregate. Combine the two paths to obtain the true address of
375 // our element.
376 ArrayRef<unsigned> ExtractLoc = EVI->getIndices();
377 ValLoc.append(in_start: ExtractLoc.rbegin(), in_end: ExtractLoc.rend());
378 NoopInput = Op;
379 }
380 // Terminate if we couldn't find anything to look through.
381 if (!NoopInput)
382 return V;
383
384 V = NoopInput;
385 }
386}
387
388/// Return true if this scalar return value only has bits discarded on its path
389/// from the "tail call" to the "ret". This includes the obvious noop
390/// instructions handled by getNoopInput above as well as free truncations (or
391/// extensions prior to the call).
392static bool slotOnlyDiscardsData(const Value *RetVal, const Value *CallVal,
393 SmallVectorImpl<unsigned> &RetIndices,
394 SmallVectorImpl<unsigned> &CallIndices,
395 bool AllowDifferingSizes,
396 const TargetLoweringBase &TLI,
397 const DataLayout &DL) {
398
399 // Trace the sub-value needed by the return value as far back up the graph as
400 // possible, in the hope that it will intersect with the value produced by the
401 // call. In the simple case with no "returned" attribute, the hope is actually
402 // that we end up back at the tail call instruction itself.
403 unsigned BitsRequired = UINT_MAX;
404 RetVal = getNoopInput(V: RetVal, ValLoc&: RetIndices, DataBits&: BitsRequired, TLI, DL);
405
406 // If this slot in the value returned is undef, it doesn't matter what the
407 // call puts there, it'll be fine.
408 if (isa<UndefValue>(Val: RetVal))
409 return true;
410
411 // Now do a similar search up through the graph to find where the value
412 // actually returned by the "tail call" comes from. In the simple case without
413 // a "returned" attribute, the search will be blocked immediately and the loop
414 // a Noop.
415 unsigned BitsProvided = UINT_MAX;
416 CallVal = getNoopInput(V: CallVal, ValLoc&: CallIndices, DataBits&: BitsProvided, TLI, DL);
417
418 // There's no hope if we can't actually trace them to (the same part of!) the
419 // same value.
420 if (CallVal != RetVal || CallIndices != RetIndices)
421 return false;
422
423 // However, intervening truncates may have made the call non-tail. Make sure
424 // all the bits that are needed by the "ret" have been provided by the "tail
425 // call". FIXME: with sufficiently cunning bit-tracking, we could look through
426 // extensions too.
427 if (BitsProvided < BitsRequired ||
428 (!AllowDifferingSizes && BitsProvided != BitsRequired))
429 return false;
430
431 return true;
432}
433
434/// For an aggregate type, determine whether a given index is within bounds or
435/// not.
436static bool indexReallyValid(Type *T, unsigned Idx) {
437 if (ArrayType *AT = dyn_cast<ArrayType>(Val: T))
438 return Idx < AT->getNumElements();
439
440 return Idx < cast<StructType>(Val: T)->getNumElements();
441}
442
443/// Move the given iterators to the next leaf type in depth first traversal.
444///
445/// Performs a depth-first traversal of the type as specified by its arguments,
446/// stopping at the next leaf node (which may be a legitimate scalar type or an
447/// empty struct or array).
448///
449/// @param SubTypes List of the partial components making up the type from
450/// outermost to innermost non-empty aggregate. The element currently
451/// represented is SubTypes.back()->getTypeAtIndex(Path.back() - 1).
452///
453/// @param Path Set of extractvalue indices leading from the outermost type
454/// (SubTypes[0]) to the leaf node currently represented.
455///
456/// @returns true if a new type was found, false otherwise. Calling this
457/// function again on a finished iterator will repeatedly return
458/// false. SubTypes.back()->getTypeAtIndex(Path.back()) is either an empty
459/// aggregate or a non-aggregate
460static bool advanceToNextLeafType(SmallVectorImpl<Type *> &SubTypes,
461 SmallVectorImpl<unsigned> &Path) {
462 // First march back up the tree until we can successfully increment one of the
463 // coordinates in Path.
464 while (!Path.empty() && !indexReallyValid(T: SubTypes.back(), Idx: Path.back() + 1)) {
465 Path.pop_back();
466 SubTypes.pop_back();
467 }
468
469 // If we reached the top, then the iterator is done.
470 if (Path.empty())
471 return false;
472
473 // We know there's *some* valid leaf now, so march back down the tree picking
474 // out the left-most element at each node.
475 ++Path.back();
476 Type *DeeperType =
477 ExtractValueInst::getIndexedType(Agg: SubTypes.back(), Idxs: Path.back());
478 while (DeeperType->isAggregateType()) {
479 if (!indexReallyValid(T: DeeperType, Idx: 0))
480 return true;
481
482 SubTypes.push_back(Elt: DeeperType);
483 Path.push_back(Elt: 0);
484
485 DeeperType = ExtractValueInst::getIndexedType(Agg: DeeperType, Idxs: 0);
486 }
487
488 return true;
489}
490
491/// Find the first non-empty, scalar-like type in Next and setup the iterator
492/// components.
493///
494/// Assuming Next is an aggregate of some kind, this function will traverse the
495/// tree from left to right (i.e. depth-first) looking for the first
496/// non-aggregate type which will play a role in function return.
497///
498/// For example, if Next was {[0 x i64], {{}, i32, {}}, i32} then we would setup
499/// Path as [1, 1] and SubTypes as [Next, {{}, i32, {}}] to represent the first
500/// i32 in that type.
501static bool firstRealType(Type *Next, SmallVectorImpl<Type *> &SubTypes,
502 SmallVectorImpl<unsigned> &Path) {
503 // First initialise the iterator components to the first "leaf" node
504 // (i.e. node with no valid sub-type at any index, so {} does count as a leaf
505 // despite nominally being an aggregate).
506 while (Type *FirstInner = ExtractValueInst::getIndexedType(Agg: Next, Idxs: 0)) {
507 SubTypes.push_back(Elt: Next);
508 Path.push_back(Elt: 0);
509 Next = FirstInner;
510 }
511
512 // If there's no Path now, Next was originally scalar already (or empty
513 // leaf). We're done.
514 if (Path.empty())
515 return true;
516
517 // Otherwise, use normal iteration to keep looking through the tree until we
518 // find a non-aggregate type.
519 while (ExtractValueInst::getIndexedType(Agg: SubTypes.back(), Idxs: Path.back())
520 ->isAggregateType()) {
521 if (!advanceToNextLeafType(SubTypes, Path))
522 return false;
523 }
524
525 return true;
526}
527
528/// Set the iterator data-structures to the next non-empty, non-aggregate
529/// subtype.
530static bool nextRealType(SmallVectorImpl<Type *> &SubTypes,
531 SmallVectorImpl<unsigned> &Path) {
532 do {
533 if (!advanceToNextLeafType(SubTypes, Path))
534 return false;
535
536 assert(!Path.empty() && "found a leaf but didn't set the path?");
537 } while (ExtractValueInst::getIndexedType(Agg: SubTypes.back(), Idxs: Path.back())
538 ->isAggregateType());
539
540 return true;
541}
542
543/// Resolve the DWARF version the way DwarfDebug does.
544/// FIXME: Share this resolution with DwarfDebug's, which has to match.
545static unsigned getDwarfVersion(const MachineFunction &MF) {
546 unsigned DwarfVersion = MF.getTarget().Options.MCOptions.DwarfVersion;
547 if (!DwarfVersion)
548 DwarfVersion = MF.getFunction().getParent()->getDwarfVersion();
549 if (!DwarfVersion)
550 DwarfVersion = dwarf::DWARF_VERSION;
551 return DwarfVersion;
552}
553
554bool llvm::canDescribeGlobalAddressInDebugInfo(const GlobalValue *GV,
555 const MachineFunction &MF) {
556 // Only definitions have an address a symbol reference can name.
557 if (GV->isDeclarationForLinker())
558 return false;
559 // A thread-local's address is not known until it is resolved against a
560 // thread's storage, which a plain symbol reference cannot express.
561 if (GV->isThreadLocal())
562 return false;
563 // Computing the address of a dllimport'd entity requires a load from the
564 // import address table, which a static symbol reference cannot express.
565 if (GV->hasDLLImportStorageClass())
566 return false;
567 // An ifunc resolves to whatever its resolver returns at load time, so the
568 // symbol's own address is not the value of the pointer.
569 if (isa<GlobalIFunc>(Val: GV))
570 return false;
571
572 const Module &M = *MF.getFunction().getParent();
573 const TargetMachine &TM = MF.getTarget();
574
575 // AsmPrinter may fold a GOT equivalent (an unnamed private constant
576 // holding the address of another global) into a GOT-relative
577 // relocation at its use and then never define the symbol. Whether
578 // that happens is only known once every use has been emitted, and a
579 // debug info reference does not count as a use, so it is not safe
580 // return true here.
581 if (TM.getObjFileLowering()->supportIndirectSymViaGOTPCRel())
582 if (const auto *GVar = dyn_cast<GlobalVariable>(Val: GV))
583 if (GVar->hasGlobalUnnamedAddr() && GVar->isConstant() &&
584 GVar->hasInitializer() && GVar->isDiscardableIfUnused() &&
585 isa<GlobalValue>(Val: GVar->getOperand(i_nocapture: 0)))
586 return false;
587
588 // CodeView has no way to name a symbol in a local variable's location, so
589 // choosing one here would leave the variable with no location at all.
590 if (M.getCodeViewFlag())
591 return false;
592
593 // Saying that the variable holds this address, rather than that it lives at
594 // it, needs DW_OP_stack_value, which DWARF 4 introduced. Nothing older can
595 // express the difference, so leave those versions to describe the variable by
596 // wherever the address is materialized instead. DwarfExpression refuses the
597 // same versions; deciding here only picks the better of the two fallbacks,
598 // while a materialized location is still available to fall back on.
599 if (getDwarfVersion(MF) < 4)
600 return false;
601
602 // On some targets a global does not live at its symbol's address; a base
603 // known only at run time has to be added to it. DwarfCompileUnit builds
604 // those addends for global variables, but they need a relocation, which a
605 // location list cannot carry, so a local pointing at such a global has to
606 // keep being described by whatever register holds the computed address.
607 if (M.getTargetTriple().isWasm() && TM.getRelocationModel() == Reloc::PIC_)
608 return false;
609 if (TM.getRelocationModel() == Reloc::RWPI ||
610 TM.getRelocationModel() == Reloc::ROPI_RWPI) {
611 // Only writable globals are addressed relative to the static base;
612 // read-only ones keep an absolute address. An alias may name either, so
613 // give up rather than chase it.
614 const auto *GO = dyn_cast<GlobalObject>(Val: GV);
615 if (!GO || !TM.getObjFileLowering()->getKindForGlobal(GO, TM).isReadOnly())
616 return false;
617 }
618
619 return true;
620}
621
622const GlobalValue *
623llvm::getDescribableGlobalAddress(const Constant *C, int64_t &Offset,
624 const MachineFunction &MF) {
625 Offset = 0;
626 if (!C->getType()->isPointerTy())
627 return nullptr;
628
629 // Non-inbounds offsets are stripped as well, which is the default. The
630 // inbounds flag constrains what the program may do with the pointer, not
631 // what its value is, and describing an address needs only the value.
632 int64_t GVOffset;
633 const auto *GV = dyn_cast<GlobalValue>(
634 Val: GetPointerBaseWithConstantOffset(Ptr: C, Offset&: GVOffset, DL: MF.getDataLayout()));
635 if (!GV || !canDescribeGlobalAddressInDebugInfo(GV, MF))
636 return nullptr;
637
638 Offset = GVOffset;
639 return GV;
640}
641
642bool llvm::canDescribeGlobalAddressInLocationList(const MachineFunction &MF) {
643 // A location list is emitted as plain bytes, which cannot carry the
644 // relocation a DW_OP_addr needs, so there the address has to be an index into
645 // the address pool. Before DWARF 5 that pool only exists under split DWARF.
646 return getDwarfVersion(MF) >= 5 ||
647 !MF.getTarget().Options.MCOptions.SplitDwarfFile.empty();
648}
649
650/// Test if the given instruction is in a position to be optimized
651/// with a tail-call. This roughly means that it's in a block with
652/// a return and there's nothing that needs to be scheduled
653/// between it and the return.
654///
655/// This function only tests target-independent requirements.
656bool llvm::isInTailCallPosition(const CallBase &Call, const TargetMachine &TM,
657 bool ReturnsFirstArg) {
658 const BasicBlock *ExitBB = Call.getParent();
659 const Instruction *Term = ExitBB->getTerminator();
660 const ReturnInst *Ret = dyn_cast<ReturnInst>(Val: Term);
661
662 // The block must end in a return statement or unreachable.
663 //
664 // FIXME: Decline tailcall if it's not guaranteed and if the block ends in
665 // an unreachable, for now. The way tailcall optimization is currently
666 // implemented means it will add an epilogue followed by a jump. That is
667 // not profitable. Also, if the callee is a special function (e.g.
668 // longjmp on x86), it can end up causing miscompilation that has not
669 // been fully understood.
670 if (!Ret && ((!TM.Options.GuaranteedTailCallOpt &&
671 Call.getCallingConv() != CallingConv::Tail &&
672 Call.getCallingConv() != CallingConv::SwiftTail) ||
673 !isa<UnreachableInst>(Val: Term)))
674 return false;
675
676 // If I will have a chain, make sure no other instruction that will have a
677 // chain interposes between I and the return.
678 // Check for all calls including speculatable functions.
679 for (BasicBlock::const_iterator BBI = std::prev(x: ExitBB->end(), n: 2);; --BBI) {
680 if (&*BBI == &Call)
681 break;
682 // Debug info intrinsics do not get in the way of tail call optimization.
683 // Pseudo probe intrinsics do not block tail call optimization either.
684 if (BBI->isDebugOrPseudoInst())
685 continue;
686 // A lifetime end, assume or noalias.decl intrinsic should not stop tail
687 // call optimization.
688 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val&: BBI))
689 if (II->getIntrinsicID() == Intrinsic::lifetime_end ||
690 II->getIntrinsicID() == Intrinsic::assume ||
691 II->getIntrinsicID() == Intrinsic::experimental_noalias_scope_decl ||
692 II->getIntrinsicID() == Intrinsic::fake_use)
693 continue;
694 if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() ||
695 !isSafeToSpeculativelyExecute(I: &*BBI))
696 return false;
697 }
698
699 const Function *F = ExitBB->getParent();
700 return returnTypeIsEligibleForTailCall(
701 F, I: &Call, Ret, TLI: *TM.getSubtargetImpl(*F)->getTargetLowering(),
702 ReturnsFirstArg);
703}
704
705bool llvm::attributesPermitTailCall(const Function *F, const Instruction *I,
706 const ReturnInst *Ret,
707 const TargetLoweringBase &TLI,
708 bool *AllowDifferingSizes) {
709 // ADS may be null, so don't write to it directly.
710 bool DummyADS;
711 bool &ADS = AllowDifferingSizes ? *AllowDifferingSizes : DummyADS;
712 ADS = true;
713
714 AttrBuilder CallerAttrs(F->getContext(), F->getAttributes().getRetAttrs());
715 AttrBuilder CalleeAttrs(F->getContext(),
716 cast<CallInst>(Val: I)->getAttributes().getRetAttrs());
717
718 // Following attributes are completely benign as far as calling convention
719 // goes, they shouldn't affect whether the call is a tail call.
720 for (const auto &Attr : {Attribute::Alignment, Attribute::Dereferenceable,
721 Attribute::DereferenceableOrNull, Attribute::NoAlias,
722 Attribute::NonNull, Attribute::NoUndef,
723 Attribute::Range, Attribute::NoFPClass}) {
724 CallerAttrs.removeAttribute(Val: Attr);
725 CalleeAttrs.removeAttribute(Val: Attr);
726 }
727
728 if (CallerAttrs.contains(A: Attribute::ZExt)) {
729 if (!CalleeAttrs.contains(A: Attribute::ZExt))
730 return false;
731
732 ADS = false;
733 CallerAttrs.removeAttribute(Val: Attribute::ZExt);
734 CalleeAttrs.removeAttribute(Val: Attribute::ZExt);
735 } else if (CallerAttrs.contains(A: Attribute::SExt)) {
736 if (!CalleeAttrs.contains(A: Attribute::SExt))
737 return false;
738
739 ADS = false;
740 CallerAttrs.removeAttribute(Val: Attribute::SExt);
741 CalleeAttrs.removeAttribute(Val: Attribute::SExt);
742 }
743
744 // Drop sext and zext return attributes if the result is not used.
745 // This enables tail calls for code like:
746 //
747 // define void @caller() {
748 // entry:
749 // %unused_result = tail call zeroext i1 @callee()
750 // br label %retlabel
751 // retlabel:
752 // ret void
753 // }
754 if (I->use_empty()) {
755 CalleeAttrs.removeAttribute(Val: Attribute::SExt);
756 CalleeAttrs.removeAttribute(Val: Attribute::ZExt);
757 }
758
759 // If they're still different, there's some facet we don't understand
760 // (currently only "inreg", but in future who knows). It may be OK but the
761 // only safe option is to reject the tail call.
762 return CallerAttrs == CalleeAttrs;
763}
764
765bool llvm::returnTypeIsEligibleForTailCall(const Function *F,
766 const Instruction *I,
767 const ReturnInst *Ret,
768 const TargetLoweringBase &TLI,
769 bool ReturnsFirstArg) {
770 // If the block ends with a void return or unreachable, it doesn't matter
771 // what the call's return type is.
772 if (!Ret || Ret->getNumOperands() == 0) return true;
773
774 // If the return value is undef, it doesn't matter what the call's
775 // return type is.
776 if (isa<UndefValue>(Val: Ret->getOperand(i_nocapture: 0))) return true;
777
778 // Make sure the attributes attached to each return are compatible.
779 bool AllowDifferingSizes;
780 if (!attributesPermitTailCall(F, I, Ret, TLI, AllowDifferingSizes: &AllowDifferingSizes))
781 return false;
782
783 // If the return value is the first argument of the call.
784 if (ReturnsFirstArg)
785 return true;
786
787 const Value *RetVal = Ret->getOperand(i_nocapture: 0), *CallVal = I;
788 SmallVector<unsigned, 4> RetPath, CallPath;
789 SmallVector<Type *, 4> RetSubTypes, CallSubTypes;
790
791 bool RetEmpty = !firstRealType(Next: RetVal->getType(), SubTypes&: RetSubTypes, Path&: RetPath);
792 bool CallEmpty = !firstRealType(Next: CallVal->getType(), SubTypes&: CallSubTypes, Path&: CallPath);
793
794 // Nothing's actually returned, it doesn't matter what the callee put there
795 // it's a valid tail call.
796 if (RetEmpty)
797 return true;
798
799 // Iterate pairwise through each of the value types making up the tail call
800 // and the corresponding return. For each one we want to know whether it's
801 // essentially going directly from the tail call to the ret, via operations
802 // that end up not generating any code.
803 //
804 // We allow a certain amount of covariance here. For example it's permitted
805 // for the tail call to define more bits than the ret actually cares about
806 // (e.g. via a truncate).
807 do {
808 if (CallEmpty) {
809 // We've exhausted the values produced by the tail call instruction, the
810 // rest are essentially undef. The type doesn't really matter, but we need
811 // *something*.
812 Type *SlotType =
813 ExtractValueInst::getIndexedType(Agg: RetSubTypes.back(), Idxs: RetPath.back());
814 CallVal = UndefValue::get(T: SlotType);
815 }
816
817 // The manipulations performed when we're looking through an insertvalue or
818 // an extractvalue would happen at the front of the RetPath list, so since
819 // we have to copy it anyway it's more efficient to create a reversed copy.
820 SmallVector<unsigned, 4> TmpRetPath(llvm::reverse(C&: RetPath));
821 SmallVector<unsigned, 4> TmpCallPath(llvm::reverse(C&: CallPath));
822
823 // Finally, we can check whether the value produced by the tail call at this
824 // index is compatible with the value we return.
825 if (!slotOnlyDiscardsData(RetVal, CallVal, RetIndices&: TmpRetPath, CallIndices&: TmpCallPath,
826 AllowDifferingSizes, TLI,
827 DL: F->getDataLayout()))
828 return false;
829
830 CallEmpty = !nextRealType(SubTypes&: CallSubTypes, Path&: CallPath);
831 } while(nextRealType(SubTypes&: RetSubTypes, Path&: RetPath));
832
833 return true;
834}
835
836bool llvm::funcReturnsFirstArgOfCall(const CallInst &CI) {
837 const ReturnInst *Ret = dyn_cast<ReturnInst>(Val: CI.getParent()->getTerminator());
838 Value *RetVal = Ret ? Ret->getReturnValue() : nullptr;
839 bool ReturnsFirstArg = false;
840 if (RetVal && ((RetVal == CI.getArgOperand(i: 0))))
841 ReturnsFirstArg = true;
842 return ReturnsFirstArg;
843}
844
845static void collectEHScopeMembers(
846 DenseMap<const MachineBasicBlock *, int> &EHScopeMembership, int EHScope,
847 const MachineBasicBlock *MBB) {
848 SmallVector<const MachineBasicBlock *, 16> Worklist = {MBB};
849 while (!Worklist.empty()) {
850 const MachineBasicBlock *Visiting = Worklist.pop_back_val();
851 // Don't follow blocks which start new scopes.
852 if (Visiting->isEHPad() && Visiting != MBB)
853 continue;
854
855 // Add this MBB to our scope.
856 auto P = EHScopeMembership.insert(KV: std::make_pair(x&: Visiting, y&: EHScope));
857
858 // Don't revisit blocks.
859 if (!P.second) {
860 assert(P.first->second == EHScope && "MBB is part of two scopes!");
861 continue;
862 }
863
864 // Returns are boundaries where scope transfer can occur, don't follow
865 // successors.
866 if (Visiting->isEHScopeReturnBlock())
867 continue;
868
869 append_range(C&: Worklist, R: Visiting->successors());
870 }
871}
872
873DenseMap<const MachineBasicBlock *, int>
874llvm::getEHScopeMembership(const MachineFunction &MF) {
875 DenseMap<const MachineBasicBlock *, int> EHScopeMembership;
876
877 // We don't have anything to do if there aren't any EH pads.
878 if (!MF.hasEHScopes())
879 return EHScopeMembership;
880
881 int EntryBBNumber = MF.front().getNumber();
882 bool IsSEH = isAsynchronousEHPersonality(
883 Pers: classifyEHPersonality(Pers: MF.getFunction().getPersonalityFn()));
884
885 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
886 SmallVector<const MachineBasicBlock *, 16> EHScopeBlocks;
887 SmallVector<const MachineBasicBlock *, 16> UnreachableBlocks;
888 SmallVector<const MachineBasicBlock *, 16> SEHCatchPads;
889 SmallVector<std::pair<const MachineBasicBlock *, int>, 16> CatchRetSuccessors;
890 for (const MachineBasicBlock &MBB : MF) {
891 if (MBB.isEHScopeEntry()) {
892 EHScopeBlocks.push_back(Elt: &MBB);
893 } else if (IsSEH && MBB.isEHPad()) {
894 SEHCatchPads.push_back(Elt: &MBB);
895 } else if (MBB.pred_empty()) {
896 UnreachableBlocks.push_back(Elt: &MBB);
897 }
898
899 MachineBasicBlock::const_iterator MBBI = MBB.getFirstTerminator();
900
901 // CatchPads are not scopes for SEH so do not consider CatchRet to
902 // transfer control to another scope.
903 if (MBBI == MBB.end() || MBBI->getOpcode() != TII->getCatchReturnOpcode())
904 continue;
905
906 // FIXME: SEH CatchPads are not necessarily in the parent function:
907 // they could be inside a finally block.
908 const MachineBasicBlock *Successor = MBBI->getOperand(i: 0).getMBB();
909 const MachineBasicBlock *SuccessorColor = MBBI->getOperand(i: 1).getMBB();
910 CatchRetSuccessors.push_back(
911 Elt: {Successor, IsSEH ? EntryBBNumber : SuccessorColor->getNumber()});
912 }
913
914 // We don't have anything to do if there aren't any EH pads.
915 if (EHScopeBlocks.empty())
916 return EHScopeMembership;
917
918 // Identify all the basic blocks reachable from the function entry.
919 collectEHScopeMembers(EHScopeMembership, EHScope: EntryBBNumber, MBB: &MF.front());
920 // All blocks not part of a scope are in the parent function.
921 for (const MachineBasicBlock *MBB : UnreachableBlocks)
922 collectEHScopeMembers(EHScopeMembership, EHScope: EntryBBNumber, MBB);
923 // Next, identify all the blocks inside the scopes.
924 for (const MachineBasicBlock *MBB : EHScopeBlocks)
925 collectEHScopeMembers(EHScopeMembership, EHScope: MBB->getNumber(), MBB);
926 // SEH CatchPads aren't really scopes, handle them separately.
927 for (const MachineBasicBlock *MBB : SEHCatchPads)
928 collectEHScopeMembers(EHScopeMembership, EHScope: EntryBBNumber, MBB);
929 // Finally, identify all the targets of a catchret.
930 for (std::pair<const MachineBasicBlock *, int> CatchRetPair :
931 CatchRetSuccessors)
932 collectEHScopeMembers(EHScopeMembership, EHScope: CatchRetPair.second,
933 MBB: CatchRetPair.first);
934
935 // Add any remaining blocks in the function to the unreachable set, which
936 // might not otherwise have been identified as unreachable (such as infinite
937 // loops).
938 for (const MachineBasicBlock &MBB : MF)
939 if (!EHScopeMembership.count(Val: &MBB))
940 collectEHScopeMembers(EHScopeMembership, EHScope: EntryBBNumber, MBB: &MBB);
941
942 return EHScopeMembership;
943}
944