Page MenuHomePhabricator

baziotis (Stefanos Baziotis)
User

Projects

User does not belong to any projects.

User Details

User Since
Dec 12 2019, 1:37 PM (10 w, 4 d)

Recent Activity

Yesterday

baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

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.

wow, that grapical approach is beautiful , thanks

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

Sun, Feb 23, 4:33 PM · Restricted Project
baziotis added inline comments to D74989: [LoopTerminology] Loop Simplify Form.
Sun, Feb 23, 4:19 PM · Restricted Project
baziotis updated the diff for D74989: [LoopTerminology] Loop Simplify Form.

Addressed comments.

Sun, Feb 23, 4:15 PM · Restricted Project
baziotis added inline comments to D74989: [LoopTerminology] Loop Simplify Form.
Sun, Feb 23, 4:06 PM · Restricted Project
baziotis added inline comments to D75013: [LoopTerminology] Rotated Loops.
Sun, Feb 23, 4:01 PM · Restricted Project
baziotis added inline comments to D75013: [LoopTerminology] Rotated Loops.
Sun, Feb 23, 4:01 PM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

btw, I recommend that you try to answer questions by following the code - it's always a learning experience).

Sun, Feb 23, 3:20 PM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

@omarahmed @jdoerfert

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.

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;
; }
Sun, Feb 23, 2:59 PM · Restricted Project
baziotis updated subscribers of D74691: [Attributor] Detect SCCs with unbounded cycles.
Sun, Feb 23, 12:48 PM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

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.

Sun, Feb 23, 12:47 PM · Restricted Project
baziotis added a comment to D75024: [SCCIterator] Check if a SCC is a natural loop..

Hmm, that's bizarre. Won't the SCCIterator go through all the SCCs? That is, let's say we have a topmost loop with blocks: A, B, C. And blocks B, C also form a loop.
Won't we get a separate SCC for A, B, C and B, C?

It uses Tarjan's algorithm which only returns maximal connected subgraphs. Anything else would be infeasible. Think of a complete graph, every subset of nodes would by strongly connected (but not maximal), hence return an exponential number of strongly connected subgraphs. Only the entire complete graph is maximal and considered a component.

Sun, Feb 23, 12:38 PM · Restricted Project
baziotis added a comment to D75024: [SCCIterator] Check if a SCC is a natural loop..

"ADT" stands for "Abstract Data Type". This use case is rather concrete. Unfortunately, LoopInfo ignores non-natural loops, but it would be the place for this.

So, a function that gets an SCC and decides if it's a loop, alright.

IIUC, there will be an SCC only for an topmost loop including all its nested loop. Its not possible using SCCIterator to match a non-topmost loops.

Sun, Feb 23, 12:07 PM · Restricted Project
baziotis added a comment to D75024: [SCCIterator] Check if a SCC is a natural loop..

I'm not sure this fits here, this is very specific to GraphT=Function*, since LoopInfo::getLoopFor() is only defined for (function) basic blocks.

Sun, Feb 23, 12:03 PM · Restricted Project
baziotis added inline comments to D74691: [Attributor] Detect SCCs with unbounded cycles.
Sun, Feb 23, 12:03 PM · Restricted Project
baziotis added a comment to D75024: [SCCIterator] Check if a SCC is a natural loop..

First of all, do you think this is a useful addition to the SCC interface? We recently needed it in a patch.

Sun, Feb 23, 11:36 AM · Restricted Project
baziotis created D75024: [SCCIterator] Check if a SCC is a natural loop..
Sun, Feb 23, 11:31 AM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

[...]
Btw, the search for some loops may need to happen in AAUB, since it is considered UB if I understood correctly.

So infinite loops without progress are UB, I think

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.

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.

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.

Sun, Feb 23, 5:06 AM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

[Attributor]Detect SCCs with unbounded cycles

  1. Updating D74691: [Attributor] add some pattern to containsCycle #
  2. Enter a brief description of the changes included in this update.
  3. The first line is used as subject, next lines as comment. #
  4. If you intended to create a new revision, use:
  5. $ arc diff --create
