lib/SILOptimizer/LoopTransforms/LICM.cpp - third_party/swift - Git at Google

 //===--- LICM.cpp - Loop invariant code motion ----------------------------===//
 //
 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
 // Licensed under Apache License v2.0 with Runtime Library Exception
 //
 // See https://swift.org/LICENSE.txt for license information
 // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
 //
 //===----------------------------------------------------------------------===//

 #define DEBUG_TYPE "sil-licm"

 #include "swift/SIL/Dominance.h"
 #include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
 #include "swift/SILOptimizer/Analysis/Analysis.h"
 #include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
 #include "swift/SILOptimizer/Analysis/LoopAnalysis.h"
 #include "swift/SILOptimizer/Analysis/ArraySemantic.h"
 #include "swift/SILOptimizer/Analysis/SideEffectAnalysis.h"
 #include "swift/SILOptimizer/PassManager/Passes.h"
 #include "swift/SILOptimizer/PassManager/Transforms.h"
 #include "swift/SILOptimizer/Utils/CFG.h"
 #include "swift/SILOptimizer/Utils/SILSSAUpdater.h"
 #include "swift/SILOptimizer/Utils/Local.h"
 #include "swift/SIL/SILArgument.h"
 #include "swift/SIL/SILBuilder.h"
 #include "swift/SIL/SILInstruction.h"
 #include "swift/SIL/InstructionUtils.h"

 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/Debug.h"

 #include "llvm/Support/CommandLine.h"

 using namespace swift;

 /// Instructions which read from memory, e.g. loads, or function calls without
 /// side effects.
 using ReadSet = llvm::SmallPtrSet<SILInstruction *, 8>;

 /// Instructions which (potentially) write memory.
 using WriteSet = SmallVector<SILInstruction *, 8>;

 /// Returns true if the \p MayWrites set contains any memory writes which may
 /// alias with the memory addressed by \a LI.
 static bool mayWriteTo(AliasAnalysis *AA, WriteSet &MayWrites, LoadInst *LI) {
   for (auto *W : MayWrites)
     if (AA->mayWriteToMemory(W, LI->getOperand())) {
       DEBUG(llvm::dbgs() << "  mayWriteTo\n" << *W << " to " << *LI << "\n");
       return true;
     }
   return false;
 }

 /// Returns true if the \p MayWrites set contains any memory writes which may
 /// alias with any memory which is read by \p AI.
 static bool mayWriteTo(AliasAnalysis *AA, SideEffectAnalysis *SEA,
                        WriteSet &MayWrites, ApplyInst *AI) {
   SideEffectAnalysis::FunctionEffects E;
   SEA->getEffects(E, AI);
   assert(E.getMemBehavior(RetainObserveKind::IgnoreRetains) <=
          SILInstruction::MemoryBehavior::MayRead &&
          "apply should only read from memory");
   if (E.getGlobalEffects().mayRead() && !MayWrites.empty()) {
     // We don't know which memory is read in the callee. Therefore we bail if
     // there are any writes in the loop.
     return true;
   }

   for (unsigned Idx = 0, End = AI->getNumArguments(); Idx < End; ++Idx) {
     auto &ArgEffect = E.getParameterEffects()[Idx];
     if (!ArgEffect.mayRead())
       continue;

     SILValue Arg = AI->getArgument(Idx);

     // Check if the memory addressed by the argument may alias any writes.
     for (auto *W : MayWrites) {
       if (AA->mayWriteToMemory(W, Arg)) {
         DEBUG(llvm::dbgs() << "  mayWriteTo\n" << *W << " to " << *AI << "\n");
         return true;
       }
     }
   }
   return false;
 }

 static void removeWrittenTo(AliasAnalysis *AA, ReadSet &Reads,
                             SILInstruction *ByInst) {

   // We can ignore retains, cond_fails, and dealloc_stacks.
   if (isa<StrongRetainInst>(ByInst) || isa<RetainValueInst>(ByInst) ||
       isa<CondFailInst>(ByInst) || isa<DeallocStackInst>(ByInst))
     return;

   SmallVector<SILInstruction *, 8> RS(Reads.begin(), Reads.end());
   for (auto R : RS) {
     auto *LI = dyn_cast<LoadInst>(R);
     if (LI && !AA->mayWriteToMemory(ByInst, LI->getOperand()))
       continue;

     DEBUG(llvm::dbgs() << "  mayWriteTo\n" << *ByInst << " to " << *R << "\n");
     Reads.erase(R);
   }
 }

 static bool hasLoopInvariantOperands(SILInstruction *I, SILLoop *L) {
   auto Opds = I->getAllOperands();

   return std::all_of(Opds.begin(), Opds.end(), [=](Operand &Op) {

     ValueBase *Def = Op.get();

     // Operand is defined outside the loop.
     if (auto *Inst = dyn_cast<SILInstruction>(Def))
       return !L->contains(Inst->getParent());
     if (auto *Arg = dyn_cast<SILArgument>(Def))
       return !L->contains(Arg->getParent());

     return false;
   });
 }

 /// Check if an address does not depend on other values in a basic block.
 static SILInstruction *addressIndependent(SILValue Addr) {
   Addr = stripCasts(Addr);
   if (GlobalAddrInst *SGAI = dyn_cast<GlobalAddrInst>(Addr))
     return SGAI;
   if (StructElementAddrInst *SEAI = dyn_cast<StructElementAddrInst>(Addr))
     return addressIndependent(SEAI->getOperand());
   return nullptr;
 }

 /// Check if two addresses can potentially access the same memory.
 /// For now, return true when both can be traced to the same global variable.
 static bool addressCanPairUp(SILValue Addr1, SILValue Addr2) {
   SILInstruction *Origin1 = addressIndependent(Addr1);
   return Origin1 && Origin1 == addressIndependent(Addr2);
 }

 /// Move cond_fail down if it can potentially help register promotion later.
 static bool sinkCondFail(SILLoop *Loop) {
   // Only handle innermost loops for now.
   if (!Loop->getSubLoops().empty())
     return false;

   bool Changed = false;
   for (auto *BB : Loop->getBlocks()) {
     // A list of CondFails that can be moved down.
     SmallVector<CondFailInst*, 4> CFs;
     // A pair of load and store that are independent of the CondFails and
     // can potentially access the same memory.
     LoadInst *LIOfPair = nullptr;
     bool foundPair = false;

     for (auto &Inst : *BB) {
       if (foundPair) {
         // Move CFs to right before Inst.
         for (unsigned I = 0, E = CFs.size(); I < E; I++) {
           DEBUG(llvm::dbgs() << "sinking cond_fail down ");
           DEBUG(CFs[I]->dump());
           DEBUG(llvm::dbgs() << "  before ");
           DEBUG(Inst.dump());
           CFs[I]->moveBefore(&Inst);
         }
         Changed = true;

         foundPair = false;
         LIOfPair = nullptr;
       }

       if (auto CF = dyn_cast<CondFailInst>(&Inst)) {
         CFs.push_back(CF);
       } else if (auto LI = dyn_cast<LoadInst>(&Inst)) {
         if (addressIndependent(LI->getOperand())) {
           LIOfPair = LI;
         } else {
           CFs.clear();
           LIOfPair = nullptr;
         }
       } else if (auto SI = dyn_cast<StoreInst>(&Inst)) {
         if (addressIndependent(SI->getDest())) {
           if (LIOfPair &&
               addressCanPairUp(SI->getDest(), LIOfPair->getOperand()))
             foundPair = true;
         } else {
           CFs.clear();
           LIOfPair = nullptr;
         }
       } else if (Inst.mayHaveSideEffects()) {
         CFs.clear();
         LIOfPair = nullptr;
       }
     }
   }
   return Changed;
 }

 /// Checks if \p Inst has no side effects which prevent hoisting.
 /// The \a SafeReads set contain instructions which we already proved to have
 /// no such side effects.
 static bool hasNoSideEffect(SILInstruction *Inst, ReadSet &SafeReads) {
   // We can (and must) hoist cond_fail instructions if the operand is
   // invariant. We must hoist them so that we preserve memory safety. A
   // cond_fail that would have protected (executed before) a memory access
   // must - after hoisting - also be executed before said access.
   if (isa<CondFailInst>(Inst))
     return true;

   // Can't hoist if the instruction could read from memory and is not marked
   // as safe.
   if (SafeReads.count(Inst))
     return true;

   if (Inst->getMemoryBehavior() == SILInstruction::MemoryBehavior::None)
     return true;

   return false;
 }

 static bool canHoistInstruction(SILInstruction *Inst, SILLoop *Loop,
                                 ReadSet &SafeReads) {
   // Can't hoist terminators.
   if (isa<TermInst>(Inst))
     return false;

   // Can't hoist allocation and dealloc stacks.
   if (isa<AllocationInst>(Inst) || isa<DeallocStackInst>(Inst))
     return false;

   // Can't hoist instructions which may have side effects.
   if (!hasNoSideEffect(Inst, SafeReads))
     return false;

   // The operands need to be loop invariant.
   if (!hasLoopInvariantOperands(Inst, Loop)) {
     DEBUG(llvm::dbgs() << "   loop variant operands\n");
     return false;
   }

   return true;
 }

 static bool hoistInstructions(SILLoop *Loop, DominanceInfo *DT,
                               ReadSet &SafeReads, bool RunsOnHighLevelSil) {
   auto Preheader = Loop->getLoopPreheader();
   if (!Preheader)
     return false;

   DEBUG(llvm::dbgs() << " Hoisting instructions.\n");

   auto HeaderBB = Loop->getHeader();
   bool Changed = false;

   // Traverse the dominator tree starting at the loop header. Hoisting
   // instructions as we go.
   auto DTRoot = DT->getNode(HeaderBB);
   SmallVector<SILBasicBlock *, 8> ExitingBBs;
   Loop->getExitingBlocks(ExitingBBs);
   for (llvm::df_iterator<DominanceInfoNode *> It = llvm::df_begin(DTRoot),
                                               E = llvm::df_end(DTRoot);
        It != E;) {
     auto *CurBB = It->getBlock();

     // Don't decent into control-dependent code. Only traverse into basic blocks
     // that dominate all exits.
     if (!std::all_of(ExitingBBs.begin(), ExitingBBs.end(),
                      [=](SILBasicBlock *ExitBB) {
           if (DT->dominates(CurBB, ExitBB))
             return true;
           return false;
         })) {
       DEBUG(llvm::dbgs() << "  skipping conditional block " << *CurBB << "\n");
       It.skipChildren();
       continue;
     }

     // We now that the block is guaranteed to be executed. Hoist if we can.
     for (auto InstIt = CurBB->begin(), E = CurBB->end(); InstIt != E; ) {
       SILInstruction *Inst = &*InstIt;
       ++InstIt;
       DEBUG(llvm::dbgs() << "  looking at " << *Inst);
       if (canHoistInstruction(Inst, Loop, SafeReads)) {
         DEBUG(llvm::dbgs() << "   hoisting to preheader.\n");
         Changed = true;
         Inst->moveBefore(Preheader->getTerminator());
       } else if (RunsOnHighLevelSil) {
         ArraySemanticsCall semCall(Inst);
         switch (semCall.getKind()) {
         case ArrayCallKind::kGetCount:
         case ArrayCallKind::kGetCapacity:
           if (hasLoopInvariantOperands(Inst, Loop) &&
               semCall.canHoist(Preheader->getTerminator(), DT)) {
             Changed = true;
             semCall.hoist(Preheader->getTerminator(), DT);
           }
           break;
         default:
           break;
         }
       }
     }

     // Next block in dominator tree.
     ++It;
   }
   return Changed;
 }

 static bool sinkFixLifetime(SILLoop *Loop, DominanceInfo *DomTree,
                             SILLoopInfo *LI) {
   DEBUG(llvm::errs() << " Sink fix_lifetime attempt\n");
   auto Preheader = Loop->getLoopPreheader();
   if (!Preheader)
     return false;

   // Only handle innermost loops for now.
   if (!Loop->getSubLoops().empty())
     return false;

   // Only handle single exit blocks for now.
   auto *ExitBB = Loop->getExitBlock();
   if (!ExitBB)
     return false;
   auto *ExitingBB = Loop->getExitingBlock();
   if (!ExitingBB)
     return false;

   // We can sink fix_lifetime instructions if there are no reference counting
   // instructions in the loop.
   SmallVector<FixLifetimeInst *, 16> FixLifetimeInsts;
   for (auto *BB : Loop->getBlocks()) {
     for (auto &Inst : *BB) {
       if (auto FLI = dyn_cast<FixLifetimeInst>(&Inst)) {
         FixLifetimeInsts.push_back(FLI);
       } else if (Inst.mayHaveSideEffects() && !isa<LoadInst>(&Inst) &&
                  !isa<StoreInst>(&Inst)) {
         DEBUG(llvm::errs() << "  mayhavesideeffects because of" << Inst);
         DEBUG(Inst.getParent()->dump());
         return false;
       }
     }
   }

   // Sink the fix_lifetime instruction.
   bool Changed = false;
   for (auto *FLI : FixLifetimeInsts)
     if (DomTree->dominates(FLI->getOperand()->getParentBlock(),
                            Preheader)) {
       auto Succs = ExitingBB->getSuccessors();
       for (unsigned EdgeIdx = 0; EdgeIdx <  Succs.size(); ++EdgeIdx) {
         SILBasicBlock *BB = Succs[EdgeIdx];
         if (BB == ExitBB) {
           auto *SplitBB = splitCriticalEdge(ExitingBB->getTerminator(), EdgeIdx,
                                             DomTree, LI);
           auto *OutsideBB = SplitBB ? SplitBB : ExitBB;
           // Update the ExitBB.
           ExitBB = OutsideBB;
           DEBUG(llvm::errs() << "  moving fix_lifetime to exit BB " << *FLI);
           FLI->moveBefore(&*OutsideBB->begin());
           Changed = true;
         }
       }
     } else {
       DEBUG(llvm::errs() << "  does not dominate " << *FLI);
     }

   return Changed;
 }

 namespace {
 /// \brief Summary of may writes occurring in the loop tree rooted at \p
 /// Loop. This includes all writes of the sub loops and the loop itself.
 struct LoopNestSummary {
   SILLoop *Loop;
   WriteSet MayWrites;

   LoopNestSummary(SILLoop *Curr) : Loop(Curr) {}


   void copySummary(LoopNestSummary &Other) {
     MayWrites.append(Other.MayWrites.begin(), Other.MayWrites.end());
   }

   LoopNestSummary(const LoopNestSummary &) = delete;
   LoopNestSummary &operator=(const LoopNestSummary &) = delete;
   LoopNestSummary(LoopNestSummary &&) = delete;
 };

 /// \brief Optimize the loop tree bottom up propagating loop's summaries up the
 /// loop tree.
 class LoopTreeOptimization {
   llvm::DenseMap<SILLoop *, std::unique_ptr<LoopNestSummary>>
       LoopNestSummaryMap;
   SmallVector<SILLoop *, 8> BotUpWorkList;
   SILLoopInfo *LoopInfo;
   AliasAnalysis *AA;
   SideEffectAnalysis *SEA;
   DominanceInfo *DomTree;
   bool Changed;

   /// True if LICM is done on high-level SIL, i.e. semantic calls are not
   /// inlined yet. In this case some semantic calls can be hoisted.
   bool RunsOnHighLevelSil;

 public:
   LoopTreeOptimization(SILLoop *TopLevelLoop, SILLoopInfo *LI,
                        AliasAnalysis *AA, SideEffectAnalysis *SEA,
                        DominanceInfo *DT,
                        bool RunsOnHighLevelSil)
       : LoopInfo(LI), AA(AA), SEA(SEA), DomTree(DT), Changed(false),
         RunsOnHighLevelSil(RunsOnHighLevelSil) {
     // Collect loops for a recursive bottom-up traversal in the loop tree.
     BotUpWorkList.push_back(TopLevelLoop);
     for (unsigned i = 0; i < BotUpWorkList.size(); ++i) {
       auto *L = BotUpWorkList[i];
       for (auto *SubLoop : *L)
         BotUpWorkList.push_back(SubLoop);
     }
   }

   /// \brief Optimize this loop tree.
   bool optimize();

 protected:
   /// \brief Propagate the sub-loops' summaries up to the current loop.
   void propagateSummaries(std::unique_ptr<LoopNestSummary> &CurrSummary);

   /// \brief Collect a set of reads that can be hoisted to the loop's preheader.
   void analyzeCurrentLoop(std::unique_ptr<LoopNestSummary> &CurrSummary,
                           ReadSet &SafeReads);

   /// \brief Optimize the current loop nest.
   void optimizeLoop(SILLoop *CurrentLoop, ReadSet &SafeReads);
 };
 } // end anonymous namespace

 bool LoopTreeOptimization::optimize() {
   // Process loops bottom up in the loop tree.
   while (!BotUpWorkList.empty()) {
     SILLoop *CurrentLoop = BotUpWorkList.pop_back_val();
     DEBUG(llvm::dbgs() << "Processing loop " << *CurrentLoop);

     // Collect all summary of all sub loops of the current loop. Since we
     // process the loop tree bottom up they are guaranteed to be available in
     // the map.
     auto CurrLoopSummary = llvm::make_unique<LoopNestSummary>(CurrentLoop);
     propagateSummaries(CurrLoopSummary);

     // Analyze the current loop for reads that can be hoisted.
     ReadSet SafeReads;
     analyzeCurrentLoop(CurrLoopSummary, SafeReads);

     optimizeLoop(CurrentLoop, SafeReads);

     // Store the summary for parent loops to use.
     LoopNestSummaryMap[CurrentLoop] = std::move(CurrLoopSummary);
   }
   return Changed;
 }

 void LoopTreeOptimization::propagateSummaries(
     std::unique_ptr<LoopNestSummary> &CurrSummary) {
   for (auto *SubLoop : *CurrSummary->Loop) {
     assert(LoopNestSummaryMap.count(SubLoop) && "Must have data for sub loops");
     CurrSummary->copySummary(*LoopNestSummaryMap[SubLoop]);
     LoopNestSummaryMap.erase(SubLoop);
   }
 }

 void LoopTreeOptimization::analyzeCurrentLoop(
     std::unique_ptr<LoopNestSummary> &CurrSummary, ReadSet &SafeReads) {
   WriteSet &MayWrites = CurrSummary->MayWrites;
   SILLoop *Loop = CurrSummary->Loop;
   DEBUG(llvm::dbgs() << " Analyzing accesses.\n");

   // Contains function calls in the loop, which only read from memory.
   SmallVector<ApplyInst *, 8> ReadOnlyApplies;

   for (auto *BB : Loop->getBlocks()) {
     for (auto &Inst : *BB) {
       // Ignore fix_lifetime instructions.
       if (isa<FixLifetimeInst>(&Inst))
         continue;

       // Collect loads.
       auto LI = dyn_cast<LoadInst>(&Inst);
       if (LI) {
         if (!mayWriteTo(AA, MayWrites, LI))
           SafeReads.insert(LI);
         continue;
       }
       if (auto *AI = dyn_cast<ApplyInst>(&Inst)) {
         // In contrast to load instructions, we first collect all read-only
         // function calls and add them later to SafeReads.
         SideEffectAnalysis::FunctionEffects E;
         SEA->getEffects(E, AI);

         auto MB = E.getMemBehavior(RetainObserveKind::ObserveRetains);
         if (MB <= SILInstruction::MemoryBehavior::MayRead)
           ReadOnlyApplies.push_back(AI);
       }
       if (Inst.mayHaveSideEffects()) {
         MayWrites.push_back(&Inst);
         // Remove clobbered loads we have seen before.
         removeWrittenTo(AA, SafeReads, &Inst);
       }
     }
   }
   for (auto *AI : ReadOnlyApplies) {
     if (!mayWriteTo(AA, SEA, MayWrites, AI))
       SafeReads.insert(AI);
   }
 }

 void LoopTreeOptimization::optimizeLoop(SILLoop *CurrentLoop,
                                         ReadSet &SafeReads) {
   Changed |= sinkCondFail(CurrentLoop);
   Changed |= hoistInstructions(CurrentLoop, DomTree, SafeReads,
                                RunsOnHighLevelSil);
   Changed |= sinkFixLifetime(CurrentLoop, DomTree, LoopInfo);
 }

 namespace {
 /// Hoist loop invariant code out of innermost loops.
 class LICM : public SILFunctionTransform {

 public:
   LICM(bool RunsOnHighLevelSil) : RunsOnHighLevelSil(RunsOnHighLevelSil) {}

   /// True if LICM is done on high-level SIL, i.e. semantic calls are not
   /// inlined yet. In this case some semantic calls can be hoisted.
   /// We only hoist semantic calls on high-level SIL because we can be sure that
   /// e.g. an Array as SILValue is really immutable (including its content).
   bool RunsOnHighLevelSil;

   StringRef getName() override {
     return RunsOnHighLevelSil ? "High-level Loop Invariant Code Motion" :
                                 "Loop Invariant Code Motion";
   }

   void run() override {
     SILFunction *F = getFunction();
     SILLoopAnalysis *LA = PM->getAnalysis<SILLoopAnalysis>();
     SILLoopInfo *LoopInfo = LA->get(F);

     if (LoopInfo->empty()) {
       DEBUG(llvm::dbgs() << "No loops in " << F->getName() << "\n");
       return;
     }

     DominanceAnalysis *DA = PM->getAnalysis<DominanceAnalysis>();
     AliasAnalysis *AA = PM->getAnalysis<AliasAnalysis>();
     SideEffectAnalysis *SEA = PM->getAnalysis<SideEffectAnalysis>();
     DominanceInfo *DomTree = nullptr;

     DEBUG(llvm::dbgs() << "Processing loops in " << F->getName() << "\n");
     bool Changed = false;

     for (auto *TopLevelLoop : *LoopInfo) {
       if (!DomTree) DomTree = DA->get(F);
       LoopTreeOptimization Opt(TopLevelLoop, LoopInfo, AA, SEA, DomTree,
                                RunsOnHighLevelSil);
       Changed |= Opt.optimize();
     }

     if (Changed) {
       LA->lockInvalidation();
       DA->lockInvalidation();
       PM->invalidateAnalysis(F, SILAnalysis::InvalidationKind::FunctionBody);
       LA->unlockInvalidation();
       DA->unlockInvalidation();
     }
   }
 };
 } // end anonymous namespace

 SILTransform *swift::createLICM() {
   return new LICM(false);
 }

 SILTransform *swift::createHighLevelLICM() {
   return new LICM(true);
 }
	//===--- LICM.cpp - Loop invariant code motion ----------------------------===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See https://swift.org/LICENSE.txt for license information
	// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//

	#define DEBUG_TYPE "sil-licm"

	#include "swift/SIL/Dominance.h"
	#include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
	#include "swift/SILOptimizer/Analysis/Analysis.h"
	#include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
	#include "swift/SILOptimizer/Analysis/LoopAnalysis.h"
	#include "swift/SILOptimizer/Analysis/ArraySemantic.h"
	#include "swift/SILOptimizer/Analysis/SideEffectAnalysis.h"
	#include "swift/SILOptimizer/PassManager/Passes.h"
	#include "swift/SILOptimizer/PassManager/Transforms.h"
	#include "swift/SILOptimizer/Utils/CFG.h"
	#include "swift/SILOptimizer/Utils/SILSSAUpdater.h"
	#include "swift/SILOptimizer/Utils/Local.h"
	#include "swift/SIL/SILArgument.h"
	#include "swift/SIL/SILBuilder.h"
	#include "swift/SIL/SILInstruction.h"
	#include "swift/SIL/InstructionUtils.h"

	#include "llvm/ADT/DepthFirstIterator.h"
	#include "llvm/ADT/SmallPtrSet.h"
	#include "llvm/Support/Debug.h"

	#include "llvm/Support/CommandLine.h"

	using namespace swift;

	/// Instructions which read from memory, e.g. loads, or function calls without
	/// side effects.
	using ReadSet = llvm::SmallPtrSet<SILInstruction *, 8>;

	/// Instructions which (potentially) write memory.
	using WriteSet = SmallVector<SILInstruction *, 8>;

	/// Returns true if the \p MayWrites set contains any memory writes which may
	/// alias with the memory addressed by \a LI.
	static bool mayWriteTo(AliasAnalysis AA, WriteSet &MayWrites, LoadInst LI) {
	for (auto *W : MayWrites)
	if (AA->mayWriteToMemory(W, LI->getOperand())) {
	DEBUG(llvm::dbgs() << " mayWriteTo\n" << W << " to " << LI << "\n");
	return true;
	}
	return false;
	}

	/// Returns true if the \p MayWrites set contains any memory writes which may
	/// alias with any memory which is read by \p AI.
	static bool mayWriteTo(AliasAnalysis AA, SideEffectAnalysis SEA,
	WriteSet &MayWrites, ApplyInst *AI) {
	SideEffectAnalysis::FunctionEffects E;
	SEA->getEffects(E, AI);
	assert(E.getMemBehavior(RetainObserveKind::IgnoreRetains) <=
	SILInstruction::MemoryBehavior::MayRead &&
	"apply should only read from memory");
	if (E.getGlobalEffects().mayRead() && !MayWrites.empty()) {
	// We don't know which memory is read in the callee. Therefore we bail if
	// there are any writes in the loop.
	return true;
	}

	for (unsigned Idx = 0, End = AI->getNumArguments(); Idx < End; ++Idx) {
	auto &ArgEffect = E.getParameterEffects()[Idx];
	if (!ArgEffect.mayRead())
	continue;

	SILValue Arg = AI->getArgument(Idx);

	// Check if the memory addressed by the argument may alias any writes.
	for (auto *W : MayWrites) {
	if (AA->mayWriteToMemory(W, Arg)) {
	DEBUG(llvm::dbgs() << " mayWriteTo\n" << W << " to " << AI << "\n");
	return true;
	}
	}
	}
	return false;
	}

	static void removeWrittenTo(AliasAnalysis *AA, ReadSet &Reads,
	SILInstruction *ByInst) {

	// We can ignore retains, cond_fails, and dealloc_stacks.
	if (isa<StrongRetainInst>(ByInst) \|\| isa<RetainValueInst>(ByInst) \|\|
	isa<CondFailInst>(ByInst) \|\| isa<DeallocStackInst>(ByInst))
	return;

	SmallVector<SILInstruction *, 8> RS(Reads.begin(), Reads.end());
	for (auto R : RS) {
	auto *LI = dyn_cast<LoadInst>(R);
	if (LI && !AA->mayWriteToMemory(ByInst, LI->getOperand()))
	continue;

	DEBUG(llvm::dbgs() << " mayWriteTo\n" << ByInst << " to " << R << "\n");
	Reads.erase(R);
	}
	}

	static bool hasLoopInvariantOperands(SILInstruction I, SILLoop L) {
	auto Opds = I->getAllOperands();

	return std::all_of(Opds.begin(), Opds.end(), [=](Operand &Op) {

	ValueBase *Def = Op.get();

	// Operand is defined outside the loop.
	if (auto *Inst = dyn_cast<SILInstruction>(Def))
	return !L->contains(Inst->getParent());
	if (auto *Arg = dyn_cast<SILArgument>(Def))
	return !L->contains(Arg->getParent());

	return false;
	});
	}

	/// Check if an address does not depend on other values in a basic block.
	static SILInstruction *addressIndependent(SILValue Addr) {
	Addr = stripCasts(Addr);
	if (GlobalAddrInst *SGAI = dyn_cast<GlobalAddrInst>(Addr))
	return SGAI;
	if (StructElementAddrInst *SEAI = dyn_cast<StructElementAddrInst>(Addr))
	return addressIndependent(SEAI->getOperand());
	return nullptr;
	}

	/// Check if two addresses can potentially access the same memory.
	/// For now, return true when both can be traced to the same global variable.
	static bool addressCanPairUp(SILValue Addr1, SILValue Addr2) {
	SILInstruction *Origin1 = addressIndependent(Addr1);
	return Origin1 && Origin1 == addressIndependent(Addr2);
	}

	/// Move cond_fail down if it can potentially help register promotion later.
	static bool sinkCondFail(SILLoop *Loop) {
	// Only handle innermost loops for now.
	if (!Loop->getSubLoops().empty())
	return false;

	bool Changed = false;
	for (auto *BB : Loop->getBlocks()) {
	// A list of CondFails that can be moved down.
	SmallVector<CondFailInst*, 4> CFs;
	// A pair of load and store that are independent of the CondFails and
	// can potentially access the same memory.
	LoadInst *LIOfPair = nullptr;
	bool foundPair = false;

	for (auto &Inst : *BB) {
	if (foundPair) {
	// Move CFs to right before Inst.
	for (unsigned I = 0, E = CFs.size(); I < E; I++) {
	DEBUG(llvm::dbgs() << "sinking cond_fail down ");
	DEBUG(CFs[I]->dump());
	DEBUG(llvm::dbgs() << " before ");
	DEBUG(Inst.dump());
	CFs[I]->moveBefore(&Inst);
	}
	Changed = true;

	foundPair = false;
	LIOfPair = nullptr;
	}

	if (auto CF = dyn_cast<CondFailInst>(&Inst)) {
	CFs.push_back(CF);
	} else if (auto LI = dyn_cast<LoadInst>(&Inst)) {
	if (addressIndependent(LI->getOperand())) {
	LIOfPair = LI;
	} else {
	CFs.clear();
	LIOfPair = nullptr;
	}
	} else if (auto SI = dyn_cast<StoreInst>(&Inst)) {
	if (addressIndependent(SI->getDest())) {
	if (LIOfPair &&
	addressCanPairUp(SI->getDest(), LIOfPair->getOperand()))
	foundPair = true;
	} else {
	CFs.clear();
	LIOfPair = nullptr;
	}
	} else if (Inst.mayHaveSideEffects()) {
	CFs.clear();
	LIOfPair = nullptr;
	}
	}
	}
	return Changed;
	}

	/// Checks if \p Inst has no side effects which prevent hoisting.
	/// The \a SafeReads set contain instructions which we already proved to have
	/// no such side effects.
	static bool hasNoSideEffect(SILInstruction *Inst, ReadSet &SafeReads) {
	// We can (and must) hoist cond_fail instructions if the operand is
	// invariant. We must hoist them so that we preserve memory safety. A
	// cond_fail that would have protected (executed before) a memory access
	// must - after hoisting - also be executed before said access.
	if (isa<CondFailInst>(Inst))
	return true;

	// Can't hoist if the instruction could read from memory and is not marked
	// as safe.
	if (SafeReads.count(Inst))
	return true;

	if (Inst->getMemoryBehavior() == SILInstruction::MemoryBehavior::None)
	return true;

	return false;
	}

	static bool canHoistInstruction(SILInstruction Inst, SILLoop Loop,
	ReadSet &SafeReads) {
	// Can't hoist terminators.
	if (isa<TermInst>(Inst))
	return false;

	// Can't hoist allocation and dealloc stacks.
	if (isa<AllocationInst>(Inst) \|\| isa<DeallocStackInst>(Inst))
	return false;

	// Can't hoist instructions which may have side effects.
	if (!hasNoSideEffect(Inst, SafeReads))
	return false;

	// The operands need to be loop invariant.
	if (!hasLoopInvariantOperands(Inst, Loop)) {
	DEBUG(llvm::dbgs() << " loop variant operands\n");
	return false;
	}

	return true;
	}

	static bool hoistInstructions(SILLoop Loop, DominanceInfo DT,
	ReadSet &SafeReads, bool RunsOnHighLevelSil) {
	auto Preheader = Loop->getLoopPreheader();
	if (!Preheader)
	return false;

	DEBUG(llvm::dbgs() << " Hoisting instructions.\n");

	auto HeaderBB = Loop->getHeader();
	bool Changed = false;

	// Traverse the dominator tree starting at the loop header. Hoisting
	// instructions as we go.
	auto DTRoot = DT->getNode(HeaderBB);
	SmallVector<SILBasicBlock *, 8> ExitingBBs;
	Loop->getExitingBlocks(ExitingBBs);
	for (llvm::df_iterator<DominanceInfoNode *> It = llvm::df_begin(DTRoot),
	E = llvm::df_end(DTRoot);
	It != E;) {
	auto *CurBB = It->getBlock();

	// Don't decent into control-dependent code. Only traverse into basic blocks
	// that dominate all exits.
	if (!std::all_of(ExitingBBs.begin(), ExitingBBs.end(),
	[=](SILBasicBlock *ExitBB) {
	if (DT->dominates(CurBB, ExitBB))
	return true;
	return false;
	})) {
	DEBUG(llvm::dbgs() << " skipping conditional block " << *CurBB << "\n");
	It.skipChildren();
	continue;
	}

	// We now that the block is guaranteed to be executed. Hoist if we can.
	for (auto InstIt = CurBB->begin(), E = CurBB->end(); InstIt != E; ) {
	SILInstruction Inst = &InstIt;
	++InstIt;
	DEBUG(llvm::dbgs() << " looking at " << *Inst);
	if (canHoistInstruction(Inst, Loop, SafeReads)) {
	DEBUG(llvm::dbgs() << " hoisting to preheader.\n");
	Changed = true;
	Inst->moveBefore(Preheader->getTerminator());
	} else if (RunsOnHighLevelSil) {
	ArraySemanticsCall semCall(Inst);
	switch (semCall.getKind()) {
	case ArrayCallKind::kGetCount:
	case ArrayCallKind::kGetCapacity:
	if (hasLoopInvariantOperands(Inst, Loop) &&
	semCall.canHoist(Preheader->getTerminator(), DT)) {
	Changed = true;
	semCall.hoist(Preheader->getTerminator(), DT);
	}
	break;
	default:
	break;
	}
	}
	}

	// Next block in dominator tree.
	++It;
	}
	return Changed;
	}

	static bool sinkFixLifetime(SILLoop Loop, DominanceInfo DomTree,
	SILLoopInfo *LI) {
	DEBUG(llvm::errs() << " Sink fix_lifetime attempt\n");
	auto Preheader = Loop->getLoopPreheader();
	if (!Preheader)
	return false;

	// Only handle innermost loops for now.
	if (!Loop->getSubLoops().empty())
	return false;

	// Only handle single exit blocks for now.
	auto *ExitBB = Loop->getExitBlock();
	if (!ExitBB)
	return false;
	auto *ExitingBB = Loop->getExitingBlock();
	if (!ExitingBB)
	return false;

	// We can sink fix_lifetime instructions if there are no reference counting
	// instructions in the loop.
	SmallVector<FixLifetimeInst *, 16> FixLifetimeInsts;
	for (auto *BB : Loop->getBlocks()) {
	for (auto &Inst : *BB) {
	if (auto FLI = dyn_cast<FixLifetimeInst>(&Inst)) {
	FixLifetimeInsts.push_back(FLI);
	} else if (Inst.mayHaveSideEffects() && !isa<LoadInst>(&Inst) &&
	!isa<StoreInst>(&Inst)) {
	DEBUG(llvm::errs() << " mayhavesideeffects because of" << Inst);
	DEBUG(Inst.getParent()->dump());
	return false;
	}
	}
	}

	// Sink the fix_lifetime instruction.
	bool Changed = false;
	for (auto *FLI : FixLifetimeInsts)
	if (DomTree->dominates(FLI->getOperand()->getParentBlock(),
	Preheader)) {
	auto Succs = ExitingBB->getSuccessors();
	for (unsigned EdgeIdx = 0; EdgeIdx < Succs.size(); ++EdgeIdx) {
	SILBasicBlock *BB = Succs[EdgeIdx];
	if (BB == ExitBB) {
	auto *SplitBB = splitCriticalEdge(ExitingBB->getTerminator(), EdgeIdx,
	DomTree, LI);
	auto *OutsideBB = SplitBB ? SplitBB : ExitBB;
	// Update the ExitBB.
	ExitBB = OutsideBB;
	DEBUG(llvm::errs() << " moving fix_lifetime to exit BB " << *FLI);
	FLI->moveBefore(&*OutsideBB->begin());
	Changed = true;
	}
	}
	} else {
	DEBUG(llvm::errs() << " does not dominate " << *FLI);
	}

	return Changed;
	}

	namespace {
	/// \brief Summary of may writes occurring in the loop tree rooted at \p
	/// Loop. This includes all writes of the sub loops and the loop itself.
	struct LoopNestSummary {
	SILLoop *Loop;
	WriteSet MayWrites;

	LoopNestSummary(SILLoop *Curr) : Loop(Curr) {}


	void copySummary(LoopNestSummary &Other) {
	MayWrites.append(Other.MayWrites.begin(), Other.MayWrites.end());
	}

	LoopNestSummary(const LoopNestSummary &) = delete;
	LoopNestSummary &operator=(const LoopNestSummary &) = delete;
	LoopNestSummary(LoopNestSummary &&) = delete;
	};

	/// \brief Optimize the loop tree bottom up propagating loop's summaries up the
	/// loop tree.
	class LoopTreeOptimization {
	llvm::DenseMap<SILLoop *, std::unique_ptr<LoopNestSummary>>
	LoopNestSummaryMap;
	SmallVector<SILLoop *, 8> BotUpWorkList;
	SILLoopInfo *LoopInfo;
	AliasAnalysis *AA;
	SideEffectAnalysis *SEA;
	DominanceInfo *DomTree;
	bool Changed;

	/// True if LICM is done on high-level SIL, i.e. semantic calls are not
	/// inlined yet. In this case some semantic calls can be hoisted.
	bool RunsOnHighLevelSil;

	public:
	LoopTreeOptimization(SILLoop TopLevelLoop, SILLoopInfo LI,
	AliasAnalysis AA, SideEffectAnalysis SEA,
	DominanceInfo *DT,
	bool RunsOnHighLevelSil)
	: LoopInfo(LI), AA(AA), SEA(SEA), DomTree(DT), Changed(false),
	RunsOnHighLevelSil(RunsOnHighLevelSil) {
	// Collect loops for a recursive bottom-up traversal in the loop tree.
	BotUpWorkList.push_back(TopLevelLoop);
	for (unsigned i = 0; i < BotUpWorkList.size(); ++i) {
	auto *L = BotUpWorkList[i];
	for (auto SubLoop : L)
	BotUpWorkList.push_back(SubLoop);
	}
	}

	/// \brief Optimize this loop tree.
	bool optimize();

	protected:
	/// \brief Propagate the sub-loops' summaries up to the current loop.
	void propagateSummaries(std::unique_ptr<LoopNestSummary> &CurrSummary);

	/// \brief Collect a set of reads that can be hoisted to the loop's preheader.
	void analyzeCurrentLoop(std::unique_ptr<LoopNestSummary> &CurrSummary,
	ReadSet &SafeReads);

	/// \brief Optimize the current loop nest.
	void optimizeLoop(SILLoop *CurrentLoop, ReadSet &SafeReads);
	};
	} // end anonymous namespace

	bool LoopTreeOptimization::optimize() {
	// Process loops bottom up in the loop tree.
	while (!BotUpWorkList.empty()) {
	SILLoop *CurrentLoop = BotUpWorkList.pop_back_val();
	DEBUG(llvm::dbgs() << "Processing loop " << *CurrentLoop);

	// Collect all summary of all sub loops of the current loop. Since we
	// process the loop tree bottom up they are guaranteed to be available in
	// the map.
	auto CurrLoopSummary = llvm::make_unique<LoopNestSummary>(CurrentLoop);
	propagateSummaries(CurrLoopSummary);

	// Analyze the current loop for reads that can be hoisted.
	ReadSet SafeReads;
	analyzeCurrentLoop(CurrLoopSummary, SafeReads);

	optimizeLoop(CurrentLoop, SafeReads);

	// Store the summary for parent loops to use.
	LoopNestSummaryMap[CurrentLoop] = std::move(CurrLoopSummary);
	}
	return Changed;
	}

	void LoopTreeOptimization::propagateSummaries(
	std::unique_ptr<LoopNestSummary> &CurrSummary) {
	for (auto SubLoop : CurrSummary->Loop) {
	assert(LoopNestSummaryMap.count(SubLoop) && "Must have data for sub loops");
	CurrSummary->copySummary(*LoopNestSummaryMap[SubLoop]);
	LoopNestSummaryMap.erase(SubLoop);
	}
	}

	void LoopTreeOptimization::analyzeCurrentLoop(
	std::unique_ptr<LoopNestSummary> &CurrSummary, ReadSet &SafeReads) {
	WriteSet &MayWrites = CurrSummary->MayWrites;
	SILLoop *Loop = CurrSummary->Loop;
	DEBUG(llvm::dbgs() << " Analyzing accesses.\n");

	// Contains function calls in the loop, which only read from memory.
	SmallVector<ApplyInst *, 8> ReadOnlyApplies;

	for (auto *BB : Loop->getBlocks()) {
	for (auto &Inst : *BB) {
	// Ignore fix_lifetime instructions.
	if (isa<FixLifetimeInst>(&Inst))
	continue;

	// Collect loads.
	auto LI = dyn_cast<LoadInst>(&Inst);
	if (LI) {
	if (!mayWriteTo(AA, MayWrites, LI))
	SafeReads.insert(LI);
	continue;
	}
	if (auto *AI = dyn_cast<ApplyInst>(&Inst)) {
	// In contrast to load instructions, we first collect all read-only
	// function calls and add them later to SafeReads.
	SideEffectAnalysis::FunctionEffects E;
	SEA->getEffects(E, AI);

	auto MB = E.getMemBehavior(RetainObserveKind::ObserveRetains);
	if (MB <= SILInstruction::MemoryBehavior::MayRead)
	ReadOnlyApplies.push_back(AI);
	}
	if (Inst.mayHaveSideEffects()) {
	MayWrites.push_back(&Inst);
	// Remove clobbered loads we have seen before.
	removeWrittenTo(AA, SafeReads, &Inst);
	}
	}
	}
	for (auto *AI : ReadOnlyApplies) {
	if (!mayWriteTo(AA, SEA, MayWrites, AI))
	SafeReads.insert(AI);
	}
	}

	void LoopTreeOptimization::optimizeLoop(SILLoop *CurrentLoop,
	ReadSet &SafeReads) {
	Changed \|= sinkCondFail(CurrentLoop);
	Changed \|= hoistInstructions(CurrentLoop, DomTree, SafeReads,
	RunsOnHighLevelSil);
	Changed \|= sinkFixLifetime(CurrentLoop, DomTree, LoopInfo);
	}

	namespace {
	/// Hoist loop invariant code out of innermost loops.
	class LICM : public SILFunctionTransform {

	public:
	LICM(bool RunsOnHighLevelSil) : RunsOnHighLevelSil(RunsOnHighLevelSil) {}

	/// True if LICM is done on high-level SIL, i.e. semantic calls are not
	/// inlined yet. In this case some semantic calls can be hoisted.
	/// We only hoist semantic calls on high-level SIL because we can be sure that
	/// e.g. an Array as SILValue is really immutable (including its content).
	bool RunsOnHighLevelSil;

	StringRef getName() override {
	return RunsOnHighLevelSil ? "High-level Loop Invariant Code Motion" :
	"Loop Invariant Code Motion";
	}

	void run() override {
	SILFunction *F = getFunction();
	SILLoopAnalysis *LA = PM->getAnalysis<SILLoopAnalysis>();
	SILLoopInfo *LoopInfo = LA->get(F);

	if (LoopInfo->empty()) {
	DEBUG(llvm::dbgs() << "No loops in " << F->getName() << "\n");
	return;
	}

	DominanceAnalysis *DA = PM->getAnalysis<DominanceAnalysis>();
	AliasAnalysis *AA = PM->getAnalysis<AliasAnalysis>();
	SideEffectAnalysis *SEA = PM->getAnalysis<SideEffectAnalysis>();
	DominanceInfo *DomTree = nullptr;

	DEBUG(llvm::dbgs() << "Processing loops in " << F->getName() << "\n");
	bool Changed = false;

	for (auto TopLevelLoop : LoopInfo) {
	if (!DomTree) DomTree = DA->get(F);
	LoopTreeOptimization Opt(TopLevelLoop, LoopInfo, AA, SEA, DomTree,
	RunsOnHighLevelSil);
	Changed \|= Opt.optimize();
	}

	if (Changed) {
	LA->lockInvalidation();
	DA->lockInvalidation();
	PM->invalidateAnalysis(F, SILAnalysis::InvalidationKind::FunctionBody);
	LA->unlockInvalidation();
	DA->unlockInvalidation();
	}
	}
	};
	} // end anonymous namespace

	SILTransform *swift::createLICM() {
	return new LICM(false);
	}

	SILTransform *swift::createHighLevelLICM() {
	return new LICM(true);
	}