search for: backedges

Hi all, It looks like the induction variable simplification pass prefers doing a zero-extension to compute the wider trip count of loops when extending the IV. This can sometimes result in loss of information making ScalarEvolution's analysis conservative which can lead to missed performance opportunities. For example, consider this loopnest- int i, j; for(i=0; i< 40; i++) for(j=0;

Hi: I hope to cut all backedges of MachineFunction CFG, then topological sort MachineBasicBlocks. 1. MachineDominatorTree *domintree = new MachineDominatorTree(); domintree->runOnMachineFunction(mf); 2. Then travel mf one by one. When domintree->dominates(next,current) is true, there is a backedge from current node...

...er I finish one node, push it into a stack. [0, 1, 2, M] <---push. [0, 1, 2, M,...N] <---push. When resolving node M, find a edge from node N to node M, N is not in stack(M < N), It is a backedge. N is in stack(M > N), It is NOT a backedge. I treat these backedges as loop-edges. M is Loop header node. If I cut these edges from CFG, CFG can be topological sort. Am I right??? --- 10年1月26日，周二, Benoit Boissinot <bboissin+llvm at gmail.com> 写道： > 发件人: Benoit Boissinot <bboissin+llvm at gmail.com> > 主题: Re: [LLVMdev] Find all back...

2010/1/25 任坤 <hbrenkun at yahoo.cn>: > Hi: > > I hope to cut all backedges of MachineFunction CFG, then topological sort MachineBasicBlocks. > > 1. MachineDominatorTree *domintree = new MachineDominatorTree(); > domintree->runOnMachineFunction(mf); > > 2. Then travel mf one by one. > When domintree->dominates(next,current) is true, there is a b...