Sun, Feb 23, 5:06 AM · Restricted Project
baziotis added inline comments to D75013: [LoopTerminology] Rotated Loops.
Sun, Feb 23, 4:20 AM · Restricted Project
baziotis added inline comments to D74989: [LoopTerminology] Loop Simplify Form.
Sun, Feb 23, 3:08 AM · Restricted Project

Sat, Feb 22

baziotis added a comment to D74989: [LoopTerminology] Loop Simplify Form.
Sat, Feb 22, 1:13 PM · Restricted Project
baziotis added a comment to D74989: [LoopTerminology] Loop Simplify Form.

https://llvm.org/docs/Passes.html#loop-simplify-canonicalize-natural-loops Also has some info about loop simplify form. It would be good to at least cross reference the 2 documents and/or maybe consider unifying / aligning the descriptions

Sat, Feb 22, 1:13 PM · Restricted Project
baziotis added a comment to D75013: [LoopTerminology] Rotated Loops.

So, I'm sure I'm not the best to write this one since I have not understood it completely, but first of all, after trying a lot to understand it, I feel it needs doc.
Second, I hope that you can help me write it correctly. :)

Sat, Feb 22, 1:07 PM · Restricted Project
baziotis created D75013: [LoopTerminology] Rotated Loops.
Sat, Feb 22, 1:04 PM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

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.

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?

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?

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.

So infinite loops without progress are UB, I think

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.

Sat, Feb 22, 12:04 PM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

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.

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?

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?

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.

Sat, Feb 22, 8:45 AM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

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.

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

Sat, Feb 22, 4:59 AM · Restricted Project

Fri, Feb 21

baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

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

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

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 ]

Fri, Feb 21, 5:51 PM · Restricted Project
baziotis added a comment to D74989: [LoopTerminology] Loop Simplify Form.

Oh thanks, I didn't know that. So, closing. Can I add any part that is not addressed in this draft? For example, rotated loops
I think aren't and personally I feel they really need doc.

I think the author abandoned it. In the current state it looks more like a API reference.

Fri, Feb 21, 4:11 PM · Restricted Project
baziotis added a comment to D74989: [LoopTerminology] Loop Simplify Form.

Note that there already is a draft filling out this section at D65257.

Fri, Feb 21, 3:44 PM · Restricted Project
baziotis updated the diff for D74989: [LoopTerminology] Loop Simplify Form.

Rebased

Fri, Feb 21, 3:25 PM · Restricted Project
baziotis created D74989: [LoopTerminology] Loop Simplify Form.
Fri, Feb 21, 3:16 PM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

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

Fri, Feb 21, 2:48 PM · Restricted Project
baziotis added a comment to D74890: [Analysis][Docs] Parents of loops documentation.

LGTM

Fri, Feb 21, 2:39 PM · Restricted Project
baziotis updated the diff for D74890: [Analysis][Docs] Parents of loops documentation.

Address comments. The addition in the terminology might be a little too short.

Fri, Feb 21, 2:20 PM · Restricted Project
baziotis added inline comments to D74890: [Analysis][Docs] Parents of loops documentation.
Fri, Feb 21, 2:02 PM · Restricted Project

Thu, Feb 20

baziotis added inline comments to D73428: [Attributor] Improve `noalias` deduction based on memory information.
Thu, Feb 20, 5:29 PM · Restricted Project
baziotis updated the diff for D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.
  • Rebased with AAUB not manifesting
Thu, Feb 20, 5:14 PM · Restricted Project
baziotis updated the diff for D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.

I've been looking today again at this and it's the first time in the Attributor that I don't understand what is happening. This diff contains some prints and the weirdest is the print that shows us that AAIsDeadFunction::initialize() is called multiple times (the manifest though none). I'll continue looking into this but any help is appreciated, I have lost episodes.

Thu, Feb 20, 3:25 PM · Restricted Project
baziotis added inline comments to D74890: [Analysis][Docs] Parents of loops documentation.
Thu, Feb 20, 2:58 PM · Restricted Project
baziotis updated the diff for D74890: [Analysis][Docs] Parents of loops documentation.
  • Address comment.
