search for: tailrecursionelimin

Hi, I was looking into the implementation of TailRecursionElimination, and noticed that we have the constrain that if any call uses a local, even though it doesn't capture the local, it would still prohibit TCE. This contain seems unnecessary and overly limiting? Relevant code is here: https://github.com/llvm/llvm-project/blob/cbe77ca9bd05393b1df1abf016b01f4...

On 2020-05-08 1:34 p.m., Xun Li wrote: > Hi, > > I was looking into the implementation of TailRecursionElimination, and > noticed that we have the constrain that if any call uses a local, even > though it doesn't capture the local, it would still prohibit TCE. This > contain seems unnecessary and overly limiting? I think it's a necessary limitation. The idea is that something marked '...

...a look at how > to improve this. > > Nick, > Thanks. I agree that's the proper constrain to mark a call as > tailcall, however not being able to mark a call as tailcall shouldn't > completely kill TCE. (i.e. AllCallsAreTailCalls seems overly > limiting). I get it now. TailRecursionElimination.cpp does two optimizations, marking of tail and converting recursion to loops. I thought you were proposing a change to the marking of tail. Thanks for the example! "PR962" refers to "problem report 962" or https://llvm.org/PR962 . "rdar" is Apple's "...

...e(L->getLoopLatch(), Exit, this); Would it make sense to move the ProfileInfo updating code into SplitEdge? That way all users of SplitEdge would automatically do the right thing. Actually, SplitEdge just delegates to either SplitCriticalEdge or SplitBlock, so those two should do the work. In TailRecursionElimination.cpp, there's logic which uses a "10-fold increase" heuristic. It would be nice if that code were factored out into a utility routine so that the profiling heuristics are more centralized. > - bool Folded = ConstantFoldTerminator(I->getParent()); > + bool...

Hi all, this (altough a big patch) is actually pretty straight forward: It (tries) to preserve ProfileInfo in all -std-compile-opts passes and all X86-Backend passes. There is still some passes that have corner cases where the ProfileInfo is not correct after the pass. Some passes are still missing... How shall I proceed with this? Andi -------------- next part -------------- A non-text

...t; lib/AsmParser/LLParser.cpp > lib/AsmParser/LLToken.h > lib/Bitcode/Reader/BitcodeReader.cpp > lib/Bitcode/Writer/BitcodeWriter.cpp > lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp > lib/IR/Attributes.cpp > lib/IR/Verifier.cpp > lib/Transforms/Scalar/TailRecursionElimination.cpp > test/Bindings/llvm-c/Inputs/invalid.ll.bc > test/Bindings/llvm-c/invalid-bitcode.test > test/Bitcode/attributes.ll > test/Bitcode/invalid.ll > test/Bitcode/invalid.ll.bc > test/CodeGen/X86/attr-notail.ll > test/Transforms/TailCallElim/notail.ll &...

...Parser/LLToken.h >> lib/Bitcode/Reader/BitcodeReader.cpp >> lib/Bitcode/Writer/BitcodeWriter.cpp >> lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp >> lib/IR/Attributes.cpp >> lib/IR/Verifier.cpp >> lib/Transforms/Scalar/TailRecursionElimination.cpp >> test/Bindings/llvm-c/Inputs/invalid.ll.bc >> test/Bindings/llvm-c/invalid-bitcode.test >> test/Bitcode/attributes.ll >> test/Bitcode/invalid.ll >> test/Bitcode/invalid.ll.bc >> test/CodeGen/X86/attr-notail.ll...

...wo should do the work. Yes, this is implemented already, but I have not removed the call to PI->SplitEdge(), in generall this patch is perliminary and my big question was how to deal with it commiting-wise, I still have to figure out some technical details. But thanks for the hint! > In TailRecursionElimination.cpp, there's logic which uses a > "10-fold increase" heuristic. It would be nice if that code were > factored out into a utility routine so that the profiling > heuristics are more centralized. Agreed. Its hard to find all points that use such heuristics, since I co...

...sweb/cvsweb.cgi/llvm/lib/Transforms/Scalar/LICM.cpp?rev=1.59&content-type=text/x-cvsweb-markup http://llvm.cs.uiuc.edu/cvsweb/cvsweb.cgi/llvm/lib/Transforms/Scalar/Reassociate.cpp?rev=1.30&content-type=text/x-cvsweb-markup http://llvm.cs.uiuc.edu/cvsweb/cvsweb.cgi/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp?rev=1.13&content-type=text/x-cvsweb-markup -Chris -- http://llvm.cs.uiuc.edu/ http://www.nondot.org/~sabre/Projects/

...code/Reader/BitcodeReader.cpp >>> lib/Bitcode/Writer/BitcodeWriter.cpp >>> lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp >>> lib/IR/Attributes.cpp >>> lib/IR/Verifier.cpp >>> lib/Transforms/Scalar/TailRecursionElimination.cpp >>> test/Bindings/llvm-c/Inputs/invalid.ll.bc >>> test/Bindings/llvm-c/invalid-bitcode.test >>> test/Bitcode/attributes.ll >>> test/Bitcode/invalid.ll >>> test/Bitcode/invalid.ll.bc >>...

