<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal">Hi all,<o:p></o:p></p>
<p class="MsoNormal"><b><o:p> </o:p></b></p>
<p class="MsoNormal">I have been looking at how to convert by-reference captures into by-copy captures for captured statements and possibly C++ lambdas, and am looking for some feedback on my approach. The motivation for trying to use copy captures is to avoid
unnecessary loads that are otherwise required inside the outlined function. This can be important when the outlined function represents the body of a loop, and cannot be inlined, such as in cilk_for, or using a library-based parallel for with lambdas.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I have been prototyping an LLVM IR pass that can move loads out of a captured statement body when possible. The approach:
<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Use named metadata to find the captured statement helpers (or lambda functions), as well as the “kind” of captured region they represent.<o:p></o:p></p>
<p class="MsoNormal">e.g.<o:p></o:p></p>
<p class="MsoNormal">!capturedstmt.helper = !{!0, !1}<o:p></o:p></p>
<p class="MsoNormal">!0 = metadata !{<function1>, metadata !"cilk_for"}<o:p></o:p></p>
<p class="MsoNormal">!1 = metadata !{<function2>, metadata !"default"}<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">For each field in the implicit capture-struct parameter, determine whether it can be “promoted” to a by-copy capture. This involves<o:p></o:p></p>
<p class="MsoNormal">1) checking the type of the field: only pointers to pointers or pointers to primitive types with size <= the original pointer can currently be promoted – this skips types that might require a copy constructor, and ensures that they are
cheap to pass by value.<o:p></o:p></p>
<p class="MsoNormal">2) looking at the uses of the field in the helper: if the field is used in any operation other than a load, then assume it cannot be promoted<o:p></o:p></p>
<p class="MsoNormal">3) looking at the uses of the field in the call-site(s): if the pointer stored in the field may also be passed into the helper in another way, then it cannot be promoted. I have not implemented anything for this, but I imagine there are
existing passes that would be useful here, such as alias analysis. For captured statements, there is only one call-site to worry about, but in lambdas all call-sites would need to be considered.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">If any fields can be promoted, then clone the original function with a new capture struct parameter e.g. {i32**, i32*} -> {i32*, i32}. Then replace loads of the original field with the value inside the outlined function. The call-site
is updated to call the new function, and add loads of any arguments that have been promoted. These loads may be removed by later optimizations.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">e.g.<o:p></o:p></p>
<p class="MsoNormal">%a = alloca i32<o:p></o:p></p>
<p class="MsoNormal">%context = alloca {i32*}<o:p></o:p></p>
<p class="MsoNormal">%field = getelementptr inbounds {i32*}* %context, i32 0, i32 0<o:p></o:p></p>
<p class="MsoNormal">store i32* %a, i32** %field<o:p></o:p></p>
<p class="MsoNormal">call void @__captured_stmt_helper({i32*}* %context)<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">define void @__captured_stmt_helper({i32*}* %context) {<o:p></o:p></p>
<p class="MsoNormal"> %field = getelementptr inbounds {i32*}* %context, i32 0, i32 0<o:p></o:p></p>
<p class="MsoNormal"> %load.field = load i32** %field<o:p></o:p></p>
<p class="MsoNormal"> %a = load i32* %load.field<o:p></o:p></p>
<p class="MsoNormal"> …<o:p></o:p></p>
<p class="MsoNormal">}<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Becomes something like<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">%a = alloca i32<o:p></o:p></p>
<p class="MsoNormal">%context = alloca {i32}<o:p></o:p></p>
<p class="MsoNormal">%field = getelementptr inbounds {i32}* %context, i32 0, i32 0<o:p></o:p></p>
<p class="MsoNormal">%load.a = load i32* %a<o:p></o:p></p>
<p class="MsoNormal">store i32 %load.a, i32* %field<o:p></o:p></p>
<p class="MsoNormal">call void @__captured_stmt_helper_new({i32}* %context)<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">define void @__captured_stmt_helper_new({i32}* %context) {<o:p></o:p></p>
<p class="MsoNormal"> %field = getelementptr inbounds {i32}* %context, i32 0, i32 0<o:p></o:p></p>
<p class="MsoNormal"> %a = load i32* %field<o:p></o:p></p>
<p class="MsoNormal"> …<o:p></o:p></p>
<p class="MsoNormal">}<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I’d love to hear any feedback about this approach, since I’m not totally convinced yet this should not be done in Clang’s AST instead. Thanks,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Ben<o:p></o:p></p>
</div>
</body>
</html>