Thu, Feb 20, 6:04 AM · Restricted Project
baziotis added inline comments to D74890: [Analysis][Docs] Parents of loops documentation.
Thu, Feb 20, 4:52 AM · Restricted Project
baziotis created D74890: [Analysis][Docs] Parents of loops documentation.
Thu, Feb 20, 2:59 AM · Restricted Project
baziotis updated the summary of D74890: [Analysis][Docs] Parents of loops documentation.
Thu, Feb 20, 2:59 AM · Restricted Project
baziotis added inline comments to D74691: [Attributor] Detect SCCs with unbounded cycles.
Thu, Feb 20, 2:44 AM · Restricted Project

Wed, Feb 19

baziotis added inline comments to D74691: [Attributor] Detect SCCs with unbounded cycles.
Wed, Feb 19, 3:17 PM · Restricted Project
baziotis added a comment to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..

Fixed test which actually exposed a FIXME. Again for the same reason, it doesn't seem to get a known value from AAValueSimplify.
Should I go ahead and change to unreachable the assumed instructions as well? Meaning in manifest(), after the updates have finished.

Yes, I think something like that makes sense. Let's do that in a follow up though. This looks good now and I'll commit it once I get the chance.

Wed, Feb 19, 2:58 PM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

[...]
as the code puts on this function willreturn attribute and in the file read_write_returned_arguments_scc.ll it doesn't contain willreturn attribute so it gives an error with filecheck

It should have. Your extension to AAWillReturn should generally result in more willreturn attributes being deduced. That is the point after all. We need to verify each change to the CHECK lines though. We should also write explicit tests for loops with and without upper trip count limits, assuming we don't have them already.

Wed, Feb 19, 12:42 PM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

Caps on the name. Be sure to check the nearby code and use clang-format (it seems you have done so, just reminding).

I thought the default clang-format do it as required , I realized now that it is different :) , will fix it

Wed, Feb 19, 8:23 AM · Restricted Project
baziotis added inline comments to D74691: [Attributor] Detect SCCs with unbounded cycles.
Wed, Feb 19, 6:22 AM · Restricted Project
baziotis added a comment to D74801: [ADT][NFC] SCCIterator: Change hasLoop() to hasCycle().

lg

Wed, Feb 19, 4:36 AM · Restricted Project, Restricted Project

Tue, Feb 18

baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

First of all, try to get L. If you don't have a loop (so, L is null) then this
SCC is not a loop so return true immediately.

couldn't we use SCCiter.hasLoop() in addition to this condition to check for loops as this condition always breaks with me in tests like that which have SCCs with single block that does not have loops and the above condition makes them return true when they don't have any cycles ?

define void @only_return() #0 {
    ret void
}

Yes, you're right! I missed that.

Tue, Feb 18, 11:01 PM · Restricted Project
baziotis updated the diff for D74801: [ADT][NFC] SCCIterator: Change hasLoop() to hasCycle().

Self-cycle to self-loop

Tue, Feb 18, 3:56 PM · Restricted Project, Restricted Project
baziotis added inline comments to D74801: [ADT][NFC] SCCIterator: Change hasLoop() to hasCycle().
Tue, Feb 18, 3:47 PM · Restricted Project, Restricted Project
baziotis added a comment to D74801: [ADT][NFC] SCCIterator: Change hasLoop() to hasCycle().

While i certainly agree that it's kinda confusing, i'm not really sure this is conceptually correct change.
https://en.wikipedia.org/wiki/Loop_(graph_theory)

In graph theory, a loop (also called a self-loop or a "buckle") is an edge that connects a vertex to itself. A simple graph contains no loops.

which is exactly the case here.

https://en.wikipedia.org/wiki/Cycle_(graph_theory)
seems more generic than that.

Tue, Feb 18, 3:38 PM · Restricted Project, Restricted Project
baziotis updated subscribers of D74801: [ADT][NFC] SCCIterator: Change hasLoop() to hasCycle().

Seems fine.

Tue, Feb 18, 3:34 PM · Restricted Project, Restricted Project
baziotis created D74801: [ADT][NFC] SCCIterator: Change hasLoop() to hasCycle().
Tue, Feb 18, 3:15 PM · Restricted Project, Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

First of all, try to get L. If you don't have a loop (so, L is null) then this
SCC is not a loop so return true immediately.

couldn't we use SCCiter.hasLoop() in addition to this condition to check for loops as this condition always breaks with me in tests like that which have SCCs with single block that does not have loops and the above condition makes them return true when they don't have any cycles ?

