Analysis.cpp 33 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802
  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. #include "llvm/CodeGen/Analysis.h"
  13. #include "llvm/Analysis/ValueTracking.h"
  14. #include "llvm/CodeGen/MachineFunction.h"
  15. #include "llvm/CodeGen/TargetInstrInfo.h"
  16. #include "llvm/CodeGen/TargetLowering.h"
  17. #include "llvm/CodeGen/TargetSubtargetInfo.h"
  18. #include "llvm/IR/DataLayout.h"
  19. #include "llvm/IR/DerivedTypes.h"
  20. #include "llvm/IR/Function.h"
  21. #include "llvm/IR/Instructions.h"
  22. #include "llvm/IR/IntrinsicInst.h"
  23. #include "llvm/IR/LLVMContext.h"
  24. #include "llvm/IR/Module.h"
  25. #include "llvm/Support/ErrorHandling.h"
  26. #include "llvm/Support/MathExtras.h"
  27. #include "llvm/Target/TargetMachine.h"
  28. #include "llvm/Transforms/Utils/GlobalStatus.h"
  29. using namespace llvm;
  30. /// Compute the linearized index of a member in a nested aggregate/struct/array
  31. /// by recursing and accumulating CurIndex as long as there are indices in the
  32. /// index list.
  33. unsigned 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. // Given a struct type, recursively traverse the elements.
  41. if (StructType *STy = dyn_cast<StructType>(Ty)) {
  42. for (StructType::element_iterator EB = STy->element_begin(),
  43. EI = EB,
  44. EE = STy->element_end();
  45. EI != EE; ++EI) {
  46. if (Indices && *Indices == unsigned(EI - EB))
  47. return ComputeLinearIndex(*EI, Indices+1, IndicesEnd, CurIndex);
  48. CurIndex = ComputeLinearIndex(*EI, nullptr, nullptr, CurIndex);
  49. }
  50. assert(!Indices && "Unexpected out of bound");
  51. return CurIndex;
  52. }
  53. // Given an array type, recursively traverse the elements.
  54. else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
  55. Type *EltTy = ATy->getElementType();
  56. unsigned NumElts = ATy->getNumElements();
  57. // Compute the Linear offset when jumping one element of the array
  58. unsigned EltLinearOffset = ComputeLinearIndex(EltTy, nullptr, nullptr, 0);
  59. if (Indices) {
  60. assert(*Indices < NumElts && "Unexpected out of bound");
  61. // If the indice is inside the array, compute the index to the requested
  62. // elt and recurse inside the element with the end of the indices list
  63. CurIndex += EltLinearOffset* *Indices;
  64. return ComputeLinearIndex(EltTy, Indices+1, IndicesEnd, CurIndex);
  65. }
  66. CurIndex += EltLinearOffset*NumElts;
  67. return CurIndex;
  68. }
  69. // We haven't found the type we're looking for, so keep searching.
  70. return CurIndex + 1;
  71. }
  72. /// ComputeValueVTs - Given an LLVM IR type, compute a sequence of
  73. /// EVTs that represent all the individual underlying
  74. /// non-aggregate types that comprise it.
  75. ///
  76. /// If Offsets is non-null, it points to a vector to be filled in
  77. /// with the in-memory offsets of each of the individual values.
  78. ///
  79. void llvm::ComputeValueVTs(const TargetLowering &TLI, const DataLayout &DL,
  80. Type *Ty, SmallVectorImpl<EVT> &ValueVTs,
  81. SmallVectorImpl<EVT> *MemVTs,
  82. SmallVectorImpl<uint64_t> *Offsets,
  83. uint64_t StartingOffset) {
  84. // Given a struct type, recursively traverse the elements.
  85. if (StructType *STy = dyn_cast<StructType>(Ty)) {
  86. // If the Offsets aren't needed, don't query the struct layout. This allows
  87. // us to support structs with scalable vectors for operations that don't
  88. // need offsets.
  89. const StructLayout *SL = Offsets ? DL.getStructLayout(STy) : nullptr;
  90. for (StructType::element_iterator EB = STy->element_begin(),
  91. EI = EB,
  92. EE = STy->element_end();
  93. EI != EE; ++EI) {
  94. // Don't compute the element offset if we didn't get a StructLayout above.
  95. uint64_t EltOffset = SL ? SL->getElementOffset(EI - EB) : 0;
  96. ComputeValueVTs(TLI, DL, *EI, ValueVTs, MemVTs, Offsets,
  97. StartingOffset + EltOffset);
  98. }
  99. return;
  100. }
  101. // Given an array type, recursively traverse the elements.
  102. if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
  103. Type *EltTy = ATy->getElementType();
  104. uint64_t EltSize = DL.getTypeAllocSize(EltTy).getFixedValue();
  105. for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
  106. ComputeValueVTs(TLI, DL, EltTy, ValueVTs, MemVTs, Offsets,
  107. StartingOffset + i * EltSize);
  108. return;
  109. }
  110. // Interpret void as zero return values.
  111. if (Ty->isVoidTy())
  112. return;
  113. // Base case: we can get an EVT for this LLVM IR type.
  114. ValueVTs.push_back(TLI.getValueType(DL, Ty));
  115. if (MemVTs)
  116. MemVTs->push_back(TLI.getMemValueType(DL, Ty));
  117. if (Offsets)
  118. Offsets->push_back(StartingOffset);
  119. }
  120. void llvm::ComputeValueVTs(const TargetLowering &TLI, const DataLayout &DL,
  121. Type *Ty, SmallVectorImpl<EVT> &ValueVTs,
  122. SmallVectorImpl<uint64_t> *Offsets,
  123. uint64_t StartingOffset) {
  124. return ComputeValueVTs(TLI, DL, Ty, ValueVTs, /*MemVTs=*/nullptr, Offsets,
  125. StartingOffset);
  126. }
  127. void llvm::computeValueLLTs(const DataLayout &DL, Type &Ty,
  128. SmallVectorImpl<LLT> &ValueTys,
  129. SmallVectorImpl<uint64_t> *Offsets,
  130. uint64_t StartingOffset) {
  131. // Given a struct type, recursively traverse the elements.
  132. if (StructType *STy = dyn_cast<StructType>(&Ty)) {
  133. // If the Offsets aren't needed, don't query the struct layout. This allows
  134. // us to support structs with scalable vectors for operations that don't
  135. // need offsets.
  136. const StructLayout *SL = Offsets ? DL.getStructLayout(STy) : nullptr;
  137. for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
  138. uint64_t EltOffset = SL ? SL->getElementOffset(I) : 0;
  139. computeValueLLTs(DL, *STy->getElementType(I), ValueTys, Offsets,
  140. StartingOffset + EltOffset);
  141. }
  142. return;
  143. }
  144. // Given an array type, recursively traverse the elements.
  145. if (ArrayType *ATy = dyn_cast<ArrayType>(&Ty)) {
  146. Type *EltTy = ATy->getElementType();
  147. uint64_t EltSize = DL.getTypeAllocSize(EltTy).getFixedValue();
  148. for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
  149. computeValueLLTs(DL, *EltTy, ValueTys, Offsets,
  150. StartingOffset + i * EltSize);
  151. return;
  152. }
  153. // Interpret void as zero return values.
  154. if (Ty.isVoidTy())
  155. return;
  156. // Base case: we can get an LLT for this LLVM IR type.
  157. ValueTys.push_back(getLLTForType(Ty, DL));
  158. if (Offsets != nullptr)
  159. Offsets->push_back(StartingOffset * 8);
  160. }
  161. /// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V.
  162. GlobalValue *llvm::ExtractTypeInfo(Value *V) {
  163. V = V->stripPointerCasts();
  164. GlobalValue *GV = dyn_cast<GlobalValue>(V);
  165. GlobalVariable *Var = dyn_cast<GlobalVariable>(V);
  166. if (Var && Var->getName() == "llvm.eh.catch.all.value") {
  167. assert(Var->hasInitializer() &&
  168. "The EH catch-all value must have an initializer");
  169. Value *Init = Var->getInitializer();
  170. GV = dyn_cast<GlobalValue>(Init);
  171. if (!GV) V = cast<ConstantPointerNull>(Init);
  172. }
  173. assert((GV || isa<ConstantPointerNull>(V)) &&
  174. "TypeInfo must be a global variable or NULL");
  175. return GV;
  176. }
  177. /// getFCmpCondCode - Return the ISD condition code corresponding to
  178. /// the given LLVM IR floating-point condition code. This includes
  179. /// consideration of global floating-point math flags.
  180. ///
  181. ISD::CondCode llvm::getFCmpCondCode(FCmpInst::Predicate Pred) {
  182. switch (Pred) {
  183. case FCmpInst::FCMP_FALSE: return ISD::SETFALSE;
  184. case FCmpInst::FCMP_OEQ: return ISD::SETOEQ;
  185. case FCmpInst::FCMP_OGT: return ISD::SETOGT;
  186. case FCmpInst::FCMP_OGE: return ISD::SETOGE;
  187. case FCmpInst::FCMP_OLT: return ISD::SETOLT;
  188. case FCmpInst::FCMP_OLE: return ISD::SETOLE;
  189. case FCmpInst::FCMP_ONE: return ISD::SETONE;
  190. case FCmpInst::FCMP_ORD: return ISD::SETO;
  191. case FCmpInst::FCMP_UNO: return ISD::SETUO;
  192. case FCmpInst::FCMP_UEQ: return ISD::SETUEQ;
  193. case FCmpInst::FCMP_UGT: return ISD::SETUGT;
  194. case FCmpInst::FCMP_UGE: return ISD::SETUGE;
  195. case FCmpInst::FCMP_ULT: return ISD::SETULT;
  196. case FCmpInst::FCMP_ULE: return ISD::SETULE;
  197. case FCmpInst::FCMP_UNE: return ISD::SETUNE;
  198. case FCmpInst::FCMP_TRUE: return ISD::SETTRUE;
  199. default: llvm_unreachable("Invalid FCmp predicate opcode!");
  200. }
  201. }
  202. ISD::CondCode llvm::getFCmpCodeWithoutNaN(ISD::CondCode CC) {
  203. switch (CC) {
  204. case ISD::SETOEQ: case ISD::SETUEQ: return ISD::SETEQ;
  205. case ISD::SETONE: case ISD::SETUNE: return ISD::SETNE;
  206. case ISD::SETOLT: case ISD::SETULT: return ISD::SETLT;
  207. case ISD::SETOLE: case ISD::SETULE: return ISD::SETLE;
  208. case ISD::SETOGT: case ISD::SETUGT: return ISD::SETGT;
  209. case ISD::SETOGE: case ISD::SETUGE: return ISD::SETGE;
  210. default: return CC;
  211. }
  212. }
  213. /// getICmpCondCode - Return the ISD condition code corresponding to
  214. /// the given LLVM IR integer condition code.
  215. ///
  216. ISD::CondCode llvm::getICmpCondCode(ICmpInst::Predicate Pred) {
  217. switch (Pred) {
  218. case ICmpInst::ICMP_EQ: return ISD::SETEQ;
  219. case ICmpInst::ICMP_NE: return ISD::SETNE;
  220. case ICmpInst::ICMP_SLE: return ISD::SETLE;
  221. case ICmpInst::ICMP_ULE: return ISD::SETULE;
  222. case ICmpInst::ICMP_SGE: return ISD::SETGE;
  223. case ICmpInst::ICMP_UGE: return ISD::SETUGE;
  224. case ICmpInst::ICMP_SLT: return ISD::SETLT;
  225. case ICmpInst::ICMP_ULT: return ISD::SETULT;
  226. case ICmpInst::ICMP_SGT: return ISD::SETGT;
  227. case ICmpInst::ICMP_UGT: return ISD::SETUGT;
  228. default:
  229. llvm_unreachable("Invalid ICmp predicate opcode!");
  230. }
  231. }
  232. static bool isNoopBitcast(Type *T1, Type *T2,
  233. const TargetLoweringBase& TLI) {
  234. return T1 == T2 || (T1->isPointerTy() && T2->isPointerTy()) ||
  235. (isa<VectorType>(T1) && isa<VectorType>(T2) &&
  236. TLI.isTypeLegal(EVT::getEVT(T1)) && TLI.isTypeLegal(EVT::getEVT(T2)));
  237. }
  238. /// Look through operations that will be free to find the earliest source of
  239. /// this value.
  240. ///
  241. /// @param ValLoc If V has aggregate type, we will be interested in a particular
  242. /// scalar component. This records its address; the reverse of this list gives a
  243. /// sequence of indices appropriate for an extractvalue to locate the important
  244. /// value. This value is updated during the function and on exit will indicate
  245. /// similar information for the Value returned.
  246. ///
  247. /// @param DataBits If this function looks through truncate instructions, this
  248. /// will record the smallest size attained.
  249. static const Value *getNoopInput(const Value *V,
  250. SmallVectorImpl<unsigned> &ValLoc,
  251. unsigned &DataBits,
  252. const TargetLoweringBase &TLI,
  253. const DataLayout &DL) {
  254. while (true) {
  255. // Try to look through V1; if V1 is not an instruction, it can't be looked
  256. // through.
  257. const Instruction *I = dyn_cast<Instruction>(V);
  258. if (!I || I->getNumOperands() == 0) return V;
  259. const Value *NoopInput = nullptr;
  260. Value *Op = I->getOperand(0);
  261. if (isa<BitCastInst>(I)) {
  262. // Look through truly no-op bitcasts.
  263. if (isNoopBitcast(Op->getType(), I->getType(), TLI))
  264. NoopInput = Op;
  265. } else if (isa<GetElementPtrInst>(I)) {
  266. // Look through getelementptr
  267. if (cast<GetElementPtrInst>(I)->hasAllZeroIndices())
  268. NoopInput = Op;
  269. } else if (isa<IntToPtrInst>(I)) {
  270. // Look through inttoptr.
  271. // Make sure this isn't a truncating or extending cast. We could
  272. // support this eventually, but don't bother for now.
  273. if (!isa<VectorType>(I->getType()) &&
  274. DL.getPointerSizeInBits() ==
  275. cast<IntegerType>(Op->getType())->getBitWidth())
  276. NoopInput = Op;
  277. } else if (isa<PtrToIntInst>(I)) {
  278. // Look through ptrtoint.
  279. // Make sure this isn't a truncating or extending cast. We could
  280. // support this eventually, but don't bother for now.
  281. if (!isa<VectorType>(I->getType()) &&
  282. DL.getPointerSizeInBits() ==
  283. cast<IntegerType>(I->getType())->getBitWidth())
  284. NoopInput = Op;
  285. } else if (isa<TruncInst>(I) &&
  286. TLI.allowTruncateForTailCall(Op->getType(), I->getType())) {
  287. DataBits = std::min((uint64_t)DataBits,
  288. I->getType()->getPrimitiveSizeInBits().getFixedSize());
  289. NoopInput = Op;
  290. } else if (auto *CB = dyn_cast<CallBase>(I)) {
  291. const Value *ReturnedOp = CB->getReturnedArgOperand();
  292. if (ReturnedOp && isNoopBitcast(ReturnedOp->getType(), I->getType(), TLI))
  293. NoopInput = ReturnedOp;
  294. } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(V)) {
  295. // Value may come from either the aggregate or the scalar
  296. ArrayRef<unsigned> InsertLoc = IVI->getIndices();
  297. if (ValLoc.size() >= InsertLoc.size() &&
  298. std::equal(InsertLoc.begin(), InsertLoc.end(), ValLoc.rbegin())) {
  299. // The type being inserted is a nested sub-type of the aggregate; we
  300. // have to remove those initial indices to get the location we're
  301. // interested in for the operand.
  302. ValLoc.resize(ValLoc.size() - InsertLoc.size());
  303. NoopInput = IVI->getInsertedValueOperand();
  304. } else {
  305. // The struct we're inserting into has the value we're interested in, no
  306. // change of address.
  307. NoopInput = Op;
  308. }
  309. } else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) {
  310. // The part we're interested in will inevitably be some sub-section of the
  311. // previous aggregate. Combine the two paths to obtain the true address of
  312. // our element.
  313. ArrayRef<unsigned> ExtractLoc = EVI->getIndices();
  314. ValLoc.append(ExtractLoc.rbegin(), ExtractLoc.rend());
  315. NoopInput = Op;
  316. }
  317. // Terminate if we couldn't find anything to look through.
  318. if (!NoopInput)
  319. return V;
  320. V = NoopInput;
  321. }
  322. }
  323. /// Return true if this scalar return value only has bits discarded on its path
  324. /// from the "tail call" to the "ret". This includes the obvious noop
  325. /// instructions handled by getNoopInput above as well as free truncations (or
  326. /// extensions prior to the call).
  327. static bool slotOnlyDiscardsData(const Value *RetVal, const Value *CallVal,
  328. SmallVectorImpl<unsigned> &RetIndices,
  329. SmallVectorImpl<unsigned> &CallIndices,
  330. bool AllowDifferingSizes,
  331. const TargetLoweringBase &TLI,
  332. const DataLayout &DL) {
  333. // Trace the sub-value needed by the return value as far back up the graph as
  334. // possible, in the hope that it will intersect with the value produced by the
  335. // call. In the simple case with no "returned" attribute, the hope is actually
  336. // that we end up back at the tail call instruction itself.
  337. unsigned BitsRequired = UINT_MAX;
  338. RetVal = getNoopInput(RetVal, RetIndices, BitsRequired, TLI, DL);
  339. // If this slot in the value returned is undef, it doesn't matter what the
  340. // call puts there, it'll be fine.
  341. if (isa<UndefValue>(RetVal))
  342. return true;
  343. // Now do a similar search up through the graph to find where the value
  344. // actually returned by the "tail call" comes from. In the simple case without
  345. // a "returned" attribute, the search will be blocked immediately and the loop
  346. // a Noop.
  347. unsigned BitsProvided = UINT_MAX;
  348. CallVal = getNoopInput(CallVal, CallIndices, BitsProvided, TLI, DL);
  349. // There's no hope if we can't actually trace them to (the same part of!) the
  350. // same value.
  351. if (CallVal != RetVal || CallIndices != RetIndices)
  352. return false;
  353. // However, intervening truncates may have made the call non-tail. Make sure
  354. // all the bits that are needed by the "ret" have been provided by the "tail
  355. // call". FIXME: with sufficiently cunning bit-tracking, we could look through
  356. // extensions too.
  357. if (BitsProvided < BitsRequired ||
  358. (!AllowDifferingSizes && BitsProvided != BitsRequired))
  359. return false;
  360. return true;
  361. }
  362. /// For an aggregate type, determine whether a given index is within bounds or
  363. /// not.
  364. static bool indexReallyValid(Type *T, unsigned Idx) {
  365. if (ArrayType *AT = dyn_cast<ArrayType>(T))
  366. return Idx < AT->getNumElements();
  367. return Idx < cast<StructType>(T)->getNumElements();
  368. }
  369. /// Move the given iterators to the next leaf type in depth first traversal.
  370. ///
  371. /// Performs a depth-first traversal of the type as specified by its arguments,
  372. /// stopping at the next leaf node (which may be a legitimate scalar type or an
  373. /// empty struct or array).
  374. ///
  375. /// @param SubTypes List of the partial components making up the type from
  376. /// outermost to innermost non-empty aggregate. The element currently
  377. /// represented is SubTypes.back()->getTypeAtIndex(Path.back() - 1).
  378. ///
  379. /// @param Path Set of extractvalue indices leading from the outermost type
  380. /// (SubTypes[0]) to the leaf node currently represented.
  381. ///
  382. /// @returns true if a new type was found, false otherwise. Calling this
  383. /// function again on a finished iterator will repeatedly return
  384. /// false. SubTypes.back()->getTypeAtIndex(Path.back()) is either an empty
  385. /// aggregate or a non-aggregate
  386. static bool advanceToNextLeafType(SmallVectorImpl<Type *> &SubTypes,
  387. SmallVectorImpl<unsigned> &Path) {
  388. // First march back up the tree until we can successfully increment one of the
  389. // coordinates in Path.
  390. while (!Path.empty() && !indexReallyValid(SubTypes.back(), Path.back() + 1)) {
  391. Path.pop_back();
  392. SubTypes.pop_back();
  393. }
  394. // If we reached the top, then the iterator is done.
  395. if (Path.empty())
  396. return false;
  397. // We know there's *some* valid leaf now, so march back down the tree picking
  398. // out the left-most element at each node.
  399. ++Path.back();
  400. Type *DeeperType =
  401. ExtractValueInst::getIndexedType(SubTypes.back(), Path.back());
  402. while (DeeperType->isAggregateType()) {
  403. if (!indexReallyValid(DeeperType, 0))
  404. return true;
  405. SubTypes.push_back(DeeperType);
  406. Path.push_back(0);
  407. DeeperType = ExtractValueInst::getIndexedType(DeeperType, 0);
  408. }
  409. return true;
  410. }
  411. /// Find the first non-empty, scalar-like type in Next and setup the iterator
  412. /// components.
  413. ///
  414. /// Assuming Next is an aggregate of some kind, this function will traverse the
  415. /// tree from left to right (i.e. depth-first) looking for the first
  416. /// non-aggregate type which will play a role in function return.
  417. ///
  418. /// For example, if Next was {[0 x i64], {{}, i32, {}}, i32} then we would setup
  419. /// Path as [1, 1] and SubTypes as [Next, {{}, i32, {}}] to represent the first
  420. /// i32 in that type.
  421. static bool firstRealType(Type *Next, SmallVectorImpl<Type *> &SubTypes,
  422. SmallVectorImpl<unsigned> &Path) {
  423. // First initialise the iterator components to the first "leaf" node
  424. // (i.e. node with no valid sub-type at any index, so {} does count as a leaf
  425. // despite nominally being an aggregate).
  426. while (Type *FirstInner = ExtractValueInst::getIndexedType(Next, 0)) {
  427. SubTypes.push_back(Next);
  428. Path.push_back(0);
  429. Next = FirstInner;
  430. }
  431. // If there's no Path now, Next was originally scalar already (or empty
  432. // leaf). We're done.
  433. if (Path.empty())
  434. return true;
  435. // Otherwise, use normal iteration to keep looking through the tree until we
  436. // find a non-aggregate type.
  437. while (ExtractValueInst::getIndexedType(SubTypes.back(), Path.back())
  438. ->isAggregateType()) {
  439. if (!advanceToNextLeafType(SubTypes, Path))
  440. return false;
  441. }
  442. return true;
  443. }
  444. /// Set the iterator data-structures to the next non-empty, non-aggregate
  445. /// subtype.
  446. static bool nextRealType(SmallVectorImpl<Type *> &SubTypes,
  447. SmallVectorImpl<unsigned> &Path) {
  448. do {
  449. if (!advanceToNextLeafType(SubTypes, Path))
  450. return false;
  451. assert(!Path.empty() && "found a leaf but didn't set the path?");
  452. } while (ExtractValueInst::getIndexedType(SubTypes.back(), Path.back())
  453. ->isAggregateType());
  454. return true;
  455. }
  456. /// Test if the given instruction is in a position to be optimized
  457. /// with a tail-call. This roughly means that it's in a block with
  458. /// a return and there's nothing that needs to be scheduled
  459. /// between it and the return.
  460. ///
  461. /// This function only tests target-independent requirements.
  462. bool llvm::isInTailCallPosition(const CallBase &Call, const TargetMachine &TM) {
  463. const BasicBlock *ExitBB = Call.getParent();
  464. const Instruction *Term = ExitBB->getTerminator();
  465. const ReturnInst *Ret = dyn_cast<ReturnInst>(Term);
  466. // The block must end in a return statement or unreachable.
  467. //
  468. // FIXME: Decline tailcall if it's not guaranteed and if the block ends in
  469. // an unreachable, for now. The way tailcall optimization is currently
  470. // implemented means it will add an epilogue followed by a jump. That is
  471. // not profitable. Also, if the callee is a special function (e.g.
  472. // longjmp on x86), it can end up causing miscompilation that has not
  473. // been fully understood.
  474. if (!Ret &&
  475. ((!TM.Options.GuaranteedTailCallOpt &&
  476. Call.getCallingConv() != CallingConv::Tail) || !isa<UnreachableInst>(Term)))
  477. return false;
  478. // If I will have a chain, make sure no other instruction that will have a
  479. // chain interposes between I and the return.
  480. // Check for all calls including speculatable functions.
  481. for (BasicBlock::const_iterator BBI = std::prev(ExitBB->end(), 2);; --BBI) {
  482. if (&*BBI == &Call)
  483. break;
  484. // Debug info intrinsics do not get in the way of tail call optimization.
  485. if (isa<DbgInfoIntrinsic>(BBI))
  486. continue;
  487. // Pseudo probe intrinsics do not block tail call optimization either.
  488. if (isa<PseudoProbeInst>(BBI))
  489. continue;
  490. // A lifetime end, assume or noalias.decl intrinsic should not stop tail
  491. // call optimization.
  492. if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI))
  493. if (II->getIntrinsicID() == Intrinsic::lifetime_end ||
  494. II->getIntrinsicID() == Intrinsic::assume ||
  495. II->getIntrinsicID() == Intrinsic::experimental_noalias_scope_decl)
  496. continue;
  497. if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() ||
  498. !isSafeToSpeculativelyExecute(&*BBI))
  499. return false;
  500. }
  501. const Function *F = ExitBB->getParent();
  502. return returnTypeIsEligibleForTailCall(
  503. F, &Call, Ret, *TM.getSubtargetImpl(*F)->getTargetLowering());
  504. }
  505. bool llvm::attributesPermitTailCall(const Function *F, const Instruction *I,
  506. const ReturnInst *Ret,
  507. const TargetLoweringBase &TLI,
  508. bool *AllowDifferingSizes) {
  509. // ADS may be null, so don't write to it directly.
  510. bool DummyADS;
  511. bool &ADS = AllowDifferingSizes ? *AllowDifferingSizes : DummyADS;
  512. ADS = true;
  513. AttrBuilder CallerAttrs(F->getAttributes(), AttributeList::ReturnIndex);
  514. AttrBuilder CalleeAttrs(cast<CallInst>(I)->getAttributes(),
  515. AttributeList::ReturnIndex);
  516. // Following attributes are completely benign as far as calling convention
  517. // goes, they shouldn't affect whether the call is a tail call.
  518. CallerAttrs.removeAttribute(Attribute::NoAlias);
  519. CalleeAttrs.removeAttribute(Attribute::NoAlias);
  520. CallerAttrs.removeAttribute(Attribute::NonNull);
  521. CalleeAttrs.removeAttribute(Attribute::NonNull);
  522. CallerAttrs.removeAttribute(Attribute::Dereferenceable);
  523. CalleeAttrs.removeAttribute(Attribute::Dereferenceable);
  524. CallerAttrs.removeAttribute(Attribute::DereferenceableOrNull);
  525. CalleeAttrs.removeAttribute(Attribute::DereferenceableOrNull);
  526. if (CallerAttrs.contains(Attribute::ZExt)) {
  527. if (!CalleeAttrs.contains(Attribute::ZExt))
  528. return false;
  529. ADS = false;
  530. CallerAttrs.removeAttribute(Attribute::ZExt);
  531. CalleeAttrs.removeAttribute(Attribute::ZExt);
  532. } else if (CallerAttrs.contains(Attribute::SExt)) {
  533. if (!CalleeAttrs.contains(Attribute::SExt))
  534. return false;
  535. ADS = false;
  536. CallerAttrs.removeAttribute(Attribute::SExt);
  537. CalleeAttrs.removeAttribute(Attribute::SExt);
  538. }
  539. // Drop sext and zext return attributes if the result is not used.
  540. // This enables tail calls for code like:
  541. //
  542. // define void @caller() {
  543. // entry:
  544. // %unused_result = tail call zeroext i1 @callee()
  545. // br label %retlabel
  546. // retlabel:
  547. // ret void
  548. // }
  549. if (I->use_empty()) {
  550. CalleeAttrs.removeAttribute(Attribute::SExt);
  551. CalleeAttrs.removeAttribute(Attribute::ZExt);
  552. }
  553. // If they're still different, there's some facet we don't understand
  554. // (currently only "inreg", but in future who knows). It may be OK but the
  555. // only safe option is to reject the tail call.
  556. return CallerAttrs == CalleeAttrs;
  557. }
  558. /// Check whether B is a bitcast of a pointer type to another pointer type,
  559. /// which is equal to A.
  560. static bool isPointerBitcastEqualTo(const Value *A, const Value *B) {
  561. assert(A && B && "Expected non-null inputs!");
  562. auto *BitCastIn = dyn_cast<BitCastInst>(B);
  563. if (!BitCastIn)
  564. return false;
  565. if (!A->getType()->isPointerTy() || !B->getType()->isPointerTy())
  566. return false;
  567. return A == BitCastIn->getOperand(0);
  568. }
  569. bool llvm::returnTypeIsEligibleForTailCall(const Function *F,
  570. const Instruction *I,
  571. const ReturnInst *Ret,
  572. const TargetLoweringBase &TLI) {
  573. // If the block ends with a void return or unreachable, it doesn't matter
  574. // what the call's return type is.
  575. if (!Ret || Ret->getNumOperands() == 0) return true;
  576. // If the return value is undef, it doesn't matter what the call's
  577. // return type is.
  578. if (isa<UndefValue>(Ret->getOperand(0))) return true;
  579. // Make sure the attributes attached to each return are compatible.
  580. bool AllowDifferingSizes;
  581. if (!attributesPermitTailCall(F, I, Ret, TLI, &AllowDifferingSizes))
  582. return false;
  583. const Value *RetVal = Ret->getOperand(0), *CallVal = I;
  584. // Intrinsic like llvm.memcpy has no return value, but the expanded
  585. // libcall may or may not have return value. On most platforms, it
  586. // will be expanded as memcpy in libc, which returns the first
  587. // argument. On other platforms like arm-none-eabi, memcpy may be
  588. // expanded as library call without return value, like __aeabi_memcpy.
  589. const CallInst *Call = cast<CallInst>(I);
  590. if (Function *F = Call->getCalledFunction()) {
  591. Intrinsic::ID IID = F->getIntrinsicID();
  592. if (((IID == Intrinsic::memcpy &&
  593. TLI.getLibcallName(RTLIB::MEMCPY) == StringRef("memcpy")) ||
  594. (IID == Intrinsic::memmove &&
  595. TLI.getLibcallName(RTLIB::MEMMOVE) == StringRef("memmove")) ||
  596. (IID == Intrinsic::memset &&
  597. TLI.getLibcallName(RTLIB::MEMSET) == StringRef("memset"))) &&
  598. (RetVal == Call->getArgOperand(0) ||
  599. isPointerBitcastEqualTo(RetVal, Call->getArgOperand(0))))
  600. return true;
  601. }
  602. SmallVector<unsigned, 4> RetPath, CallPath;
  603. SmallVector<Type *, 4> RetSubTypes, CallSubTypes;
  604. bool RetEmpty = !firstRealType(RetVal->getType(), RetSubTypes, RetPath);
  605. bool CallEmpty = !firstRealType(CallVal->getType(), CallSubTypes, CallPath);
  606. // Nothing's actually returned, it doesn't matter what the callee put there
  607. // it's a valid tail call.
  608. if (RetEmpty)
  609. return true;
  610. // Iterate pairwise through each of the value types making up the tail call
  611. // and the corresponding return. For each one we want to know whether it's
  612. // essentially going directly from the tail call to the ret, via operations
  613. // that end up not generating any code.
  614. //
  615. // We allow a certain amount of covariance here. For example it's permitted
  616. // for the tail call to define more bits than the ret actually cares about
  617. // (e.g. via a truncate).
  618. do {
  619. if (CallEmpty) {
  620. // We've exhausted the values produced by the tail call instruction, the
  621. // rest are essentially undef. The type doesn't really matter, but we need
  622. // *something*.
  623. Type *SlotType =
  624. ExtractValueInst::getIndexedType(RetSubTypes.back(), RetPath.back());
  625. CallVal = UndefValue::get(SlotType);
  626. }
  627. // The manipulations performed when we're looking through an insertvalue or
  628. // an extractvalue would happen at the front of the RetPath list, so since
  629. // we have to copy it anyway it's more efficient to create a reversed copy.
  630. SmallVector<unsigned, 4> TmpRetPath(RetPath.rbegin(), RetPath.rend());
  631. SmallVector<unsigned, 4> TmpCallPath(CallPath.rbegin(), CallPath.rend());
  632. // Finally, we can check whether the value produced by the tail call at this
  633. // index is compatible with the value we return.
  634. if (!slotOnlyDiscardsData(RetVal, CallVal, TmpRetPath, TmpCallPath,
  635. AllowDifferingSizes, TLI,
  636. F->getParent()->getDataLayout()))
  637. return false;
  638. CallEmpty = !nextRealType(CallSubTypes, CallPath);
  639. } while(nextRealType(RetSubTypes, RetPath));
  640. return true;
  641. }
  642. static void collectEHScopeMembers(
  643. DenseMap<const MachineBasicBlock *, int> &EHScopeMembership, int EHScope,
  644. const MachineBasicBlock *MBB) {
  645. SmallVector<const MachineBasicBlock *, 16> Worklist = {MBB};
  646. while (!Worklist.empty()) {
  647. const MachineBasicBlock *Visiting = Worklist.pop_back_val();
  648. // Don't follow blocks which start new scopes.
  649. if (Visiting->isEHPad() && Visiting != MBB)
  650. continue;
  651. // Add this MBB to our scope.
  652. auto P = EHScopeMembership.insert(std::make_pair(Visiting, EHScope));
  653. // Don't revisit blocks.
  654. if (!P.second) {
  655. assert(P.first->second == EHScope && "MBB is part of two scopes!");
  656. continue;
  657. }
  658. // Returns are boundaries where scope transfer can occur, don't follow
  659. // successors.
  660. if (Visiting->isEHScopeReturnBlock())
  661. continue;
  662. append_range(Worklist, Visiting->successors());
  663. }
  664. }
  665. DenseMap<const MachineBasicBlock *, int>
  666. llvm::getEHScopeMembership(const MachineFunction &MF) {
  667. DenseMap<const MachineBasicBlock *, int> EHScopeMembership;
  668. // We don't have anything to do if there aren't any EH pads.
  669. if (!MF.hasEHScopes())
  670. return EHScopeMembership;
  671. int EntryBBNumber = MF.front().getNumber();
  672. bool IsSEH = isAsynchronousEHPersonality(
  673. classifyEHPersonality(MF.getFunction().getPersonalityFn()));
  674. const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
  675. SmallVector<const MachineBasicBlock *, 16> EHScopeBlocks;
  676. SmallVector<const MachineBasicBlock *, 16> UnreachableBlocks;
  677. SmallVector<const MachineBasicBlock *, 16> SEHCatchPads;
  678. SmallVector<std::pair<const MachineBasicBlock *, int>, 16> CatchRetSuccessors;
  679. for (const MachineBasicBlock &MBB : MF) {
  680. if (MBB.isEHScopeEntry()) {
  681. EHScopeBlocks.push_back(&MBB);
  682. } else if (IsSEH && MBB.isEHPad()) {
  683. SEHCatchPads.push_back(&MBB);
  684. } else if (MBB.pred_empty()) {
  685. UnreachableBlocks.push_back(&MBB);
  686. }
  687. MachineBasicBlock::const_iterator MBBI = MBB.getFirstTerminator();
  688. // CatchPads are not scopes for SEH so do not consider CatchRet to
  689. // transfer control to another scope.
  690. if (MBBI == MBB.end() || MBBI->getOpcode() != TII->getCatchReturnOpcode())
  691. continue;
  692. // FIXME: SEH CatchPads are not necessarily in the parent function:
  693. // they could be inside a finally block.
  694. const MachineBasicBlock *Successor = MBBI->getOperand(0).getMBB();
  695. const MachineBasicBlock *SuccessorColor = MBBI->getOperand(1).getMBB();
  696. CatchRetSuccessors.push_back(
  697. {Successor, IsSEH ? EntryBBNumber : SuccessorColor->getNumber()});
  698. }
  699. // We don't have anything to do if there aren't any EH pads.
  700. if (EHScopeBlocks.empty())
  701. return EHScopeMembership;
  702. // Identify all the basic blocks reachable from the function entry.
  703. collectEHScopeMembers(EHScopeMembership, EntryBBNumber, &MF.front());
  704. // All blocks not part of a scope are in the parent function.
  705. for (const MachineBasicBlock *MBB : UnreachableBlocks)
  706. collectEHScopeMembers(EHScopeMembership, EntryBBNumber, MBB);
  707. // Next, identify all the blocks inside the scopes.
  708. for (const MachineBasicBlock *MBB : EHScopeBlocks)
  709. collectEHScopeMembers(EHScopeMembership, MBB->getNumber(), MBB);
  710. // SEH CatchPads aren't really scopes, handle them separately.
  711. for (const MachineBasicBlock *MBB : SEHCatchPads)
  712. collectEHScopeMembers(EHScopeMembership, EntryBBNumber, MBB);
  713. // Finally, identify all the targets of a catchret.
  714. for (std::pair<const MachineBasicBlock *, int> CatchRetPair :
  715. CatchRetSuccessors)
  716. collectEHScopeMembers(EHScopeMembership, CatchRetPair.second,
  717. CatchRetPair.first);
  718. return EHScopeMembership;
  719. }