Index: lib/Transforms/Scalar/LowerExpectIntrinsic.cpp =================================================================== --- lib/Transforms/Scalar/LowerExpectIntrinsic.cpp +++ lib/Transforms/Scalar/LowerExpectIntrinsic.cpp @@ -83,6 +83,109 @@ return true; } +// Handle phi node which define the value of the +// the builtin_expect's argument value: +// If the operand of the phi has a constant value +// and it 'contradicts' with the expected value of +// phi def, then the corresponding incoming edge +// of the phi is unlikely to be taken. Using that +// information, the branch probability info for the +// originating branch can be inferred. +void static handlePhiDef(CallInst *Expect) { + Value *ArgValue = Expect->getArgOperand(0); + ConstantInt *ExpectedValue = dyn_cast(Expect->getArgOperand(1)); + PHINode *PhiDef = nullptr; + bool ValueInverted = false; + // walk up the copy chain until phi is reached or + // non copy like instruction is reached. + Value *V = ArgValue; + while (true) { + if (ZExtInst *ZExt = dyn_cast(V)) { + V = ZExt->getOperand(0); + } else if (SExtInst *SExt = dyn_cast(V)) { + V = SExt->getOperand(0); + } else if (BinaryOperator *BinOp = dyn_cast(V)) { + Instruction::BinaryOps Opcode = BinOp->getOpcode(); + if (Opcode == Instruction::Xor) { + Value *Opnd0 = BinOp->getOperand(0); + Value *Opnd1 = BinOp->getOperand(1); + + assert(!dyn_cast(Opnd0) && "expression not canonicalized"); + if (ConstantInt *CInt = dyn_cast(Opnd1)) { + V = Opnd0; + if (CInt->getZExtValue()) + ValueInverted = !ValueInverted; + } else { + // Not copy like, bail + break; + } + continue; + } + // unknown binary ops + break; + } else if (PHINode *Phi = dyn_cast(V)) { + PhiDef = Phi; + break; + } else { + break; + } + } + + if (!PhiDef) + return; + + bool IsPhiValueOne = ((!ValueInverted && !ExpectedValue->isZero()) || + (ValueInverted && ExpectedValue->isZero())); + + // Get the first dominating conditional branch of the operand + // i's incoming block. + auto GetDomConditional = [=](unsigned i) -> BranchInst * { + BasicBlock *BB = PhiDef->getIncomingBlock(i); + BranchInst *BR = dyn_cast(BB->getTerminator()); + if (BR && BR->isConditional()) + return BR; + // CFG may not be simplified yet, walk up one level + BB = BB->getSinglePredecessor(); + if (!BB) + return nullptr; + BR = dyn_cast(BB->getTerminator()); + if (!BR || BR->isUnconditional()) + return nullptr; + return BR; + }; + + // Now walk through all Phi operands: + for (unsigned i = 0, e = PhiDef->getNumIncomingValues(); i != e; ++i) { + Value *PhiOpnd = PhiDef->getIncomingValue(i); + ConstantInt *CI = dyn_cast(PhiOpnd); + if (!CI) + continue; + bool IsPhiOpndOne = !CI->isZero(); + bool IsUnlikely = (IsPhiValueOne != IsPhiOpndOne); + // Not an interesting case: + if (!IsUnlikely) + continue; + + BranchInst *BR = GetDomConditional(i); + if (!BR) + continue; + + MDBuilder MDB(PhiDef->getContext()); + MDNode *Node = nullptr; + + // Triangular or diamond shaped: + if (PhiDef->getParent() == BR->getSuccessor(1) || + PhiDef->getIncomingBlock(i) == BR->getSuccessor(1)) + Node = MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight); + else if (PhiDef->getParent() == BR->getSuccessor(0) || + PhiDef->getIncomingBlock(i) == BR->getSuccessor(0)) + Node = MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight); + + if (Node) + BR->setMetadata(LLVMContext::MD_prof, Node); + } +} + // Handle both BranchInst and SelectInst. template static bool handleBrSelExpect(BrSelInst &BSI) { @@ -173,6 +276,10 @@ Function *Fn = CI->getCalledFunction(); if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) { + // Before erasing the phi, walk backward to find + // phi that define builin_expect's first arg, and + // infer branch probability: + handlePhiDef(CI); Value *Exp = CI->getArgOperand(0); CI->replaceAllUsesWith(Exp); CI->eraseFromParent(); Index: test/Transforms/LowerExpectIntrinsic/phi_merge.ll =================================================================== --- test/Transforms/LowerExpectIntrinsic/phi_merge.ll +++ test/Transforms/LowerExpectIntrinsic/phi_merge.ll @@ -0,0 +1,132 @@ +; RUN: opt -lower-expect -S -o - < %s | FileCheck %s +; RUN: opt -S -passes='function(lower-expect)' < %s | FileCheck %s + +; The C case +; if (__builtin_expect((x > goo() && y > hoo() && z > too()), 1)) +; For the above case, all 3 branches should be annotated. +; +; if (__builtin_expect((x > goo() && y > hoo() && z > too()), 0)) +; For the above case, we don't have enough information, so +; only the last branch is annotated. + +define void @foo(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3) #0 { +bb: + %tmp = alloca i32, align 4 + %tmp4 = alloca i32, align 4 + %tmp5 = alloca i32, align 4 + %tmp6 = alloca i32, align 4 + store i32 %arg, i32* %tmp, align 4 + store i32 %arg1, i32* %tmp4, align 4 + store i32 %arg2, i32* %tmp5, align 4 + store i32 %arg3, i32* %tmp6, align 4 + %tmp7 = load i32, i32* %tmp, align 4 + %tmp8 = call i32 (...) @goo() + %tmp9 = icmp slt i32 %tmp7, %tmp8 +; CHECK: !prof [[WEIGHT:![0-9]+]] + br i1 %tmp9, label %bb10, label %bb18 + +bb10: ; preds = %bb + %tmp11 = load i32, i32* %tmp5, align 4 + %tmp12 = call i32 (...) @hoo() + %tmp13 = icmp sgt i32 %tmp11, %tmp12 +; CHECK: br i1 %tmp13, {{.*}}!prof [[WEIGHT]] + br i1 %tmp13, label %bb14, label %bb18 + +bb14: ; preds = %bb10 + %tmp15 = load i32, i32* %tmp6, align 4 + %tmp16 = call i32 (...) @too() + %tmp17 = icmp sgt i32 %tmp15, %tmp16 + br label %bb18 + +bb18: ; preds = %bb14, %bb10, %bb + %tmp19 = phi i1 [ false, %bb10 ], [ false, %bb ], [ %tmp17, %bb14 ] + %tmp20 = xor i1 %tmp19, true + %tmp21 = xor i1 %tmp20, true + %tmp22 = zext i1 %tmp21 to i32 + %tmp23 = sext i32 %tmp22 to i64 + %tmp24 = call i64 @llvm.expect.i64(i64 %tmp23, i64 1) + %tmp25 = icmp ne i64 %tmp24, 0 +; CHECK: br i1 %tmp25,{{.*}}!prof [[WEIGHT]] + br i1 %tmp25, label %bb26, label %bb28 + +bb26: ; preds = %bb18 + %tmp27 = call i32 (...) @goo() + br label %bb30 + +bb28: ; preds = %bb18 + %tmp29 = call i32 (...) @hoo() + br label %bb30 + +bb30: ; preds = %bb28, %bb26 + ret void +} + +define void @foo2(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3) #0 { +bb: + %tmp = alloca i32, align 4 + %tmp4 = alloca i32, align 4 + %tmp5 = alloca i32, align 4 + %tmp6 = alloca i32, align 4 + store i32 %arg, i32* %tmp, align 4 + store i32 %arg1, i32* %tmp4, align 4 + store i32 %arg2, i32* %tmp5, align 4 + store i32 %arg3, i32* %tmp6, align 4 + %tmp7 = load i32, i32* %tmp, align 4 + %tmp8 = call i32 (...) @goo() + %tmp9 = icmp slt i32 %tmp7, %tmp8 +; CHECK-NOT: !prof + br i1 %tmp9, label %bb10, label %bb18 + +bb10: ; preds = %bb + %tmp11 = load i32, i32* %tmp5, align 4 + %tmp12 = call i32 (...) @hoo() + %tmp13 = icmp sgt i32 %tmp11, %tmp12 +; CHECK-NOT: !prof + br i1 %tmp13, label %bb14, label %bb18 + +bb14: ; preds = %bb10 + %tmp15 = load i32, i32* %tmp6, align 4 + %tmp16 = call i32 (...) @too() + %tmp17 = icmp sgt i32 %tmp15, %tmp16 + br label %bb18 + +bb18: ; preds = %bb14, %bb10, %bb + %tmp19 = phi i1 [ false, %bb10 ], [ false, %bb ], [ %tmp17, %bb14 ] + %tmp20 = xor i1 %tmp19, true + %tmp21 = xor i1 %tmp20, true + %tmp22 = zext i1 %tmp21 to i32 + %tmp23 = sext i32 %tmp22 to i64 + %tmp24 = call i64 @llvm.expect.i64(i64 %tmp23, i64 0) + %tmp25 = icmp ne i64 %tmp24, 0 +; CHECK: br i1 %tmp25,{{.*}}!prof [[WEIGHT2:![0-9]+]] + br i1 %tmp25, label %bb26, label %bb28 + +bb26: ; preds = %bb18 + %tmp27 = call i32 (...) @goo() + br label %bb30 + +bb28: ; preds = %bb18 + %tmp29 = call i32 (...) @hoo() + br label %bb30 + +bb30: ; preds = %bb28, %bb26 + ret void +} + +declare i32 @goo(...) + +declare i32 @hoo(...) + +declare i32 @too(...) + +; Function Attrs: nounwind readnone +declare i64 @llvm.expect.i64(i64, i64) #1 + +attributes #0 = { noinline nounwind uwtable } +attributes #1 = { nounwind readnone } + +!llvm.ident = !{!0} + +!0 = !{!"clang version 5.0.0 (trunk 302965)"} +; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 2000, i32 1} +; CHECK: [[WEIGHT2]] = !{!"branch_weights", i32 1, i32 2000} Index: test/Transforms/LowerExpectIntrinsic/phi_or.ll =================================================================== --- test/Transforms/LowerExpectIntrinsic/phi_or.ll +++ test/Transforms/LowerExpectIntrinsic/phi_or.ll @@ -0,0 +1,113 @@ +; RUN: opt -lower-expect -S -o - < %s | FileCheck %s +; RUN: opt -S -passes='function(lower-expect)' < %s | FileCheck %s +; +; if (__builtin_expect((x > goo() || y > hoo()), 1)) { +; .. +; } +; For the above case, only the second branch should be +; annotated. +; if (__builtin_expect((x > goo() || y > hoo()), 0)) { +; .. +; } +; For the above case, two branches should be annotated. +; Function Attrs: noinline nounwind uwtable +define void @foo(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3) #0 { +bb: + %tmp = alloca i32, align 4 + %tmp4 = alloca i32, align 4 + %tmp5 = alloca i32, align 4 + %tmp6 = alloca i32, align 4 + store i32 %arg, i32* %tmp, align 4 + store i32 %arg1, i32* %tmp4, align 4 + store i32 %arg2, i32* %tmp5, align 4 + store i32 %arg3, i32* %tmp6, align 4 + %tmp7 = load i32, i32* %tmp, align 4 + %tmp8 = call i32 (...) @goo() + %tmp9 = icmp slt i32 %tmp7, %tmp8 +; CHECK-NOT: br i1 %tmp9{{.*}}!prof + br i1 %tmp9, label %bb14, label %bb10 + +bb10: ; preds = %bb + %tmp11 = load i32, i32* %tmp5, align 4 + %tmp12 = call i32 (...) @hoo() + %tmp13 = icmp sgt i32 %tmp11, %tmp12 + br label %bb14 + +bb14: ; preds = %bb10, %bb + %tmp15 = phi i1 [ true, %bb ], [ %tmp13, %bb10 ] + %tmp16 = zext i1 %tmp15 to i32 + %tmp17 = sext i32 %tmp16 to i64 + %expect = call i64 @llvm.expect.i64(i64 %tmp17, i64 1) + %tmp18 = icmp ne i64 %expect, 0 +; CHECK: br i1 %tmp18{{.*}}!prof [[WEIGHT:![0-9]+]] + br i1 %tmp18, label %bb19, label %bb21 + +bb19: ; preds = %bb14 + %tmp20 = call i32 (...) @goo() + br label %bb23 + +bb21: ; preds = %bb14 + %tmp22 = call i32 (...) @hoo() + br label %bb23 + +bb23: ; preds = %bb21, %bb19 + ret void +} + +define void @foo2(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3) #0 { +bb: + %tmp = alloca i32, align 4 + %tmp4 = alloca i32, align 4 + %tmp5 = alloca i32, align 4 + %tmp6 = alloca i32, align 4 + store i32 %arg, i32* %tmp, align 4 + store i32 %arg1, i32* %tmp4, align 4 + store i32 %arg2, i32* %tmp5, align 4 + store i32 %arg3, i32* %tmp6, align 4 + %tmp7 = load i32, i32* %tmp, align 4 + %tmp8 = call i32 (...) @goo() + %tmp9 = icmp slt i32 %tmp7, %tmp8 +; CHECK: br i1 %tmp9{{.*}}!prof [[WEIGHT2:![0-9]+]] + br i1 %tmp9, label %bb14, label %bb10 + +bb10: ; preds = %bb + %tmp11 = load i32, i32* %tmp5, align 4 + %tmp12 = call i32 (...) @hoo() + %tmp13 = icmp sgt i32 %tmp11, %tmp12 + br label %bb14 + +bb14: ; preds = %bb10, %bb + %tmp15 = phi i1 [ true, %bb ], [ %tmp13, %bb10 ] + %tmp16 = zext i1 %tmp15 to i32 + %tmp17 = sext i32 %tmp16 to i64 + %expect = call i64 @llvm.expect.i64(i64 %tmp17, i64 0) + %tmp18 = icmp ne i64 %expect, 0 +; CHECK: br i1 %tmp18{{.*}}!prof [[WEIGHT2]] + br i1 %tmp18, label %bb19, label %bb21 + +bb19: ; preds = %bb14 + %tmp20 = call i32 (...) @goo() + br label %bb23 + +bb21: ; preds = %bb14 + %tmp22 = call i32 (...) @hoo() + br label %bb23 + +bb23: ; preds = %bb21, %bb19 + ret void +} + +declare i32 @goo(...) #1 +declare i32 @hoo(...) #1 +declare i64 @llvm.expect.i64(i64, i64) #2 + +attributes #0 = { noinline nounwind uwtable } +attributes #1 = { noinline nounwind uwtable } +attributes #2 = { nounwind readnone } + +!llvm.ident = !{!0} + + +!0 = !{!"clang version 5.0.0 (trunk 302965)"} +; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 2000, i32 1} +; CHECK: [[WEIGHT2]] = !{!"branch_weights", i32 1, i32 2000} Index: test/Transforms/LowerExpectIntrinsic/phi_tern.ll =================================================================== --- test/Transforms/LowerExpectIntrinsic/phi_tern.ll +++ test/Transforms/LowerExpectIntrinsic/phi_tern.ll @@ -0,0 +1,70 @@ +; RUN: opt -lower-expect -S -o - < %s | FileCheck %s +; RUN: opt -S -passes='function(lower-expect)' < %s | FileCheck %s + +; return __builtin_expect((a > b ? 1, goo(), 0); +; +; Function Attrs: noinline nounwind uwtable +define i32 @foo(i32 %arg, i32 %arg1) #0 { +bb: + %tmp = alloca i32, align 4 + %tmp2 = alloca i32, align 4 + store i32 %arg, i32* %tmp, align 4 + store i32 %arg1, i32* %tmp2, align 4 + %tmp3 = load i32, i32* %tmp, align 4 + %tmp4 = load i32, i32* %tmp2, align 4 + %tmp5 = icmp sgt i32 %tmp3, %tmp4 +; CHECK: br i1 %tmp5{{.*}}!prof [[WEIGHT:![0-9]+]] + br i1 %tmp5, label %bb9, label %bb7 + +bb7: ; preds = %bb + %tmp8 = call i32 (...) @goo() + br label %bb9 + +bb9: ; preds = %bb7, %bb9 + %tmp10 = phi i32 [ 1, %bb ], [ %tmp8, %bb7 ] + %tmp11 = sext i32 %tmp10 to i64 + %expect = call i64 @llvm.expect.i64(i64 %tmp11, i64 0) + %tmp12 = trunc i64 %expect to i32 + ret i32 %tmp12 +} + +define i32 @foo2(i32 %arg, i32 %arg1) #0 { +bb: + %tmp = alloca i32, align 4 + %tmp2 = alloca i32, align 4 + store i32 %arg, i32* %tmp, align 4 + store i32 %arg1, i32* %tmp2, align 4 + %tmp3 = load i32, i32* %tmp, align 4 + %tmp4 = load i32, i32* %tmp2, align 4 + %tmp5 = icmp sgt i32 %tmp3, %tmp4 +; CHECK: br i1 %tmp5{{.*}}!prof [[WEIGHT:![0-9]+]] + br i1 %tmp5, label %bb6, label %bb7 + +bb6: ; preds = %bb + br label %bb9 + +bb7: ; preds = %bb + %tmp8 = call i32 (...) @goo() + br label %bb9 + +bb9: ; preds = %bb7, %bb6 + %tmp10 = phi i32 [ 1, %bb6 ], [ %tmp8, %bb7 ] + %tmp11 = sext i32 %tmp10 to i64 + %expect = call i64 @llvm.expect.i64(i64 %tmp11, i64 0) + %tmp12 = trunc i64 %expect to i32 + ret i32 %tmp12 +} + +declare i32 @goo(...) #1 +declare i64 @llvm.expect.i64(i64, i64) #2 + +attributes #0 = { noinline nounwind uwtable } +attributes #1 = { noinline nounwind uwtable } +attributes #2 = { nounwind readnone } + + +!llvm.ident = !{!0} + +!0 = !{!"clang version 5.0.0 (trunk 302965)"} + +; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 1, i32 2000}