Hello again,
In discussing my proposed patches for supporting alignment assumptions (for
supporting __builtin_assume_aligned; see
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20121126/157659.html),
Chandler and I have started discussing an infrastructure for declaring
invariants in the IR for use by the optimizer.
The basic idea is to introduce a new intrinsic:
void @llvm.invariant(i1 %cond)
which declares that the %cond is defined to be true.
First, we need to make sure that instructions that contribute only to forming
the invariant conditions don't interfere with optimization and code
generation. We'll call these instructions 'ephemeral' (this was
Chandler's idea). An analysis pass can walk instructions starting from the
@llvm.invariant calls and record those instructions as ephemeral those used only
by other ephemeral instructions (the invariant call is also ephemeral). This
analysis pass will be used by:
- The inliner (with cost metrics) to treat all ephemeral instructions as free
- The vectorizers (with VTTI); bb-vectorize would ignore ephemeral instructions
- The selection-DAG builder so that code is not generated for ephemeral
instructions
- DCE so that ephemeral instructions that don't indirectly depend on live
instructions can be removed (and any blocks being kept alive by those
instructions can also be removed)
Otherwise, these instructions will be optimized and normalized just like all
other instructions. This will give ScalarEvolution, ValueTracking, etc. the
benefit of analyzing these invariants in normalized form.
The next step is introducing some way to use these invariants. I think that a
natural place is to integrate these is with ScalarEvolution. We'd want
functions like getUnsignedRange, isKnownNegative, isKnownPredicate, etc. to
automatically take advantage of declared invariants. Internally, SE uses a
function:
/// isImpliedCondOperands - Test whether the condition described by Pred,
/// LHS, and RHS is true whenever the condition described by Pred, FoundLHS,
/// and FoundRHS is true.
bool isImpliedCondOperands(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS,
const SCEV *FoundLHS, const SCEV *FoundRHS);
and this seems to be exactly the right interface for incorporating information
from the invariant conditions into the predicate-evaluation queries.
Unfortunately, we may quickly run into a limitation of SE: it has no native
support for boolean/bitwise operations. For one thing, it seems like what
we'd really like to do is "and" together all relevant invariant
conditions, but I don't currently see a way to do that. SE does currently do
some limited analysis of bitwise-operation operands, but only by using
ValueTracking on SCEVUnknown operands. To really make this work well (especially
if we'd like to use this infrastructure to say something about pointer
alignments, for example), we may need to give SE some of the same ability to
interpret bitwise operations that ValueTracking has (hopefully by refactoring).
I'd also like to point out that these SE enhancements (or whatever method we
choose), can also be used with the predicates that guard conditional branches.
Does this sound reasonable? How do you think these invariants could/should be
used?
Thanks again,
Hal
--
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory
