lib/Transforms/Scalar/CorrelatedValuePropagation.cpp - platform/external/spirv-llvm - Git at Google

 //===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Correlated Value Propagation pass.
 //
 //===----------------------------------------------------------------------===//

 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;

 #define DEBUG_TYPE "correlated-value-propagation"

 STATISTIC(NumPhis,      "Number of phis propagated");
 STATISTIC(NumSelects,   "Number of selects propagated");
 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
 STATISTIC(NumCmps,      "Number of comparisons propagated");
 STATISTIC(NumReturns,   "Number of return values propagated");
 STATISTIC(NumDeadCases, "Number of switch cases removed");

 namespace {
   class CorrelatedValuePropagation : public FunctionPass {
     LazyValueInfo *LVI;

     bool processSelect(SelectInst *SI);
     bool processPHI(PHINode *P);
     bool processMemAccess(Instruction *I);
     bool processCmp(CmpInst *C);
     bool processSwitch(SwitchInst *SI);
     bool processCallSite(CallSite CS);

     /// Return a constant value for V usable at At and everything it
     /// dominates.  If no such Constant can be found, return nullptr.
     Constant *getConstantAt(Value *V, Instruction *At);

   public:
     static char ID;
     CorrelatedValuePropagation(): FunctionPass(ID) {
      initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
     }

     bool runOnFunction(Function &F) override;

     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<LazyValueInfo>();
       AU.addPreserved<GlobalsAAWrapperPass>();
     }
   };
 }

 char CorrelatedValuePropagation::ID = 0;
 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
                 "Value Propagation", false, false)
 INITIALIZE_PASS_DEPENDENCY(LazyValueInfo)
 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
                 "Value Propagation", false, false)

 // Public interface to the Value Propagation pass
 Pass *llvm::createCorrelatedValuePropagationPass() {
   return new CorrelatedValuePropagation();
 }

 bool CorrelatedValuePropagation::processSelect(SelectInst *S) {
   if (S->getType()->isVectorTy()) return false;
   if (isa<Constant>(S->getOperand(0))) return false;

   Constant *C = LVI->getConstant(S->getOperand(0), S->getParent(), S);
   if (!C) return false;

   ConstantInt *CI = dyn_cast<ConstantInt>(C);
   if (!CI) return false;

   Value *ReplaceWith = S->getOperand(1);
   Value *Other = S->getOperand(2);
   if (!CI->isOne()) std::swap(ReplaceWith, Other);
   if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType());

   S->replaceAllUsesWith(ReplaceWith);
   S->eraseFromParent();

   ++NumSelects;

   return true;
 }

 bool CorrelatedValuePropagation::processPHI(PHINode *P) {
   bool Changed = false;

   BasicBlock *BB = P->getParent();
   for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
     Value *Incoming = P->getIncomingValue(i);
     if (isa<Constant>(Incoming)) continue;

     Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);

     // Look if the incoming value is a select with a scalar condition for which
     // LVI can tells us the value. In that case replace the incoming value with
     // the appropriate value of the select. This often allows us to remove the
     // select later.
     if (!V) {
       SelectInst *SI = dyn_cast<SelectInst>(Incoming);
       if (!SI) continue;

       Value *Condition = SI->getCondition();
       if (!Condition->getType()->isVectorTy()) {
         if (Constant *C = LVI->getConstantOnEdge(
                 Condition, P->getIncomingBlock(i), BB, P)) {
           if (C->isOneValue()) {
             V = SI->getTrueValue();
           } else if (C->isZeroValue()) {
             V = SI->getFalseValue();
           }
           // Once LVI learns to handle vector types, we could also add support
           // for vector type constants that are not all zeroes or all ones.
         }
       }

       // Look if the select has a constant but LVI tells us that the incoming
       // value can never be that constant. In that case replace the incoming
       // value with the other value of the select. This often allows us to
       // remove the select later.
       if (!V) {
         Constant *C = dyn_cast<Constant>(SI->getFalseValue());
         if (!C) continue;

         if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
               P->getIncomingBlock(i), BB, P) !=
             LazyValueInfo::False)
           continue;
         V = SI->getTrueValue();
       }

       DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
     }

     P->setIncomingValue(i, V);
     Changed = true;
   }

   // FIXME: Provide TLI, DT, AT to SimplifyInstruction.
   const DataLayout &DL = BB->getModule()->getDataLayout();
   if (Value *V = SimplifyInstruction(P, DL)) {
     P->replaceAllUsesWith(V);
     P->eraseFromParent();
     Changed = true;
   }

   if (Changed)
     ++NumPhis;

   return Changed;
 }

 bool CorrelatedValuePropagation::processMemAccess(Instruction *I) {
   Value *Pointer = nullptr;
   if (LoadInst *L = dyn_cast<LoadInst>(I))
     Pointer = L->getPointerOperand();
   else
     Pointer = cast<StoreInst>(I)->getPointerOperand();

   if (isa<Constant>(Pointer)) return false;

   Constant *C = LVI->getConstant(Pointer, I->getParent(), I);
   if (!C) return false;

   ++NumMemAccess;
   I->replaceUsesOfWith(Pointer, C);
   return true;
 }

 /// processCmp - See if LazyValueInfo's ability to exploit edge conditions,
 /// or range information is sufficient to prove this comparison.  Even for
 /// local conditions, this can sometimes prove conditions instcombine can't by
 /// exploiting range information.
 bool CorrelatedValuePropagation::processCmp(CmpInst *C) {
   Value *Op0 = C->getOperand(0);
   Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
   if (!Op1) return false;

   // As a policy choice, we choose not to waste compile time on anything where
   // the comparison is testing local values.  While LVI can sometimes reason
   // about such cases, it's not its primary purpose.  We do make sure to do
   // the block local query for uses from terminator instructions, but that's
   // handled in the code for each terminator.
   auto *I = dyn_cast<Instruction>(Op0);
   if (I && I->getParent() == C->getParent())
     return false;

   LazyValueInfo::Tristate Result =
     LVI->getPredicateAt(C->getPredicate(), Op0, Op1, C);
   if (Result == LazyValueInfo::Unknown) return false;

   ++NumCmps;
   if (Result == LazyValueInfo::True)
     C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext()));
   else
     C->replaceAllUsesWith(ConstantInt::getFalse(C->getContext()));
   C->eraseFromParent();

   return true;
 }

 /// processSwitch - Simplify a switch instruction by removing cases which can
 /// never fire.  If the uselessness of a case could be determined locally then
 /// constant propagation would already have figured it out.  Instead, walk the
 /// predecessors and statically evaluate cases based on information available
 /// on that edge.  Cases that cannot fire no matter what the incoming edge can
 /// safely be removed.  If a case fires on every incoming edge then the entire
 /// switch can be removed and replaced with a branch to the case destination.
 bool CorrelatedValuePropagation::processSwitch(SwitchInst *SI) {
   Value *Cond = SI->getCondition();
   BasicBlock *BB = SI->getParent();

   // If the condition was defined in same block as the switch then LazyValueInfo
   // currently won't say anything useful about it, though in theory it could.
   if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
     return false;

   // If the switch is unreachable then trying to improve it is a waste of time.
   pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
   if (PB == PE) return false;

   // Analyse each switch case in turn.  This is done in reverse order so that
   // removing a case doesn't cause trouble for the iteration.
   bool Changed = false;
   for (SwitchInst::CaseIt CI = SI->case_end(), CE = SI->case_begin(); CI-- != CE;
        ) {
     ConstantInt *Case = CI.getCaseValue();

     // Check to see if the switch condition is equal to/not equal to the case
     // value on every incoming edge, equal/not equal being the same each time.
     LazyValueInfo::Tristate State = LazyValueInfo::Unknown;
     for (pred_iterator PI = PB; PI != PE; ++PI) {
       // Is the switch condition equal to the case value?
       LazyValueInfo::Tristate Value = LVI->getPredicateOnEdge(CmpInst::ICMP_EQ,
                                                               Cond, Case, *PI,
                                                               BB, SI);
       // Give up on this case if nothing is known.
       if (Value == LazyValueInfo::Unknown) {
         State = LazyValueInfo::Unknown;
         break;
       }

       // If this was the first edge to be visited, record that all other edges
       // need to give the same result.
       if (PI == PB) {
         State = Value;
         continue;
       }

       // If this case is known to fire for some edges and known not to fire for
       // others then there is nothing we can do - give up.
       if (Value != State) {
         State = LazyValueInfo::Unknown;
         break;
       }
     }

     if (State == LazyValueInfo::False) {
       // This case never fires - remove it.
       CI.getCaseSuccessor()->removePredecessor(BB);
       SI->removeCase(CI); // Does not invalidate the iterator.

       // The condition can be modified by removePredecessor's PHI simplification
       // logic.
       Cond = SI->getCondition();

       ++NumDeadCases;
       Changed = true;
     } else if (State == LazyValueInfo::True) {
       // This case always fires.  Arrange for the switch to be turned into an
       // unconditional branch by replacing the switch condition with the case
       // value.
       SI->setCondition(Case);
       NumDeadCases += SI->getNumCases();
       Changed = true;
       break;
     }
   }

   if (Changed)
     // If the switch has been simplified to the point where it can be replaced
     // by a branch then do so now.
     ConstantFoldTerminator(BB);

   return Changed;
 }

 /// processCallSite - Infer nonnull attributes for the arguments at the
 /// specified callsite.
 bool CorrelatedValuePropagation::processCallSite(CallSite CS) {
   SmallVector<unsigned, 4> Indices;
   unsigned ArgNo = 0;

   for (Value *V : CS.args()) {
     PointerType *Type = dyn_cast<PointerType>(V->getType());

     if (Type && !CS.paramHasAttr(ArgNo + 1, Attribute::NonNull) &&
         LVI->getPredicateAt(ICmpInst::ICMP_EQ, V,
                             ConstantPointerNull::get(Type),
                             CS.getInstruction()) == LazyValueInfo::False)
       Indices.push_back(ArgNo + 1);
     ArgNo++;
   }

   assert(ArgNo == CS.arg_size() && "sanity check");

   if (Indices.empty())
     return false;

   AttributeSet AS = CS.getAttributes();
   LLVMContext &Ctx = CS.getInstruction()->getContext();
   AS = AS.addAttribute(Ctx, Indices, Attribute::get(Ctx, Attribute::NonNull));
   CS.setAttributes(AS);

   return true;
 }

 Constant *CorrelatedValuePropagation::getConstantAt(Value *V, Instruction *At) {
   if (Constant *C = LVI->getConstant(V, At->getParent(), At))
     return C;

   // TODO: The following really should be sunk inside LVI's core algorithm, or
   // at least the outer shims around such.
   auto *C = dyn_cast<CmpInst>(V);
   if (!C) return nullptr;

   Value *Op0 = C->getOperand(0);
   Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
   if (!Op1) return nullptr;

   LazyValueInfo::Tristate Result =
     LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At);
   if (Result == LazyValueInfo::Unknown)
     return nullptr;

   return (Result == LazyValueInfo::True) ?
     ConstantInt::getTrue(C->getContext()) :
     ConstantInt::getFalse(C->getContext());
 }

 bool CorrelatedValuePropagation::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;

   LVI = &getAnalysis<LazyValueInfo>();

   bool FnChanged = false;

   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
     bool BBChanged = false;
     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
       Instruction *II = &*BI++;
       switch (II->getOpcode()) {
       case Instruction::Select:
         BBChanged |= processSelect(cast<SelectInst>(II));
         break;
       case Instruction::PHI:
         BBChanged |= processPHI(cast<PHINode>(II));
         break;
       case Instruction::ICmp:
       case Instruction::FCmp:
         BBChanged |= processCmp(cast<CmpInst>(II));
         break;
       case Instruction::Load:
       case Instruction::Store:
         BBChanged |= processMemAccess(II);
         break;
       case Instruction::Call:
       case Instruction::Invoke:
         BBChanged |= processCallSite(CallSite(II));
         break;
       }
     }

     Instruction *Term = FI->getTerminator();
     switch (Term->getOpcode()) {
     case Instruction::Switch:
       BBChanged |= processSwitch(cast<SwitchInst>(Term));
       break;
     case Instruction::Ret: {
       auto *RI = cast<ReturnInst>(Term);
       // Try to determine the return value if we can.  This is mainly here to
       // simplify the writing of unit tests, but also helps to enable IPO by
       // constant folding the return values of callees.
       auto *RetVal = RI->getReturnValue();
       if (!RetVal) break; // handle "ret void"
       if (isa<Constant>(RetVal)) break; // nothing to do
       if (auto *C = getConstantAt(RetVal, RI)) {
         ++NumReturns;
         RI->replaceUsesOfWith(RetVal, C);
         BBChanged = true;
       }
     }
     };

     FnChanged |= BBChanged;
   }

   return FnChanged;
 }
	//===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// This file implements the Correlated Value Propagation pass.
	//
	//===----------------------------------------------------------------------===//

	#include "llvm/Transforms/Scalar.h"
	#include "llvm/ADT/Statistic.h"
	#include "llvm/Analysis/GlobalsModRef.h"
	#include "llvm/Analysis/InstructionSimplify.h"
	#include "llvm/Analysis/LazyValueInfo.h"
	#include "llvm/IR/CFG.h"
	#include "llvm/IR/Constants.h"
	#include "llvm/IR/Function.h"
	#include "llvm/IR/Instructions.h"
	#include "llvm/IR/Module.h"
	#include "llvm/Pass.h"
	#include "llvm/Support/Debug.h"
	#include "llvm/Support/raw_ostream.h"
	#include "llvm/Transforms/Utils/Local.h"
	using namespace llvm;

	#define DEBUG_TYPE "correlated-value-propagation"

	STATISTIC(NumPhis, "Number of phis propagated");
	STATISTIC(NumSelects, "Number of selects propagated");
	STATISTIC(NumMemAccess, "Number of memory access targets propagated");
	STATISTIC(NumCmps, "Number of comparisons propagated");
	STATISTIC(NumReturns, "Number of return values propagated");
	STATISTIC(NumDeadCases, "Number of switch cases removed");

	namespace {
	class CorrelatedValuePropagation : public FunctionPass {
	LazyValueInfo *LVI;

	bool processSelect(SelectInst *SI);
	bool processPHI(PHINode *P);
	bool processMemAccess(Instruction *I);
	bool processCmp(CmpInst *C);
	bool processSwitch(SwitchInst *SI);
	bool processCallSite(CallSite CS);

	/// Return a constant value for V usable at At and everything it
	/// dominates. If no such Constant can be found, return nullptr.
	Constant getConstantAt(Value V, Instruction *At);

	public:
	static char ID;
	CorrelatedValuePropagation(): FunctionPass(ID) {
	initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
	}

	bool runOnFunction(Function &F) override;

	void getAnalysisUsage(AnalysisUsage &AU) const override {
	AU.addRequired<LazyValueInfo>();
	AU.addPreserved<GlobalsAAWrapperPass>();
	}
	};
	}

	char CorrelatedValuePropagation::ID = 0;
	INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
	"Value Propagation", false, false)
	INITIALIZE_PASS_DEPENDENCY(LazyValueInfo)
	INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
	"Value Propagation", false, false)

	// Public interface to the Value Propagation pass
	Pass *llvm::createCorrelatedValuePropagationPass() {
	return new CorrelatedValuePropagation();
	}

	bool CorrelatedValuePropagation::processSelect(SelectInst *S) {
	if (S->getType()->isVectorTy()) return false;
	if (isa<Constant>(S->getOperand(0))) return false;

	Constant *C = LVI->getConstant(S->getOperand(0), S->getParent(), S);
	if (!C) return false;

	ConstantInt *CI = dyn_cast<ConstantInt>(C);
	if (!CI) return false;

	Value *ReplaceWith = S->getOperand(1);
	Value *Other = S->getOperand(2);
	if (!CI->isOne()) std::swap(ReplaceWith, Other);
	if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType());

	S->replaceAllUsesWith(ReplaceWith);
	S->eraseFromParent();

	++NumSelects;

	return true;
	}

	bool CorrelatedValuePropagation::processPHI(PHINode *P) {
	bool Changed = false;

	BasicBlock *BB = P->getParent();
	for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
	Value *Incoming = P->getIncomingValue(i);
	if (isa<Constant>(Incoming)) continue;

	Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);

	// Look if the incoming value is a select with a scalar condition for which
	// LVI can tells us the value. In that case replace the incoming value with
	// the appropriate value of the select. This often allows us to remove the
	// select later.
	if (!V) {
	SelectInst *SI = dyn_cast<SelectInst>(Incoming);
	if (!SI) continue;

	Value *Condition = SI->getCondition();
	if (!Condition->getType()->isVectorTy()) {
	if (Constant *C = LVI->getConstantOnEdge(
	Condition, P->getIncomingBlock(i), BB, P)) {
	if (C->isOneValue()) {
	V = SI->getTrueValue();
	} else if (C->isZeroValue()) {
	V = SI->getFalseValue();
	}
	// Once LVI learns to handle vector types, we could also add support
	// for vector type constants that are not all zeroes or all ones.
	}
	}

	// Look if the select has a constant but LVI tells us that the incoming
	// value can never be that constant. In that case replace the incoming
	// value with the other value of the select. This often allows us to
	// remove the select later.
	if (!V) {
	Constant *C = dyn_cast<Constant>(SI->getFalseValue());
	if (!C) continue;

	if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
	P->getIncomingBlock(i), BB, P) !=
	LazyValueInfo::False)
	continue;
	V = SI->getTrueValue();
	}

	DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
	}

	P->setIncomingValue(i, V);
	Changed = true;
	}

	// FIXME: Provide TLI, DT, AT to SimplifyInstruction.
	const DataLayout &DL = BB->getModule()->getDataLayout();
	if (Value *V = SimplifyInstruction(P, DL)) {
	P->replaceAllUsesWith(V);
	P->eraseFromParent();
	Changed = true;
	}

	if (Changed)
	++NumPhis;

	return Changed;
	}

	bool CorrelatedValuePropagation::processMemAccess(Instruction *I) {
	Value *Pointer = nullptr;
	if (LoadInst *L = dyn_cast<LoadInst>(I))
	Pointer = L->getPointerOperand();
	else
	Pointer = cast<StoreInst>(I)->getPointerOperand();

	if (isa<Constant>(Pointer)) return false;

	Constant *C = LVI->getConstant(Pointer, I->getParent(), I);
	if (!C) return false;

	++NumMemAccess;
	I->replaceUsesOfWith(Pointer, C);
	return true;
	}

	/// processCmp - See if LazyValueInfo's ability to exploit edge conditions,
	/// or range information is sufficient to prove this comparison. Even for
	/// local conditions, this can sometimes prove conditions instcombine can't by
	/// exploiting range information.
	bool CorrelatedValuePropagation::processCmp(CmpInst *C) {
	Value *Op0 = C->getOperand(0);
	Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
	if (!Op1) return false;

	// As a policy choice, we choose not to waste compile time on anything where
	// the comparison is testing local values. While LVI can sometimes reason
	// about such cases, it's not its primary purpose. We do make sure to do
	// the block local query for uses from terminator instructions, but that's
	// handled in the code for each terminator.
	auto *I = dyn_cast<Instruction>(Op0);
	if (I && I->getParent() == C->getParent())
	return false;

	LazyValueInfo::Tristate Result =
	LVI->getPredicateAt(C->getPredicate(), Op0, Op1, C);
	if (Result == LazyValueInfo::Unknown) return false;

	++NumCmps;
	if (Result == LazyValueInfo::True)
	C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext()));
	else
	C->replaceAllUsesWith(ConstantInt::getFalse(C->getContext()));
	C->eraseFromParent();

	return true;
	}

	/// processSwitch - Simplify a switch instruction by removing cases which can
	/// never fire. If the uselessness of a case could be determined locally then
	/// constant propagation would already have figured it out. Instead, walk the
	/// predecessors and statically evaluate cases based on information available
	/// on that edge. Cases that cannot fire no matter what the incoming edge can
	/// safely be removed. If a case fires on every incoming edge then the entire
	/// switch can be removed and replaced with a branch to the case destination.
	bool CorrelatedValuePropagation::processSwitch(SwitchInst *SI) {
	Value *Cond = SI->getCondition();
	BasicBlock *BB = SI->getParent();

	// If the condition was defined in same block as the switch then LazyValueInfo
	// currently won't say anything useful about it, though in theory it could.
	if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
	return false;

	// If the switch is unreachable then trying to improve it is a waste of time.
	pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
	if (PB == PE) return false;

	// Analyse each switch case in turn. This is done in reverse order so that
	// removing a case doesn't cause trouble for the iteration.
	bool Changed = false;
	for (SwitchInst::CaseIt CI = SI->case_end(), CE = SI->case_begin(); CI-- != CE;
	) {
	ConstantInt *Case = CI.getCaseValue();

	// Check to see if the switch condition is equal to/not equal to the case
	// value on every incoming edge, equal/not equal being the same each time.
	LazyValueInfo::Tristate State = LazyValueInfo::Unknown;
	for (pred_iterator PI = PB; PI != PE; ++PI) {
	// Is the switch condition equal to the case value?
	LazyValueInfo::Tristate Value = LVI->getPredicateOnEdge(CmpInst::ICMP_EQ,
	Cond, Case, *PI,
	BB, SI);
	// Give up on this case if nothing is known.
	if (Value == LazyValueInfo::Unknown) {
	State = LazyValueInfo::Unknown;
	break;
	}

	// If this was the first edge to be visited, record that all other edges
	// need to give the same result.
	if (PI == PB) {
	State = Value;
	continue;
	}

	// If this case is known to fire for some edges and known not to fire for
	// others then there is nothing we can do - give up.
	if (Value != State) {
	State = LazyValueInfo::Unknown;
	break;
	}
	}

	if (State == LazyValueInfo::False) {
	// This case never fires - remove it.
	CI.getCaseSuccessor()->removePredecessor(BB);
	SI->removeCase(CI); // Does not invalidate the iterator.

	// The condition can be modified by removePredecessor's PHI simplification
	// logic.
	Cond = SI->getCondition();

	++NumDeadCases;
	Changed = true;
	} else if (State == LazyValueInfo::True) {
	// This case always fires. Arrange for the switch to be turned into an
	// unconditional branch by replacing the switch condition with the case
	// value.
	SI->setCondition(Case);
	NumDeadCases += SI->getNumCases();
	Changed = true;
	break;
	}
	}

	if (Changed)
	// If the switch has been simplified to the point where it can be replaced
	// by a branch then do so now.
	ConstantFoldTerminator(BB);

	return Changed;
	}

	/// processCallSite - Infer nonnull attributes for the arguments at the
	/// specified callsite.
	bool CorrelatedValuePropagation::processCallSite(CallSite CS) {
	SmallVector<unsigned, 4> Indices;
	unsigned ArgNo = 0;

	for (Value *V : CS.args()) {
	PointerType *Type = dyn_cast<PointerType>(V->getType());

	if (Type && !CS.paramHasAttr(ArgNo + 1, Attribute::NonNull) &&
	LVI->getPredicateAt(ICmpInst::ICMP_EQ, V,
	ConstantPointerNull::get(Type),
	CS.getInstruction()) == LazyValueInfo::False)
	Indices.push_back(ArgNo + 1);
	ArgNo++;
	}

	assert(ArgNo == CS.arg_size() && "sanity check");

	if (Indices.empty())
	return false;

	AttributeSet AS = CS.getAttributes();
	LLVMContext &Ctx = CS.getInstruction()->getContext();
	AS = AS.addAttribute(Ctx, Indices, Attribute::get(Ctx, Attribute::NonNull));
	CS.setAttributes(AS);

	return true;
	}

	Constant CorrelatedValuePropagation::getConstantAt(Value V, Instruction *At) {
	if (Constant *C = LVI->getConstant(V, At->getParent(), At))
	return C;

	// TODO: The following really should be sunk inside LVI's core algorithm, or
	// at least the outer shims around such.
	auto *C = dyn_cast<CmpInst>(V);
	if (!C) return nullptr;

	Value *Op0 = C->getOperand(0);
	Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
	if (!Op1) return nullptr;

	LazyValueInfo::Tristate Result =
	LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At);
	if (Result == LazyValueInfo::Unknown)
	return nullptr;

	return (Result == LazyValueInfo::True) ?
	ConstantInt::getTrue(C->getContext()) :
	ConstantInt::getFalse(C->getContext());
	}

	bool CorrelatedValuePropagation::runOnFunction(Function &F) {
	if (skipOptnoneFunction(F))
	return false;

	LVI = &getAnalysis<LazyValueInfo>();

	bool FnChanged = false;

	for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
	bool BBChanged = false;
	for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
	Instruction II = &BI++;
	switch (II->getOpcode()) {
	case Instruction::Select:
	BBChanged \|= processSelect(cast<SelectInst>(II));
	break;
	case Instruction::PHI:
	BBChanged \|= processPHI(cast<PHINode>(II));
	break;
	case Instruction::ICmp:
	case Instruction::FCmp:
	BBChanged \|= processCmp(cast<CmpInst>(II));
	break;
	case Instruction::Load:
	case Instruction::Store:
	BBChanged \|= processMemAccess(II);
	break;
	case Instruction::Call:
	case Instruction::Invoke:
	BBChanged \|= processCallSite(CallSite(II));
	break;
	}
	}

	Instruction *Term = FI->getTerminator();
	switch (Term->getOpcode()) {
	case Instruction::Switch:
	BBChanged \|= processSwitch(cast<SwitchInst>(Term));
	break;
	case Instruction::Ret: {
	auto *RI = cast<ReturnInst>(Term);
	// Try to determine the return value if we can. This is mainly here to
	// simplify the writing of unit tests, but also helps to enable IPO by
	// constant folding the return values of callees.
	auto *RetVal = RI->getReturnValue();
	if (!RetVal) break; // handle "ret void"
	if (isa<Constant>(RetVal)) break; // nothing to do
	if (auto *C = getConstantAt(RetVal, RI)) {
	++NumReturns;
	RI->replaceUsesOfWith(RetVal, C);
	BBChanged = true;
	}
	}
	};

	FnChanged \|= BBChanged;
	}

	return FnChanged;
	}