define void @only_return() #0 {
    ret void
}
Tue, Feb 18, 2:56 PM · Restricted Project
baziotis added inline comments to D74691: [Attributor] Detect SCCs with unbounded cycles.
Tue, Feb 18, 10:25 AM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.
Failing Tests (74):
    LLVM :: Transforms/Attributor/ArgumentPromotion/2008-02-01-ReturnAttrs.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/2008-07-02-array-indexing.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/2008-09-07-CGUpdate.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/2008-09-08-CGUpdateSelfEdge.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/X86/attributes.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/X86/min-legal-vector-width.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/aggregate-promote.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/alignment.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/attrs.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/basictest.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/byval-2.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/byval.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/chained.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/control-flow.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/control-flow2.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/crash.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/dbg.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/fp80.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/inalloca.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/live_called_from_dead.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/live_called_from_dead_2.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/musttail.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/naked_functions.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/nonzero-address-spaces.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/pr27568.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/pr3085.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/pr32917.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/pr33641_remove_arg_dbgvalue.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/profile.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/reserve-tbaa.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/sret.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/tail.ll
    LLVM :: Transforms/Attributor/ArgumentPromotion/variadic.ll
    LLVM :: Transforms/Attributor/IPConstantProp/2009-09-24-byval-ptr.ll
    LLVM :: Transforms/Attributor/IPConstantProp/PR16052.ll
    LLVM :: Transforms/Attributor/IPConstantProp/PR26044.ll
    LLVM :: Transforms/Attributor/IPConstantProp/PR43857.ll
    LLVM :: Transforms/Attributor/IPConstantProp/arg-count-mismatch.ll
    LLVM :: Transforms/Attributor/IPConstantProp/arg-type-mismatch.ll
    LLVM :: Transforms/Attributor/IPConstantProp/comdat-ipo.ll
    LLVM :: Transforms/Attributor/IPConstantProp/dangling-block-address.ll
    LLVM :: Transforms/Attributor/IPConstantProp/fp-bc-icmp-const-fold.ll
    LLVM :: Transforms/Attributor/IPConstantProp/global.ll
    LLVM :: Transforms/Attributor/IPConstantProp/multiple_callbacks.ll
    LLVM :: Transforms/Attributor/IPConstantProp/musttail-call.ll
    LLVM :: Transforms/Attributor/IPConstantProp/naked-return.ll
    LLVM :: Transforms/Attributor/IPConstantProp/openmp_parallel_for.ll
    LLVM :: Transforms/Attributor/IPConstantProp/pthreads.ll
    LLVM :: Transforms/Attributor/IPConstantProp/recursion.ll
    LLVM :: Transforms/Attributor/IPConstantProp/remove-call-inst.ll
    LLVM :: Transforms/Attributor/IPConstantProp/return-argument.ll
    LLVM :: Transforms/Attributor/IPConstantProp/return-constant.ll
    LLVM :: Transforms/Attributor/IPConstantProp/return-constants.ll
    LLVM :: Transforms/Attributor/IPConstantProp/solve-after-each-resolving-undefs-for-function.ll
    LLVM :: Transforms/Attributor/IPConstantProp/thread_local_acs.ll
    LLVM :: Transforms/Attributor/align.ll
    LLVM :: Transforms/Attributor/callbacks.ll
    LLVM :: Transforms/Attributor/heap_to_stack.ll
    LLVM :: Transforms/Attributor/internal-noalias.ll
    LLVM :: Transforms/Attributor/liveness.ll
    LLVM :: Transforms/Attributor/liveness_chains.ll
    LLVM :: Transforms/Attributor/lvi-after-jumpthreading.ll
    LLVM :: Transforms/Attributor/lvi-for-ashr.ll
    LLVM :: Transforms/Attributor/memory_locations.ll
    LLVM :: Transforms/Attributor/misc.ll
    LLVM :: Transforms/Attributor/noalias.ll
    LLVM :: Transforms/Attributor/nocapture-1.ll
    LLVM :: Transforms/Attributor/nonnull.ll
    LLVM :: Transforms/Attributor/norecurse.ll
    LLVM :: Transforms/Attributor/range.ll
    LLVM :: Transforms/Attributor/read_write_returned_arguments_scc.ll
    LLVM :: Transforms/Attributor/readattrs.ll
    LLVM :: Transforms/Attributor/reduced/register_benchmark_test.ll
    LLVM :: Transforms/Attributor/willreturn.ll

  Expected Passes    : 17
  Unexpected Failures: 74

