diff --git a/llvm/include/llvm-c/Transforms/Scalar.h b/llvm/include/llvm-c/Transforms/Scalar.h --- a/llvm/include/llvm-c/Transforms/Scalar.h +++ b/llvm/include/llvm-c/Transforms/Scalar.h @@ -94,9 +94,6 @@ /** See llvm::createLoopUnrollAndJamPass function. */ void LLVMAddLoopUnrollAndJamPass(LLVMPassManagerRef PM); -/** See llvm::createLoopUnswitchPass function. */ -void LLVMAddLoopUnswitchPass(LLVMPassManagerRef PM); - /** See llvm::createLowerAtomicPass function. */ void LLVMAddLowerAtomicPass(LLVMPassManagerRef PM); diff --git a/llvm/include/llvm/LinkAllPasses.h b/llvm/include/llvm/LinkAllPasses.h --- a/llvm/include/llvm/LinkAllPasses.h +++ b/llvm/include/llvm/LinkAllPasses.h @@ -133,7 +133,6 @@ (void) llvm::createLoopRerollPass(); (void) llvm::createLoopUnrollPass(); (void) llvm::createLoopUnrollAndJamPass(); - (void) llvm::createLoopUnswitchPass(); (void) llvm::createLoopVersioningLICMPass(); (void) llvm::createLoopIdiomPass(); (void) llvm::createLoopRotatePass(); diff --git a/llvm/include/llvm/Transforms/Scalar.h b/llvm/include/llvm/Transforms/Scalar.h --- a/llvm/include/llvm/Transforms/Scalar.h +++ b/llvm/include/llvm/Transforms/Scalar.h @@ -169,13 +169,6 @@ // Pass *createLoopStrengthReducePass(); -//===----------------------------------------------------------------------===// -// -// LoopUnswitch - This pass is a simple loop unswitching pass. -// -Pass *createLoopUnswitchPass(bool OptimizeForSize = false, - bool hasBranchDivergence = false); - //===----------------------------------------------------------------------===// // // LoopInstSimplify - This pass simplifies instructions in a loop's body. diff --git a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp --- a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp +++ b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -130,11 +130,6 @@ cl::Hidden, cl::desc("Disable shrink-wrap library calls")); -static cl::opt EnableSimpleLoopUnswitch( - "enable-simple-loop-unswitch", cl::init(false), cl::Hidden, - cl::desc("Enable the simple loop unswitch pass. Also enables independent " - "cleanup passes integrated into the loop pass manager pipeline.")); - cl::opt EnableGVNSink("enable-gvn-sink", cl::init(false), cl::ZeroOrMore, cl::desc("Enable the GVN sinking pass (default = off)")); @@ -382,13 +377,13 @@ MPM.add(createVectorCombinePass()); // Begin the loop pass pipeline. - if (EnableSimpleLoopUnswitch) { - // The simple loop unswitch pass relies on separate cleanup passes. Schedule - // them first so when we re-process a loop they run before other loop - // passes. - MPM.add(createLoopInstSimplifyPass()); - MPM.add(createLoopSimplifyCFGPass()); - } + + // The simple loop unswitch pass relies on separate cleanup passes. Schedule + // them first so when we re-process a loop they run before other loop + // passes. + MPM.add(createLoopInstSimplifyPass()); + MPM.add(createLoopSimplifyCFGPass()); + // Try to remove as much code from the loop header as possible, // to reduce amount of IR that will have to be duplicated. However, // do not perform speculative hoisting the first time as LICM @@ -402,10 +397,7 @@ // TODO: Investigate promotion cap for O1. MPM.add(createLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap, /*AllowSpeculation=*/true)); - if (EnableSimpleLoopUnswitch) - MPM.add(createSimpleLoopUnswitchLegacyPass()); - else - MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3, DivergentTarget)); + MPM.add(createSimpleLoopUnswitchLegacyPass(OptLevel == 3)); // FIXME: We break the loop pass pipeline here in order to do full // simplifycfg. Eventually loop-simplifycfg should be enhanced to replace the // need for this. @@ -528,7 +520,7 @@ PM.add(createInstructionCombiningPass()); PM.add(createLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap, /*AllowSpeculation=*/true)); - PM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3, DivergentTarget)); + PM.add(createSimpleLoopUnswitchLegacyPass()); PM.add(createCFGSimplificationPass( SimplifyCFGOptions().convertSwitchRangeToICmp(true))); PM.add(createInstructionCombiningPass()); diff --git a/llvm/lib/Transforms/Scalar/CMakeLists.txt b/llvm/lib/Transforms/Scalar/CMakeLists.txt --- a/llvm/lib/Transforms/Scalar/CMakeLists.txt +++ b/llvm/lib/Transforms/Scalar/CMakeLists.txt @@ -45,7 +45,6 @@ LoopStrengthReduce.cpp LoopUnrollPass.cpp LoopUnrollAndJamPass.cpp - LoopUnswitch.cpp LoopVersioningLICM.cpp LowerAtomicPass.cpp LowerConstantIntrinsics.cpp diff --git a/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp deleted file mode 100644 --- a/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp +++ /dev/null @@ -1,1772 +0,0 @@ -//===- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop -------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// This pass transforms loops that contain branches on loop-invariant conditions -// to multiple loops. For example, it turns the left into the right code: -// -// for (...) if (lic) -// A for (...) -// if (lic) A; B; C -// B else -// C for (...) -// A; C -// -// This can increase the size of the code exponentially (doubling it every time -// a loop is unswitched) so we only unswitch if the resultant code will be -// smaller than a threshold. -// -// This pass expects LICM to be run before it to hoist invariant conditions out -// of the loop, to make the unswitching opportunity obvious. -// -//===----------------------------------------------------------------------===// - -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/AssumptionCache.h" -#include "llvm/Analysis/CodeMetrics.h" -#include "llvm/Analysis/DomTreeUpdater.h" -#include "llvm/Analysis/InstructionSimplify.h" -#include "llvm/Analysis/LazyBlockFrequencyInfo.h" -#include "llvm/Analysis/LegacyDivergenceAnalysis.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/LoopIterator.h" -#include "llvm/Analysis/LoopPass.h" -#include "llvm/Analysis/MemorySSA.h" -#include "llvm/Analysis/MemorySSAUpdater.h" -#include "llvm/Analysis/MustExecute.h" -#include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Analysis/TargetTransformInfo.h" -#include "llvm/IR/Attributes.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Constant.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/DerivedTypes.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Instruction.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/IntrinsicInst.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/Type.h" -#include "llvm/IR/User.h" -#include "llvm/IR/Value.h" -#include "llvm/IR/ValueHandle.h" -#include "llvm/InitializePasses.h" -#include "llvm/Pass.h" -#include "llvm/Support/Casting.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/Transforms/Utils/Cloning.h" -#include "llvm/Transforms/Utils/Local.h" -#include "llvm/Transforms/Utils/LoopUtils.h" -#include "llvm/Transforms/Utils/ValueMapper.h" -#include -#include -#include -#include -#include -#include - -using namespace llvm; - -#define DEBUG_TYPE "loop-unswitch" - -STATISTIC(NumBranches, "Number of branches unswitched"); -STATISTIC(NumSwitches, "Number of switches unswitched"); -STATISTIC(NumGuards, "Number of guards unswitched"); -STATISTIC(NumSelects , "Number of selects unswitched"); -STATISTIC(NumTrivial , "Number of unswitches that are trivial"); -STATISTIC(NumSimplify, "Number of simplifications of unswitched code"); -STATISTIC(TotalInsts, "Total number of instructions analyzed"); - -// The specific value of 100 here was chosen based only on intuition and a -// few specific examples. -static cl::opt -Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), - cl::init(100), cl::Hidden); - -static cl::opt - MSSAThreshold("loop-unswitch-memoryssa-threshold", - cl::desc("Max number of memory uses to explore during " - "partial unswitching analysis"), - cl::init(100), cl::Hidden); - -namespace { - - class LUAnalysisCache { - using UnswitchedValsMap = - DenseMap>; - using UnswitchedValsIt = UnswitchedValsMap::iterator; - - struct LoopProperties { - unsigned CanBeUnswitchedCount; - unsigned WasUnswitchedCount; - unsigned SizeEstimation; - UnswitchedValsMap UnswitchedVals; - }; - - // Here we use std::map instead of DenseMap, since we need to keep valid - // LoopProperties pointer for current loop for better performance. - using LoopPropsMap = std::map; - using LoopPropsMapIt = LoopPropsMap::iterator; - - LoopPropsMap LoopsProperties; - UnswitchedValsMap *CurLoopInstructions = nullptr; - LoopProperties *CurrentLoopProperties = nullptr; - - // A loop unswitching with an estimated cost above this threshold - // is not performed. MaxSize is turned into unswitching quota for - // the current loop, and reduced correspondingly, though note that - // the quota is returned by releaseMemory() when the loop has been - // processed, so that MaxSize will return to its previous - // value. So in most cases MaxSize will equal the Threshold flag - // when a new loop is processed. An exception to that is that - // MaxSize will have a smaller value while processing nested loops - // that were introduced due to loop unswitching of an outer loop. - // - // FIXME: The way that MaxSize works is subtle and depends on the - // pass manager processing loops and calling releaseMemory() in a - // specific order. It would be good to find a more straightforward - // way of doing what MaxSize does. - unsigned MaxSize; - - public: - LUAnalysisCache() : MaxSize(Threshold) {} - - // Analyze loop. Check its size, calculate is it possible to unswitch - // it. Returns true if we can unswitch this loop. - bool countLoop(const Loop *L, const TargetTransformInfo &TTI, - AssumptionCache *AC); - - // Clean all data related to given loop. - void forgetLoop(const Loop *L); - - // Mark case value as unswitched. - // Since SI instruction can be partly unswitched, in order to avoid - // extra unswitching in cloned loops keep track all unswitched values. - void setUnswitched(const SwitchInst *SI, const Value *V); - - // Check was this case value unswitched before or not. - bool isUnswitched(const SwitchInst *SI, const Value *V); - - // Returns true if another unswitching could be done within the cost - // threshold. - bool costAllowsUnswitching(); - - // Clone all loop-unswitch related loop properties. - // Redistribute unswitching quotas. - // Note, that new loop data is stored inside the VMap. - void cloneData(const Loop *NewLoop, const Loop *OldLoop, - const ValueToValueMapTy &VMap); - }; - - class LoopUnswitch : public LoopPass { - LoopInfo *LI; // Loop information - LPPassManager *LPM; - AssumptionCache *AC; - - // Used to check if second loop needs processing after - // rewriteLoopBodyWithConditionConstant rewrites first loop. - std::vector LoopProcessWorklist; - - LUAnalysisCache BranchesInfo; - - bool OptimizeForSize; - bool RedoLoop = false; - - Loop *CurrentLoop = nullptr; - DominatorTree *DT = nullptr; - MemorySSA *MSSA = nullptr; - AAResults *AA = nullptr; - std::unique_ptr MSSAU; - BasicBlock *LoopHeader = nullptr; - BasicBlock *LoopPreheader = nullptr; - - bool SanitizeMemory; - SimpleLoopSafetyInfo SafetyInfo; - - // LoopBlocks contains all of the basic blocks of the loop, including the - // preheader of the loop, the body of the loop, and the exit blocks of the - // loop, in that order. - std::vector LoopBlocks; - // NewBlocks contained cloned copy of basic blocks from LoopBlocks. - std::vector NewBlocks; - - bool HasBranchDivergence; - - public: - static char ID; // Pass ID, replacement for typeid - - explicit LoopUnswitch(bool Os = false, bool HasBranchDivergence = false) - : LoopPass(ID), OptimizeForSize(Os), - HasBranchDivergence(HasBranchDivergence) { - initializeLoopUnswitchPass(*PassRegistry::getPassRegistry()); - } - - bool runOnLoop(Loop *L, LPPassManager &LPM) override; - bool processCurrentLoop(); - bool isUnreachableDueToPreviousUnswitching(BasicBlock *); - - /// This transformation requires natural loop information & requires that - /// loop preheaders be inserted into the CFG. - /// - void getAnalysisUsage(AnalysisUsage &AU) const override { - // Lazy BFI and BPI are marked as preserved here so Loop Unswitching - // can remain part of the same loop pass as LICM - AU.addPreserved(); - AU.addPreserved(); - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); - AU.addPreserved(); - if (HasBranchDivergence) - AU.addRequired(); - getLoopAnalysisUsage(AU); - } - - private: - void releaseMemory() override { BranchesInfo.forgetLoop(CurrentLoop); } - - void initLoopData() { - LoopHeader = CurrentLoop->getHeader(); - LoopPreheader = CurrentLoop->getLoopPreheader(); - } - - /// Split all of the edges from inside the loop to their exit blocks. - /// Update the appropriate Phi nodes as we do so. - void splitExitEdges(Loop *L, - const SmallVectorImpl &ExitBlocks); - - bool tryTrivialLoopUnswitch(bool &Changed); - - bool unswitchIfProfitable(Value *LoopCond, Constant *Val, - Instruction *TI = nullptr, - ArrayRef ToDuplicate = {}); - void unswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, - BasicBlock *ExitBlock, Instruction *TI); - void unswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L, - Instruction *TI, - ArrayRef ToDuplicate = {}); - - void rewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, - Constant *Val, bool IsEqual); - - void - emitPreheaderBranchOnCondition(Value *LIC, Constant *Val, - BasicBlock *TrueDest, BasicBlock *FalseDest, - BranchInst *OldBranch, Instruction *TI, - ArrayRef ToDuplicate = {}); - - void simplifyCode(std::vector &Worklist, Loop *L); - - /// Given that the Invariant is not equal to Val. Simplify instructions - /// in the loop. - Value *simplifyInstructionWithNotEqual(Instruction *Inst, Value *Invariant, - Constant *Val); - }; - -} // end anonymous namespace - -// Analyze loop. Check its size, calculate is it possible to unswitch -// it. Returns true if we can unswitch this loop. -bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI, - AssumptionCache *AC) { - LoopPropsMapIt PropsIt; - bool Inserted; - std::tie(PropsIt, Inserted) = - LoopsProperties.insert(std::make_pair(L, LoopProperties())); - - LoopProperties &Props = PropsIt->second; - - if (Inserted) { - // New loop. - - // Limit the number of instructions to avoid causing significant code - // expansion, and the number of basic blocks, to avoid loops with - // large numbers of branches which cause loop unswitching to go crazy. - // This is a very ad-hoc heuristic. - - SmallPtrSet EphValues; - CodeMetrics::collectEphemeralValues(L, AC, EphValues); - - // FIXME: This is overly conservative because it does not take into - // consideration code simplification opportunities and code that can - // be shared by the resultant unswitched loops. - CodeMetrics Metrics; - for (BasicBlock *BB : L->blocks()) - Metrics.analyzeBasicBlock(BB, TTI, EphValues); - - Props.SizeEstimation = Metrics.NumInsts; - Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation); - Props.WasUnswitchedCount = 0; - MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount; - - if (Metrics.notDuplicatable) { - LLVM_DEBUG(dbgs() << "NOT unswitching loop %" << L->getHeader()->getName() - << ", contents cannot be " - << "duplicated!\n"); - return false; - } - } - - // Be careful. This links are good only before new loop addition. - CurrentLoopProperties = &Props; - CurLoopInstructions = &Props.UnswitchedVals; - - return true; -} - -// Clean all data related to given loop. -void LUAnalysisCache::forgetLoop(const Loop *L) { - LoopPropsMapIt LIt = LoopsProperties.find(L); - - if (LIt != LoopsProperties.end()) { - LoopProperties &Props = LIt->second; - MaxSize += (Props.CanBeUnswitchedCount + Props.WasUnswitchedCount) * - Props.SizeEstimation; - LoopsProperties.erase(LIt); - } - - CurrentLoopProperties = nullptr; - CurLoopInstructions = nullptr; -} - -// Mark case value as unswitched. -// Since SI instruction can be partly unswitched, in order to avoid -// extra unswitching in cloned loops keep track all unswitched values. -void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) { - (*CurLoopInstructions)[SI].insert(V); -} - -// Check was this case value unswitched before or not. -bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) { - return (*CurLoopInstructions)[SI].count(V); -} - -bool LUAnalysisCache::costAllowsUnswitching() { - return CurrentLoopProperties->CanBeUnswitchedCount > 0; -} - -// Clone all loop-unswitch related loop properties. -// Redistribute unswitching quotas. -// Note, that new loop data is stored inside the VMap. -void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop, - const ValueToValueMapTy &VMap) { - LoopProperties &NewLoopProps = LoopsProperties[NewLoop]; - LoopProperties &OldLoopProps = *CurrentLoopProperties; - UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals; - - // Reallocate "can-be-unswitched quota" - - --OldLoopProps.CanBeUnswitchedCount; - ++OldLoopProps.WasUnswitchedCount; - NewLoopProps.WasUnswitchedCount = 0; - unsigned Quota = OldLoopProps.CanBeUnswitchedCount; - NewLoopProps.CanBeUnswitchedCount = Quota / 2; - OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2; - - NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation; - - // Clone unswitched values info: - // for new loop switches we clone info about values that was - // already unswitched and has redundant successors. - for (const auto &I : Insts) { - const SwitchInst *OldInst = I.first; - Value *NewI = VMap.lookup(OldInst); - const SwitchInst *NewInst = cast_or_null(NewI); - assert(NewInst && "All instructions that are in SrcBB must be in VMap."); - - NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst]; - } -} - -char LoopUnswitch::ID = 0; - -INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops", - false, false) -INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) -INITIALIZE_PASS_DEPENDENCY(LoopPass) -INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) -INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis) -INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) -INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops", - false, false) - -Pass *llvm::createLoopUnswitchPass(bool Os, bool HasBranchDivergence) { - return new LoopUnswitch(Os, HasBranchDivergence); -} - -/// Operator chain lattice. -enum OperatorChain { - OC_OpChainNone, ///< There is no operator. - OC_OpChainOr, ///< There are only ORs. - OC_OpChainAnd, ///< There are only ANDs. - OC_OpChainMixed ///< There are ANDs and ORs. -}; - -/// Cond is a condition that occurs in L. If it is invariant in the loop, or has -/// an invariant piece, return the invariant. Otherwise, return null. -// -/// NOTE: findLIVLoopCondition will not return a partial LIV by walking up a -/// mixed operator chain, as we can not reliably find a value which will -/// simplify the operator chain. If the chain is AND-only or OR-only, we can use -/// 0 or ~0 to simplify the chain. -/// -/// NOTE: In case a partial LIV and a mixed operator chain, we may be able to -/// simplify the condition itself to a loop variant condition, but at the -/// cost of creating an entirely new loop. -static Value *findLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, - OperatorChain &ParentChain, - DenseMap &Cache, - MemorySSAUpdater *MSSAU) { - auto CacheIt = Cache.find(Cond); - if (CacheIt != Cache.end()) - return CacheIt->second; - - // We started analyze new instruction, increment scanned instructions counter. - ++TotalInsts; - - // We can never unswitch on vector conditions. - if (Cond->getType()->isVectorTy()) - return nullptr; - - // Constants should be folded, not unswitched on! - if (isa(Cond)) return nullptr; - - // TODO: Handle: br (VARIANT|INVARIANT). - - // Hoist simple values out. - if (L->makeLoopInvariant(Cond, Changed, nullptr, MSSAU)) { - Cache[Cond] = Cond; - return Cond; - } - - // Walk up the operator chain to find partial invariant conditions. - if (BinaryOperator *BO = dyn_cast(Cond)) - if (BO->getOpcode() == Instruction::And || - BO->getOpcode() == Instruction::Or) { - // Given the previous operator, compute the current operator chain status. - OperatorChain NewChain; - switch (ParentChain) { - case OC_OpChainNone: - NewChain = BO->getOpcode() == Instruction::And ? OC_OpChainAnd : - OC_OpChainOr; - break; - case OC_OpChainOr: - NewChain = BO->getOpcode() == Instruction::Or ? OC_OpChainOr : - OC_OpChainMixed; - break; - case OC_OpChainAnd: - NewChain = BO->getOpcode() == Instruction::And ? OC_OpChainAnd : - OC_OpChainMixed; - break; - case OC_OpChainMixed: - NewChain = OC_OpChainMixed; - break; - } - - // If we reach a Mixed state, we do not want to keep walking up as we can not - // reliably find a value that will simplify the chain. With this check, we - // will return null on the first sight of mixed chain and the caller will - // either backtrack to find partial LIV in other operand or return null. - if (NewChain != OC_OpChainMixed) { - // Update the current operator chain type before we search up the chain. - ParentChain = NewChain; - // If either the left or right side is invariant, we can unswitch on this, - // which will cause the branch to go away in one loop and the condition to - // simplify in the other one. - if (Value *LHS = findLIVLoopCondition(BO->getOperand(0), L, Changed, - ParentChain, Cache, MSSAU)) { - Cache[Cond] = LHS; - return LHS; - } - // We did not manage to find a partial LIV in operand(0). Backtrack and try - // operand(1). - ParentChain = NewChain; - if (Value *RHS = findLIVLoopCondition(BO->getOperand(1), L, Changed, - ParentChain, Cache, MSSAU)) { - Cache[Cond] = RHS; - return RHS; - } - } - } - - Cache[Cond] = nullptr; - return nullptr; -} - -/// Cond is a condition that occurs in L. If it is invariant in the loop, or has -/// an invariant piece, return the invariant along with the operator chain type. -/// Otherwise, return null. -static std::pair -findLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, - MemorySSAUpdater *MSSAU) { - DenseMap Cache; - OperatorChain OpChain = OC_OpChainNone; - Value *FCond = findLIVLoopCondition(Cond, L, Changed, OpChain, Cache, MSSAU); - - // In case we do find a LIV, it can not be obtained by walking up a mixed - // operator chain. - assert((!FCond || OpChain != OC_OpChainMixed) && - "Do not expect a partial LIV with mixed operator chain"); - return {FCond, OpChain}; -} - -bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPMRef) { - if (skipLoop(L)) - return false; - - AC = &getAnalysis().getAssumptionCache( - *L->getHeader()->getParent()); - LI = &getAnalysis().getLoopInfo(); - LPM = &LPMRef; - DT = &getAnalysis().getDomTree(); - AA = &getAnalysis().getAAResults(); - MSSA = &getAnalysis().getMSSA(); - MSSAU = std::make_unique(MSSA); - CurrentLoop = L; - Function *F = CurrentLoop->getHeader()->getParent(); - - SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory); - if (SanitizeMemory) - SafetyInfo.computeLoopSafetyInfo(L); - - if (VerifyMemorySSA) - MSSA->verifyMemorySSA(); - - bool Changed = false; - do { - assert(CurrentLoop->isLCSSAForm(*DT)); - if (VerifyMemorySSA) - MSSA->verifyMemorySSA(); - RedoLoop = false; - Changed |= processCurrentLoop(); - } while (RedoLoop); - - if (VerifyMemorySSA) - MSSA->verifyMemorySSA(); - - return Changed; -} - -// Return true if the BasicBlock BB is unreachable from the loop header. -// Return false, otherwise. -bool LoopUnswitch::isUnreachableDueToPreviousUnswitching(BasicBlock *BB) { - auto *Node = DT->getNode(BB)->getIDom(); - BasicBlock *DomBB = Node->getBlock(); - while (CurrentLoop->contains(DomBB)) { - BranchInst *BInst = dyn_cast(DomBB->getTerminator()); - - Node = DT->getNode(DomBB)->getIDom(); - DomBB = Node->getBlock(); - - if (!BInst || !BInst->isConditional()) - continue; - - Value *Cond = BInst->getCondition(); - if (!isa(Cond)) - continue; - - BasicBlock *UnreachableSucc = - Cond == ConstantInt::getTrue(Cond->getContext()) - ? BInst->getSuccessor(1) - : BInst->getSuccessor(0); - - if (DT->dominates(UnreachableSucc, BB)) - return true; - } - return false; -} - -/// FIXME: Remove this workaround when freeze related patches are done. -/// LoopUnswitch and Equality propagation in GVN have discrepancy about -/// whether branch on undef/poison has undefine behavior. Here it is to -/// rule out some common cases that we found such discrepancy already -/// causing problems. Detail could be found in PR31652. Note if the -/// func returns true, it is unsafe. But if it is false, it doesn't mean -/// it is necessarily safe. -static bool equalityPropUnSafe(Value &LoopCond) { - ICmpInst *CI = dyn_cast(&LoopCond); - if (!CI || !CI->isEquality()) - return false; - - Value *LHS = CI->getOperand(0); - Value *RHS = CI->getOperand(1); - if (isa(LHS) || isa(RHS)) - return true; - - auto HasUndefInPHI = [](PHINode &PN) { - for (Value *Opd : PN.incoming_values()) { - if (isa(Opd)) - return true; - } - return false; - }; - PHINode *LPHI = dyn_cast(LHS); - PHINode *RPHI = dyn_cast(RHS); - if ((LPHI && HasUndefInPHI(*LPHI)) || (RPHI && HasUndefInPHI(*RPHI))) - return true; - - auto HasUndefInSelect = [](SelectInst &SI) { - if (isa(SI.getTrueValue()) || - isa(SI.getFalseValue())) - return true; - return false; - }; - SelectInst *LSI = dyn_cast(LHS); - SelectInst *RSI = dyn_cast(RHS); - if ((LSI && HasUndefInSelect(*LSI)) || (RSI && HasUndefInSelect(*RSI))) - return true; - return false; -} - -/// Do actual work and unswitch loop if possible and profitable. -bool LoopUnswitch::processCurrentLoop() { - bool Changed = false; - - initLoopData(); - - // If LoopSimplify was unable to form a preheader, don't do any unswitching. - if (!LoopPreheader) - return false; - - // Loops with indirectbr cannot be cloned. - if (!CurrentLoop->isSafeToClone()) - return false; - - // Without dedicated exits, splitting the exit edge may fail. - if (!CurrentLoop->hasDedicatedExits()) - return false; - - LLVMContext &Context = LoopHeader->getContext(); - - // Analyze loop cost, and stop unswitching if loop content can not be duplicated. - if (!BranchesInfo.countLoop( - CurrentLoop, - getAnalysis().getTTI( - *CurrentLoop->getHeader()->getParent()), - AC)) - return false; - - // Try trivial unswitch first before loop over other basic blocks in the loop. - if (tryTrivialLoopUnswitch(Changed)) { - return true; - } - - // Do not do non-trivial unswitch while optimizing for size. - // FIXME: Use Function::hasOptSize(). - if (OptimizeForSize || - LoopHeader->getParent()->hasFnAttribute(Attribute::OptimizeForSize)) - return Changed; - - // Run through the instructions in the loop, keeping track of three things: - // - // - That we do not unswitch loops containing convergent operations, as we - // might be making them control dependent on the unswitch value when they - // were not before. - // FIXME: This could be refined to only bail if the convergent operation is - // not already control-dependent on the unswitch value. - // - // - That basic blocks in the loop contain invokes whose predecessor edges we - // cannot split. - // - // - The set of guard intrinsics encountered (these are non terminator - // instructions that are also profitable to be unswitched). - - SmallVector Guards; - - for (const auto BB : CurrentLoop->blocks()) { - for (auto &I : *BB) { - auto *CB = dyn_cast(&I); - if (!CB) - continue; - if (CB->isConvergent()) - return Changed; - if (auto *II = dyn_cast(&I)) - if (!II->getUnwindDest()->canSplitPredecessors()) - return Changed; - if (auto *II = dyn_cast(&I)) - if (II->getIntrinsicID() == Intrinsic::experimental_guard) - Guards.push_back(II); - } - } - - for (IntrinsicInst *Guard : Guards) { - Value *LoopCond = findLIVLoopCondition(Guard->getOperand(0), CurrentLoop, - Changed, MSSAU.get()) - .first; - if (LoopCond && - unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) { - // NB! Unswitching (if successful) could have erased some of the - // instructions in Guards leaving dangling pointers there. This is fine - // because we're returning now, and won't look at Guards again. - ++NumGuards; - return true; - } - } - - // Loop over all of the basic blocks in the loop. If we find an interior - // block that is branching on a loop-invariant condition, we can unswitch this - // loop. - for (Loop::block_iterator I = CurrentLoop->block_begin(), - E = CurrentLoop->block_end(); - I != E; ++I) { - Instruction *TI = (*I)->getTerminator(); - - // Unswitching on a potentially uninitialized predicate is not - // MSan-friendly. Limit this to the cases when the original predicate is - // guaranteed to execute, to avoid creating a use-of-uninitialized-value - // in the code that did not have one. - // This is a workaround for the discrepancy between LLVM IR and MSan - // semantics. See PR28054 for more details. - if (SanitizeMemory && - !SafetyInfo.isGuaranteedToExecute(*TI, DT, CurrentLoop)) - continue; - - if (BranchInst *BI = dyn_cast(TI)) { - // Some branches may be rendered unreachable because of previous - // unswitching. - // Unswitch only those branches that are reachable. - if (isUnreachableDueToPreviousUnswitching(*I)) - continue; - - // If this isn't branching on an invariant condition, we can't unswitch - // it. - if (BI->isConditional()) { - // See if this, or some part of it, is loop invariant. If so, we can - // unswitch on it if we desire. - Value *LoopCond = findLIVLoopCondition(BI->getCondition(), CurrentLoop, - Changed, MSSAU.get()) - .first; - if (LoopCond && !equalityPropUnSafe(*LoopCond) && - unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) { - ++NumBranches; - return true; - } - } - } else if (SwitchInst *SI = dyn_cast(TI)) { - Value *SC = SI->getCondition(); - Value *LoopCond; - OperatorChain OpChain; - std::tie(LoopCond, OpChain) = - findLIVLoopCondition(SC, CurrentLoop, Changed, MSSAU.get()); - - unsigned NumCases = SI->getNumCases(); - if (LoopCond && NumCases) { - // Find a value to unswitch on: - // FIXME: this should chose the most expensive case! - // FIXME: scan for a case with a non-critical edge? - Constant *UnswitchVal = nullptr; - // Find a case value such that at least one case value is unswitched - // out. - if (OpChain == OC_OpChainAnd) { - // If the chain only has ANDs and the switch has a case value of 0. - // Dropping in a 0 to the chain will unswitch out the 0-casevalue. - auto *AllZero = cast(Constant::getNullValue(SC->getType())); - if (BranchesInfo.isUnswitched(SI, AllZero)) - continue; - // We are unswitching 0 out. - UnswitchVal = AllZero; - } else if (OpChain == OC_OpChainOr) { - // If the chain only has ORs and the switch has a case value of ~0. - // Dropping in a ~0 to the chain will unswitch out the ~0-casevalue. - auto *AllOne = cast(Constant::getAllOnesValue(SC->getType())); - if (BranchesInfo.isUnswitched(SI, AllOne)) - continue; - // We are unswitching ~0 out. - UnswitchVal = AllOne; - } else { - assert(OpChain == OC_OpChainNone && - "Expect to unswitch on trivial chain"); - // Do not process same value again and again. - // At this point we have some cases already unswitched and - // some not yet unswitched. Let's find the first not yet unswitched one. - for (auto Case : SI->cases()) { - Constant *UnswitchValCandidate = Case.getCaseValue(); - if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) { - UnswitchVal = UnswitchValCandidate; - break; - } - } - } - - if (!UnswitchVal) - continue; - - if (unswitchIfProfitable(LoopCond, UnswitchVal)) { - ++NumSwitches; - // In case of a full LIV, UnswitchVal is the value we unswitched out. - // In case of a partial LIV, we only unswitch when its an AND-chain - // or OR-chain. In both cases switch input value simplifies to - // UnswitchVal. - BranchesInfo.setUnswitched(SI, UnswitchVal); - return true; - } - } - } - - // Scan the instructions to check for unswitchable values. - for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end(); - BBI != E; ++BBI) - if (SelectInst *SI = dyn_cast(BBI)) { - Value *LoopCond = findLIVLoopCondition(SI->getCondition(), CurrentLoop, - Changed, MSSAU.get()) - .first; - if (LoopCond && - unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) { - ++NumSelects; - return true; - } - } - } - - // Check if there is a header condition that is invariant along the patch from - // either the true or false successors to the header. This allows unswitching - // conditions depending on memory accesses, if there's a path not clobbering - // the memory locations. Check if this transform has been disabled using - // metadata, to avoid unswitching the same loop multiple times. - if (MSSA && - !findOptionMDForLoop(CurrentLoop, "llvm.loop.unswitch.partial.disable")) { - if (auto Info = - hasPartialIVCondition(*CurrentLoop, MSSAThreshold, *MSSA, *AA)) { - assert(!Info->InstToDuplicate.empty() && - "need at least a partially invariant condition"); - LLVM_DEBUG(dbgs() << "loop-unswitch: Found partially invariant condition " - << *Info->InstToDuplicate[0] << "\n"); - - Instruction *TI = CurrentLoop->getHeader()->getTerminator(); - Value *LoopCond = Info->InstToDuplicate[0]; - - // If the partially unswitched path is a no-op and has a single exit - // block, we do not need to do full unswitching. Instead, we can directly - // branch to the exit. - // TODO: Instead of duplicating the checks, we could also just directly - // branch to the exit from the conditional branch in the loop. - if (Info->PathIsNoop) { - if (HasBranchDivergence && - getAnalysis().isDivergent(LoopCond)) { - LLVM_DEBUG(dbgs() << "NOT unswitching loop %" - << CurrentLoop->getHeader()->getName() - << " at non-trivial condition '" - << *Info->KnownValue << "' == " << *LoopCond << "\n" - << ". Condition is divergent.\n"); - return false; - } - - ++NumBranches; - - BasicBlock *TrueDest = LoopHeader; - BasicBlock *FalseDest = Info->ExitForPath; - if (Info->KnownValue->isOneValue()) - std::swap(TrueDest, FalseDest); - - auto *OldBr = - cast(CurrentLoop->getLoopPreheader()->getTerminator()); - emitPreheaderBranchOnCondition(LoopCond, Info->KnownValue, TrueDest, - FalseDest, OldBr, TI, - Info->InstToDuplicate); - delete OldBr; - RedoLoop = false; - return true; - } - - // Otherwise, the path is not a no-op. Run regular unswitching. - if (unswitchIfProfitable(LoopCond, Info->KnownValue, - CurrentLoop->getHeader()->getTerminator(), - Info->InstToDuplicate)) { - ++NumBranches; - RedoLoop = false; - return true; - } - } - } - - return Changed; -} - -/// Check to see if all paths from BB exit the loop with no side effects -/// (including infinite loops). -/// -/// If true, we return true and set ExitBB to the block we -/// exit through. -/// -static bool -isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB, BasicBlock *&ExitBB, - SmallPtrSet &Visited) { - if (!Visited.insert(BB).second) { - // Already visited. Without more analysis, this could indicate an infinite - // loop. - return false; - } - if (!L->contains(BB)) { - // Otherwise, this is a loop exit, this is fine so long as this is the - // first exit. - if (ExitBB) return false; - ExitBB = BB; - return true; - } - - // Otherwise, this is an unvisited intra-loop node. Check all successors. - for (BasicBlock *Succ : successors(BB)) { - // Check to see if the successor is a trivial loop exit. - if (!isTrivialLoopExitBlockHelper(L, Succ, ExitBB, Visited)) - return false; - } - - // Okay, everything after this looks good, check to make sure that this block - // doesn't include any side effects. - for (Instruction &I : *BB) - if (I.mayHaveSideEffects()) - return false; - - return true; -} - -/// Return true if the specified block unconditionally leads to an exit from -/// the specified loop, and has no side-effects in the process. If so, return -/// the block that is exited to, otherwise return null. -static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) { - SmallPtrSet Visited; - Visited.insert(L->getHeader()); // Branches to header make infinite loops. - BasicBlock *ExitBB = nullptr; - if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited)) - return ExitBB; - return nullptr; -} - -/// We have found that we can unswitch CurrentLoop when LoopCond == Val to -/// simplify the loop. If we decide that this is profitable, -/// unswitch the loop, reprocess the pieces, then return true. -bool LoopUnswitch::unswitchIfProfitable(Value *LoopCond, Constant *Val, - Instruction *TI, - ArrayRef ToDuplicate) { - // Check to see if it would be profitable to unswitch current loop. - if (!BranchesInfo.costAllowsUnswitching()) { - LLVM_DEBUG(dbgs() << "NOT unswitching loop %" - << CurrentLoop->getHeader()->getName() - << " at non-trivial condition '" << *Val - << "' == " << *LoopCond << "\n" - << ". Cost too high.\n"); - return false; - } - if (HasBranchDivergence && - getAnalysis().isDivergent(LoopCond)) { - LLVM_DEBUG(dbgs() << "NOT unswitching loop %" - << CurrentLoop->getHeader()->getName() - << " at non-trivial condition '" << *Val - << "' == " << *LoopCond << "\n" - << ". Condition is divergent.\n"); - return false; - } - - unswitchNontrivialCondition(LoopCond, Val, CurrentLoop, TI, ToDuplicate); - return true; -} - -/// Emit a conditional branch on two values if LIC == Val, branch to TrueDst, -/// otherwise branch to FalseDest. Insert the code immediately before OldBranch -/// and remove (but not erase!) it from the function. -void LoopUnswitch::emitPreheaderBranchOnCondition( - Value *LIC, Constant *Val, BasicBlock *TrueDest, BasicBlock *FalseDest, - BranchInst *OldBranch, Instruction *TI, - ArrayRef ToDuplicate) { - assert(OldBranch->isUnconditional() && "Preheader is not split correctly"); - assert(TrueDest != FalseDest && "Branch targets should be different"); - - // Insert a conditional branch on LIC to the two preheaders. The original - // code is the true version and the new code is the false version. - Value *BranchVal = LIC; - bool Swapped = false; - - if (!ToDuplicate.empty()) { - ValueToValueMapTy Old2New; - for (Instruction *I : reverse(ToDuplicate)) { - auto *New = I->clone(); - New->insertBefore(OldBranch); - RemapInstruction(New, Old2New, - RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); - Old2New[I] = New; - - if (MSSAU) { - MemorySSA *MSSA = MSSAU->getMemorySSA(); - auto *MemA = dyn_cast_or_null(MSSA->getMemoryAccess(I)); - if (!MemA) - continue; - - Loop *L = LI->getLoopFor(I->getParent()); - auto *DefiningAccess = MemA->getDefiningAccess(); - // Get the first defining access before the loop. - while (L->contains(DefiningAccess->getBlock())) { - // If the defining access is a MemoryPhi, get the incoming - // value for the pre-header as defining access. - if (auto *MemPhi = dyn_cast(DefiningAccess)) { - DefiningAccess = - MemPhi->getIncomingValueForBlock(L->getLoopPreheader()); - } else { - DefiningAccess = - cast(DefiningAccess)->getDefiningAccess(); - } - } - MSSAU->createMemoryAccessInBB(New, DefiningAccess, New->getParent(), - MemorySSA::BeforeTerminator); - } - } - BranchVal = Old2New[ToDuplicate[0]]; - } else { - - if (!isa(Val) || - Val->getType() != Type::getInt1Ty(LIC->getContext())) - BranchVal = new ICmpInst(OldBranch, ICmpInst::ICMP_EQ, LIC, Val); - else if (Val != ConstantInt::getTrue(Val->getContext())) { - // We want to enter the new loop when the condition is true. - std::swap(TrueDest, FalseDest); - Swapped = true; - } - } - - // Old branch will be removed, so save its parent and successor to update the - // DomTree. - auto *OldBranchSucc = OldBranch->getSuccessor(0); - auto *OldBranchParent = OldBranch->getParent(); - - // Insert the new branch. - BranchInst *BI = - IRBuilder<>(OldBranch).CreateCondBr(BranchVal, TrueDest, FalseDest, TI); - if (Swapped) - BI->swapProfMetadata(); - - // Remove the old branch so there is only one branch at the end. This is - // needed to perform DomTree's internal DFS walk on the function's CFG. - OldBranch->removeFromParent(); - - // Inform the DT about the new branch. - if (DT) { - // First, add both successors. - SmallVector Updates; - if (TrueDest != OldBranchSucc) - Updates.push_back({DominatorTree::Insert, OldBranchParent, TrueDest}); - if (FalseDest != OldBranchSucc) - Updates.push_back({DominatorTree::Insert, OldBranchParent, FalseDest}); - // If both of the new successors are different from the old one, inform the - // DT that the edge was deleted. - if (OldBranchSucc != TrueDest && OldBranchSucc != FalseDest) { - Updates.push_back({DominatorTree::Delete, OldBranchParent, OldBranchSucc}); - } - - if (MSSAU) - MSSAU->applyUpdates(Updates, *DT, /*UpdateDT=*/true); - else - DT->applyUpdates(Updates); - } - - // If either edge is critical, split it. This helps preserve LoopSimplify - // form for enclosing loops. - auto Options = - CriticalEdgeSplittingOptions(DT, LI, MSSAU.get()).setPreserveLCSSA(); - SplitCriticalEdge(BI, 0, Options); - SplitCriticalEdge(BI, 1, Options); -} - -/// Given a loop that has a trivial unswitchable condition in it (a cond branch -/// from its header block to its latch block, where the path through the loop -/// that doesn't execute its body has no side-effects), unswitch it. This -/// doesn't involve any code duplication, just moving the conditional branch -/// outside of the loop and updating loop info. -void LoopUnswitch::unswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, - BasicBlock *ExitBlock, - Instruction *TI) { - LLVM_DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %" - << LoopHeader->getName() << " [" << L->getBlocks().size() - << " blocks] in Function " - << L->getHeader()->getParent()->getName() - << " on cond: " << *Val << " == " << *Cond << "\n"); - // We are going to make essential changes to CFG. This may invalidate cached - // information for L or one of its parent loops in SCEV. - if (auto *SEWP = getAnalysisIfAvailable()) - SEWP->getSE().forgetTopmostLoop(L); - - // First step, split the preheader, so that we know that there is a safe place - // to insert the conditional branch. We will change LoopPreheader to have a - // conditional branch on Cond. - BasicBlock *NewPH = SplitEdge(LoopPreheader, LoopHeader, DT, LI, MSSAU.get()); - - // Now that we have a place to insert the conditional branch, create a place - // to branch to: this is the exit block out of the loop that we should - // short-circuit to. - - // Split this block now, so that the loop maintains its exit block, and so - // that the jump from the preheader can execute the contents of the exit block - // without actually branching to it (the exit block should be dominated by the - // loop header, not the preheader). - assert(!L->contains(ExitBlock) && "Exit block is in the loop?"); - BasicBlock *NewExit = - SplitBlock(ExitBlock, &ExitBlock->front(), DT, LI, MSSAU.get()); - - // Okay, now we have a position to branch from and a position to branch to, - // insert the new conditional branch. - auto *OldBranch = dyn_cast(LoopPreheader->getTerminator()); - assert(OldBranch && "Failed to split the preheader"); - emitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OldBranch, TI); - - // emitPreheaderBranchOnCondition removed the OldBranch from the function. - // Delete it, as it is no longer needed. - delete OldBranch; - - // We need to reprocess this loop, it could be unswitched again. - RedoLoop = true; - - // Now that we know that the loop is never entered when this condition is a - // particular value, rewrite the loop with this info. We know that this will - // at least eliminate the old branch. - rewriteLoopBodyWithConditionConstant(L, Cond, Val, /*IsEqual=*/false); - - ++NumTrivial; -} - -/// Check if the first non-constant condition starting from the loop header is -/// a trivial unswitch condition: that is, a condition controls whether or not -/// the loop does anything at all. If it is a trivial condition, unswitching -/// produces no code duplications (equivalently, it produces a simpler loop and -/// a new empty loop, which gets deleted). Therefore always unswitch trivial -/// condition. -bool LoopUnswitch::tryTrivialLoopUnswitch(bool &Changed) { - BasicBlock *CurrentBB = CurrentLoop->getHeader(); - Instruction *CurrentTerm = CurrentBB->getTerminator(); - LLVMContext &Context = CurrentBB->getContext(); - - // If loop header has only one reachable successor (currently via an - // unconditional branch or constant foldable conditional branch, but - // should also consider adding constant foldable switch instruction in - // future), we should keep looking for trivial condition candidates in - // the successor as well. An alternative is to constant fold conditions - // and merge successors into loop header (then we only need to check header's - // terminator). The reason for not doing this in LoopUnswitch pass is that - // it could potentially break LoopPassManager's invariants. Folding dead - // branches could either eliminate the current loop or make other loops - // unreachable. LCSSA form might also not be preserved after deleting - // branches. The following code keeps traversing loop header's successors - // until it finds the trivial condition candidate (condition that is not a - // constant). Since unswitching generates branches with constant conditions, - // this scenario could be very common in practice. - SmallPtrSet Visited; - - while (true) { - // If we exit loop or reach a previous visited block, then - // we can not reach any trivial condition candidates (unfoldable - // branch instructions or switch instructions) and no unswitch - // can happen. Exit and return false. - if (!CurrentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second) - return false; - - // Check if this loop will execute any side-effecting instructions (e.g. - // stores, calls, volatile loads) in the part of the loop that the code - // *would* execute. Check the header first. - for (Instruction &I : *CurrentBB) - if (I.mayHaveSideEffects()) - return false; - - if (BranchInst *BI = dyn_cast(CurrentTerm)) { - if (BI->isUnconditional()) { - CurrentBB = BI->getSuccessor(0); - } else if (BI->getCondition() == ConstantInt::getTrue(Context)) { - CurrentBB = BI->getSuccessor(0); - } else if (BI->getCondition() == ConstantInt::getFalse(Context)) { - CurrentBB = BI->getSuccessor(1); - } else { - // Found a trivial condition candidate: non-foldable conditional branch. - break; - } - } else if (SwitchInst *SI = dyn_cast(CurrentTerm)) { - // At this point, any constant-foldable instructions should have probably - // been folded. - ConstantInt *Cond = dyn_cast(SI->getCondition()); - if (!Cond) - break; - // Find the target block we are definitely going to. - CurrentBB = SI->findCaseValue(Cond)->getCaseSuccessor(); - } else { - // We do not understand these terminator instructions. - break; - } - - CurrentTerm = CurrentBB->getTerminator(); - } - - // CondVal is the condition that controls the trivial condition. - // LoopExitBB is the BasicBlock that loop exits when meets trivial condition. - Constant *CondVal = nullptr; - BasicBlock *LoopExitBB = nullptr; - - if (BranchInst *BI = dyn_cast(CurrentTerm)) { - // If this isn't branching on an invariant condition, we can't unswitch it. - if (!BI->isConditional()) - return false; - - Value *LoopCond = findLIVLoopCondition(BI->getCondition(), CurrentLoop, - Changed, MSSAU.get()) - .first; - - // Unswitch only if the trivial condition itself is an LIV (not - // partial LIV which could occur in and/or) - if (!LoopCond || LoopCond != BI->getCondition()) - return false; - - // Check to see if a successor of the branch is guaranteed to - // exit through a unique exit block without having any - // side-effects. If so, determine the value of Cond that causes - // it to do this. - if ((LoopExitBB = - isTrivialLoopExitBlock(CurrentLoop, BI->getSuccessor(0)))) { - CondVal = ConstantInt::getTrue(Context); - } else if ((LoopExitBB = - isTrivialLoopExitBlock(CurrentLoop, BI->getSuccessor(1)))) { - CondVal = ConstantInt::getFalse(Context); - } - - // If we didn't find a single unique LoopExit block, or if the loop exit - // block contains phi nodes, this isn't trivial. - if (!LoopExitBB || isa(LoopExitBB->begin())) - return false; // Can't handle this. - - if (equalityPropUnSafe(*LoopCond)) - return false; - - unswitchTrivialCondition(CurrentLoop, LoopCond, CondVal, LoopExitBB, - CurrentTerm); - ++NumBranches; - return true; - } else if (SwitchInst *SI = dyn_cast(CurrentTerm)) { - // If this isn't switching on an invariant condition, we can't unswitch it. - Value *LoopCond = findLIVLoopCondition(SI->getCondition(), CurrentLoop, - Changed, MSSAU.get()) - .first; - - // Unswitch only if the trivial condition itself is an LIV (not - // partial LIV which could occur in and/or) - if (!LoopCond || LoopCond != SI->getCondition()) - return false; - - // Check to see if a successor of the switch is guaranteed to go to the - // latch block or exit through a one exit block without having any - // side-effects. If so, determine the value of Cond that causes it to do - // this. - // Note that we can't trivially unswitch on the default case or - // on already unswitched cases. - for (auto Case : SI->cases()) { - BasicBlock *LoopExitCandidate; - if ((LoopExitCandidate = - isTrivialLoopExitBlock(CurrentLoop, Case.getCaseSuccessor()))) { - // Okay, we found a trivial case, remember the value that is trivial. - ConstantInt *CaseVal = Case.getCaseValue(); - - // Check that it was not unswitched before, since already unswitched - // trivial vals are looks trivial too. - if (BranchesInfo.isUnswitched(SI, CaseVal)) - continue; - LoopExitBB = LoopExitCandidate; - CondVal = CaseVal; - break; - } - } - - // If we didn't find a single unique LoopExit block, or if the loop exit - // block contains phi nodes, this isn't trivial. - if (!LoopExitBB || isa(LoopExitBB->begin())) - return false; // Can't handle this. - - unswitchTrivialCondition(CurrentLoop, LoopCond, CondVal, LoopExitBB, - nullptr); - - // We are only unswitching full LIV. - BranchesInfo.setUnswitched(SI, CondVal); - ++NumSwitches; - return true; - } - return false; -} - -/// Split all of the edges from inside the loop to their exit blocks. -/// Update the appropriate Phi nodes as we do so. -void LoopUnswitch::splitExitEdges( - Loop *L, const SmallVectorImpl &ExitBlocks) { - - for (unsigned I = 0, E = ExitBlocks.size(); I != E; ++I) { - BasicBlock *ExitBlock = ExitBlocks[I]; - SmallVector Preds(predecessors(ExitBlock)); - - // Although SplitBlockPredecessors doesn't preserve loop-simplify in - // general, if we call it on all predecessors of all exits then it does. - SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, MSSAU.get(), - /*PreserveLCSSA*/ true); - } -} - -/// We determined that the loop is profitable to unswitch when LIC equal Val. -/// Split it into loop versions and test the condition outside of either loop. -/// Return the loops created as Out1/Out2. -void LoopUnswitch::unswitchNontrivialCondition( - Value *LIC, Constant *Val, Loop *L, Instruction *TI, - ArrayRef ToDuplicate) { - Function *F = LoopHeader->getParent(); - LLVM_DEBUG(dbgs() << "loop-unswitch: Unswitching loop %" - << LoopHeader->getName() << " [" << L->getBlocks().size() - << " blocks] in Function " << F->getName() << " when '" - << *Val << "' == " << *LIC << "\n"); - - // We are going to make essential changes to CFG. This may invalidate cached - // information for L or one of its parent loops in SCEV. - if (auto *SEWP = getAnalysisIfAvailable()) - SEWP->getSE().forgetTopmostLoop(L); - - LoopBlocks.clear(); - NewBlocks.clear(); - - if (MSSAU && VerifyMemorySSA) - MSSA->verifyMemorySSA(); - - // First step, split the preheader and exit blocks, and add these blocks to - // the LoopBlocks list. - BasicBlock *NewPreheader = - SplitEdge(LoopPreheader, LoopHeader, DT, LI, MSSAU.get()); - LoopBlocks.push_back(NewPreheader); - - // We want the loop to come after the preheader, but before the exit blocks. - llvm::append_range(LoopBlocks, L->blocks()); - - SmallVector ExitBlocks; - L->getUniqueExitBlocks(ExitBlocks); - - // Split all of the edges from inside the loop to their exit blocks. Update - // the appropriate Phi nodes as we do so. - splitExitEdges(L, ExitBlocks); - - // The exit blocks may have been changed due to edge splitting, recompute. - ExitBlocks.clear(); - L->getUniqueExitBlocks(ExitBlocks); - - // Add exit blocks to the loop blocks. - llvm::append_range(LoopBlocks, ExitBlocks); - - // Next step, clone all of the basic blocks that make up the loop (including - // the loop preheader and exit blocks), keeping track of the mapping between - // the instructions and blocks. - NewBlocks.reserve(LoopBlocks.size()); - ValueToValueMapTy VMap; - for (unsigned I = 0, E = LoopBlocks.size(); I != E; ++I) { - BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[I], VMap, ".us", F); - - NewBlocks.push_back(NewBB); - VMap[LoopBlocks[I]] = NewBB; // Keep the BB mapping. - } - - // Splice the newly inserted blocks into the function right before the - // original preheader. - F->getBasicBlockList().splice(NewPreheader->getIterator(), - F->getBasicBlockList(), - NewBlocks[0]->getIterator(), F->end()); - - // Now we create the new Loop object for the versioned loop. - Loop *NewLoop = cloneLoop(L, L->getParentLoop(), VMap, LI, LPM); - - // Recalculate unswitching quota, inherit simplified switches info for NewBB, - // Probably clone more loop-unswitch related loop properties. - BranchesInfo.cloneData(NewLoop, L, VMap); - - Loop *ParentLoop = L->getParentLoop(); - if (ParentLoop) { - // Make sure to add the cloned preheader and exit blocks to the parent loop - // as well. - ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI); - } - - for (unsigned EBI = 0, EBE = ExitBlocks.size(); EBI != EBE; ++EBI) { - BasicBlock *NewExit = cast(VMap[ExitBlocks[EBI]]); - // The new exit block should be in the same loop as the old one. - if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[EBI])) - ExitBBLoop->addBasicBlockToLoop(NewExit, *LI); - - assert(NewExit->getTerminator()->getNumSuccessors() == 1 && - "Exit block should have been split to have one successor!"); - BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0); - - // If the successor of the exit block had PHI nodes, add an entry for - // NewExit. - for (PHINode &PN : ExitSucc->phis()) { - Value *V = PN.getIncomingValueForBlock(ExitBlocks[EBI]); - ValueToValueMapTy::iterator It = VMap.find(V); - if (It != VMap.end()) V = It->second; - PN.addIncoming(V, NewExit); - } - - if (LandingPadInst *LPad = NewExit->getLandingPadInst()) { - PHINode *PN = PHINode::Create(LPad->getType(), 0, "", - &*ExitSucc->getFirstInsertionPt()); - - for (BasicBlock *BB : predecessors(ExitSucc)) { - LandingPadInst *LPI = BB->getLandingPadInst(); - LPI->replaceAllUsesWith(PN); - PN->addIncoming(LPI, BB); - } - } - } - - // Rewrite the code to refer to itself. - for (unsigned NBI = 0, NBE = NewBlocks.size(); NBI != NBE; ++NBI) { - for (Instruction &I : *NewBlocks[NBI]) { - RemapInstruction(&I, VMap, - RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); - if (auto *II = dyn_cast(&I)) - AC->registerAssumption(II); - } - } - - // Rewrite the original preheader to select between versions of the loop. - BranchInst *OldBR = cast(LoopPreheader->getTerminator()); - assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] && - "Preheader splitting did not work correctly!"); - - if (MSSAU) { - // Update MemorySSA after cloning, and before splitting to unreachables, - // since that invalidates the 1:1 mapping of clones in VMap. - LoopBlocksRPO LBRPO(L); - LBRPO.perform(LI); - MSSAU->updateForClonedLoop(LBRPO, ExitBlocks, VMap); - } - - // Emit the new branch that selects between the two versions of this loop. - emitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR, - TI, ToDuplicate); - if (MSSAU) { - // Update MemoryPhis in Exit blocks. - MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMap, *DT); - if (VerifyMemorySSA) - MSSA->verifyMemorySSA(); - } - - // The OldBr was replaced by a new one and removed (but not erased) by - // emitPreheaderBranchOnCondition. It is no longer needed, so delete it. - delete OldBR; - - LoopProcessWorklist.push_back(NewLoop); - RedoLoop = true; - - // Keep a WeakTrackingVH holding onto LIC. If the first call to - // RewriteLoopBody - // deletes the instruction (for example by simplifying a PHI that feeds into - // the condition that we're unswitching on), we don't rewrite the second - // iteration. - WeakTrackingVH LICHandle(LIC); - - if (ToDuplicate.empty()) { - // Now we rewrite the original code to know that the condition is true and - // the new code to know that the condition is false. - rewriteLoopBodyWithConditionConstant(L, LIC, Val, /*IsEqual=*/false); - - // It's possible that simplifying one loop could cause the other to be - // changed to another value or a constant. If its a constant, don't - // simplify it. - if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop && - LICHandle && !isa(LICHandle)) - rewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, - /*IsEqual=*/true); - } else { - // Partial unswitching. Update the condition in the right loop with the - // constant. - auto *CC = cast(Val); - if (CC->isOneValue()) { - rewriteLoopBodyWithConditionConstant(NewLoop, VMap[LIC], Val, - /*IsEqual=*/true); - } else - rewriteLoopBodyWithConditionConstant(L, LIC, Val, /*IsEqual=*/true); - - // Mark the new loop as partially unswitched, to avoid unswitching on the - // same condition again. - auto &Context = NewLoop->getHeader()->getContext(); - MDNode *DisableUnswitchMD = MDNode::get( - Context, MDString::get(Context, "llvm.loop.unswitch.partial.disable")); - MDNode *NewLoopID = makePostTransformationMetadata( - Context, L->getLoopID(), {"llvm.loop.unswitch.partial"}, - {DisableUnswitchMD}); - NewLoop->setLoopID(NewLoopID); - } - - if (MSSA && VerifyMemorySSA) - MSSA->verifyMemorySSA(); -} - -/// Remove all instances of I from the worklist vector specified. -static void removeFromWorklist(Instruction *I, - std::vector &Worklist) { - llvm::erase_value(Worklist, I); -} - -/// When we find that I really equals V, remove I from the -/// program, replacing all uses with V and update the worklist. -static void replaceUsesOfWith(Instruction *I, Value *V, - std::vector &Worklist, Loop *L, - LPPassManager *LPM, MemorySSAUpdater *MSSAU) { - LLVM_DEBUG(dbgs() << "Replace with '" << *V << "': " << *I << "\n"); - - // Add uses to the worklist, which may be dead now. - for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) - if (Instruction *Use = dyn_cast(I->getOperand(i))) - Worklist.push_back(Use); - - // Add users to the worklist which may be simplified now. - for (User *U : I->users()) - Worklist.push_back(cast(U)); - removeFromWorklist(I, Worklist); - I->replaceAllUsesWith(V); - if (!I->mayHaveSideEffects()) { - if (MSSAU) - MSSAU->removeMemoryAccess(I); - I->eraseFromParent(); - } - ++NumSimplify; -} - -/// We know either that the value LIC has the value specified by Val in the -/// specified loop, or we know it does NOT have that value. -/// Rewrite any uses of LIC or of properties correlated to it. -void LoopUnswitch::rewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, - Constant *Val, - bool IsEqual) { - assert(!isa(LIC) && "Why are we unswitching on a constant?"); - - // FIXME: Support correlated properties, like: - // for (...) - // if (li1 < li2) - // ... - // if (li1 > li2) - // ... - - // FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches, - // selects, switches. - std::vector Worklist; - LLVMContext &Context = Val->getContext(); - - // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC - // in the loop with the appropriate one directly. - if (IsEqual || (isa(Val) && - Val->getType()->isIntegerTy(1))) { - Value *Replacement; - if (IsEqual) - Replacement = Val; - else - Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()), - !cast(Val)->getZExtValue()); - - for (User *U : LIC->users()) { - Instruction *UI = dyn_cast(U); - if (!UI || !L->contains(UI)) - continue; - Worklist.push_back(UI); - } - - for (Instruction *UI : Worklist) - UI->replaceUsesOfWith(LIC, Replacement); - - simplifyCode(Worklist, L); - return; - } - - // Otherwise, we don't know the precise value of LIC, but we do know that it - // is certainly NOT "Val". As such, simplify any uses in the loop that we - // can. This case occurs when we unswitch switch statements. - for (User *U : LIC->users()) { - Instruction *UI = dyn_cast(U); - if (!UI || !L->contains(UI)) - continue; - - // At this point, we know LIC is definitely not Val. Try to use some simple - // logic to simplify the user w.r.t. to the context. - if (Value *Replacement = simplifyInstructionWithNotEqual(UI, LIC, Val)) { - if (LI->replacementPreservesLCSSAForm(UI, Replacement)) { - // This in-loop instruction has been simplified w.r.t. its context, - // i.e. LIC != Val, make sure we propagate its replacement value to - // all its users. - // - // We can not yet delete UI, the LIC user, yet, because that would invalidate - // the LIC->users() iterator !. However, we can make this instruction - // dead by replacing all its users and push it onto the worklist so that - // it can be properly deleted and its operands simplified. - UI->replaceAllUsesWith(Replacement); - } - } - - // This is a LIC user, push it into the worklist so that simplifyCode can - // attempt to simplify it. - Worklist.push_back(UI); - - // If we know that LIC is not Val, use this info to simplify code. - SwitchInst *SI = dyn_cast(UI); - if (!SI || !isa(Val)) continue; - - // NOTE: if a case value for the switch is unswitched out, we record it - // after the unswitch finishes. We can not record it here as the switch - // is not a direct user of the partial LIV. - SwitchInst::CaseHandle DeadCase = - *SI->findCaseValue(cast(Val)); - // Default case is live for multiple values. - if (DeadCase == *SI->case_default()) - continue; - - // Found a dead case value. Don't remove PHI nodes in the - // successor if they become single-entry, those PHI nodes may - // be in the Users list. - - BasicBlock *Switch = SI->getParent(); - BasicBlock *SISucc = DeadCase.getCaseSuccessor(); - BasicBlock *Latch = L->getLoopLatch(); - - if (!SI->findCaseDest(SISucc)) continue; // Edge is critical. - // If the DeadCase successor dominates the loop latch, then the - // transformation isn't safe since it will delete the sole predecessor edge - // to the latch. - if (Latch && DT->dominates(SISucc, Latch)) - continue; - - // FIXME: This is a hack. We need to keep the successor around - // and hooked up so as to preserve the loop structure, because - // trying to update it is complicated. So instead we preserve the - // loop structure and put the block on a dead code path. - SplitEdge(Switch, SISucc, DT, LI, MSSAU.get()); - // Compute the successors instead of relying on the return value - // of SplitEdge, since it may have split the switch successor - // after PHI nodes. - BasicBlock *NewSISucc = DeadCase.getCaseSuccessor(); - BasicBlock *OldSISucc = *succ_begin(NewSISucc); - // Create an "unreachable" destination. - BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable", - Switch->getParent(), - OldSISucc); - new UnreachableInst(Context, Abort); - // Force the new case destination to branch to the "unreachable" - // block while maintaining a (dead) CFG edge to the old block. - NewSISucc->getTerminator()->eraseFromParent(); - BranchInst::Create(Abort, OldSISucc, - ConstantInt::getTrue(Context), NewSISucc); - // Release the PHI operands for this edge. - for (PHINode &PN : NewSISucc->phis()) - PN.setIncomingValueForBlock(Switch, UndefValue::get(PN.getType())); - // Tell the domtree about the new block. We don't fully update the - // domtree here -- instead we force it to do a full recomputation - // after the pass is complete -- but we do need to inform it of - // new blocks. - DT->addNewBlock(Abort, NewSISucc); - } - - simplifyCode(Worklist, L); -} - -/// Now that we have simplified some instructions in the loop, walk over it and -/// constant prop, dce, and fold control flow where possible. Note that this is -/// effectively a very simple loop-structure-aware optimizer. During processing -/// of this loop, L could very well be deleted, so it must not be used. -/// -/// FIXME: When the loop optimizer is more mature, separate this out to a new -/// pass. -/// -void LoopUnswitch::simplifyCode(std::vector &Worklist, Loop *L) { - const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); - while (!Worklist.empty()) { - Instruction *I = Worklist.back(); - Worklist.pop_back(); - - // Simple DCE. - if (isInstructionTriviallyDead(I)) { - LLVM_DEBUG(dbgs() << "Remove dead instruction '" << *I << "\n"); - - // Add uses to the worklist, which may be dead now. - for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) - if (Instruction *Use = dyn_cast(I->getOperand(i))) - Worklist.push_back(Use); - removeFromWorklist(I, Worklist); - if (MSSAU) - MSSAU->removeMemoryAccess(I); - I->eraseFromParent(); - ++NumSimplify; - continue; - } - - // See if instruction simplification can hack this up. This is common for - // things like "select false, X, Y" after unswitching made the condition be - // 'false'. TODO: update the domtree properly so we can pass it here. - if (Value *V = SimplifyInstruction(I, DL)) - if (LI->replacementPreservesLCSSAForm(I, V)) { - replaceUsesOfWith(I, V, Worklist, L, LPM, MSSAU.get()); - continue; - } - - // Special case hacks that appear commonly in unswitched code. - if (BranchInst *BI = dyn_cast(I)) { - if (BI->isUnconditional()) { - // If BI's parent is the only pred of the successor, fold the two blocks - // together. - BasicBlock *Pred = BI->getParent(); - (void)Pred; - BasicBlock *Succ = BI->getSuccessor(0); - BasicBlock *SinglePred = Succ->getSinglePredecessor(); - if (!SinglePred) continue; // Nothing to do. - assert(SinglePred == Pred && "CFG broken"); - - // Make the LPM and Worklist updates specific to LoopUnswitch. - removeFromWorklist(BI, Worklist); - auto SuccIt = Succ->begin(); - while (PHINode *PN = dyn_cast(SuccIt++)) { - for (unsigned It = 0, E = PN->getNumOperands(); It != E; ++It) - if (Instruction *Use = dyn_cast(PN->getOperand(It))) - Worklist.push_back(Use); - for (User *U : PN->users()) - Worklist.push_back(cast(U)); - removeFromWorklist(PN, Worklist); - ++NumSimplify; - } - // Merge the block and make the remaining analyses updates. - DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); - MergeBlockIntoPredecessor(Succ, &DTU, LI, MSSAU.get()); - ++NumSimplify; - continue; - } - - continue; - } - } -} - -/// Simple simplifications we can do given the information that Cond is -/// definitely not equal to Val. -Value *LoopUnswitch::simplifyInstructionWithNotEqual(Instruction *Inst, - Value *Invariant, - Constant *Val) { - // icmp eq cond, val -> false - ICmpInst *CI = dyn_cast(Inst); - if (CI && CI->isEquality()) { - Value *Op0 = CI->getOperand(0); - Value *Op1 = CI->getOperand(1); - if ((Op0 == Invariant && Op1 == Val) || (Op0 == Val && Op1 == Invariant)) { - LLVMContext &Ctx = Inst->getContext(); - if (CI->getPredicate() == CmpInst::ICMP_EQ) - return ConstantInt::getFalse(Ctx); - else - return ConstantInt::getTrue(Ctx); - } - } - - // FIXME: there may be other opportunities, e.g. comparison with floating - // point, or Invariant - Val != 0, etc. - return nullptr; -} diff --git a/llvm/lib/Transforms/Scalar/Scalar.cpp b/llvm/lib/Transforms/Scalar/Scalar.cpp --- a/llvm/lib/Transforms/Scalar/Scalar.cpp +++ b/llvm/lib/Transforms/Scalar/Scalar.cpp @@ -73,7 +73,6 @@ initializeLoopRerollLegacyPassPass(Registry); initializeLoopUnrollPass(Registry); initializeLoopUnrollAndJamPass(Registry); - initializeLoopUnswitchPass(Registry); initializeWarnMissedTransformationsLegacyPass(Registry); initializeLoopVersioningLICMLegacyPassPass(Registry); initializeLoopIdiomRecognizeLegacyPassPass(Registry); @@ -212,10 +211,6 @@ unwrap(PM)->add(createLoopUnrollAndJamPass()); } -void LLVMAddLoopUnswitchPass(LLVMPassManagerRef PM) { - unwrap(PM)->add(createLoopUnswitchPass()); -} - void LLVMAddLowerAtomicPass(LLVMPassManagerRef PM) { unwrap(PM)->add(createLowerAtomicPass()); } diff --git a/llvm/test/Analysis/MemorySSA/pr40038.ll b/llvm/test/Analysis/MemorySSA/pr40038.ll --- a/llvm/test/Analysis/MemorySSA/pr40038.ll +++ b/llvm/test/Analysis/MemorySSA/pr40038.ll @@ -1,5 +1,5 @@ ; REQUIRES: asserts -; RUN: opt -S -mtriple=systemz-unknown -mcpu=z13 -O3 -enable-simple-loop-unswitch -verify-memoryssa < %s | FileCheck %s +; RUN: opt -S -mtriple=systemz-unknown -mcpu=z13 -O3 -verify-memoryssa < %s | FileCheck %s target datalayout = "E-m:e-i1:8:16-i8:8:16-i64:64-f128:64-v128:64-a:8:16-n32:64" target triple = "s390x-ibm-linux" diff --git a/llvm/test/Feature/optnone-opt.ll b/llvm/test/Feature/optnone-opt.ll --- a/llvm/test/Feature/optnone-opt.ll +++ b/llvm/test/Feature/optnone-opt.ll @@ -3,7 +3,6 @@ ; RUN: opt -O2 -S -debug -enable-new-pm=0 %s 2>&1 | FileCheck %s --check-prefix=O1 --check-prefix=O2O3 ; RUN: opt -O3 -S -debug -enable-new-pm=0 %s 2>&1 | FileCheck %s --check-prefix=O1 --check-prefix=O2O3 ; RUN: opt -dce -gvn-hoist -loweratomic -S -debug -enable-new-pm=0 %s 2>&1 | FileCheck %s --check-prefix=MORE -; RUN: opt -indvars -licm -loop-deletion -loop-extract -loop-idiom -loop-instsimplify -loop-reduce -loop-reroll -loop-rotate -loop-unroll -loop-unswitch -enable-new-pm=0 -S -debug %s 2>&1 | FileCheck %s --check-prefix=LOOP ; RUN: opt -passes='default' -S -debug-pass-manager %s 2>&1 | FileCheck %s --check-prefix=%llvmcheckext-NPM-O0 ; RUN: opt -passes='default' -S -debug-pass-manager %s 2>&1 | FileCheck %s --check-prefix=NPM-O1 ; RUN: opt -passes='default' -S -debug-pass-manager %s 2>&1 | FileCheck %s --check-prefix=NPM-O1 --check-prefix=NPM-O2O3 diff --git a/llvm/test/Transforms/LoopUnswitch/2006-06-13-SingleEntryPHI.ll b/llvm/test/Transforms/LoopUnswitch/2006-06-13-SingleEntryPHI.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2006-06-13-SingleEntryPHI.ll +++ /dev/null @@ -1,35 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output - - %struct.BLEND_MAP = type { i16, i16, i16, i32, %struct.BLEND_MAP_ENTRY* } - %struct.BLEND_MAP_ENTRY = type { float, i8, { [5 x float], [4 x i8] } } - %struct.TPATTERN = type { i16, i16, i16, i32, float, float, float, %struct.WARP*, %struct.TPATTERN*, %struct.BLEND_MAP*, { %struct.anon, [4 x i8] } } - %struct.TURB = type { i16, %struct.WARP*, [3 x double], i32, float, float } - %struct.WARP = type { i16, %struct.WARP* } - %struct.anon = type { float, [3 x double] } - -define void @Parse_Pattern() { -entry: - br label %bb1096.outer20 -bb671: ; preds = %cond_true1099 - br label %bb1096.outer23 -bb1096.outer20.loopexit: ; preds = %cond_true1099 - %Local_Turb.0.ph24.lcssa = phi %struct.TURB* [ %Local_Turb.0.ph24, %cond_true1099 ] ; <%struct.TURB*> [#uses=1] - br label %bb1096.outer20 -bb1096.outer20: ; preds = %bb1096.outer20.loopexit, %entry - %Local_Turb.0.ph22 = phi %struct.TURB* [ undef, %entry ], [ %Local_Turb.0.ph24.lcssa, %bb1096.outer20.loopexit ] ; <%struct.TURB*> [#uses=1] - %tmp1098 = icmp eq i32 0, 0 ; [#uses=1] - br label %bb1096.outer23 -bb1096.outer23: ; preds = %bb1096.outer20, %bb671 - %Local_Turb.0.ph24 = phi %struct.TURB* [ %Local_Turb.0.ph22, %bb1096.outer20 ], [ null, %bb671 ] ; <%struct.TURB*> [#uses=2] - br label %bb1096 -bb1096: ; preds = %cond_true1099, %bb1096.outer23 - br i1 %tmp1098, label %cond_true1099, label %bb1102 -cond_true1099: ; preds = %bb1096 - switch i32 0, label %bb1096.outer20.loopexit [ - i32 161, label %bb671 - i32 359, label %bb1096 - ] -bb1102: ; preds = %bb1096 - %Local_Turb.0.ph24.lcssa1 = phi %struct.TURB* [ %Local_Turb.0.ph24, %bb1096 ] ; <%struct.TURB*> [#uses=0] - ret void -} diff --git a/llvm/test/Transforms/LoopUnswitch/2006-06-27-DeadSwitchCase.ll b/llvm/test/Transforms/LoopUnswitch/2006-06-27-DeadSwitchCase.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2006-06-27-DeadSwitchCase.ll +++ /dev/null @@ -1,25 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output - -define void @init_caller_save() { -entry: - br label %cond_true78 -cond_next20: ; preds = %cond_true64 - br label %bb31 -bb31: ; preds = %cond_true64, %cond_true64, %cond_next20 - %iftmp.29.1 = phi i32 [ 0, %cond_next20 ], [ 0, %cond_true64 ], [ 0, %cond_true64 ] ; [#uses=0] - br label %bb54 -bb54: ; preds = %cond_true78, %bb31 - br i1 false, label %bb75, label %cond_true64 -cond_true64: ; preds = %bb54 - switch i32 %i.0.0, label %cond_next20 [ - i32 17, label %bb31 - i32 18, label %bb31 - ] -bb75: ; preds = %bb54 - %tmp74.0 = add i32 %i.0.0, 1 ; [#uses=1] - br label %cond_true78 -cond_true78: ; preds = %bb75, %entry - %i.0.0 = phi i32 [ 0, %entry ], [ %tmp74.0, %bb75 ] ; [#uses=2] - br label %bb54 -} - diff --git a/llvm/test/Transforms/LoopUnswitch/2007-05-09-Unreachable.ll b/llvm/test/Transforms/LoopUnswitch/2007-05-09-Unreachable.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2007-05-09-Unreachable.ll +++ /dev/null @@ -1,29 +0,0 @@ -; PR1333 -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -disable-output -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output - -target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64" -target triple = "i686-pc-linux-gnu" - %struct.ada__streams__root_stream_type = type { %struct.ada__tags__dispatch_table* } - %struct.ada__tags__dispatch_table = type { [1 x i8*] } - %struct.quotes__T173s = type { i8, %struct.quotes__T173s__T174s, [2 x [1 x double]], [2 x i16], i64, i8 } - %struct.quotes__T173s__T174s = type { i8, i8, i8, i16, i16, [2 x [1 x double]] } - -define void @quotes__write_quote() { -entry: - %tmp606.i = icmp eq i32 0, 0 ; [#uses=1] - br label %bb -bb: ; preds = %cond_next73, %bb, %entry - br i1 false, label %bb51, label %bb -bb51: ; preds = %cond_next73, %bb - br i1 %tmp606.i, label %quotes__bid_ask_depth_offset_matrices__get_price.exit, label %cond_true.i -cond_true.i: ; preds = %bb51 - unreachable -quotes__bid_ask_depth_offset_matrices__get_price.exit: ; preds = %bb51 - br i1 false, label %cond_next73, label %cond_true72 -cond_true72: ; preds = %quotes__bid_ask_depth_offset_matrices__get_price.exit - unreachable -cond_next73: ; preds = %quotes__bid_ask_depth_offset_matrices__get_price.exit - br i1 false, label %bb, label %bb51 -} - diff --git a/llvm/test/Transforms/LoopUnswitch/2007-05-09-tl.ll b/llvm/test/Transforms/LoopUnswitch/2007-05-09-tl.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2007-05-09-tl.ll +++ /dev/null @@ -1,95 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output -; PR1333 - -define void @pp_cxx_expression() { -entry: - %tmp6 = lshr i32 0, 24 ; [#uses=1] - br label %tailrecurse - -tailrecurse: ; preds = %tailrecurse, %tailrecurse, %entry - switch i32 %tmp6, label %bb96 [ - i32 24, label %bb10 - i32 25, label %bb10 - i32 28, label %bb10 - i32 29, label %bb48 - i32 31, label %bb48 - i32 32, label %bb48 - i32 33, label %bb48 - i32 34, label %bb48 - i32 36, label %bb15 - i32 51, label %bb89 - i32 52, label %bb89 - i32 54, label %bb83 - i32 57, label %bb59 - i32 63, label %bb80 - i32 64, label %bb80 - i32 68, label %bb80 - i32 169, label %bb75 - i32 170, label %bb19 - i32 171, label %bb63 - i32 172, label %bb63 - i32 173, label %bb67 - i32 174, label %bb67 - i32 175, label %bb19 - i32 176, label %bb75 - i32 178, label %bb59 - i32 179, label %bb89 - i32 180, label %bb59 - i32 182, label %bb48 - i32 183, label %bb48 - i32 184, label %bb48 - i32 185, label %bb48 - i32 186, label %bb48 - i32 195, label %bb48 - i32 196, label %bb59 - i32 197, label %bb89 - i32 198, label %bb70 - i32 199, label %bb59 - i32 200, label %bb59 - i32 201, label %bb59 - i32 202, label %bb59 - i32 203, label %bb75 - i32 204, label %bb59 - i32 205, label %tailrecurse - i32 210, label %tailrecurse - ] - -bb10: ; preds = %tailrecurse, %tailrecurse, %tailrecurse - ret void - -bb15: ; preds = %tailrecurse - ret void - -bb19: ; preds = %tailrecurse, %tailrecurse - ret void - -bb48: ; preds = %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse - ret void - -bb59: ; preds = %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse - ret void - -bb63: ; preds = %tailrecurse, %tailrecurse - ret void - -bb67: ; preds = %tailrecurse, %tailrecurse - ret void - -bb70: ; preds = %tailrecurse - ret void - -bb75: ; preds = %tailrecurse, %tailrecurse, %tailrecurse - ret void - -bb80: ; preds = %tailrecurse, %tailrecurse, %tailrecurse - ret void - -bb83: ; preds = %tailrecurse - ret void - -bb89: ; preds = %tailrecurse, %tailrecurse, %tailrecurse, %tailrecurse - ret void - -bb96: ; preds = %tailrecurse - ret void -} diff --git a/llvm/test/Transforms/LoopUnswitch/2007-07-12-ExitDomInfo.ll b/llvm/test/Transforms/LoopUnswitch/2007-07-12-ExitDomInfo.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2007-07-12-ExitDomInfo.ll +++ /dev/null @@ -1,45 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -instcombine -disable-output - -@str3 = external constant [3 x i8] ; <[3 x i8]*> [#uses=1] - -define i32 @stringSearch_Clib(i32 %count) { -entry: - %ttmp25 = icmp sgt i32 %count, 0 ; [#uses=1] - br i1 %ttmp25, label %bb36.preheader, label %bb44 - -bb36.preheader: ; preds = %entry - %ttmp33 = icmp slt i32 0, 250 ; [#uses=1] - br label %bb36.outer - -bb36.outer: ; preds = %bb41, %bb36.preheader - br i1 %ttmp33, label %bb.nph, label %bb41 - -bb.nph: ; preds = %bb36.outer - %ttmp8 = icmp eq i8* null, null ; [#uses=1] - %ttmp6 = icmp eq i8* null, null ; [#uses=1] - %tmp31 = call i32 @strcspn( i8* null, i8* getelementptr ([3 x i8], [3 x i8]* @str3, i64 0, i64 0) ) ; [#uses=1] - br i1 %ttmp8, label %cond_next, label %cond_true - -cond_true: ; preds = %bb.nph - ret i32 0 - -cond_next: ; preds = %bb.nph - br i1 %ttmp6, label %cond_next28, label %cond_true20 - -cond_true20: ; preds = %cond_next - ret i32 0 - -cond_next28: ; preds = %cond_next - %tmp33 = add i32 %tmp31, 0 ; [#uses=1] - br label %bb41 - -bb41: ; preds = %cond_next28, %bb36.outer - %c.2.lcssa = phi i32 [ 0, %bb36.outer ], [ %tmp33, %cond_next28 ] ; [#uses=1] - br i1 false, label %bb36.outer, label %bb44 - -bb44: ; preds = %bb41, %entry - %c.01.1 = phi i32 [ 0, %entry ], [ %c.2.lcssa, %bb41 ] ; [#uses=1] - ret i32 %c.01.1 -} - -declare i32 @strcspn(i8*, i8*) diff --git a/llvm/test/Transforms/LoopUnswitch/2007-07-13-DomInfo.ll b/llvm/test/Transforms/LoopUnswitch/2007-07-13-DomInfo.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2007-07-13-DomInfo.ll +++ /dev/null @@ -1,27 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output - -define i32 @main(i32 %argc, i8** %argv) { -entry: - %tmp1785365 = icmp ult i32 0, 100 ; [#uses=1] - br label %bb - -bb: ; preds = %cond_true, %entry - br i1 false, label %cond_true, label %cond_next - -cond_true: ; preds = %bb - br i1 %tmp1785365, label %bb, label %bb1788 - -cond_next: ; preds = %bb - %iftmp.1.0 = select i1 false, i32 0, i32 0 ; [#uses=1] - br i1 false, label %cond_true47, label %cond_next74 - -cond_true47: ; preds = %cond_next - %tmp53 = urem i32 %iftmp.1.0, 0 ; [#uses=0] - ret i32 0 - -cond_next74: ; preds = %cond_next - ret i32 0 - -bb1788: ; preds = %cond_true - ret i32 0 -} diff --git a/llvm/test/Transforms/LoopUnswitch/2007-07-18-DomInfo.ll b/llvm/test/Transforms/LoopUnswitch/2007-07-18-DomInfo.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2007-07-18-DomInfo.ll +++ /dev/null @@ -1,66 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output -; PR1559 - -target triple = "i686-pc-linux-gnu" - %struct.re_pattern_buffer = type { i8*, i32, i32, i32, i8*, i8*, i32, i8 } - -define fastcc i32 @byte_regex_compile(i8* %pattern, i32 %size, i32 %syntax, %struct.re_pattern_buffer* %bufp) { -entry: - br i1 false, label %bb147, label %cond_next123 - -cond_next123: ; preds = %entry - ret i32 0 - -bb147: ; preds = %entry - switch i32 0, label %normal_char [ - i32 91, label %bb1734 - i32 92, label %bb5700 - ] - -bb1734: ; preds = %bb147 - br label %bb1855.outer.outer - -cond_true1831: ; preds = %bb1855.outer - br i1 %tmp1837, label %cond_next1844, label %cond_true1840 - -cond_true1840: ; preds = %cond_true1831 - ret i32 0 - -cond_next1844: ; preds = %cond_true1831 - br i1 false, label %bb1855.outer, label %cond_true1849 - -cond_true1849: ; preds = %cond_next1844 - br label %bb1855.outer.outer - -bb1855.outer.outer: ; preds = %cond_true1849, %bb1734 - %b.10.ph.ph = phi i8* [ null, %cond_true1849 ], [ null, %bb1734 ] ; [#uses=1] - br label %bb1855.outer - -bb1855.outer: ; preds = %bb1855.outer.outer, %cond_next1844 - %b.10.ph = phi i8* [ null, %cond_next1844 ], [ %b.10.ph.ph, %bb1855.outer.outer ] ; [#uses=1] - %tmp1837 = icmp eq i8* null, null ; [#uses=2] - br i1 false, label %cond_true1831, label %cond_next1915 - -cond_next1915: ; preds = %cond_next1961, %bb1855.outer - store i8* null, i8** null - br i1 %tmp1837, label %cond_next1929, label %cond_true1923 - -cond_true1923: ; preds = %cond_next1915 - ret i32 0 - -cond_next1929: ; preds = %cond_next1915 - br i1 false, label %cond_next1961, label %cond_next2009 - -cond_next1961: ; preds = %cond_next1929 - %tmp1992 = getelementptr i8, i8* %b.10.ph, i32 0 ; [#uses=0] - br label %cond_next1915 - -cond_next2009: ; preds = %cond_next1929 - ret i32 0 - -bb5700: ; preds = %bb147 - ret i32 0 - -normal_char: ; preds = %bb147 - ret i32 0 -} diff --git a/llvm/test/Transforms/LoopUnswitch/2007-08-01-Dom.ll b/llvm/test/Transforms/LoopUnswitch/2007-08-01-Dom.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2007-08-01-Dom.ll +++ /dev/null @@ -1,30 +0,0 @@ -; RUN: opt < %s -licm -loop-unswitch -enable-new-pm=0 -disable-output -; PR 1589 - - %struct.QBasicAtomic = type { i32 } - -define void @_ZNK5QDate9addMonthsEi(%struct.QBasicAtomic* sret(%struct.QBasicAtomic) %agg.result, %struct.QBasicAtomic* %this, i32 %nmonths) { -entry: - br label %cond_true90 - -bb16: ; preds = %cond_true90 - br i1 false, label %bb93, label %cond_true90 - -bb45: ; preds = %cond_true90 - br i1 false, label %bb53, label %bb58 - -bb53: ; preds = %bb45 - br i1 false, label %bb93, label %cond_true90 - -bb58: ; preds = %bb45 - store i32 0, i32* null, align 4 - br i1 false, label %cond_true90, label %bb93 - -cond_true90: ; preds = %bb58, %bb53, %bb16, %entry - %nmonths_addr.016.1 = phi i32 [ %nmonths, %entry ], [ 0, %bb16 ], [ 0, %bb53 ], [ %nmonths_addr.016.1, %bb58 ] ; [#uses=2] - %tmp14 = icmp slt i32 %nmonths_addr.016.1, -11 ; [#uses=1] - br i1 %tmp14, label %bb16, label %bb45 - -bb93: ; preds = %bb58, %bb53, %bb16 - ret void -} diff --git a/llvm/test/Transforms/LoopUnswitch/2007-08-01-LCSSA.ll b/llvm/test/Transforms/LoopUnswitch/2007-08-01-LCSSA.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2007-08-01-LCSSA.ll +++ /dev/null @@ -1,55 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -instcombine -disable-output - %struct.ClassDef = type { %struct.QByteArray, %struct.QByteArray, %"struct.QList", %"struct.QList", i8, i8, %"struct.QList", %"struct.QList", %"struct.QList", %"struct.QList", %"struct.QList", %"struct.QList", %"struct.QMap", %"struct.QList", %"struct.QMap", i32, i32 } - %struct.FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct.FILE*, i32, i32, i32, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i32, i32, [40 x i8] } - %struct.Generator = type { %struct.FILE*, %struct.ClassDef*, %"struct.QList", %struct.QByteArray, %"struct.QList" } - %struct.QBasicAtomic = type { i32 } - %struct.QByteArray = type { %"struct.QByteArray::Data"* } - %"struct.QByteArray::Data" = type { %struct.QBasicAtomic, i32, i32, i8*, [1 x i8] } - %"struct.QList" = type { %"struct.QList::._19" } - %"struct.QList::._19" = type { %struct.QListData } - %struct.QListData = type { %"struct.QListData::Data"* } - %"struct.QListData::Data" = type { %struct.QBasicAtomic, i32, i32, i32, i8, [1 x i8*] } - %"struct.QMap" = type { %"struct.QMap::._56" } - %"struct.QMap::._56" = type { %struct.QMapData* } - %struct.QMapData = type { %struct.QMapData*, [12 x %struct.QMapData*], %struct.QBasicAtomic, i32, i32, i32, i8 } - %struct._IO_marker = type { %struct._IO_marker*, %struct.FILE*, i32 } -@.str9 = external constant [1 x i8] ; <[1 x i8]*> [#uses=1] - -declare i32 @strcmp(i8*, i8*) - -define i32 @_ZN9Generator6strregEPKc(%struct.Generator* %this, i8* %s) { -entry: - %s_addr.0 = select i1 false, i8* getelementptr ([1 x i8], [1 x i8]* @.str9, i32 0, i32 0), i8* %s ; [#uses=2] - %tmp122 = icmp eq i8* %s_addr.0, null ; [#uses=1] - br label %bb184 - -bb55: ; preds = %bb184 - ret i32 0 - -bb88: ; preds = %bb184 - br i1 %tmp122, label %bb154, label %bb128 - -bb128: ; preds = %bb88 - %tmp138 = call i32 @strcmp( i8* null, i8* %s_addr.0 ) ; [#uses=1] - %iftmp.37.0.in4 = icmp eq i32 %tmp138, 0 ; [#uses=1] - br i1 %iftmp.37.0.in4, label %bb250, label %bb166 - -bb154: ; preds = %bb88 - br i1 false, label %bb250, label %bb166 - -bb166: ; preds = %bb154, %bb128 - %tmp175 = add i32 %idx.0, 1 ; [#uses=1] - %tmp177 = add i32 %tmp175, 0 ; [#uses=1] - %tmp181 = add i32 %tmp177, 0 ; [#uses=1] - %tmp183 = add i32 %i33.0, 1 ; [#uses=1] - br label %bb184 - -bb184: ; preds = %bb166, %entry - %i33.0 = phi i32 [ 0, %entry ], [ %tmp183, %bb166 ] ; [#uses=2] - %idx.0 = phi i32 [ 0, %entry ], [ %tmp181, %bb166 ] ; [#uses=2] - %tmp49 = icmp slt i32 %i33.0, 0 ; [#uses=1] - br i1 %tmp49, label %bb88, label %bb55 - -bb250: ; preds = %bb154, %bb128 - ret i32 %idx.0 -} diff --git a/llvm/test/Transforms/LoopUnswitch/2007-10-04-DomFrontier.ll b/llvm/test/Transforms/LoopUnswitch/2007-10-04-DomFrontier.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2007-10-04-DomFrontier.ll +++ /dev/null @@ -1,29 +0,0 @@ -; RUN: opt < %s -licm -loop-unroll -disable-output - -@resonant = external global i32 ; [#uses=2] - -define void @weightadj() { -entry: - br label %bb - -bb: ; preds = %bb158, %entry - store i32 0, i32* @resonant, align 4 - br i1 false, label %g.exit, label %bb158 - -g.exit: ; preds = %bb68, %bb - br i1 false, label %bb68, label %cond_true - -cond_true: ; preds = %g.exit - store i32 1, i32* @resonant, align 4 - br label %bb68 - -bb68: ; preds = %cond_true, %g.exit - %tmp71 = icmp slt i32 0, 0 ; [#uses=1] - br i1 %tmp71, label %g.exit, label %bb158 - -bb158: ; preds = %bb68, %bb - br i1 false, label %bb, label %return - -return: ; preds = %bb158 - ret void -} diff --git a/llvm/test/Transforms/LoopUnswitch/2008-06-02-DomInfo.ll b/llvm/test/Transforms/LoopUnswitch/2008-06-02-DomInfo.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2008-06-02-DomInfo.ll +++ /dev/null @@ -1,26 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -instcombine -gvn -verify-memoryssa -disable-output -; PR2372 -target triple = "i386-pc-linux-gnu" - -define i32 @func_3(i16 signext %p_5, i16 signext %p_6) nounwind { -entry: - %tmp3 = icmp eq i16 %p_5, 0 ; [#uses=1] - %tmp1314 = sext i16 %p_6 to i32 ; [#uses=1] - %tmp28 = icmp ugt i32 %tmp1314, 3 ; [#uses=1] - %bothcond = or i1 %tmp28, false ; [#uses=1] - br label %bb -bb: ; preds = %bb54, %entry - br i1 %tmp3, label %bb54, label %bb5 -bb5: ; preds = %bb - br i1 %bothcond, label %bb54, label %bb31 -bb31: ; preds = %bb5 - br label %bb54 -bb54: ; preds = %bb31, %bb5, %bb - br i1 false, label %bb64, label %bb -bb64: ; preds = %bb54 - %tmp6566 = sext i16 %p_6 to i32 ; [#uses=1] - %tmp68 = tail call i32 (...) @func_18( i32 1, i32 %tmp6566, i32 1 ) nounwind ; [#uses=0] - ret i32 undef -} - -declare i32 @func_18(...) diff --git a/llvm/test/Transforms/LoopUnswitch/2008-06-17-DomFrontier.ll b/llvm/test/Transforms/LoopUnswitch/2008-06-17-DomFrontier.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2008-06-17-DomFrontier.ll +++ /dev/null @@ -1,22 +0,0 @@ -; RUN: opt < %s -licm -loop-unswitch -enable-new-pm=0 -disable-output -@g_56 = external global i16 ; [#uses=2] - -define i32 @func_67(i32 %p_68, i8 signext %p_69, i8 signext %p_71) nounwind { -entry: - br label %bb -bb: ; preds = %bb44, %entry - br label %bb3 -bb3: ; preds = %bb36, %bb - %bothcond = or i1 false, false ; [#uses=1] - br i1 %bothcond, label %bb29, label %bb19 -bb19: ; preds = %bb3 - br i1 false, label %bb36, label %bb29 -bb29: ; preds = %bb19, %bb3 - ret i32 0 -bb36: ; preds = %bb19 - store i16 0, i16* @g_56, align 2 - br i1 false, label %bb44, label %bb3 -bb44: ; preds = %bb44, %bb36 - %tmp46 = load i16, i16* @g_56, align 2 ; [#uses=0] - br i1 false, label %bb, label %bb44 -} diff --git a/llvm/test/Transforms/LoopUnswitch/2008-11-03-Invariant.ll b/llvm/test/Transforms/LoopUnswitch/2008-11-03-Invariant.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2008-11-03-Invariant.ll +++ /dev/null @@ -1,41 +0,0 @@ -; REQUIRES: asserts -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -stats -disable-output 2>&1 | FileCheck %s -; PR 3170 - -define i32 @a(i32 %x, i32 %y) nounwind { -; CHECK: 1 loop-unswitch - Number of branches unswitched -; CHECK-NOT: Number of branches unswitched - -entry: - %0 = icmp ult i32 0, %y ; [#uses=1] - br i1 %0, label %bb.nph, label %bb4 - -bb.nph: ; preds = %entry - %1 = icmp eq i32 %x, 0 ; [#uses=1] - br label %bb - -bb: ; preds = %bb.nph, %bb3 - %i.01 = phi i32 [ %3, %bb3 ], [ 0, %bb.nph ] ; [#uses=1] - br i1 %1, label %bb2, label %bb1 - -bb1: ; preds = %bb - %2 = tail call i32 (...) @b() nounwind ; [#uses=0] - br label %bb2 - -bb2: ; preds = %bb, %bb1 - %3 = add i32 %i.01, 1 ; [#uses=2] - br label %bb3 - -bb3: ; preds = %bb2 - %i.0 = phi i32 [ %3, %bb2 ] ; [#uses=1] - %4 = icmp ult i32 %i.0, %y ; [#uses=1] - br i1 %4, label %bb, label %bb3.bb4_crit_edge - -bb3.bb4_crit_edge: ; preds = %bb3 - br label %bb4 - -bb4: ; preds = %bb3.bb4_crit_edge, %entry - ret i32 0 -} - -declare i32 @b(...) diff --git a/llvm/test/Transforms/LoopUnswitch/2010-11-18-LCSSA.ll b/llvm/test/Transforms/LoopUnswitch/2010-11-18-LCSSA.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2010-11-18-LCSSA.ll +++ /dev/null @@ -1,28 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -; PR8622 -@g_38 = external global i32, align 4 - -define void @func_67(i32 %p_68.coerce) nounwind { -entry: - br i1 true, label %for.end12, label %bb.nph - -bb.nph: ; preds = %entry - %g_38.promoted = load i32, i32* @g_38 - br label %for.body - -for.body: ; preds = %for.cond, %bb.nph - %tobool.i = icmp eq i32 %p_68.coerce, 1 - %xor4.i = xor i32 %p_68.coerce, 1 - %call1 = select i1 %tobool.i, i32 0, i32 %xor4.i - br label %for.cond - -for.cond: ; preds = %for.body - br i1 true, label %for.cond.for.end12_crit_edge, label %for.body - -for.cond.for.end12_crit_edge: ; preds = %for.cond - store i32 %call1, i32* @g_38 - br label %for.end12 - -for.end12: ; preds = %for.cond.for.end12_crit_edge, %entry - ret void -} diff --git a/llvm/test/Transforms/LoopUnswitch/2011-06-02-CritSwitch.ll b/llvm/test/Transforms/LoopUnswitch/2011-06-02-CritSwitch.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2011-06-02-CritSwitch.ll +++ /dev/null @@ -1,28 +0,0 @@ -; RUN: opt -loop-unswitch -enable-new-pm=0 -disable-output < %s -; PR10031 - -define i32 @test(i32 %command) { -entry: - br label %tailrecurse - -tailrecurse: ; preds = %if.then14, %tailrecurse, %entry - br i1 undef, label %if.then, label %tailrecurse - -if.then: ; preds = %tailrecurse - switch i32 %command, label %sw.bb [ - i32 2, label %land.lhs.true - i32 0, label %land.lhs.true - ] - -land.lhs.true: ; preds = %if.then, %if.then - br i1 undef, label %sw.bb, label %if.then14 - -if.then14: ; preds = %land.lhs.true - switch i32 %command, label %tailrecurse [ - i32 0, label %sw.bb - i32 1, label %sw.bb - ] - -sw.bb: ; preds = %if.then14 - unreachable -} diff --git a/llvm/test/Transforms/LoopUnswitch/2011-09-26-EHCrash.ll b/llvm/test/Transforms/LoopUnswitch/2011-09-26-EHCrash.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2011-09-26-EHCrash.ll +++ /dev/null @@ -1,63 +0,0 @@ -; RUN: opt < %s -sroa -loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output -; PR11016 -target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" -target triple = "x86_64-apple-macosx10.7.2" - -%class.MyContainer.1.3.19.29 = type { [6 x %class.MyMemVarClass.0.2.18.28*] } -%class.MyMemVarClass.0.2.18.28 = type { i32 } - -define void @_ZN11MyContainer1fEi(%class.MyContainer.1.3.19.29* %this, i32 %doit) uwtable ssp align 2 personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) { -entry: - br label %for.cond - -for.cond: ; preds = %for.inc, %entry - %inc1 = phi i32 [ %inc, %for.inc ], [ 0, %entry ] - %conv = sext i32 %inc1 to i64 - %cmp = icmp ult i64 %conv, 6 - br i1 %cmp, label %for.body, label %for.end - -for.body: ; preds = %for.cond - %tobool = icmp ne i32 %doit, 0 - br i1 %tobool, label %for.inc, label %if.then - -if.then: ; preds = %for.body - %idxprom = sext i32 %inc1 to i64 - %array_ = getelementptr inbounds %class.MyContainer.1.3.19.29, %class.MyContainer.1.3.19.29* %this, i32 0, i32 0 - %arrayidx = getelementptr inbounds [6 x %class.MyMemVarClass.0.2.18.28*], [6 x %class.MyMemVarClass.0.2.18.28*]* %array_, i32 0, i64 %idxprom - %tmp4 = load %class.MyMemVarClass.0.2.18.28*, %class.MyMemVarClass.0.2.18.28** %arrayidx, align 8 - %isnull = icmp eq %class.MyMemVarClass.0.2.18.28* %tmp4, null - br i1 %isnull, label %for.inc, label %delete.notnull - -delete.notnull: ; preds = %if.then - invoke void @_ZN13MyMemVarClassD1Ev(%class.MyMemVarClass.0.2.18.28* %tmp4) - to label %invoke.cont unwind label %lpad - -invoke.cont: ; preds = %delete.notnull - %0 = bitcast %class.MyMemVarClass.0.2.18.28* %tmp4 to i8* - call void @_ZdlPv(i8* %0) nounwind - br label %for.inc - -lpad: ; preds = %delete.notnull - %1 = landingpad { i8*, i32 } - cleanup - %2 = extractvalue { i8*, i32 } %1, 0 - %3 = extractvalue { i8*, i32 } %1, 1 - %4 = bitcast %class.MyMemVarClass.0.2.18.28* %tmp4 to i8* - call void @_ZdlPv(i8* %4) nounwind - %lpad.val = insertvalue { i8*, i32 } undef, i8* %2, 0 - %lpad.val7 = insertvalue { i8*, i32 } %lpad.val, i32 %3, 1 - resume { i8*, i32 } %lpad.val7 - -for.inc: ; preds = %invoke.cont, %if.then, %for.body - %inc = add nsw i32 %inc1, 1 - br label %for.cond - -for.end: ; preds = %for.cond - ret void -} - -declare void @_ZN13MyMemVarClassD1Ev(%class.MyMemVarClass.0.2.18.28*) - -declare i32 @__gxx_personality_v0(...) - -declare void @_ZdlPv(i8*) nounwind diff --git a/llvm/test/Transforms/LoopUnswitch/2011-11-18-SimpleSwitch.ll b/llvm/test/Transforms/LoopUnswitch/2011-11-18-SimpleSwitch.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2011-11-18-SimpleSwitch.ll +++ /dev/null @@ -1,94 +0,0 @@ -; REQUIRES: asserts -; RUN: opt -loop-unswitch -enable-new-pm=0 -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s -; RUN: opt -S -loop-unswitch -enable-new-pm=0 -verify-loop-info -verify-dom-info -verify-memoryssa < %s | FileCheck %s - -; STATS: 2 loop-unswitch - Number of switches unswitched - -; CHECK: %1 = icmp eq i32 %c, 1 -; CHECK-NEXT: br i1 %1, label %.split.us, label %..split_crit_edge - -; CHECK: ..split_crit_edge: ; preds = %0 -; CHECK-NEXT: br label %.split - -; CHECK: .split.us: ; preds = %0 -; CHECK-NEXT: br label %loop_begin.us - -; CHECK: loop_begin.us: ; preds = %loop_begin.backedge.us, %.split.us -; CHECK-NEXT: %var_val.us = load i32, i32* %var -; CHECK-NEXT: switch i32 1, label %default.us-lcssa.us [ -; CHECK-NEXT: i32 1, label %inc.us - -; CHECK: inc.us: ; preds = %loop_begin.us -; CHECK-NEXT: call void @incf() [[NOR_NUW:#[0-9]+]] -; CHECK-NEXT: br label %loop_begin.backedge.us - -; CHECK: .split: ; preds = %..split_crit_edge -; CHECK-NEXT: %2 = icmp eq i32 %c, 2 -; CHECK-NEXT: br i1 %2, label %.split.split.us, label %.split..split.split_crit_edge - -; CHECK: .split..split.split_crit_edge: ; preds = %.split -; CHECK-NEXT: br label %.split.split - -; CHECK: .split.split.us: ; preds = %.split -; CHECK-NEXT: br label %loop_begin.us1 - -; CHECK: loop_begin.us1: ; preds = %loop_begin.backedge.us5, %.split.split.us -; CHECK-NEXT: %var_val.us2 = load i32, i32* %var -; CHECK-NEXT: switch i32 2, label %default.us-lcssa.us-lcssa.us [ -; CHECK-NEXT: i32 1, label %inc.split.us -; CHECK-NEXT: i32 2, label %dec.us3 -; CHECK-NEXT: ] - -; CHECK: dec.us3: ; preds = %loop_begin.us1 -; CHECK-NEXT: call void @decf() [[NOR_NUW]] -; CHECK-NEXT: br label %loop_begin.backedge.us5 - -; CHECK: .split.split: ; preds = %.split..split.split_crit_edge -; CHECK-NEXT: br label %loop_begin - -; CHECK: loop_begin: ; preds = %loop_begin.backedge, %.split.split -; CHECK-NEXT: %var_val = load i32, i32* %var -; CHECK-NEXT: switch i32 %c, label %default.us-lcssa.us-lcssa [ -; CHECK-NEXT: i32 1, label %inc.split -; CHECK-NEXT: i32 2, label %dec.split -; CHECK-NEXT: ] - -; CHECK: inc.split: ; preds = %loop_begin -; CHECK-NEXT: br i1 true, label %us-unreachable.us-lcssa, label %inc - -; CHECK: dec.split: ; preds = %loop_begin -; CHECK-NEXT: br i1 true, label %us-unreachable6, label %dec - -define i32 @test(i32* %var) { - %mem = alloca i32 - store i32 2, i32* %mem - %c = load i32, i32* %mem - - br label %loop_begin - -loop_begin: - - %var_val = load i32, i32* %var - - switch i32 %c, label %default [ - i32 1, label %inc - i32 2, label %dec - ] - -inc: - call void @incf() noreturn nounwind - br label %loop_begin -dec: - call void @decf() noreturn nounwind - br label %loop_begin -default: - br label %loop_exit -loop_exit: - ret i32 0 -} - -declare void @incf() noreturn -declare void @decf() noreturn - -; CHECK: attributes #0 = { noreturn } -; CHECK: attributes [[NOR_NUW]] = { noreturn nounwind } diff --git a/llvm/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches-Threshold.ll b/llvm/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches-Threshold.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches-Threshold.ll +++ /dev/null @@ -1,87 +0,0 @@ -; REQUIRES: asserts -; RUN: opt -loop-unswitch -enable-new-pm=0 -loop-unswitch-threshold 13 -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s -; RUN: opt -S -loop-unswitch -enable-new-pm=0 -loop-unswitch-threshold 13 -verify-loop-info -verify-dom-info -verify-memoryssa < %s | FileCheck %s - -; STATS: 1 loop-unswitch - Number of switches unswitched - -; ModuleID = '../llvm/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll' - -; CHECK: %1 = icmp eq i32 %c, 1 -; CHECK-NEXT: br i1 %1, label %.split.us, label %..split_crit_edge - -; CHECK: ..split_crit_edge: ; preds = %0 -; CHECK-NEXT: br label %.split - -; CHECK: .split.us: ; preds = %0 -; CHECK-NEXT: br label %loop_begin.us - -; CHECK: loop_begin.us: ; preds = %loop_begin.backedge.us, %.split.us -; CHECK: switch i32 1, label %second_switch.us [ -; CHECK-NEXT: i32 1, label %inc.us - -; CHECK: second_switch.us: ; preds = %loop_begin.us -; CHECK-NEXT: switch i32 %d, label %default.us [ -; CHECK-NEXT: i32 1, label %inc.us -; CHECK-NEXT: ] - -; CHECK: inc.us: ; preds = %second_switch.us, %loop_begin.us -; CHECK-NEXT: call void @incf() [[NOR_NUW:#[0-9]+]] -; CHECK-NEXT: br label %loop_begin.backedge.us - -; CHECK: .split: ; preds = %..split_crit_edge -; CHECK-NEXT: br label %loop_begin - -; CHECK: loop_begin: ; preds = %loop_begin.backedge, %.split -; CHECK: switch i32 %c, label %second_switch [ -; CHECK-NEXT: i32 1, label %loop_begin.inc_crit_edge -; CHECK-NEXT: ] - -; CHECK: loop_begin.inc_crit_edge: ; preds = %loop_begin -; CHECK-NEXT: br i1 true, label %us-unreachable, label %inc - -; CHECK: second_switch: ; preds = %loop_begin -; CHECK-NEXT: switch i32 %d, label %default [ -; CHECK-NEXT: i32 1, label %inc -; CHECK-NEXT: ] - -; CHECK: inc: ; preds = %loop_begin.inc_crit_edge, %second_switch -; CHECK-NEXT: call void @incf() [[NOR_NUW]] -; CHECK-NEXT: br label %loop_begin.backedge - -define i32 @test(i32* %var) { - %mem = alloca i32 - store i32 2, i32* %mem - %c = load i32, i32* %mem - %d = load i32, i32* %mem - - br label %loop_begin - -loop_begin: - - %var_val = load i32, i32* %var - - switch i32 %c, label %second_switch [ - i32 1, label %inc - ] - -second_switch: - switch i32 %d, label %default [ - i32 1, label %inc - ] - -inc: - call void @incf() noreturn nounwind - br label %loop_begin - -default: - br label %loop_begin - -loop_exit: - ret i32 0 -} - -declare void @incf() noreturn -declare void @decf() noreturn - -; CHECK: attributes #0 = { noreturn } -; CHECK: attributes [[NOR_NUW]] = { noreturn nounwind } diff --git a/llvm/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll b/llvm/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll +++ /dev/null @@ -1,141 +0,0 @@ -; REQUIRES: asserts -; RUN: opt -loop-unswitch -enable-new-pm=0 -loop-unswitch-threshold 1000 -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s -; RUN: opt -S -loop-unswitch -enable-new-pm=0 -loop-unswitch-threshold 1000 -verify-loop-info -verify-dom-info -verify-memoryssa < %s | FileCheck %s - -; STATS: 3 loop-unswitch - Number of switches unswitched - -; CHECK: %1 = icmp eq i32 %c, 1 -; CHECK-NEXT: br i1 %1, label %.split.us, label %..split_crit_edge - -; CHECK: ..split_crit_edge: ; preds = %0 -; CHECK-NEXT: br label %.split - -; CHECK: .split.us: ; preds = %0 -; CHECK-NEXT: %2 = icmp eq i32 %d, 1 -; CHECK-NEXT: br i1 %2, label %.split.us.split.us, label %.split.us..split.us.split_crit_edge - -; CHECK: .split.us..split.us.split_crit_edge: ; preds = %.split.us -; CHECK-NEXT: br label %.split.us.split - -; CHECK: .split.us.split.us: ; preds = %.split.us -; CHECK-NEXT: br label %loop_begin.us.us - -; CHECK: loop_begin.us.us: ; preds = %loop_begin.backedge.us.us, %.split.us.split.us -; CHECK-NEXT: %var_val.us.us = load i32, i32* %var -; CHECK-NEXT: switch i32 1, label %second_switch.us.us [ -; CHECK-NEXT: i32 1, label %inc.us.us - -; CHECK: second_switch.us.us: ; preds = %loop_begin.us.us -; CHECK-NEXT: switch i32 1, label %default.us.us [ -; CHECK-NEXT: i32 1, label %inc.us.us - -; CHECK: inc.us.us: ; preds = %second_switch.us.us, %loop_begin.us.us -; CHECK-NEXT: call void @incf() [[NOR_NUW:#[0-9]+]] -; CHECK-NEXT: br label %loop_begin.backedge.us.us - -; CHECK: .split.us.split: ; preds = %.split.us..split.us.split_crit_edge -; CHECK-NEXT: br label %loop_begin.us - -; CHECK: loop_begin.us: ; preds = %loop_begin.backedge.us, %.split.us.split -; CHECK-NEXT: %var_val.us = load i32, i32* %var -; CHECK-NEXT: switch i32 1, label %second_switch.us [ -; CHECK-NEXT: i32 1, label %inc.us - -; CHECK: second_switch.us: ; preds = %loop_begin.us -; CHECK-NEXT: switch i32 %d, label %default.us [ -; CHECK-NEXT: i32 1, label %second_switch.us.inc.us_crit_edge -; CHECK-NEXT: ] - -; CHECK: second_switch.us.inc.us_crit_edge: ; preds = %second_switch.us -; CHECK-NEXT: br i1 true, label %us-unreachable8, label %inc.us - -; CHECK: inc.us: ; preds = %second_switch.us.inc.us_crit_edge, %loop_begin.us -; CHECK-NEXT: call void @incf() [[NOR_NUW]] -; CHECK-NEXT: br label %loop_begin.backedge.us - -; CHECK: .split: ; preds = %..split_crit_edge -; CHECK-NEXT: %3 = icmp eq i32 %d, 1 -; CHECK-NEXT: br i1 %3, label %.split.split.us, label %.split..split.split_crit_edge - -; CHECK: .split..split.split_crit_edge: ; preds = %.split -; CHECK-NEXT: br label %.split.split - -; CHECK: .split.split.us: ; preds = %.split -; CHECK-NEXT: br label %loop_begin.us1 - -; CHECK: loop_begin.us1: ; preds = %loop_begin.backedge.us6, %.split.split.us -; CHECK-NEXT: %var_val.us2 = load i32, i32* %var -; CHECK-NEXT: switch i32 %c, label %second_switch.us3 [ -; CHECK-NEXT: i32 1, label %loop_begin.inc_crit_edge.us -; CHECK-NEXT: ] - -; CHECK: second_switch.us3: ; preds = %loop_begin.us1 -; CHECK-NEXT: switch i32 1, label %default.us5 [ -; CHECK-NEXT: i32 1, label %inc.us4 -; CHECK-NEXT: ] - -; CHECK: inc.us4: ; preds = %loop_begin.inc_crit_edge.us, %second_switch.us3 -; CHECK-NEXT: call void @incf() [[NOR_NUW]] -; CHECK-NEXT: br label %loop_begin.backedge.us6 - -; CHECK: loop_begin.inc_crit_edge.us: ; preds = %loop_begin.us1 -; CHECK-NEXT: br i1 true, label %us-unreachable.us-lcssa.us, label %inc.us4 - -; CHECK: .split.split: ; preds = %.split..split.split_crit_edge -; CHECK-NEXT: br label %loop_begin - -; CHECK: loop_begin: ; preds = %loop_begin.backedge, %.split.split -; CHECK-NEXT: %var_val = load i32, i32* %var -; CHECK-NEXT: switch i32 %c, label %second_switch [ -; CHECK-NEXT: i32 1, label %loop_begin.inc_crit_edge -; CHECK-NEXT: ] - -; CHECK: loop_begin.inc_crit_edge: ; preds = %loop_begin -; CHECK-NEXT: br i1 true, label %us-unreachable.us-lcssa, label %inc - -; CHECK: second_switch: ; preds = %loop_begin -; CHECK-NEXT: switch i32 %d, label %default [ -; CHECK-NEXT: i32 1, label %second_switch.inc_crit_edge -; CHECK-NEXT: ] - -; CHECK: second_switch.inc_crit_edge: ; preds = %second_switch -; CHECK-NEXT: br i1 true, label %us-unreachable7, label %inc - - -define i32 @test(i32* %var) { - %mem = alloca i32 - store i32 2, i32* %mem - %c = load i32, i32* %mem - %d = load i32, i32* %mem - - br label %loop_begin - -loop_begin: - - %var_val = load i32, i32* %var - - switch i32 %c, label %second_switch [ - i32 1, label %inc - ] - -second_switch: - switch i32 %d, label %default [ - i32 1, label %inc - ] - -inc: - call void @incf() noreturn nounwind - br label %loop_begin - -default: - br label %loop_begin - -loop_exit: - ret i32 0 -} - -declare void @incf() noreturn -declare void @decf() noreturn - -; CHECK: attributes #0 = { noreturn } -; CHECK: attributes [[NOR_NUW]] = { noreturn nounwind } diff --git a/llvm/test/Transforms/LoopUnswitch/2012-04-02-IndirectBr.ll b/llvm/test/Transforms/LoopUnswitch/2012-04-02-IndirectBr.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2012-04-02-IndirectBr.ll +++ /dev/null @@ -1,41 +0,0 @@ -; RUN: opt < %s -S -loop-unswitch -enable-new-pm=0 -verify-loop-info -verify-dom-info -verify-memoryssa | FileCheck %s -; PR12343: -loop-unswitch -enable-new-pm=0 crash on indirect branch - -; CHECK: %0 = icmp eq i64 undef, 0 -; CHECK-NEXT: br i1 %0, label %"5", label %"4" - -; CHECK: "5": ; preds = %entry -; CHECK-NEXT: br label %"16" - -; CHECK: "16": ; preds = %"22", %"5" -; CHECK-NEXT: indirectbr i8* undef, [label %"22", label %"33"] - -; CHECK: "22": ; preds = %"16" -; CHECK-NEXT: br i1 %0, label %"16", label %"26" - -; CHECK: "26": ; preds = %"22" -; CHECK-NEXT: unreachable - -define void @foo() { -entry: - %0 = icmp eq i64 undef, 0 - br i1 %0, label %"5", label %"4" - -"4": ; preds = %entry - unreachable - -"5": ; preds = %entry - br label %"16" - -"16": ; preds = %"22", %"5" - indirectbr i8* undef, [label %"22", label %"33"] - -"22": ; preds = %"16" - br i1 %0, label %"16", label %"26" - -"26": ; preds = %"22" - unreachable - -"33": ; preds = %"16" - unreachable -} diff --git a/llvm/test/Transforms/LoopUnswitch/2012-04-30-LoopUnswitch-LPad-Crash.ll b/llvm/test/Transforms/LoopUnswitch/2012-04-30-LoopUnswitch-LPad-Crash.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2012-04-30-LoopUnswitch-LPad-Crash.ll +++ /dev/null @@ -1,97 +0,0 @@ -; RUN: opt < %s -basic-aa -instcombine -inline -function-attrs -licm -loop-unswitch -enable-new-pm=0 -gvn -verify -; PR12573 -target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" -target triple = "x86_64-apple-macosx10.7.0" - -%class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379 = type { %class.C.23.43.67.103.139.159.179.199.239.243.247.251.263.295.303.339.347.376*, %class.B.21.41.65.101.137.157.177.197.237.241.245.249.261.293.301.337.345.378 } -%class.C.23.43.67.103.139.159.179.199.239.243.247.251.263.295.303.339.347.376 = type { %class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379* } -%class.B.21.41.65.101.137.157.177.197.237.241.245.249.261.293.301.337.345.378 = type { %class.A.20.40.64.100.136.156.176.196.236.240.244.248.260.292.300.336.344.377* } -%class.A.20.40.64.100.136.156.176.196.236.240.244.248.260.292.300.336.344.377 = type { i8 } - -define void @_Z23get_reconstruction_pathv() uwtable ssp personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) { -entry: - %c = alloca %class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379, align 8 - br label %for.cond - -for.cond: ; preds = %for.end, %entry - invoke void @_ZN1DptEv(%class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379* %c) - to label %invoke.cont unwind label %lpad - -invoke.cont: ; preds = %for.cond - invoke void @_ZN1C3endEv() - to label %for.cond3 unwind label %lpad - -for.cond3: ; preds = %invoke.cont6, %invoke.cont - invoke void @_ZN1DptEv(%class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379* %c) - to label %invoke.cont4 unwind label %lpad - -invoke.cont4: ; preds = %for.cond3 - invoke void @_ZN1C3endEv() - to label %invoke.cont6 unwind label %lpad - -invoke.cont6: ; preds = %invoke.cont4 - br i1 undef, label %for.cond3, label %for.end - -lpad: ; preds = %for.end, %invoke.cont4, %for.cond3, %invoke.cont, %for.cond - %0 = landingpad { i8*, i32 } - cleanup - resume { i8*, i32 } undef - -for.end: ; preds = %invoke.cont6 - invoke void @_ZN1C13_M_insert_auxER1D() - to label %for.cond unwind label %lpad -} - -define void @_ZN1DptEv(%class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379* %this) uwtable ssp align 2 { -entry: - %this.addr = alloca %class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379*, align 8 - store %class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379* %this, %class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379** %this.addr, align 8 - %this1 = load %class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379*, %class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379** %this.addr - %px = getelementptr inbounds %class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379, %class.D.22.42.66.102.138.158.178.198.238.242.246.250.262.294.302.338.346.379* %this1, i32 0, i32 0 - %0 = load %class.C.23.43.67.103.139.159.179.199.239.243.247.251.263.295.303.339.347.376*, %class.C.23.43.67.103.139.159.179.199.239.243.247.251.263.295.303.339.347.376** %px, align 8 - %tobool = icmp ne %class.C.23.43.67.103.139.159.179.199.239.243.247.251.263.295.303.339.347.376* %0, null - br i1 %tobool, label %cond.end, label %cond.false - -cond.false: ; preds = %entry - call void @_Z10__assert13v() noreturn - unreachable - -cond.end: ; preds = %entry - ret void -} - -declare i32 @__gxx_personality_v0(...) - -declare void @_ZN1C3endEv() - -define void @_ZN1C13_M_insert_auxER1D() uwtable ssp align 2 { -entry: - ret void -} - -define void @_ZN1DD1Ev() unnamed_addr uwtable inlinehint ssp align 2 { -entry: - ret void -} - -define void @_ZN1DD2Ev() unnamed_addr uwtable inlinehint ssp align 2 { -entry: - ret void -} - -define void @_ZN1BD1Ev() unnamed_addr uwtable ssp align 2 { -entry: - ret void -} - -define void @_ZN1BD2Ev() unnamed_addr uwtable ssp align 2 { -entry: - ret void -} - -define void @_ZN1BaSERS_() uwtable ssp align 2 { -entry: - unreachable -} - -declare void @_Z10__assert13v() noreturn diff --git a/llvm/test/Transforms/LoopUnswitch/2012-05-20-Phi.ll b/llvm/test/Transforms/LoopUnswitch/2012-05-20-Phi.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2012-05-20-Phi.ll +++ /dev/null @@ -1,25 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output -; PR12887 -target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" -target triple = "x86_64-unknown-linux-gnu" - -@a = common global i32 0, align 4 -@c = common global i32 0, align 4 -@b = common global i32 0, align 4 - -define void @func() noreturn nounwind uwtable { -entry: - %0 = load i32, i32* @a, align 4 - %tobool = icmp eq i32 %0, 0 - %1 = load i32, i32* @b, align 4 - br label %while.body - -while.body: ; preds = %while.body, %entry - %d.0 = phi i8 [ undef, %entry ], [ %conv2, %while.body ] - %conv = sext i8 %d.0 to i32 - %cond = select i1 %tobool, i32 0, i32 %conv - %conv11 = zext i8 %d.0 to i32 - %add = add i32 %1, %conv11 - %conv2 = trunc i32 %add to i8 - br label %while.body -} diff --git a/llvm/test/Transforms/LoopUnswitch/2015-06-17-Metadata.ll b/llvm/test/Transforms/LoopUnswitch/2015-06-17-Metadata.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2015-06-17-Metadata.ll +++ /dev/null @@ -1,104 +0,0 @@ -; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -;RUN: opt -loop-unswitch -enable-new-pm=0 -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S < %s | FileCheck %s - -define i32 @foo(i32 %a, i32 %b) { -; CHECK-LABEL: @foo( -; CHECK-NEXT: entry: -; CHECK-NEXT: [[CMP0:%.*]] = icmp sgt i32 [[B:%.*]], 0 -; CHECK-NEXT: br i1 [[CMP0]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]] -; CHECK: for.body.preheader: -; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], 12345 -; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_US:%.*]], label [[FOR_BODY:%.*]], !prof [[PROF0:![0-9]+]] -; CHECK: for.body.us: -; CHECK-NEXT: [[INC_I_US:%.*]] = phi i32 [ [[INC_US:%.*]], [[FOR_BODY_US]] ], [ 0, [[FOR_BODY_PREHEADER]] ] -; CHECK-NEXT: [[MUL_I_US:%.*]] = phi i32 [ [[B]], [[FOR_BODY_US]] ], [ 3, [[FOR_BODY_PREHEADER]] ] -; CHECK-NEXT: [[ADD_I_US:%.*]] = phi i32 [ [[ADD_US:%.*]], [[FOR_BODY_US]] ], [ [[A]], [[FOR_BODY_PREHEADER]] ] -; CHECK-NEXT: [[ADD_US]] = add nsw i32 [[ADD_I_US]], 123 -; CHECK-NEXT: [[INC_US]] = add nuw nsw i32 [[INC_I_US]], 1 -; CHECK-NEXT: [[EXITCOND_US:%.*]] = icmp eq i32 [[INC_US]], [[B]] -; CHECK-NEXT: br i1 [[EXITCOND_US]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY_US]] -; CHECK: for.body: -; CHECK-NEXT: [[INC_I:%.*]] = phi i32 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, [[FOR_BODY_PREHEADER]] ] -; CHECK-NEXT: [[MUL_I:%.*]] = phi i32 [ [[MUL:%.*]], [[FOR_BODY]] ], [ 3, [[FOR_BODY_PREHEADER]] ] -; CHECK-NEXT: [[ADD_I:%.*]] = phi i32 [ [[A]], [[FOR_BODY]] ], [ [[A]], [[FOR_BODY_PREHEADER]] ] -; CHECK-NEXT: [[MUL]] = mul nsw i32 [[MUL_I]], [[B]] -; CHECK-NEXT: [[INC]] = add nuw nsw i32 [[INC_I]], 1 -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[INC]], [[B]] -; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY]] -; CHECK: for.cond.cleanup: -; CHECK-NEXT: [[T2:%.*]] = phi i32 [ [[B]], [[ENTRY:%.*]] ], [ [[B]], [[FOR_BODY_US]] ], [ [[MUL]], [[FOR_BODY]] ] -; CHECK-NEXT: [[T1:%.*]] = phi i32 [ [[A]], [[ENTRY]] ], [ [[ADD_US]], [[FOR_BODY_US]] ], [ [[A]], [[FOR_BODY]] ] -; CHECK-NEXT: [[ADD3:%.*]] = add nsw i32 [[T2]], [[T1]] -; CHECK-NEXT: ret i32 [[ADD3]] -; -entry: - br label %for.body.lr.ph - -for.body.lr.ph: ; preds = %entry - %cmp0 = icmp sgt i32 %b, 0 - br i1 %cmp0, label %for.body, label %for.cond.cleanup - -for.body: ; preds = %for.inc, %for.body.lr.ph - %inc.i = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ] - %mul.i = phi i32 [ 3, %for.body.lr.ph ], [ %mul.p, %for.inc ] - %add.i = phi i32 [ %a, %for.body.lr.ph ], [ %add.p, %for.inc ] - %cmp1 = icmp eq i32 %a, 12345 - br i1 %cmp1, label %if.then, label %if.else, !prof !0 -if.then: ; preds = %for.body - %add = add nsw i32 %add.i, 123 - br label %for.inc - -if.else: ; preds = %for.body - %mul = mul nsw i32 %mul.i, %b - br label %for.inc -for.inc: ; preds = %if.then, %if.else - %mul.p = phi i32 [ %b, %if.then ], [ %mul, %if.else ] - %add.p = phi i32 [ %add, %if.then ], [ %a, %if.else ] - %inc = add nuw nsw i32 %inc.i, 1 - %exitcond = icmp eq i32 %inc, %b - br i1 %exitcond, label %for.cond.cleanup, label %for.body - -for.cond.cleanup: ; preds = %for.inc, %for.body.lr.ph - %t2 = phi i32 [ %b, %for.body.lr.ph ], [ %mul.p, %for.inc ] - %t1 = phi i32 [ %a, %for.body.lr.ph ], [ %add.p, %for.inc ] - %add3 = add nsw i32 %t2, %t1 - ret i32 %add3 -} - -define void @foo_swapped(i32 %a, i32 %b) { -; CHECK-LABEL: @foo_swapped( -; CHECK-NEXT: entry: -; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 1, 2 -; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY:%.*]], label [[FOR_COND_CLEANUP_SPLIT:%.*]], !prof [[PROF1:![0-9]+]] -; CHECK: for.body: -; CHECK-NEXT: [[INC_I:%.*]] = phi i32 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ] -; CHECK-NEXT: [[ADD_I:%.*]] = phi i32 [ [[ADD:%.*]], [[FOR_BODY]] ], [ 100, [[ENTRY]] ] -; CHECK-NEXT: [[INC]] = add nuw nsw i32 [[INC_I]], 1 -; CHECK-NEXT: [[ADD]] = add nsw i32 [[A:%.*]], [[ADD_I]] -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[INC]], [[B:%.*]] -; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP_SPLIT]], label [[FOR_BODY]] -; CHECK: for.cond.cleanup.split: -; CHECK-NEXT: ret void -; -entry: - br label %for.body -for.body: ; preds = %for.inc, %entry - %inc.i = phi i32 [ 0, %entry ], [ %inc, %if.then ] - %add.i = phi i32 [ 100, %entry ], [ %add, %if.then ] - %inc = add nuw nsw i32 %inc.i, 1 - %cmp1 = icmp eq i32 1, 2 - br i1 %cmp1, label %if.then, label %for.cond.cleanup, !prof !0 - -if.then: ; preds = %for.body - %add = add nsw i32 %a, %add.i - - %exitcond = icmp eq i32 %inc, %b - br i1 %exitcond, label %for.cond.cleanup, label %for.body - -for.cond.cleanup: ; preds = %for.inc, %for.body.lr.ph, %for.body - ret void -} -!0 = !{!"branch_weights", i32 64, i32 4} - -;CHECK: !0 = !{!"branch_weights", i32 64, i32 4} -;CHECK: !1 = !{!"branch_weights", i32 4, i32 64} diff --git a/llvm/test/Transforms/LoopUnswitch/2015-09-18-Addrspace.ll b/llvm/test/Transforms/LoopUnswitch/2015-09-18-Addrspace.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/2015-09-18-Addrspace.ll +++ /dev/null @@ -1,28 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -S | FileCheck %s - -; In cases where two address spaces do not have the same size pointer, the -; input for the addrspacecast should not be used as a substitute for itself -; when manipulating the pointer. - -target datalayout = "e-m:e-p:16:16-p1:32:16-i32:16-i64:16-n8:16" - -define void @foo() { -; CHECK-LABEL: @foo -entry: - %arrayidx.i1 = getelementptr inbounds i16, i16* undef, i16 undef - %arrayidx.i = addrspacecast i16* %arrayidx.i1 to i16 addrspace(1)* - br i1 undef, label %for.body.i, label %bar.exit - -for.body.i: ; preds = %for.body.i, %entry -; When we call makeLoopInvariant (i.e. trivial LICM) on this load, it -; will try to find the base object to prove deferenceability. If we look -; through the addrspacecast, we'll fail an assertion about bitwidths matching -; CHECK-LABEL: for.body.i -; CHECK: %0 = load i16, i16 addrspace(1)* %arrayidx.i, align 2 - %0 = load i16, i16 addrspace(1)* %arrayidx.i, align 2 - %cmp1.i = icmp eq i16 %0, 0 - br i1 %cmp1.i, label %bar.exit, label %for.body.i - -bar.exit: ; preds = %for.body.i, %entry - ret void -} diff --git a/llvm/test/Transforms/LoopUnswitch/AMDGPU/divergent-unswitch.ll b/llvm/test/Transforms/LoopUnswitch/AMDGPU/divergent-unswitch.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/AMDGPU/divergent-unswitch.ll +++ /dev/null @@ -1,45 +0,0 @@ -; RUN: opt -mtriple=amdgcn-- -O3 -S %s | FileCheck %s - -; Check that loop unswitch does not happen if condition is divergent. - -; CHECK-LABEL: {{^}}define amdgpu_kernel void @divergent_unswitch -; CHECK: entry: -; CHECK: icmp -; CHECK: [[IF_COND:%[a-z0-9]+]] = icmp {{.*}} 567890 -; CHECK: br label -; CHECK: br i1 [[IF_COND]] - -define amdgpu_kernel void @divergent_unswitch(i32 * nocapture %out, i32 %n) { -entry: - %cmp9 = icmp sgt i32 %n, 0 - br i1 %cmp9, label %for.body.lr.ph, label %for.cond.cleanup - -for.body.lr.ph: ; preds = %entry - %call = tail call i32 @llvm.amdgcn.workitem.id.x() #0 - %cmp2 = icmp eq i32 %call, 567890 - br label %for.body - -for.cond.cleanup.loopexit: ; preds = %for.inc - br label %for.cond.cleanup - -for.cond.cleanup: ; preds = %for.cond.cleanup.loopexit, %entry - ret void - -for.body: ; preds = %for.inc, %for.body.lr.ph - %i.010 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ] - br i1 %cmp2, label %if.then, label %for.inc - -if.then: ; preds = %for.body - %arrayidx = getelementptr inbounds i32, i32 * %out, i32 %i.010 - store i32 %i.010, i32 * %arrayidx, align 4 - br label %for.inc - -for.inc: ; preds = %for.body, %if.then - %inc = add nuw nsw i32 %i.010, 1 - %exitcond = icmp eq i32 %inc, %n - br i1 %exitcond, label %for.cond.cleanup.loopexit, label %for.body -} - -declare i32 @llvm.amdgcn.workitem.id.x() #0 - -attributes #0 = { nounwind readnone } diff --git a/llvm/test/Transforms/LoopUnswitch/AMDGPU/lit.local.cfg b/llvm/test/Transforms/LoopUnswitch/AMDGPU/lit.local.cfg deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/AMDGPU/lit.local.cfg +++ /dev/null @@ -1,2 +0,0 @@ -if not 'AMDGPU' in config.root.targets: - config.unsupported = True diff --git a/llvm/test/Transforms/LoopUnswitch/AMDGPU/uniform-unswitch.ll b/llvm/test/Transforms/LoopUnswitch/AMDGPU/uniform-unswitch.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/AMDGPU/uniform-unswitch.ll +++ /dev/null @@ -1,53 +0,0 @@ -; RUN: opt -mtriple=amdgcn-- -passes='default' -S %s | FileCheck %s -; XFAIL: * - -; Check that loop unswitch happened and condition hoisted out of the loop. -; Condition is uniform so even targets with divergence should perform unswitching. - -; This fails with the new pass manager: -; https://bugs.llvm.org/show_bug.cgi?id=48819 -; The correct behaviour (allow uniform non-trivial branches to be -; unswitched on all targets) requires access to the function-level -; divergence analysis from a loop transform, which is currently not -; supported in the new pass manager. - -; CHECK-LABEL: {{^}}define amdgpu_kernel void @uniform_unswitch -; CHECK: entry: -; CHECK-NEXT: [[LOOP_COND:%[a-z0-9]+]] = icmp -; CHECK-NEXT: [[IF_COND:%[a-z0-9]+]] = icmp eq i32 %x, 123456 -; CHECK-NEXT: and i1 [[LOOP_COND]], [[IF_COND]] -; CHECK-NEXT: br i1 - -define amdgpu_kernel void @uniform_unswitch(i32 * nocapture %out, i32 %n, i32 %x) { -entry: - %cmp6 = icmp sgt i32 %n, 0 - br i1 %cmp6, label %for.body.lr.ph, label %for.cond.cleanup - -for.body.lr.ph: ; preds = %entry - %cmp1 = icmp eq i32 %x, 123456 - br label %for.body - -for.cond.cleanup.loopexit: ; preds = %for.inc - br label %for.cond.cleanup - -for.cond.cleanup: ; preds = %for.cond.cleanup.loopexit, %entry - ret void - -for.body: ; preds = %for.inc, %for.body.lr.ph - %i.07 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ] - br i1 %cmp1, label %if.then, label %for.inc - -if.then: ; preds = %for.body - %arrayidx = getelementptr inbounds i32, i32 * %out, i32 %i.07 - store i32 %i.07, i32 * %arrayidx, align 4 - br label %for.inc - -for.inc: ; preds = %for.body, %if.then - %inc = add nuw nsw i32 %i.07, 1 - %exitcond = icmp eq i32 %inc, %n - br i1 %exitcond, label %for.cond.cleanup.loopexit, label %for.body -} - -declare i32 @llvm.amdgcn.workitem.id.x() #0 - -attributes #0 = { nounwind readnone } diff --git a/llvm/test/Transforms/LoopUnswitch/LIV-loop-condtion.ll b/llvm/test/Transforms/LoopUnswitch/LIV-loop-condtion.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/LIV-loop-condtion.ll +++ /dev/null @@ -1,28 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -loop-unswitch-threshold=0 -verify-memoryssa -S 2>&1 | FileCheck %s - -; This is to test trivial loop unswitch only happens when trivial condition -; itself is an LIV loop condition (not partial LIV which could occur in and/or). - -define i32 @test(i1 %cond1, i32 %var1) { -entry: - br label %loop_begin - -loop_begin: - %var3 = phi i32 [%var1, %entry], [%var2, %do_something] - %cond2 = icmp eq i32 %var3, 10 - %cond.and = and i1 %cond1, %cond2 - -; %cond.and only has %cond1 as LIV so no unswitch should happen. -; CHECK: br i1 %cond.and, label %do_something, label %loop_exit - br i1 %cond.and, label %do_something, label %loop_exit - -do_something: - %var2 = add i32 %var3, 1 - call void @some_func() noreturn nounwind - br label %loop_begin - -loop_exit: - ret i32 0 -} - -declare void @some_func() noreturn diff --git a/llvm/test/Transforms/LoopUnswitch/basictest.ll b/llvm/test/Transforms/LoopUnswitch/basictest.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/basictest.ll +++ /dev/null @@ -1,318 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-loop-info -verify-memoryssa -S < %s 2>&1 | FileCheck %s - -define i32 @test(i32* %A, i1 %C) { -entry: - br label %no_exit -no_exit: ; preds = %no_exit.backedge, %entry - %i.0.0 = phi i32 [ 0, %entry ], [ %i.0.0.be, %no_exit.backedge ] ; [#uses=3] - %gep.upgrd.1 = zext i32 %i.0.0 to i64 ; [#uses=1] - %tmp.7 = getelementptr i32, i32* %A, i64 %gep.upgrd.1 ; [#uses=4] - %tmp.13 = load i32, i32* %tmp.7 ; [#uses=2] - %tmp.14 = add i32 %tmp.13, 1 ; [#uses=1] - store i32 %tmp.14, i32* %tmp.7 - br i1 %C, label %then, label %endif -then: ; preds = %no_exit - %tmp.29 = load i32, i32* %tmp.7 ; [#uses=1] - %tmp.30 = add i32 %tmp.29, 2 ; [#uses=1] - store i32 %tmp.30, i32* %tmp.7 - %inc9 = add i32 %i.0.0, 1 ; [#uses=2] - %tmp.112 = icmp ult i32 %inc9, 100000 ; [#uses=1] - br i1 %tmp.112, label %no_exit.backedge, label %return -no_exit.backedge: ; preds = %endif, %then - %i.0.0.be = phi i32 [ %inc9, %then ], [ %inc, %endif ] ; [#uses=1] - br label %no_exit -endif: ; preds = %no_exit - %inc = add i32 %i.0.0, 1 ; [#uses=2] - %tmp.1 = icmp ult i32 %inc, 100000 ; [#uses=1] - br i1 %tmp.1, label %no_exit.backedge, label %return -return: ; preds = %endif, %then - ret i32 %tmp.13 -} - -; This simple test would normally unswitch, but should be inhibited by the presence of -; the noduplicate call. - -; CHECK-LABEL: @test2( -define i32 @test2(i32* %var) { - %mem = alloca i32 - store i32 2, i32* %mem - %c = load i32, i32* %mem - - br label %loop_begin - -loop_begin: - - %var_val = load i32, i32* %var - - switch i32 %c, label %default [ - i32 1, label %inc - i32 2, label %dec - ] - -inc: - call void @incf() noreturn nounwind - br label %loop_begin -dec: -; CHECK: call void @decf() -; CHECK-NOT: call void @decf() - call void @decf() noreturn nounwind noduplicate - br label %loop_begin -default: - br label %loop_exit -loop_exit: - ret i32 0 -; CHECK: } -} - -; This simple test would normally unswitch, but should be inhibited by the presence of -; the convergent call that is not control-dependent on the unswitch condition. - -; CHECK-LABEL: @test3( -define i32 @test3(i32* %var) { - %mem = alloca i32 - store i32 2, i32* %mem - %c = load i32, i32* %mem - - br label %loop_begin - -loop_begin: - - %var_val = load i32, i32* %var - -; CHECK: call void @conv() -; CHECK-NOT: call void @conv() - call void @conv() convergent - - switch i32 %c, label %default [ - i32 1, label %inc - i32 2, label %dec - ] - -inc: - call void @incf() noreturn nounwind - br label %loop_begin -dec: - call void @decf() noreturn nounwind - br label %loop_begin -default: - br label %loop_exit -loop_exit: - ret i32 0 -; CHECK: } -} - -; Make sure we unswitch %a == 0 out of the loop. -; -; CHECK: define void @and_i2_as_switch_input(i2 -; CHECK: entry: -; This is an indication that the loop has been unswitched. -; CHECK: icmp eq i2 %a, 0 -; CHECK: br -; There should be no more unswitching after the 1st unswitch. -; CHECK-NOT: icmp eq -; CHECK: ret -define void @and_i2_as_switch_input(i2 %a) { -entry: - br label %for.body - -for.body: - %i = phi i2 [ 0, %entry ], [ %inc, %for.inc ] - %and = and i2 %a, %i - %and1 = and i2 %and, %i - switch i2 %and1, label %sw.default [ - i2 0, label %sw.bb - i2 1, label %sw.bb1 - ] - -sw.bb: - br label %sw.epilog - -sw.bb1: - br label %sw.epilog - -sw.default: - br label %sw.epilog - -sw.epilog: - br label %for.inc - -for.inc: - %inc = add nsw i2 %i, 1 - %cmp = icmp slt i2 %inc, 3 - br i1 %cmp, label %for.body, label %for.end - -for.end: - ret void -} - -; Make sure we unswitch %a == !0 out of the loop. -; -; CHECK: define void @or_i2_as_switch_input(i2 -; CHECK: entry: -; This is an indication that the loop has been unswitched. -; CHECK: icmp eq i2 %a, -1 -; CHECK: br -; There should be no more unswitching after the 1st unswitch. -; CHECK-NOT: icmp eq -; CHECK: ret -define void @or_i2_as_switch_input(i2 %a) { -entry: - br label %for.body - -for.body: - %i = phi i2 [ 0, %entry ], [ %inc, %for.inc ] - %or = or i2 %a, %i - %or1 = or i2 %or, %i - switch i2 %or1, label %sw.default [ - i2 2, label %sw.bb - i2 3, label %sw.bb1 - ] - -sw.bb: - br label %sw.epilog - -sw.bb1: - br label %sw.epilog - -sw.default: - br label %sw.epilog - -sw.epilog: - br label %for.inc - -for.inc: - %inc = add nsw i2 %i, 1 - %cmp = icmp slt i2 %inc, 3 - br i1 %cmp, label %for.body, label %for.end - -for.end: - ret void -} - -; Make sure we unswitch %a == !0 out of the loop. Even we do not -; have it as a case value. Unswitching it out allows us to simplify -; the or operator chain. -; -; CHECK: define void @or_i2_as_switch_input_unswitch_default(i2 -; CHECK: entry: -; This is an indication that the loop has been unswitched. -; CHECK: icmp eq i2 %a, -1 -; CHECK: br -; There should be no more unswitching after the 1st unswitch. -; CHECK-NOT: icmp eq -; CHECK: ret -define void @or_i2_as_switch_input_unswitch_default(i2 %a) { -entry: - br label %for.body - -for.body: - %i = phi i2 [ 0, %entry ], [ %inc, %for.inc ] - %or = or i2 %a, %i - %or1 = or i2 %or, %i - switch i2 %or1, label %sw.default [ - i2 1, label %sw.bb - i2 2, label %sw.bb1 - ] - -sw.bb: - br label %sw.epilog - -sw.bb1: - br label %sw.epilog - -sw.default: - br label %sw.epilog - -sw.epilog: - br label %for.inc - -for.inc: - %inc = add nsw i2 %i, 1 - %cmp = icmp slt i2 %inc, 3 - br i1 %cmp, label %for.body, label %for.end - -for.end: - ret void -} - -; Make sure we don't unswitch, as we can not find an input value %a -; that will effectively unswitch 0 or 3 out of the loop. -; -; CHECK: define void @and_or_i2_as_switch_input(i2 -; CHECK: entry: -; This is an indication that the loop has NOT been unswitched. -; CHECK-NOT: icmp -; CHECK: br -define void @and_or_i2_as_switch_input(i2 %a) { -entry: - br label %for.body - -for.body: - %i = phi i2 [ 0, %entry ], [ %inc, %for.inc ] - %and = and i2 %a, %i - %or = or i2 %and, %i - switch i2 %or, label %sw.default [ - i2 0, label %sw.bb - i2 3, label %sw.bb1 - ] - -sw.bb: - br label %sw.epilog - -sw.bb1: - br label %sw.epilog - -sw.default: - br label %sw.epilog - -sw.epilog: - br label %for.inc - -for.inc: - %inc = add nsw i2 %i, 1 - %cmp = icmp slt i2 %inc, 3 - br i1 %cmp, label %for.body, label %for.end - -for.end: - ret void -} - -; Make sure we don't unswitch, as we can not find an input value %a -; that will effectively unswitch true/false out of the loop. -; -; CHECK: define void @and_or_i1_as_branch_input(i1 -; CHECK: entry: -; This is an indication that the loop has NOT been unswitched. -; CHECK-NOT: icmp -; CHECK: br -define void @and_or_i1_as_branch_input(i1 %a) { -entry: - br label %for.body - -for.body: - %i = phi i1 [ 0, %entry ], [ %inc, %for.inc ] - %and = and i1 %a, %i - %or = or i1 %and, %i - br i1 %or, label %sw.bb, label %sw.bb1 - -sw.bb: - br label %sw.epilog - -sw.bb1: - br label %sw.epilog - -sw.epilog: - br label %for.inc - -for.inc: - %inc = add nsw i1 %i, 1 - %cmp = icmp slt i1 %inc, 1 - br i1 %cmp, label %for.body, label %for.end - -for.end: - ret void -} - -declare void @incf() noreturn -declare void @decf() noreturn -declare void @conv() convergent diff --git a/llvm/test/Transforms/LoopUnswitch/callbr.ll b/llvm/test/Transforms/LoopUnswitch/callbr.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/callbr.ll +++ /dev/null @@ -1,66 +0,0 @@ -; RUN: opt -loop-unswitch -enable-new-pm=0 %s -S | FileCheck %s - -; We want to check that the loop does not get split (so only 2 callbr's not 4). -; It's ok to modify this test in the future should we allow the loop containing -; callbr to be unswitched and are able to do so correctly. - -; CHECK: callbr void asm sideeffect "# ${0:l}", "i,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10)) -; CHECK: to label %7 [label %10] -; CHECK: callbr void asm sideeffect "# ${0:l}", "i,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10)) -; CHECK: to label %9 [label %10] - -; CHECK-NOT: callbr void asm sideeffect "# ${0:l}", "i,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10)) -; CHECK-NOT: to label %7 [label %10] -; CHECK-NOT: callbr void asm sideeffect "# ${0:l}", "i,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10)) -; CHECK-NOT: to label %9 [label %10] -; CHECK-NOT: callbr void asm sideeffect "# ${0:l}", "i,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %19)) -; CHECK-NOT: to label %16 [label %19] -; CHECK-NOT: callbr void asm sideeffect "# ${0:l}", "i,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %19)) -; CHECK-NOT: to label %18 [label %19] - -; This test is essentially: -; void foo(int n) { -; for (int i = 0; i < 1000; ++i) -; if (n) { -; asm goto("# %l0"::::bar); -; bar:; -; } else { -; asm goto("# %l0"::::baz); -; baz:; -; } -;} - -define dso_local void @foo(i32) #0 { - br label %2 - -2: ; preds = %10, %1 - %.0 = phi i32 [ 0, %1 ], [ %11, %10 ] - %3 = icmp ult i32 %.0, 1000 - br i1 %3, label %4, label %12 - -4: ; preds = %2 - %5 = icmp eq i32 %0, 0 - br i1 %5, label %8, label %6 - -6: ; preds = %4 - callbr void asm sideeffect "# ${0:l}", "i,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10)) #0 - to label %7 [label %10] - -7: ; preds = %6 - br label %10 - -8: ; preds = %4 - callbr void asm sideeffect "# ${0:l}", "i,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10)) #0 - to label %9 [label %10] - -9: ; preds = %8 - br label %10 - -10: ; preds = %7, %6, %9, %8 - %11 = add nuw nsw i32 %.0, 1 - br label %2 - -12: ; preds = %2 - ret void -} - diff --git a/llvm/test/Transforms/LoopUnswitch/cleanuppad.ll b/llvm/test/Transforms/LoopUnswitch/cleanuppad.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/cleanuppad.ll +++ /dev/null @@ -1,44 +0,0 @@ -; RUN: opt -S -loop-unswitch -enable-new-pm=0 -verify-memoryssa < %s | FileCheck %s -target triple = "x86_64-pc-win32" - -define void @f(i32 %doit, i1 %x, i1 %y) personality i32 (...)* @__CxxFrameHandler3 { -entry: - %tobool = icmp eq i32 %doit, 0 - br label %for.cond - -for.cond: ; preds = %for.inc, %entry - br i1 %x, label %for.body, label %for.end - -for.body: ; preds = %for.cond - br i1 %tobool, label %if.then, label %for.inc - -if.then: ; preds = %for.body - br i1 %y, label %for.inc, label %delete.notnull - -delete.notnull: ; preds = %if.then - invoke void @g() - to label %invoke.cont unwind label %lpad - -invoke.cont: ; preds = %delete.notnull - br label %for.inc - -lpad: ; preds = %delete.notnull - %cp = cleanuppad within none [] - cleanupret from %cp unwind to caller - -for.inc: ; preds = %invoke.cont, %if.then, %for.body - br label %for.cond - -for.end: ; preds = %for.cond - ret void -} - -declare void @g() - -declare i32 @__CxxFrameHandler3(...) - -; CHECK-LABEL: define void @f( -; CHECK: cleanuppad within none [] -; CHECK-NOT: cleanuppad - -attributes #0 = { ssp uwtable } diff --git a/llvm/test/Transforms/LoopUnswitch/convergent-hoist-modified.ll b/llvm/test/Transforms/LoopUnswitch/convergent-hoist-modified.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/convergent-hoist-modified.ll +++ /dev/null @@ -1,42 +0,0 @@ -; RUN: opt -loop-unswitch -enable-new-pm=0 %s -S | FileCheck %s - -; When hoisting simple values out from a loop, and not being able to unswitch -; the loop due to the convergent call, the pass would return an incorrect -; Modified status. This was caught by the pass return status check that is -; hidden under EXPENSIVE_CHECKS. - -; CHECK-LABEL: entry: -; CHECK-NEXT: %0 = call i32 @llvm.objectsize.i32.p0i8(i8* bitcast (%struct.anon* @b to i8*), i1 false, i1 false, i1 false) -; CHECK-NEXT: %1 = icmp uge i32 %0, 1 -; CHECK-NEXT: br label %for.cond - -%struct.anon = type { i16 } - -@b = global %struct.anon zeroinitializer, align 1 - -; Function Attrs: nounwind -define i16 @c() #0 { -entry: - br label %for.cond - -for.cond: ; preds = %cont, %entry - br label %for.inc - -for.inc: ; preds = %for.cond - %0 = call i32 @llvm.objectsize.i32.p0i8(i8* bitcast (%struct.anon* @b to i8*), i1 false, i1 false, i1 false) - %1 = icmp uge i32 %0, 1 - br i1 %1, label %cont, label %cont - -cont: ; preds = %for.inc - call void @conv() convergent - %2 = load i16, i16* getelementptr inbounds (%struct.anon, %struct.anon* @b, i32 0, i32 0), align 1 - br label %for.cond -} - -; Function Attrs: nounwind readnone speculatable willreturn -declare i32 @llvm.objectsize.i32.p0i8(i8*, i1 immarg, i1 immarg, i1 immarg) #1 - -declare void @conv() convergent - -attributes #0 = { nounwind } -attributes #1 = { nounwind readnone speculatable willreturn } diff --git a/llvm/test/Transforms/LoopUnswitch/copy-metadata.ll b/llvm/test/Transforms/LoopUnswitch/copy-metadata.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/copy-metadata.ll +++ /dev/null @@ -1,23 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -S < %s 2>&1 | FileCheck %s - -; This test checks if unswitched condition preserve make.implicit metadata. - -define i32 @test(i1 %cond) { -; CHECK-LABEL: @test( -; CHECK: br i1 %cond, label %..split_crit_edge, label %.loop_exit.split_crit_edge, !make.implicit !0 - br label %loop_begin - -loop_begin: - br i1 %cond, label %continue, label %loop_exit, !make.implicit !0 - -continue: - call void @some_func() - br label %loop_begin - -loop_exit: - ret i32 0 -} - -declare void @some_func() - -!0 = !{} diff --git a/llvm/test/Transforms/LoopUnswitch/crash.ll b/llvm/test/Transforms/LoopUnswitch/crash.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/crash.ll +++ /dev/null @@ -1,66 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output - -define void @test1(i32* %S2) { -entry: - br i1 false, label %list_Length.exit, label %cond_true.i -cond_true.i: ; preds = %entry - ret void -list_Length.exit: ; preds = %entry - br i1 false, label %list_Length.exit9, label %cond_true.i5 -cond_true.i5: ; preds = %list_Length.exit - ret void -list_Length.exit9: ; preds = %list_Length.exit - br i1 false, label %bb78, label %return -bb44: ; preds = %bb78, %cond_next68 - br i1 %tmp49.not, label %bb62, label %bb62.loopexit -bb62.loopexit: ; preds = %bb44 - br label %bb62 -bb62: ; preds = %bb62.loopexit, %bb44 - br i1 false, label %return.loopexit, label %cond_next68 -cond_next68: ; preds = %bb62 - br i1 false, label %return.loopexit, label %bb44 -bb78: ; preds = %list_Length.exit9 - %tmp49.not = icmp eq i32* %S2, null ; [#uses=1] - br label %bb44 -return.loopexit: ; preds = %cond_next68, %bb62 - %retval.0.ph = phi i32 [ 1, %cond_next68 ], [ 0, %bb62 ] ; [#uses=1] - br label %return -return: ; preds = %return.loopexit, %list_Length.exit9 - %retval.0 = phi i32 [ 0, %list_Length.exit9 ], [ %retval.0.ph, %return.loopexit ] ; [#uses=0] - ret void -} - -define void @test2() nounwind { -entry: - br label %bb.nph - -bb.nph: ; preds = %entry - %and.i13521 = and <4 x i1> undef, undef ; <<4 x i1>> [#uses=1] - br label %for.body - -for.body: ; preds = %for.body, %bb.nph - %or.i = select <4 x i1> %and.i13521, <4 x i32> undef, <4 x i32> undef ; <<4 x i32>> [#uses=0] - br i1 false, label %for.body, label %for.end - -for.end: ; preds = %for.body, %entry - ret void -} - -; PR6879 -define i32* @test3(i32** %p_45, i16 zeroext %p_46, i64 %p_47, i64 %p_48, i16 signext %p_49) nounwind { -entry: - br label %for.cond - -for.cond: ; preds = %for.cond4, %entry - br i1 false, label %for.cond4, label %for.end88 - -for.cond4: ; preds = %for.cond - %conv46 = trunc i32 0 to i8 ; [#uses=2] - %cmp60 = icmp sgt i8 %conv46, 124 ; [#uses=1] - %or.cond = and i1 undef, %cmp60 ; [#uses=1] - %cond = select i1 %or.cond, i8 %conv46, i8 undef ; [#uses=0] - br label %for.cond - -for.end88: ; preds = %for.cond - ret i32* undef -} diff --git a/llvm/test/Transforms/LoopUnswitch/elseif-non-exponential-behavior.ll b/llvm/test/Transforms/LoopUnswitch/elseif-non-exponential-behavior.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/elseif-non-exponential-behavior.ll +++ /dev/null @@ -1,62 +0,0 @@ -; RUN: opt -loop-unswitch -enable-new-pm=0 -verify-memoryssa -S - < %s | FileCheck %s - -;CHECK-LABEL: @b -;CHECK: [[Loop1:for\.end.*]]: ; preds = %for.cond.us -;CHECK-NEXT: %[[PhiVar1:pdt.*]] = phi i32 [ %pdt.0.us, %for.cond.us ] -;CHECK: [[Loop2:for\.end.*]]: ; preds = %for.cond.us1 -;CHECK-NEXT: %[[PhiVar2:pdt.*]] = phi i32 [ %pdt.0.us2, %for.cond.us1 ] -;CHECK: [[Loop3:for\.end.*]]: ; preds = %for.cond -;CHECK-NEXT: %[[PhiVar3:pdt.*]] = phi i32 [ %pdt.0, %for.cond ] -;CHECK: [[Join1:for\.end.*]]: ; preds = %[[Loop2]], %[[Loop3]] -;CHECK-NEXT: %[[PhiRes1:pdt.*]] = phi i32 [ %[[PhiVar3]], %[[Loop3]] ], [ %[[PhiVar2]], %[[Loop2]] ] -;CHECK: for.end: ; preds = %[[Loop1]], %[[Join1]] -;CHECK-NEXT: %[[PhiRes2:pdt.*]] = phi i32 [ %[[PhiRes1]], %[[Join1]] ], [ %[[PhiVar1]], %[[Loop1]] ] -;CHECK-NEXT: ret i32 %[[PhiRes2]] - -; Function Attrs: nounwind uwtable -define i32 @b(i32 %x, i32 %y) #0 { -entry: - br label %for.cond - -for.cond: ; preds = %for.inc, %entry - %pdt.0 = phi i32 [ 1, %entry ], [ %pdt.2, %for.inc ] - %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] - %cmp = icmp slt i32 %i.0, 100 - br i1 %cmp, label %for.body, label %for.end - -for.body: ; preds = %for.cond - %tobool = icmp ne i32 %x, 0 - br i1 %tobool, label %if.then, label %if.else - -if.then: ; preds = %for.body - %mul = mul nsw i32 %pdt.0, 2 - br label %if.end6 - -if.else: ; preds = %for.body - %tobool1 = icmp ne i32 %y, 0 - br i1 %tobool1, label %if.then2, label %if.else4 - -if.then2: ; preds = %if.else - %mul3 = mul nsw i32 %pdt.0, 3 - br label %if.end - -if.else4: ; preds = %if.else - %mul5 = mul nsw i32 %pdt.0, 4 - br label %if.end - -if.end: ; preds = %if.else4, %if.then2 - %pdt.1 = phi i32 [ %mul3, %if.then2 ], [ %mul5, %if.else4 ] - br label %if.end6 - -if.end6: ; preds = %if.end, %if.then - %pdt.2 = phi i32 [ %mul, %if.then ], [ %pdt.1, %if.end ] - br label %for.inc - -for.inc: ; preds = %if.end6 - %inc = add nsw i32 %i.0, 1 - br label %for.cond - -for.end: ; preds = %for.cond - ret i32 %pdt.0 -} - diff --git a/llvm/test/Transforms/LoopUnswitch/exponential-behavior.ll b/llvm/test/Transforms/LoopUnswitch/exponential-behavior.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/exponential-behavior.ll +++ /dev/null @@ -1,52 +0,0 @@ -; RUN: opt -loop-unswitch -enable-new-pm=0 -S < %s | FileCheck %s -; RUN: opt -loop-unswitch -enable-new-pm=0 -verify-memoryssa -S < %s | FileCheck %s - -define void @f(i32 %n, i32* %ptr) { -; CHECK-LABEL: @f( -entry: - br label %loop - -loop: - %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] - %iv.inc = add i32 %iv, 1 - %unswitch_cond_root = icmp ne i32 %iv.inc, 42 - %us.0 = and i1 %unswitch_cond_root, %unswitch_cond_root - %us.1 = and i1 %us.0, %us.0 - %us.2 = and i1 %us.1, %us.1 - %us.3 = and i1 %us.2, %us.2 - %us.4 = and i1 %us.3, %us.3 - %us.5 = and i1 %us.4, %us.4 - %us.6 = and i1 %us.5, %us.5 - %us.7 = and i1 %us.6, %us.6 - %us.8 = and i1 %us.7, %us.7 - %us.9 = and i1 %us.8, %us.8 - %us.10 = and i1 %us.9, %us.9 - %us.11 = and i1 %us.10, %us.10 - %us.12 = and i1 %us.11, %us.11 - %us.13 = and i1 %us.12, %us.12 - %us.14 = and i1 %us.13, %us.13 - %us.15 = and i1 %us.14, %us.14 - %us.16 = and i1 %us.15, %us.15 - %us.17 = and i1 %us.16, %us.16 - %us.18 = and i1 %us.17, %us.17 - %us.19 = and i1 %us.18, %us.18 - %us.20 = and i1 %us.19, %us.19 - %us.21 = and i1 %us.20, %us.20 - %us.22 = and i1 %us.21, %us.21 - %us.23 = and i1 %us.22, %us.22 - %us.24 = and i1 %us.23, %us.23 - %us.25 = and i1 %us.24, %us.24 - %us.26 = and i1 %us.25, %us.25 - %us.27 = and i1 %us.26, %us.26 - %us.28 = and i1 %us.27, %us.27 - %us.29 = and i1 %us.28, %us.28 - br i1 %us.29, label %leave, label %be - -be: - store volatile i32 0, i32* %ptr - %becond = icmp ult i32 %iv.inc, %n - br i1 %becond, label %leave, label %loop - -leave: - ret void -} diff --git a/llvm/test/Transforms/LoopUnswitch/guards.ll b/llvm/test/Transforms/LoopUnswitch/guards.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/guards.ll +++ /dev/null @@ -1,97 +0,0 @@ -; RUN: opt -S -loop-unswitch -enable-new-pm=0 -verify-memoryssa < %s | FileCheck %s - -declare void @llvm.experimental.guard(i1, ...) - -define void @f_0(i32 %n, i32* %ptr, i1 %c) { -; CHECK-LABEL: @f_0( -; CHECK: loop.us: -; CHECK-NOT: guard -; CHECK: loop: -; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ] -entry: - br label %loop - -loop: - %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ] - %iv.inc = add i32 %iv, 1 - call void(i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ] - store volatile i32 0, i32* %ptr - %becond = icmp ult i32 %iv.inc, %n - br i1 %becond, label %leave, label %loop - -leave: - ret void -} - -define void @f_1(i32 %n, i32* %ptr, i1 %c_0, i1 %c_1) { -; CHECK-LABEL: @f_1( -; CHECK: loop.us.us: -; CHECK-NOT: guard -; CHECK: loop.us: -; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 2) ] -; CHECK-NOT: guard -; CHECK: loop.us1: -; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 1) ] -; CHECK-NOT: guard -; CHECK: loop: -; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 1) ] -; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 2) ] -entry: - br label %loop - -loop: - %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ] - %iv.inc = add i32 %iv, 1 - call void(i1, ...) @llvm.experimental.guard(i1 %c_0) [ "deopt"(i32 1) ] - store volatile i32 0, i32* %ptr - call void(i1, ...) @llvm.experimental.guard(i1 %c_1) [ "deopt"(i32 2) ] - %becond = icmp ult i32 %iv.inc, %n - br i1 %becond, label %leave, label %loop - -leave: - ret void -} - -; Basic negative test - -define void @f_3(i32 %n, i32* %ptr, i1* %c_ptr) { -; CHECK-LABEL: @f_3( -; CHECK-NOT: loop.us: -entry: - br label %loop - -loop: - %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ] - %iv.inc = add i32 %iv, 1 - %c = load volatile i1, i1* %c_ptr - call void(i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ] - store volatile i32 0, i32* %ptr - %becond = icmp ult i32 %iv.inc, %n - br i1 %becond, label %leave, label %loop - -leave: - ret void -} - -define void @f_4(i32 %n, i32* %ptr, i1 %c) { -; CHECK-LABEL: @f_4( -; -; Demonstrate that unswitching on one guard can cause another guard to -; be erased (this has implications on what guards we can keep raw -; pointers to). -entry: - br label %loop - -loop: - %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ] - %iv.inc = add i32 %iv, 1 - call void(i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"(i32 1) ] - store volatile i32 0, i32* %ptr - %neg = xor i1 %c, 1 - call void(i1, ...) @llvm.experimental.guard(i1 %neg) [ "deopt"(i32 2) ] - %becond = icmp ult i32 %iv.inc, %n - br i1 %becond, label %leave, label %loop - -leave: - ret void -} diff --git a/llvm/test/Transforms/LoopUnswitch/infinite-loop.ll b/llvm/test/Transforms/LoopUnswitch/infinite-loop.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/infinite-loop.ll +++ /dev/null @@ -1,58 +0,0 @@ -; REQUIRES: asserts -; RUN: opt -loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s -; RUN: opt -loop-unswitch -enable-new-pm=0 -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S < %s | FileCheck %s -; PR5373 - -; Loop unswitching shouldn't trivially unswitch the true case of condition %a -; in the code here because it leads to an infinite loop. While this doesn't -; contain any instructions with side effects, it's still a kind of side effect. -; It can trivially unswitch on the false case of condition %a though. - -; STATS: 2 loop-unswitch - Number of branches unswitched -; STATS: 2 loop-unswitch - Number of unswitches that are trivial - -; CHECK-LABEL: @func_16( -; CHECK-NEXT: entry: -; CHECK-NEXT: br i1 %a, label %entry.split, label %abort0.split - -; CHECK: entry.split: -; CHECK-NEXT: br i1 %b, label %for.body, label %abort1.split - -; CHECK: for.body: -; CHECK-NEXT: br label %for.body - -; CHECK: abort0.split: -; CHECK-NEXT: call void @end0() [[NOR_NUW:#[0-9]+]] -; CHECK-NEXT: unreachable - -; CHECK: abort1.split: -; CHECK-NEXT: call void @end1() [[NOR_NUW]] -; CHECK-NEXT: unreachable - -; CHECK: } - -define void @func_16(i1 %a, i1 %b) nounwind { -entry: - br label %for.body - -for.body: - br i1 %a, label %cond.end, label %abort0 - -cond.end: - br i1 %b, label %for.body, label %abort1 - -abort0: - call void @end0() noreturn nounwind - unreachable - -abort1: - call void @end1() noreturn nounwind - unreachable -} - -declare void @end0() noreturn -declare void @end1() noreturn - -; CHECK: attributes #0 = { nounwind } -; CHECK: attributes #1 = { noreturn } -; CHECK: attributes [[NOR_NUW]] = { noreturn nounwind } diff --git a/llvm/test/Transforms/LoopUnswitch/invalidate-scev.ll b/llvm/test/Transforms/LoopUnswitch/invalidate-scev.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/invalidate-scev.ll +++ /dev/null @@ -1,33 +0,0 @@ -; RUN: opt -S -indvars -loop-unswitch -enable-new-pm=0 -verify-memoryssa < %s | FileCheck %s - -target triple = "x86_64-unknown-linux-gnu" - -define void @test_01() { - -; Make sure we don't fail by SCEV's assertion due to incorrect invalidation. -; CHECK-LABEL: @test_01 - -entry: - br label %loop - -loop: ; preds = %backedge, %entry - %p_50.addr.0 = phi i16 [ undef, %entry ], [ %add2699, %backedge ] - %idxprom2690 = sext i16 %p_50.addr.0 to i32 - %arrayidx2691 = getelementptr inbounds [5 x i32], [5 x i32]* undef, i32 0, i32 %idxprom2690 - %0 = load i32, i32* %arrayidx2691, align 1 - %tobool2692 = icmp ne i32 %0, 0 - br label %inner_loop - -inner_loop: ; preds = %inner_backedge, %loop - br i1 %tobool2692, label %backedge, label %inner_backedge - -inner_backedge: ; preds = %inner_loop - br label %inner_loop - -backedge: ; preds = %inner_loop - %add2699 = add nsw i16 %p_50.addr.0, 1 - br i1 false, label %loop, label %exit - -exit: ; preds = %backedge - unreachable -} diff --git a/llvm/test/Transforms/LoopUnswitch/invoke-hoist-modified.ll b/llvm/test/Transforms/LoopUnswitch/invoke-hoist-modified.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/invoke-hoist-modified.ll +++ /dev/null @@ -1,53 +0,0 @@ -; RUN: opt -loop-unswitch -enable-new-pm=0 %s -S | FileCheck %s - -; When hoisting simple values out from a loop, and not being able to unswitch -; the loop due to the invoke instruction, the pass would return an incorrect -; Modified status. This was caught by the pass return status check that is -; hidden under EXPENSIVE_CHECKS. - -; CHECK-LABEL: for.cond: -; CHECK-NEXT: %0 = call i32 @llvm.objectsize.i32.p0i8(i8* bitcast (%struct.anon* @b to i8*), i1 false, i1 false, i1 false) -; CHECK-NEXT: %1 = icmp uge i32 %0, 1 -; CHECK-NEXT: br label %for.inc - -%struct.anon = type { i16 } - -@b = global %struct.anon zeroinitializer, align 1 - -; Function Attrs: nounwind -define i32 @c() #0 personality i32 (...)* @__CxxFrameHandler3 { -entry: - br label %for.cond - -for.cond: ; preds = %cont, %entry - br label %for.inc - -for.inc: ; preds = %for.cond - %0 = call i32 @llvm.objectsize.i32.p0i8(i8* bitcast (%struct.anon* @b to i8*), i1 false, i1 false, i1 false) - %1 = icmp uge i32 %0, 1 - br i1 %1, label %delete.notnull, label %delete.notnull - -delete.notnull: ; preds = %for.inc - invoke void @g() to label %invoke.cont unwind label %lpad - -invoke.cont: ; preds = %delete.notnull - br label %for.inc - -lpad: ; preds = %delete.notnull - %cp = cleanuppad within none [] - cleanupret from %cp unwind to caller - -cont: ; preds = %for.inc - %2 = load i16, i16* getelementptr inbounds (%struct.anon, %struct.anon* @b, i32 0, i32 0), align 1 - br label %for.cond -} - -; Function Attrs: nounwind readnone speculatable willreturn -declare i32 @llvm.objectsize.i32.p0i8(i8*, i1 immarg, i1 immarg, i1 immarg) #1 - -declare void @g() - -declare i32 @__CxxFrameHandler3(...) - -attributes #0 = { nounwind } -attributes #1 = { nounwind readnone speculatable willreturn } diff --git a/llvm/test/Transforms/LoopUnswitch/msan.ll b/llvm/test/Transforms/LoopUnswitch/msan.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/msan.ll +++ /dev/null @@ -1,153 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-loop-info -verify-memoryssa -S < %s 2>&1 | FileCheck %s - -@sink = global i32 0, align 4 -@y = global i64 0, align 8 - -; The following is approximately: -; void f(bool x, int p, int q) { -; volatile bool x2 = x; -; for (int i = 0; i < 1; ++i) { -; if (x2) { -; if (y) -; sink = p; -; else -; sink = q; -; } -; } -; } -; With MemorySanitizer, the loop can not be unswitched on "y", because "y" could -; be uninitialized when x == false. -; Test that the branch on "y" is inside the loop (after the first unconditional -; branch). - -define void @may_not_execute(i1 zeroext %x, i32 %p, i32 %q) sanitize_memory { -; CHECK-LABEL: @may_not_execute( -entry: -; CHECK: %[[Y:.*]] = load i64, i64* @y, align 8 -; CHECK: %[[YB:.*]] = icmp eq i64 %[[Y]], 0 -; CHECK-NOT: br i1 -; CHECK: br label -; CHECK: br i1 %[[YB]] - - %x2 = alloca i8, align 1 - %frombool1 = zext i1 %x to i8 - store volatile i8 %frombool1, i8* %x2, align 1 - %0 = load i64, i64* @y, align 8 - %tobool3 = icmp eq i64 %0, 0 - br label %for.body - -for.body: - %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] - %x2.0. = load volatile i8, i8* %x2, align 1 - %tobool2 = icmp eq i8 %x2.0., 0 - br i1 %tobool2, label %for.inc, label %if.then - -if.then: - br i1 %tobool3, label %if.else, label %if.then4 - -if.then4: - store volatile i32 %p, i32* @sink, align 4 - br label %for.inc - -if.else: - store volatile i32 %q, i32* @sink, align 4 - br label %for.inc - -for.inc: - %inc = add nsw i32 %i.01, 1 - %cmp = icmp slt i32 %inc, 1 - br i1 %cmp, label %for.body, label %for.end - -for.end: - ret void -} - - -; The same as above, but "y" is a function parameter instead of a global. -; This shows that it is not enough to suppress hoisting of load instructions, -; the actual problem is in the speculative branching. - -define void @may_not_execute2(i1 zeroext %x, i1 zeroext %y, i32 %p, i32 %q) sanitize_memory { -; CHECK-LABEL: @may_not_execute2( -entry: -; CHECK-NOT: br i1 -; CHECK: br label -; CHECK: br i1 %y, - %x2 = alloca i8, align 1 - %frombool2 = zext i1 %x to i8 - store volatile i8 %frombool2, i8* %x2, align 1 - br label %for.body - -for.body: - %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] - %x2.0. = load volatile i8, i8* %x2, align 1 - %tobool3 = icmp eq i8 %x2.0., 0 - br i1 %tobool3, label %for.inc, label %if.then - -if.then: - br i1 %y, label %if.then5, label %if.else - -if.then5: - store volatile i32 %p, i32* @sink, align 4 - br label %for.inc - -if.else: - store volatile i32 %q, i32* @sink, align 4 - br label %for.inc - -for.inc: - %inc = add nsw i32 %i.01, 1 - %cmp = icmp slt i32 %inc, 1 - br i1 %cmp, label %for.body, label %for.end - -for.end: - ret void -} - - -; The following is approximately: -; void f(bool x, int p, int q) { -; volatile bool x2 = x; -; for (int i = 0; i < 1; ++i) { -; if (y) -; sink = p; -; else -; sink = q; -; } -; } -; "if (y)" is guaranteed to execute; the loop can be unswitched. - -define void @must_execute(i1 zeroext %x, i32 %p, i32 %q) sanitize_memory { -; CHECK-LABEL: @must_execute( -entry: -; CHECK: %[[Y:.*]] = load i64, i64* @y, align 8 -; CHECK-NEXT: %[[YB:.*]] = icmp eq i64 %[[Y]], 0 -; CHECK-NEXT: br i1 %[[YB]], - - %x2 = alloca i8, align 1 - %frombool1 = zext i1 %x to i8 - store volatile i8 %frombool1, i8* %x2, align 1 - %0 = load i64, i64* @y, align 8 - %tobool2 = icmp eq i64 %0, 0 - br label %for.body - -for.body: - %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] - br i1 %tobool2, label %if.else, label %if.then - -if.then: - store volatile i32 %p, i32* @sink, align 4 - br label %for.inc - -if.else: - store volatile i32 %q, i32* @sink, align 4 - br label %for.inc - -for.inc: - %inc = add nsw i32 %i.01, 1 - %cmp = icmp slt i32 %inc, 1 - br i1 %cmp, label %for.body, label %for.end - -for.end: - ret void -} diff --git a/llvm/test/Transforms/LoopUnswitch/optsize-hoist-modified.ll b/llvm/test/Transforms/LoopUnswitch/optsize-hoist-modified.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/optsize-hoist-modified.ll +++ /dev/null @@ -1,39 +0,0 @@ -; RUN: opt -loop-unswitch -enable-new-pm=0 %s -S | FileCheck %s - -; When hoisting simple values out from a loop, and not being able to attempt to -; non-trivally unswitch the loop, due to the optsize attribute, the pass would -; return an incorrect Modified status. This was caught by the pass return -; status check that is hidden under EXPENSIVE_CHECKS. - -; CHECK-LABEL: entry: -; CHECK-NEXT: %0 = call i32 @llvm.objectsize.i32.p0i8(i8* bitcast (%struct.anon* @b to i8*), i1 false, i1 false, i1 false) -; CHECK-NEXT: %1 = icmp uge i32 %0, 1 -; CHECK-NEXT: br label %for.cond - -%struct.anon = type { i16 } - -@b = global %struct.anon zeroinitializer, align 1 - -; Function Attrs: minsize nounwind optsize -define i16 @c() #0 { -entry: - br label %for.cond - -for.cond: ; preds = %cont, %entry - br label %for.inc - -for.inc: ; preds = %for.cond - %0 = call i32 @llvm.objectsize.i32.p0i8(i8* bitcast (%struct.anon* @b to i8*), i1 false, i1 false, i1 false) - %1 = icmp uge i32 %0, 1 - br i1 %1, label %cont, label %cont - -cont: ; preds = %for.inc - %2 = load i16, i16* getelementptr inbounds (%struct.anon, %struct.anon* @b, i32 0, i32 0), align 1 - br label %for.cond -} - -; Function Attrs: nounwind readnone speculatable willreturn -declare i32 @llvm.objectsize.i32.p0i8(i8*, i1 immarg, i1 immarg, i1 immarg) #1 - -attributes #0 = { minsize nounwind optsize } -attributes #1 = { nounwind readnone speculatable willreturn } diff --git a/llvm/test/Transforms/LoopUnswitch/partial-unswitch-cost.ll b/llvm/test/Transforms/LoopUnswitch/partial-unswitch-cost.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/partial-unswitch-cost.ll +++ /dev/null @@ -1,426 +0,0 @@ -; RUN: opt -loop-unswitch -loop-unswitch-threshold=10 -verify-dom-info -verify-memoryssa -S -enable-new-pm=0 %s | FileCheck %s - -declare void @clobber() - -; Test cases for partial unswitching, where the regular cost-model overestimates -; the cost of unswitching, because it misses the fact that the unswitched paths -; are no-ops. - - -define i32 @no_partial_unswitch_size_too_large_no_mustprogress(i32* %ptr, i32 %N) { -; CHECK-LABEL: @no_partial_unswitch_size_too_large_no_mustprogress -; CHECK-LABEL: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define i32 @partial_unswitch_shortcut_mustprogress(i32* %ptr, i32 %N) mustprogress { -; CHECK-LABEL: @partial_unswitch_shortcut_mustprogress -; CHECK-LABEL: entry: -; CHECK-NEXT: [[LV:%[0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; CHECK-NEXT: br i1 [[C]], label %[[CRIT_TO_EXIT:[a-z._]+]], label %[[CRIT_TO_HEADER:[a-z._]+]] -; -; CHECK: [[CRIT_TO_HEADER]]: -; CHECK-NEXT: br label %loop.header -; -; CHECK: [[CRIT_TO_EXIT]]: -; CHECK-NEXT: br label %exit -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define i32 @partial_unswitch_shortcut_mustprogress_single_exit_on_path(i32* %ptr, i32 %N) mustprogress { -; CHECK-LABEL: @partial_unswitch_shortcut_mustprogress_single_exit_on_path -; CHECK-LABEL: entry: -; CHECK-NEXT: [[LV:%[0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; CHECK-NEXT: br i1 [[C]], label %[[CRIT_TO_EXIT:.+]], label %[[CRIT_TO_HEADER:[a-z._]+]] -; -; CHECK: [[CRIT_TO_HEADER]]: -; CHECK-NEXT: br label %loop.header -; -; CHECK: [[CRIT_TO_EXIT]]: -; CHECK-NEXT: br label %exit -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - %c.1 = icmp ult i32 %iv, 123 - br i1 %c.1, label %loop.latch, label %exit.1 - -clobber: - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - %c = icmp ult i32 %iv, %N - br i1 %c, label %loop.latch, label %exit.2 - -loop.latch: - %iv.next = add i32 %iv, 1 - br label %loop.header - -exit.1: - ret i32 10 - -exit.2: - ret i32 10 -} - -define i32 @no_partial_unswitch_shortcut_mustprogress_no_exit_on_path(i32* %ptr, i32 %N) mustprogress { -; CHECK-LABEL: @no_partial_unswitch_shortcut_mustprogress_no_exit_on_path -; CHECK-LABEL: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - %c = icmp ult i32 %iv, %N - br i1 %c, label %loop.latch, label %exit - -loop.latch: - %iv.next = add i32 %iv, 1 - br label %loop.header - -exit: - ret i32 10 -} - -define i32 @no_partial_unswitch_shortcut_mustprogress_exit_value_used(i32* %ptr, i32 %N) mustprogress { -; CHECK-LABEL: @no_partial_unswitch_shortcut_mustprogress_exit_value_use -; CHECK-LABEL: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %red = phi i32 [ 0, %entry ], [ %red.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - %red.add = add i32 %red, %lv - br label %loop.latch - -clobber: - %red.mul = mul i32 %red, %lv - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - br label %loop.latch - -loop.latch: - %red.next = phi i32 [ %red.add, %noclobber ], [ %red.mul, %clobber ] - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 %red.next -} - -define i32 @partial_unswitch_shortcut_multiple_exiting_blocks(i32* %ptr, i32 %N, i1 %ec.1) mustprogress { -; CHECK-LABEL: @partial_unswitch_shortcut_multiple_exiting_blocks -; CHECK-LABEL: entry: -; CHECK-NEXT: [[LV:%[0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; CHECK-NEXT: br i1 [[C]], label %[[CRIT_TO_EXIT:.+]], label %[[CRIT_TO_HEADER:[a-z._]+]] -; -; CHECK: [[CRIT_TO_HEADER]]: -; CHECK-NEXT: br label %loop.header -; -; CHECK: [[CRIT_TO_EXIT]]: -; CHECK-NEXT: br label %exit -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br i1 %ec.1, label %loop.latch, label %exit - -clobber: - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define i32 @no_partial_unswitch_shortcut_multiple_exit_blocks(i32* %ptr, i32 %N, i1 %ec.1) mustprogress { -; CHECK-LABEL: @no_partial_unswitch_shortcut_multiple_exit_blocks -; CHECK-LABEL: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br i1 %ec.1, label %loop.latch, label %exit.2 - -clobber: - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit.1 - -exit.1: - ret i32 10 - -exit.2: - ret i32 20 -} - -define i32 @no_partial_unswitch_shortcut_mustprogress_store(i32* %ptr, i32* noalias %dst, i32 %N) mustprogress { -; CHECK-LABEL: @no_partial_unswitch_shortcut_mustprogress_store -; CHECK-LABEL: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - store i32 0, i32* %dst - br label %loop.latch - -clobber: - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define i32 @no_partial_unswitch_shortcut_mustprogress_store2(i32* %ptr, i32* noalias %dst, i32 %N) mustprogress { -; CHECK-LABEL: @no_partial_unswitch_shortcut_mustprogress_store -; CHECK-LABEL: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - br label %loop.latch - -loop.latch: - store i32 0, i32* %dst - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define i32 @no_partial_unswitch_shortcut_mustprogress_store3(i32* %ptr, i32* noalias %dst, i32 %N) mustprogress { -; CHECK-LABEL: @no_partial_unswitch_shortcut_mustprogress_store -; CHECK-LABEL: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - store i32 0, i32* %dst - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} diff --git a/llvm/test/Transforms/LoopUnswitch/partial-unswitch-mssa-threshold.ll b/llvm/test/Transforms/LoopUnswitch/partial-unswitch-mssa-threshold.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/partial-unswitch-mssa-threshold.ll +++ /dev/null @@ -1,48 +0,0 @@ -; RUN: opt -loop-unswitch -loop-unswitch-memoryssa-threshold=0 -memssa-check-limit=1 -enable-new-pm=0 -S %s | FileCheck --check-prefix=THRESHOLD-0 %s -; RUN: opt -loop-unswitch -memssa-check-limit=1 -S -enable-new-pm=0 %s | FileCheck --check-prefix=THRESHOLD-DEFAULT %s - -; Make sure -loop-unswitch-memoryssa-threshold works. The test uses -; -memssa-check-limit=1 to effectively disable any MemorySSA optimizations -; on construction, so the test can be kept simple. - -declare void @clobber() - -; Partial unswitching is possible, because the store in %noclobber does not -; alias the load of the condition. -define i32 @partial_unswitch_true_successor_noclobber(i32* noalias %ptr.1, i32* noalias %ptr.2, i32 %N) { -; THRESHOLD-0-LABEL: @partial_unswitch_true_successor -; THRESHOLD-0: entry: -; THRESHOLD-0: br label %loop.header -; -; THRESHOLD-DEFAULT-LABEL: @partial_unswitch_true_successor -; THRESHOLD-DEFAULT-NEXT: entry: -; THRESHOLD-DEFAULT-NEXT: [[LV:%[0-9]+]] = load i32, i32* %ptr.1, align 4 -; THRESHOLD-DEFAULT-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; THRESHOLD-DEFAULT-NEXT: br i1 [[C]] -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr.1 - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - %gep.1 = getelementptr i32, i32* %ptr.2, i32 %iv - store i32 %lv, i32* %gep.1 - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} diff --git a/llvm/test/Transforms/LoopUnswitch/partial-unswitch-update-memoryssa.ll b/llvm/test/Transforms/LoopUnswitch/partial-unswitch-update-memoryssa.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/partial-unswitch-update-memoryssa.ll +++ /dev/null @@ -1,76 +0,0 @@ -; RUN: opt -loop-unswitch -verify-dom-info -verify-memoryssa -S -enable-new-pm=0 %s | FileCheck %s -; RUN: opt -loop-unswitch -memssa-check-limit=3 -verify-dom-info -verify-memoryssa -S -enable-new-pm=0 %s | FileCheck %s - -declare void @clobber() - -; Check that MemorySSA updating can deal with a clobbering access of a -; duplicated load being a MemoryPHI outside the loop. -define void @partial_unswitch_memssa_update(i32* noalias %ptr, i1 %c) { -; CHECK-LABEL: @partial_unswitch_memssa_update( -; CHECK-LABEL: loop.ph: -; CHECK-NEXT: [[LV:%[a-z0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[C:%[a-z0-9]+]] = icmp eq i32 [[LV]], 0 -; CHECK-NEXT: br i1 [[C]] -entry: - br i1 %c, label %loop.ph, label %outside.clobber - -outside.clobber: - call void @clobber() - br label %loop.ph - -loop.ph: - br label %loop.header - -loop.header: - %lv = load i32, i32* %ptr, align 4 - %hc = icmp eq i32 %lv, 0 - br i1 %hc, label %if, label %then - -if: - br label %loop.latch - -then: - br label %loop.latch - -loop.latch: - br i1 true, label %loop.header, label %exit - -exit: - ret void -} - -; Check that MemorySSA updating can deal with skipping defining accesses in the -; loop body until it finds the first defining access outside the loop. -define void @partial_unswitch_inloop_stores_beteween_outside_defining_access(i64* noalias %ptr, i16* noalias %src) { -; CHECK-LABEL: @partial_unswitch_inloop_stores_beteween_outside_defining_access -; CHECK-LABEL: entry: -; CHECK-NEXT: store i64 0, i64* %ptr, align 1 -; CHECK-NEXT: store i64 1, i64* %ptr, align 1 -; CHECK-NEXT: [[LV:%[a-z0-9]+]] = load i16, i16* %src, align 1 -; CHECK-NEXT: [[C:%[a-z0-9]+]] = icmp eq i16 [[LV]], 0 -; CHECK-NEXT: br i1 [[C]] -; -entry: - store i64 0, i64* %ptr, align 1 - store i64 1, i64* %ptr, align 1 - br label %loop - -loop: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - store i64 2, i64* %ptr, align 1 - %lv = load i16, i16* %src, align 1 - %invar.cond = icmp eq i16 %lv, 0 - br i1 %invar.cond, label %noclobber, label %loop.latch - -noclobber: - br label %loop.latch - -loop.latch: - %iv.next = add i32 %iv, 1 - %ec = icmp eq i32 %iv, 1000 - br i1 %ec, label %exit, label %loop - -exit: - ret void -} - diff --git a/llvm/test/Transforms/LoopUnswitch/partial-unswitch.ll b/llvm/test/Transforms/LoopUnswitch/partial-unswitch.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/partial-unswitch.ll +++ /dev/null @@ -1,875 +0,0 @@ -; RUN: opt -loop-unswitch -verify-dom-info -verify-memoryssa -S -enable-new-pm=0 %s | FileCheck %s - -declare void @clobber() - -define i32 @partial_unswitch_true_successor(i32* %ptr, i32 %N) { -; CHECK-LABEL: @partial_unswitch_true_successor -; CHECK-LABEL: entry: -; CHECK-NEXT: [[LV:%[0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; CHECK-NEXT: br i1 [[C]], label %[[SPLIT_TRUE_PH:[a-z._]+]], label %[[FALSE_CRIT:[a-z._]+]] - -; CHECK: [[FALSE_CRIT]]: -; CHECK-NEXT: br label %[[FALSE_PH:[a-z.]+]] - -; CHECK: [[SPLIT_TRUE_PH]]: -; CHECK-NEXT: br label %[[TRUE_HEADER:[a-z.]+]] - -; CHECK: [[TRUE_HEADER]]: -; CHECK-NEXT: phi i32 -; CHECK-NEXT: [[TRUE_LV:%[a-z.0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[TRUE_C:%[a-z.0-9]+]] = icmp eq i32 [[TRUE_LV]], 100 -; CHECK-NEXT: br i1 true, label %[[TRUE_NOCLOBBER:.+]], label %[[TRUE_CLOBBER:[a-z0-9._]+]] - -; CHECK: [[TRUE_CLOBBER]]: -; CHECK-NEXT: call -; CHECK-NEXT: br label %[[TRUE_LATCH:[a-z0-9._]+]] - -; CHECK: [[TRUE_NOCLOBBER]]: -; CHECK-NEXT: br label %[[TRUE_LATCH:[a-z0-9._]+]] - -; CHECK: [[TRUE_LATCH]]: -; CHECK-NEXT: icmp -; CHECK-NEXT: add -; CHECK-NEXT: br {{.*}} label %[[TRUE_HEADER]] - - -; CHECK: [[FALSE_PH]]: -; CHECK-NEXT: br label %[[FALSE_HEADER:[a-z.]+]] - -; CHECK: [[FALSE_HEADER]]: -; CHECK-NEXT: phi i32 -; CHECK-NEXT: [[FALSE_LV:%[a-z.0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[FALSE_C:%[a-z.0-9]+]] = icmp eq i32 [[FALSE_LV]], 100 -; CHECK-NEXT: br i1 [[FALSE_C]], label %[[FALSE_NOCLOBBER:.+]], label %[[FALSE_CLOBBER:[a-z0-9._]+]] - -; CHECK: [[FALSE_NOCLOBBER]]: -; CHECK-NEXT: br label %[[FALSE_LATCH:[a-z0-9._]+]] - -; CHECK: [[FALSE_CLOBBER]]: -; CHECK-NEXT: call -; CHECK-NEXT: br label %[[FALSE_LATCH:[a-z0-9._]+]] - -; CHECK: [[FALSE_LATCH]]: -; CHECK-NEXT: icmp -; CHECK-NEXT: add -; CHECK-NEXT: br {{.*}} label %[[FALSE_HEADER]] -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define i32 @partial_unswitch_false_successor(i32* %ptr, i32 %N) { -; CHECK-LABEL: @partial_unswitch_false_successor -; CHECK-LABEL: entry: -; CHECK-NEXT: [[LV:%[0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; CHECK-NEXT: br i1 [[C]], label %[[SPLIT_TRUE_PH:[a-z._]+]], label %[[FALSE_CRIT:[a-z._]+]] - -; CHECK: [[FALSE_CRIT]]: -; CHECK-NEXT: br label %[[FALSE_PH:[a-z.]+]] - -; CHECK: [[SPLIT_TRUE_PH]]: -; CHECK-NEXT: br label %[[TRUE_HEADER:[a-z.]+]] - -; CHECK: [[TRUE_HEADER]]: -; CHECK-NEXT: phi i32 -; CHECK-NEXT: [[TRUE_LV:%[a-z.0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[TRUE_C:%[a-z.0-9]+]] = icmp eq i32 [[TRUE_LV]], 100 -; CHECK-NEXT: br i1 [[TRUE_C]], label %[[TRUE_CLOBBER:.+]], label %[[TRUE_NOCLOBBER:[a-z0-9._]+]] - -; CHECK: [[TRUE_NOCLOBBER]]: -; CHECK-NEXT: br label %[[TRUE_LATCH:[a-z0-9._]+]] - -; CHECK: [[TRUE_CLOBBER]]: -; CHECK-NEXT: call -; CHECK-NEXT: br label %[[TRUE_LATCH:[a-z0-9._]+]] - -; CHECK: [[TRUE_LATCH]]: -; CHECK-NEXT: icmp -; CHECK-NEXT: add -; CHECK-NEXT: br {{.*}} label %[[TRUE_HEADER]] - - -; CHECK: [[FALSE_PH]]: -; CHECK-NEXT: br label %[[FALSE_HEADER:[a-z.]+]] - -; CHECK: [[FALSE_HEADER]]: -; CHECK-NEXT: phi i32 -; CHECK-NEXT: [[FALSE_LV:%[a-z.0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[FALSE_C:%[a-z.0-9]+]] = icmp eq i32 [[FALSE_LV]], 100 -; CHECK-NEXT: br i1 false, label %[[FALSE_CLOBBER:.+]], label %[[FALSE_NOCLOBBER:[a-z0-9._]+]] - -; CHECK: [[FALSE_CLOBBER]]: -; CHECK-NEXT: call -; CHECK-NEXT: br label %[[FALSE_LATCH:[a-z0-9._]+]] - -; CHECK: [[FALSE_NOCLOBBER]]: -; CHECK-NEXT: br label %[[FALSE_LATCH:[a-z0-9._]+]] - -; CHECK: [[FALSE_LATCH]]: -; CHECK-NEXT: icmp -; CHECK-NEXT: add -; CHECK-NEXT: br {{.*}} label %[[FALSE_HEADER]] -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %clobber, label %noclobber - -clobber: - call void @clobber() - br label %loop.latch - -noclobber: - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define i32 @partial_unswtich_gep_load_icmp(i32** %ptr, i32 %N) { -; CHECK-LABEL: @partial_unswtich_gep_load_icmp -; CHECK-LABEL: entry: -; CHECK-NEXT: [[GEP:%[a-z.0-9]+]] = getelementptr i32*, i32** %ptr, i32 1 -; CHECK-NEXT: [[LV0:%[a-z.0-9]+]] = load i32*, i32** [[GEP]] -; CHECK-NEXT: [[LV1:%[a-z.0-9]+]] = load i32, i32* [[LV0]] -; CHECK-NEXT: [[C:%[a-z.0-9]+]] = icmp eq i32 [[LV1]], 100 -; CHECK-NEXT: br i1 [[C]], label %[[SPLIT_TRUE_PH:[a-z._]+]], label %[[FALSE_CRIT:[a-z._]+]] - -; CHECK: [[FALSE_CRIT]]: -; CHECK-NEXT: br label %[[FALSE_PH:[a-z.]+]] - -; CHECK: [[SPLIT_TRUE_PH]]: -; CHECK-NEXT: br label %[[TRUE_HEADER:[a-z.]+]] - -; CHECK: [[TRUE_HEADER]]: -; CHECK-NEXT: phi i32 -; CHECK-NEXT: [[TRUE_GEP:%[a-z.0-9]+]] = getelementptr i32*, i32** %ptr, i32 1 -; CHECK-NEXT: [[TRUE_LV0:%[a-z.0-9]+]] = load i32*, i32** [[TRUE_GEP]] -; CHECK-NEXT: [[TRUE_LV1:%[a-z.0-9]+]] = load i32, i32* [[TRUE_LV0]] -; CHECK-NEXT: [[TRUE_C:%[a-z.0-9]+]] = icmp eq i32 [[TRUE_LV1]], 100 -; CHECK-NEXT: br i1 true, label %[[TRUE_NOCLOBBER:.+]], label %[[TRUE_CLOBBER:[a-z0-9._]+]] - -; CHECK: [[TRUE_CLOBBER]]: -; CHECK-NEXT: call -; CHECK-NEXT: br label %[[TRUE_LATCH:[a-z0-9._]+]] - -; CHECK: [[TRUE_NOCLOBBER]]: -; CHECK-NEXT: br label %[[TRUE_LATCH:[a-z0-9._]+]] - -; CHECK: [[TRUE_LATCH]]: -; CHECK-NEXT: icmp -; CHECK-NEXT: add -; CHECK-NEXT: br {{.*}} label %[[TRUE_HEADER]] - -; CHECK: [[FALSE_PH]]: -; CHECK-NEXT: br label %[[FALSE_HEADER:[a-z.]+]] - -; CHECK: [[FALSE_HEADER]]: -; CHECK-NEXT: phi i32 -; CHECK-NEXT: [[FALSE_GEP:%[a-z.0-9]+]] = getelementptr i32*, i32** %ptr, i32 1 -; CHECK-NEXT: [[FALSE_LV0:%[a-z.0-9]+]] = load i32*, i32** [[FALSE_GEP]] -; CHECK-NEXT: [[FALSE_LV1:%[a-z.0-9]+]] = load i32, i32* [[FALSE_LV0]] -; CHECK-NEXT: [[FALSE_C:%[a-z.0-9]+]] = icmp eq i32 [[FALSE_LV1]], 100 -; CHECK-NEXT: br i1 [[FALSE_C]], label %[[FALSE_NOCLOBBER:.+]], label %[[FALSE_CLOBBER:[a-z0-9._]+]] - -; CHECK: [[FALSE_NOCLOBBER]]: -; CHECK-NEXT: br label %[[FALSE_LATCH:[a-z0-9._]+]] - -; CHECK: [[FALSE_CLOBBER]]: -; CHECK-NEXT: call -; CHECK-NEXT: br label %[[FALSE_LATCH:[a-z0-9._]+]] - - -; CHECK: [[FALSE_LATCH]]: -; CHECK-NEXT: icmp -; CHECK-NEXT: add -; CHECK-NEXT: br {{.*}} label %[[FALSE_HEADER]] -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %gep = getelementptr i32*, i32** %ptr, i32 1 - %lv.1 = load i32*, i32** %gep - %lv = load i32, i32* %lv.1 - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define i32 @partial_unswitch_reduction_phi(i32* %ptr, i32 %N) { -; CHECK-LABEL: @partial_unswitch_reduction_phi -; CHECK-LABEL: entry: -; CHECK-NEXT: [[LV:%[0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; CHECK-NEXT: br i1 [[C]], label %[[SPLIT_TRUE_PH:[a-z._]+]], label %[[FALSE_CRIT:[a-z._]+]] - -; CHECK: [[FALSE_CRIT]]: -; CHECK-NEXT: br label %[[FALSE_PH:[a-z.]+]] - -; CHECK: [[SPLIT_TRUE_PH]]: -; CHECK-NEXT: br label %[[TRUE_HEADER:[a-z.]+]] - -; CHECK: [[TRUE_HEADER]]: -; CHECK-NEXT: phi i32 -; CHECK-NEXT: [[TRUE_RED:%[a-z.0-9]+]] = phi i32 [ 20, %[[SPLIT_TRUE_PH]] ], [ [[TRUE_RED_NEXT:%[a-z.0-9]+]], %[[TRUE_LATCH:[a-z.0-9]+]] -; CHECK-NEXT: [[TRUE_LV:%[a-z.0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[TRUE_C:%[a-z.0-9]+]] = icmp eq i32 [[TRUE_LV]], 100 -; CHECK-NEXT: br i1 [[TRUE_C]], label %[[TRUE_CLOBBER:.+]], label %[[TRUE_NOCLOBBER:[a-z0-9._]+]] - -; CHECK: [[TRUE_NOCLOBBER]]: -; CHECK-NEXT: [[TRUE_ADD10:%.+]] = add i32 [[TRUE_RED]], 10 -; CHECK-NEXT: br label %[[TRUE_LATCH]] - -; CHECK: [[TRUE_CLOBBER]]: -; CHECK-NEXT: call -; CHECK-NEXT: [[TRUE_ADD5:%.+]] = add i32 [[TRUE_RED]], 5 -; CHECK-NEXT: br label %[[TRUE_LATCH]] - -; CHECK: [[TRUE_LATCH]]: -; CHECK-NEXT: [[TRUE_RED_NEXT]] = phi i32 [ [[TRUE_ADD5]], %[[TRUE_CLOBBER]] ], [ [[TRUE_ADD10]], %[[TRUE_NOCLOBBER]] ] -; CHECK-NEXT: icmp -; CHECK-NEXT: add -; CHECK-NEXT: br {{.*}} label %[[TRUE_HEADER]] - - -; CHECK: [[FALSE_PH]]: -; CHECK-NEXT: br label %[[FALSE_HEADER:[a-z.]+]] - -; CHECK: [[FALSE_HEADER]]: -; CHECK-NEXT: phi i32 -; CHECK-NEXT: [[FALSE_RED:%[a-z.0-9]+]] = phi i32 [ 20, %[[FALSE_PH]] ], [ [[FALSE_RED_NEXT:%[a-z.0-9]+]], %[[FALSE_LATCH:[a-z.0-9]+]] -; CHECK-NEXT: [[FALSE_LV:%[a-z.0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[FALSE_C:%[a-z.0-9]+]] = icmp eq i32 [[FALSE_LV]], 100 -; CHECK-NEXT: br i1 false, label %[[FALSE_CLOBBER:.+]], label %[[FALSE_NOCLOBBER:[a-z0-9._]+]] - -; CHECK: [[FALSE_CLOBBER]]: -; CHECK-NEXT: call -; CHECK-NEXT: [[FALSE_ADD5:%.+]] = add i32 [[FALSE_RED]], 5 -; CHECK-NEXT: br label %[[FALSE_LATCH:[a-z0-9._]+]] - -; CHECK: [[FALSE_NOCLOBBER]]: -; CHECK-NEXT: [[FALSE_ADD10:%.+]] = add i32 [[FALSE_RED]], 10 -; CHECK-NEXT: br label %[[FALSE_LATCH:[a-z0-9._]+]] - -; CHECK: [[FALSE_LATCH]]: -; CHECK-NEXT: [[FALSE_RED_NEXT]] = phi i32 [ [[FALSE_ADD5]], %[[FALSE_CLOBBER]] ], [ [[FALSE_ADD10]], %[[FALSE_NOCLOBBER]] ] -; CHECK-NEXT: icmp -; CHECK-NEXT: add -; CHECK-NEXT: br {{.*}} label %[[FALSE_HEADER]] -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %red = phi i32 [ 20, %entry ], [ %red.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %clobber, label %noclobber - -clobber: - call void @clobber() - %add.5 = add i32 %red, 5 - br label %loop.latch - -noclobber: - %add.10 = add i32 %red, 10 - br label %loop.latch - -loop.latch: - %red.next = phi i32 [ %add.5, %clobber ], [ %add.10, %noclobber ] - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - %red.next.lcssa = phi i32 [ %red.next, %loop.latch ] - ret i32 %red.next.lcssa -} - -; Partial unswitching is possible, because the store in %noclobber does not -; alias the load of the condition. -define i32 @partial_unswitch_true_successor_noclobber(i32* noalias %ptr.1, i32* noalias %ptr.2, i32 %N) { -; CHECK-LABEL: @partial_unswitch_true_successor -; CHECK-NEXT: entry: -; CHECK-NEXT: [[LV:%[0-9]+]] = load i32, i32* %ptr.1, align 4 -; CHECK-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; CHECK-NEXT: br i1 [[C]], label %[[SPLIT_TRUE_PH:[a-z._]+]], label %[[FALSE_CRIT:[a-z._]+]] - -; CHECK: [[FALSE_CRIT]]: -; CHECK-NEXT: br label %[[FALSE_PH:[a-z.]+]] - -; CHECK: [[SPLIT_TRUE_PH]]: -; CHECK-NEXT: br label %[[TRUE_HEADER:[a-z.]+]] - -; CHECK: [[TRUE_HEADER]]: -; CHECK-NEXT: phi i32 -; CHECK-NEXT: [[TRUE_LV:%[a-z.0-9]+]] = load i32, i32* %ptr.1, align 4 -; CHECK-NEXT: [[TRUE_C:%[a-z.0-9]+]] = icmp eq i32 [[TRUE_LV]], 100 -; CHECK-NEXT: br i1 true, label %[[TRUE_NOCLOBBER:.+]], label %[[TRUE_CLOBBER:[a-z0-9._]+]] - -; CHECK: [[TRUE_CLOBBER]]: -; CHECK-NEXT: call -; CHECK-NEXT: br label %[[TRUE_LATCH:[a-z0-9._]+]] - -; CHECK: [[TRUE_NOCLOBBER]]: -; CHECK-NEXT: [[TRUE_GEP:%[a-z0-9._]+]] = getelementptr i32, i32* %ptr.2 -; CHECK-NEXT: store i32 [[TRUE_LV]], i32* [[TRUE_GEP]], align 4 -; CHECK-NEXT: br label %[[TRUE_LATCH:[a-z0-9._]+]] - -; CHECK: [[TRUE_LATCH]]: -; CHECK-NEXT: icmp -; CHECK-NEXT: add -; CHECK-NEXT: br {{.*}} label %[[TRUE_HEADER]] - - -; CHECK: [[FALSE_PH]]: -; CHECK-NEXT: br label %[[FALSE_HEADER:[a-z.]+]] - -; CHECK: [[FALSE_HEADER]]: -; CHECK-NEXT: phi i32 -; CHECK-NEXT: [[FALSE_LV:%[a-z.0-9]+]] = load i32, i32* %ptr.1, align 4 -; CHECK-NEXT: [[FALSE_C:%[a-z.0-9]+]] = icmp eq i32 [[FALSE_LV]], 100 -; CHECK-NEXT: br i1 [[FALSE_C]], label %[[FALSE_NOCLOBBER:.+]], label %[[FALSE_CLOBBER:[a-z0-9._]+]] - -; CHECK: [[FALSE_NOCLOBBER]]: -; CHECK-NEXT: [[FALSE_GEP:%[a-z0-9._]+]] = getelementptr i32, i32* %ptr.2 -; CHECK-NEXT: store i32 [[FALSE_LV]], i32* [[FALSE_GEP]], align 4 -; CHECK-NEXT: br label %[[FALSE_LATCH:[a-z0-9._]+]] - -; CHECK: [[FALSE_CLOBBER]]: -; CHECK-NEXT: call -; CHECK-NEXT: br label %[[FALSE_LATCH:[a-z0-9._]+]] - -; CHECK: [[FALSE_LATCH]]: -; CHECK-NEXT: icmp -; CHECK-NEXT: add -; CHECK-NEXT: br {{.*}} label %[[FALSE_HEADER]] -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr.1 - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - %gep.1 = getelementptr i32, i32* %ptr.2, i32 %iv - store i32 %lv, i32* %gep.1 - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define void @no_partial_unswitch_phi_cond(i1 %lc, i32 %N) { -; CHECK-LABEL: @no_partial_unswitch_phi_cond -; CHECK-NEXT: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %sc = phi i1 [ %lc, %entry ], [ true, %loop.latch ] - br i1 %sc, label %clobber, label %noclobber - -clobber: - call void @clobber() - br label %loop.latch - -noclobber: - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret void -} - -define void @no_partial_unswitch_clobber_latch(i32* %ptr, i32 %N) { -; CHECK-LABEL: @no_partial_unswitch_clobber_latch -; CHECK-NEXT: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - call void @clobber() - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret void -} - -define void @no_partial_unswitch_clobber_header(i32* %ptr, i32 %N) { -; CHECK-LABEL: @no_partial_unswitch_clobber_header -; CHECK-NEXT: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - call void @clobber() - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret void -} - -define void @no_partial_unswitch_clobber_both(i32* %ptr, i32 %N) { -; CHECK-LABEL: @no_partial_unswitch_clobber_both -; CHECK-NEXT: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - call void @clobber() - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret void -} - -define i32 @no_partial_unswitch_true_successor_storeclobber(i32* %ptr.1, i32* %ptr.2, i32 %N) { -; CHECK-LABEL: @no_partial_unswitch_true_successor_storeclobber -; CHECK-NEXT: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr.1 - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - %gep.1 = getelementptr i32, i32* %ptr.2, i32 %iv - store i32 %lv, i32* %gep.1 - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -; Make sure the duplicated instructions are moved to a preheader that always -; executes when the loop body also executes. Do not check the unswitched code, -; because it is already checked in the @partial_unswitch_true_successor test -; case. -define i32 @partial_unswitch_true_successor_preheader_insertion(i32* %ptr, i32 %N) { -; CHECK-LABEL: @partial_unswitch_true_successor_preheader_insertion( -; CHECK-NEXT: entry: -; CHECK-NEXT: [[EC:%[a-z]+]] = icmp ne i32* %ptr, null -; CHECK-NEXT: br i1 [[EC]], label %[[PH:[a-z0-9.]+]], label %[[EXIT:[a-z0-9.]+]] - -; CHECK: [[PH]]: -; CHECK-NEXT: [[LV:%[0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; CHECK-NEXT: br i1 [[C]] -; -entry: - %ec = icmp ne i32* %ptr, null - br i1 %ec, label %loop.ph, label %exit - -loop.ph: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %loop.ph ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -; Make sure the duplicated instructions are hoisted just before the branch of -; the preheader. Do not check the unswitched code, because it is already checked -; in the @partial_unswitch_true_successor test case -define i32 @partial_unswitch_true_successor_insert_point(i32* %ptr, i32 %N) { -; CHECK-LABEL: @partial_unswitch_true_successor_insert_point( -; CHECK-NEXT: entry: -; CHECK-NEXT: call void @clobber() -; CHECK-NEXT: [[LV:%[0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; CHECK-NEXT: br i1 [[C]] -; -entry: - call void @clobber() - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -; Make sure invariant instructions in the loop are also hoisted to the preheader. -; Do not check the unswitched code, because it is already checked in the -; @partial_unswitch_true_successor test case -define i32 @partial_unswitch_true_successor_hoist_invariant(i32* %ptr, i32 %N) { -; CHECK-LABEL: @partial_unswitch_true_successor_hoist_invariant( -; CHECK-NEXT: entry: -; CHECK-NEXT: [[GEP:%[0-9]+]] = getelementptr i32, i32* %ptr, i64 1 -; CHECK-NEXT: [[LV:%[0-9]+]] = load i32, i32* [[GEP]], align 4 -; CHECK-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; CHECK-NEXT: br i1 [[C]] -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %gep = getelementptr i32, i32* %ptr, i64 1 - %lv = load i32, i32* %gep - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -; Do not unswitch if the condition depends on an atomic load. Duplicating such -; loads is not safe. -define i32 @no_partial_unswitch_atomic_load_unordered(i32* %ptr, i32 %N) { -; CHECK-LABEL: @no_partial_unswitch_atomic_load_unordered -; CHECK-NEXT: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load atomic i32, i32* %ptr unordered, align 4 - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -; Do not unswitch if the condition depends on an atomic load. Duplicating such -; loads is not safe. -define i32 @no_partial_unswitch_atomic_load_monotonic(i32* %ptr, i32 %N) { -; CHECK-LABEL: @no_partial_unswitch_atomic_load_monotonic -; CHECK-NEXT: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load atomic i32, i32* %ptr monotonic, align 4 - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - - -declare i32 @get_value() - -; Do not unswitch if the condition depends on a call, that may clobber memory. -; Duplicating such a call is not safe. -define i32 @no_partial_unswitch_cond_call(i32* %ptr, i32 %N) { -; CHECK-LABEL: @no_partial_unswitch_cond_call -; CHECK-NEXT: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = call i32 @get_value() - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %clobber - -noclobber: - br label %loop.latch - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define i32 @no_partial_unswitch_true_successor_exit(i32* %ptr, i32 %N) { -; CHECK-LABEL: @no_partial_unswitch_true_successor_exit -; CHECK-LABEL: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %exit, label %clobber - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define i32 @no_partial_unswitch_true_same_successor(i32* %ptr, i32 %N) { -; CHECK-LABEL: @no_partial_unswitch_true_same_successor -; CHECK-LABEL: entry: -; CHECK-NEXT: br label %loop.header -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %noclobber, label %noclobber - -noclobber: - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} - -define i32 @partial_unswitch_true_to_latch(i32* %ptr, i32 %N) { -; CHECK-LABEL: @partial_unswitch_true_to_latch -; CHECK-LABEL: entry: -; CHECK-NEXT: [[LV:%[0-9]+]] = load i32, i32* %ptr, align 4 -; CHECK-NEXT: [[C:%[0-9]+]] = icmp eq i32 [[LV]], 100 -; CHECK-NEXT: br i1 [[C]], -; -entry: - br label %loop.header - -loop.header: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] - %lv = load i32, i32* %ptr - %sc = icmp eq i32 %lv, 100 - br i1 %sc, label %loop.latch, label %clobber - -clobber: - call void @clobber() - br label %loop.latch - -loop.latch: - %c = icmp ult i32 %iv, %N - %iv.next = add i32 %iv, 1 - br i1 %c, label %loop.header, label %exit - -exit: - ret i32 10 -} diff --git a/llvm/test/Transforms/LoopUnswitch/pr32818.ll b/llvm/test/Transforms/LoopUnswitch/pr32818.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/pr32818.ll +++ /dev/null @@ -1,19 +0,0 @@ -; Check that the call doesn't get removed even if -; it has no uses. It could have side-effects. -; RUN: opt -loop-unswitch -enable-new-pm=0 -verify-memoryssa -S %s | FileCheck %s - -; CHECK-LABEL: @tinky -define i32 @tinkywinky(i8 %patatino) { - %cmp1 = icmp slt i8 %patatino, 5 - br label %body -body: - %i = select i1 %cmp1, i8 6, i8 undef - br i1 true, label %body, label %end -end: - %split = phi i8 [ %i, %body ] - %conv4 = sext i8 %split to i32 -; CHECK: tail call fastcc i32 @fn5( - %call = tail call fastcc i32 @fn5(i32 %conv4) - ret i32 0 -} -declare fastcc i32 @fn5(i32 returned) unnamed_addr diff --git a/llvm/test/Transforms/LoopUnswitch/preserve-analyses.ll b/llvm/test/Transforms/LoopUnswitch/preserve-analyses.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/preserve-analyses.ll +++ /dev/null @@ -1,129 +0,0 @@ -; RUN: opt -loop-unswitch -enable-new-pm=0 -verify-memoryssa -verify-loop-info -verify-dom-info -disable-output < %s - -; Loop unswitch should be able to unswitch these loops and -; preserve LCSSA and LoopSimplify forms. - -target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:32-f32:32:32-f64:32:32-v64:64:64-v128:128:128-a0:0:64" -target triple = "armv6-apple-darwin9" - -@delim1 = external global i32 ; [#uses=1] -@delim2 = external global i32 ; [#uses=1] - -define i32 @ineqn(i8* %s, i8* %p) nounwind readonly { -entry: - %0 = load i32, i32* @delim1, align 4 ; [#uses=1] - %1 = load i32, i32* @delim2, align 4 ; [#uses=1] - br label %bb8.outer - -bb: ; preds = %bb8 - %2 = icmp eq i8* %p_addr.0, %s ; [#uses=1] - br i1 %2, label %bb10, label %bb2 - -bb2: ; preds = %bb - %3 = getelementptr inbounds i8, i8* %p_addr.0, i32 1 ; [#uses=3] - switch i32 %ineq.0.ph, label %bb8.backedge [ - i32 0, label %bb3 - i32 1, label %bb6 - ] - -bb8.backedge: ; preds = %bb6, %bb5, %bb2 - br label %bb8 - -bb3: ; preds = %bb2 - %4 = icmp eq i32 %8, %0 ; [#uses=1] - br i1 %4, label %bb8.outer.loopexit, label %bb5 - -bb5: ; preds = %bb3 - br i1 %6, label %bb6, label %bb8.backedge - -bb6: ; preds = %bb5, %bb2 - %5 = icmp eq i32 %8, %1 ; [#uses=1] - br i1 %5, label %bb7, label %bb8.backedge - -bb7: ; preds = %bb6 - %.lcssa1 = phi i8* [ %3, %bb6 ] ; [#uses=1] - br label %bb8.outer.backedge - -bb8.outer.backedge: ; preds = %bb8.outer.loopexit, %bb7 - %.lcssa2 = phi i8* [ %.lcssa1, %bb7 ], [ %.lcssa, %bb8.outer.loopexit ] ; [#uses=1] - %ineq.0.ph.be = phi i32 [ 0, %bb7 ], [ 1, %bb8.outer.loopexit ] ; [#uses=1] - br label %bb8.outer - -bb8.outer.loopexit: ; preds = %bb3 - %.lcssa = phi i8* [ %3, %bb3 ] ; [#uses=1] - br label %bb8.outer.backedge - -bb8.outer: ; preds = %bb8.outer.backedge, %entry - %ineq.0.ph = phi i32 [ 0, %entry ], [ %ineq.0.ph.be, %bb8.outer.backedge ] ; [#uses=3] - %p_addr.0.ph = phi i8* [ %p, %entry ], [ %.lcssa2, %bb8.outer.backedge ] ; [#uses=1] - %6 = icmp eq i32 %ineq.0.ph, 1 ; [#uses=1] - br label %bb8 - -bb8: ; preds = %bb8.outer, %bb8.backedge - %p_addr.0 = phi i8* [ %p_addr.0.ph, %bb8.outer ], [ %3, %bb8.backedge ] ; [#uses=3] - %7 = load i8, i8* %p_addr.0, align 1 ; [#uses=2] - %8 = sext i8 %7 to i32 ; [#uses=2] - %9 = icmp eq i8 %7, 0 ; [#uses=1] - br i1 %9, label %bb10, label %bb - -bb10: ; preds = %bb8, %bb - %.0 = phi i32 [ %ineq.0.ph, %bb ], [ 0, %bb8 ] ; [#uses=1] - ret i32 %.0 -} - -; This is a simplified form of ineqn from above. It triggers some -; different cases in the loop-unswitch code. - -define void @simplified_ineqn() nounwind readonly { -entry: - br label %bb8.outer - -bb8.outer: ; preds = %bb6, %bb2, %entry - %x = phi i32 [ 0, %entry ], [ 0, %bb6 ], [ 1, %bb2 ] ; [#uses=1] - br i1 undef, label %return, label %bb2 - -bb2: ; preds = %bb - switch i32 %x, label %bb6 [ - i32 0, label %bb8.outer - ] - -bb6: ; preds = %bb2 - br i1 undef, label %bb8.outer, label %bb2 - -return: ; preds = %bb8, %bb - ret void -} - -; This function requires special handling to preserve LCSSA form. -; PR4934 - -define void @pnp_check_irq() nounwind noredzone { -entry: - %conv56 = trunc i64 undef to i32 ; [#uses=1] - br label %while.cond.i - -while.cond.i: ; preds = %while.cond.i.backedge, %entry - %call.i25 = call i8* @pci_get_device() nounwind noredzone ; [#uses=2] - br i1 undef, label %if.then65, label %while.body.i - -while.body.i: ; preds = %while.cond.i - br i1 undef, label %if.then31.i.i, label %while.cond.i.backedge - -while.cond.i.backedge: ; preds = %if.then31.i.i, %while.body.i - br label %while.cond.i - -if.then31.i.i: ; preds = %while.body.i - switch i32 %conv56, label %while.cond.i.backedge [ - i32 14, label %if.then42.i.i - i32 15, label %if.then42.i.i - ] - -if.then42.i.i: ; preds = %if.then31.i.i, %if.then31.i.i - %call.i25.lcssa48 = phi i8* [ %call.i25, %if.then31.i.i ], [ %call.i25, %if.then31.i.i ] ; [#uses=0] - unreachable - -if.then65: ; preds = %while.cond.i - unreachable -} - -declare i8* @pci_get_device() noredzone diff --git a/llvm/test/Transforms/LoopUnswitch/simplify-with-nonvalness.ll b/llvm/test/Transforms/LoopUnswitch/simplify-with-nonvalness.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/simplify-with-nonvalness.ll +++ /dev/null @@ -1,58 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-loop-info -verify-memoryssa -S < %s 2>&1 | FileCheck %s - -; There are 1 case and 1 default case in the switch. after we unswitch, we know the -; %a is definitely not 0 in one of the unswitched loop, make sure we take advantage -; of that and simplify the branches in the loop. -; -; CHECK: define void @simplify_with_nonvalness( - -; This is the loop in which we know %a is definitely 0. -; CHECK: sw.bb.us: -; CHECK: br i1 true, label %if.then.us, label %if.end.us - -; This is the loop in which we do not know what %a is but we know %a is definitely NOT 0. -; Make sure we use that information to simplify. -; The icmp eq i32 %a, 0 in one of the unswitched loop is simplified to false. -; CHECK: sw.bb.split: -; CHECK: br i1 false, label %if.then, label %if.end - -define void @simplify_with_nonvalness(i32 %a) #0 { -entry: - br label %for.cond - -for.cond: - %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] - %cmp = icmp slt i32 %i.0, 1024 - br i1 %cmp, label %for.body, label %for.end - -for.body: - switch i32 %a, label %sw.default [ - i32 0, label %sw.bb - ] - -sw.bb: - %cmp1 = icmp eq i32 %a, 0 - br i1 %cmp1, label %if.then, label %if.end - -if.then: - call void (...) @bar() - br label %if.end - -if.end: - br label %sw.epilog - -sw.default: - br label %sw.epilog - -sw.epilog: - br label %for.inc - -for.inc: - %inc = add nsw i32 %i.0, 1 - br label %for.cond - -for.end: - ret void -} - -declare void @bar(...) diff --git a/llvm/test/Transforms/LoopUnswitch/trivial-unswitch.ll b/llvm/test/Transforms/LoopUnswitch/trivial-unswitch.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/trivial-unswitch.ll +++ /dev/null @@ -1,91 +0,0 @@ -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -loop-unswitch-threshold=0 -verify-loop-info -verify-memoryssa -S < %s 2>&1 | FileCheck %s - -; This test contains two trivial unswitch condition in one loop. -; LoopUnswitch pass should be able to unswitch the second one -; after unswitching the first one. - - -; CHECK: br i1 %cond1, label %..split_crit_edge, label %.loop_exit.split_crit_edge - -; CHECK: ..split_crit_edge: ; preds = %0 -; CHECK: br label %.split - -; CHECK: .split: ; preds = %..split_crit_edge -; CHECK: br i1 %cond2, label %.split..split.split_crit_edge, label %.split.loop_exit.split1_crit_edge - -; CHECK: .split..split.split_crit_edge: ; preds = %.split -; CHECK: br label %.split.split - -; CHECK: .split.split: ; preds = %.split..split.split_crit_edge -; CHECK: br label %loop_begin - -; CHECK: loop_begin: ; preds = %do_something, %.split.split -; CHECK: br i1 true, label %continue, label %loop_exit - -; CHECK: continue: ; preds = %loop_begin -; CHECK: %var_val = load i32, i32* %var -; CHECK: br i1 true, label %do_something, label %loop_exit - -define i32 @test(i32* %var, i1 %cond1, i1 %cond2) { - br label %loop_begin - -loop_begin: - br i1 %cond1, label %continue, label %loop_exit ; first trivial condition - -continue: - %var_val = load i32, i32* %var - br i1 %cond2, label %do_something, label %loop_exit ; second trivial condition - -do_something: - call void @some_func() noreturn nounwind - br label %loop_begin - -loop_exit: - ret i32 0 -} - - -; We will not be able trivially unswitch on the SwitchInst, as its input -; is a constant. However, since its a constant we should be able to figure -; out that the switch can be folded into a unconditional branch to %continue. -; Then we unswitch on the br inst in %continue. -; -; CHECK: define i32 @test2( -; This is an indication that the loop has been unswitched on %cond1. -; CHECK: br i1 %cond1, label %..split_crit_edge, label %.loop_exit.split_crit_edge - -; CHECK: ..split_crit_edge: ; preds = %0 -; CHECK: br label %.split - -; CHECK: .split: ; preds = %..split_crit_edge -; CHECK: br label %loop_begin - -; CHECK: loop_begin: ; preds = %do_something, %.split -; CHECK: switch i32 - -; CHECK: continue: ; preds = %loop_begin -; CHECK: %var_val = load i32, i32* %var -; CHECK: br i1 true, label %do_something, label %loop_exit - -define i32 @test2(i32* %var, i1 %cond1) { - br label %loop_begin - -loop_begin: - switch i32 1, label %continue [ - i32 0, label %loop_exit - i32 1, label %continue - ] - -continue: - %var_val = load i32, i32* %var - br i1 %cond1, label %do_something, label %loop_exit - -do_something: - call void @some_func() noreturn nounwind - br label %loop_begin - -loop_exit: - ret i32 0 -} - -declare void @some_func() noreturn diff --git a/llvm/test/Transforms/LoopUnswitch/unswitch-equality-undef.ll b/llvm/test/Transforms/LoopUnswitch/unswitch-equality-undef.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/unswitch-equality-undef.ll +++ /dev/null @@ -1,122 +0,0 @@ -; REQUIRES: asserts -; RUN: opt < %s -instcombine -licm -loop-unswitch -enable-new-pm=0 -loop-unswitch-threshold=1000 -verify-memoryssa -disable-output -stats 2>&1| FileCheck %s -; Check no loop unswitch is done because unswitching of equality expr with -; undef is unsafe before the freeze patch is committed. -; CHECK-NOT: Number of branches unswitched - -define void @ham(i64 %arg) local_unnamed_addr { -bb: - %tmp = icmp eq i64 %arg, 0 - br i1 %tmp, label %bb3, label %bb1 - -bb1: ; preds = %bb - %tmp2 = load volatile i64, i64* @global, align 8 - br label %bb3 - -bb3: ; preds = %bb1, %bb - %tmp4 = phi i64 [ %tmp2, %bb1 ], [ undef, %bb ] - %tmp5 = load i64, i64* @global.1, align 8 - br label %bb6 - -bb6: ; preds = %bb21, %bb3 - %tmp7 = phi i64 [ 3, %bb21 ], [ %tmp5, %bb3 ] - %tmp8 = phi i64 [ %tmp25, %bb21 ], [ 0, %bb3 ] - %tmp9 = icmp eq i64 %tmp7, %arg - br i1 %tmp9, label %bb10, label %bb28 - -bb10: ; preds = %bb6 - %tmp11 = icmp eq i64 %tmp7, 0 - br i1 %tmp11, label %bb21, label %bb12 - -bb12: ; preds = %bb10 - %tmp13 = load i64, i64* @global.2, align 8 - %tmp14 = add nsw i64 %tmp13, 1 - store i64 %tmp14, i64* @global.2, align 8 - %tmp15 = load i64, i64* @global.3, align 8 - %tmp16 = icmp eq i64 %tmp15, %tmp4 - br i1 %tmp16, label %bb17, label %bb21 - -bb17: ; preds = %bb12 - %tmp18 = phi i64 [ %tmp15, %bb12 ] - %tmp19 = load i64, i64* @global.4, align 8 - %tmp20 = add nsw i64 %tmp19, %tmp18 - store i64 %tmp20, i64* @global.5, align 8 - br label %bb29 - -bb21: ; preds = %bb12, %bb10 - %tmp22 = load i64, i64* @global.3, align 8 - %tmp23 = load volatile i64, i64* @global, align 8 - %tmp24 = add nsw i64 %tmp23, %tmp22 - store i64 %tmp24, i64* @global.5, align 8 - store i64 3, i64* @global.1, align 8 - %tmp25 = add nsw i64 %tmp8, 1 - %tmp26 = load i64, i64* @global.6, align 8 - %tmp27 = icmp slt i64 %tmp25, %tmp26 - br i1 %tmp27, label %bb6, label %bb28 - -bb28: ; preds = %bb21, %bb6 - br label %bb29 - -bb29: ; preds = %bb28, %bb17 - ret void -} - -define void @zot(i64 %arg, i64 %arg1) local_unnamed_addr { -bb: - %tmp = icmp eq i64 %arg, 0 - %tmp2 = select i1 %tmp, i64 %arg1, i64 undef - %tmp3 = load i64, i64* @global.1, align 8 - br label %bb4 - -bb4: ; preds = %bb19, %bb - %tmp5 = phi i64 [ 3, %bb19 ], [ %tmp3, %bb ] - %tmp6 = phi i64 [ %tmp23, %bb19 ], [ 0, %bb ] - %tmp7 = icmp eq i64 %tmp5, %arg - br i1 %tmp7, label %bb8, label %bb26 - -bb8: ; preds = %bb4 - %tmp9 = icmp eq i64 %tmp5, 0 - br i1 %tmp9, label %bb19, label %bb10 - -bb10: ; preds = %bb8 - %tmp11 = load i64, i64* @global.2, align 8 - %tmp12 = add nsw i64 %tmp11, 1 - store i64 %tmp12, i64* @global.2, align 8 - %tmp13 = load i64, i64* @global.3, align 8 - %tmp14 = icmp eq i64 %tmp13, %tmp2 - br i1 %tmp14, label %bb15, label %bb19 - -bb15: ; preds = %bb10 - %tmp16 = phi i64 [ %tmp13, %bb10 ] - %tmp17 = load i64, i64* @global.4, align 8 - %tmp18 = add nsw i64 %tmp17, %tmp16 - store i64 %tmp18, i64* @global.5, align 8 - br label %bb27 - -bb19: ; preds = %bb10, %bb8 - %tmp20 = load i64, i64* @global.3, align 8 - %tmp21 = load volatile i64, i64* @global, align 8 - %tmp22 = add nsw i64 %tmp21, %tmp20 - store i64 %tmp22, i64* @global.5, align 8 - store i64 3, i64* @global.1, align 8 - %tmp23 = add nsw i64 %tmp6, 1 - %tmp24 = load i64, i64* @global.6, align 8 - %tmp25 = icmp slt i64 %tmp23, %tmp24 - br i1 %tmp25, label %bb4, label %bb26 - -bb26: ; preds = %bb19, %bb4 - br label %bb27 - -bb27: ; preds = %bb26, %bb15 - ret void -} - -@global = common global i64 0, align 8 -@global.1 = common global i64 0, align 8 -@global.2 = common global i64 0, align 8 -@global.3 = common global i64 0, align 8 -@global.4 = common global i64 0, align 8 -@global.5 = common global i64 0, align 8 -@global.6 = common global i64 0, align 8 - - diff --git a/llvm/test/Transforms/LoopUnswitch/unswitch-select.ll b/llvm/test/Transforms/LoopUnswitch/unswitch-select.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopUnswitch/unswitch-select.ll +++ /dev/null @@ -1,26 +0,0 @@ -; REQUIRES: asserts -; RUN: opt < %s -loop-unswitch -enable-new-pm=0 -verify-memoryssa -disable-output -stats 2>&1| FileCheck %s - -; Check the select statement in the loop will be unswitched. -; CHECK: 1 loop-unswitch - Number of selects unswitched -define i32 @test(i1 zeroext %x, i32 %a) local_unnamed_addr #0 { -entry: - br label %while.cond - -while.cond: ; preds = %while.body, %entry - %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.body ] - %s.0 = phi i32 [ %a, %entry ], [ %add, %while.body ] - %cmp = icmp slt i32 %i.0, 10000 - br i1 %cmp, label %while.body, label %while.end - -while.body: ; preds = %while.cond - %cond = select i1 %x, i32 %a, i32 %i.0 - %add = add nsw i32 %s.0, %cond - %inc = add nsw i32 %i.0, 1 - br label %while.cond - -while.end: ; preds = %while.cond - %s.0.lcssa = phi i32 [ %s.0, %while.cond ] - ret i32 %s.0.lcssa -} - diff --git a/polly/lib/CodeGen/CodegenCleanup.cpp b/polly/lib/CodeGen/CodegenCleanup.cpp --- a/polly/lib/CodeGen/CodegenCleanup.cpp +++ b/polly/lib/CodeGen/CodegenCleanup.cpp @@ -17,6 +17,7 @@ #include "llvm/Transforms/InstCombine/InstCombine.h" #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Scalar/GVN.h" +#include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h" #include "llvm/Transforms/Utils.h" #define DEBUG_TYPE "polly-cleanup" @@ -79,7 +80,7 @@ FPM->add(createLoopRotatePass(-1)); FPM->add(createGVNPass()); FPM->add(createLICMPass()); - FPM->add(createLoopUnswitchPass()); + FPM->add(createSimpleLoopUnswitchLegacyPass()); FPM->add(createCFGSimplificationPass()); FPM->add(createInstructionCombiningPass(true)); FPM->add(createIndVarSimplifyPass());