This patch add mayContainUnboundedCycle helper function which checks whether a function has any cycle which we don't know if it is bounded or not.
Loops with maximum trip count are considered bounded, any other cycle not.
It also contains some fixed tests and some added tests contain bounded and
unbounded loops and non-loop cycles.
Details
Details
Diff Detail
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
There are a very large number of changes, so older changes are hidden. Show Older Changes
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2539 | the while version was making an infinte loop error , I think getParentLoop when there was no parent anymore it returned the same loop and not null so i fixed it by this first check . | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2539 | oh i didn't see this continue part so i think now it is the one that makes that , i will edit it to the while version again :) | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2539 | :) | |
Comment Actions
@jdoerfert I have found examples in the willreturn.ll file for explicit tests for bounded and unbounded loops and I fixed them , does we need to add more complex examples like a bounded loop inside unbounded loop or this is redundant and not important ?
Comment Actions
I think you can first of all upload your diff and it will be easier to comment on what is missing. Some tests you can add (or check if there are some already in willreturn.ll) are basically stressing the algorithm.
That e.g. means add a quite deep loop. Add a non-loop SCC inside a loop. Add a loop that has max trip count inside another with max trip count (so you can check the moving upwards).
Comment Actions
Yes. Please keep the diff up to date so it is easier to follow.
[ Btw. if someone is up for it I have already the next extension in mind. though we can tackle that once this one is done ]
Comment Actions
I'm up for it. Although I'd like to wait for Omar to finish this one and see if he thinks he can tackle the next (assuming he wants to). :)
Comment Actions
I'm up for it. Although I'd like to wait for Omar to finish this one and see if he thinks he can tackle the next (assuming he wants to). :)
I'm ready for it :)
Comment Actions
I added a bunch of comments. Mostly minor. I think this is almost done and I like how it turned out. Once the comments are addressed I'm fine with this, @baziotis feel free to accept then.
The next step to improve willreturn is actually to allow loops with unknown bounds, e.g., link-list traversals but also SCCs that are not loops. During initialize we collect all the ones that might be endless, and in the updateImpl we have to "justify" why they are not. The justification criterion is: they do not contain any synchronizing instruction. AANoSync can help with identifying those ;)
@omarahmed Let me know if that is something you want to look into (eventually). If so, we can talk about it more.
[EDIT: Now that I think about it for another second, we should probably split that logic I describe above into a new abstract attribute, e.g., AALoopInformation. We also need to sync up with @uenoku, I remember vaguely that he looked into something at similar at some point but it's all pretty foggy...]
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2510 | Nit: No braces. | |
| 2511 | I have the feeling there is something missing. What if there is an outer SCC with no loop that is as big as the SCC? I think you need a matching loop with max trip count (not even constant btw.) for each SCC. That is, after the do-loop ended, check if L is null or not. If it is, we did not find a matching loop. | |
| 2514 | Nit: Move the decleration of SCCBBs here (where it is used). | |
| 2520 | Nit: Maybe for (auto &It : make_range(scc_begin(&F), scc_end(&F))) | |
| 2530 | Style: No else after return. | |
| 2533 | Style: go over the comments and make them all sentences, e.g., capital starting letter, dot at the end, dot in between sentences, etc. | |
| llvm/test/Transforms/Attributor/willreturn.ll | ||
| 596 | I like the tests a lot. Can we add one or two more with irreducible control, hence SCCs that are not (natural) "loops". | |
Comment Actions
Ok, yes.
The next step to improve willreturn is actually to allow loops with unknown bounds, e.g., link-list traversals but also SCCs that are not loops. During initialize we collect all the ones that might be endless, and in the updateImpl we have to "justify" why they are not. The justification criterion is: they do not contain any synchronizing instruction. AANoSync can help with identifying those ;)
@omarahmed Let me know if that is something you want to look into (eventually). If so, we can talk about it more.[EDIT: Now that I think about it for another second, we should probably split that logic I describe above into a new abstract attribute, e.g., AALoopInformation. We also need to sync up with @uenoku, I remember vaguely that he looked into something at similar at some point but it's all pretty foggy...]
I may be missing something because I'm not familiar with synchronizing instructions but why does that guarantee that a loop will end? Or why can we assume it will end?
I was reading the C11 standard:
An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate.
That is, basically we can assume a loop ends (even if it doesn't actually) if it is side-effect free. That is, it has no sync instructions, no read/write instructions and no volatile accesses.
I don't know if we follow the C11 standard but don't we fill only 1 of 3 if we only test for synchronizing instructions?
Comment Actions
C/C++ atomics and volatile are considered synchronization, according to AANoSync, so we are good on that front I think. Or did you mean something else?
The one thing we should do however is start a discussion about a no-forward-process-guarantee attribute on llvm-dev. People that do not come from C/C++ already asked for that (https://bugs.llvm.org/show_bug.cgi?id=965). If you read the bug comments and look at the dates, we have that problem for a while and I think the function attribute is the cleanest solution here.
Comment Actions
That's what I figured by reading AANoSync but I had some wrong terminology in my head for the term "atomic". So, yes, you're right.
The one thing we should do however is start a discussion about a no-forward-process-guarantee attribute on llvm-dev. People that do not come from C/C++ already asked for that (https://bugs.llvm.org/show_bug.cgi?id=965). If you read the bug comments and look at the dates, we have that problem for a while and I think the function attribute is the cleanest solution here.
no-forward-process-guarantee is basically the attribute version of containsPossiblyEndlessLoop() right (when it returns true) ? (Although, I believe we should name this with process -> progress).
I don't quite get why this will be helpful though. I got that Reid Kleckner proposed forward-progress-guarantee so that we can put into functions in which we can remove infinite loops with no side-effects.
Btw, the search for some loops may need to happen in AAUB, since it is considered UB if I understood correctly.
Comment Actions
So infinite loops without progress are UB, I think, but loops that might be infinite without progress are not necessarily. We can remove the latter and insert an unreachable for UB as always.
The attribute would actually allow or prevent the above, deepening which default we choose. Basically opt-in or out of the forward progress which enables or disables the proposed reasoning.
Comment Actions
Me too, because of the C11 standard excerpt I quoted above.
but loops that might be infinite without progress are not necessarily. We can remove the latter and insert an unreachable for UB as always.
Yes, that's what I meant. Assuming that here you meant "with", not "without" and "former", not "latter". Or otherwise I missed something.
The attribute would actually allow or prevent the above, deepening which default we choose. Basically opt-in or out of the forward progress which enables or disables the proposed reasoning.
Oh, ok. So, my assumption was:
- forward-progress would mean: You can remove side-effect-free infinite loops. One implication of that is: This function _definitely_ forwards progress although it might never return.
This is also how I think people in llvm-dev wanted to use that: If you're compiling a C/C++ function, put this attribute so you can do this optimization. Otherwise, don't, so you can't.
- On the other hand, no-forward-progress-guarantee I think does not make sense (because of its name) to mean: You can't remove such loops. I got that it means: "This function may get into a side-effect-free infinite loop".
Which is a piece of information nonetheless.
All in all, definitely I'm not the one to decide but I would be glad if you could clarify which of the above are planned (or you plan) to be added.
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2520 | I am kind of stuck in using hasLoop function with using these method for looping :) , so how could I change It( vector<Block*>) to SCC_iter<Function *> type | |
Comment Actions
Assuming forward-progress-guarantees, as we do in LLVM now, you can:
- Remove a loop that has no side-effect/sync, regardless of the trip count.
- Replace a loop that has no side-effect/sync with an unreachable, if it is proven endless.
The second transformation is "stronger" but also more restrictive. For example,
while(c) {}cannot be replaced with unreachable but can be removed if you don't know anything about c. You
can replace the loop with llvm.assume(!c) if you want.
The attribute would actually allow or prevent the above, deepening which default we choose. Basically opt-in or out of the forward progress which enables or disables the proposed reasoning.
Oh, ok. So, my assumption was:
- forward-progress would mean: You can remove side-effect-free infinite loops. One implication of that is: This function _definitely_ forwards progress although it might never return.
This is also how I think people in llvm-dev wanted to use that: If you're compiling a C/C++ function, put this attribute so you can do this optimization. Otherwise, don't, so you can't.
- On the other hand, no-forward-progress-guarantee I think does not make sense (because of its name) to mean: You can't remove such loops. I got that it means: "This function may get into a side-effect-free infinite loop".
Which is a piece of information nonetheless.
no-forward-progress-guarantee would effectively mean that you cannot remove or replace loops that do not have side-effects/syncs. On way of thinking of this is: (non-)termination becomes observable and threads might be interrupted by events even if there is no direct control flow path.
All in all, definitely I'm not the one to decide but I would be glad if you could clarify which of the above are planned (or you plan) to be added.
I'm not necessarily favoring a default but we need to propose this as an RFC on the list and see where people stand.
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2520 | Never mind then ;) | |
Comment Actions
I just saw, the commit subject and message needs to be written though. Explaining what this patch does.
Comment Actions
[Attributor]Detect SCCs with unbounded cycles
- Updating D74691: [Attributor] add some pattern to containsCycle #
- Enter a brief description of the changes included in this update.
- The first line is used as subject, next lines as comment. #
- If you intended to create a new revision, use:
- $ arc diff --create
This patch implements containsUnboundedCycle which checks for unbounded cycle
which is either a loop that does not have a maximal trip count or any other
cycle.
It contains some fixes for willreturn tests and addition of bounded
and unbounded loop tests.
Comment Actions
Ok, clearer, thanks!
The attribute would actually allow or prevent the above, deepening which default we choose. Basically opt-in or out of the forward progress which enables or disables the proposed reasoning.
Oh, ok. So, my assumption was:
- forward-progress would mean: You can remove side-effect-free infinite loops. One implication of that is: This function _definitely_ forwards progress although it might never return.
This is also how I think people in llvm-dev wanted to use that: If you're compiling a C/C++ function, put this attribute so you can do this optimization. Otherwise, don't, so you can't.
- On the other hand, no-forward-progress-guarantee I think does not make sense (because of its name) to mean: You can't remove such loops. I got that it means: "This function may get into a side-effect-free infinite loop".
Which is a piece of information nonetheless.
no-forward-progress-guarantee would effectively mean that you cannot remove or replace loops that do not have side-effects/syncs. On way of thinking of this is: (non-)termination becomes observable and threads might be interrupted by events even if there is no direct control flow path.
Yes, it makes sense.
All in all, definitely I'm not the one to decide but I would be glad if you could clarify which of the above are planned (or you plan) to be added.
I'm not necessarily favoring a default but we need to propose this as an RFC on the list and see where people stand.
Me neither, and I'm positive to the RFC of course. If I can help in any way, ping me. I'll definitely take part in the review. :)
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2508 | There's https://reviews.llvm.org/D74801. If it gets committed before this, I'll notify you to just change the naming. | |
| 2517 | To me, that's a little bit inaccurate. It seems like this if checks if the SCC is a loop or not. But that's actually the whole code that follows. | |
| 2519–2520 | The SCC might have a loop inside, but it might not be a loop itself. I propose something like: If L is nullptr, we found no loop that matches exactly the number of blocks of the SCC and so the SCC is not a loop Feel free to revise it but still remain accurate. :) | |
| 2521–2523 | One note is that we get the innermost loop with getLoopFor() rather than the outermost. Also, the part about the loop cycle was unclear to me. Still, I feel breaking it down into 3 cases is clearer but here's another take: L is the innermost loop that has a common block with the SCC. Since a loop is always an SCC, if their number of blocks are equal, the SCC is a loop - specifically, L. Otherwise, there are 2 cases: - If the SCC has less blocks, then it is definitely not a loop. - If it has more, then we can't decide since the SCC can be a parent loop of L. So, we perform the same test for the parent of L. | |
Comment Actions
You don't need this part anywhere.
This patch implements containsUnboundedCycle which checks for unbounded cycle
which is either a loop that does not have a maximal trip count or any other
cycle.It contains some fixes for willreturn tests and addition of bounded
and unbounded loop tests.
That commit message I think is very good. It's good if you put it in the summary as well.
Comment Actions
[Attributor]Detect SCCs with unbounded cycles
This patch implements containsUnboundedCycle which checks for unbounded cycle
which is either a loop that does not have a maximal trip count or any other
cycle.
It contains some fixes for willreturn tests and addition of bounded
and unbounded loop tests.
Comment Actions
The patch description is not very useful.
It should actually explain the patch, and why that is the correct solution.
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2494 | The old comment is strictly more understandable. | |
| 2511 | s/if/whether/ | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2494 | Yeah, the addition that we check inside a function would be good. Otherwise, I think the new one is clearer on what it is considered an unbounded cycle in this case. | |
Comment Actions
I'm in the unpleasant position to tell you that the method I proposed is wrong. SCCIterator uses Tarjan's algorithm which for some reason, I remembered it finds all strongly-connected components but actually, it finds only maximal.
That means, if a loop has an SCC inside it, we'll never find it since the loop is the maximal SCC. That probably means that we have to fall-back to the method that Johannes had proposed:
As before, we identify all cycles via the depth-first search and the visited set. If a cycles is found we did bail before but now we ask LI & SE instead. If they say we found a proper loop header of a loop with a bounded trip count we can ignore that cycles and continue exploring.
I'm really sorry for that. I'll try to think if anything better can be done.
Edit: Let's not forget of course: A big thanks to @Meinersbur for pointing this out.
Comment Actions
that's fine , no problem :D
I think i can move faster now as i know the small mistakes i have done till now from the great reviews :)
But if it finds only the maximum ones why it hadn't returned willreturn here , as it shouldn't have seen the while inside
; int non_loop_inside_loop(int n) {
; int ans = 0;
; for (int i = 0; i < n; i++) {
; while (1)
; ans++;
; }
; return ans;
; }Comment Actions
It's good to refer to the LLVM IR, rather than the C/C++ because they can have multiple LLVM IR translations. Just to be sure we're talking about the same thing. :)
In this case, I assume you meant the relevant test case in willreturn.ll. If you put it in a file on its own and run it through the Attributor, with a couple of prints, you'll
see that NoAnalysis is true (btw, I recommend that you try to answer questions by following the code - it's always a learning experience).
I don't know why and that's a good question (on another topic, but still). Interestingly, both LI and SE are null. So, for some reason, for this function, we couldn't
get either of those analyses. I'll try to find some time to check tomorrow.
Comment Actions
btw, I recommend that you try to answer questions by following the code - it's always a learning experience).
Since we took that road, let's have a little more fun. Let's start simple by printing the SCCs we get. A simple way to do that is with sth like:
for (scc_iterator<Function *> It = scc_begin(&F), IE = scc_end(&F); It != IE;
++It) {
const std::vector<BasicBlock *> &SCCBBs = *It;
for (BasicBlock *BB : SCCBBs) {
dbgs() << *BB << "\n";
}
dbgs() << "----- END -----\n\n\n\n\n";
}But, we can actually do better if we take a graphical view of the CFG, with view-cfg. You can do that with sth like:
./bin/opt -view-cfg test.ll
Assuming that you are in the llvm-project dir, that you have built opt and that your file is test.ll. Now, this will generate a .dot file.
This is a special "graphics" format for which we should not care about right now. If you do that, you'll probably see something like:
... Writing '/tmp/cfgnon_loop_inside_loop-a0c3a3.dot'... done. Trying 'xdg-open' program... Remember to erase graph file: /tmp/cfgnon_loop_inside_loop-a0c3a3.dot gio: file:///tmp/cfgnon_loop_inside_loop-a0c3a3.dot: No application is registered as handling this file
For me, it created /tmp/cfgnon_loop_inside_loop-a0c3a3.dot (you won't necessarily have the same name, that's ok). Then, it will try to find
default program to open it (with the xdg-open command), which as you can see, for me it didn't work. Basically, you now have to have a program that understands
that file. The dot app will do the job, but you'll probably won't have it by default. Search online for how to install graphviz package. For example, in Ubuntu I think you can do it with sudo apt-get install graphviz.
Finally, you should be able to create a PDF out of the .dot file as:
dot -Tpdf /tmp/cfgnon_loop_inside_loop-a0c3a3.dot -o <pdf_filename>.pdf
Then, you can open the pdf and expect to see sth like this: https://imgur.com/a/oW2xgNt
I think viewing CFGs like that, at times can be very helpful. In this case for example, it becomes instantly apparent that the for and the while don't form a SCC.
Comment Actions
wow, that grapical approach is beautiful , thanks
regarding the old approach i tested it with the if-then-else test i listed before
define i32* @external_sink_ret2_nrw(i32* %n0, i32* %r0, i32* %w0) {
entry:
%tobool = icmp ne i32* %n0, null
br i1 %tobool, label %if.end, label %if.then
if.then: ; preds = %entry
br label %return
if.end: ; preds = %entry
%0 = load i32, i32* %r0, align 4
store i32 %0, i32* %w0, align 4
br label %return
return: ; preds = %if.end, %if.then
ret i32* %w0
}and it seems to work fine with it after adding the analysis and maxTripCount part but it fails in another tests , I will work on them tmw and submit another diff
Comment Actions
No problem :)
regarding the old approach i tested it with the if-then-else test i listed before
define i32* @external_sink_ret2_nrw(i32* %n0, i32* %r0, i32* %w0) { entry: %tobool = icmp ne i32* %n0, null br i1 %tobool, label %if.end, label %if.then if.then: ; preds = %entry br label %return if.end: ; preds = %entry %0 = load i32, i32* %r0, align 4 store i32 %0, i32* %w0, align 4 br label %return return: ; preds = %if.end, %if.then ret i32* %w0 }and it seems to work fine with it after adding the analysis and maxTripCount part but it fails in another tests , I will work on them tmw and submit another diff
Ok, good. I'll check the method again tomorrow.
Comment Actions
[Attributor]Detect functions with unbounded loops
This patch changes the approach of containsCycle function of looping on
the CFG from dfs to bfs as the dfs approach detects if-then-else part in
functions as a loop and that result in wrong behaviour, so bfs solves that
problem by only moving level by level on the CFG and only detects loops when
there is an edge to a BB in a visited level.
This patch also uses maxTripCount to detect unbounded loops in function.
It also contains some fixed tests and some added tests contain bounded and
unbounded loops.
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2494–2495 | I'm a little bit lost here, if a loop is not known to have SmallConstantMaxTripCount, | |
Comment Actions
Please change that to "[Attributor] Detect possibly unbounded cycles in functions"
This patch changes the approach of containsCycle function of looping on
the CFG from dfs to bfs as the dfs approach detects if-then-else part in
functions as a loop and that result in wrong behaviour, so bfs solves that
problem by only moving level by level on the CFG and only detects loops when
there is an edge to a BB in a visited level.
This patch also uses maxTripCount to detect unbounded loops in function.
It also contains some fixed tests and some added tests contain bounded and
unbounded loops.
This message is good, but we will make it better. For now, certainly the old method
is wrong, I just saw it, but also this method is wrong.
First of all, the old method is wrong because of the example you posted. Generally,
that's not a good way to test cycles because the idea is to do a sort of O(n^2), which means
marking nodes visited but then marking them unvisited. You have to do in a kind of recursive
algorithm where as you forward (and deeper in the recursion) you mark them and as you come
back (returning from the recursion) you unmark them. I'll come back to this in a bit.
Regarding your method, consider this case:
define i32* @test2(i32* %n0, i32* %r0, i32* %w0) {
entry:
%tobool = icmp ne i32* %n0, null
br i1 %tobool, label %l2, label %l1
l1:
br label %l2
l2:
br label %return
return:
ret i32* %w0
}Visually (and you can see this with view-cfg) it looks like that: https://imgur.com/a/n8iG7Ig (using my awful drawing skills)
And we construct the branch to first visit the l2 (by putting in the true label of br) so that when l1 does BFS.
It detects it as a cycle but it's not.
Certainly, BFS is not a popular way to do cycle-detection and I'd abstain from that as all the algorithmic literature
that I know of uses some sort of DFS for this purpose.
So, for now, and we may be able to make it better, you can use something like this:
bool containsCycle(BasicBlock *BB, SmallPtrSet<BasicBlock *, 32> &Visited, SmallPtrSet<BasicBlock *, 32> &Processed) {
if (Processed.count(BB)) {
Visited.erase(BB);
return false;
}
Processed.insert(BB);
Visited.insert(BB);
for (auto *SuccBB : successors(BB)) {
if (!Processed.count(SuccBB) && containsCycle(SuccBB, Visited, Processed))
return true;
else if (Visited.count(SuccBB))
return true;
}
Visited.erase(BB);
return false;
}This function works as a utility and you initialize the 2 sets in the main function.
I wrote this quickly but I think it works. Note the usage of the 2 sets:
- Processed helps us not do the same work for the same starting BB. It does not help us identify cycles.
- This is done by the Visited set. The trick here is that when returning from the recursion, we mark the nodes unvisited, so we can start search in a different tree.
Edit: I'll come back with how we can make maxTripCount fit into this.
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2494–2495 | It doesn't. In a previous review the name mayContainUnboundedCycle was proposed IIRC, which I prefer. | |
| 2494–2495 | Here, you want something clearer to what the function does. I'd say, you can go with: | |
Comment Actions
Edit: I'll come back with how we can make maxTripCount fit into this.
So, I'm back. Before continuing, please tell me if everything in this algorithm was clear.
If there are any questions, please ask. So, this algorithm should be strictly better
than the original but still we haven't used LoopInfo and SCEV.
Here's another quick version that I think does that. Btw, please don't code anything yet
because especially after my last mistake I want to be extra sure that what I propose
is totally correct. Here we go:
Ok, in the version I posted above, in the else if, where we check if the successor is
already visited, if it is true, we just found a cycle. But, how do we check
whether this cycle is a loop or not? One way is to getLoopFor() for a node of
the cycle and if we do get a Loop back, check if the size of the loop with the size
of the cycle is the same. If yes, it is a loop, specifically the one we got. This is a little
subtle, so to understand this, think that a loop is always a SCC (same for the cycle). Now,
2 SCCs are either completely disjoint (no common node) or they make one big SCC.
Since the loop and the cycle do have one common node (the one we used in getLoopFor()),
they are in the same SCC. So, if the cycle and the loop have the same number of nodes,
then they're the same thing.
But, how do we get the number of nodes?
Well, in the else if, where we find a cycle, one start of the cycle is
SuccBB. The thing is, going up the recursion, we have already seen this
node (that's why it's visited). So, going down the recursion (i.e. returning)
we're going to see it again. If we save what is this starting node and count
how many nodes we go down until we find it again, this is the size of the cycle.
The code looks something like this:
static SmallPtrSet<BasicBlock *, 32> *Visited;
static SmallPtrSet<BasicBlock *, 32> *Processed;
static BasicBlock *StartBB;
static unsigned BBCount;
bool containsCycleUtil(BasicBlock *BB) {
if (Processed->count(BB)) {
Visited->erase(BB);
return false;
}
Processed->insert(BB);
Visited->insert(BB);
for (auto *SuccBB : successors(BB)) {
if (!Processed->count(SuccBB) && containsCycleUtil(SuccBB)) {
++BBCount;
// Continue going down, we haven't found
// the start yet.
if (StartBB != BB) {
return true;
}
} else if (Visited->count(SuccBB)) {
// Found cycle, save the start.
StartBB = SuccBB;
++BBCount;
return true;
}
}
Visited->erase(BB);
return false;
}(I just moved the invariants to globals so that they're not passed
back and forth in the recursion).
What remains is to utilize the LoopInfo. I have
an algorithm but before doing that we have to solve an important problem. I don't seem to be able
to get LoopInfo, it's always null. I found that I probably
need to add -loops -analyze in the command-line but still
it doesn't work. @jdoerfert any idea?
Comment Actions
bool containsCycle(BasicBlock *BB, SmallPtrSet<BasicBlock *, 32> &Visited, SmallPtrSet<BasicBlock *, 32> &Processed) {
if (Processed.count(BB)) {
Visited.erase(BB);
return false;
}
Processed.insert(BB);
Visited.insert(BB);
for (auto *SuccBB : successors(BB)) {
if (!Processed.count(SuccBB) && containsCycle(SuccBB, Visited, Processed))
return true;
else if (Visited.count(SuccBB))
return true;
}
Visited.erase(BB);
return false;
}what i get is that we will implement dfs by our hand to detect loops so can't we use stack method in dfs that will provide us to not split the function into 2 and keep all the logic inside contains cycle
Comment Actions
Yes
to detect SCCs
Cycles, it's a little bit different.
so can't we use stack method in dfs that will provide us to not split the function into 2 and keep all the logic inside contains cycle
Yes you can. But note that the runtime stack (which is implemented in the hardware) is quite faster than a software stack.
OTOH, a software stack is not as limited to its depth as a software stack. But, given that we pass a single pointer, it should
be able to handle quite a big number of blocks.
It's an implementation detail and not the most important thing. That would be the algorithm. I'd prefer the recursion but we can sure ask @jdoerfert on this.
Comment Actions
I am sorry but I can't get what the test that the approach of moving on the SCCs fails in as I have tried to test it a bit with tests like that and printed the SCCs that it gets
https://i.imgur.com/fpZhpST.png
1 - entry
2- condition - body
3- return
4 - l4
https://i.imgur.com/UJJ3aH0.png
1- entry
2- l1 - l2 - l3 - l4 - l5
3- return
4- l6 - l7 - l8
https://i.imgur.com/92NS6rp.png
1- entry
2- l1 - l2 - l3 - l4 - l5 - l6 - l7
3- return
and in all of them it reached the cycle and outputs that the loop does not have a max trip count
Comment Actions
Sorry, but I didn't understand your comment very much. The code I wrote certainly can't detect max trip count.
It only correctly (hopefully) finds if there's a cycle or not. The second modification also found the size of the cycle.
Did you write any code that used LI ? In that case, as I said earlier, I have some algorithm in mind that uses LI
but I can't seem to be able to get LI (i.e. it's always nullptr). So, probably the same will be true for you
even if your code is correct. Hopefully we can get an answer about why that happens.
Comment Actions
I mean the code you suggested that loops on SCCs using SCCiter then it appeared that tarjan only detects maximal SCCs, the one that uses tarjan algorithm :)
Comment Actions
Can u share the IR (with the appropriate RUN lines, thus tests) not the images please?
Comment Actions
With that code the reason you don't find any max trip count as I said is that you probably don't have LoopInfo. Running the examples,
I could not get LoopInfo in any way, even with -loops -analyze. That's a problem that we have to fix so that the new algorithm can be improved
with LoopInfo as well.
Comment Actions
Could you make sure that you are using a new pass manager? (It means to use ./opt -passes=attributor .. but not ./opt -attributor ..)
If you are using an old pass manager, you might not get LoopInfo or other analysis.
Comment Actions
okay , sorry for this anonymous comment
the first IR :
define i32* @test1(i32* %n0, i32* %r0, i32* %w0) {
entry:
%tmp = add i32 0, 0
br label %condition
condition:
%tobool2 = icmp ne i32* %n0, null
br i1 %tobool2, label %body, label %return
body:
%tobool3 = icmp ne i32* %n0, null
br i1 %tobool3, label %l4, label %condition
l4:
br label %l4
return:
ret i32* %w0
}the second IR :
define i32* @test2(i32* %n0, i32* %r0, i32* %w0) {
entry:
br label %l1
l1:
br label %l2
l2:
br label %l3
l3:
%tobool = icmp ne i32* %n0, null
br i1 %tobool, label %return, label %l4
l4:
%tobool2 = icmp ne i32* %n0, null
br i1 %tobool2, label %l6, label %l5
l5:
br label %l1
l6:
br label %l7
l7:
br label %l8
l8:
br label %l6
return:
ret i32* %w0
}the third IR :
define i32* @test3(i32* %n0, i32* %r0, i32* %w0) {
entry:
br label %l1
l1:
br label %l2
l2:
br label %l3
l3:
%tobool = icmp ne i32* %n0, null
br i1 %tobool, label %return, label %l4
l4:
%tobool2 = icmp ne i32* %n0, null
br i1 %tobool2, label %l6, label %l5
l5:
br label %l1
l6:
br label %l7
l7:
br label %l4
return:
ret i32* %w0
}the run command :
./bin/opt -passes=attributor --attributor-disable=false /home/omar/mytest.ll -S
the code I tested it on :
static bool containsUnboundedCycle(Function &F, Attributor &A) {
bool NoAnalysis = false;
ScalarEvolution *SE =
A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>(F);
LoopInfo *LI = A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>(F);
if (!LI || !SE){
NoAnalysis = true;
dbgs() << "no analysis in function\n";
}
for (scc_iterator<Function *> It = scc_begin(&F), IE = scc_end(&F); It != IE;
++It) {
dbgs()<<"SCC start\n\n\n";
for(auto SCCBB : *It){
dbgs()<< *SCCBB <<"\n";
}
bool SCCHasLoop = It.hasLoop();
if (!SCCHasLoop){
dbgs()<<"SCC does not have loop\n";
continue;
}
// When NoAnalysis available then check only if the SCC has loop or not.
if (NoAnalysis && SCCHasLoop){
dbgs() << "no analysis and does have loop\n";
return true;
}
const std::vector<BasicBlock *> &SCCBBs = *It;
// If any random block in this SCC does not belong to a loop, then this SCC
// is definitely not a loop.
Loop *L = LI->getLoopFor(SCCBBs.front());
if (!L){
dbgs() << "loop is null so current SCC does not have loop\n";
return true;
}
// L is the innermost loop that has a common block with the SCC. Since a
// loop is always an SCC, if their number of blocks are equal, the SCC is a
// loop so we check if it is bounded or Unbounded loop by checking the
// maxTripCount. Otherwise, there are 2 cases:
// - If the SCC has less blocks, then it is definitely not a loop.
// - If it has more, then we can't decide since the SCC can be a parent loop
// of L. So, we perform the same test for the parent of L.
do {
if (L->getNumBlocks() > SCCBBs.size()){
dbgs() << "SCC is less so not loop\n";
return true;
}
if (L->getNumBlocks() == SCCBBs.size())
if (!SE->getSmallConstantMaxTripCount(L)){
dbgs() << "there is no max trip count for the current SCC\n";
return true;
}
dbgs() << "loop with max trip count\n";
break;
} while ((L = L->getParentLoop()));
// Check if L is null, we found no loop that matches exactly the number of
// blocks of the SCC and so the SCC is not a loop.
if (!L)
return true;
}
return false;
}and in the three tests it gets me "there is no max trip count for the current SCC\n" and return true
so I what I was asking is that I can't figure out what is the test that would fail in this code ?
more explanation :
I can't figure out this test to try it and see why it is failing in it :)
That means, if a loop has an SCC inside it, we'll never find it since the loop is the maximal SCC.
Comment Actions
Thank you mate, I didn't know I was using the old pass manager.
@omarahmed I would advise you to not work anymore on the old algorithm as it's certainly not effective. I'm sorry, but
I barely have time to work on the new algorithm :/ Otherwise, I would try to answer it.
So, here's a new algorithm with a couple of debug prints:
static DenseMap<BasicBlock *, unsigned> VisitingTime;
bool containsCycleUtil(BasicBlock *BB) {
dbgs() << "Visiting: " << BB->getName() << "\n";
unsigned VisitingTimeCurrent = VisitingTime[BB];
for (auto *SuccBB : successors(BB)) {
dbgs() << BB->getName() << " -> " << SuccBB->getName() << "\n\n";
unsigned &VisitingTimeSucc = VisitingTime[SuccBB];
if (!VisitingTimeSucc) {
VisitingTimeSucc = VisitingTimeCurrent + 1;
containsCycleUtil(SuccBB);
VisitingTimeSucc = 0;
} else {
dbgs() << "Found cycle: " << VisitingTimeCurrent << ", " << VisitingTimeSucc << "\n";
assert(VisitingTimeCurrent >= VisitingTimeSucc);
unsigned CycleSize = VisitingTimeCurrent - VisitingTimeSucc + 1;
dbgs() << "Cycle size: " << CycleSize << "\n";
}
}
return false;
}
static bool containsCycle(Attributor &A, Function &F) {
BasicBlock *EntryBB = &F.getEntryBlock();
VisitingTime[EntryBB] = 1;
return containsCycleUtil(EntryBB);
}The main modification compared to the last one is that I track visiting time
instead of going back the recursion. This makes the algorithm so much
cleaner (and reliable, for reasons that are not on topic).
Now, this algorithm, AFAICT, finds all cycles, without false positives. Plus, it detects
only statically reachable cycles. That's good news, it should be strictly better than the initial.
Naively, one could then say "let's apply the same idea as with the SCCs algorithm.
This does not fully work though because check this:
define void @loop_with_if(i1 %c1, i1 %c2) {
entry:
br label %w1
w1:
br i1 %c1, label %b1, label %exit
b1:
br label %if
if:
br i1 %c2, label %t1, label %e1
t1:
br label %latch
e1:
br label %latch
latch:
br label %w1
exit:
ret void
}If you pay attention, it's a while with an if inside. If you draw out the CFG, you can
see that there's a cycle: w1 -> b1 -> if -> e1 -> latch -> w1
which the algorithm will (correctly) find. The cycle size is 5 but the loop size is 6.
So, in such loops, even if SCEV can deduce a max trip count (which is possible),
the initial method will fail to realize this is one loop.
Which makes a point: There can be a cycle, which is not a loop, which still does not
disrupt the maximum trip count guarantee (interestingly, that means that even if
SCCIterator gave us all the SCCs, we would stumble upon this problem).
Edit: Well, that was obvious before but not quite in the same context.
And there can be many many such real-world cases.
From this point on, the problem I think starts to get quite complicated. It seems we
need to start saying "if all the blocks of the cycle belong to the same loop and
these blocks contain the header and the latch of the loop blah.. blah.." then
this cycle can be skipped.
IMHO, we should maybe just live with a not-so-perfect-algorithm, or decide
that it is going to take a good amount of time to get it right.
And sorry for the long posts, but this problem turned out to be more complicated
that it initially seemed. I hope I helped a bit.
Comment Actions
I now understand the problem clearly , Thank you really , u helped me a lot :)
I will try to submit a diff tmw with this new algorithm with adding a doc :)
Comment Actions
I now understand the problem clearly , Thank you really , u helped me a lot :)
No problem! If you have any questions, please ask.
I will try to submit a diff tmw with this new algorithm with adding a doc :)
You may want to submit it initially without the LoopInfo.
Comment Actions
I tried to use loopInfo on the algorithm , I have came with 2 approaches :
the first is that if we found a cycle we add the BB in the cycle in a allCyclesBBs vector and after we return from containCycleUtil with all the BBs that makes cycles then loop on the allCyclesBBs vector in the containsCycle function and get the information of the loop with getloopfor as we was doing or ask this inside the containCycleUtil and make this function return us if there was a cycle with no maxTripCount
the second is that we do this dfs in a stack style and if we find a cycle we ask for loop info and do the same checks as before like maxtripCount
I don't know which of them is better ?
also the algorithm sometimes in cases moves on BBs 2 times like this case here :
define i32* @external_sink_ret2_nrw(i32* %n0, i32* %r0, i32* %w0) {
entry:
%tobool = icmp ne i32* %n0, null
br i1 %tobool, label %if.end, label %if.then
if.then: ; preds = %entry
%tobool2 = icmp ne i32* %n0, null
br i1 %tobool2, label %return, label %if.end
if.end: ; preds = %entry
br label %return
return: ; preds = %if.end, %if.then
ret i32* %w0
}so I think if we keep not only the visiting time but the start time = visitingTime and finish time of each node we have visited then we can detect a cycle if we reach a node with no finishTime that means that this node we have visited but not returned from it to make it finish , so this makes the complexity in all the situations O( N+E )
another question Is it normal to make global variables as I have not found any in the code ?
Comment Actions
The second one unless I miss something. Oh, I just saw I didn't post the code with LoopInfo. But in any case,
you don't need to save the cycles for any reason cycles.
also the algorithm sometimes in cases moves on BBs 2 times
You probably mean the return label. Yes it does, because you try to find all cycles. Compare this to the initial algorithm in which you find if there's any cycle at all (check the Processed there that is missing here).
like this case here :
define i32* @external_sink_ret2_nrw(i32* %n0, i32* %r0, i32* %w0) { entry: %tobool = icmp ne i32* %n0, null br i1 %tobool, label %if.end, label %if.then if.then: ; preds = %entry %tobool2 = icmp ne i32* %n0, null br i1 %tobool2, label %return, label %if.end if.end: ; preds = %entry br label %return return: ; preds = %if.end, %if.then ret i32* %w0 }so I think if we keep not only the visiting time but the start time = visitingTime and finish time of each node we have visited then we can detect a cycle if we reach a node with no finishTime that means that this node we have visited but not returned from it to make it finish , so this makes the complexity in all the situations O( N+E )
another question Is it normal to make global variables as I have not found any in the code ?
Generally, global variables are bad. However, when doing recursion, you don't want to pass parameters that are invariant because the fill the stack without a reason
and limit the recursion depth. So, you have 2 choices. Either you make global variables or you make a class that does the thing you want to do.
Then, the global variables get replaced by member variables. To me, this is mostly a matter of preference. Indeed, there are no global variables in the Attributor generally
but in this case, I don't know what would be preferred. This is the easiest thing to replace, so you can use them for now if you want.
In any case, this patch got an unexpected turn so I'd wait for @jdoerfert to tell us an opinion in general. Give him a little a bit of time since:
a) There's a lot to read.
b) He's travelling.
Comment Actions
I haven't read all the comments but the code looks good with one problem, see below.
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2501 | Nit: bool NoAnalysis = !SE || !LI; | |
| 2516 | if (!L || !SE->getSmallConstantMaxTripCount(L)) return true; You ignore non-loop cycles otherwise. Please add a non-loop cycle test case, aka. irreducible control flow test case. Here is a piece of C that should help create the test: if (foo())
goto entry1;
else
goto entry2;
entry1:
if (foo())
goto exit;
else
goto entry2;
entry2:
if (foo())
goto exit;
else
goto entry1;
exit:
return; | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2516 | Please note that this code (i.e. the original) is wrong anyway, as for example in this it finds a cycle because define i32* @external_sink_ret2_nrw(i32* %n0, i32* %r0, i32* %w0) {
entry:
%tobool = icmp ne i32* %n0, null
br i1 %tobool, label %if.end, label %if.then
if.then: ; preds = %entry
br label %return
if.end: ; preds = %entry
%0 = load i32, i32* %r0, align 4
store i32 %0, i32* %w0, align 4
br label %return
return: ; preds = %if.end, %if.then
ret i32* %w0
}As I noted in earlier comments, to find all cycles correctly, one has to visit but then unvisit nodes when trying a new cycle. | |
Comment Actions
Please add a non-loop cycle test case, aka. irreducible control flow test case.
okay I will add it in the next diff :)
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2516 | Not wrong but too conservative ;) That's a big difference. However, I agree, we should be as precise as is reasonably cheap. | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2516 | If you mean that the actual problem is the speed which is a side-effect of conservation, then yes, definitely it's unreasonably slow (given a complete graph, it has sth like exponential time). | |
Comment Actions
[Attributor]Detect possibly unbounded cycles in functions
This patch changes the approach of containsCycle function of looping on
the CFG by depth_first to another approach as the depth_first function approach detects if-then-else part in
functions as a loop and that result in wrong behaviour, so the new approach detects cycles by using a recursive function that dfs on the CFG from the entry block and detects a cycle when we go in a recursive calls chain and visit one of the nodes of the chain.
This new approach also saves the processed nodes so not compute them two times thus enhancing the complexity of the algorithm to be O(N+E).
The approach also doesn't visit statically unreachable blocks so that also enhances the complexity.
This patch also uses maxTripCount to detect if a function has a cycle,then we check
further whether the cycle is a bounded loop cycle.
Loops with maximum trip count are considered bounded, any other cycle not.
It also contains some fixed tests and some added tests contain bounded and
unbounded loops.
Comment Actions
[Attributor]Detect possibly unbounded cycles in functions
This patch changes the approach of containsCycle function of looping on
the CFG by depth_first to another approach as the depth_first function approach detects if-then-else part in
functions as a loop and that result in wrong behaviour, so the new approach detects cycles by using a recursive function that dfs on the CFG from the entry block and detects a cycle when we go in a recursive calls chain and visit one of the nodes of the chain.
This new approach also saves the processed nodes so not compute them two times thus enhancing the complexity of the algorithm to be O(N+E).
The approach also doesn't visit statically unreachable blocks so that also enhances the complexity.
This patch also uses maxTripCount to detect if a function has a cycle,then we check
further whether the cycle is a bounded loop cycle.
Loops with maximum trip count are considered bounded, any other cycle not.
It also contains some fixed tests and some added tests contain bounded and
unbounded loops.
Comment Actions
Note that this algorithm detects whether there is a cycle in the function (correctl). But now
note that if you find a cycle, you may want to skip it. In that case, it is wrong.
Specifically, because of the Processed, say you find a cycle A and you skip it
because it is a loop with max trip count (how do you do that reliably is another story).
There can be a cycle B (in which some nodes of A are contained) that won't be found.
That is a false negative (i.e. we'll say the function is willreturn but it might
not be). I think this is a problem.
I'll have to think if that can happen in the CFG, but from the graph theory perspective,
it definitely can.
This new approach also saves the processed nodes so not compute them two times thus enhancing the complexity of the algorithm to be O(N+E).
The approach also doesn't visit statically unreachable blocks so that also enhances the complexity.
Those 2 were true for the previous algorithm as well. If I'm not mistaken, we're doing strictly more work than the previous algorithm (although
the facts you wrote are correct).
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2516 | Note that as I mentioned, if a node of a cycle is within a loop, it doesn't mean it is the loop. | |
Comment Actions
From what i understaand is that when we have a case like that https://i.imgur.com/cvAjcMa.png and when cycle 1-2-3 have amax trip count and we visit them first we have a problem
but i think it won't make a problem since 2 and 3 which are in the bigger cycle must have edges in the cycle in here is the edge of 3 to 4 so 3 and 2 will not be marked processed until they completly finish the 3 node successors so it will complete in the bigger cycle and detect the cycle . I think marking processed at the end will make us escape from a problem like that
Comment Actions
In such scenarios you won't have a problem indeed. What I meant is such scenarios: https://imgur.com/a/Ua8xwhg
Consider the case where you find the cycle 0-1-2-0 but it is a loop with max trip count. Upon returning (from recursion) in 1, you will visit 3. But from 3, you won't visit 1 because it's already processed.
If you're doing cycle detection (i.e. check if a graph has a cycle whatsoever), this is correct because there's no point revisiting processed nodes. But this is not our case because we skip.
So, to sum up: As I mentioned, LoopInfo I think can't be used reliably as it is used now for the points mentioned previously. And we have 2 cases:
- If we find a reliable way to skip cycles, in this algorithm we will have false negatives which I think is bad. Maybe better the initial version which while it had false positives, it didn't have false negatives.
- If not, this is probably as good as we can get in cycle detection and has a good complexity.
Comment Actions
High level comments:
- Please do not use global variables. If you need a set/map, create it on the stack and pass it as a reference.
- If the algorithm to distinguish cycles and loops makes problems, we can just go through all loops in loop info and verify there is no irreducible control (see for example mayContainIrreducibleControl in MustExecute.cpp)
Comment Actions
That's a great idea! @omarahmed note that LoopInfo gives you the top-level loops (https://llvm.org/docs/LoopTerminology.html#id3). One way to get top-level loops is getLoopsInPreorder(). Then, you can get all the sub-loops of a loop using getSubLoops(). However, note that this will give you the immediate children if I'm not mistaken. That is, say you have a top-level loop A that contains B that contains C. A->getSubLoops() will give you B. You then have to do B->getSubLoops() to get C.
Before you do all that, you check for irreducible control of course.
Other than that, and you may skip that, I think it's interesting to see what happens behind the scenes. mayContainIrreducibleControl() calls containsIrreducibleCFG().
This requires LoopInfo. Apart from its implementation that is interesting, it's also educational to read about how do you test for irreducible control in a CFG (i.e. cycle that is not a Loop in the LLVM terms) without LoopInfo.
Here's the diff in which it was added: https://reviews.llvm.org/D40874#1013599 . Check online for T1 / T2 transformations in control-flow graphs (I just did 'cause of course I didn't know any of that and it's quite fun).
Comment Actions
okay will work on it right away and see how this goes :) , Thanks for pointing me to this great resources will definitely check all of them :D
Comment Actions
[Attributor] Detect possibly unbounded cycles in functions
This patch changes the approach of containsCycle function of looping on
the CFG by depth_first to another approach as the depth_first function approach detects if-then-else part in
functions as a loop and that result in wrong behaviour, so this approach checks first the analysis of the function if no analysis available for the function then it loops on the SCCs and checkss if the SCC is a cycle or not,this is done with the assumption that any cycle is unbounded.
If analysis is present for the function then we check for irreducible control to check if there is a non loop cycles if there weren't any then we loop on the loop cycles in the function and check the maxTripCount of the loop.
This patch also uses maxTripCount to check if a function have bounded loop cycles.
Loops with maximum trip count are considered bounded, any other cycle not.
It also contains some fixed tests and some added tests contain bounded and
unbounded loops and non-loop cycles.
Comment Actions
[Attributor] Detect possibly unbounded cycles in functions
This patch changes the approach of containsCycle function of looping on
the CFG by depth_first to another approach as the depth_first function approach detects if-then-else part in
functions as a loop and that result in wrong behaviour, so this approach checks first the analysis of the function if no analysis available for the function then it loops on the SCCs and checkss if the SCC is a cycle or not,this is done with the assumption that any cycle is unbounded.
If analysis is present for the function then we check for irreducible control to check if there is a non loop cycles if there weren't any then we loop on the loop cycles in the function and check the maxTripCount of the loop.
This patch also uses maxTripCount to check if a function have bounded loop cycles.
Loops with maximum trip count are considered bounded, any other cycle not.
It also contains some fixed tests and some added tests contain bounded and
unbounded loops and non-loop cycles.
Comment Actions
You don't need anything above here. :)
If analysis is present for the function then we check for irreducible control to check if there is a non loop cycles if there weren't any then we loop on the loop cycles in the function and check the maxTripCount of the loop.
It would be great to fix grammar / syntax a little bit. You can break sentences to make this easier. Also, you can be a little more specific (when it is useful). For example:
If LoopInfo and SCEV analyses are available, then:
- We can test whether there is irreducible control (i.e. non-loop cycles). If there is, one of those cycles can be infinite, so we return true.
- Otherwise, loop through all the loops in the function (including child loops) and test whether any of those does not have a maximal trip count (in which case it might be infinite).
Note that the first step can be done more cheaply without requiring LoopInfo. But we use it since it is implicitly needed in the second step.
It also contains some fixed tests and some added tests contain bounded and
unbounded loops and non-loop cycles.
This is good, you can leave that.
Aside from the description, we have to do something when analyses are not available. My proposal is to use the old method, again because it doesn't have false negatives and it's reasonably cheap.
Lastly, I want to reiterate that if there's anything that is unclear, please ask.
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2499–2505 | You don't need any of that. This is what was mentioned in a previous diff: Specifically that SCC iterator does not loop through all SCCs, only the top-level one, so you can't do that. | |
| 2513–2519 | As @jdoerfert mentioned, you can replace this with mayContainIrreducibleControl | |
| 2523–2524 | As I said in a previous comment, getLoopsInPreorder() (or any way that LoopInfo gives you access to all the loops) gives you the top-level loops. The fact that a top-level loop has a maximal trip count does not mean that its children loops (i.e. loops entirely contained within this loop) will also have a maximal trip count. So, for every top-level loop, you have to check all its children (i.e. getSubLoops()). And all that, in a loop / recursion, because the sub loops may themselves have children loops etc. | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2499–2505 | I tried to do the old method but with no false positives, from what I understand here we wanted only to detect if a cycle exists only and doesn't care if it is a loop or not so I thought that SCCs evenwhen they will give us the top level ones these top level ones will mean that there is a cycle and if there were not these top level SCC structure and it is only consists of single nodes SCCs it will make us not detect a cycle so i used hasCycle function to detect that , does a top level SCC can exist that is not a cycle and a smaller SCC that is a cycle exist in it ? | |
| 2513–2519 | I found that the function is in mustExcute.cpp only and not available in the header file mustExcute.h so how could i use it in this case i guess it should be added to the header :) | |
| 2523–2524 | I have tried it with a test like that for(int i=0;i<n;i++)
for(int j =0;j<n;j++)
for(int k = 0;k<n;k++)
for(int l = 0;l<n;l++)and printed the loops that it iterate on and i found it had iterated even on the forth level one , also I have looked on the implementation of the cycle and found that it recursivly was going inside the loops so i guess it goes throw all of the loops not only the top-level ones or I miss something here ? | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2523–2524 | I mean the implementation of the function not cycle it is a typo :) | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2499–2505 | Sorry, I wrote these comments quite quickly yesterday. You're right. To answer, at first, no, any SCC unless it is single-node without self-loop. Now, scc_iterator uses Tarjan, which finds all the maximal SCCs. Those are SCCs which are as big as they can get. i.e. in which you can't put any other node and still have an SCC. To detect if there's a cycle, you only need to find the maximal ones. Also, note that in this case, you could use the algorithm version with Processed. This checked whether there is a cycle in the graph in the same complexity as Tarjan, but it's also simpler. Use what you like. However, if you use the scc_iterator version, we need a good explanation (you can pick stuff from this comment). | |
| 2513–2519 | Yep, true, it's static. Please add it to the header. :) | |
| 2523–2524 | Yes, also true, it gives you all the loops in preorder, I just checked the function. So, yes that should work. | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2513–2519 | i tried to erase static as static means that it will only used in the cpp file also i have put the definition in the header file but that resulted in an error in linking so how could we do that here ? I guess also that all the functions i saw was only static in the cpp file or they are belong to a class in the .h or cpp file but no function that is implemented alone so I think that getting this 3 lines is more clean or what do you think ? | |
Comment Actions
Patch updates :
Check If LoopInfo and SCEV analyses are available, then:
- We can test whether there is irreducible control (i.e. non-loop cycles). If there is, one of those cycles can be infinite, so we return true.
- Otherwise, loop through all the loops in the function (including child loops) and test whether any of those does not have a maximal trip count (in which case it might be infinite).
Else if unavailable:
- We check if any cycle exists then we return true or else we return false.we use scc_iterator to check for cycles.
Note:
- scc_iterator uses Tarjan, which finds all the maximal SCCs. Those are SCCs which are as big as they can get. i.e. in which you can't put any other node and still have an SCC. To detect if there's a cycle, you only need to find the maximal ones.
Comment Actions
why it is failing in harbor master remote builds,I am sure it compiles , passes tests and clang format run on it?
also regarding the tests it gives expected fails =1 in liveness.ll , from what i understand it is expected to fail anyway but is that a problem that needs to be fixed ?
Comment Actions
That's quite better I think! :) Side note: You can rephrase or change my proposals regarding documentation, commit messages etc. I'm here only to try to make sure that you get the point across (you're also
free to copy exactly what I say of course, pick whatever you like).
why it is failing in harbor master remote builds,I am sure it compiles , passes tests and clang format run on it?
On that part unfortunately I can't help. I'm not familiar with harbomaster. AFAIK, it shouldn't fail. Maybe Johannes or @uenoku can help.
also regarding the tests it gives expected fails =1 in liveness.ll , from what i understand it is expected to fail anyway but is that a problem that needs to be fixed ?
AFAIK, no, this is not a problem. But make sure that you run the whole test suite. That is, probably now you run the tests in llvm/test/Transforms/Attributor/. After verifying that those pass,
you can run all the tests in llvm/test. Note that this should not make a difference since the Attributor is not currently used anywhere. But it's something that should be done in general.
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2513–2519 | I think it's better if we use the already made function. I'll try to do that myself tomorrow and see what problems come up. [Irrelevant] Some more info about static: It means that you can use the function only in this compilation unit. Usually, a compilation unit is a .cpp file, but if you include a .cpp file in another, those 2 will make one compilation unit. | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2523 | After a little bit of search, clang-tidy fails in the Harbomaster because you can declare L as auto *L (instead of auto L). | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2523 | oh sry that was obvious somehow and i didn't saw it,Thanks :) | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2513–2519 | So, I had forgotten about namespace llvm. You need to put the declaration of the function inside namespace llvm in MustExecute.h. | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2501 | nit: Normally, the word "strongly connected components" contains its maximality. So I think it's more concise to omit the description for maximality. | |
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2501 | I'm not sure there's a definitive answer here. It depends on the definition. If we use the "reachability" definition, then it's not implied. An SCC can contain an SCC. But if we talk about plural, i.e. SCCs of a graph, the definition contains the term partition. Which implies maximality. I've seen both in books and I believe it's a long discussion in which we don't want to get the reader to. The fact that I didn't remember that scc_iterators finds maximal SCCs led to 3-4 days at least of working on a wrong solution (in this patch actually). | |
Comment Actions
Patch updates :
- Add mayContainIrreducibleControl() function to the MustExecute.h so it could be used in mayContainUnboundedCycle() function in Attributtor.cpp.
- Fix mayContainIrreducibleControl() function as the return value was reversed , it was :
- Return true if Reducible control.
- Return false if Irreducible control.
- Minor fixes in docs.
Comment Actions
I don't know if reversing the condition of mayContainIrreducibleControl is right but it seemed logical to me also I have run llvm\test\analysis tests and it didn't break any test
Comment Actions
Patch updates :
- Add mayContainIrreducibleControl() function to the MustExecute.h so it could be used in mayContainUnboundedCycle() function in Attributtor.cpp.
- Fix mayContainIrreducibleControl() function as the return value was reversed , it was :
- Return true if Reducible control.
- Return false if Irreducible control.
- Minor fixes in docs.
Comment Actions
Generally it LGTM. I've added some nit comments. Before accepting, I'd like @jdoerfert opinion on the change in mayContainIrreducibleControl().
I think it's a correct change.
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2494–2495 | Remove the TODO. | |
| 2499 | "If NoAnalysis is available ..." -> "If either SCEV or LoopInfo is not available ..." | |
| 2502 | "you only need" -> "we only need" | |
| 2513 | If there's irreducible control, the function may contain non-loop cycles. | |
| 2518 | Any loop that does not have a max trip count is considered unbounded cycle. | |
Comment Actions
Remove the TODO.
Then please see the comment above.
sry , I don't understand what u mean by the comment above , does u mean your comment to uenoko ?
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2501 | Ok, I'm fine with either way :) | |
Comment Actions
No sorry, I meant this:
Here, you want something clearer to what the function does. I'd say, you can go with: "Helper function that checks whether a function has any cycle which we don't know is bounded. Loops with maximum trip count are considered bounded, any other cycle not." We may have to revise this further but it seems a good start.
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2501 | Cool :) | |
Comment Actions
I added a single nit comment. Otherwise it LGTM! :)
| llvm/lib/Transforms/IPO/Attributor.cpp | ||
|---|---|---|
| 2495–2509 | [Nit][Grammar] "we don't know is bounded" -> "we don't know if it is bounded" | |
Comment Actions
No problem, I hope it helped. :) Let's wait for a couple of days for other reviewers and then I can commit.
Although I just saw we should also change the commit message (i.e. the description).
The following is a quick write that seems fine.
Add mayContainUnboundedCycle which checks if there's a cycle
in a function that we consider unbounded.
All loops with max trip count are considered bounded.
Any other cycle is not.
Comment Actions
Sorry probably it wasn't clear. I meant that you should also update the description of this patch. :)
Comment Actions
I think it is ok. Although I haven't seen much the tests. Let's wait a couple of days for another reviewer and we can commit then.
Comment Actions
Thanks all :D
I am sorry but a message sent to me with this
The Buildbot has detected a new failure on builder fuchsia-x86_64-linux while building llvm.
So does that mean i broke something here ?
Comment Actions
You don't have to care about the failure if the failure doesn't occur multiple times.
Please see https://lists.llvm.org/pipermail/llvm-dev/2019-November/136710.html
Comment Actions
I think a better way to put it is that you don't have to care about the failure if you did not cause it (e.g. you might not get multiple emails if other bots were broken before)
The old comment is strictly more understandable.
New comment does not mention at all that we are checking inside functions only.