allow branch weight metadata on select instructions (PR26636)

[spatel]

Summary

As noted in:
https://llvm.org/bugs/show_bug.cgi?id=26636

This doesn't accomplish anything on its own. It's the first step towards preserving and using branch weights with selects.

If this looks ok, the next step would be to make sure we're propagating the info in all of the other places where we create selects (SimplifyCFG, InstCombine, etc). I don't think there's an easy fix to make this happen; we have to look at each transform individually to determine how to correctly propagate the weights.

Along with that step, we need to then use the weights when making subsequent transform decisions such as discussed in http://reviews.llvm.org/D16836.

[davidxl]

This definitetly the right thing to do.

include/llvm/IR/IRBuilder.h

1579 ↗

(On Diff #50553)

The cloneImpl member method of the SelectInstr also needs to be updated to clone the metadata.

[spatel]

include/llvm/IR/IRBuilder.h

1579 ↗

(On Diff #50553)

Please let me know if there's a logic hole, but I think the base Instruction::clone() method handles this, so subclasses don't need to:
http://llvm.org/klaus/llvm/blob/master/lib/IR/Instruction.cpp#L-577

[spatel]

Patch updated:
Rather than creating a new regression test to verify the metadata, just add metadata to the existing test case for the transform.
We're going to need several of these updates, so I don't want to add regression test overhead for duplicate checking of every transform where metadata will be added.

[davidxl]

include/llvm/IR/IRBuilder.h

1571 ↗

(On Diff #50604)

Ok.

Is it possible to add a small test case (or update existing test case) to cover this -- i.e., after cloning (i.e via inlining), the meta data is maintained for select?

[spatel]

include/llvm/IR/IRBuilder.h

1571 ↗

(On Diff #50604)

Sure - that seems possible. But I wonder if we want to have multi-pass regression tests here? Ie, it would require 'opt -inline -simplifycfg'.

I thought we shy away from that form of regression test...although there is precedent in test/Transforms/Inline/invoke_test-2.ll.

[davidxl]

include/llvm/IR/IRBuilder.h

1571 ↗

(On Diff #50604)

Can you feed the inliner with IR that includes profile annotated 'select'? We just need to test the inline instance has 'select' that is also profile annotated.

[spatel]

include/llvm/IR/IRBuilder.h

1571 ↗

(On Diff #50604)

Ah, in that case the test that you would like to see is actually independent of this patch. I'll add it anyway to make sure that I'm understanding. It doesn't look like we even have a test with that profile metadata check for an inlined *branch*.

[spatel]

Patch updated:
Add inliner tests to make sure that cloned selects and branches are preserving profile metadata.

[davidxl]

lgtm.

include/llvm/IR/IRBuilder.h

1571 ↗

(On Diff #50628)

yes, this test case is what I am looking for -- I think it should be part of this patch (though the branch instruction meta test testing can be added in a separate patch though I won't mind either way).

I also suggesting changing the file name to 'profile-meta.ll'

llvm/trunk/include/llvm/IR/IRBuilder.h

public:
   }
 
   CallInst *CreateCall(Function *Callee, ArrayRef<Value *> Args,
                        const Twine &Name = "", MDNode *FPMathTag = nullptr) {
     return CreateCall(Callee->getFunctionType(), Callee, Args, Name, FPMathTag);
   }
 
   Value *CreateSelect(Value *C, Value *True, Value *False,
-                      const Twine &Name = "") {
+                      const Twine &Name = "", MDNode *ProfWeights = nullptr) {
     if (Constant *CC = dyn_cast<Constant>(C))
       if (Constant *TC = dyn_cast<Constant>(True))
         if (Constant *FC = dyn_cast<Constant>(False))
           return Insert(Folder.CreateSelect(CC, TC, FC), Name);
-    return Insert(SelectInst::Create(C, True, False), Name);
+
+    SelectInst *Sel = SelectInst::Create(C, True, False);
+    // TODO: "unpredictable" metadata can apply to a select too.
+    Sel->setMetadata(LLVMContext::MD_prof, ProfWeights);
+    return Insert(Sel, Name);
   }
 
   VAArgInst *CreateVAArg(Value *List, Type *Ty, const Twine &Name = "") {
     return Insert(new VAArgInst(List, Ty), Name);
   }
 
   Value *CreateExtractElement(Value *Vec, Value *Idx,
                               const Twine &Name = "") {

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

DomBlock->getInstList().splice(InsertPt->getIterator(),
                                    IfBlock2->getInstList(), IfBlock2->begin(),
                                    IfBlock2->getTerminator()->getIterator());
 
   while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
     // Change the PHI node into a select instruction.
     Value *TrueVal  = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
     Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
 
-    Value *Select = Builder.CreateSelect(IfCond, TrueVal, FalseVal);
+    MDNode *MDN = InsertPt->getMetadata(LLVMContext::MD_prof);
+    Value *Select = Builder.CreateSelect(IfCond, TrueVal, FalseVal, "", MDN);
     PN->replaceAllUsesWith(Select);
     Select->takeName(PN);
     PN->eraseFromParent();
   }
 
   // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement
   // has been flattened.  Change DomBlock to jump directly to our new block to
   // avoid other simplifycfg's kicking in on the diamond.

llvm/trunk/test/Transforms/Inline/profile-meta.ll

+; RUN: opt < %s -S -inline | FileCheck %s
+
+; Make sure that profile metadata is preserved when cloning a select.
+
+define i32 @callee_with_select(i1 %c, i32 %a, i32 %b) {
+  %sel = select i1 %c, i32 %a, i32 %b, !prof !0
+  ret i32 %sel
+}
+
+define i32 @caller_of_select(i1 %C, i32 %A, i32 %B) {
+  %ret = call i32 @callee_with_select(i1 %C, i32 %A, i32 %B)
+  ret i32 %ret
+
+; CHECK-LABEL: @caller_of_select(
+; CHECK-NEXT:  [[SEL:%.*]] = select i1 %C, i32 %A, i32 %B, !prof !0
+; CHECK-NEXT:  ret i32 [[SEL]]
+}
+
+; Make sure that profile metadata is preserved when cloning a branch.
+
+define i32 @callee_with_branch(i1 %c) {
+  br i1 %c, label %if, label %else, !prof !1
+if:
+  ret i32 1
+else:
+  ret i32 2
+}
+
+define i32 @caller_of_branch(i1 %C) {
+  %ret = call i32 @callee_with_branch(i1 %C)
+  ret i32 %ret
+
+; CHECK-LABEL: @caller_of_branch(
+; CHECK-NEXT:  br i1 %C, label %{{.*}}, label %{{.*}}, !prof !1
+}
+
+!0 = !{!"branch_weights", i32 1, i32 2}
+!1 = !{!"branch_weights", i32 3, i32 4}
+; CHECK: !0 = !{!"branch_weights", i32 1, i32 2}
+; CHECK: !1 = !{!"branch_weights", i32 3, i32 4}
+

llvm/trunk/test/Transforms/SimplifyCFG/PhiEliminate2.ll

 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
 
+; Use a select to make this a single BB.
+; Also, make sure the profile metadata is propagated to the select (PR26636).
+
 define i32 @FoldTwoEntryPHINode(i1 %C, i32 %V1, i32 %V2, i16 %V3) {
 entry:
-        br i1 %C, label %then, label %else
+        br i1 %C, label %then, label %else, !prof !0
 then:
         %V4 = or i32 %V2, %V1
         br label %Cont
 else:
         %V5 = sext i16 %V3 to i32
         br label %Cont
 Cont:
         %V6 = phi i32 [ %V5, %else ], [ %V4, %then ]
         call i32 @FoldTwoEntryPHINode( i1 false, i32 0, i32 0, i16 0 )
         ret i32 %V1
 
 ; CHECK-LABEL: @FoldTwoEntryPHINode(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:  %V5 = sext i16 %V3 to i32
 ; CHECK-NEXT:  %V4 = or i32 %V2, %V1
-; CHECK-NEXT:  %V6 = select i1 %C, i32 %V4, i32 %V5
+; CHECK-NEXT:  %V6 = select i1 %C, i32 %V4, i32 %V5, !prof !0
 ; CHECK-NEXT:  %0 = call i32 @FoldTwoEntryPHINode(i1 false, i32 0, i32 0, i16 0)
 ; CHECK-NEXT:  ret i32 %V1
 }
 
+!0 = !{!"branch_weights", i32 3, i32 5}
+
+; CHECK: !0 = !{!"branch_weights", i32 3, i32 5}
+