the code I have updated fails in nearly all the tests , I think all the tests fails because the function always returns true not false so what could possibly result in that ?

Tue, Feb 18, 8:44 AM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

Thanks for this great reviews :)

No problem.

They're equal: This SCC is a loop, continue to the next.
The loop is bigger: The SCC is not a loop, return.

@baziotis Shouldn't this conditions be reversed as when we find a loop we should check the max trip count and return if it was 0 , and when the loop is bigger we should continue looping on the SCCs ?

Tue, Feb 18, 7:21 AM · Restricted Project

Mon, Feb 17

baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

Edit: Alternatively, we could loop through the SCCs and check if any of them is not a loop but I didn't find an easy way to do that.

@omarahmed I think @baziotis has a really good point here. Let's do it this way :)

:)
Here's something I hadn't thought when I wrote it. But before that, @omarahmed be sure to check the loop terminology (https://llvm.org/docs/LoopTerminology.html) and pay extra attention to the dominance ('cause you mind another way using it). And that not every SCC is a loop.
Now, I hope that what I'll say below is correct. I'm not a loop guru, so take it with a grain of salt.
To check if an SCC is a loop, take a random BB (e.g. the first) in the SCC and check if it's in a loop (as you did, with getLoopFor()). Then, compare the size (that is, the number of blocks) of the SCC (.size()) with the size of the loop (.getNumBlocks() IIRC). 3 cases:

  • They're equal: This SCC is a loop, continue to the next.
  • The loop is bigger: The SCC is not a loop, return.
  • The loop is smaller: Unfortunately, that is tricky. If the loop is smaller, we can't deduce that the SCC is not a loop because getLoopFor() gives you the innermost loop. Consider that the SCC has the blocks: A, B, C. The blocks A,B might make a loop. But the blocks A, B, C might also make a loop (I don't know if that can happen with 2 vs 3 blocks but you get the point). If the random node you picked happens to be A, then getLoopFor() will give you the A, B loop back. But, note that A, B is a child loop of A, B, C. How that could help us? :)

In the last case you do L = L->getParentLoop() and go back as if this was the return of getLoopFor().

Yep.

P.S. 2 vs 3 blocks can happen, since you have single block loops.

Mon, Feb 17, 3:41 AM · Restricted Project
baziotis added inline comments to D73428: [Attributor] Improve `noalias` deduction based on memory information.
Mon, Feb 17, 3:41 AM · Restricted Project
baziotis added inline comments to D73428: [Attributor] Improve `noalias` deduction based on memory information.
Mon, Feb 17, 3:32 AM · Restricted Project

Sun, Feb 16

baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

Edit: Alternatively, we could loop through the SCCs and check if any of them is not a loop but I didn't find an easy way to do that.

@omarahmed I think @baziotis has a really good point here. Let's do it this way :)

Sun, Feb 16, 6:09 PM · Restricted Project
baziotis added a comment to D74691: [Attributor] Detect SCCs with unbounded cycles.

I'm not sure whether we can say if all the loops given by LoopInfo have a max trip count and all the callees are willreturn, then we can guarantee the termination of that function.

We can not. But if all cycles in the CFG are loops recognized by loop info and they have a max trip count we are good (in this part), I think.

How can we confirm all cycles in the CFG are recognized actually by loop info? Is there a simple way?

What @omarahmed does here should work (with the fixes I mentioned). 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. Do you think there is a problem with that logic?

Sun, Feb 16, 4:39 PM · Restricted Project

Fri, Feb 14

baziotis added inline comments to D73428: [Attributor] Improve `noalias` deduction based on memory information.
Fri, Feb 14, 7:22 PM · Restricted Project
baziotis added a comment to D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.

I forgot about this. Can we rebase it :) ?

Fri, Feb 14, 5:42 PM · Restricted Project
baziotis updated the diff for D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..

