search for: backedge

...an 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; j< i-1; j++) A[i+j] = j; We are mainly interested in the backedge taken count of the inner loop. Before indvars, the backedge information computed by ScalarEvolution is as follows- Outer loop- backedge-taken count is 39 max backedge-taken count is 39 Inner loop- backedge-taken count is {-2,+,1}<nsw><%for.cond1.preheader> max backedge-taken count is...

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

Hi, Dear Boissinot: 1. When I have irreducible CFG, I travel its nodes by DFS. search backedge for every node. After 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...

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

...ispositions: > { %for.body: Computable } > %inc = add nuw nsw i64 %x.06, 1 > --> {2,+,1}<nuw><%for.body> U: [2,0) S: [2,0) Exits: (zext i32 %n to > i64) LoopDispositions: { %for.body: Computable } > Determining loop execution counts for: @func > Loop %for.body: backedge-taken count is (-2 + (zext i32 %n to i64))<nsw> > Loop %for.body: max backedge-taken count is -2 > Loop %for.body: Predicated backedge-taken count is (-2 + (zext i32 %n to > i64))<nsw> > Predicates: > Loop %for.body: Trip multiple is 1 Now, I was surprised by the max b...

...source.html) we have the method InnerLoopVectorizer::getOrCreateTripCount() that seems to do a better job at computing the trip count, even if the implementation differences are not big. The differences are subtle - first of all the method getOrCreateTripCount() doesn't call hasLoopInvariantBackedgeTakenCount(). Please don't hesitate to comment why InnerLoopVectorizer::getOrCreateTripCount() works better. I will try to come back myself with more info. Thank you, Alex PS: Could you please recommend me one important paper for Scalar evolutions?

...e 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 %8: Unpredictable predicated backedge-taken count. which means it is unable to compute iteration count. However, when .bc file is generated using LLVM 4.0 i am getting following; Determining loop execution counts for: @main 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 lo...

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

...ders as well. > There isn't really any reason to collapse 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...

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 vice-versa. I believe this is...

...%for.body: Computable } >> %inc = add nuw nsw i64 %x.06, 1 >> --> {2,+,1}<nuw><%for.body> U: [2,0) S: [2,0) Exits: (zext i32 %n to >> i64) LoopDispositions: { %for.body: Computable } >> Determining loop execution counts for: @func >> Loop %for.body: backedge-taken count is (-2 + (zext i32 %n to i64))<nsw> >> Loop %for.body: max backedge-taken count is -2 >> Loop %for.body: Predicated backedge-taken count is (-2 + (zext i32 %n to >> i64))<nsw> >> Predicates: >> Loop %for.body: Trip multiple is 1 > > >...

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

...> > > 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 %8: Unpredictable predicated backedge-taken count. > > which means it is unable to compute iteration count. > > > > However, when .bc file is generated using LLVM 4.0 i am getting > following...

...ually programmers do not write non-nature loops), it doesn't really need to evolute some conditional-variables. but, LLVM uses SCEV for otherall loop-analysis, typically Loop Unroll, etc. That really does need to anaylze conditional-expressions, lets see following C/C++ code. void UnpredictableBackedgeTakenCountFunc1() { for(unsigned int i = 0; i != 10; ++i) { // Exception of variable i... if(i == 4) ++i; // when the variable i is 4, we increase it. so its 5. if(i == 7) ++i; // when the variable i is 7, we increase it. so its 8. // do something here.... }...

Thank you, Nick. Yes, I have add getAnalysisUsage. As I know, some CFG is irreducible. At this time, 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....

Hi Pankaj, Chawla, Pankaj via llvm-dev wrote: > 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...

...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/listi...

...ll, > > In the attached test case there, is an unnested loop with 2 > iterations. The loop latch block is terminated by an unconditional > branch, so simplifycfg folds the almost empty latch block into its > *successor* which is the loop header. This results in an additional > backedge in the CFG, so when LoopRotate pass is called it > canonicalizes the loop into a nested loop. However, now the loop trip > count is unpredictable as the BackedgeTakenCount for the outer loop is > not loop invariant. As a result the loop cannot be unrolled. Is this > the intended can...

Hi, Is it fair to say that we require loops 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 doe...