Hi devels, there are two issues concerning invoking optimizations: 1. this document: http://llvm.cs.uiuc.edu/docs/GettingStarted.html is very nice, it would be good though to add in a section An Example Using the LLVM Tool Chain examples on optimization step. 2. If i am not wrong there is no tool, which integrates all steps: llvmgcc->opt->llc into something like llcc (and

...t;> lib/Bitcode/Writer/BitcodeWriter.cpp >>>> lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp >>>> lib/IR/Attributes.cpp >>>> lib/IR/Verifier.cpp >>>> lib/Transforms/Scalar/TailRecursionElimination.cpp >>>> test/Bindings/llvm-c/Inputs/invalid.ll.bc >>>> test/Bindings/llvm-c/invalid-bitcode.test >>>> test/Bitcode/attributes.ll >>>> test/Bitcode/invalid.ll >>>>...

...; > > gets converted to: > > > > > > while (1) { > > if (i == 0) break; > > a[i] = i+1; > > i = i-1; > > } > > > > > > Now, the above is the simplest case and is pure tail recursion. We > > can eliminate this currently with the TailRecursionElimination pass. > > The more complex case is where we have non-tail recusion and live > > variables. > > > > > > void ex2(i) { > > if (i == 0) return; > > j = a[i]; > > ex2(i-1) > > b[j] = i; > > } > > > > > > This requires a...

...xample: void ex1(i) { if (i == 0) return; a[i] = i+1; ex1(i-1); } gets converted to: while (1) { if (i == 0) break; a[i] = i+1; i = i-1; } Now, the above is the simplest case and is pure tail recursion. We can eliminate this currently with the TailRecursionElimination pass. The more complex case is where we have non-tail recusion and live variables. void ex2(i) { if (i == 0) return; j = a[i]; ex2(i-1) b[j] = i; } This requires a stack being modelled and could be converted to: cnt = 0; while (1) { if (i == 0)...

...e/Writer/BitcodeWriter.cpp >>>>> lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp >>>>> lib/IR/Attributes.cpp >>>>> lib/IR/Verifier.cpp >>>>> lib/Transforms/Scalar/TailRecursionElimination.cpp >>>>> test/Bindings/llvm-c/Inputs/invalid.ll.bc >>>>> test/Bindings/llvm-c/invalid-bitcode.test >>>>> test/Bitcode/attributes.ll >>>>> test/Bitcode/invali...

...lib/Transforms/Instrumentation/ProfilingUtils.cpp U lib/Transforms/Scalar/LoopUnswitch.cpp U lib/Transforms/Scalar/IndVarSimplify.cpp U lib/Transforms/Scalar/GVNPRE.cpp U lib/Transforms/Scalar/InstructionCombining.cpp U lib/Transforms/Scalar/SimplifyCFG.cpp U lib/Transforms/Scalar/TailRecursionElimination.cpp U lib/Transforms/Scalar/LoopIndexSplit.cpp U lib/Transforms/Scalar/LoopStrengthReduce.cpp U lib/Transforms/Scalar/GCSE.cpp U lib/Transforms/Scalar/ScalarReplAggregates.cpp U lib/Transforms/Scalar/SCCP.cpp U lib/Transforms/Scalar/LoopRotation.cpp U lib/Transforms/Scalar...

...; > > gets converted to: > > > > > > while (1) { > > if (i == 0) break; > > a[i] = i+1; > > i = i-1; > > } > > > > > > Now, the above is the simplest case and is pure tail recursion. We > > can eliminate this currently with the TailRecursionElimination pass. > > The more complex case is where we have non-tail recusion and live > > variables. > > > > > > void ex2(i) { > > if (i == 0) return; > > j = a[i]; > > ex2(i-1) > > b[j] = i; > > } > > > > > > This requires a...

...ativePath="..\..\lib\Transforms\Scalar\SymbolStripping.cpp"> > </File> > <File > RelativePath="..\..\lib\Transforms\Scalar\TailDuplication.cpp"> > </File> > <File > RelativePath="..\..\lib\Transforms\Scalar\TailRecursionElimination.cpp"> > </File> > </Filter> > <Filter > Name="Parallel" > Filter=""> > </Filter> > <Filter > Name="Utils" > Filter=""> > <File > RelativePa...

...d llvm[3]: Compiling DeadArgumentElimination.cpp for Release+Asserts build llvm[2]: Compiling DeadMachineInstructionElim.cpp for Release+Asserts build llvm[2]: Compiling DwarfEHPrepare.cpp for Release+Asserts build llvm[3]: Compiling RuntimeDyldMachO.cpp for Release+Asserts build llvm[3]: Compiling TailRecursionElimination.cpp for Release+Asserts build llvm[3]: Compiling ElimAvailExtern.cpp for Release+Asserts build llvm[2]: Compiling EarlyIfConversion.cpp for Release+Asserts build llvm[3]: Compiling ExtractGV.cpp for Release+Asserts build llvm[3]: Building Release+Asserts Archive Library libLLVMRuntimeDyld.a ma...