Fixed test which actually exposed a FIXME. Again for the same reason, it doesn't seem to get a known value from AAValueSimplify.
Should I go ahead and change to unreachable the assumed instructions as well? Meaning in manifest(), after the updates have finished.

Fri, Feb 14, 4:39 PM · Restricted Project
baziotis added a comment to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..

One last nit with one of the tests, then I'll commit this.

Fri, Feb 14, 4:22 PM · Restricted Project
baziotis added a comment to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..

I have a similar case how to exploit UB to simplify code:

int process(char *p) __attribute__((nonnull));


void doit(bool b, char *d) {
    char *p = 0;
    if (b)
        p = d;
    process(p);
}

https://godbolt.org/z/eYcApm

In this case, it is invalid to call process with null pointer since args are nonnull, so we can remove branch and call process(d) directly.

Fri, Feb 14, 2:30 PM · Restricted Project
baziotis updated the diff for D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..

Now tests are a lot better!

Fri, Feb 14, 9:45 AM · Restricted Project
baziotis added a comment to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
  • Added tests

All the tests have FIXMEs, right? Can you explain why they don't work yet?

Yes. For most tests the reason is that AAValueSimplify doesn't give a known value. In other words, in stopOnUndefOrAssumed(), we don't get past the first if (if (!ValueSimplifyAA.isKnown())).

Seeing that again though, returning from this if effectively means that the instruction remains assumed UB.
The whole procedure ends with the instruction still assumed UB. So, doesn't that fixpoint to known UB actually ?

But then, check this:

define internal i32* @ret_null(i32* %A) {
  ret i32* %A
}

define void @load_null_propagated(i32* %A) {
  %ptr = call i32* @ret_null(i32* %A)
  %a = load i32, i32* %ptr
  ret void
}

The output is (same with AAUB disabled):

define void @load_null_propagated(i32* nocapture nofree readonly %A) #0 {
  %a = load i32, i32* undef
  ret void
}

First of all, even if what I said above is correct, AAValueSimplify still gives us no value for the pointer which keeps an actually non-UB instruction to assumed till the end.
But then second, isn't that output wrong in general ?

I think this is a bad artifact of our current "code deletion" at the end of the Attributor run. Make the load live and it will not happen, I mean, the load in the example above can be removed either way.

Fri, Feb 14, 9:18 AM · Restricted Project

Thu, Feb 13

baziotis added a comment to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
  • Added tests

All the tests have FIXMEs, right? Can you explain why they don't work yet?

Thu, Feb 13, 6:55 PM · Restricted Project

Wed, Feb 12

baziotis updated the diff for D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
  • Added tests
Wed, Feb 12, 4:58 PM · Restricted Project
baziotis added a comment to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
  • Update commit message and test cases

    in ArgumentPromotion/2008-07-02-array-indexing.ll, there was a weird align value that was only in the CHECK directives so it didn't seem it was coming from somewhere. I had to change it to make it pass. Please verify that it is not needed.

The align was "derived" from a null pointer, which has every alignment. Since you made the UB go away by using an argument instead of loading from null, the alignment is no longer deduced. All as expected :)

Ok and so it put a random value, got it :)

  1. add a test that checks the functionality. the test changes in this patch "repair" existing tests to not expose unwanted UB but we want to have at least one test that exhibits UB and which gets exploited due to this patch.

Something more complicated than load_null_propagated() and / or cond_br_on_undef* functions (in undefined_behavior.ll testcase) ?

Nothing complicated. Along those lines but as far as I can tell this patch does not include changes to these tests, correct?

Wed, Feb 12, 4:31 PM · Restricted Project
baziotis added a comment to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
  1. add a test that checks the functionality. the test changes in this patch "repair" existing tests to not expose unwanted UB but we want to have at least one test that exhibits UB and which gets exploited due to this patch.
Wed, Feb 12, 9:38 AM · Restricted Project
baziotis updated the diff for D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
  • Update commit message and test cases
Wed, Feb 12, 9:38 AM · Restricted Project

Mon, Feb 10

baziotis added a comment to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..

Anything else needed for that?

Mon, Feb 10, 11:50 AM · Restricted Project
baziotis added a comment to D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.

