aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis')
-rw-r--r--lib/Analysis/BranchProbabilityInfo.cpp32
-rw-r--r--lib/Analysis/ConstantFolding.cpp35
-rw-r--r--lib/Analysis/InlineCost.cpp30
-rw-r--r--lib/Analysis/InstructionSimplify.cpp28
-rw-r--r--lib/Analysis/MemoryBuiltins.cpp39
-rw-r--r--lib/Analysis/MemoryDependenceAnalysis.cpp9
-rw-r--r--lib/Analysis/RegionInfo.cpp16
-rw-r--r--lib/Analysis/ScalarEvolution.cpp6
8 files changed, 144 insertions, 51 deletions
diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp
index 2730ce6..b255ce6 100644
--- a/lib/Analysis/BranchProbabilityInfo.cpp
+++ b/lib/Analysis/BranchProbabilityInfo.cpp
@@ -1,4 +1,4 @@
-//===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -*- C++ -*-===//
+//===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -----------===//
//
// The LLVM Compiler Infrastructure
//
@@ -78,6 +78,19 @@ static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
static const uint32_t FPH_TAKEN_WEIGHT = 20;
static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
+/// \brief Invoke-terminating normal branch taken weight
+///
+/// This is the weight for branching to the normal destination of an invoke
+/// instruction. We expect this to happen most of the time. Set the weight to an
+/// absurdly high value so that nested loops subsume it.
+static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
+
+/// \brief Invoke-terminating normal branch not-taken weight.
+///
+/// This is the weight for branching to the unwind destination of an invoke
+/// instruction. This is essentially never taken.
+static const uint32_t IH_NONTAKEN_WEIGHT = 1;
+
// Standard weight value. Used when none of the heuristics set weight for
// the edge.
static const uint32_t NORMAL_WEIGHT = 16;
@@ -371,6 +384,19 @@ bool BranchProbabilityInfo::calcFloatingPointHeuristics(BasicBlock *BB) {
return true;
}
+bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) {
+ InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
+ if (!II)
+ return false;
+
+ BasicBlock *Normal = II->getNormalDest();
+ BasicBlock *Unwind = II->getUnwindDest();
+
+ setEdgeWeight(BB, Normal, IH_TAKEN_WEIGHT);
+ setEdgeWeight(BB, Unwind, IH_NONTAKEN_WEIGHT);
+ return true;
+}
+
void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<LoopInfo>();
AU.setPreservesAll();
@@ -397,7 +423,9 @@ bool BranchProbabilityInfo::runOnFunction(Function &F) {
continue;
if (calcZeroHeuristics(*I))
continue;
- calcFloatingPointHeuristics(*I);
+ if (calcFloatingPointHeuristics(*I))
+ continue;
+ calcInvokeHeuristics(*I);
}
PostDominatedByUnreachable.clear();
diff --git a/lib/Analysis/ConstantFolding.cpp b/lib/Analysis/ConstantFolding.cpp
index 7ced848..f5e619c 100644
--- a/lib/Analysis/ConstantFolding.cpp
+++ b/lib/Analysis/ConstantFolding.cpp
@@ -358,17 +358,20 @@ static bool ReadDataFromGlobal(Constant *C, uint64_t ByteOffset,
NumElts = AT->getNumElements();
else
NumElts = cast<VectorType>(C->getType())->getNumElements();
-
+
for (; Index != NumElts; ++Index) {
if (!ReadDataFromGlobal(C->getAggregateElement(Index), Offset, CurPtr,
BytesLeft, TD))
return false;
- if (EltSize >= BytesLeft)
+
+ uint64_t BytesWritten = EltSize - Offset;
+ assert(BytesWritten <= EltSize && "Not indexing into this element?");
+ if (BytesWritten >= BytesLeft)
return true;
-
+
Offset = 0;
- BytesLeft -= EltSize;
- CurPtr += EltSize;
+ BytesLeft -= BytesWritten;
+ CurPtr += BytesWritten;
}
return true;
}
@@ -600,6 +603,22 @@ static Constant *CastGEPIndices(ArrayRef<Constant *> Ops,
return C;
}
+/// Strip the pointer casts, but preserve the address space information.
+static Constant* StripPtrCastKeepAS(Constant* Ptr) {
+ assert(Ptr->getType()->isPointerTy() && "Not a pointer type");
+ PointerType *OldPtrTy = cast<PointerType>(Ptr->getType());
+ Ptr = cast<Constant>(Ptr->stripPointerCasts());
+ PointerType *NewPtrTy = cast<PointerType>(Ptr->getType());
+
+ // Preserve the address space number of the pointer.
+ if (NewPtrTy->getAddressSpace() != OldPtrTy->getAddressSpace()) {
+ NewPtrTy = NewPtrTy->getElementType()->getPointerTo(
+ OldPtrTy->getAddressSpace());
+ Ptr = ConstantExpr::getBitCast(Ptr, NewPtrTy);
+ }
+ return Ptr;
+}
+
/// SymbolicallyEvaluateGEP - If we can symbolically evaluate the specified GEP
/// constant expression, do so.
static Constant *SymbolicallyEvaluateGEP(ArrayRef<Constant *> Ops,
@@ -636,13 +655,13 @@ static Constant *SymbolicallyEvaluateGEP(ArrayRef<Constant *> Ops,
}
return 0;
}
-
+
unsigned BitWidth = TD->getTypeSizeInBits(IntPtrTy);
APInt Offset =
APInt(BitWidth, TD->getIndexedOffset(Ptr->getType(),
makeArrayRef((Value **)Ops.data() + 1,
Ops.size() - 1)));
- Ptr = cast<Constant>(Ptr->stripPointerCasts());
+ Ptr = StripPtrCastKeepAS(Ptr);
// If this is a GEP of a GEP, fold it all into a single GEP.
while (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) {
@@ -661,7 +680,7 @@ static Constant *SymbolicallyEvaluateGEP(ArrayRef<Constant *> Ops,
Ptr = cast<Constant>(GEP->getOperand(0));
Offset += APInt(BitWidth,
TD->getIndexedOffset(Ptr->getType(), NestedOps));
- Ptr = cast<Constant>(Ptr->stripPointerCasts());
+ Ptr = StripPtrCastKeepAS(Ptr);
}
// If the base value for this address is a literal integer value, fold the
diff --git a/lib/Analysis/InlineCost.cpp b/lib/Analysis/InlineCost.cpp
index a6bf4a8..bc1ecd2 100644
--- a/lib/Analysis/InlineCost.cpp
+++ b/lib/Analysis/InlineCost.cpp
@@ -797,9 +797,33 @@ bool CallAnalyzer::analyzeCall(CallSite CS) {
FiftyPercentVectorBonus = Threshold;
TenPercentVectorBonus = Threshold / 2;
- // Subtract off one instruction per call argument as those will be free after
- // inlining.
- Cost -= CS.arg_size() * InlineConstants::InstrCost;
+ // Give out bonuses per argument, as the instructions setting them up will
+ // be gone after inlining.
+ for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) {
+ if (TD && CS.isByValArgument(I)) {
+ // We approximate the number of loads and stores needed by dividing the
+ // size of the byval type by the target's pointer size.
+ PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType());
+ unsigned TypeSize = TD->getTypeSizeInBits(PTy->getElementType());
+ unsigned PointerSize = TD->getPointerSizeInBits();
+ // Ceiling division.
+ unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize;
+
+ // If it generates more than 8 stores it is likely to be expanded as an
+ // inline memcpy so we take that as an upper bound. Otherwise we assume
+ // one load and one store per word copied.
+ // FIXME: The maxStoresPerMemcpy setting from the target should be used
+ // here instead of a magic number of 8, but it's not available via
+ // TargetData.
+ NumStores = std::min(NumStores, 8U);
+
+ Cost -= 2 * NumStores * InlineConstants::InstrCost;
+ } else {
+ // For non-byval arguments subtract off one instruction per call
+ // argument.
+ Cost -= InlineConstants::InstrCost;
+ }
+ }
// If there is only one call of the function, and it has internal linkage,
// the cost of inlining it drops dramatically.
diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp
index 16a9a04..379a35a 100644
--- a/lib/Analysis/InstructionSimplify.cpp
+++ b/lib/Analysis/InstructionSimplify.cpp
@@ -1719,10 +1719,13 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
return ConstantInt::get(ITy, false);
// A local identified object (alloca or noalias call) can't equal any
- // incoming argument, unless they're both null.
- if (isa<Instruction>(LHSPtr) && isa<Argument>(RHSPtr) &&
- Pred == CmpInst::ICMP_EQ)
- return ConstantInt::get(ITy, false);
+ // incoming argument, unless they're both null or they belong to
+ // different functions. The latter happens during inlining.
+ if (Instruction *LHSInst = dyn_cast<Instruction>(LHSPtr))
+ if (Argument *RHSArg = dyn_cast<Argument>(RHSPtr))
+ if (LHSInst->getParent()->getParent() == RHSArg->getParent() &&
+ Pred == CmpInst::ICMP_EQ)
+ return ConstantInt::get(ITy, false);
}
// Assume that the constant null is on the right.
@@ -1732,14 +1735,17 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
else if (Pred == CmpInst::ICMP_NE)
return ConstantInt::get(ITy, true);
}
- } else if (isa<Argument>(LHSPtr)) {
+ } else if (Argument *LHSArg = dyn_cast<Argument>(LHSPtr)) {
RHSPtr = RHSPtr->stripInBoundsOffsets();
- // An alloca can't be equal to an argument.
- if (isa<AllocaInst>(RHSPtr)) {
- if (Pred == CmpInst::ICMP_EQ)
- return ConstantInt::get(ITy, false);
- else if (Pred == CmpInst::ICMP_NE)
- return ConstantInt::get(ITy, true);
+ // An alloca can't be equal to an argument unless they come from separate
+ // functions via inlining.
+ if (AllocaInst *RHSInst = dyn_cast<AllocaInst>(RHSPtr)) {
+ if (LHSArg->getParent() == RHSInst->getParent()->getParent()) {
+ if (Pred == CmpInst::ICMP_EQ)
+ return ConstantInt::get(ITy, false);
+ else if (Pred == CmpInst::ICMP_NE)
+ return ConstantInt::get(ITy, true);
+ }
}
}
diff --git a/lib/Analysis/MemoryBuiltins.cpp b/lib/Analysis/MemoryBuiltins.cpp
index 8d99ec3..b986b32 100644
--- a/lib/Analysis/MemoryBuiltins.cpp
+++ b/lib/Analysis/MemoryBuiltins.cpp
@@ -64,7 +64,7 @@ static const AllocFnsTy AllocationFnData[] = {
{"realloc", ReallocLike, 2, 1, -1},
{"reallocf", ReallocLike, 2, 1, -1},
{"strdup", StrDupLike, 1, -1, -1},
- {"strndup", StrDupLike, 2, -1, -1}
+ {"strndup", StrDupLike, 2, 1, -1}
};
@@ -358,11 +358,16 @@ ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const TargetData *TD,
SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) {
V = V->stripPointerCasts();
+ if (Instruction *I = dyn_cast<Instruction>(V)) {
+ // If we have already seen this instruction, bail out. Cycles can happen in
+ // unreachable code after constant propagation.
+ if (!SeenInsts.insert(I))
+ return unknown();
- if (GEPOperator *GEP = dyn_cast<GEPOperator>(V))
- return visitGEPOperator(*GEP);
- if (Instruction *I = dyn_cast<Instruction>(V))
+ if (GEPOperator *GEP = dyn_cast<GEPOperator>(V))
+ return visitGEPOperator(*GEP);
return visit(*I);
+ }
if (Argument *A = dyn_cast<Argument>(V))
return visitArgument(*A);
if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))
@@ -371,9 +376,12 @@ SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) {
return visitGlobalVariable(*GV);
if (UndefValue *UV = dyn_cast<UndefValue>(V))
return visitUndefValue(*UV);
- if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
+ if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
if (CE->getOpcode() == Instruction::IntToPtr)
return unknown(); // clueless
+ if (CE->getOpcode() == Instruction::GetElementPtr)
+ return visitGEPOperator(cast<GEPOperator>(*CE));
+ }
DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V
<< '\n');
@@ -414,8 +422,21 @@ SizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) {
// handle strdup-like functions separately
if (FnData->AllocTy == StrDupLike) {
- // TODO
- return unknown();
+ APInt Size(IntTyBits, GetStringLength(CS.getArgument(0)));
+ if (!Size)
+ return unknown();
+
+ // strndup limits strlen
+ if (FnData->FstParam > 0) {
+ ConstantInt *Arg= dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
+ if (!Arg)
+ return unknown();
+
+ APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits);
+ if (Size.ugt(MaxSize))
+ Size = MaxSize + 1;
+ }
+ return std::make_pair(Size, Zero);
}
ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
@@ -512,8 +533,7 @@ SizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) {
ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(const TargetData *TD,
LLVMContext &Context)
-: TD(TD), Context(Context), Builder(Context, TargetFolder(TD)),
-Visitor(TD, Context) {
+: TD(TD), Context(Context), Builder(Context, TargetFolder(TD)) {
IntTy = TD->getIntPtrType(Context);
Zero = ConstantInt::get(IntTy, 0);
}
@@ -538,6 +558,7 @@ SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) {
}
SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) {
+ ObjectSizeOffsetVisitor Visitor(TD, Context);
SizeOffsetType Const = Visitor.compute(V);
if (Visitor.bothKnown(Const))
return std::make_pair(ConstantInt::get(Context, Const.first),
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 7fb154d..059e574 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -227,13 +227,18 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
// Otherwise if the two calls don't interact (e.g. InstCS is readnone)
// keep scanning.
- break;
+ continue;
default:
return MemDepResult::getClobber(Inst);
}
}
+
+ // If we could not obtain a pointer for the instruction and the instruction
+ // touches memory then assume that this is a dependency.
+ if (MR != AliasAnalysis::NoModRef)
+ return MemDepResult::getClobber(Inst);
}
-
+
// No dependence found. If this is the entry block of the function, it is
// unknown, otherwise it is non-local.
if (BB != &BB->getParent()->getEntryBlock())
diff --git a/lib/Analysis/RegionInfo.cpp b/lib/Analysis/RegionInfo.cpp
index 5f4458b..868f483 100644
--- a/lib/Analysis/RegionInfo.cpp
+++ b/lib/Analysis/RegionInfo.cpp
@@ -262,22 +262,6 @@ Region::const_block_node_iterator Region::block_node_end() const {
return GraphTraits<FlatIt<const Region*> >::nodes_end(this);
}
-Region::block_iterator Region::block_begin() {
- return block_node_begin();
-}
-
-Region::block_iterator Region::block_end() {
- return block_node_end();
-}
-
-Region::const_block_iterator Region::block_begin() const {
- return block_node_begin();
-}
-
-Region::const_block_iterator Region::block_end() const {
- return block_node_end();
-}
-
Region::element_iterator Region::element_begin() {
return GraphTraits<Region*>::nodes_begin(this);
}
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index f0f3b1c..a654648 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -5370,6 +5370,12 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
SqrtTerm *= B;
SqrtTerm -= Four * (A * C);
+ if (SqrtTerm.isNegative()) {
+ // The loop is provably infinite.
+ const SCEV *CNC = SE.getCouldNotCompute();
+ return std::make_pair(CNC, CNC);
+ }
+
// Compute sqrt(B^2-4ac). This is guaranteed to be the nearest
// integer value or else APInt::sqrt() will assert.
APInt SqrtVal(SqrtTerm.sqrt());
generated by cgit v1.1 at 2025-11-10 21:58:42 +0000