//
//===----------------------------------------------------------------------===//
//
-// This file defines several CodeGen-specific LLVM IR analysis utilties.
+// This file defines several CodeGen-specific LLVM IR analysis utilities.
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/Analysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Target/TargetLowering.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
+#include "llvm/Transforms/Utils/GlobalStatus.h"
+
using namespace llvm;
-/// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence
-/// of insertvalue or extractvalue indices that identify a member, return
-/// the linearized index of the start of the member.
-///
+/// Compute the linearized index of a member in a nested aggregate/struct/array
+/// by recursing and accumulating CurIndex as long as there are indices in the
+/// index list.
unsigned llvm::ComputeLinearIndex(Type *Ty,
const unsigned *Indices,
const unsigned *IndicesEnd,
EI != EE; ++EI) {
if (Indices && *Indices == unsigned(EI - EB))
return ComputeLinearIndex(*EI, Indices+1, IndicesEnd, CurIndex);
- CurIndex = ComputeLinearIndex(*EI, 0, 0, CurIndex);
+ CurIndex = ComputeLinearIndex(*EI, nullptr, nullptr, CurIndex);
}
+ assert(!Indices && "Unexpected out of bound");
return CurIndex;
}
// Given an array type, recursively traverse the elements.
else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
Type *EltTy = ATy->getElementType();
- for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) {
- if (Indices && *Indices == i)
- return ComputeLinearIndex(EltTy, Indices+1, IndicesEnd, CurIndex);
- CurIndex = ComputeLinearIndex(EltTy, 0, 0, CurIndex);
+ unsigned NumElts = ATy->getNumElements();
+ // Compute the Linear offset when jumping one element of the array
+ unsigned EltLinearOffset = ComputeLinearIndex(EltTy, nullptr, nullptr, 0);
+ if (Indices) {
+ assert(*Indices < NumElts && "Unexpected out of bound");
+ // If the indice is inside the array, compute the index to the requested
+ // elt and recurse inside the element with the end of the indices list
+ CurIndex += EltLinearOffset* *Indices;
+ return ComputeLinearIndex(EltTy, Indices+1, IndicesEnd, CurIndex);
}
+ CurIndex += EltLinearOffset*NumElts;
return CurIndex;
}
// We haven't found the type we're looking for, so keep searching.
}
/// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V.
-GlobalVariable *llvm::ExtractTypeInfo(Value *V) {
+GlobalValue *llvm::ExtractTypeInfo(Value *V) {
V = V->stripPointerCasts();
- GlobalVariable *GV = dyn_cast<GlobalVariable>(V);
+ GlobalValue *GV = dyn_cast<GlobalValue>(V);
+ GlobalVariable *Var = dyn_cast<GlobalVariable>(V);
- if (GV && GV->getName() == "llvm.eh.catch.all.value") {
- assert(GV->hasInitializer() &&
+ if (Var && Var->getName() == "llvm.eh.catch.all.value") {
+ assert(Var->hasInitializer() &&
"The EH catch-all value must have an initializer");
- Value *Init = GV->getInitializer();
- GV = dyn_cast<GlobalVariable>(Init);
+ Value *Init = Var->getInitializer();
+ GV = dyn_cast<GlobalValue>(Init);
if (!GV) V = cast<ConstantPointerNull>(Init);
}
// through.
const Instruction *I = dyn_cast<Instruction>(V);
if (!I || I->getNumOperands() == 0) return V;
- const Value *NoopInput = 0;
+ const Value *NoopInput = nullptr;
Value *Op = I->getOperand(0);
if (isa<BitCastInst>(I)) {
static bool slotOnlyDiscardsData(const Value *RetVal, const Value *CallVal,
SmallVectorImpl<unsigned> &RetIndices,
SmallVectorImpl<unsigned> &CallIndices,
+ bool AllowDifferingSizes,
const TargetLoweringBase &TLI) {
// Trace the sub-value needed by the return value as far back up the graph as
// all the bits that are needed by the "ret" have been provided by the "tail
// call". FIXME: with sufficiently cunning bit-tracking, we could look through
// extensions too.
- if (BitsProvided < BitsRequired)
+ if (BitsProvided < BitsRequired ||
+ (!AllowDifferingSizes && BitsProvided != BitsRequired))
return false;
return true;
/// function again on a finished iterator will repeatedly return
/// false. SubTypes.back()->getTypeAtIndex(Path.back()) is either an empty
/// aggregate or a non-aggregate
-static bool
-advanceToNextLeafType(SmallVectorImpl<CompositeType *> &SubTypes,
- SmallVectorImpl<unsigned> &Path) {
+static bool advanceToNextLeafType(SmallVectorImpl<CompositeType *> &SubTypes,
+ SmallVectorImpl<unsigned> &Path) {
// First march back up the tree until we can successfully increment one of the
// coordinates in Path.
while (!Path.empty() && !indexReallyValid(SubTypes.back(), Path.back() + 1)) {
/// Set the iterator data-structures to the next non-empty, non-aggregate
/// subtype.
-bool nextRealType(SmallVectorImpl<CompositeType *> &SubTypes,
- SmallVectorImpl<unsigned> &Path) {
+static bool nextRealType(SmallVectorImpl<CompositeType *> &SubTypes,
+ SmallVectorImpl<unsigned> &Path) {
do {
if (!advanceToNextLeafType(SubTypes, Path))
return false;
/// between it and the return.
///
/// This function only tests target-independent requirements.
-bool llvm::isInTailCallPosition(ImmutableCallSite CS,
- const TargetLowering &TLI) {
+bool llvm::isInTailCallPosition(ImmutableCallSite CS, const TargetMachine &TM) {
const Instruction *I = CS.getInstruction();
const BasicBlock *ExitBB = I->getParent();
const TerminatorInst *Term = ExitBB->getTerminator();
// longjmp on x86), it can end up causing miscompilation that has not
// been fully understood.
if (!Ret &&
- (!TLI.getTargetMachine().Options.GuaranteedTailCallOpt ||
- !isa<UnreachableInst>(Term)))
+ (!TM.Options.GuaranteedTailCallOpt || !isa<UnreachableInst>(Term)))
return false;
// If I will have a chain, make sure no other instruction that will have a
// chain interposes between I and the return.
if (I->mayHaveSideEffects() || I->mayReadFromMemory() ||
!isSafeToSpeculativelyExecute(I))
- for (BasicBlock::const_iterator BBI = prior(prior(ExitBB->end())); ;
- --BBI) {
+ for (BasicBlock::const_iterator BBI = std::prev(ExitBB->end(), 2);; --BBI) {
if (&*BBI == I)
break;
// Debug info intrinsics do not get in the way of tail call optimization.
return false;
}
+ return returnTypeIsEligibleForTailCall(
+ ExitBB->getParent(), I, Ret, *TM.getSubtargetImpl()->getTargetLowering());
+}
+
+bool llvm::returnTypeIsEligibleForTailCall(const Function *F,
+ const Instruction *I,
+ const ReturnInst *Ret,
+ const TargetLoweringBase &TLI) {
// If the block ends with a void return or unreachable, it doesn't matter
// what the call's return type is.
if (!Ret || Ret->getNumOperands() == 0) return true;
// return type is.
if (isa<UndefValue>(Ret->getOperand(0))) return true;
- // Conservatively require the attributes of the call to match those of
- // the return. Ignore noalias because it doesn't affect the call sequence.
- const Function *F = ExitBB->getParent();
- AttributeSet CallerAttrs = F->getAttributes();
- if (AttrBuilder(CallerAttrs, AttributeSet::ReturnIndex).
- removeAttribute(Attribute::NoAlias) !=
- AttrBuilder(CallerAttrs, AttributeSet::ReturnIndex).
- removeAttribute(Attribute::NoAlias))
- return false;
+ // Make sure the attributes attached to each return are compatible.
+ AttrBuilder CallerAttrs(F->getAttributes(),
+ AttributeSet::ReturnIndex);
+ AttrBuilder CalleeAttrs(cast<CallInst>(I)->getAttributes(),
+ AttributeSet::ReturnIndex);
+
+ // Noalias is completely benign as far as calling convention goes, it
+ // shouldn't affect whether the call is a tail call.
+ CallerAttrs = CallerAttrs.removeAttribute(Attribute::NoAlias);
+ CalleeAttrs = CalleeAttrs.removeAttribute(Attribute::NoAlias);
+
+ bool AllowDifferingSizes = true;
+ if (CallerAttrs.contains(Attribute::ZExt)) {
+ if (!CalleeAttrs.contains(Attribute::ZExt))
+ return false;
+
+ AllowDifferingSizes = false;
+ CallerAttrs.removeAttribute(Attribute::ZExt);
+ CalleeAttrs.removeAttribute(Attribute::ZExt);
+ } else if (CallerAttrs.contains(Attribute::SExt)) {
+ if (!CalleeAttrs.contains(Attribute::SExt))
+ return false;
+
+ AllowDifferingSizes = false;
+ CallerAttrs.removeAttribute(Attribute::SExt);
+ CalleeAttrs.removeAttribute(Attribute::SExt);
+ }
- // It's not safe to eliminate the sign / zero extension of the return value.
- if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) ||
- CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt))
+ // If they're still different, there's some facet we don't understand
+ // (currently only "inreg", but in future who knows). It may be OK but the
+ // only safe option is to reject the tail call.
+ if (CallerAttrs != CalleeAttrs)
return false;
const Value *RetVal = Ret->getOperand(0), *CallVal = I;
// Finally, we can check whether the value produced by the tail call at this
// index is compatible with the value we return.
- if (!slotOnlyDiscardsData(RetVal, CallVal, TmpRetPath, TmpCallPath, TLI))
+ if (!slotOnlyDiscardsData(RetVal, CallVal, TmpRetPath, TmpCallPath,
+ AllowDifferingSizes, TLI))
return false;
CallEmpty = !nextRealType(CallSubTypes, CallPath);
return true;
}
+
+bool llvm::canBeOmittedFromSymbolTable(const GlobalValue *GV) {
+ if (!GV->hasLinkOnceODRLinkage())
+ return false;
+
+ if (GV->hasUnnamedAddr())
+ return true;
+
+ // If it is a non constant variable, it needs to be uniqued across shared
+ // objects.
+ if (const GlobalVariable *Var = dyn_cast<GlobalVariable>(GV)) {
+ if (!Var->isConstant())
+ return false;
+ }
+
+ // An alias can point to a variable. We could try to resolve the alias to
+ // decide, but for now just don't hide them.
+ if (isa<GlobalAlias>(GV))
+ return false;
+
+ GlobalStatus GS;
+ if (GlobalStatus::analyzeGlobal(GV, GS))
+ return false;
+
+ return !GS.IsCompared;
+}