Page MenuHomePhabricator

omarahmed (omar ahmed)
User

Projects

User does not belong to any projects.

User Details

User Since
Feb 14 2020, 9:35 PM (129 w, 1 d)

omarpiratee2010@gmail.com

Recent Activity

Fri, Jul 15

omarahmed updated the diff for D127270: [clang-format] Add space in placement new expression.

Change removes to remove

Fri, Jul 15, 7:00 PM · Restricted Project, Restricted Project, Restricted Project

Wed, Jul 13

omarahmed added a comment to D127270: [clang-format] Add space in placement new expression.

I don't have push credentials so If everything is okay with the patch, can you push it for me. My email is omarpiratee2010@gmail.com

Wed, Jul 13, 1:27 PM · Restricted Project, Restricted Project, Restricted Project
omarahmed updated omarahmed.
Wed, Jul 13, 1:27 PM

Jun 22 2022

omarahmed updated the diff for D127270: [clang-format] Add space in placement new expression.

Format files

Jun 22 2022, 3:36 AM · Restricted Project, Restricted Project, Restricted Project

Jun 21 2022

omarahmed updated the diff for D127270: [clang-format] Add space in placement new expression.

Format files

Jun 21 2022, 8:36 AM · Restricted Project, Restricted Project, Restricted Project
omarahmed added inline comments to D127270: [clang-format] Add space in placement new expression.
Jun 21 2022, 5:39 AM · Restricted Project, Restricted Project, Restricted Project
omarahmed updated the diff for D127270: [clang-format] Add space in placement new expression.

Change the default to APO_Leave

Jun 21 2022, 5:32 AM · Restricted Project, Restricted Project, Restricted Project

Jun 20 2022

omarahmed added inline comments to D127270: [clang-format] Add space in placement new expression.
Jun 20 2022, 10:02 AM · Restricted Project, Restricted Project, Restricted Project
omarahmed added inline comments to D127270: [clang-format] Add space in placement new expression.
Jun 20 2022, 9:53 AM · Restricted Project, Restricted Project, Restricted Project
omarahmed updated the diff for D127270: [clang-format] Add space in placement new expression.
  • Add version for nestedEnums and nestedFields
  • Make tests valid
Jun 20 2022, 9:53 AM · Restricted Project, Restricted Project, Restricted Project

Jun 17 2022

omarahmed updated the diff for D127270: [clang-format] Add space in placement new expression.

Add Parse check

Jun 17 2022, 11:25 AM · Restricted Project, Restricted Project, Restricted Project
omarahmed added a comment to D127270: [clang-format] Add space in placement new expression.

As I understand, the default behavior for when the user didn't use SBPO_Custom is to add a space in placement operators based on this issue. And, at the same time, the default behavior should be APO_Never when we have SBPO_Custom so that we handle other code that depends on that. the existing tests confirm this understanding. So, the current logic was added based on this understanding.

Jun 17 2022, 10:38 AM · Restricted Project, Restricted Project, Restricted Project
omarahmed updated the diff for D127270: [clang-format] Add space in placement new expression.

Refactor the tests and add new parsing logic for nested enums in dump_format_style.py

Jun 17 2022, 10:38 AM · Restricted Project, Restricted Project, Restricted Project
omarahmed added inline comments to D127270: [clang-format] Add space in placement new expression.
Jun 17 2022, 2:32 AM · Restricted Project, Restricted Project, Restricted Project

Jun 16 2022

omarahmed added a comment to D127270: [clang-format] Add space in placement new expression.

Does this patch really fix https://github.com/llvm/llvm-project/issues/54703?
If so, please add test for it. Otherwise remove the link from the summary (and if possible handle it in another review).

Jun 16 2022, 1:20 AM · Restricted Project, Restricted Project, Restricted Project
omarahmed updated the diff for D127270: [clang-format] Add space in placement new expression.

Add coverage for placement delete expressions and transform bool option to enum

