[LLVMdev] [RFC] Intrinsic for declaring invariants

[Hal Finkel]

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