Index: lib/Analysis/BranchProbabilityInfo.cpp =================================================================== --- lib/Analysis/BranchProbabilityInfo.cpp +++ lib/Analysis/BranchProbabilityInfo.cpp @@ -22,6 +22,7 @@ #include "llvm/IR/Metadata.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include using namespace llvm; @@ -206,6 +207,25 @@ } assert(Weights.size() == TI->getNumSuccessors() && "Checked above"); + // Weight cannot be zero. Here we find out all zero weights read from MD, and + // replace them by 1. If any other weight is not zero, we need to normalize + // other weights so that the sum of all weights are maximized but less than + // UINT32_MAX. + auto ZeroWeightNum = std::count(Weights.begin(), Weights.end(), 0u); + if (ZeroWeightNum > 0) { + // If all weights are zeros, replace them by 1. + if (ZeroWeightNum == Weights.size()) + std::fill(Weights.begin(), Weights.end(), 1u); + else { + uint64_t ScalingFactor = (UINT32_MAX - ZeroWeightNum) / WeightSum; + if (ScalingFactor > 1) + for (auto &W : Weights) + W *= ScalingFactor; + std::replace(Weights.begin(), Weights.end(), 0u, 1u); + } + WeightSum += ZeroWeightNum; + } + // If the sum of weights does not fit in 32 bits, scale every weight down // accordingly. uint64_t ScalingFactor = @@ -213,7 +233,8 @@ WeightSum = 0; for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { - uint32_t W = Weights[i] / ScalingFactor; + // Make sure the weight is greater than 0. + uint32_t W = std::max(Weights[i] / ScalingFactor, 1); WeightSum += W; setEdgeWeight(BB, i, W); } Index: test/Analysis/BlockFrequencyInfo/bad_input.ll =================================================================== --- test/Analysis/BlockFrequencyInfo/bad_input.ll +++ test/Analysis/BlockFrequencyInfo/bad_input.ll @@ -9,8 +9,8 @@ entry: br label %for.body -; Check that we get 1,4 instead of 0,3. -; CHECK-NEXT: for.body: float = 4.0, +; Check that we get 1, ~UINT32_MAX instead of 0, 3. +; CHECK-NEXT: for.body: float = 4294967291.0, for.body: %i = phi i32 [ 0, %entry ], [ %inc, %for.body ] call void @g(i32 %i) Index: test/Transforms/SampleProfile/branch.ll =================================================================== --- test/Transforms/SampleProfile/branch.ll +++ test/Transforms/SampleProfile/branch.ll @@ -36,8 +36,8 @@ 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 0 / 1 = 0% -; CHECK: edge entry -> if.end probability is 1 / 1 = 100% +; CHECK: edge entry -> return probability is 1 / 4294967295 = 2.32831e-08% +; CHECK: edge entry -> if.end probability is 4294967294 / 4294967295 = 100% [HOT edge] if.end: ; preds = %entry %arrayidx = getelementptr inbounds i8*, i8** %argv, i64 1, !dbg !30 @@ -46,8 +46,8 @@ 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 0 / 1 = 0% -; CHECK: edge if.end -> if.end6 probability is 1 / 1 = 100% +; CHECK: edge if.end -> for.body probability is 1 / 4294967295 = 2.32831e-08% +; CHECK: edge if.end -> if.end6 probability is 4294967294 / 4294967295 = 100% [HOT edge] for.body: ; preds = %if.end, %for.body %u.016 = phi i32 [ %inc, %for.body ], [ 0, %if.end ] @@ -65,8 +65,8 @@ 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 0 / 10226 = 0% -; CHECK: edge for.body -> for.body probability is 10226 / 10226 = 100% [HOT edge] +; CHECK: edge for.body -> if.end6 probability is 1 / 4294960905 = 2.32831e-08% +; CHECK: edge for.body -> for.body probability is 4294960904 / 4294960905 = 100% [HOT edge] if.end6: ; preds = %for.body, %if.end %result.0 = phi double [ 0.000000e+00, %if.end ], [ %sub, %for.body ] Index: test/Transforms/SampleProfile/calls.ll =================================================================== --- test/Transforms/SampleProfile/calls.ll +++ test/Transforms/SampleProfile/calls.ll @@ -52,8 +52,8 @@ 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 / 5391 = 100% [HOT edge] -; CHECK: edge while.cond -> while.end probability is 0 / 5391 = 0% +; CHECK: edge while.cond -> while.body probability is 4294966572 / 4294966573 = 100% [HOT edge] +; CHECK: edge while.cond -> while.end probability is 1 / 4294966573 = 2.32831e-08% while.body: ; preds = %while.cond %1 = load i32, i32* %i, align 4, !dbg !16 @@ -63,8 +63,8 @@ ; 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 / 5752 = 100% [HOT edge] -; CHECK: edge while.body -> if.else probability is 0 / 5752 = 0% +; CHECK: edge while.body -> if.then probability is 4294966632 / 4294966633 = 100% [HOT edge] +; CHECK: edge while.body -> if.else probability is 1 / 4294966633 = 2.32831e-08% if.then: ; preds = %while.body Index: test/Transforms/SampleProfile/propagate.ll =================================================================== --- test/Transforms/SampleProfile/propagate.ll +++ test/Transforms/SampleProfile/propagate.ll @@ -73,8 +73,8 @@ %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 / 10 = 100% [HOT edge] -; CHECK: edge for.cond -> for.end18 probability is 0 / 10 = 0% +; CHECK: edge for.cond -> for.body probability is 4294967290 / 4294967291 = 100% [HOT edge] +; CHECK: edge for.cond -> for.end18 probability is 1 / 4294967291 = 2.32831e-08% for.body: ; preds = %for.cond %6 = load i64, i64* %i, align 8, !dbg !18 @@ -119,8 +119,8 @@ %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 / 16191 = 100% [HOT edge] -; CHECK: edge for.cond8 -> for.end probability is 0 / 16191 = 0% +; CHECK: edge if.then6 -> if.end15 probability is 16 / 16 = 100% [HOT edge] +; CHECK: edge for.cond8 -> for.end probability is 1 / 4294954189 = 2.32831e-08% for.body11: ; preds = %for.cond8 %15 = load i32, i32* %j, align 4, !dbg !31