Jun 16 2022, 1:19 AM · Restricted Project, Restricted Project, Restricted Project

Jun 12 2022

omarahmed added inline comments to D127270: [clang-format] Add space in placement new expression.
Jun 12 2022, 6:36 AM · Restricted Project, Restricted Project, Restricted Project

Jun 11 2022

omarahmed updated the summary of D127270: [clang-format] Add space in placement new expression.
Jun 11 2022, 11:04 AM · Restricted Project, Restricted Project, Restricted Project

Jun 7 2022

omarahmed requested review of D127270: [clang-format] Add space in placement new expression.
Jun 7 2022, 9:10 PM · Restricted Project, Restricted Project, Restricted Project

Apr 14 2020

omarahmed added a comment to D76550: [Attributor] Improve the alignment of the loads.

@jdoerfert ping :)

Apr 14 2020, 4:13 AM · Restricted Project

Apr 10 2020

omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Merge the patch with the new Attributor files structure

Apr 10 2020, 10:14 AM · Restricted Project

Apr 4 2020

omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Minor fix

Apr 4 2020, 1:49 PM · Restricted Project
omarahmed added a comment to D76550: [Attributor] Improve the alignment of the loads.

Sry for a lot of reformating patches, didn't know that i should rebuild clang format :)
My data :
Omar Ahmed <omarpirate2010@yahoo.com>

Apr 4 2020, 1:49 PM · Restricted Project
omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Minor format

Apr 4 2020, 1:17 PM · Restricted Project
omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Make the dependence optional
omar ahmed <omarpirate2010@yahoo.com>

Apr 4 2020, 11:41 AM · Restricted Project

Apr 3 2020

omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Minor formatting

Apr 3 2020, 9:38 PM · Restricted Project
omarahmed added a comment to D76550: [Attributor] Improve the alignment of the loads.

I think what you can do is to precompute the AAAlign in manifest instead of doing this

Apr 3 2020, 9:06 PM · Restricted Project
omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Minor fix

Apr 3 2020, 8:34 PM · Restricted Project
omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Precompute the alignment for the loads in manifest and add test with different alignment privatizable arguments

Apr 3 2020, 9:40 AM · Restricted Project

Apr 1 2020

omarahmed added a comment to D76550: [Attributor] Improve the alignment of the loads.

sry for late update, Hard times
Anyway I wanted to ask about a thing i noticed in AAPrivatizable attribute :

Apr 1 2020, 2:04 PM · Restricted Project
omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Usage of AssumeAligned to force natural alignment

Apr 1 2020, 1:30 PM · Restricted Project

Mar 23 2020

omarahmed added a comment to D76550: [Attributor] Improve the alignment of the loads.

If you always deal with defined alignment there is no need to use MaybeAlign.
Use Align in createReplacementValues (it will get rid of the extra if check).

