Index: include/llvm/Analysis/LazyValueInfo.h =================================================================== --- include/llvm/Analysis/LazyValueInfo.h +++ include/llvm/Analysis/LazyValueInfo.h @@ -64,30 +64,74 @@ // Public query interface. + /// Understanding Context Instructions, Assumes, and Guards + /// -------------------------------------------------------- + /// The LVI query predicates accept a CFG element (Block, Edge) and an + /// optional context instruction. Without a context specified, the return + /// value simply describes facts known to be true at the specified CFG + /// element. That is, a value might be known constant within a block or on a + /// given edge. Without a context, the facts returned a true anywhere within + /// the specified block. + /// However, there are control flow facts which can become true part way + /// through a block. The simplest example is we may encounter a function + /// which throws if it's argument is non-zero. For an context before that + /// function call, we have to assume the value might be non-zero, but after + /// the function call, we know the value is zero. In general, we don't + /// exploit such interprocedural reasoning today, but in principle, we + /// could. Today, we do have a couple of argument attributes (e.g. nonnull) + /// which can summarize interprocedural facts. We also have a couple of + /// special intrinsics with related semantics: assume, and guards. + /// The optional context instruction provides a means to query these + /// facts. We also allow context instructions which are not within the block + /// being queried. This ends up being very useful for a number of transforms + /// (e.g. jump-threading) as it allows questions of the form "what is the + /// value of Y in BB if I reach CxtI?". As such, the return value of a call + /// which names both a CFG element and a context instruction describes a + /// property of the specified Value which is true at the given CFG element if + /// execution also reaches the context instruction. + /// TODO: We could be much more aggressive about exploiting the last point + /// if we thought this was profitable for transforms. + /// -------------------------------------------------------- + /// Determine whether the specified value comparison with a constant is known - /// to be true or false on the specified CFG edge. - /// Pred is a CmpInst predicate. + /// to be true or false on the specified CFG edge. Pred is a CmpInst + /// predicate. See note above about semantics of context instructions. Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI = nullptr); /// Determine whether the specified value comparison with a constant is known - /// to be true or false at the specified instruction - /// (from an assume intrinsic). Pred is a CmpInst predicate. + /// to be true or false at the specified instruction. Pred is a CmpInst + /// predicate. Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI); - /// Determine whether the specified value is known to be a - /// constant at the end of the specified block. Return null if not. + /// Determine whether the specified value is known to be a constant within + /// the specified block. Return null if not. See note above about semantics + /// of context instructions. Constant *getConstant(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr); - /// Return the ConstantRange constraint that is known to hold for the - /// specified value at the end of the specified block. This may only be called - /// on integer-typed Values. - ConstantRange getConstantRange(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr); + /// Determine whether the specified value is known to be a constant at the + /// the specified context instruction. Return null if not. + Constant *getConstant(Value *V, Instruction *CxtI) { + return getConstant(V, CxtI->getParent(), CxtI); + } - /// Determine whether the specified value is known to be a - /// constant on the specified edge. Return null if not. + /// Return the ConstantRange constraint that is known to hold for the + /// specified value within the specified block . This may only be called on + /// integer-typed Values. See note above about semantics of context + /// instructions. + ConstantRange getConstantRange(Value *V, BasicBlock *BB, + Instruction *CxtI = nullptr); + + /// Returns the ConstantRange constraint known to be true for 'V' at the + /// specified context. + ConstantRange getConstantRange(Value *V, Instruction *CxtI); + + /// Determine whether the specified value is known to be a constant on the + /// specified edge, given execution reaches both Edge and (optionally) CxtI. + /// Return null if not. See note above about semantics of context + /// instructions. Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI = nullptr); Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -383,8 +383,12 @@ } // end anonymous namespace namespace { - /// This is the cache kept by LazyValueInfo which - /// maintains information about queries across the clients' queries. + /// This is the cache kept by LazyValueInfo which maintains information + /// about queries across the clients' queries. Note that facts stored in + /// this structure are true for a given Value anywhere within the given + /// block. This means that an unconditional assume within a block can + /// influence the value cached, but that an assume after a potentially + /// throwing call can not. class LazyValueInfoCache { /// This is all of the cached block information for exactly one Value*. /// The entries are sorted by the BasicBlock* of the @@ -955,7 +959,15 @@ bool isTrueDest = true); // If we can determine a constraint on the value given conditions assumed by -// the program, intersect those constraints with BBLV +// the program, intersect those constraints with BBLV. +// Note: This function is used in two related but distinct purposes. Within +// the solve infrastructure, it is used to find assumed facts which are true +// about intermediate values at their point of use. This is result is safe to +// cache since the def-use graph/cfg is fixed for all queuries. For an +// individual query, we also intersect facts about the specific context +// instruction provided with the cached result. This produces a result which +// is valid for a given query, but can't be cached because it is context +// specific. void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange( Value *Val, LVILatticeVal &BBLV, Instruction *BBI) { BBI = BBI ? BBI : dyn_cast(Val); @@ -978,6 +990,7 @@ if (!GuardDecl || GuardDecl->use_empty()) return; + // TODO: handle guards in dominating blocks as well for (BasicBlock::iterator I = BBI->getIterator(), E = BBI->getParent()->begin(); I != E; I--) { Value *Cond = nullptr; @@ -1623,7 +1636,7 @@ const DataLayout &DL = BB->getModule()->getDataLayout(); LVILatticeVal Result = - getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); + getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB); if (Result.isConstant()) return Result.getConstant(); @@ -1641,7 +1654,8 @@ unsigned Width = V->getType()->getIntegerBitWidth(); const DataLayout &DL = BB->getModule()->getDataLayout(); LVILatticeVal Result = - getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); + getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); + if (Result.isUndefined()) return ConstantRange(Width, /*isFullSet=*/false); if (Result.isConstantRange()) @@ -1653,6 +1667,10 @@ return ConstantRange(Width, /*isFullSet=*/true); } +ConstantRange LazyValueInfo::getConstantRange(Value *V, Instruction *CxtI) { + return getConstantRange(V, CxtI->getParent(), CxtI); +} + /// Determine whether the specified value is known to be a /// constant on the specified edge. Return null if not. Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, Index: lib/Transforms/Scalar/CorrelatedValuePropagation.cpp =================================================================== --- lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -75,7 +75,7 @@ if (S->getType()->isVectorTy()) return false; if (isa(S->getOperand(0))) return false; - Constant *C = LVI->getConstant(S->getOperand(0), S->getParent(), S); + Constant *C = LVI->getConstant(S->getOperand(0), S); if (!C) return false; ConstantInt *CI = dyn_cast(C); @@ -171,7 +171,7 @@ if (isa(Pointer)) return false; - Constant *C = LVI->getConstant(Pointer, I->getParent(), I); + Constant *C = LVI->getConstant(Pointer, I); if (!C) return false; ++NumMemAccess; @@ -398,12 +398,10 @@ if (NSW && NUW) return false; - BasicBlock *BB = AddOp->getParent(); - Value *LHS = AddOp->getOperand(0); Value *RHS = AddOp->getOperand(1); - ConstantRange LRange = LVI->getConstantRange(LHS, BB, AddOp); + ConstantRange LRange = LVI->getConstantRange(LHS, AddOp); // Initialize RRange only if we need it. If we know that guaranteed no wrap // range for the given LHS range is empty don't spend time calculating the @@ -411,7 +409,7 @@ Optional RRange; auto LazyRRange = [&] () { if (!RRange) - RRange = LVI->getConstantRange(RHS, BB, AddOp); + RRange = LVI->getConstantRange(RHS, AddOp); return RRange.getValue(); }; @@ -441,7 +439,7 @@ } static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) { - if (Constant *C = LVI->getConstant(V, At->getParent(), At)) + if (Constant *C = LVI->getConstant(V, At)) return C; // TODO: The following really should be sunk inside LVI's core algorithm, or