<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 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@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:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p.MsoPlainText, li.MsoPlainText, div.MsoPlainText
{mso-style-priority:99;
mso-style-link:"Plain Text Char";
margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.PlainTextChar
{mso-style-name:"Plain Text Char";
mso-style-priority:99;
mso-style-link:"Plain Text";
font-family:"Calibri",sans-serif;}
.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="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoPlainText">Hi all,<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">during the last US LLVM conference (October last year), I had two 'BoF restrict' sessions.<o:p></o:p></p>
<p class="MsoPlainText">During these sessions, I discussed with a number of persons our view and mechanism on fixing the issues<o:p></o:p></p>
<p class="MsoPlainText">with llvm's restrict implementation and Hal Finkel's local restrict patches. One outcome of these discussions<o:p></o:p></p>
<p class="MsoPlainText">was a request to put all of this together in an RFC and present it to the larger llvm community so that a<o:p></o:p></p>
<p class="MsoPlainText">broader discussion can be started.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">With thanks to Wouter, Bruno, Dirk, Gert, Troy, David, Johannes for helping with the initial review of this rfc.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Greetings,<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Jeroen Dobbelaere<o:p></o:p></p>
<p class="MsoPlainText">---<o:p></o:p></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> 2019-03-19 jeroen.dobbelaere@synopsys.com<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">
<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">RFC: Full 'restrict' support in LLVM<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">== Introduction ==<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">LLVM only has basic support for restrict on function arguments. All other<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">restrict usages are ignored. This document proposes a mechanism to get full<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">support for restrict in LLVM.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">== 'restrict' ==<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">C99 introduces the 'restrict' keyword for pointer operands [1, 2]. It helps the<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">programmer to specify that memory accesses will not interfere with each<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">other. Based on such information, the compiler can decide to do better<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">optimizations and transformations, as it can assume that certain memory accesses<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">will never alias. This can result in dramatic speed improvements.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Restrict pointers can occur as function arguments, local variables (local restrict),<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">struct members (restrict member pointers), global variables, ...<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">== Current status (LLVM-8) ==<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">LLVM mostly ignores the 'restrict' keyword. It only has support for restrict<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">pointer arguments of a function. Even there, the C restrict keyword is mapped<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">onto the 'noalias' argument attribute, which is in some way stronger than<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">'restrict' [5,9].<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">While inlining, LLVM tries to track the 'noalias' argument information through<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">the '!noalias' and '!alias.scope' metadata. This easily results in<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">transformations that are not correct according to the C restrict rules, as this<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">metadata representation is not sufficient to retain all information that is<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">needed to represent all cases [6].<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Another example that demonstrates this problem is shown in [7]:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> #define SIZE 1024<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> <o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> // Testcase showing that llvm-ir is not able to
<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> // differentiate between following two cases.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> // (restrict outside ('0') or inside ('1') the loop)<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> <o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> // Toggle '0' to '1' and see that the metadata
<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> // (!noalias, !alias.scope) remains similar.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> #if 0<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> static __attribute__((always_inline))<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> void add_element(int* restrict pDest, int* restrict pA, int* restrict pB) {<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> *pDest = *pA+*pB;<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> <o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> void test_add_array01(int* pDest, int* pA, int* pB) {<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> for (int i=0; i<SIZE; ++i) {<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> // restrict only holds per iteration, not across iterations<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> add_element(pDest++, pA++, pB++);<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> #else<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> static __attribute__((always_inline))<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> void add_array(int* restrict pDest, int* restrict pA, int* restrict pB) {<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> for (int i=0; i<SIZE; ++i) {<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> *pDest++=*pA++ + *pB++; // restrict holds across iterations<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> <o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> void test_add_array02(int* pDest, int* pA, int* pB) {<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> // restrict info is similar to 'test_add_array01', no differentiation possible<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> add_array(pDest, pA, pB);<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> #endif<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> <o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> <o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">== 'local restrict' patches ==<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Around 2014/2015, Hal Finkel proposed a number of patches, fixing some of the<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">observed issues with restrict, while also adding support for local restrict [4].<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Hal had the following goals:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Fix the issue with inlined functions, where restrictness inside vs outside<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> the loop body was not decidable<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Enable support for local restrict<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Some of the initial patches have been added to LLVM in the meantime. But, a<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">number of main changes are still pending, due to slow review progress, but also<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">due to a number of issues that popped up in the meantime.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">How it works:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Whenever a value is assigned to a restrict pointer, a 'llvm.noalias %p,<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> metadata !x' intrinsic is put between the assignment and the value.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> '!x' is a list of a single scope id that represents the specific restrict pointer.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Whenever a memory instruction is produced, the '!noalias !y' metadata scope is<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> added.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> '!y' is a list of all scoped id's that are active at the moment of the memory<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> instruction.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* The combination of the intrinsic and the !noalias scope allows to check if two<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> memory accesses can/cannot alias according to the restrict rules.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Observed issues:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Performance:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** The intrinsic blocks certain optimizations.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** In some combinations of local restrict and inlining, the restrictness is<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> lost, resulting in slow code.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Correctness:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** Some optimizations (like LSR) eliminate the intrinsics, possibly resulting<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> in wrong code.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** Loop unrolling can result in wrong code. [6]<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">== A way out ==<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">I had the following goals when trying to fix the observed issues with the local<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">restrict implementation:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Fix the known issues wrt to the local restrict implementation. Both<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> correctness (must) and performance (as much as possible)<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Make it safe(r) against the unexpected effect of (new) optimization passes:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> prefer slow code over incorrect code<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Make it easy to add support for restrict member pointers.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Make it feasible to implement the 'alias_set' proposal (n4150) [3]<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">High level strategy:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Keep most of the restrictness annotations out the way of the normal program<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> flow, except when it is needed for correctness.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Follow the restrict specification [2] to the letter. More precisely:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** Track the declaration of a 'object P'.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** Each distinct restrict pointer 'object P' points to its own set of objects<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> (within the valid scope).<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> As such, restrictness is introduced when using a restrict pointer<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> (not when assigning it).<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> Example:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> void foo(int* restrict rP, int* restrict * pRP) {<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> int* p2=rP; // 'using rP' introduces restrictness<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> *p2=42; // dereferencing a pointer based on a restrict pointer<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> rP=&someInt; // assignment does not introduce (additional) restrictness<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> int* p3=*pRP; // 'using *pRP' introduces restrictness<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> *p3=43; // dereferencing a pointer based on a restrict pointer<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** Track the 'based on' expressions in an accurate way.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">NOTE: Part of those ideas have been discussed in small group during 2 BOF<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> sessions during the 2018 US LLVM Conference.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">The following sections explain how to come to a full set of intrinsics that should<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">support restrict:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">(A) The Basics<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">In principle, two intrinsics should be sufficient:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* 'llvm.noalias.decl %p.alloc, metadata !Scope' intrinsic:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** indicates at what place in the program a restrict pointer has been declared.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** %p.alloc: represents the alloca associated with the declaration.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** !Scope: metadata that represents a unique scope, associated with this specific<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> declaration.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** NOTE: the llvm.noalias.decl intrinsic can normally not be moved outside<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> loops. Its purpose is to identify the freedom that a restrict pointer has<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> wrt to the loop bodies and other blocks. As such it helps to resolve<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> problems as seen in [6] and [7].<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* 'llvm.noalias %p, %p.decl, %p.addr' intrinsic:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** created when a restrict pointer object P is _read_.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> It is used to track the 'based-on' dependency.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** %p: is the pointer value that was read. This is also the value that the<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> intrinsic returns.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** %p.decl: refers to the 'llvm.noalias.decl' that is associated with the<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> restrict pointer.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** %p.addr represents the address of 'object P'<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** NOTE: sometimes the declaration is not known upfront, in that case '%p.decl'<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> is 'null'. After inlining and/or optimizations, it can be possible to infer<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> the llvm.noalias.decl (based on %p.addr).<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Example A:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> int foo(int* pA, int* pB) {<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> int * restrict rpA=pA;<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> *rpA=42;<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> *pB=99;<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> return *rpA;<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> (pseudo LLVM-IR)<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> define @foo(i32* pA, i32* pB) {<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> %rpA.address = alloca i32*<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> %rpA.decl = llvm.noalias.decl %rpA.address, !metadata !10 ; declaration of a restrict pointer<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> store i32* %pA, %rpA.address, !noalias !10<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> %rpA = load i32* %rpA.address, !noalias !10<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> %rpA.1 = i32* llvm.noalias %rpA, %rpA.decl, %rpA.address ; reading of a restrict pointer<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> store i32 42, %rpA.1, !noalias !10<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> store i32 99, %pB, !noalias !10<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> %1 = load i32 %rpA.1, !noalias !10<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> ret i32 %1<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">NOTES:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* this is slightly different from Hal Finkel's approach, where the<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> 'llvm.noalias' intrinsics is used when storing a value in the pointer.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* this representation suffers from possible blocking of optimizations. But, when<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> 'llvm.noalias' is made too transparent, it can result in wrong code.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Summary:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias.decl %p.alloc, metadata !Scope<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias %p, %p.decl, %p.addr<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">(B) The side channel<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">We introduce a 'side channel' for load/store instructions. The idea is that we<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">use the 'pointer operand' for normal pointer computations, and the 'side channel<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">operand' for restrict related dependencies. Optimizations (like LSR) can modify the<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">'pointer operand' as they see fit. As long as the 'side channel operand' is not<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">touched, we are still able to deduce the restrict related information. When an<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">optimization introduces a load/store without a side channel operand, we fall<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">back to the fail-safe 'worst case'.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">NOTE: the name 'side channel' comes from the need to track the restrict information<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> for load/store instructions 'on the side'. In a way that is hidden for normal<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> optimizations.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Although the actual pointer computations can be removed in the side channel, it<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">can still contain PHI nodes and 'select' instructions.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">As it is hard to track the usage of a pointer in clang, we will work on llvm-IR<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">level. Because of that the annotations exist in two states:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* Before 'noalias propagation'<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> This state is produced by clang. It is similar to (A). The main difference is<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> that the 'llvm.noalias' intrinsic becomes completely opaque for optimizations.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* After 'noalias propagation'<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> A 'noalias propagation' pass is introduced that converts the llvm-IR code to<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> the second state:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** llvm.noalias intrinsics are converted into 'llvm.side_noalias' intrinsics<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** their usage is removed from the main pointer computations, and moved to the<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> side channel of load/store instructions<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** When a pointer depending on a llvm.noalias intrinsic is passed as an<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> argument, returned from a function or stored into memory, we introduce a<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> 'llvm.noalias.arg.guard'. This combines the original pointer computation<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> with the side channel information. After inlining, it is also used to<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> propagate the noalias information to the load/store instructions.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">So, we now have two extra intrinsics:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* 'llvm.side.noalias %side.p, %p.decl, %p.addr' intrinsic:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** provides restrict information to a side channel.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** %side.p: tracks the side channel associated with the pointer value that was read.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** %p.decl: refers to the 'llvm.noalias.decl' that is associated with the<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> restrict pointer.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** %p.addr: represents the address of 'object P'.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* 'llvm.noalias.arg.guard %p, %side.p' intrinsic:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** combines pointer and restrict information when a restrict pointer value<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> escapes. It is normally used for function arguments, returns, or stores to<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> memory.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** %p tracks the pointer computation<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** %side.p tracks the side channel associated with the pointer value<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Example B: After noalias propagation, example A becomes:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> (pseudo LLVM-IR)<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> define @foo(i32* pA, i32* pB) {<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> %rpA.address = alloca i32*<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> %rpA.decl = llvm.noalias.decl %rpA.address, !metadata !10 ; declaration of a restrict pointer<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> store i32* %pA, %rpA.address, noalias_sidechannel undef, !noalias !10<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> %rpA = load i32* %rpA.address, noalias_sidechannel undef, !noalias !10<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> %side.rpA.1 = i32* llvm.side.noalias %rpA, %rpA.decl, %rpA.address ; reading of a restrict pointer<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> store i32 42, %rpA, noalias_sidechannel %side.rpA.1, !noalias !10<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> store i32 99, %pB, noalias_sidechannel undef, !noalias !10<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> %1 = load i32 %rpA, noalias_sidechannel %side.rpA.1, !noalias !10<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> ret i32 %1<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Summary:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias.decl %p.alloc, metadata !Scope<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias %p, %p.decl, %p.addr<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.side.noalias %side.p, %p.decl, %p.addr<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias.arg.guard %p, %side.p<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">(C) Optimizations that eliminate the location of 'object P' from the stack<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">When SROA eliminates a local variable, we do not have an address for 'object P'<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">anymore (the alloca is removed and %p.addr becomes 'null'). At that moment we<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">must depend on the '!Scope' metadata to differentiate restrict objects.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">For convenience, we also add this information to the llvm.noalias and<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">llvm.side.noalias intrinsics.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">It is also possible that a single variable declaration contains multiple<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">restrict pointers (think of a struct containing multiple restrict pointers, or<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">an array of restrict pointers). Instead of introducing new scopes when this<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">happens, we introduce an extra object ID (objId) parameter for<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">llvm.noalias.decl, llvm.noalias and llvm.side.noalias. This can be thought of as<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">the 'offset in the variable'.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Summary:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias.decl %p.alloc, i32 objId, metadata !Scope<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias %p, %p.decl, %p.addr, i32 objId, metadata !Scope<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.side.noalias %side.p, %p.decl, %p.addr, i32 objId, metadata !Scope<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias.arg.guard %p, %side.p<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">For alias analysis, this means that two llvm.side.noalias intrinsics represent a<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">different 'object P0', 'object P1', if:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* %p0.addr and $p1.addr are different<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* or, objId0 and objId1 are different<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* or, !Scope0 and !Scope1 are different<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">(D) Optimizing a restrict pointer pointing to a restrict pointer<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Example:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> int * restrict * restrict ppA = ...;<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> int * restrict * restrict ppB = ...;<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> **ppA=42;<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> **ppB=99;<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> return **ppA; // according to C99, 6.7.3.1 paragraph 4, **ppA and **ppB are not aliasing<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">In order to allow this optimization, we also need to track the !noalias scope<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">where the 'llvm.noalias' intrinsic was introduced. The %p.addr parameter in the<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">'llvm.side.noalias' will also get a noalias side channel, through the<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">%side.p.addr argument.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">In short, we treat the 'llvm.noalias' and 'llvm.side.noalias' intrinsics as if<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">they are a memory operation.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Summary:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias.decl %p.alloc, i32 objId, metadata !Scope<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias %p, %p.decl, %p.addr, i32 objId, metadata !Scope, !noalias !visible_scopes<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.side.noalias %side.p, %p.decl, %p.addr, %side.p.addr, i32 objId, metadata !Scope, !noalias !visible_scopes<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias.arg.guard %p, %side.p<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">For alias analysis, this means that two llvm.side.noalias intrinsics represent a<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">different 'object P0', 'object P1', if:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* %p0.addr and $p1.addr are different<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* or, objId0 and objId1 are different<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* or, !Scope0 and !Scope1 are different<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* or we can prove that (%p0.addr, %side.p0.addr, !visible_scopes0) and<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> (%p1.addr, %side.p1.addr, !visible_scopes1) do not alias for both intrinsics.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> (as if we treat each of the two 'llvm.side.noalias' as a 'store to %p.addr'<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> and we must prove that the two stores do not alias; also see [8], question 2)<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">(E) 'unknown function' scope<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">When the declaration of a restrict pointer is not visible, C99, 6.7.3.1<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">paragraph 2, says that the pointer is assumed to start living from 'main'.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">This case can be handled by the 'unknown function' scope, which is annotated to<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">the function itself. This can be treated as saying: the scope of this restrict<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">pointer starts somewhere outside this function. In such case, the 'llvm.noalias'<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">and 'llvm.side.noalias' will not be associated with a 'llvm.noalias.decl'. It is<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">possible that after inlining, the scopes can be refined to a declaration which<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">became visible.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">For convenience, each function can have its own unknown scope specified by a<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">'noalias !UnknownScope' metadata attribute on the function itself.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">(F) Aggregate copies<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Restrictness is introduced by 'reading a restrict pointer'. It is not always<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">possible to add the necessary 'llvm.noalias' annotation when this is done. An<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">aggregate containing one or more restrict pointers can be copied with a single<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">load/store pair or a llvm.memcpy. This makes it hard to track when a restrict<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">pointer is copied over.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">For this, a final intrinsic is introduced: 'llvm.noalias.copy.guard':<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* 'llvm.noalias.copy.guard %p.addr, %p.decl, metadata !indices, metadata !Scope' intrinsic<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** Guards a %p.addr object that is copied as a single aggregate or llvm.memcpy<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** %p.addr: the object to guard<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** %p.decl: (when available), the llvm.noalias.decl associated with the object<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** !indices: The !indices refers to a metadata list. Each element of the list<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""> refers to a set of indices where a restrict pointer is located.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">** !Scope: the declaration scope of %p.decl<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">This information allows SROA to introduce the needed 'llvm.noalias' intrinsics<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">when a struct is split up.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Summary:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* potential '!noalias !UnknownScope' annotation at function level<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias.decl %p.alloc, i32 objId, metadata !Scope<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias %p, %p.decl, %p.addr, i32 objId, metadata !Scope, !noalias !visible_scopes<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.side.noalias %side.p, %p.decl, %p.addr, %side.p.addr, i32 objId, metadata !Scope, !noalias !visible_scopes<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias.arg.guard %p, %side.p<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* llvm.noalias.copy.guard %p.addr, %p.decl, metadata !indices, metadata !Scope<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">(G) Optimization passes<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">For correctness, some optimization passes must be aware of the noalias intrinsics:<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">inlining [7], unrolling [6], loop rotation, ... Whenever a body is duplicated that<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">contains a llvm.noalias.decl, it must be decided how that duplication must be done.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Sometimes new unique scopes must be introduced, sometimes not.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">Other optimization passes can perform better by knowing about the side channels: when<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">new load/store instructions are introduced, adding side channel information can result<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">in better alias analysis for those load/stores.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">== c++ alias_set ==<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">With this framework in place, it should be easy to extend it to support the<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">'alias_set' proposal [3]. This can be done by tracking a separate 'universe<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">object', instead of 'object P'.<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">== References ==<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* [1] https://en.wikipedia.org/wiki/Restrict<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* [2] WG14 N1256: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf (Chapter 6.7.3.1 Formal definition of restrict)<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* [3] WG21 N4150: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4150.pdf<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* [4] https://reviews.llvm.org/D9375 Hal Finkel's local restrict patches<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* [5] https://bugs.llvm.org/show_bug.cgi?id=39240 "clang/llvm looses restrictness, resulting in wrong code"<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* [6] https://bugs.llvm.org/show_bug.cgi?id=39282 "Loop unrolling incorrectly duplicates noalias metadata"<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* [7] https://www.godbolt.org/z/cUk6To "testcase showing that llvm-ir is not able to differentiate if restrict is done inside or outside the loop"<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* [8] DR294: http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_294.htm<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New"">* [9] WG14 N2250: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2260.pdf Clarifying the restrict Keyword v2<o:p></o:p></span></p>
<p class="MsoPlainText"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoPlainText"><o:p> </o:p></p>
</div>
</body>
</html>