Cranmer, Joshua via llvm-dev
2021-Jun-01 16:10 UTC
[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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210601/7b6b9eee/attachment-0001.html>
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210602/119a8998/attachment.html>