lib/SILAnalysis/SideEffectAnalysis.cpp - third_party/swift - Git at Google

 //===---------- SideEffectAnalysis.cpp - SIL Side Effect Analysis ---------===//
 //
 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
 // Licensed under Apache License v2.0 with Runtime Library Exception
 //
 // See http://swift.org/LICENSE.txt for license information
 // See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
 //
 //===----------------------------------------------------------------------===//

 #define DEBUG_TYPE "sil-sea"
 #include "swift/SILAnalysis/SideEffectAnalysis.h"
 #include "swift/SILAnalysis/CallGraphAnalysis.h"
 #include "swift/SILAnalysis/ArraySemantic.h"
 #include "swift/SILPasses/PassManager.h"
 #include "swift/SIL/SILArgument.h"


 using namespace swift;

 SILInstruction::MemoryBehavior
 SideEffectAnalysis::FunctionEffects::getMemBehavior(bool IgnoreRetains) const {
   if ((!IgnoreRetains && mayAllocObjects()) || mayReadRC())
     return SILInstruction::MemoryBehavior::MayHaveSideEffects;

   // Start with the global effects.
   auto Behavior = GlobalEffects.getMemBehavior(IgnoreRetains);

   // Add effects from the parameters.
   for (auto Iter = ParamEffects.begin(), End = ParamEffects.end();
        Iter != End &&
        Behavior < SILInstruction::MemoryBehavior::MayHaveSideEffects;
        ++Iter) {
     const Effects &ParamEffect = *Iter;
     auto ArgBehavior = ParamEffect.getMemBehavior(IgnoreRetains);
     if (ArgBehavior > Behavior)
       Behavior = ArgBehavior;
   }
   return Behavior;
 }

 bool SideEffectAnalysis::FunctionEffects::mergeFrom(const FunctionEffects &RHS) {
   bool Changed = mergeFlags(RHS);
   Changed |= GlobalEffects.mergeFrom(RHS.GlobalEffects);
   Changed |= LocalEffects.mergeFrom(RHS.LocalEffects);
   // In case of an external function, the RHS may have 0 arguments.
   unsigned NumArgs = RHS.ParamEffects.size();
   for (unsigned Idx = 0; Idx < NumArgs; Idx++) {
     // In case of a partial_apply, the RHS (= callee) may have more arguments
     // than the apply instruction.
     if (Idx < ParamEffects.size()) {
       Changed |= ParamEffects[Idx].mergeFrom(RHS.ParamEffects[Idx]);
     } else {
       Changed |= GlobalEffects.mergeFrom(RHS.ParamEffects[Idx]);
     }
   }
   return Changed;
 }

 bool SideEffectAnalysis::FunctionEffects::mergeFromApply(
                   const FunctionEffects &ApplyEffects, FullApplySite FAS) {
   bool Changed = mergeFlags(ApplyEffects);
   Changed |= GlobalEffects.mergeFrom(ApplyEffects.GlobalEffects);
   auto Args = FAS.getArguments();
   unsigned NumCalleeArgs = ApplyEffects.ParamEffects.size();
   assert(NumCalleeArgs == Args.size());
   for (unsigned Idx = 0; Idx < NumCalleeArgs; Idx++) {
     // Map the callee argument effects to parameters of this function.
     Effects *E = getEffectsOn(Args[Idx]);
     Changed |= E->mergeFrom(ApplyEffects.ParamEffects[Idx]);
   }
   return Changed;
 }

 void SideEffectAnalysis::FunctionEffects::dump() {
   llvm::errs() << *this << '\n';
 }

 static SILValue skipAddrProjections(SILValue V) {
   for (;;) {
     switch (V->getKind()) {
       case ValueKind::IndexAddrInst:
       case ValueKind::IndexRawPointerInst:
       case ValueKind::StructElementAddrInst:
       case ValueKind::TupleElementAddrInst:
       case ValueKind::RefElementAddrInst:
       case ValueKind::UncheckedTakeEnumDataAddrInst:
       case ValueKind::PointerToAddressInst:
         V = cast<SILInstruction>(V)->getOperand(0);
         break;
       default:
         return V;
     }
   }
   llvm_unreachable("there is no escape from an infinite loop");
 }

 static SILValue skipValueProjections(SILValue V) {
   for (;;) {
     switch (V->getKind()) {
       case ValueKind::StructExtractInst:
       case ValueKind::TupleExtractInst:
       case ValueKind::UncheckedEnumDataInst:
       case ValueKind::UncheckedTrivialBitCastInst:
         V = cast<SILInstruction>(V)->getOperand(0);
         break;
       default:
         return V;
     }
   }
   llvm_unreachable("there is no escape from an infinite loop");
 }

 SideEffectAnalysis::Effects *
 SideEffectAnalysis::FunctionEffects::getEffectsOn(SILValue Addr) {
   SILValue BaseAddr = skipValueProjections(skipAddrProjections(Addr));
   switch (BaseAddr->getKind()) {
     case swift::ValueKind::SILArgument: {
       // Can we associate the address to a function parameter?
       SILArgument *Arg = cast<SILArgument>(BaseAddr);
       if (Arg->isFunctionArg()) {
         return &ParamEffects[Arg->getIndex()];
       }
       break;
     }
     case ValueKind::AllocStackInst:
     case ValueKind::AllocRefInst:
     case ValueKind::AllocRefDynamicInst:
     case ValueKind::AllocBoxInst:
       // Effects on locally allocated storage.
       return &LocalEffects;
     default:
       break;
   }
   // Everything else.
   return &GlobalEffects;
 }

 bool SideEffectAnalysis::getDefinedEffects(FunctionEffects &Effects,
                                            SILFunction *F) {
   if (F->getLoweredFunctionType()->isNoReturn()) {
     Effects.Traps = true;
     return true;
   }
   switch (F->getEffectsKind()) {
     case EffectsKind::ReadNone:
       return true;
     case EffectsKind::ReadOnly:
       // @effects(readonly) is worthless if we have owned parameters, because
       // the release inside the callee may call a deinit, which itself can do
       // anything.
       if (!F->hasOwnedParameters()) {
         Effects.GlobalEffects.Reads = true;
         return true;
       }
       break;
     default:
       break;
   }

   return false;
 }

 bool SideEffectAnalysis::getSemanticEffects(FunctionEffects &FE,
                                             FullApplySite FAS) {
   ArraySemanticsCall ASC(FAS.getInstruction());
   if (!ASC || !ASC.hasSelf())
     return false;

   auto &SelfEffects = FE.ParamEffects[FAS.getNumArguments() - 1];

   // Currently we only handle array semantics.
   // TODO: also handle other semantic functions.

   switch (ASC.getKind()) {
     case ArrayCallKind::kGetCount:
     case ArrayCallKind::kGetCapacity:
       if (!ASC.mayHaveBridgedObjectElementType()) {
         SelfEffects.Reads = true;
         SelfEffects.Releases |= !ASC.hasGuaranteedSelf();
         return true;
       }
       return false;

     case ArrayCallKind::kCheckSubscript:
     case ArrayCallKind::kCheckIndex:
       if (!ASC.mayHaveBridgedObjectElementType()) {
         SelfEffects.Reads = true;
         SelfEffects.Releases |= !ASC.hasGuaranteedSelf();
         FE.Traps = true;
         return true;
       }
       return false;

     case ArrayCallKind::kGetElement:
       if (!ASC.mayHaveBridgedObjectElementType()) {
         SelfEffects.Reads = true;
         SelfEffects.Releases |= !ASC.hasGuaranteedSelf();
         if (FAS.getOrigCalleeType()->hasIndirectResult())
           FE.ParamEffects[0].Writes = true;
         return true;
       }
       return false;

     case ArrayCallKind::kArrayPropsIsNative:
     case ArrayCallKind::kArrayPropsIsNativeTypeChecked:
       SelfEffects.Releases |= !ASC.hasGuaranteedSelf();
       // The isNative checks evaluate to a constant (no read!) if the array
       // cannot be bridged.
       if (ASC.mayHaveBridgedObjectElementType())
         SelfEffects.Reads = true;
       return true;

     case ArrayCallKind::kGetElementAddress:
       SelfEffects.Reads = true;
       SelfEffects.Releases |= !ASC.hasGuaranteedSelf();
       return true;

     case ArrayCallKind::kMakeMutable:
       if (!ASC.mayHaveBridgedObjectElementType()) {
         SelfEffects.Writes = true;
         FE.GlobalEffects.Releases = true;
         FE.AllocsObjects = true;
         FE.ReadsRC = true;
         return true;
       }
       return false;

     default:
       return false;
   }
 }

 void SideEffectAnalysis::analyzeFunction(SILFunction *F,
                                          WorkListType &WorkList,
                                          CallGraph &CG) {
   DEBUG(llvm::dbgs() << "analyze " << F->getName() << "\n");
   auto *FE = getFunctionEffects(F, true);

   // Handle @effects attributes
   if (getDefinedEffects(*FE, F))
     return;

   if (!F->isDefinition()) {
     // We can't assume anything about external functions.
     FE->setWorstEffects();
     return;
   }

   FunctionEffects NewEffects(F->getArguments().size());
 #ifndef NDEBUG
   FunctionEffects RefEffects = *FE;
 #endif
   // Check all instructions of the function
   for (auto &BB : *F) {
     for (auto &I : BB) {
       analyzeInstruction(NewEffects, &I, CG);
       DEBUG(if (RefEffects.mergeFrom(NewEffects))
               llvm::dbgs() << "  " << NewEffects << "\t changed in " << I);
     }
   }
   if (FE->mergeFrom(NewEffects)) {
     // The effects have changed. We also have to recompute the effects of all
     // callers.
     for (auto *CallerEdge : CG.getCallerEdges(F)) {
       SILFunction *Caller = CallerEdge->getInstruction()->getFunction();
       WorkList.insert(Caller);
     }
   }
 }

 void SideEffectAnalysis::analyzeInstruction(FunctionEffects &FE,
                                             SILInstruction *I, CallGraph &CG) {
   if (FullApplySite FAS = FullApplySite::isa(I)) {
     FunctionEffects ApplyEffects;
     getEffectsOfApply(ApplyEffects, FAS, CG, true);
     FE.mergeFromApply(ApplyEffects, FAS);
     return;
   }
   // Handle some kind of instructions specially.
   switch (I->getKind()) {
     case ValueKind::AllocStackInst:
     case ValueKind::DeallocStackInst:
       return;
     case ValueKind::StrongRetainInst:
     case ValueKind::StrongRetainUnownedInst:
     case ValueKind::RetainValueInst:
     case ValueKind::UnownedRetainInst:
       FE.getEffectsOn(I->getOperand(0))->Retains = true;
       return;
     case ValueKind::StrongReleaseInst:
     case ValueKind::ReleaseValueInst:
     case ValueKind::UnownedReleaseInst:
       FE.getEffectsOn(I->getOperand(0))->Releases = true;

       // TODO: Check the call graph to be less conservative about what
       // destructors might be called.
       FE.setWorstEffects();
       return;
     case ValueKind::LoadInst:
       FE.getEffectsOn(cast<LoadInst>(I)->getOperand())->Reads = true;
       return;
     case ValueKind::StoreInst:
       FE.getEffectsOn(cast<StoreInst>(I)->getDest())->Writes = true;
       return;
     case ValueKind::CondFailInst:
       FE.Traps = true;
       return;
     case ValueKind::PartialApplyInst:
       FE.AllocsObjects = true;
       return;
     case ValueKind::BuiltinInst: {
       auto &BI = cast<BuiltinInst>(I)->getBuiltinInfo();
       switch (BI.ID) {
         case BuiltinValueKind::IsUnique:
           // TODO: derive this information in a more general way, e.g. add it
           // to Builtins.def
           FE.ReadsRC = true;
           break;
         default:
           break;
       }
       // Detailed memory effects of builtins are handled below by checking the
       // memory behavior of the instruction.
       break;
       }
     default:
       break;
   }

   if (isa<AllocationInst>(I)) {
     // Excluding AllocStackInst (which is handled above).
     FE.AllocsObjects = true;
   }

   // Check the general memory behavior for instructions we didn't handle above.
   switch (I->getMemoryBehavior()) {
     case SILInstruction::MemoryBehavior::None:
       break;
     case SILInstruction::MemoryBehavior::MayRead:
       FE.GlobalEffects.Reads = true;
       break;
     case SILInstruction::MemoryBehavior::MayWrite:
       FE.GlobalEffects.Writes = true;
       break;
     case SILInstruction::MemoryBehavior::MayReadWrite:
       FE.GlobalEffects.Reads = true;
       FE.GlobalEffects.Writes = true;
       break;
     case SILInstruction::MemoryBehavior::MayHaveSideEffects:
       FE.setWorstEffects();
       break;
   }
   if (I->mayTrap())
     FE.Traps = true;
 }

 void SideEffectAnalysis::getEffectsOfApply(FunctionEffects &ApplyEffects,
                                            FullApplySite FAS, CallGraph &CG,
                                            bool isRecomputing) {

   assert(ApplyEffects.ParamEffects.size() == 0 &&
          "Not using a new ApplyEffects?");
   ApplyEffects.ParamEffects.resize(FAS.getNumArguments());

   // Is this a call to a semantics function?
   if (getSemanticEffects(ApplyEffects, FAS))
     return;

   if (CG.canCallUnknownFunction(FAS.getInstruction())) {
     ApplyEffects.setWorstEffects();
     return;
   }

   // We can see all the callees. So we just merge the effects from all of
   // them.
   for (auto *F : CG.getCallees(FAS.getInstruction())) {
     auto *E = getFunctionEffects(F, isRecomputing);
     ApplyEffects.mergeFrom(*E);
   }
 }

 void SideEffectAnalysis::initialize(SILPassManager *PM) {
   CGA = PM->getAnalysis<CallGraphAnalysis>();
 }

 void SideEffectAnalysis::recompute() {

   // Did anything change since the last recompuation? (Probably yes)
   if (!shouldRecompute)
     return;

   Function2Effects.clear();
   Allocator.DestroyAll();
   shouldRecompute = false;

   WorkListType WorkList;

   CallGraph &CG = CGA->getOrBuildCallGraph();
   auto BottomUpFunctions = CG.getBottomUpFunctionOrder();

   // Copy the bottom-up function list into the worklist.
   for (auto I = BottomUpFunctions.rbegin(), E = BottomUpFunctions.rend();
        I != E; ++I)
     WorkList.insert(*I);

   // Iterate until the side-effect information stabilizes.
   while (!WorkList.empty()) {
     auto *F = WorkList.pop_back_val();
     analyzeFunction(F, WorkList, CG);
   }
 }

 void SideEffectAnalysis::getEffects(FunctionEffects &FE, FullApplySite FAS) {
   CallGraph *CG = CGA->getCallGraphOrNull();
   if (CG) {
     getEffectsOfApply(FE, FAS, *CG, false);
     return;
   }
   FE.setWorstEffects();
 }

 SILAnalysis *swift::createSideEffectAnalysis(SILModule *M) {
   return new SideEffectAnalysis(M);
 }
	//===---------- SideEffectAnalysis.cpp - SIL Side Effect Analysis ---------===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See http://swift.org/LICENSE.txt for license information
	// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//

	#define DEBUG_TYPE "sil-sea"
	#include "swift/SILAnalysis/SideEffectAnalysis.h"
	#include "swift/SILAnalysis/CallGraphAnalysis.h"
	#include "swift/SILAnalysis/ArraySemantic.h"
	#include "swift/SILPasses/PassManager.h"
	#include "swift/SIL/SILArgument.h"


	using namespace swift;

	SILInstruction::MemoryBehavior
	SideEffectAnalysis::FunctionEffects::getMemBehavior(bool IgnoreRetains) const {
	if ((!IgnoreRetains && mayAllocObjects()) \|\| mayReadRC())
	return SILInstruction::MemoryBehavior::MayHaveSideEffects;

	// Start with the global effects.
	auto Behavior = GlobalEffects.getMemBehavior(IgnoreRetains);

	// Add effects from the parameters.
	for (auto Iter = ParamEffects.begin(), End = ParamEffects.end();
	Iter != End &&
	Behavior < SILInstruction::MemoryBehavior::MayHaveSideEffects;
	++Iter) {
	const Effects &ParamEffect = *Iter;
	auto ArgBehavior = ParamEffect.getMemBehavior(IgnoreRetains);
	if (ArgBehavior > Behavior)
	Behavior = ArgBehavior;
	}
	return Behavior;
	}

	bool SideEffectAnalysis::FunctionEffects::mergeFrom(const FunctionEffects &RHS) {
	bool Changed = mergeFlags(RHS);
	Changed \|= GlobalEffects.mergeFrom(RHS.GlobalEffects);
	Changed \|= LocalEffects.mergeFrom(RHS.LocalEffects);
	// In case of an external function, the RHS may have 0 arguments.
	unsigned NumArgs = RHS.ParamEffects.size();
	for (unsigned Idx = 0; Idx < NumArgs; Idx++) {
	// In case of a partial_apply, the RHS (= callee) may have more arguments
	// than the apply instruction.
	if (Idx < ParamEffects.size()) {
	Changed \|= ParamEffects[Idx].mergeFrom(RHS.ParamEffects[Idx]);
	} else {
	Changed \|= GlobalEffects.mergeFrom(RHS.ParamEffects[Idx]);
	}
	}
	return Changed;
	}

	bool SideEffectAnalysis::FunctionEffects::mergeFromApply(
	const FunctionEffects &ApplyEffects, FullApplySite FAS) {
	bool Changed = mergeFlags(ApplyEffects);
	Changed \|= GlobalEffects.mergeFrom(ApplyEffects.GlobalEffects);
	auto Args = FAS.getArguments();
	unsigned NumCalleeArgs = ApplyEffects.ParamEffects.size();
	assert(NumCalleeArgs == Args.size());
	for (unsigned Idx = 0; Idx < NumCalleeArgs; Idx++) {
	// Map the callee argument effects to parameters of this function.
	Effects *E = getEffectsOn(Args[Idx]);
	Changed \|= E->mergeFrom(ApplyEffects.ParamEffects[Idx]);
	}
	return Changed;
	}

	void SideEffectAnalysis::FunctionEffects::dump() {
	llvm::errs() << *this << '\n';
	}

	static SILValue skipAddrProjections(SILValue V) {
	for (;;) {
	switch (V->getKind()) {
	case ValueKind::IndexAddrInst:
	case ValueKind::IndexRawPointerInst:
	case ValueKind::StructElementAddrInst:
	case ValueKind::TupleElementAddrInst:
	case ValueKind::RefElementAddrInst:
	case ValueKind::UncheckedTakeEnumDataAddrInst:
	case ValueKind::PointerToAddressInst:
	V = cast<SILInstruction>(V)->getOperand(0);
	break;
	default:
	return V;
	}
	}
	llvm_unreachable("there is no escape from an infinite loop");
	}

	static SILValue skipValueProjections(SILValue V) {
	for (;;) {
	switch (V->getKind()) {
	case ValueKind::StructExtractInst:
	case ValueKind::TupleExtractInst:
	case ValueKind::UncheckedEnumDataInst:
	case ValueKind::UncheckedTrivialBitCastInst:
	V = cast<SILInstruction>(V)->getOperand(0);
	break;
	default:
	return V;
	}
	}
	llvm_unreachable("there is no escape from an infinite loop");
	}

	SideEffectAnalysis::Effects *
	SideEffectAnalysis::FunctionEffects::getEffectsOn(SILValue Addr) {
	SILValue BaseAddr = skipValueProjections(skipAddrProjections(Addr));
	switch (BaseAddr->getKind()) {
	case swift::ValueKind::SILArgument: {
	// Can we associate the address to a function parameter?
	SILArgument *Arg = cast<SILArgument>(BaseAddr);
	if (Arg->isFunctionArg()) {
	return &ParamEffects[Arg->getIndex()];
	}
	break;
	}
	case ValueKind::AllocStackInst:
	case ValueKind::AllocRefInst:
	case ValueKind::AllocRefDynamicInst:
	case ValueKind::AllocBoxInst:
	// Effects on locally allocated storage.
	return &LocalEffects;
	default:
	break;
	}
	// Everything else.
	return &GlobalEffects;
	}

	bool SideEffectAnalysis::getDefinedEffects(FunctionEffects &Effects,
	SILFunction *F) {
	if (F->getLoweredFunctionType()->isNoReturn()) {
	Effects.Traps = true;
	return true;
	}
	switch (F->getEffectsKind()) {
	case EffectsKind::ReadNone:
	return true;
	case EffectsKind::ReadOnly:
	// @effects(readonly) is worthless if we have owned parameters, because
	// the release inside the callee may call a deinit, which itself can do
	// anything.
	if (!F->hasOwnedParameters()) {
	Effects.GlobalEffects.Reads = true;
	return true;
	}
	break;
	default:
	break;
	}

	return false;
	}

	bool SideEffectAnalysis::getSemanticEffects(FunctionEffects &FE,
	FullApplySite FAS) {
	ArraySemanticsCall ASC(FAS.getInstruction());
	if (!ASC \|\| !ASC.hasSelf())
	return false;

	auto &SelfEffects = FE.ParamEffects[FAS.getNumArguments() - 1];

	// Currently we only handle array semantics.
	// TODO: also handle other semantic functions.

	switch (ASC.getKind()) {
	case ArrayCallKind::kGetCount:
	case ArrayCallKind::kGetCapacity:
	if (!ASC.mayHaveBridgedObjectElementType()) {
	SelfEffects.Reads = true;
	SelfEffects.Releases \|= !ASC.hasGuaranteedSelf();
	return true;
	}
	return false;

	case ArrayCallKind::kCheckSubscript:
	case ArrayCallKind::kCheckIndex:
	if (!ASC.mayHaveBridgedObjectElementType()) {
	SelfEffects.Reads = true;
	SelfEffects.Releases \|= !ASC.hasGuaranteedSelf();
	FE.Traps = true;
	return true;
	}
	return false;

	case ArrayCallKind::kGetElement:
	if (!ASC.mayHaveBridgedObjectElementType()) {
	SelfEffects.Reads = true;
	SelfEffects.Releases \|= !ASC.hasGuaranteedSelf();
	if (FAS.getOrigCalleeType()->hasIndirectResult())
	FE.ParamEffects[0].Writes = true;
	return true;
	}
	return false;

	case ArrayCallKind::kArrayPropsIsNative:
	case ArrayCallKind::kArrayPropsIsNativeTypeChecked:
	SelfEffects.Releases \|= !ASC.hasGuaranteedSelf();
	// The isNative checks evaluate to a constant (no read!) if the array
	// cannot be bridged.
	if (ASC.mayHaveBridgedObjectElementType())
	SelfEffects.Reads = true;
	return true;

	case ArrayCallKind::kGetElementAddress:
	SelfEffects.Reads = true;
	SelfEffects.Releases \|= !ASC.hasGuaranteedSelf();
	return true;

	case ArrayCallKind::kMakeMutable:
	if (!ASC.mayHaveBridgedObjectElementType()) {
	SelfEffects.Writes = true;
	FE.GlobalEffects.Releases = true;
	FE.AllocsObjects = true;
	FE.ReadsRC = true;
	return true;
	}
	return false;

	default:
	return false;
	}
	}

	void SideEffectAnalysis::analyzeFunction(SILFunction *F,
	WorkListType &WorkList,
	CallGraph &CG) {
	DEBUG(llvm::dbgs() << "analyze " << F->getName() << "\n");
	auto *FE = getFunctionEffects(F, true);

	// Handle @effects attributes
	if (getDefinedEffects(*FE, F))
	return;

	if (!F->isDefinition()) {
	// We can't assume anything about external functions.
	FE->setWorstEffects();
	return;
	}

	FunctionEffects NewEffects(F->getArguments().size());
	#ifndef NDEBUG
	FunctionEffects RefEffects = *FE;
	#endif
	// Check all instructions of the function
	for (auto &BB : *F) {
	for (auto &I : BB) {
	analyzeInstruction(NewEffects, &I, CG);
	DEBUG(if (RefEffects.mergeFrom(NewEffects))
	llvm::dbgs() << " " << NewEffects << "\t changed in " << I);
	}
	}
	if (FE->mergeFrom(NewEffects)) {
	// The effects have changed. We also have to recompute the effects of all
	// callers.
	for (auto *CallerEdge : CG.getCallerEdges(F)) {
	SILFunction *Caller = CallerEdge->getInstruction()->getFunction();
	WorkList.insert(Caller);
	}
	}
	}

	void SideEffectAnalysis::analyzeInstruction(FunctionEffects &FE,
	SILInstruction *I, CallGraph &CG) {
	if (FullApplySite FAS = FullApplySite::isa(I)) {
	FunctionEffects ApplyEffects;
	getEffectsOfApply(ApplyEffects, FAS, CG, true);
	FE.mergeFromApply(ApplyEffects, FAS);
	return;
	}
	// Handle some kind of instructions specially.
	switch (I->getKind()) {
	case ValueKind::AllocStackInst:
	case ValueKind::DeallocStackInst:
	return;
	case ValueKind::StrongRetainInst:
	case ValueKind::StrongRetainUnownedInst:
	case ValueKind::RetainValueInst:
	case ValueKind::UnownedRetainInst:
	FE.getEffectsOn(I->getOperand(0))->Retains = true;
	return;
	case ValueKind::StrongReleaseInst:
	case ValueKind::ReleaseValueInst:
	case ValueKind::UnownedReleaseInst:
	FE.getEffectsOn(I->getOperand(0))->Releases = true;

	// TODO: Check the call graph to be less conservative about what
	// destructors might be called.
	FE.setWorstEffects();
	return;
	case ValueKind::LoadInst:
	FE.getEffectsOn(cast<LoadInst>(I)->getOperand())->Reads = true;
	return;
	case ValueKind::StoreInst:
	FE.getEffectsOn(cast<StoreInst>(I)->getDest())->Writes = true;
	return;
	case ValueKind::CondFailInst:
	FE.Traps = true;
	return;
	case ValueKind::PartialApplyInst:
	FE.AllocsObjects = true;
	return;
	case ValueKind::BuiltinInst: {
	auto &BI = cast<BuiltinInst>(I)->getBuiltinInfo();
	switch (BI.ID) {
	case BuiltinValueKind::IsUnique:
	// TODO: derive this information in a more general way, e.g. add it
	// to Builtins.def
	FE.ReadsRC = true;
	break;
	default:
	break;
	}
	// Detailed memory effects of builtins are handled below by checking the
	// memory behavior of the instruction.
	break;
	}
	default:
	break;
	}

	if (isa<AllocationInst>(I)) {
	// Excluding AllocStackInst (which is handled above).
	FE.AllocsObjects = true;
	}

	// Check the general memory behavior for instructions we didn't handle above.
	switch (I->getMemoryBehavior()) {
	case SILInstruction::MemoryBehavior::None:
	break;
	case SILInstruction::MemoryBehavior::MayRead:
	FE.GlobalEffects.Reads = true;
	break;
	case SILInstruction::MemoryBehavior::MayWrite:
	FE.GlobalEffects.Writes = true;
	break;
	case SILInstruction::MemoryBehavior::MayReadWrite:
	FE.GlobalEffects.Reads = true;
	FE.GlobalEffects.Writes = true;
	break;
	case SILInstruction::MemoryBehavior::MayHaveSideEffects:
	FE.setWorstEffects();
	break;
	}
	if (I->mayTrap())
	FE.Traps = true;
	}

	void SideEffectAnalysis::getEffectsOfApply(FunctionEffects &ApplyEffects,
	FullApplySite FAS, CallGraph &CG,
	bool isRecomputing) {

	assert(ApplyEffects.ParamEffects.size() == 0 &&
	"Not using a new ApplyEffects?");
	ApplyEffects.ParamEffects.resize(FAS.getNumArguments());

	// Is this a call to a semantics function?
	if (getSemanticEffects(ApplyEffects, FAS))
	return;

	if (CG.canCallUnknownFunction(FAS.getInstruction())) {
	ApplyEffects.setWorstEffects();
	return;
	}

	// We can see all the callees. So we just merge the effects from all of
	// them.
	for (auto *F : CG.getCallees(FAS.getInstruction())) {
	auto *E = getFunctionEffects(F, isRecomputing);
	ApplyEffects.mergeFrom(*E);
	}
	}

	void SideEffectAnalysis::initialize(SILPassManager *PM) {
	CGA = PM->getAnalysis<CallGraphAnalysis>();
	}

	void SideEffectAnalysis::recompute() {

	// Did anything change since the last recompuation? (Probably yes)
	if (!shouldRecompute)
	return;

	Function2Effects.clear();
	Allocator.DestroyAll();
	shouldRecompute = false;

	WorkListType WorkList;

	CallGraph &CG = CGA->getOrBuildCallGraph();
	auto BottomUpFunctions = CG.getBottomUpFunctionOrder();

	// Copy the bottom-up function list into the worklist.
	for (auto I = BottomUpFunctions.rbegin(), E = BottomUpFunctions.rend();
	I != E; ++I)
	WorkList.insert(*I);

	// Iterate until the side-effect information stabilizes.
	while (!WorkList.empty()) {
	auto *F = WorkList.pop_back_val();
	analyzeFunction(F, WorkList, CG);
	}
	}

	void SideEffectAnalysis::getEffects(FunctionEffects &FE, FullApplySite FAS) {
	CallGraph *CG = CGA->getCallGraphOrNull();
	if (CG) {
	getEffectsOfApply(FE, FAS, *CG, false);
	return;
	}
	FE.setWorstEffects();
	}

	SILAnalysis swift::createSideEffectAnalysis(SILModule M) {
	return new SideEffectAnalysis(M);
	}