Most of my programs contain loops that the LoopDeletion pass is unable to remove. It appears that the following code in LoopDeletion.cpp:152 is the culprit:
ScalarEvolution& SE = getAnalysis<ScalarEvolution>();
const SCEV *S = SE.getMaxBackedgeTakenCount(L);
if (isa<SCEVCouldNotCompute>(S))
return Changed;
So, LoopDeletion thinks my loops might be infinite so it does not delete them - even if they do not write to any of the function return values. Is there a way to flag a loop as non-infinite? Or will I need to create my own modified loop deletion pass that can eliminate potentially infinite loops. Is it correct just to remove the above code to allow deletion of infinite loops?
Most of my programs contain loops that the LoopDeletion pass is unable
to remove. It appears that the following code in LoopDeletion.cpp:152
is the culprit:
ScalarEvolution& SE = getAnalysis<ScalarEvolution>();
const SCEV *S = SE.getMaxBackedgeTakenCount(L);
if (isa<SCEVCouldNotCompute>(S))
return Changed;
So, LoopDeletion thinks my loops might be infinite so it does not delete
them - even if they do not write to any of the function return values.
Is there a way to flag a loop as non-infinite? Or will I need to create
my own modified loop deletion pass that can eliminate potentially
infinite loops. Is it correct just to remove the above code to allow
deletion of infinite loops?
I think what you actually want is the ADCE pass (opt -adce). The reason we turned ADCE off by default is that it kept deleting infinite loops, and the LoopDeletion pass was written as a safe replacement.
This looks sort of like what I'm looking for. The only problem is that ADCE is treating all terminator instructions as live:
// Collect the set of "root" instructions that are known live.
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
if (isa<TerminatorInst>(I.getInstructionIterator()) ||
isa<DbgInfoIntrinsic>(I.getInstructionIterator()) ||
I->mayHaveSideEffects()) {
alive.insert(I.getInstructionIterator());
worklist.push_back(I.getInstructionIterator());
}
Is this correct? I would have thought that branch instructions should not be initially live.
FYI, removing the ScalarEvolution conditional in the LoopDeletion code (and copying the algorithm to my own loop deletion pass) seems to correctly handle the elimination of infinite loops. However I'd still like to find a way to do this with standard passes if possible.
That's a good question. I think the reason that ScalarEvolution doesn't know the loop is finite is that the loop conditional depends on values that are only known at runtime, since I'm using external unbound functions as input to the loop's conditional branch.
So given that eliminating infinite loops is incorrect, I guess my question now would be what is the best way to let LLVM know that my loop is finite. In this case, I think I have more information than LLVM - the functions that evaluate at runtime to determine the loop iteration count will eventually cause the loop to terminate, but I don't see any way to indicate to the optimizer that this is the case.
I'm thinking a good way to support this feature would be to add a new function attribute "AlwaysReturn" that would indicate that a function does not contain any infinite loops, so that the LoopDeletion pass and others could treat it accordingly. What do you think?
What's the best way for me to submit changes back to the LLVM repository?
Most of my programs contain loops that the LoopDeletion pass is unable
to remove. It appears that the following code in LoopDeletion.cpp:152
is the culprit:
ScalarEvolution& SE = getAnalysis<ScalarEvolution>();
const SCEV *S = SE.getMaxBackedgeTakenCount(L);
if (isa<SCEVCouldNotCompute>(S))
return Changed;
So, LoopDeletion thinks my loops might be infinite so it does not delete
them - even if they do not write to any of the function return values.
Is there a way to flag a loop as non-infinite? Or will I need to create
my own modified loop deletion pass that can eliminate potentially
infinite loops. Is it correct just to remove the above code to allow
deletion of infinite loops?
No. Removing an infinite loop changes the semantics of the source program.
The question you should be asking is: why can't ScalarEvolution determine that your loops are finite?
--Owen
That's a good question. I think the reason that ScalarEvolution doesn't
know the loop is finite is that the loop conditional depends on values
that are only known at runtime, since I'm using external unbound
functions as input to the loop's conditional branch.
So given that eliminating infinite loops is incorrect, I guess my
question now would be what is the best way to let LLVM know that my loop
is finite. In this case, I think I have more information than LLVM -
the functions that evaluate at runtime to determine the loop iteration
count will eventually cause the loop to terminate, but I don't see any
way to indicate to the optimizer that this is the case.
Andrew
I'm thinking a good way to support this feature would be to add a new
function attribute "AlwaysReturn" that would indicate that a function
does not contain any infinite loops, so that the LoopDeletion pass and
others could treat it accordingly. What do you think?
but it turns out that making it efficient at compile time and make the optimizers make use of it is very tricky. In short, we want to be able to automatically deduce that a function is halting (as well as permitting labelling by the frontend which is easy) and that deduction requires a FunctionPass but the user of the information is a CallGraphSCCPass and you can't have CGSCC passes depending on function passes. So, it's blocked on changes to the pass manager to make this possible.
What's the best way for me to submit changes back to the LLVM repository?
I'm thinking a good way to support this feature would be to add a new
function attribute "AlwaysReturn" that would indicate that a function
does not contain any infinite loops, so that the LoopDeletion pass and
others could treat it accordingly. What do you think?
That's probably the best way to really fix this, yes. I'd go for a
different name though, since 'AlwaysReturn' implies the function
doesn't throw any exceptions, which is a separate issue already
addressed by 'nounwind'.
You'll also want some way to set the attribute. Ideally, some pass
would automatically set it on appropriate functions. For some of the
other attributes -functionattrs does this. It'd probably be a decent
place to set the attribute for simple non-looping functions, but
getting the best results probably requires something like
ScalarEvolution analysis so I'm not sure if this would be appropriate
there.
Eventually llvm-gcc/dragonegg/clang should also have support for an
explicit attribute to set this, but first it should work :).
What's the best way for me to submit changes back to the LLVM repository?
Assuming the question means you don't have commit access, just send
one or more patches to llvm-commits@cs.uiuc.edu.
That looks good. I guess my 2 cents are then that it would still be useful to have this Halting attribute even if it can't be automatically deduced, since often the front end will know whether the function should be treated as halting and can label it accordingly. Function attributes are not strict, correct? So you could have functions that halt but without the halting attribute, and still rely on correct optimization behavior.
FWIW, this is currently a discussion in the C++ and C committees, and my understanding is that this has changed (or is changing soon) in the C'1x draft. Assuming it happens, it will make it valid to assume that loops always terminate unless they are written with a condition that is an integer constant expression that folds to 1.
In addition to being able to delete noop loops that traverse over pointer-based data structures, this will also solve the:
for (unsigned i = 0; i <= N; ++i)
class of problems. I'm obviously strongly in favor of this, and I also think we should apply it to all C languages. I don't see any reason for people to write infinite loops with non-trivial conditions.
FYI, removing the ScalarEvolution conditional in the LoopDeletion code
(and copying the algorithm to my own loop deletion pass) seems to
correctly handle the elimination of infinite loops. However I'd still
like to find a way to do this with standard passes if possible.
FWIW, this is currently a discussion in the C++ and C committees, and my understanding is that this has changed (or is changing soon) in the C'1x draft. Assuming it happens, it will make it valid to assume that loops always terminate unless they are written with a condition that is an integer constant expression that folds to 1.
the C++/C standards are not relevant to other languages, such as Ada.
In addition to being able to delete noop loops that traverse over pointer-based data structures, this will also solve the:
for (unsigned i = 0; i<= N; ++i)
class of problems.
Also not relevant to Ada!
I'm obviously strongly in favor of this, and I also think we should apply it to all C languages. I don't see any reason for people to write infinite loops with non-trivial conditions.
Do you have a suggestion for how best to enable this optimization for some
languages and disable it for others?
Do you have a suggestion for how best to enable this optimization for some
languages and disable it for others?
Function attribute or metadata to let the optimizer know that all
loops in the given function are finite? That should allow mixing IL
files from different languages.
Do you have a suggestion for how best to enable this optimization for some
languages and disable it for others?
Function attribute or metadata to let the optimizer know that all
loops in the given function are finite? That should allow mixing IL
files from different languages.
a function attribute would be suboptimal if you inline C++ code into an
Ada function or vice versa, though it could be made to be conservatively
correct.
a function attribute would be suboptimal if you inline C++ code into an
Ada function or vice versa, though it could be made to be conservatively
correct.
It would be ok for C being inlined into ADA since ADA is the more
restrictive one. If we inline any ADA function with loops into a C++
one we would have to drop the attribute from the caller.
To do better we would have to mark the loops. That looks a bit harder
to track
In addition to being able to delete noop loops that traverse over pointer-based data structures, this will also solve the:
for (unsigned i = 0; i<= N; ++i)
class of problems.
Also not relevant to Ada!
Ada? What's that?
Do you have a suggestion for how best to enable this optimization for some
languages and disable it for others?
Sure, there are two ways to go:
1. Assume that loops are never infinite and add IR support to say that a loop *is*.
2. Assume that loops are possibly infinite and add IR support to say that a loop *isn't*.
I'm just saying I'm in favor of #1. This could take the form of an intrinsic that gets called in loop headers or something.
