From 26e46f2283043c805e3682f3009f67fbaaf5706c Mon Sep 17 00:00:00 2001 From: Diego Novillo Date: Wed, 6 May 2015 17:55:11 +0000 Subject: [PATCH] Allow 0-weight branches in BranchProbabilityInfo. Summary: When computing branch weights in BPI, we used to disallow branches with weight 0. This is a minor nuisance, because a branch with weight 0 is different to "don't have information". In the context of instrumentation, it may mean "never executed", in the context of sampling, it means "never or seldom executed". In allowing 0 weight branches, I ran into issues with the switch expansion code in selection DAG. It is currently hardwired to not handle branches with weight 0. To maintain the current behaviour, I changed it to use 1 when it finds 0, but perhaps the algorithm needs changes to tolerate branches with weight zero. Reviewers: hansw Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9533 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@236617 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/BranchProbabilityInfo.cpp | 12 +++++++----- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 6 +++++- test/Transforms/SampleProfile/branch.ll | 12 ++++++------ test/Transforms/SampleProfile/calls.ll | 8 ++++---- test/Transforms/SampleProfile/propagate.ll | 8 ++++---- 5 files changed, 26 insertions(+), 20 deletions(-) diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index 036da5f16eb..4591eb3bf41 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -201,8 +201,7 @@ bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) { mdconst::dyn_extract(WeightsNode->getOperand(i)); if (!Weight) return false; - Weights.push_back( - std::max(1, Weight->getLimitedValue(WeightLimit))); + Weights.push_back(Weight->getLimitedValue(WeightLimit)); } assert(Weights.size() == TI->getNumSuccessors() && "Checked above"); for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) @@ -553,7 +552,7 @@ uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const { uint32_t PrevSum = Sum; Sum += Weight; - assert(Sum > PrevSum); (void) PrevSum; + assert(Sum >= PrevSum); (void) PrevSum; } return Sum; @@ -616,14 +615,17 @@ uint32_t BranchProbabilityInfo::getEdgeWeight(const BasicBlock *Src, uint32_t BranchProbabilityInfo:: getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const { uint32_t Weight = 0; + bool FoundWeight = false; DenseMap::const_iterator MapI; for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I) if (*I == Dst) { MapI = Weights.find(std::make_pair(Src, I.getSuccessorIndex())); - if (MapI != Weights.end()) + if (MapI != Weights.end()) { + FoundWeight = true; Weight += MapI->second; + } } - return (Weight == 0) ? DEFAULT_WEIGHT : Weight; + return (!FoundWeight) ? DEFAULT_WEIGHT : Weight; } /// Set the edge weight for a given edge specified by PredBlock and an index diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index d0bda11eb05..fe96f33d772 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -8009,7 +8009,11 @@ void SelectionDAGBuilder::visitSwitch(const SwitchInst &SI) { const ConstantInt *CaseVal = I.getCaseValue(); uint32_t Weight = 1; if (BPI) { - Weight = BPI->getEdgeWeight(SI.getParent(), I.getSuccessorIndex()); + // TODO - BPI used to guarantee non-zero weights, but this produces + // information loss (see PR 22718). Since we can't handle zero weights + // here, use the same flooring mechanism previously used by BPI. + Weight = std::max( + 1u, BPI->getEdgeWeight(SI.getParent(), I.getSuccessorIndex())); assert(Weight <= UINT32_MAX / SI.getNumSuccessors()); } Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Weight)); diff --git a/test/Transforms/SampleProfile/branch.ll b/test/Transforms/SampleProfile/branch.ll index aeb367132aa..25bd455a044 100644 --- a/test/Transforms/SampleProfile/branch.ll +++ b/test/Transforms/SampleProfile/branch.ll @@ -36,8 +36,8 @@ entry: tail call void @llvm.dbg.value(metadata i8** %argv, i64 0, metadata !14, metadata !DIExpression()), !dbg !27 %cmp = icmp slt i32 %argc, 2, !dbg !28 br i1 %cmp, label %return, label %if.end, !dbg !28 -; CHECK: edge entry -> return probability is 1 / 2 = 50% -; CHECK: edge entry -> if.end probability is 1 / 2 = 50% +; CHECK: edge entry -> return probability is 0 / 1 = 0% +; CHECK: edge entry -> if.end probability is 1 / 1 = 100% if.end: ; preds = %entry %arrayidx = getelementptr inbounds i8*, i8** %argv, i64 1, !dbg !30 @@ -46,8 +46,8 @@ if.end: ; preds = %entry tail call void @llvm.dbg.value(metadata i32 %call, i64 0, metadata !17, metadata !DIExpression()), !dbg !30 %cmp1 = icmp sgt i32 %call, 100, !dbg !35 br i1 %cmp1, label %for.body, label %if.end6, !dbg !35 -; CHECK: edge if.end -> for.body probability is 1 / 2 = 50% -; CHECK: edge if.end -> if.end6 probability is 1 / 2 = 50% +; CHECK: edge if.end -> for.body probability is 0 / 1 = 0% +; CHECK: edge if.end -> if.end6 probability is 1 / 1 = 100% for.body: ; preds = %if.end, %for.body %u.016 = phi i32 [ %inc, %for.body ], [ 0, %if.end ] @@ -65,8 +65,8 @@ for.body: ; preds = %if.end, %for.body tail call void @llvm.dbg.value(metadata i32 %inc, i64 0, metadata !21, metadata !DIExpression()), !dbg !38 %exitcond = icmp eq i32 %inc, %call, !dbg !38 br i1 %exitcond, label %if.end6, label %for.body, !dbg !38 -; CHECK: edge for.body -> if.end6 probability is 1 / 10227 = 0.00977804 -; CHECK: edge for.body -> for.body probability is 10226 / 10227 = 99.9902% [HOT edge] +; CHECK: edge for.body -> if.end6 probability is 0 / 10226 = 0% +; CHECK: edge for.body -> for.body probability is 10226 / 10226 = 100% [HOT edge] if.end6: ; preds = %for.body, %if.end %result.0 = phi double [ 0.000000e+00, %if.end ], [ %sub, %for.body ] diff --git a/test/Transforms/SampleProfile/calls.ll b/test/Transforms/SampleProfile/calls.ll index a6ad3444d89..10f43a1a612 100644 --- a/test/Transforms/SampleProfile/calls.ll +++ b/test/Transforms/SampleProfile/calls.ll @@ -52,8 +52,8 @@ while.cond: ; preds = %if.end, %entry store i32 %inc, i32* %i, align 4, !dbg !14 %cmp = icmp slt i32 %0, 400000000, !dbg !14 br i1 %cmp, label %while.body, label %while.end, !dbg !14 -; CHECK: edge while.cond -> while.body probability is 5391 / 5392 = 99.9815% [HOT edge] -; CHECK: edge while.cond -> while.end probability is 1 / 5392 = 0.018546% +; CHECK: edge while.cond -> while.body probability is 5391 / 5391 = 100% [HOT edge] +; CHECK: edge while.cond -> while.end probability is 0 / 5391 = 0% while.body: ; preds = %while.cond %1 = load i32, i32* %i, align 4, !dbg !16 @@ -63,8 +63,8 @@ while.body: ; preds = %while.cond ; both branches out of while.body had the same weight. In reality, ; the edge while.body->if.then is taken most of the time. ; -; CHECK: edge while.body -> if.then probability is 5752 / 5753 = 99.9826% [HOT edge] -; CHECK: edge while.body -> if.else probability is 1 / 5753 = 0.0173822% +; CHECK: edge while.body -> if.then probability is 5752 / 5752 = 100% [HOT edge] +; CHECK: edge while.body -> if.else probability is 0 / 5752 = 0% if.then: ; preds = %while.body diff --git a/test/Transforms/SampleProfile/propagate.ll b/test/Transforms/SampleProfile/propagate.ll index 8ee1e099906..620d125875f 100644 --- a/test/Transforms/SampleProfile/propagate.ll +++ b/test/Transforms/SampleProfile/propagate.ll @@ -73,8 +73,8 @@ for.cond: ; preds = %for.inc16, %if.else %5 = load i64, i64* %N.addr, align 8, !dbg !15 %cmp1 = icmp slt i64 %4, %5, !dbg !15 br i1 %cmp1, label %for.body, label %for.end18, !dbg !15 -; CHECK: edge for.cond -> for.body probability is 10 / 11 = 90.9091% [HOT edge] -; CHECK: edge for.cond -> for.end18 probability is 1 / 11 = 9.09091% +; CHECK: edge for.cond -> for.body probability is 10 / 10 = 100% [HOT edge] +; CHECK: edge for.cond -> for.end18 probability is 0 / 10 = 0% for.body: ; preds = %for.cond %6 = load i64, i64* %i, align 8, !dbg !18 @@ -119,8 +119,8 @@ for.cond8: ; preds = %for.inc, %if.else7 %14 = load i64, i64* %i, align 8, !dbg !28 %cmp10 = icmp slt i64 %conv9, %14, !dbg !28 br i1 %cmp10, label %for.body11, label %for.end, !dbg !28 -; CHECK: edge for.cond8 -> for.body11 probability is 16191 / 16192 = 99.9938% [HOT edge] -; CHECK: edge for.cond8 -> for.end probability is 1 / 16192 = 0.00617589% +; CHECK: edge for.cond8 -> for.body11 probability is 16191 / 16191 = 100% [HOT edge] +; CHECK: edge for.cond8 -> for.end probability is 0 / 16191 = 0% for.body11: ; preds = %for.cond8 %15 = load i32, i32* %j, align 4, !dbg !31 -- 2.34.1