Page MenuHomePhabricator

[Attributor] Detect possibly unbounded cycles in functions
ClosedPublic

Authored by omarahmed on Feb 16 2020, 7:22 AM.

Details

Summary

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.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
omarahmed edited the summary of this revision. (Show Details)EditedMar 4 2020, 10:22 PM

[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.

omarahmed updated this revision to Diff 248395.Mar 4 2020, 10:28 PM

[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.

[Attributor]Detect possibly unbounded cycles in functions

so the new approach detects cycles by using a recursive function that dfs on the CFG

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.

[Attributor]Detect possibly unbounded cycles in functions

so the new approach detects cycles by using a recursive function that dfs on the CFG

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

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

[Attributor]Detect possibly unbounded cycles in functions

so the new approach detects cycles by using a recursive function that dfs on the CFG

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

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

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:

  1. 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.
  2. If not, this is probably as good as we can get in cycle detection and has a good complexity.

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

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

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

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

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

omarahmed updated this revision to Diff 248960.Mar 7 2020, 12:40 PM

[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.

omarahmed updated this revision to Diff 248963.Mar 7 2020, 1:25 PM

[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.

[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.

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.

omarahmed marked 3 inline comments as done.Mar 7 2020, 5:28 PM
omarahmed added inline comments.
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 ?

omarahmed marked an inline comment as done.Mar 7 2020, 5:52 PM
omarahmed added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
2523–2524

I mean the implementation of the function not cycle it is a typo :)

baziotis added inline comments.Mar 8 2020, 1:37 AM
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.

bbn added a subscriber: bbn.Mar 8 2020, 8:39 AM
omarahmed marked an inline comment as done.Mar 8 2020, 1:06 PM
omarahmed added inline comments.
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 ?

omarahmed updated this revision to Diff 249021.Mar 8 2020, 4:29 PM

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.

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 ?

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.

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.
As a side note, static has more to do with linking than with compiling. It basically means that the symbol (i.e. the function, which in assembly is just a label) is not exported. So, no code from another object file can jump to it.
Here's a great video in case you're interested in this kind of stuff: https://www.youtube.com/watch?v=n4fI4eUTTKM

baziotis added inline comments.Mar 8 2020, 7:32 PM
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).
You can see the failed check by clicking on the Harbomaster failed build (https://reviews.llvm.org/B48509), then "pre-merge checks"(https://reviews.llvm.org/harbormaster/build/52266/), then "External Link clang-tidy linux" (https://results.llvm-merge-guard.org/amd64_debian_testing_clang8-4435/clang-tidy.txt).

omarahmed marked an inline comment as done.Mar 8 2020, 7:56 PM
omarahmed added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
2523

oh sry that was obvious somehow and i didn't saw it,Thanks :)

baziotis added inline comments.Mar 9 2020, 6:01 AM
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.
Then, in MustExecute.cpp, you need to remove static but add llvm:: in the name, i.e. llvm::mayContainIrreducibleControl(....
In short, the function has to be declared inside the llvm namespace and when you define it, you have to specify that you want to define a function from this specific namespace.

uenoku added inline comments.Mar 9 2020, 9:09 AM
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.

baziotis added inline comments.Mar 9 2020, 10:12 AM
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).

omarahmed updated this revision to Diff 249196.EditedMar 9 2020, 1:02 PM
omarahmed marked an inline comment as done.

Patch updates :

  1. Add mayContainIrreducibleControl() function to the MustExecute.h so it could be used in mayContainUnboundedCycle() function in Attributtor.cpp.
  2. Fix mayContainIrreducibleControl() function as the return value was reversed , it was :
    • Return true if Reducible control.
    • Return false if Irreducible control.
  3. Minor fixes in docs.

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

omarahmed updated this revision to Diff 249263.EditedMar 9 2020, 6:51 PM

Patch updates :

  1. Add mayContainIrreducibleControl() function to the MustExecute.h so it could be used in mayContainUnboundedCycle() function in Attributtor.cpp.
  2. Fix mayContainIrreducibleControl() function as the return value was reversed , it was :
    • Return true if Reducible control.
    • Return false if Irreducible control.
  3. Minor fixes in docs.

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.
Then please see the comment above.

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.

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 ?

uenoku added inline comments.Mar 10 2020, 8:52 AM
llvm/lib/Transforms/IPO/Attributor.cpp
2501

Ok, I'm fine with either way :)

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 ?

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

omarahmed updated this revision to Diff 249425.Mar 10 2020, 9:37 AM

Minor cleanups

omarahmed updated this revision to Diff 249428.Mar 10 2020, 9:46 AM

Minor cleanups

Harbormaster completed remote builds in B48706: Diff 249425.
baziotis accepted this revision.Mar 10 2020, 3:48 PM

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"

omarahmed updated this revision to Diff 249520.Mar 10 2020, 4:42 PM

Minor cleanup

omarahmed added a comment.EditedMar 10 2020, 4:51 PM

I added a single nit comment. Otherwise it LGTM! :)

Thanks for the great reviews and bearing my small mistakes through this :)

I added a single nit comment. Otherwise it LGTM! :)

Thanks for the great reviews and bearing my small mistakes through this :)

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.

omarahmed updated this revision to Diff 249592.Mar 11 2020, 5:08 AM

Update commit message

Update commit message

Sorry probably it wasn't clear. I meant that you should also update the description of this patch. :)

omarahmed edited the summary of this revision. (Show Details)Mar 11 2020, 6:01 AM

Update commit message

Sorry probably it wasn't clear. I meant that you should also update the description of this patch. :)

done :) , Does we need more details than that ?

omarahmed edited the summary of this revision. (Show Details)Mar 11 2020, 6:15 AM

Update commit message

Sorry probably it wasn't clear. I meant that you should also update the description of this patch. :)

done :) , Does we need more details than that ?

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.

uenoku accepted this revision.Mar 13 2020, 3:45 AM

LGTM

jdoerfert accepted this revision.Mar 13 2020, 7:53 AM

LGTM, I'll commit

This revision is now accepted and ready to land.Mar 13 2020, 7:53 AM
This revision was automatically updated to reflect the committed changes.

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 ?

uenoku added a comment.EditedMar 13 2020, 10:29 AM

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

fhahn added a subscriber: fhahn.Mar 13 2020, 10:53 AM

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

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)

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

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)

Yes, thank you for the correction.

Got it, Thanks :)