Hello, If I run clang on the following code: void func(unsigned n) { > for (unsigned long x = 1; x < n; ++x) > dummy(x); > } I get the following llvm ir: define void @func(i32 %n) { > entry: > %conv = zext i32 %n to i64 > %cmp5 = icmp ugt i32 %n, 1 > br i1 %cmp5, label %for.body, label %for.cond.cleanup > for.cond.cleanup:

Hello. I tried to get the trip count of a loop with Scalar evolution. I got inspired from http://stackoverflow.com/questions/13834364/how-to-get-loop-bounds-in-llvm . However the analysis described there doesn't work well for the second inner loop of thes function below (although if we declare Bcols a short it works well): void MatMul(int Arows, int Acols, int Brows, int

Hello, I am trying to use scalar evolution pass using following command; opt -analyze -mem2reg -indvars -loop-simplify -scalar-evolution < vec.bc when vec.bc is generated using newer version of LLVM i.e LLVM 6 and 7 i get following message in the end; Determining loop execution counts for: @main Loop %8: Unpredictable backedge-taken count. Loop %8: Unpredictable max backedge-taken count. Loop

Hi, It looks like ScalarEvolution bails out of loop backedge computation if it cannot prove the IV stride as either positive or negative (based on loop control condition). I think this logic can be refined for signed IVs. Consider this simple loop- void foo(int *A, int n, int s) { int i; for(i=0; i<n; i += s) { A[i]++; } } The IV of this loop has this SCEV form-

Hi, How do I find out if a branch instruction belongs to an if-else or a loop i.e it is a backedge. Thanks, Bhavani

...preheaders anyway; LoopSimplify will recreate them, and they don't really block other optimizations as far as I know. > Is that reasonable approach or do we need to skip only if the original > unconditional branch was a backedge and folding this branch might > result in additional backedges? I made a quick hack to find the > function backedges and skip simplifycfg to merge the latch block into > the loop header when it results in an additional backedge. Although it > solves my purpose I am not sure if this the right approach, as finding > the backedges looks expensive....

Hi Sanjoy, I have attached the IR I got by compiling with -O2. This is just before we widen the IV. To get the backedge taken count info I ran indvars on it and then replaced zext with sext. I think regardless of where we decide to add this transformation in the pipeline, it should try to preserve as much information as it can. This means that we should generate sext for signed IVs and

Is that why we do not deduce +<nsw> from "add nsw" either? Is that an intrinsic limitation of creating a context-invariant expressions from a Value* or is that a limitation of our implementation (our unification not considering the nsw flags)? On Wed, Aug 15, 2018 at 12:39 PM Friedman, Eli <efriedma at codeaurora.org> wrote: > On 8/15/2018 12:21 PM, Alexandre Isoard via

...****************************** I copy find from MachineLICM.cpp, and change class name. What is different ?? Thanks. Ren Kun --- 10年1月26日，周二, Benoit Boissinot <bboissin+llvm at gmail.com> 写道： > 发件人: Benoit Boissinot <bboissin+llvm at gmail.com> > 主题: Re: [LLVMdev] Find all backedges of CFG by MachineDominatorTree.  please look at my jpg. > 收件人: "任坤" <hbrenkun at yahoo.cn> > 抄送: "llvm" <llvmdev at cs.uiuc.edu> > 日期: 2010年1月26日,周二,下午10:13 > On Tue, Jan 26, 2010 at 10:04:16PM > +0800, 浠诲潳   wrote: > > Hi, Dear Boissinot: > &...

Thank You.. I used following command to generate .bc or .ll /Documents/clang+llvm-4.0.0-x86_64-linux-gnu-ubuntu-16.04/bin/clang -O0 -emit-llvm -S -o vec4.ll vecsum.c /Documents/clang+llvm-7.0.0-x86_64-linux-gnu-ubuntu-16.04/bin/clang -O0 -emit-llvm -S -o vec7.ll vecsum.c On Wed, Jan 16, 2019 at 6:49 AM Sanjoy Das <sanjoy at playingwithpointers.com> wrote: > It is hard to tell

The Problem? Nowaday, SCEV called "Scalar Evolution" does only evolate instructions that has predictable operand, Constant-Based operand. such as that can evolute as a constant. otherwise we couldn't evolate it as SCEV node, evolated as SCEVUnknown. important thing that we remember is, we do not use SCEV only for Loop Deletion, which that doesn't really needed on nature loops

...Dominator Tree can not find some backedge. Is it means some MachineLoop is not be found? dominatorTree.jpg is a previous exmaple. best regards! renkun --- 10年3月9日，周二, Nick Lewycky <nicholas at mxc.ca> 写道： > 发件人: Nick Lewycky <nicholas at mxc.ca> > 主题: Re: [LLVMdev] Find all backedges of CFG by MachineDominatorTree. please look at my jpg. > 收件人: "任坤" <hbrenkun at yahoo.cn> > 抄送: "Benoit Boissinot" <bboissin+llvm at gmail.com>, "llvm" <llvmdev at cs.uiuc.edu> > 日期: 2010年3月9日,周二,下午2:02 > 任坤   wrote: > > Hi: > &gt...

...the backedge taken count as "(B - A) / 5" (roughly :) ) since if (B - A) is not divisible by 5 then we have UB due to overflow. We just have to be careful around cases like: for(i = 0; i < 60; i += s) { may_exit(); } "s" can be (say) -3 and the loop can take 160 backedges and then "exit(0)", avoiding the undefined behavior due to underflow. "s" can also be zero, in which case the loop can potentially take an infinite number of backedges. However, in the example you gave (written in LLVM's canonical rotated form): if (0 < N) { i...

...to an earlier or later basic block. Micah -----Original Message----- From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of bhavani krishnan Sent: Wednesday, December 03, 2008 3:20 PM To: Nick Lewycky; LLVM Developers Mailing List Subject: [LLVMdev] Identifying backedges Hi, How do I find out if a branch instruction belongs to an if-else or a loop i.e it is a backedge. Thanks, Bhavani _______________________________________________ LLVM Developers mailing list LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listin...

...uter loop is > not loop invariant. As a result the loop cannot be unrolled. Is this > the intended canonicalization for this loop or is the loopsimplify > canonicalizing incorrectly? Should simplifycfg skip folding the latch > block into the loop header if this results in additional backedges and > let the empty blocks be folded during CGP? More details in > https://bugs.llvm.org/show_bug.cgi?id=33605. > We have code that's supposed to prevent this from happening; see https://reviews.llvm.org/rL264697 . Maybe it also needs to check whether the destination of the branc...

...to be in canonical form with a single backedge to which we attach llvm.loop.parallel? Or is it the frontend's responsibility to attach the metadata to each backedge? Looking at the patch there is an assumption that there is a single loop latch. Clang, for example, generates loops with multiple backedges (e.g, while with continue.) How does pocl deal with this? paul On 2013-02-13, at 1:13 PM, Pekka Jääskeläinen wrote: > On 02/12/2013 11:59 PM, Nadav Rotem wrote: >> LGTM. Please commit. > > Committed in r175060. Thanks all for the feedback. > > Yes, let's see what evol...