Now, LoadInst::setAlignment takes a MaybeAlign but Align implicitly casts to MaybeAlign so you can safely pass in an Align (I'll optimize this case by providing setAlignment overloads later).

Then if you get raw alignment values that can be 0 but you assume that 0 means 1 use [assumeAligned](https://github.com/llvm/llvm-project/blob/ccf49b9ef012bab44b1f1322223e8b2e5ca89bad/llvm/include/llvm/Support/Alignment.h#L114).
Unfortunately the naming in this context is awkward (but that's how the API is supposed to be used) assumeAligned(AlignAA.getAssumedAlign()).

It will become better over time when AlignAA deals with Align/MaybeAlign directly.

Mar 23 2020, 9:15 AM · Restricted Project

Mar 22 2020

omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Add ArgumentPromotion/Basictest.ll to XFAIL,
Minor cleanup.

Mar 22 2020, 3:01 PM · Restricted Project
omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Minor cleanups

Mar 22 2020, 1:55 PM · Restricted Project
omarahmed added a comment to D76550: [Attributor] Improve the alignment of the loads.
Mar 22 2020, 12:51 PM · Restricted Project
omarahmed updated the summary of D76550: [Attributor] Improve the alignment of the loads.
Mar 22 2020, 11:44 AM · Restricted Project
omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Minor cleanups

Mar 22 2020, 11:44 AM · Restricted Project
omarahmed added inline comments to D76550: [Attributor] Improve the alignment of the loads.
Mar 22 2020, 9:04 AM · Restricted Project
omarahmed added a comment to D76550: [Attributor] Improve the alignment of the loads.

Basictest.ll always make a strange problem with me sometimes the align of the load be 0 and from the condition I added it transform to 1, and in other times it gives align to the load with 4 value so why this could happen ?

Mar 22 2020, 7:59 AM · Restricted Project
omarahmed updated the diff for D76550: [Attributor] Improve the alignment of the loads.

Address comments

Mar 22 2020, 7:59 AM · Restricted Project

Mar 21 2020

omarahmed added a comment to D76550: [Attributor] Improve the alignment of the loads.

You should query the base alignment AA in the initialize once to make sure it exists and is part of the fixpoint iteration. For now that is trivially the case but I can see that this might not be this way in the future.

Mar 21 2020, 1:52 PM · Restricted Project
omarahmed retitled D76550: [Attributor] Improve the alignment of the loads from Improve the alignment of the loads to [Attributor] Improve the alignment of the loads.
Mar 21 2020, 12:15 PM · Restricted Project
omarahmed created D76550: [Attributor] Improve the alignment of the loads.
Mar 21 2020, 12:15 PM · Restricted Project

Mar 13 2020

omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

Got it, Thanks :)

Mar 13 2020, 11:19 AM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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 ?

Mar 13 2020, 10:11 AM · Restricted Project

Mar 11 2020

omarahmed updated the summary of D74691: [Attributor] Detect possibly unbounded cycles in functions.
Mar 11 2020, 6:18 AM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

Update commit message

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

Mar 11 2020, 6:18 AM · Restricted Project
omarahmed updated the summary of D74691: [Attributor] Detect possibly unbounded cycles in functions.
Mar 11 2020, 6:18 AM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

Update commit message

Mar 11 2020, 5:08 AM · Restricted Project

Mar 10 2020

omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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

Mar 10 2020, 4:58 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

Minor cleanup

Mar 10 2020, 4:58 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

Minor cleanups

Mar 10 2020, 9:46 AM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

Minor cleanups

Mar 10 2020, 9:46 AM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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 ?

Mar 10 2020, 8:39 AM · Restricted Project

Mar 9 2020

omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

Patch updates :

Mar 9 2020, 6:54 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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

Mar 9 2020, 2:03 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

Patch updates :

Mar 9 2020, 1:30 PM · Restricted Project

Mar 8 2020

omarahmed added inline comments to D74691: [Attributor] Detect possibly unbounded cycles in functions.
Mar 8 2020, 8:14 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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 ?

Mar 8 2020, 6:06 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

Patch updates :

Mar 8 2020, 4:31 PM · Restricted Project
omarahmed added inline comments to D74691: [Attributor] Detect possibly unbounded cycles in functions.
Mar 8 2020, 1:20 PM · Restricted Project

Mar 7 2020

omarahmed added inline comments to D74691: [Attributor] Detect possibly unbounded cycles in functions.
Mar 7 2020, 6:20 PM · Restricted Project
omarahmed added inline comments to D74691: [Attributor] Detect possibly unbounded cycles in functions.
Mar 7 2020, 5:48 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

[Attributor] Detect possibly unbounded cycles in functions

Mar 7 2020, 1:33 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

[Attributor] Detect possibly unbounded cycles in functions

Mar 7 2020, 12:59 PM · Restricted Project

Mar 5 2020

omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.
  • 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).

Mar 5 2020, 5:31 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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

Mar 5 2020, 7:08 AM · Restricted Project

Mar 4 2020

omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

[Attributor]Detect possibly unbounded cycles in functions

Mar 4 2020, 10:58 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

[Attributor]Detect possibly unbounded cycles in functions

Mar 4 2020, 10:25 PM · Restricted Project

Mar 3 2020

omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

Please add a non-loop cycle test case, aka. irreducible control flow test case.

okay I will add it in the next diff :)

