153 lines · cpp
1//===------------------------------------------------------------*- C++ -*-===//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#include "llvm/Transforms/Scalar/DropUnnecessaryAssumes.h"10#include "llvm/ADT/SetVector.h"11#include "llvm/Analysis/AssumptionCache.h"12#include "llvm/Analysis/ValueTracking.h"13#include "llvm/IR/IntrinsicInst.h"14#include "llvm/IR/PatternMatch.h"15#include "llvm/Transforms/Utils/Local.h"16 17using namespace llvm;18using namespace llvm::PatternMatch;19 20static bool affectedValuesAreEphemeral(ArrayRef<Value *> Affected) {21 // Check whether all the uses are ephemeral, i.e. recursively only used22 // by assumes. In that case, the assume does not provide useful information.23 // Note that additional users may appear as a result of inlining and CSE,24 // so we should only make this assumption late in the optimization pipeline.25 SmallSetVector<Instruction *, 32> Worklist;26 auto AddUsers = [&](Value *V) {27 for (User *U : V->users()) {28 // Bail out if we need to inspect too many users.29 if (Worklist.size() >= 32)30 return false;31 Worklist.insert(cast<Instruction>(U));32 }33 return true;34 };35 36 for (Value *V : Affected) {37 // Do not handle assumes on globals for now. The use list for them may38 // contain uses in other functions.39 if (!isa<Instruction, Argument>(V))40 return false;41 42 if (!AddUsers(V))43 return false;44 }45 46 for (unsigned Idx = 0; Idx < Worklist.size(); ++Idx) {47 Instruction *I = Worklist[Idx];48 49 // Use in assume is ephemeral.50 if (isa<AssumeInst>(I))51 continue;52 53 // Use in side-effecting instruction is non-ephemeral.54 if (I->mayHaveSideEffects() || I->isTerminator())55 return false;56 57 // Otherwise, recursively look at the users.58 if (!AddUsers(I))59 return false;60 }61 62 return true;63}64 65PreservedAnalyses66DropUnnecessaryAssumesPass::run(Function &F, FunctionAnalysisManager &FAM) {67 AssumptionCache &AC = FAM.getResult<AssumptionAnalysis>(F);68 bool Changed = false;69 70 for (const WeakVH &Elem : AC.assumptions()) {71 auto *Assume = cast_or_null<AssumeInst>(Elem);72 if (!Assume)73 continue;74 75 if (Assume->hasOperandBundles()) {76 // Handle operand bundle assumptions.77 SmallVector<WeakTrackingVH> DeadBundleArgs;78 SmallVector<OperandBundleDef> KeptBundles;79 unsigned NumBundles = Assume->getNumOperandBundles();80 for (unsigned I = 0; I != NumBundles; ++I) {81 auto IsDead = [&](OperandBundleUse Bundle) {82 // "ignore" operand bundles are always dead.83 if (Bundle.getTagName() == "ignore")84 return true;85 86 // "dereferenceable" operand bundles are only dropped if requested87 // (e.g., after loop vectorization has run).88 if (Bundle.getTagName() == "dereferenceable")89 return DropDereferenceable;90 91 // Bundles without arguments do not affect any specific values.92 // Always keep them for now.93 if (Bundle.Inputs.empty())94 return false;95 96 SmallVector<Value *> Affected;97 AssumptionCache::findValuesAffectedByOperandBundle(98 Bundle, [&](Value *A) { Affected.push_back(A); });99 100 return affectedValuesAreEphemeral(Affected);101 };102 103 OperandBundleUse Bundle = Assume->getOperandBundleAt(I);104 if (IsDead(Bundle))105 append_range(DeadBundleArgs, Bundle.Inputs);106 else107 KeptBundles.emplace_back(Bundle);108 }109 110 if (KeptBundles.size() != NumBundles) {111 if (KeptBundles.empty()) {112 // All operand bundles are dead, remove the whole assume.113 Assume->eraseFromParent();114 } else {115 // Otherwise only drop the dead operand bundles.116 CallBase *NewAssume =117 CallBase::Create(Assume, KeptBundles, Assume->getIterator());118 AC.registerAssumption(cast<AssumeInst>(NewAssume));119 Assume->eraseFromParent();120 }121 122 RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadBundleArgs);123 Changed = true;124 }125 continue;126 }127 128 Value *Cond = Assume->getArgOperand(0);129 // Don't drop type tests, which have special semantics.130 if (match(Cond, m_Intrinsic<Intrinsic::type_test>()) ||131 match(Cond, m_Intrinsic<Intrinsic::public_type_test>()))132 continue;133 134 SmallVector<Value *> Affected;135 findValuesAffectedByCondition(Cond, /*IsAssume=*/true,136 [&](Value *A) { Affected.push_back(A); });137 138 if (!affectedValuesAreEphemeral(Affected))139 continue;140 141 Assume->eraseFromParent();142 RecursivelyDeleteTriviallyDeadInstructions(Cond);143 Changed = true;144 }145 146 if (Changed) {147 PreservedAnalyses PA;148 PA.preserveSet<CFGAnalyses>();149 return PA;150 }151 return PreservedAnalyses::all();152}153