823 lines · cpp
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-exception6//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/CodeGen/MachineFunction.h"16#include "llvm/CodeGen/TargetInstrInfo.h"17#include "llvm/CodeGen/TargetLowering.h"18#include "llvm/CodeGen/TargetSubtargetInfo.h"19#include "llvm/IR/DataLayout.h"20#include "llvm/IR/DerivedTypes.h"21#include "llvm/IR/Function.h"22#include "llvm/IR/Instructions.h"23#include "llvm/IR/IntrinsicInst.h"24#include "llvm/IR/Module.h"25#include "llvm/Support/ErrorHandling.h"26#include "llvm/Target/TargetMachine.h"27 28using namespace llvm;29 30/// Compute the linearized index of a member in a nested aggregate/struct/array31/// by recursing and accumulating CurIndex as long as there are indices in the32/// index list.33unsigned llvm::ComputeLinearIndex(Type *Ty,34 const unsigned *Indices,35 const unsigned *IndicesEnd,36 unsigned CurIndex) {37 // Base case: We're done.38 if (Indices && Indices == IndicesEnd)39 return CurIndex;40 41 // Given a struct type, recursively traverse the elements.42 if (StructType *STy = dyn_cast<StructType>(Ty)) {43 for (auto I : llvm::enumerate(STy->elements())) {44 Type *ET = I.value();45 if (Indices && *Indices == I.index())46 return ComputeLinearIndex(ET, Indices + 1, IndicesEnd, CurIndex);47 CurIndex = ComputeLinearIndex(ET, nullptr, nullptr, CurIndex);48 }49 assert(!Indices && "Unexpected out of bound");50 return CurIndex;51 }52 // Given an array type, recursively traverse the elements.53 else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {54 Type *EltTy = ATy->getElementType();55 unsigned NumElts = ATy->getNumElements();56 // Compute the Linear offset when jumping one element of the array57 unsigned EltLinearOffset = ComputeLinearIndex(EltTy, nullptr, nullptr, 0);58 if (Indices) {59 assert(*Indices < NumElts && "Unexpected out of bound");60 // If the indice is inside the array, compute the index to the requested61 // elt and recurse inside the element with the end of the indices list62 CurIndex += EltLinearOffset* *Indices;63 return ComputeLinearIndex(EltTy, Indices+1, IndicesEnd, CurIndex);64 }65 CurIndex += EltLinearOffset*NumElts;66 return CurIndex;67 }68 // We haven't found the type we're looking for, so keep searching.69 return CurIndex + 1;70}71 72void llvm::ComputeValueTypes(const DataLayout &DL, Type *Ty,73 SmallVectorImpl<Type *> &Types,74 SmallVectorImpl<TypeSize> *Offsets,75 TypeSize StartingOffset) {76 assert((Ty->isScalableTy() == StartingOffset.isScalable() ||77 StartingOffset.isZero()) &&78 "Offset/TypeSize mismatch!");79 // Given a struct type, recursively traverse the elements.80 if (StructType *STy = dyn_cast<StructType>(Ty)) {81 // If the Offsets aren't needed, don't query the struct layout. This allows82 // us to support structs with scalable vectors for operations that don't83 // need offsets.84 const StructLayout *SL = Offsets ? DL.getStructLayout(STy) : nullptr;85 for (StructType::element_iterator EB = STy->element_begin(), EI = EB,86 EE = STy->element_end();87 EI != EE; ++EI) {88 // Don't compute the element offset if we didn't get a StructLayout above.89 TypeSize EltOffset =90 SL ? SL->getElementOffset(EI - EB) : TypeSize::getZero();91 ComputeValueTypes(DL, *EI, Types, Offsets, StartingOffset + EltOffset);92 }93 return;94 }95 // Given an array type, recursively traverse the elements.96 if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {97 Type *EltTy = ATy->getElementType();98 TypeSize EltSize = DL.getTypeAllocSize(EltTy);99 for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)100 ComputeValueTypes(DL, EltTy, Types, Offsets,101 StartingOffset + i * EltSize);102 return;103 }104 // Interpret void as zero return values.105 if (Ty->isVoidTy())106 return;107 Types.push_back(Ty);108 if (Offsets)109 Offsets->push_back(StartingOffset);110}111 112/// ComputeValueVTs - Given an LLVM IR type, compute a sequence of113/// EVTs that represent all the individual underlying114/// non-aggregate types that comprise it.115///116/// If Offsets is non-null, it points to a vector to be filled in117/// with the in-memory offsets of each of the individual values.118///119void llvm::ComputeValueVTs(const TargetLowering &TLI, const DataLayout &DL,120 Type *Ty, SmallVectorImpl<EVT> &ValueVTs,121 SmallVectorImpl<EVT> *MemVTs,122 SmallVectorImpl<TypeSize> *Offsets,123 TypeSize StartingOffset) {124 SmallVector<Type *> Types;125 ComputeValueTypes(DL, Ty, Types, Offsets, StartingOffset);126 for (Type *Ty : Types) {127 ValueVTs.push_back(TLI.getValueType(DL, Ty));128 if (MemVTs)129 MemVTs->push_back(TLI.getMemValueType(DL, Ty));130 }131}132 133void llvm::ComputeValueVTs(const TargetLowering &TLI, const DataLayout &DL,134 Type *Ty, SmallVectorImpl<EVT> &ValueVTs,135 SmallVectorImpl<EVT> *MemVTs,136 SmallVectorImpl<uint64_t> *FixedOffsets,137 uint64_t StartingOffset) {138 TypeSize Offset = TypeSize::getFixed(StartingOffset);139 if (FixedOffsets) {140 SmallVector<TypeSize, 4> Offsets;141 ComputeValueVTs(TLI, DL, Ty, ValueVTs, MemVTs, &Offsets, Offset);142 for (TypeSize Offset : Offsets)143 FixedOffsets->push_back(Offset.getFixedValue());144 } else {145 ComputeValueVTs(TLI, DL, Ty, ValueVTs, MemVTs, nullptr, Offset);146 }147}148 149void llvm::computeValueLLTs(const DataLayout &DL, Type &Ty,150 SmallVectorImpl<LLT> &ValueTys,151 SmallVectorImpl<uint64_t> *Offsets,152 uint64_t StartingOffset) {153 // Given a struct type, recursively traverse the elements.154 if (StructType *STy = dyn_cast<StructType>(&Ty)) {155 // If the Offsets aren't needed, don't query the struct layout. This allows156 // us to support structs with scalable vectors for operations that don't157 // need offsets.158 const StructLayout *SL = Offsets ? DL.getStructLayout(STy) : nullptr;159 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {160 uint64_t EltOffset = SL ? SL->getElementOffset(I) : 0;161 computeValueLLTs(DL, *STy->getElementType(I), ValueTys, Offsets,162 StartingOffset + EltOffset);163 }164 return;165 }166 // Given an array type, recursively traverse the elements.167 if (ArrayType *ATy = dyn_cast<ArrayType>(&Ty)) {168 Type *EltTy = ATy->getElementType();169 uint64_t EltSize = DL.getTypeAllocSize(EltTy).getFixedValue();170 for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)171 computeValueLLTs(DL, *EltTy, ValueTys, Offsets,172 StartingOffset + i * EltSize);173 return;174 }175 // Interpret void as zero return values.176 if (Ty.isVoidTy())177 return;178 // Base case: we can get an LLT for this LLVM IR type.179 ValueTys.push_back(getLLTForType(Ty, DL));180 if (Offsets)181 Offsets->push_back(StartingOffset);182}183 184/// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V.185GlobalValue *llvm::ExtractTypeInfo(Value *V) {186 V = V->stripPointerCasts();187 GlobalValue *GV = dyn_cast<GlobalValue>(V);188 GlobalVariable *Var = dyn_cast<GlobalVariable>(V);189 190 if (Var && Var->getName() == "llvm.eh.catch.all.value") {191 assert(Var->hasInitializer() &&192 "The EH catch-all value must have an initializer");193 Value *Init = Var->getInitializer();194 GV = dyn_cast<GlobalValue>(Init);195 if (!GV) V = cast<ConstantPointerNull>(Init);196 }197 198 assert((GV || isa<ConstantPointerNull>(V)) &&199 "TypeInfo must be a global variable or NULL");200 return GV;201}202 203/// getFCmpCondCode - Return the ISD condition code corresponding to204/// the given LLVM IR floating-point condition code. This includes205/// consideration of global floating-point math flags.206///207ISD::CondCode llvm::getFCmpCondCode(FCmpInst::Predicate Pred) {208 switch (Pred) {209 case FCmpInst::FCMP_FALSE: return ISD::SETFALSE;210 case FCmpInst::FCMP_OEQ: return ISD::SETOEQ;211 case FCmpInst::FCMP_OGT: return ISD::SETOGT;212 case FCmpInst::FCMP_OGE: return ISD::SETOGE;213 case FCmpInst::FCMP_OLT: return ISD::SETOLT;214 case FCmpInst::FCMP_OLE: return ISD::SETOLE;215 case FCmpInst::FCMP_ONE: return ISD::SETONE;216 case FCmpInst::FCMP_ORD: return ISD::SETO;217 case FCmpInst::FCMP_UNO: return ISD::SETUO;218 case FCmpInst::FCMP_UEQ: return ISD::SETUEQ;219 case FCmpInst::FCMP_UGT: return ISD::SETUGT;220 case FCmpInst::FCMP_UGE: return ISD::SETUGE;221 case FCmpInst::FCMP_ULT: return ISD::SETULT;222 case FCmpInst::FCMP_ULE: return ISD::SETULE;223 case FCmpInst::FCMP_UNE: return ISD::SETUNE;224 case FCmpInst::FCMP_TRUE: return ISD::SETTRUE;225 default: llvm_unreachable("Invalid FCmp predicate opcode!");226 }227}228 229ISD::CondCode llvm::getFCmpCodeWithoutNaN(ISD::CondCode CC) {230 switch (CC) {231 case ISD::SETOEQ: case ISD::SETUEQ: return ISD::SETEQ;232 case ISD::SETONE: case ISD::SETUNE: return ISD::SETNE;233 case ISD::SETOLT: case ISD::SETULT: return ISD::SETLT;234 case ISD::SETOLE: case ISD::SETULE: return ISD::SETLE;235 case ISD::SETOGT: case ISD::SETUGT: return ISD::SETGT;236 case ISD::SETOGE: case ISD::SETUGE: return ISD::SETGE;237 default: return CC;238 }239}240 241ISD::CondCode llvm::getICmpCondCode(ICmpInst::Predicate Pred) {242 switch (Pred) {243 case ICmpInst::ICMP_EQ: return ISD::SETEQ;244 case ICmpInst::ICMP_NE: return ISD::SETNE;245 case ICmpInst::ICMP_SLE: return ISD::SETLE;246 case ICmpInst::ICMP_ULE: return ISD::SETULE;247 case ICmpInst::ICMP_SGE: return ISD::SETGE;248 case ICmpInst::ICMP_UGE: return ISD::SETUGE;249 case ICmpInst::ICMP_SLT: return ISD::SETLT;250 case ICmpInst::ICMP_ULT: return ISD::SETULT;251 case ICmpInst::ICMP_SGT: return ISD::SETGT;252 case ICmpInst::ICMP_UGT: return ISD::SETUGT;253 default:254 llvm_unreachable("Invalid ICmp predicate opcode!");255 }256}257 258ICmpInst::Predicate llvm::getICmpCondCode(ISD::CondCode Pred) {259 switch (Pred) {260 case ISD::SETEQ:261 return ICmpInst::ICMP_EQ;262 case ISD::SETNE:263 return ICmpInst::ICMP_NE;264 case ISD::SETLE:265 return ICmpInst::ICMP_SLE;266 case ISD::SETULE:267 return ICmpInst::ICMP_ULE;268 case ISD::SETGE:269 return ICmpInst::ICMP_SGE;270 case ISD::SETUGE:271 return ICmpInst::ICMP_UGE;272 case ISD::SETLT:273 return ICmpInst::ICMP_SLT;274 case ISD::SETULT:275 return ICmpInst::ICMP_ULT;276 case ISD::SETGT:277 return ICmpInst::ICMP_SGT;278 case ISD::SETUGT:279 return ICmpInst::ICMP_UGT;280 default:281 llvm_unreachable("Invalid ISD integer condition code!");282 }283}284 285static bool isNoopBitcast(Type *T1, Type *T2,286 const TargetLoweringBase& TLI) {287 return T1 == T2 || (T1->isPointerTy() && T2->isPointerTy()) ||288 (isa<VectorType>(T1) && isa<VectorType>(T2) &&289 TLI.isTypeLegal(EVT::getEVT(T1)) && TLI.isTypeLegal(EVT::getEVT(T2)));290}291 292/// Look through operations that will be free to find the earliest source of293/// this value.294///295/// @param ValLoc If V has aggregate type, we will be interested in a particular296/// scalar component. This records its address; the reverse of this list gives a297/// sequence of indices appropriate for an extractvalue to locate the important298/// value. This value is updated during the function and on exit will indicate299/// similar information for the Value returned.300///301/// @param DataBits If this function looks through truncate instructions, this302/// will record the smallest size attained.303static const Value *getNoopInput(const Value *V,304 SmallVectorImpl<unsigned> &ValLoc,305 unsigned &DataBits,306 const TargetLoweringBase &TLI,307 const DataLayout &DL) {308 while (true) {309 // Try to look through V1; if V1 is not an instruction, it can't be looked310 // through.311 const Instruction *I = dyn_cast<Instruction>(V);312 if (!I || I->getNumOperands() == 0) return V;313 const Value *NoopInput = nullptr;314 315 Value *Op = I->getOperand(0);316 if (isa<BitCastInst>(I)) {317 // Look through truly no-op bitcasts.318 if (isNoopBitcast(Op->getType(), I->getType(), TLI))319 NoopInput = Op;320 } else if (isa<GetElementPtrInst>(I)) {321 // Look through getelementptr322 if (cast<GetElementPtrInst>(I)->hasAllZeroIndices())323 NoopInput = Op;324 } else if (isa<IntToPtrInst>(I)) {325 // Look through inttoptr.326 // Make sure this isn't a truncating or extending cast. We could327 // support this eventually, but don't bother for now.328 if (!isa<VectorType>(I->getType()) &&329 DL.getPointerSizeInBits() ==330 cast<IntegerType>(Op->getType())->getBitWidth())331 NoopInput = Op;332 } else if (isa<PtrToIntInst>(I)) {333 // Look through ptrtoint.334 // Make sure this isn't a truncating or extending cast. We could335 // support this eventually, but don't bother for now.336 if (!isa<VectorType>(I->getType()) &&337 DL.getPointerSizeInBits() ==338 cast<IntegerType>(I->getType())->getBitWidth())339 NoopInput = Op;340 } else if (isa<TruncInst>(I) &&341 TLI.allowTruncateForTailCall(Op->getType(), I->getType())) {342 DataBits =343 std::min((uint64_t)DataBits,344 I->getType()->getPrimitiveSizeInBits().getFixedValue());345 NoopInput = Op;346 } else if (auto *CB = dyn_cast<CallBase>(I)) {347 const Value *ReturnedOp = CB->getReturnedArgOperand();348 if (ReturnedOp && isNoopBitcast(ReturnedOp->getType(), I->getType(), TLI))349 NoopInput = ReturnedOp;350 } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(V)) {351 // Value may come from either the aggregate or the scalar352 ArrayRef<unsigned> InsertLoc = IVI->getIndices();353 if (ValLoc.size() >= InsertLoc.size() &&354 std::equal(InsertLoc.begin(), InsertLoc.end(), ValLoc.rbegin())) {355 // The type being inserted is a nested sub-type of the aggregate; we356 // have to remove those initial indices to get the location we're357 // interested in for the operand.358 ValLoc.resize(ValLoc.size() - InsertLoc.size());359 NoopInput = IVI->getInsertedValueOperand();360 } else {361 // The struct we're inserting into has the value we're interested in, no362 // change of address.363 NoopInput = Op;364 }365 } else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) {366 // The part we're interested in will inevitably be some sub-section of the367 // previous aggregate. Combine the two paths to obtain the true address of368 // our element.369 ArrayRef<unsigned> ExtractLoc = EVI->getIndices();370 ValLoc.append(ExtractLoc.rbegin(), ExtractLoc.rend());371 NoopInput = Op;372 }373 // Terminate if we couldn't find anything to look through.374 if (!NoopInput)375 return V;376 377 V = NoopInput;378 }379}380 381/// Return true if this scalar return value only has bits discarded on its path382/// from the "tail call" to the "ret". This includes the obvious noop383/// instructions handled by getNoopInput above as well as free truncations (or384/// extensions prior to the call).385static bool slotOnlyDiscardsData(const Value *RetVal, const Value *CallVal,386 SmallVectorImpl<unsigned> &RetIndices,387 SmallVectorImpl<unsigned> &CallIndices,388 bool AllowDifferingSizes,389 const TargetLoweringBase &TLI,390 const DataLayout &DL) {391 392 // Trace the sub-value needed by the return value as far back up the graph as393 // possible, in the hope that it will intersect with the value produced by the394 // call. In the simple case with no "returned" attribute, the hope is actually395 // that we end up back at the tail call instruction itself.396 unsigned BitsRequired = UINT_MAX;397 RetVal = getNoopInput(RetVal, RetIndices, BitsRequired, TLI, DL);398 399 // If this slot in the value returned is undef, it doesn't matter what the400 // call puts there, it'll be fine.401 if (isa<UndefValue>(RetVal))402 return true;403 404 // Now do a similar search up through the graph to find where the value405 // actually returned by the "tail call" comes from. In the simple case without406 // a "returned" attribute, the search will be blocked immediately and the loop407 // a Noop.408 unsigned BitsProvided = UINT_MAX;409 CallVal = getNoopInput(CallVal, CallIndices, BitsProvided, TLI, DL);410 411 // There's no hope if we can't actually trace them to (the same part of!) the412 // same value.413 if (CallVal != RetVal || CallIndices != RetIndices)414 return false;415 416 // However, intervening truncates may have made the call non-tail. Make sure417 // all the bits that are needed by the "ret" have been provided by the "tail418 // call". FIXME: with sufficiently cunning bit-tracking, we could look through419 // extensions too.420 if (BitsProvided < BitsRequired ||421 (!AllowDifferingSizes && BitsProvided != BitsRequired))422 return false;423 424 return true;425}426 427/// For an aggregate type, determine whether a given index is within bounds or428/// not.429static bool indexReallyValid(Type *T, unsigned Idx) {430 if (ArrayType *AT = dyn_cast<ArrayType>(T))431 return Idx < AT->getNumElements();432 433 return Idx < cast<StructType>(T)->getNumElements();434}435 436/// Move the given iterators to the next leaf type in depth first traversal.437///438/// Performs a depth-first traversal of the type as specified by its arguments,439/// stopping at the next leaf node (which may be a legitimate scalar type or an440/// empty struct or array).441///442/// @param SubTypes List of the partial components making up the type from443/// outermost to innermost non-empty aggregate. The element currently444/// represented is SubTypes.back()->getTypeAtIndex(Path.back() - 1).445///446/// @param Path Set of extractvalue indices leading from the outermost type447/// (SubTypes[0]) to the leaf node currently represented.448///449/// @returns true if a new type was found, false otherwise. Calling this450/// function again on a finished iterator will repeatedly return451/// false. SubTypes.back()->getTypeAtIndex(Path.back()) is either an empty452/// aggregate or a non-aggregate453static bool advanceToNextLeafType(SmallVectorImpl<Type *> &SubTypes,454 SmallVectorImpl<unsigned> &Path) {455 // First march back up the tree until we can successfully increment one of the456 // coordinates in Path.457 while (!Path.empty() && !indexReallyValid(SubTypes.back(), Path.back() + 1)) {458 Path.pop_back();459 SubTypes.pop_back();460 }461 462 // If we reached the top, then the iterator is done.463 if (Path.empty())464 return false;465 466 // We know there's *some* valid leaf now, so march back down the tree picking467 // out the left-most element at each node.468 ++Path.back();469 Type *DeeperType =470 ExtractValueInst::getIndexedType(SubTypes.back(), Path.back());471 while (DeeperType->isAggregateType()) {472 if (!indexReallyValid(DeeperType, 0))473 return true;474 475 SubTypes.push_back(DeeperType);476 Path.push_back(0);477 478 DeeperType = ExtractValueInst::getIndexedType(DeeperType, 0);479 }480 481 return true;482}483 484/// Find the first non-empty, scalar-like type in Next and setup the iterator485/// components.486///487/// Assuming Next is an aggregate of some kind, this function will traverse the488/// tree from left to right (i.e. depth-first) looking for the first489/// non-aggregate type which will play a role in function return.490///491/// For example, if Next was {[0 x i64], {{}, i32, {}}, i32} then we would setup492/// Path as [1, 1] and SubTypes as [Next, {{}, i32, {}}] to represent the first493/// i32 in that type.494static bool firstRealType(Type *Next, SmallVectorImpl<Type *> &SubTypes,495 SmallVectorImpl<unsigned> &Path) {496 // First initialise the iterator components to the first "leaf" node497 // (i.e. node with no valid sub-type at any index, so {} does count as a leaf498 // despite nominally being an aggregate).499 while (Type *FirstInner = ExtractValueInst::getIndexedType(Next, 0)) {500 SubTypes.push_back(Next);501 Path.push_back(0);502 Next = FirstInner;503 }504 505 // If there's no Path now, Next was originally scalar already (or empty506 // leaf). We're done.507 if (Path.empty())508 return true;509 510 // Otherwise, use normal iteration to keep looking through the tree until we511 // find a non-aggregate type.512 while (ExtractValueInst::getIndexedType(SubTypes.back(), Path.back())513 ->isAggregateType()) {514 if (!advanceToNextLeafType(SubTypes, Path))515 return false;516 }517 518 return true;519}520 521/// Set the iterator data-structures to the next non-empty, non-aggregate522/// subtype.523static bool nextRealType(SmallVectorImpl<Type *> &SubTypes,524 SmallVectorImpl<unsigned> &Path) {525 do {526 if (!advanceToNextLeafType(SubTypes, Path))527 return false;528 529 assert(!Path.empty() && "found a leaf but didn't set the path?");530 } while (ExtractValueInst::getIndexedType(SubTypes.back(), Path.back())531 ->isAggregateType());532 533 return true;534}535 536 537/// Test if the given instruction is in a position to be optimized538/// with a tail-call. This roughly means that it's in a block with539/// a return and there's nothing that needs to be scheduled540/// between it and the return.541///542/// This function only tests target-independent requirements.543bool llvm::isInTailCallPosition(const CallBase &Call, const TargetMachine &TM,544 bool ReturnsFirstArg) {545 const BasicBlock *ExitBB = Call.getParent();546 const Instruction *Term = ExitBB->getTerminator();547 const ReturnInst *Ret = dyn_cast<ReturnInst>(Term);548 549 // The block must end in a return statement or unreachable.550 //551 // FIXME: Decline tailcall if it's not guaranteed and if the block ends in552 // an unreachable, for now. The way tailcall optimization is currently553 // implemented means it will add an epilogue followed by a jump. That is554 // not profitable. Also, if the callee is a special function (e.g.555 // longjmp on x86), it can end up causing miscompilation that has not556 // been fully understood.557 if (!Ret && ((!TM.Options.GuaranteedTailCallOpt &&558 Call.getCallingConv() != CallingConv::Tail &&559 Call.getCallingConv() != CallingConv::SwiftTail) ||560 !isa<UnreachableInst>(Term)))561 return false;562 563 // If I will have a chain, make sure no other instruction that will have a564 // chain interposes between I and the return.565 // Check for all calls including speculatable functions.566 for (BasicBlock::const_iterator BBI = std::prev(ExitBB->end(), 2);; --BBI) {567 if (&*BBI == &Call)568 break;569 // Debug info intrinsics do not get in the way of tail call optimization.570 // Pseudo probe intrinsics do not block tail call optimization either.571 if (BBI->isDebugOrPseudoInst())572 continue;573 // A lifetime end, assume or noalias.decl intrinsic should not stop tail574 // call optimization.575 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI))576 if (II->getIntrinsicID() == Intrinsic::lifetime_end ||577 II->getIntrinsicID() == Intrinsic::assume ||578 II->getIntrinsicID() == Intrinsic::experimental_noalias_scope_decl ||579 II->getIntrinsicID() == Intrinsic::fake_use)580 continue;581 if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() ||582 !isSafeToSpeculativelyExecute(&*BBI))583 return false;584 }585 586 const Function *F = ExitBB->getParent();587 return returnTypeIsEligibleForTailCall(588 F, &Call, Ret, *TM.getSubtargetImpl(*F)->getTargetLowering(),589 ReturnsFirstArg);590}591 592bool llvm::attributesPermitTailCall(const Function *F, const Instruction *I,593 const ReturnInst *Ret,594 const TargetLoweringBase &TLI,595 bool *AllowDifferingSizes) {596 // ADS may be null, so don't write to it directly.597 bool DummyADS;598 bool &ADS = AllowDifferingSizes ? *AllowDifferingSizes : DummyADS;599 ADS = true;600 601 AttrBuilder CallerAttrs(F->getContext(), F->getAttributes().getRetAttrs());602 AttrBuilder CalleeAttrs(F->getContext(),603 cast<CallInst>(I)->getAttributes().getRetAttrs());604 605 // Following attributes are completely benign as far as calling convention606 // goes, they shouldn't affect whether the call is a tail call.607 for (const auto &Attr : {Attribute::Alignment, Attribute::Dereferenceable,608 Attribute::DereferenceableOrNull, Attribute::NoAlias,609 Attribute::NonNull, Attribute::NoUndef,610 Attribute::Range, Attribute::NoFPClass}) {611 CallerAttrs.removeAttribute(Attr);612 CalleeAttrs.removeAttribute(Attr);613 }614 615 if (CallerAttrs.contains(Attribute::ZExt)) {616 if (!CalleeAttrs.contains(Attribute::ZExt))617 return false;618 619 ADS = false;620 CallerAttrs.removeAttribute(Attribute::ZExt);621 CalleeAttrs.removeAttribute(Attribute::ZExt);622 } else if (CallerAttrs.contains(Attribute::SExt)) {623 if (!CalleeAttrs.contains(Attribute::SExt))624 return false;625 626 ADS = false;627 CallerAttrs.removeAttribute(Attribute::SExt);628 CalleeAttrs.removeAttribute(Attribute::SExt);629 }630 631 // Drop sext and zext return attributes if the result is not used.632 // This enables tail calls for code like:633 //634 // define void @caller() {635 // entry:636 // %unused_result = tail call zeroext i1 @callee()637 // br label %retlabel638 // retlabel:639 // ret void640 // }641 if (I->use_empty()) {642 CalleeAttrs.removeAttribute(Attribute::SExt);643 CalleeAttrs.removeAttribute(Attribute::ZExt);644 }645 646 // If they're still different, there's some facet we don't understand647 // (currently only "inreg", but in future who knows). It may be OK but the648 // only safe option is to reject the tail call.649 return CallerAttrs == CalleeAttrs;650}651 652bool llvm::returnTypeIsEligibleForTailCall(const Function *F,653 const Instruction *I,654 const ReturnInst *Ret,655 const TargetLoweringBase &TLI,656 bool ReturnsFirstArg) {657 // If the block ends with a void return or unreachable, it doesn't matter658 // what the call's return type is.659 if (!Ret || Ret->getNumOperands() == 0) return true;660 661 // If the return value is undef, it doesn't matter what the call's662 // return type is.663 if (isa<UndefValue>(Ret->getOperand(0))) return true;664 665 // Make sure the attributes attached to each return are compatible.666 bool AllowDifferingSizes;667 if (!attributesPermitTailCall(F, I, Ret, TLI, &AllowDifferingSizes))668 return false;669 670 // If the return value is the first argument of the call.671 if (ReturnsFirstArg)672 return true;673 674 const Value *RetVal = Ret->getOperand(0), *CallVal = I;675 SmallVector<unsigned, 4> RetPath, CallPath;676 SmallVector<Type *, 4> RetSubTypes, CallSubTypes;677 678 bool RetEmpty = !firstRealType(RetVal->getType(), RetSubTypes, RetPath);679 bool CallEmpty = !firstRealType(CallVal->getType(), CallSubTypes, CallPath);680 681 // Nothing's actually returned, it doesn't matter what the callee put there682 // it's a valid tail call.683 if (RetEmpty)684 return true;685 686 // Iterate pairwise through each of the value types making up the tail call687 // and the corresponding return. For each one we want to know whether it's688 // essentially going directly from the tail call to the ret, via operations689 // that end up not generating any code.690 //691 // We allow a certain amount of covariance here. For example it's permitted692 // for the tail call to define more bits than the ret actually cares about693 // (e.g. via a truncate).694 do {695 if (CallEmpty) {696 // We've exhausted the values produced by the tail call instruction, the697 // rest are essentially undef. The type doesn't really matter, but we need698 // *something*.699 Type *SlotType =700 ExtractValueInst::getIndexedType(RetSubTypes.back(), RetPath.back());701 CallVal = UndefValue::get(SlotType);702 }703 704 // The manipulations performed when we're looking through an insertvalue or705 // an extractvalue would happen at the front of the RetPath list, so since706 // we have to copy it anyway it's more efficient to create a reversed copy.707 SmallVector<unsigned, 4> TmpRetPath(llvm::reverse(RetPath));708 SmallVector<unsigned, 4> TmpCallPath(llvm::reverse(CallPath));709 710 // Finally, we can check whether the value produced by the tail call at this711 // index is compatible with the value we return.712 if (!slotOnlyDiscardsData(RetVal, CallVal, TmpRetPath, TmpCallPath,713 AllowDifferingSizes, TLI,714 F->getDataLayout()))715 return false;716 717 CallEmpty = !nextRealType(CallSubTypes, CallPath);718 } while(nextRealType(RetSubTypes, RetPath));719 720 return true;721}722 723bool llvm::funcReturnsFirstArgOfCall(const CallInst &CI) {724 const ReturnInst *Ret = dyn_cast<ReturnInst>(CI.getParent()->getTerminator());725 Value *RetVal = Ret ? Ret->getReturnValue() : nullptr;726 bool ReturnsFirstArg = false;727 if (RetVal && ((RetVal == CI.getArgOperand(0))))728 ReturnsFirstArg = true;729 return ReturnsFirstArg;730}731 732static void collectEHScopeMembers(733 DenseMap<const MachineBasicBlock *, int> &EHScopeMembership, int EHScope,734 const MachineBasicBlock *MBB) {735 SmallVector<const MachineBasicBlock *, 16> Worklist = {MBB};736 while (!Worklist.empty()) {737 const MachineBasicBlock *Visiting = Worklist.pop_back_val();738 // Don't follow blocks which start new scopes.739 if (Visiting->isEHPad() && Visiting != MBB)740 continue;741 742 // Add this MBB to our scope.743 auto P = EHScopeMembership.insert(std::make_pair(Visiting, EHScope));744 745 // Don't revisit blocks.746 if (!P.second) {747 assert(P.first->second == EHScope && "MBB is part of two scopes!");748 continue;749 }750 751 // Returns are boundaries where scope transfer can occur, don't follow752 // successors.753 if (Visiting->isEHScopeReturnBlock())754 continue;755 756 append_range(Worklist, Visiting->successors());757 }758}759 760DenseMap<const MachineBasicBlock *, int>761llvm::getEHScopeMembership(const MachineFunction &MF) {762 DenseMap<const MachineBasicBlock *, int> EHScopeMembership;763 764 // We don't have anything to do if there aren't any EH pads.765 if (!MF.hasEHScopes())766 return EHScopeMembership;767 768 int EntryBBNumber = MF.front().getNumber();769 bool IsSEH = isAsynchronousEHPersonality(770 classifyEHPersonality(MF.getFunction().getPersonalityFn()));771 772 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();773 SmallVector<const MachineBasicBlock *, 16> EHScopeBlocks;774 SmallVector<const MachineBasicBlock *, 16> UnreachableBlocks;775 SmallVector<const MachineBasicBlock *, 16> SEHCatchPads;776 SmallVector<std::pair<const MachineBasicBlock *, int>, 16> CatchRetSuccessors;777 for (const MachineBasicBlock &MBB : MF) {778 if (MBB.isEHScopeEntry()) {779 EHScopeBlocks.push_back(&MBB);780 } else if (IsSEH && MBB.isEHPad()) {781 SEHCatchPads.push_back(&MBB);782 } else if (MBB.pred_empty()) {783 UnreachableBlocks.push_back(&MBB);784 }785 786 MachineBasicBlock::const_iterator MBBI = MBB.getFirstTerminator();787 788 // CatchPads are not scopes for SEH so do not consider CatchRet to789 // transfer control to another scope.790 if (MBBI == MBB.end() || MBBI->getOpcode() != TII->getCatchReturnOpcode())791 continue;792 793 // FIXME: SEH CatchPads are not necessarily in the parent function:794 // they could be inside a finally block.795 const MachineBasicBlock *Successor = MBBI->getOperand(0).getMBB();796 const MachineBasicBlock *SuccessorColor = MBBI->getOperand(1).getMBB();797 CatchRetSuccessors.push_back(798 {Successor, IsSEH ? EntryBBNumber : SuccessorColor->getNumber()});799 }800 801 // We don't have anything to do if there aren't any EH pads.802 if (EHScopeBlocks.empty())803 return EHScopeMembership;804 805 // Identify all the basic blocks reachable from the function entry.806 collectEHScopeMembers(EHScopeMembership, EntryBBNumber, &MF.front());807 // All blocks not part of a scope are in the parent function.808 for (const MachineBasicBlock *MBB : UnreachableBlocks)809 collectEHScopeMembers(EHScopeMembership, EntryBBNumber, MBB);810 // Next, identify all the blocks inside the scopes.811 for (const MachineBasicBlock *MBB : EHScopeBlocks)812 collectEHScopeMembers(EHScopeMembership, MBB->getNumber(), MBB);813 // SEH CatchPads aren't really scopes, handle them separately.814 for (const MachineBasicBlock *MBB : SEHCatchPads)815 collectEHScopeMembers(EHScopeMembership, EntryBBNumber, MBB);816 // Finally, identify all the targets of a catchret.817 for (std::pair<const MachineBasicBlock *, int> CatchRetPair :818 CatchRetSuccessors)819 collectEHScopeMembers(EHScopeMembership, CatchRetPair.second,820 CatchRetPair.first);821 return EHScopeMembership;822}823