Mar 3 2020, 2:24 PM · Restricted Project

Feb 28 2020

omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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 ?

Feb 28 2020, 11:51 AM · Restricted Project

Feb 26 2020

omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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.

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.

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

Feb 26 2020, 1:24 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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

Can u share the IR (with the appropriate RUN lines, thus tests) not the images please?

Feb 26 2020, 3:00 AM · Restricted Project

Feb 25 2020

omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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

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.

Feb 25 2020, 4:17 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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

Feb 25 2020, 3:32 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.
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;
}
Feb 25 2020, 11:05 AM · Restricted Project
omarahmed retitled D74691: [Attributor] Detect possibly unbounded cycles in functions from [Attributor]Detect functions with unbounded loops to [Attributor] Detect possibly unbounded cycles in functions.
Feb 25 2020, 8:17 AM · Restricted Project

Feb 24 2020

omarahmed retitled D74691: [Attributor] Detect possibly unbounded cycles in functions from [Attributor] Detect SCCs with unbounded cycles to [Attributor]Detect functions with unbounded loops.
Feb 24 2020, 4:09 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

[Attributor]Detect functions with unbounded loops

Feb 24 2020, 4:09 PM · Restricted Project

Feb 23 2020

omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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.

Feb 23 2020, 4:10 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

@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;
; }

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.

Feb 23 2020, 3:20 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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

Feb 23 2020, 2:05 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

[Attributor]Detect SCCs with unbounded cycles

Feb 23 2020, 11:54 AM · Restricted Project
omarahmed retitled D74691: [Attributor] Detect possibly unbounded cycles in functions from [Attributor] add some pattern to containsCycle to [Attributor] Detect SCCs with unbounded cycles.
Feb 23 2020, 11:45 AM · Restricted Project
omarahmed updated the summary of D74691: [Attributor] Detect possibly unbounded cycles in functions.
Feb 23 2020, 11:45 AM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

[Attributor]Detect SCCs with unbounded cycles

Feb 23 2020, 4:29 AM · Restricted Project

Feb 22 2020

omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

minor updates and added tests

Feb 22 2020, 9:26 PM · Restricted Project
omarahmed added inline comments to D74691: [Attributor] Detect possibly unbounded cycles in functions.
Feb 22 2020, 12:20 PM · Restricted Project

Feb 21 2020

omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

improve the docs and add tests

Feb 21 2020, 6:27 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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

Feb 21 2020, 6:27 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.
  • improve the docs and add tests
Feb 21 2020, 6:18 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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

Feb 21 2020, 12:46 PM · Restricted Project

Feb 19 2020

omarahmed added inline comments to D74691: [Attributor] Detect possibly unbounded cycles in functions.
Feb 19 2020, 5:01 PM · Restricted Project
omarahmed added inline comments to D74691: [Attributor] Detect possibly unbounded cycles in functions.
Feb 19 2020, 5:01 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

Can we write some explicit tests and add them to the willreturn.ll file?

Feb 19 2020, 2:57 PM · Restricted Project
omarahmed added inline comments to D74691: [Attributor] Detect possibly unbounded cycles in functions.
Feb 19 2020, 2:46 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

some cleanups and modify some tests

Feb 19 2020, 2:39 PM · Restricted Project
omarahmed updated the diff for D74691: [Attributor] Detect possibly unbounded cycles in functions.

some cleanups and modify some tests

Feb 19 2020, 2:27 PM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

In this test shouldn't it have the attribute willreturn

Feb 19 2020, 9:52 AM · Restricted Project
omarahmed added a comment to D74691: [Attributor] Detect possibly unbounded cycles in functions.

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

Feb 19 2020, 7:28 AM · Restricted Project