Sorry for being late, this is an exam period so time is very limited. I saw again the problem and it changed a bit but it's similar. To be sure we're on the same page:
In this:

define i32 @example(i1* %alloc) {
  %cond = load i1, i1* %alloc
  br i1 %cond, label %t, label %e
t:
  ret i32 1
e:
  ret i32 2
}

The block of br initially is assumed live, but AAIsDeadFunction::updateImpl() is called, which, because the br is assumed UB, removes the block from the AssumedLiveBlocks.
AAUB looks only live instructions and the br now will never be live (also maybe the fact that we're removing - and it's the only place - messes with the monotony).

Mon, Feb 10, 11:50 AM · Restricted Project

Jan 12 2020

baziotis added inline comments to D72562: [Attributor][Fix] AAHeapToStack and AAIsDead connection.
Jan 12 2020, 9:57 AM · Restricted Project

Jan 7 2020

baziotis retitled D71435: [Attributor] Function level undefined behavior attribute from [WIP] [Attributor] Function level undefined behavior attribute to [Attributor] Function level undefined behavior attribute.
Jan 7 2020, 3:04 AM · Restricted Project

Jan 2 2020

baziotis updated the diff for D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
  • Repaired test case.
Jan 2 2020, 3:45 PM · Restricted Project
baziotis added inline comments to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
Jan 2 2020, 3:36 PM · Restricted Project

Jan 1 2020

baziotis updated the diff for D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
  • Updated tests
Jan 1 2020, 5:15 PM · Restricted Project
baziotis added inline comments to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
Jan 1 2020, 5:15 PM · Restricted Project

Dec 31 2019

baziotis added inline comments to D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.
Dec 31 2019, 5:35 PM · Restricted Project
baziotis added inline comments to D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.
Dec 31 2019, 11:17 AM · Restricted Project
baziotis added inline comments to D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.
Dec 31 2019, 10:07 AM · Restricted Project
baziotis added inline comments to D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.
Dec 31 2019, 10:02 AM · Restricted Project
baziotis accepted D72016: [Attributor] Propagate known information from `checkForAllCallSites`.

LGTM too.

Dec 31 2019, 9:53 AM · Restricted Project
baziotis added inline comments to D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.
Dec 31 2019, 9:05 AM · Restricted Project
baziotis added inline comments to D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.
Dec 31 2019, 8:53 AM · Restricted Project
baziotis added inline comments to D72016: [Attributor] Propagate known information from `checkForAllCallSites`.
Dec 31 2019, 8:19 AM · Restricted Project

Dec 30 2019

baziotis added inline comments to D72016: [Attributor] Propagate known information from `checkForAllCallSites`.
Dec 30 2019, 4:12 PM · Restricted Project
baziotis updated the diff for D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.

Thanks for your suggestion Johannes, fortunately that was an easy change. But it also impacts about 26 tests or so, which I won't be able to fix today.
However now the interaction between AAUB and AAIsDead becomes interesting. For example, for this code:

define internal i1 @ret_undef() {
  ret i1 undef
}
Dec 30 2019, 3:56 PM · Restricted Project
baziotis added a comment to D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.

Similarly, in AAUB we should go through the explorer context when we add something to the knownUB set. So if I is knownUB, make all instructions in the must-be-executed-context of I knownUB, thus insert all into the set. In AAIsDead we can then simply query isKnownUB and that will only need to look into the set (as before).

If I understand it correctly, this will mark as UB all the instructions from the UB instruction and forwards (i.e. the must be executed context goes to the successors). That will probably complicate things as to see if a BB is dead, with the current code, it makes sense to see its first instruction right?

The must-be-executed-context is not defined to only contain "successors". It might right now but that will change eventually.


I think we should stick to known information right now.

Ok, isAssumedToCauseUB() is overoptimistic right now.

Dec 30 2019, 11:21 AM · Restricted Project
baziotis added inline comments to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
Dec 30 2019, 10:14 AM · Restricted Project
baziotis added inline comments to D71960: [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
Dec 30 2019, 8:50 AM · Restricted Project
baziotis added inline comments to D71974: [Attributor][WIP] Connect AAIsDead with AAUndefinedBehavior.
Dec 30 2019, 6:57 AM · Restricted Project