This is an archive of the discontinued LLVM Phabricator instance.

[ICP] Expose unconditional call promotion interface
ClosedPublic

Authored by mssimpso on Dec 1 2017, 1:25 PM.

Details

Summary

This patch modifies the common indirect call promotion utilities by by exposing and using an unconditional call promotion interface. These changes are meant to accommodate the planned use case in D39869. The unconditional promotion interface (i.e., call promotion without creating an if-then-else) can be used if it's known that an indirect call has only one possible callee. The existing conditional promotion interface uses this unconditional interface to promote an indirect call after it has been versioned and placed within the "then" block.

A consequence of unconditional promotion is that the fix-up operations for phi nodes in the normal destination of invoke instructions are changed. This is necessary because the existing implementation assumed that an invoke had been versioned, creating a "merge" block where a return value bitcast could be placed. In the new implementation, the edge between a promoted invoke's parent block and its normal destination is split if needed to add a bitcast for the return value. If the invoke is also versioned, the phi node merging the return value of the promoted and original invoke instructions is placed in the "merge" block.

Diff Detail

Repository
rL LLVM

Event Timeline

mssimpso updated this revision to Diff 125800.Dec 6 2017, 1:45 PM

Rebased. Thanks!

davidxl added inline comments.Dec 11 2017, 4:35 PM
include/llvm/Transforms/Utils/CallPromotionUtils.h
47 ↗(On Diff #125800)

Can you remove this method in this patch? It is not used anywhere

lib/Transforms/IPO/SampleProfile.cpp
829 ↗(On Diff #125800)

what is this change for?

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp
315 ↗(On Diff #125800)

What is this change for?

lib/Transforms/Utils/CallPromotionUtils.cpp
36 ↗(On Diff #125800)

Can you explain this change (and other related interface changes) perhaps with a tiny example -- there are lots of words in the description but not as helpful as an example.

279 ↗(On Diff #125800)

Remove this one from this patch.

fhahn added a subscriber: fhahn.Dec 11 2017, 11:00 PM
mssimpso updated this revision to Diff 126569.Dec 12 2017, 10:08 AM
mssimpso marked 3 inline comments as done.

Addressed David's comments. Thanks for the feedback!

  • Moved demoteCall to D39869.
  • Added comments with example code snippets to the basic transformations.
mssimpso added inline comments.
include/llvm/Transforms/Utils/CallPromotionUtils.h
47 ↗(On Diff #125800)

Sure, that make sense. I'll add this part to D39869.

lib/Transforms/IPO/SampleProfile.cpp
829 ↗(On Diff #125800)

The conditional promotion interface now modifies the given call site to be direct and returns the newly created indirect call site. Previously the given call site was left unmodified, and a newly created direct call site was returned. This change makes the conditional and unconditional promotion interfaces consistent with each other (the given call site is changed to be direct), and also works well with D39869.

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp
315 ↗(On Diff #125800)

Same as above. "Inst" is now made to be direct, and "NewInst" is the new instruction in the "else" block.

lib/Transforms/Utils/CallPromotionUtils.cpp
36 ↗(On Diff #125800)

Sure, I've added code snippets to all of the basic transformations with both call and invoke examples.

Basically, the code here is changing because the control-flow we create for conditional promotion is slightly different than it was previously. The reason it's different is described below. Previously, we generated code like:

orig_bb:
  %cond = icmp eq i32 ()* %ptr, @func
  br i1 %cond, %then_bb, %else_bb

then_bb:
  %t0 = invoke i32 @func() to label %merge_bb unwind label %unwind_dst

else_bb:
  %t1 = invoke i32 %ptr() to label %normal_dst unwind label %unwind_dst

merge_bb:
  br %normal_dst

normal_dst:
  %t2 = phi i32 [ %t0, %merge_bb ], [ %t1, %else_bb ]

Whereas now, we generate code like:

orig_bb:
  %cond = icmp eq i32 ()* %ptr, @func
  br i1 %cond, %then_bb, %else_bb

then_bb:
  %t0 = invoke i32 @func() to label %merge_bb unwind label %unwind_dst

else_bb:
  %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst

merge_bb:
  %t2 = phi i32 [ %t0, %then_bb ], [ %t1, %else_bb ]
  br %normal_dst

The difference is that now both invokes have "merge_bb" as their normal destination. Previously, only the normal destination of the promoted invoke was set to "merge_bb", where a return value bitcast was added if needed, and the phi node for merging the return values was created/modified in the original normal destination. After this patch, the normal destination of both invokes is set to "merge_bb", where the merge phi node is added, and if a return value bitcast is required, the edge between "then_bb" and "merge_bb" is split and the bitcast is placed there.

Previously, there was no way to perform a stand-alone unconditional promotion because it was assumed that an if-then-else structure would always be created. We can do that now with this patch, and the refactoring allows greater code reuse between the conditional and unconditional cases. To perform conditional promotion, we just need to version the original invoke (which creates the if-then-else structure, adds the merge phi node, and fixes up phi nodes in the normal and unwind destinations), and then unconditionally promote one of them (which also adds the return value bitcast if necessary). I hope that helps!

279 ↗(On Diff #125800)

This will be added to D39869

davidxl added inline comments.Dec 14 2017, 11:09 AM
lib/Transforms/IPO/SampleProfile.cpp
829 ↗(On Diff #125800)

I don't see pgo::promoteIndirectCall interface documentation change in this patch (in the header).

Besides, I am not sure the proposed interface change is better -- it is more natural to return the promoted 'direct call' instruction and modify I (reference) to be the indirect call, instead of requiring the client to do DI = I before the call.

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp
315 ↗(On Diff #125800)

It is very confusing -- this is the reason I don't like the interface change. A reader will naturally think NewInst is the newly created direct call (the implementation may still choose to modify the existing instruction and return it).

lib/Transforms/Utils/CallPromotionUtils.cpp
166 ↗(On Diff #126569)

Add a test case for the splitBB case for bitcast?

Thanks again for the comments, David. I'll update the patch shortly.

lib/Transforms/IPO/SampleProfile.cpp
829 ↗(On Diff #125800)

Sure, I'm fine restoring the interface if you'd prefer. The client can always swap the pointers after the call if needed.

lib/Transforms/Utils/CallPromotionUtils.cpp
166 ↗(On Diff #126569)

This case is reflected in the change to test/Transforms/PGOProfile/icp_covariant_invoke_return.ll. After versioning the invoke, the if.true.direct_targ.if.end.icp_crit_edge block, which contains the bitcast, is added between the invoke's parent block (the direct call bock), and it's normal destination (the merge block).

mssimpso updated this revision to Diff 127032.Dec 14 2017, 2:48 PM
mssimpso marked 2 inline comments as done.
mssimpso edited the summary of this revision. (Show Details)

Addressed David's comments. Thanks again!

  • Restored the existing conditional call promotion interface.
davidxl accepted this revision.Dec 14 2017, 3:14 PM

there are two small suggestions. otherwise LGTM

include/llvm/Transforms/Utils/CallPromotionUtils.h
36 ↗(On Diff #127032)

Perhaps return the callInstruction and perhaps a third optional pointer parameter to store the bitcast created.

lib/Transforms/Utils/CallPromotionUtils.cpp
424 ↗(On Diff #127032)

let NewInst = promoteCall(...) instead of implicitly assume the same instruction gets converted.

This revision is now accepted and ready to land.Dec 14 2017, 3:14 PM

Thanks David! I'll make those changes before committing.

This revision was automatically updated to reflect the committed changes.