<div dir="ltr">Hi Zhang,<div><br></div><div>What has been explained in previous replies is that at *compile-time*, you don't know whether at *runtime* argc % 2 == 0 will be true or false. So, you don't know whether __builtin_save(yyy) or __builtin_save(zzz) will be reached first. Are you maybe interested in *text order* (I don't know if this is a standard term but I mean the order at which entities appear on the text of the source file) instead of *execution order* (the order at which entities are reached during the dynamic execution)?</div><div><br></div><div>To make that clear, consider this:</div><div>```</div><div>for (int i = 0; i < 100; ++i) {</div><div>  if (i > 0) {</div><div>    foo();  // executed at the 2nd iteration</div><div>  }</div><div>  bar(); // executed at the 1st iteration</div><div>}</div><div>```</div><div><br></div><div>`foo()` is executed *after* `bar()` but appears *before* it in text order.</div><div><br></div><div>Best,</div><div>Stefanos</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Τρί, 1 Ιουν 2021 στις 7:21 μ.μ., ο/η Zhang via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> έγραψε:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><font>Hi:</font></div><div>Basically in our backend, some domain specific information are encoded as calls to a custom intrinsic. For example our semantic supports encoding a struct in multiple calls (It's a DSL for JIT-Like operations, in case you are wondering), as following:</div><div><br></div><div>```</div><div>int main(int argc){</div><div> uint32_t xxx = 0x1;</div><div>uint16_t yyy = 0x1;</div><div>uint16_t zzz = 0x1;</div><div> __builtin_save(xxx);</div><div> if(argc % 2 ==0){</div><div>     __builtin_save(yyy);</div><div>   }</div><div>else{</div><div> __builtin_save(zzz);</div><div>}</div><div>........</div><div>}</div><div><br></div><div>What I'm trying to accomplish here is basically to iterate the IR from entry and reconstruct the structure layout:</div><div>```</div><div>{</div><div> uint32_t xxx;</div><div> uint16_t yyy;</div><div>}</div><div>```</div><div><br></div><div>I'm aware directly using a StructType would be a way much simpler solution, however this is currently limited by other parts in our usage pipeline.</div><div><br></div><div>Is this feasible to implement at IR Level? Or am I better off with libClang based solutions?</div><div><br></div><div>Thanks a lot for the info.</div><div><br></div><div><br></div><div>Zhang</div><div><u></u><div> </div><div> </div><div style="color:rgb(0,0,0)"><div style="font-size:12px;font-family:"Arial Narrow";padding:2px 0px">------------------ Original ------------------</div><div style="font-size:12px;background:rgb(239,239,239);padding:8px"><div id="gmail-m_1038400784812939903menu_sender"><b>From: </b> "Cranmer, Joshua"<<a href="mailto:joshua.cranmer@intel.com" target="_blank">joshua.cranmer@intel.com</a>>;</div><div><b>Date: </b> Wed, Jun 2, 2021 00:12 AM</div><div><b>To: </b> "Zhang"<<a href="mailto:admin@mayuyu.io" target="_blank">admin@mayuyu.io</a>>; "llvm-dev"<<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>; </div><div></div><div><b>Subject: </b> RE: [llvm-dev] "Ordered" Instruction Iterator?</div></div><div> </div><div><div id="gmail-m_1038400784812939903tmpcontent_res"></div>







<div>
<p class="MsoNormal">As David points out, there’s some ambiguity as to what “ordered” means with respect to basic blocks. There are three main different traversals that LLVM automatically provides, and which one is appropriate depends on your use case.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">The first is regular traversal over all basic blocks in the function:<u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Consolas">for (auto &BB : F) {}<u></u><u></u></span></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">This will iterate over every basic block in the function in an arbitrary order (roughly, the order that they are actually laid out during emission), and the only guarantee you have is that the entry block is first.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Alternatively, you can choose to use the depth-first traversal:<u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Consolas">for (auto BB : depth_first(F)) {}<u></u><u></u></span></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">This will execute a depth-first preorder, which means every basic block will be visited after one (but not necessarily all) of its predecessors have been visited. This is sufficient to guarantee that you visit every dominator of a block
 before you visit the block itself.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Another alternative is the reverse postorder traversal (ReversePostOrderTraversal is actually expensive to compute, so you may want to save it to a variable if you intend to do multiple traversals in a pass):<u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Consolas">for (auto BB : ReversePostOrderTraversal(F)) {}<u></u><u></u></span></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Reverse post-order visits every block after all of its predecessors (excluding loops) have been visited. From the short snippet of an explanation you have provided, this may suffice for your use-case. However, it may also be overkill for
 your needs, and you might instead investigate a cheaper alternative traversal.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<div style="border-top:none;border-right:none;border-bottom:none;border-left:1.5pt solid blue;padding:0in 0in 0in 4pt">
<div>
<div style="border-right:none;border-bottom:none;border-left:none;border-top:1pt solid rgb(225,225,225);padding:3pt 0in 0in">
<p class="MsoNormal"><b>From:</b> llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@lists.llvm.org</a>> <b>On Behalf Of
</b>Zhang via llvm-dev<br>
<b>Sent:</b> Monday, May 31, 2021 22:43<br>
<b>To:</b> llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>Subject:</b> [llvm-dev] "Ordered" Instruction Iterator?<u></u><u></u></p>
</div>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">Hi:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">In my analysis Pass, I'm trying to visit CallInsts to a special Intrinsic, in the order that they'll be executed, starting from the EntryBlock.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">My naive initial assumption was to start from entryBlock and custom handle Br Instructions, but apparently this doesn't work well with more complicated CFGs like loop or Switch.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Is there any LLVM builtin infrastructure that could be used for this? Any hint would be appreciated.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Zhang<u></u><u></u></p>
</div>
</div>
</div>


</div></div><u></u></div>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>