[llvm-dev] "Ordered" Instruction Iterator?

[Stefanos Baziotis via llvm-dev]

Hi Zhang,

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)?

To make that clear, consider this:
```
for (int i = 0; i < 100; ++i) {
  if (i > 0) {
    foo();  // executed at the 2nd iteration
  }
  bar(); // executed at the 1st iteration
}
```

`foo()` is executed *after* `bar()` but appears *before* it in text order.

Best,
Stefanos

Στις Τρί, 1 Ιουν 2021 στις 7:21 μ.μ., ο/η Zhang via llvm-dev <
llvm-dev at lists.llvm.org> έγραψε:

> Hi:
> 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:
>
> ```
> int main(int argc){
>  uint32_t xxx = 0x1;
> uint16_t yyy = 0x1;
> uint16_t zzz = 0x1;
>  __builtin_save(xxx);
>  if(argc % 2 ==0){
>      __builtin_save(yyy);
>    }
> else{
>  __builtin_save(zzz);
> }
> ........
> }
>
> What I'm trying to accomplish here is basically to iterate the IR from
> entry and reconstruct the structure layout:
> ```
> {
>  uint32_t xxx;
>  uint16_t yyy;
> }
> ```
>
> 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.
>
> Is this feasible to implement at IR Level? Or am I better off with
> libClang based solutions?
>
> Thanks a lot for the info.
>
>
> Zhang
>
>
> ------------------ Original ------------------
> *From: * "Cranmer, Joshua"<joshua.cranmer at intel.com>;
> *Date: * Wed, Jun 2, 2021 00:12 AM
> *To: * "Zhang"<admin at mayuyu.io>; "llvm-dev"<llvm-dev at lists.llvm.org>;
> *Subject: * RE: [llvm-dev] "Ordered" Instruction Iterator?
>
>
> 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.
>
>
>
> The first is regular traversal over all basic blocks in the function:
>
> for (auto &BB : F) {}
>
>
>
> 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.
>
>
>
> Alternatively, you can choose to use the depth-first traversal:
>
> for (auto BB : depth_first(F)) {}
>
>
>
> 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.
>
>
>
> 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):
>
> for (auto BB : ReversePostOrderTraversal(F)) {}
>
>
>
> 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.
>
>
>
> *From:* llvm-dev <llvm-dev-bounces at lists.llvm.org> *On Behalf Of *Zhang
> via llvm-dev
> *Sent:* Monday, May 31, 2021 22:43
> *To:* llvm-dev <llvm-dev at lists.llvm.org>
> *Subject:* [llvm-dev] "Ordered" Instruction Iterator?
>
>
>
> Hi:
>
>
>
> 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.
>
> 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.
>
>
>
> Is there any LLVM builtin infrastructure that could be used for this? Any
> hint would be appreciated.
>
>
>
>
>
> Zhang
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210601/52ec8de5/attachment.html>