189 lines · cpp
1//===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This pass performs lightweight instruction simplification on loop bodies.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/Transforms/Scalar/LoopInstSimplify.h"14#include "llvm/ADT/STLExtras.h"15#include "llvm/ADT/SmallPtrSet.h"16#include "llvm/ADT/SmallVector.h"17#include "llvm/ADT/Statistic.h"18#include "llvm/Analysis/AssumptionCache.h"19#include "llvm/Analysis/InstructionSimplify.h"20#include "llvm/Analysis/LoopInfo.h"21#include "llvm/Analysis/LoopIterator.h"22#include "llvm/Analysis/LoopPass.h"23#include "llvm/Analysis/MemorySSA.h"24#include "llvm/Analysis/MemorySSAUpdater.h"25#include "llvm/Analysis/TargetLibraryInfo.h"26#include "llvm/IR/BasicBlock.h"27#include "llvm/IR/Dominators.h"28#include "llvm/IR/Instruction.h"29#include "llvm/IR/Instructions.h"30#include "llvm/Support/Casting.h"31#include "llvm/Transforms/Utils/Local.h"32#include "llvm/Transforms/Utils/LoopUtils.h"33#include <optional>34#include <utility>35 36using namespace llvm;37 38#define DEBUG_TYPE "loop-instsimplify"39 40STATISTIC(NumSimplified, "Number of redundant instructions simplified");41 42static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI,43 AssumptionCache &AC, const TargetLibraryInfo &TLI,44 MemorySSAUpdater *MSSAU) {45 const DataLayout &DL = L.getHeader()->getDataLayout();46 SimplifyQuery SQ(DL, &TLI, &DT, &AC);47 48 // On the first pass over the loop body we try to simplify every instruction.49 // On subsequent passes, we can restrict this to only simplifying instructions50 // where the inputs have been updated. We end up needing two sets: one51 // containing the instructions we are simplifying in *this* pass, and one for52 // the instructions we will want to simplify in the *next* pass. We use53 // pointers so we can swap between two stably allocated sets.54 SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;55 56 // Track the PHI nodes that have already been visited during each iteration so57 // that we can identify when it is necessary to iterate.58 SmallPtrSet<PHINode *, 4> VisitedPHIs;59 60 // While simplifying we may discover dead code or cause code to become dead.61 // Keep track of all such instructions and we will delete them at the end.62 SmallVector<WeakTrackingVH, 8> DeadInsts;63 64 // First we want to create an RPO traversal of the loop body. By processing in65 // RPO we can ensure that definitions are processed prior to uses (for non PHI66 // uses) in all cases. This ensures we maximize the simplifications in each67 // iteration over the loop and minimizes the possible causes for continuing to68 // iterate.69 LoopBlocksRPO RPOT(&L);70 RPOT.perform(&LI);71 MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;72 73 bool Changed = false;74 for (;;) {75 if (MSSAU && VerifyMemorySSA)76 MSSA->verifyMemorySSA();77 for (BasicBlock *BB : RPOT) {78 for (Instruction &I : *BB) {79 if (auto *PI = dyn_cast<PHINode>(&I))80 VisitedPHIs.insert(PI);81 82 if (I.use_empty()) {83 if (isInstructionTriviallyDead(&I, &TLI))84 DeadInsts.push_back(&I);85 continue;86 }87 88 // We special case the first iteration which we can detect due to the89 // empty `ToSimplify` set.90 bool IsFirstIteration = ToSimplify->empty();91 92 if (!IsFirstIteration && !ToSimplify->count(&I))93 continue;94 95 Value *V = simplifyInstruction(&I, SQ.getWithInstruction(&I));96 if (!V || !LI.replacementPreservesLCSSAForm(&I, V))97 continue;98 99 for (Use &U : llvm::make_early_inc_range(I.uses())) {100 auto *UserI = cast<Instruction>(U.getUser());101 U.set(V);102 103 // Do not bother dealing with unreachable code.104 if (!DT.isReachableFromEntry(UserI->getParent()))105 continue;106 107 // If the instruction is used by a PHI node we have already processed108 // we'll need to iterate on the loop body to converge, so add it to109 // the next set.110 if (auto *UserPI = dyn_cast<PHINode>(UserI))111 if (VisitedPHIs.count(UserPI)) {112 Next->insert(UserPI);113 continue;114 }115 116 // If we are only simplifying targeted instructions and the user is an117 // instruction in the loop body, add it to our set of targeted118 // instructions. Because we process defs before uses (outside of PHIs)119 // we won't have visited it yet.120 //121 // We also skip any uses outside of the loop being simplified. Those122 // should always be PHI nodes due to LCSSA form, and we don't want to123 // try to simplify those away.124 assert((L.contains(UserI) || isa<PHINode>(UserI)) &&125 "Uses outside the loop should be PHI nodes due to LCSSA!");126 if (!IsFirstIteration && L.contains(UserI))127 ToSimplify->insert(UserI);128 }129 130 if (MSSAU)131 if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(V))132 if (MemoryAccess *MA = MSSA->getMemoryAccess(&I))133 if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(SimpleI))134 MA->replaceAllUsesWith(ReplacementMA);135 136 assert(I.use_empty() && "Should always have replaced all uses!");137 if (isInstructionTriviallyDead(&I, &TLI))138 DeadInsts.push_back(&I);139 ++NumSimplified;140 Changed = true;141 }142 }143 144 // Delete any dead instructions found thus far now that we've finished an145 // iteration over all instructions in all the loop blocks.146 if (!DeadInsts.empty()) {147 Changed = true;148 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU);149 }150 151 if (MSSAU && VerifyMemorySSA)152 MSSA->verifyMemorySSA();153 154 // If we never found a PHI that needs to be simplified in the next155 // iteration, we're done.156 if (Next->empty())157 break;158 159 // Otherwise, put the next set in place for the next iteration and reset it160 // and the visited PHIs for that iteration.161 std::swap(Next, ToSimplify);162 Next->clear();163 VisitedPHIs.clear();164 DeadInsts.clear();165 }166 167 return Changed;168}169 170PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,171 LoopStandardAnalysisResults &AR,172 LPMUpdater &) {173 std::optional<MemorySSAUpdater> MSSAU;174 if (AR.MSSA) {175 MSSAU = MemorySSAUpdater(AR.MSSA);176 if (VerifyMemorySSA)177 AR.MSSA->verifyMemorySSA();178 }179 if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI,180 MSSAU ? &*MSSAU : nullptr))181 return PreservedAnalyses::all();182 183 auto PA = getLoopPassPreservedAnalyses();184 PA.preserveSet<CFGAnalyses>();185 if (AR.MSSA)186 PA.preserve<MemorySSAAnalysis>();187 return PA;188}189