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

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

[spatel]

include/llvm/IR/IRBuilder.h

1579

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

1579

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

1579

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

1579

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

1579

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

1579

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'

include/llvm/IR/IRBuilder.h

CallInst *CreateCall(Value *Callee, ArrayRef<Value *> Args,
     return Insert(CI, Name);
   }
 
   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 = "") {

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.

test/Transforms/SimplifyCFG/preserve-branchweights.ll

 for.inc:
   %shl = shl i32 %bit.0, 1
   %inc19 = add nsw i32 %i.1, 1
   br label %for.cond2
 for.exit:
   ret void
 }
 
+; PR26636: The branch metadata should get propagated to the select.
+
+define i32 @FoldTwoEntryPHINode(i32 %x) #0 {
+entry:
+  %cmp = icmp sgt i32 %x, 4
+  br i1 %cmp, label %if.then, label %if.end, !prof !12
+
+if.then:
+  %add = add nsw i32 %x, 7
+  br label %return
+
+if.end:
+  %mul = mul nsw i32 %x, 17
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %add, %if.then ], [ %mul, %if.end ]
+  ret i32 %retval.0
+
+; CHECK-LABEL: @FoldTwoEntryPHINode(
+; CHECK-NEXT: entry:
+; CHECK-NEXT:  %cmp = icmp sgt i32 %x, 4
+; CHECK-NEXT:  %add = add nsw i32 %x, 7
+; CHECK-NEXT:  %mul = mul nsw i32 %x, 17
+; CHECK-NEXT:  %retval.0 = select i1 %cmp, i32 %add, i32 %mul, !prof !11
+; CHECK-NEXT:  ret i32 %retval.0
+}
+
+
 !0 = !{!"branch_weights", i32 3, i32 5}
 !1 = !{!"branch_weights", i32 1, i32 1}
 !2 = !{!"branch_weights", i32 1, i32 2}
 !3 = !{!"branch_weights", i32 4, i32 3, i32 2, i32 1}
 !4 = !{!"branch_weights", i32 4, i32 3, i32 2, i32 1}
 !5 = !{!"branch_weights", i32 7, i32 6, i32 5}
 !6 = !{!"branch_weights", i32 1, i32 3}
 !7 = !{!"branch_weights", i32 33, i32 9, i32 8, i32 7}
 !8 = !{!"branch_weights", i32 33, i32 9, i32 8}
 !9 = !{!"branch_weights", i32 7, i32 6}
 !10 = !{!"branch_weights", i32 672646, i32 21604207}
 !11 = !{!"branch_weights", i32 6960, i32 21597248}
+!12 = !{!"branch_weights", i32 6, i32 2000}
 
 ; CHECK: !0 = !{!"branch_weights", i32 5, i32 11}
 ; CHECK: !1 = !{!"branch_weights", i32 1, i32 5}
 ; CHECK: !2 = !{!"branch_weights", i32 7, i32 1, i32 2}
 ; CHECK: !3 = !{!"branch_weights", i32 49, i32 12, i32 24, i32 35}
 ; CHECK: !4 = !{!"branch_weights", i32 11, i32 5}
 ; CHECK: !5 = !{!"branch_weights", i32 17, i32 15} 
 ; CHECK: !6 = !{!"branch_weights", i32 9, i32 7}
 ; CHECK: !7 = !{!"branch_weights", i32 17, i32 9, i32 8, i32 7, i32 17}
 ; CHECK: !8 = !{!"branch_weights", i32 24, i32 33}
 ; CHECK: !9 = !{!"branch_weights", i32 8, i32 33}
 ;; The false weight prints out as a negative integer here, but inside llvm, we
 ;; treat the weight as an unsigned integer.
 ; CHECK: !10 = !{!"branch_weights", i32 112017436, i32 -735157296}
+; CHECK: !11 = !{!"branch_weights", i32 6, i32 2000}