18a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky//===-- Analysis.cpp - CodeGen LLVM IR Analysis Utilities -----------------===// 25eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman// 35eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman// The LLVM Compiler Infrastructure 45eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman// 55eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman// This file is distributed under the University of Illinois Open Source 65eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman// License. See LICENSE.TXT for details. 75eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman// 85eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman//===----------------------------------------------------------------------===// 95eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman// 105eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman// This file defines several CodeGen-specific LLVM IR analysis utilties. 115eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman// 125eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman//===----------------------------------------------------------------------===// 135eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 145eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/CodeGen/Analysis.h" 15f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman#include "llvm/Analysis/ValueTracking.h" 165eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/DerivedTypes.h" 175eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/Function.h" 185eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/Instructions.h" 195eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/IntrinsicInst.h" 205eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/LLVMContext.h" 215eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/Module.h" 225eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/CodeGen/MachineFunction.h" 233d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng#include "llvm/CodeGen/SelectionDAG.h" 245eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/Target/TargetData.h" 255eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/Target/TargetLowering.h" 265eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/Target/TargetOptions.h" 275eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/Support/ErrorHandling.h" 285eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman#include "llvm/Support/MathExtras.h" 295eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohmanusing namespace llvm; 305eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 315eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence 325eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// of insertvalue or extractvalue indices that identify a member, return 335eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// the linearized index of the start of the member. 345eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// 35db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnerunsigned llvm::ComputeLinearIndex(Type *Ty, 365eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman const unsigned *Indices, 375eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman const unsigned *IndicesEnd, 385eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman unsigned CurIndex) { 395eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // Base case: We're done. 405eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (Indices && Indices == IndicesEnd) 415eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return CurIndex; 425eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 435eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // Given a struct type, recursively traverse the elements. 44db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (StructType *STy = dyn_cast<StructType>(Ty)) { 455eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman for (StructType::element_iterator EB = STy->element_begin(), 465eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman EI = EB, 475eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman EE = STy->element_end(); 485eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman EI != EE; ++EI) { 495eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (Indices && *Indices == unsigned(EI - EB)) 500dadb15927b912c98918e8a9e7466af77062149fDan Gohman return ComputeLinearIndex(*EI, Indices+1, IndicesEnd, CurIndex); 510dadb15927b912c98918e8a9e7466af77062149fDan Gohman CurIndex = ComputeLinearIndex(*EI, 0, 0, CurIndex); 525eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 535eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return CurIndex; 545eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 555eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // Given an array type, recursively traverse the elements. 56db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 57db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *EltTy = ATy->getElementType(); 585eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) { 595eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (Indices && *Indices == i) 600dadb15927b912c98918e8a9e7466af77062149fDan Gohman return ComputeLinearIndex(EltTy, Indices+1, IndicesEnd, CurIndex); 610dadb15927b912c98918e8a9e7466af77062149fDan Gohman CurIndex = ComputeLinearIndex(EltTy, 0, 0, CurIndex); 625eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 635eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return CurIndex; 645eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 655eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // We haven't found the type we're looking for, so keep searching. 665eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return CurIndex + 1; 675eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman} 685eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 695eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// ComputeValueVTs - Given an LLVM IR type, compute a sequence of 705eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// EVTs that represent all the individual underlying 715eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// non-aggregate types that comprise it. 725eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// 735eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// If Offsets is non-null, it points to a vector to be filled in 745eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// with the in-memory offsets of each of the individual values. 755eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// 76db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnervoid llvm::ComputeValueVTs(const TargetLowering &TLI, Type *Ty, 775eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman SmallVectorImpl<EVT> &ValueVTs, 785eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman SmallVectorImpl<uint64_t> *Offsets, 795eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman uint64_t StartingOffset) { 805eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // Given a struct type, recursively traverse the elements. 81db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (StructType *STy = dyn_cast<StructType>(Ty)) { 825eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman const StructLayout *SL = TLI.getTargetData()->getStructLayout(STy); 835eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman for (StructType::element_iterator EB = STy->element_begin(), 845eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman EI = EB, 855eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman EE = STy->element_end(); 865eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman EI != EE; ++EI) 875eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman ComputeValueVTs(TLI, *EI, ValueVTs, Offsets, 885eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman StartingOffset + SL->getElementOffset(EI - EB)); 895eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return; 905eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 915eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // Given an array type, recursively traverse the elements. 92db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 93db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *EltTy = ATy->getElementType(); 945eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman uint64_t EltSize = TLI.getTargetData()->getTypeAllocSize(EltTy); 955eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) 965eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman ComputeValueVTs(TLI, EltTy, ValueVTs, Offsets, 975eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman StartingOffset + i * EltSize); 985eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return; 995eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 1005eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // Interpret void as zero return values. 1015eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (Ty->isVoidTy()) 1025eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return; 1035eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // Base case: we can get an EVT for this LLVM IR type. 1045eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman ValueVTs.push_back(TLI.getValueType(Ty)); 1055eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (Offsets) 1065eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman Offsets->push_back(StartingOffset); 1075eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman} 1085eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 1095eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V. 1105eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan GohmanGlobalVariable *llvm::ExtractTypeInfo(Value *V) { 1115eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman V = V->stripPointerCasts(); 1125eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman GlobalVariable *GV = dyn_cast<GlobalVariable>(V); 1135eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 11423295cc1dd6dd42b999588f6de85cb52c9651165Bill Wendling if (GV && GV->getName() == "llvm.eh.catch.all.value") { 1155eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman assert(GV->hasInitializer() && 1165eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman "The EH catch-all value must have an initializer"); 1175eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman Value *Init = GV->getInitializer(); 1185eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman GV = dyn_cast<GlobalVariable>(Init); 1195eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (!GV) V = cast<ConstantPointerNull>(Init); 1205eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 1215eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 1225eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman assert((GV || isa<ConstantPointerNull>(V)) && 1235eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman "TypeInfo must be a global variable or NULL"); 1245eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return GV; 1255eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman} 1265eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 1275eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// hasInlineAsmMemConstraint - Return true if the inline asm instruction being 1285eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// processed uses a memory 'm' constraint. 1295eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohmanbool 13044ab89eb376af838d1123293a79975aede501464John Thompsonllvm::hasInlineAsmMemConstraint(InlineAsm::ConstraintInfoVector &CInfos, 1315eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman const TargetLowering &TLI) { 1325eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman for (unsigned i = 0, e = CInfos.size(); i != e; ++i) { 1335eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman InlineAsm::ConstraintInfo &CI = CInfos[i]; 1345eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman for (unsigned j = 0, ee = CI.Codes.size(); j != ee; ++j) { 1355eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman TargetLowering::ConstraintType CType = TLI.getConstraintType(CI.Codes[j]); 1365eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (CType == TargetLowering::C_Memory) 1375eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return true; 1385eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 1395eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 1405eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // Indirect operand accesses access memory. 1415eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (CI.isIndirect) 1425eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return true; 1435eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 1445eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 1455eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return false; 1465eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman} 1475eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 1485eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// getFCmpCondCode - Return the ISD condition code corresponding to 1495eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// the given LLVM IR floating-point condition code. This includes 1505eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// consideration of global floating-point math flags. 1515eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// 1525eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan GohmanISD::CondCode llvm::getFCmpCondCode(FCmpInst::Predicate Pred) { 1535eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman switch (Pred) { 1548a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_FALSE: return ISD::SETFALSE; 1558a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_OEQ: return ISD::SETOEQ; 1568a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_OGT: return ISD::SETOGT; 1578a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_OGE: return ISD::SETOGE; 1588a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_OLT: return ISD::SETOLT; 1598a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_OLE: return ISD::SETOLE; 1608a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_ONE: return ISD::SETONE; 1618a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_ORD: return ISD::SETO; 1628a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_UNO: return ISD::SETUO; 1638a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_UEQ: return ISD::SETUEQ; 1648a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_UGT: return ISD::SETUGT; 1658a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_UGE: return ISD::SETUGE; 1668a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_ULT: return ISD::SETULT; 1678a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_ULE: return ISD::SETULE; 1688a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_UNE: return ISD::SETUNE; 1698a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case FCmpInst::FCMP_TRUE: return ISD::SETTRUE; 1704d6ccb5f68cd7c6418a209f1fa4dbade569e4493David Blaikie default: llvm_unreachable("Invalid FCmp predicate opcode!"); 1718a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky } 1728a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky} 1738a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky 1748a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick LewyckyISD::CondCode llvm::getFCmpCodeWithoutNaN(ISD::CondCode CC) { 1758a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky switch (CC) { 1768a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case ISD::SETOEQ: case ISD::SETUEQ: return ISD::SETEQ; 1778a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case ISD::SETONE: case ISD::SETUNE: return ISD::SETNE; 1788a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case ISD::SETOLT: case ISD::SETULT: return ISD::SETLT; 1798a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case ISD::SETOLE: case ISD::SETULE: return ISD::SETLE; 1808a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case ISD::SETOGT: case ISD::SETUGT: return ISD::SETGT; 1818a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky case ISD::SETOGE: case ISD::SETUGE: return ISD::SETGE; 1824d6ccb5f68cd7c6418a209f1fa4dbade569e4493David Blaikie default: return CC; 1835eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 1845eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman} 1855eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 1865eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// getICmpCondCode - Return the ISD condition code corresponding to 1875eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// the given LLVM IR integer condition code. 1885eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// 1895eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan GohmanISD::CondCode llvm::getICmpCondCode(ICmpInst::Predicate Pred) { 1905eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman switch (Pred) { 1915eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman case ICmpInst::ICMP_EQ: return ISD::SETEQ; 1925eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman case ICmpInst::ICMP_NE: return ISD::SETNE; 1935eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman case ICmpInst::ICMP_SLE: return ISD::SETLE; 1945eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman case ICmpInst::ICMP_ULE: return ISD::SETULE; 1955eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman case ICmpInst::ICMP_SGE: return ISD::SETGE; 1965eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman case ICmpInst::ICMP_UGE: return ISD::SETUGE; 1975eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman case ICmpInst::ICMP_SLT: return ISD::SETLT; 1985eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman case ICmpInst::ICMP_ULT: return ISD::SETULT; 1995eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman case ICmpInst::ICMP_SGT: return ISD::SETGT; 2005eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman case ICmpInst::ICMP_UGT: return ISD::SETUGT; 2015eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman default: 2025eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman llvm_unreachable("Invalid ICmp predicate opcode!"); 2035eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 2045eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman} 2055eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 206cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner 207cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner/// getNoopInput - If V is a noop (i.e., lowers to no machine code), look 208cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner/// through it (and any transitive noop operands to it) and return its input 209cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner/// value. This is used to determine if a tail call can be formed. 210cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner/// 211cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattnerstatic const Value *getNoopInput(const Value *V, const TargetLowering &TLI) { 212cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner // If V is not an instruction, it can't be looked through. 2135b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner const Instruction *I = dyn_cast<Instruction>(V); 2145b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner if (I == 0 || !I->hasOneUse() || I->getNumOperands() == 0) return V; 215cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner 2165b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner Value *Op = I->getOperand(0); 2175b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner 218cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner // Look through truly no-op truncates. 2195b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner if (isa<TruncInst>(I) && 2205b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner TLI.isTruncateFree(I->getOperand(0)->getType(), I->getType())) 2215b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner return getNoopInput(I->getOperand(0), TLI); 222cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner 223cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner // Look through truly no-op bitcasts. 2245b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner if (isa<BitCastInst>(I)) { 2255b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner // No type change at all. 2265b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner if (Op->getType() == I->getType()) 2275b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner return getNoopInput(Op, TLI); 2285b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner 2295b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner // Pointer to pointer cast. 2305b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner if (Op->getType()->isPointerTy() && I->getType()->isPointerTy()) 2315b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner return getNoopInput(Op, TLI); 2325b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner 2335b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner if (isa<VectorType>(Op->getType()) && isa<VectorType>(I->getType()) && 2345b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner TLI.isTypeLegal(EVT::getEVT(Op->getType())) && 2355b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner TLI.isTypeLegal(EVT::getEVT(I->getType()))) 236cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner return getNoopInput(Op, TLI); 237cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner } 2385b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner 2395b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner // Look through inttoptr. 2405b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner if (isa<IntToPtrInst>(I) && !isa<VectorType>(I->getType())) { 2415b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner // Make sure this isn't a truncating or extending cast. We could support 2425b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner // this eventually, but don't bother for now. 2435b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner if (TLI.getPointerTy().getSizeInBits() == 2445b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner cast<IntegerType>(Op->getType())->getBitWidth()) 2455b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner return getNoopInput(Op, TLI); 2465b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner } 2475b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner 2485b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner // Look through ptrtoint. 2495b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner if (isa<PtrToIntInst>(I) && !isa<VectorType>(I->getType())) { 2505b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner // Make sure this isn't a truncating or extending cast. We could support 2515b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner // this eventually, but don't bother for now. 2525b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner if (TLI.getPointerTy().getSizeInBits() == 2535b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner cast<IntegerType>(I->getType())->getBitWidth()) 2545b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner return getNoopInput(Op, TLI); 2555b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner } 2565b0d9465375c4e175f5805038c5ef1d7d11193bdChris Lattner 257cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner 258cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner // Otherwise it's not something we can look through. 259cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner return V; 260cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner} 261cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner 262cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner 2635eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// Test if the given instruction is in a position to be optimized 2645eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// with a tail-call. This roughly means that it's in a block with 2655eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// a return and there's nothing that needs to be scheduled 2665eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// between it and the return. 2675eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// 2685eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman/// This function only tests target-independent requirements. 2695eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohmanbool llvm::isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr, 2705eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman const TargetLowering &TLI) { 2715eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman const Instruction *I = CS.getInstruction(); 2725eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman const BasicBlock *ExitBB = I->getParent(); 2735eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman const TerminatorInst *Term = ExitBB->getTerminator(); 2745eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman const ReturnInst *Ret = dyn_cast<ReturnInst>(Term); 2755eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 2765eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // The block must end in a return statement or unreachable. 2775eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // 2785eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // FIXME: Decline tailcall if it's not guaranteed and if the block ends in 2795eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // an unreachable, for now. The way tailcall optimization is currently 2805eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // implemented means it will add an epilogue followed by a jump. That is 2815eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // not profitable. Also, if the callee is a special function (e.g. 2825eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // longjmp on x86), it can end up causing miscompilation that has not 2835eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // been fully understood. 2845eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (!Ret && 2858a8d479214745c82ef00f08d4e4f1c173b5f9ce2Nick Lewycky (!TLI.getTargetMachine().Options.GuaranteedTailCallOpt || 286cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner !isa<UnreachableInst>(Term))) 287cd6015cc8a0da3981f298c2e92b145fe11e838e0Chris Lattner return false; 2885eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 2895eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // If I will have a chain, make sure no other instruction that will have a 2905eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // chain interposes between I and the return. 2915eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (I->mayHaveSideEffects() || I->mayReadFromMemory() || 292f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman !isSafeToSpeculativelyExecute(I)) 2935eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman for (BasicBlock::const_iterator BBI = prior(prior(ExitBB->end())); ; 2945eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman --BBI) { 2955eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (&*BBI == I) 2965eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman break; 2975eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // Debug info intrinsics do not get in the way of tail call optimization. 2985eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (isa<DbgInfoIntrinsic>(BBI)) 2995eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman continue; 3005eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() || 301f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman !isSafeToSpeculativelyExecute(BBI)) 3025eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return false; 3035eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman } 3045eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 3055eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // If the block ends with a void return or unreachable, it doesn't matter 3065eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // what the call's return type is. 3075eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (!Ret || Ret->getNumOperands() == 0) return true; 3085eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 3095eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // If the return value is undef, it doesn't matter what the call's 3105eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // return type is. 3115eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if (isa<UndefValue>(Ret->getOperand(0))) return true; 3125eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 3135eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // Conservatively require the attributes of the call to match those of 3145eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // the return. Ignore noalias because it doesn't affect the call sequence. 3159344f97108b9d5c8a5d7070d5393f107475aead0Evan Cheng const Function *F = ExitBB->getParent(); 316164b86b4399559e45fab7846f1e3e09119cab4e2Kostya Serebryany Attributes CallerRetAttr = F->getAttributes().getRetAttributes(); 3175eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if ((CalleeRetAttr ^ CallerRetAttr) & ~Attribute::NoAlias) 3185eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return false; 3195eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 3205eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // It's not safe to eliminate the sign / zero extension of the return value. 3215eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) 3225eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman return false; 3235eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 3245eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman // Otherwise, make sure the unmodified return value of I is the return value. 325f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner // We handle two cases: multiple return values + scalars. 326f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner Value *RetVal = Ret->getOperand(0); 327f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner if (!isa<InsertValueInst>(RetVal) || !isa<StructType>(RetVal->getType())) 328f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner // Handle scalars first. 329f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner return getNoopInput(Ret->getOperand(0), TLI) == I; 330f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner 331f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner // If this is an aggregate return, look through the insert/extract values and 332f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner // see if each is transparent. 333f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner for (unsigned i = 0, e =cast<StructType>(RetVal->getType())->getNumElements(); 334f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner i != e; ++i) { 33574ee0ef6a72c61766523364f7c300c2a2612aae7Chris Lattner const Value *InScalar = FindInsertedValue(RetVal, i); 33674ee0ef6a72c61766523364f7c300c2a2612aae7Chris Lattner if (InScalar == 0) return false; 33774ee0ef6a72c61766523364f7c300c2a2612aae7Chris Lattner InScalar = getNoopInput(InScalar, TLI); 338f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner 339f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner // If the scalar value being inserted is an extractvalue of the right index 340f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner // from the call, then everything is good. 341f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(InScalar); 342f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner if (EVI == 0 || EVI->getOperand(0) != I || EVI->getNumIndices() != 1 || 343f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner EVI->getIndices()[0] != i) 344f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner return false; 345f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner } 346f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner 347f59e4e34528a078c2db57ee72b2814b495989124Chris Lattner return true; 3485eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman} 3495eb6d65a27fd77a0bf10bd49f5cccb9f1796d98bDan Gohman 3503d2125c9dbac695c93f42c0f59fd040e413fd711Evan Chengbool llvm::isInTailCallPosition(SelectionDAG &DAG, SDNode *Node, 351bf010eb9110009d745382bf15131fbe556562ffeEvan Cheng SDValue &Chain, const TargetLowering &TLI) { 3523d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng const Function *F = DAG.getMachineFunction().getFunction(); 3533d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng 3543d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng // Conservatively require the attributes of the call to match those of 3553d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng // the return. Ignore noalias because it doesn't affect the call sequence. 356164b86b4399559e45fab7846f1e3e09119cab4e2Kostya Serebryany Attributes CallerRetAttr = F->getAttributes().getRetAttributes(); 3573d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng if (CallerRetAttr & ~Attribute::NoAlias) 3583d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng return false; 3593d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng 3603d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng // It's not safe to eliminate the sign / zero extension of the return value. 3613d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) 3623d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng return false; 3633d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng 3643d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng // Check if the only use is a function return node. 365bf010eb9110009d745382bf15131fbe556562ffeEvan Cheng return TLI.isUsedByReturnOnly(Node, Chain); 3663d2125c9dbac695c93f42c0f59fd040e413fd711Evan Cheng} 367