3403 lines · cpp
1//===- GVN.cpp - Eliminate redundant values and loads ---------------------===//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 global value numbering to eliminate fully redundant10// instructions. It also performs simple dead load elimination.11//12// Note that this pass does the value numbering itself; it does not use the13// ValueNumbering analysis passes.14//15//===----------------------------------------------------------------------===//16 17#include "llvm/Transforms/Scalar/GVN.h"18#include "llvm/ADT/DenseMap.h"19#include "llvm/ADT/DepthFirstIterator.h"20#include "llvm/ADT/Hashing.h"21#include "llvm/ADT/MapVector.h"22#include "llvm/ADT/PostOrderIterator.h"23#include "llvm/ADT/STLExtras.h"24#include "llvm/ADT/SetVector.h"25#include "llvm/ADT/SmallPtrSet.h"26#include "llvm/ADT/SmallVector.h"27#include "llvm/ADT/Statistic.h"28#include "llvm/Analysis/AliasAnalysis.h"29#include "llvm/Analysis/AssumeBundleQueries.h"30#include "llvm/Analysis/AssumptionCache.h"31#include "llvm/Analysis/CFG.h"32#include "llvm/Analysis/DomTreeUpdater.h"33#include "llvm/Analysis/GlobalsModRef.h"34#include "llvm/Analysis/InstructionPrecedenceTracking.h"35#include "llvm/Analysis/InstructionSimplify.h"36#include "llvm/Analysis/Loads.h"37#include "llvm/Analysis/LoopInfo.h"38#include "llvm/Analysis/MemoryBuiltins.h"39#include "llvm/Analysis/MemoryDependenceAnalysis.h"40#include "llvm/Analysis/MemorySSA.h"41#include "llvm/Analysis/MemorySSAUpdater.h"42#include "llvm/Analysis/OptimizationRemarkEmitter.h"43#include "llvm/Analysis/PHITransAddr.h"44#include "llvm/Analysis/TargetLibraryInfo.h"45#include "llvm/Analysis/ValueTracking.h"46#include "llvm/IR/Attributes.h"47#include "llvm/IR/BasicBlock.h"48#include "llvm/IR/Constant.h"49#include "llvm/IR/Constants.h"50#include "llvm/IR/DebugLoc.h"51#include "llvm/IR/Dominators.h"52#include "llvm/IR/Function.h"53#include "llvm/IR/InstrTypes.h"54#include "llvm/IR/Instruction.h"55#include "llvm/IR/Instructions.h"56#include "llvm/IR/IntrinsicInst.h"57#include "llvm/IR/LLVMContext.h"58#include "llvm/IR/Metadata.h"59#include "llvm/IR/Module.h"60#include "llvm/IR/PassManager.h"61#include "llvm/IR/PatternMatch.h"62#include "llvm/IR/Type.h"63#include "llvm/IR/Use.h"64#include "llvm/IR/Value.h"65#include "llvm/InitializePasses.h"66#include "llvm/Pass.h"67#include "llvm/Support/Casting.h"68#include "llvm/Support/CommandLine.h"69#include "llvm/Support/Compiler.h"70#include "llvm/Support/Debug.h"71#include "llvm/Support/raw_ostream.h"72#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"73#include "llvm/Transforms/Utils/BasicBlockUtils.h"74#include "llvm/Transforms/Utils/Local.h"75#include "llvm/Transforms/Utils/SSAUpdater.h"76#include "llvm/Transforms/Utils/VNCoercion.h"77#include <algorithm>78#include <cassert>79#include <cstdint>80#include <optional>81#include <utility>82 83using namespace llvm;84using namespace llvm::gvn;85using namespace llvm::VNCoercion;86using namespace PatternMatch;87 88#define DEBUG_TYPE "gvn"89 90STATISTIC(NumGVNInstr, "Number of instructions deleted");91STATISTIC(NumGVNLoad, "Number of loads deleted");92STATISTIC(NumGVNPRE, "Number of instructions PRE'd");93STATISTIC(NumGVNBlocks, "Number of blocks merged");94STATISTIC(NumGVNSimpl, "Number of instructions simplified");95STATISTIC(NumGVNEqProp, "Number of equalities propagated");96STATISTIC(NumPRELoad, "Number of loads PRE'd");97STATISTIC(NumPRELoopLoad, "Number of loop loads PRE'd");98STATISTIC(NumPRELoadMoved2CEPred,99 "Number of loads moved to predecessor of a critical edge in PRE");100 101STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax,102 "Number of blocks speculated as available in "103 "IsValueFullyAvailableInBlock(), max");104STATISTIC(MaxBBSpeculationCutoffReachedTimes,105 "Number of times we we reached gvn-max-block-speculations cut-off "106 "preventing further exploration");107 108static cl::opt<bool> GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden);109static cl::opt<bool> GVNEnableLoadPRE("enable-load-pre", cl::init(true));110static cl::opt<bool> GVNEnableLoadInLoopPRE("enable-load-in-loop-pre",111 cl::init(true));112static cl::opt<bool>113GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre",114 cl::init(false));115static cl::opt<bool> GVNEnableMemDep("enable-gvn-memdep", cl::init(true));116static cl::opt<bool> GVNEnableMemorySSA("enable-gvn-memoryssa",117 cl::init(false));118 119static cl::opt<uint32_t> MaxNumDeps(120 "gvn-max-num-deps", cl::Hidden, cl::init(100),121 cl::desc("Max number of dependences to attempt Load PRE (default = 100)"));122 123// This is based on IsValueFullyAvailableInBlockNumSpeculationsMax stat.124static cl::opt<uint32_t> MaxBBSpeculations(125 "gvn-max-block-speculations", cl::Hidden, cl::init(600),126 cl::desc("Max number of blocks we're willing to speculate on (and recurse "127 "into) when deducing if a value is fully available or not in GVN "128 "(default = 600)"));129 130static cl::opt<uint32_t> MaxNumVisitedInsts(131 "gvn-max-num-visited-insts", cl::Hidden, cl::init(100),132 cl::desc("Max number of visited instructions when trying to find "133 "dominating value of select dependency (default = 100)"));134 135static cl::opt<uint32_t> MaxNumInsnsPerBlock(136 "gvn-max-num-insns", cl::Hidden, cl::init(100),137 cl::desc("Max number of instructions to scan in each basic block in GVN "138 "(default = 100)"));139 140struct llvm::GVNPass::Expression {141 uint32_t Opcode;142 bool Commutative = false;143 // The type is not necessarily the result type of the expression, it may be144 // any additional type needed to disambiguate the expression.145 Type *Ty = nullptr;146 SmallVector<uint32_t, 4> VarArgs;147 148 AttributeList Attrs;149 150 Expression(uint32_t Op = ~2U) : Opcode(Op) {}151 152 bool operator==(const Expression &Other) const {153 if (Opcode != Other.Opcode)154 return false;155 if (Opcode == ~0U || Opcode == ~1U)156 return true;157 if (Ty != Other.Ty)158 return false;159 if (VarArgs != Other.VarArgs)160 return false;161 if ((!Attrs.isEmpty() || !Other.Attrs.isEmpty()) &&162 !Attrs.intersectWith(Ty->getContext(), Other.Attrs).has_value())163 return false;164 return true;165 }166 167 friend hash_code hash_value(const Expression &Value) {168 return hash_combine(Value.Opcode, Value.Ty,169 hash_combine_range(Value.VarArgs));170 }171};172 173template <> struct llvm::DenseMapInfo<GVNPass::Expression> {174 static inline GVNPass::Expression getEmptyKey() { return ~0U; }175 static inline GVNPass::Expression getTombstoneKey() { return ~1U; }176 177 static unsigned getHashValue(const GVNPass::Expression &E) {178 using llvm::hash_value;179 180 return static_cast<unsigned>(hash_value(E));181 }182 183 static bool isEqual(const GVNPass::Expression &LHS,184 const GVNPass::Expression &RHS) {185 return LHS == RHS;186 }187};188 189/// Represents a particular available value that we know how to materialize.190/// Materialization of an AvailableValue never fails. An AvailableValue is191/// implicitly associated with a rematerialization point which is the192/// location of the instruction from which it was formed.193struct llvm::gvn::AvailableValue {194 enum class ValType {195 SimpleVal, // A simple offsetted value that is accessed.196 LoadVal, // A value produced by a load.197 MemIntrin, // A memory intrinsic which is loaded from.198 UndefVal, // A UndefValue representing a value from dead block (which199 // is not yet physically removed from the CFG).200 SelectVal, // A pointer select which is loaded from and for which the load201 // can be replace by a value select.202 };203 204 /// Val - The value that is live out of the block.205 Value *Val;206 /// Kind of the live-out value.207 ValType Kind;208 209 /// Offset - The byte offset in Val that is interesting for the load query.210 unsigned Offset = 0;211 /// V1, V2 - The dominating non-clobbered values of SelectVal.212 Value *V1 = nullptr, *V2 = nullptr;213 214 static AvailableValue get(Value *V, unsigned Offset = 0) {215 AvailableValue Res;216 Res.Val = V;217 Res.Kind = ValType::SimpleVal;218 Res.Offset = Offset;219 return Res;220 }221 222 static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset = 0) {223 AvailableValue Res;224 Res.Val = MI;225 Res.Kind = ValType::MemIntrin;226 Res.Offset = Offset;227 return Res;228 }229 230 static AvailableValue getLoad(LoadInst *Load, unsigned Offset = 0) {231 AvailableValue Res;232 Res.Val = Load;233 Res.Kind = ValType::LoadVal;234 Res.Offset = Offset;235 return Res;236 }237 238 static AvailableValue getUndef() {239 AvailableValue Res;240 Res.Val = nullptr;241 Res.Kind = ValType::UndefVal;242 Res.Offset = 0;243 return Res;244 }245 246 static AvailableValue getSelect(SelectInst *Sel, Value *V1, Value *V2) {247 AvailableValue Res;248 Res.Val = Sel;249 Res.Kind = ValType::SelectVal;250 Res.Offset = 0;251 Res.V1 = V1;252 Res.V2 = V2;253 return Res;254 }255 256 bool isSimpleValue() const { return Kind == ValType::SimpleVal; }257 bool isCoercedLoadValue() const { return Kind == ValType::LoadVal; }258 bool isMemIntrinValue() const { return Kind == ValType::MemIntrin; }259 bool isUndefValue() const { return Kind == ValType::UndefVal; }260 bool isSelectValue() const { return Kind == ValType::SelectVal; }261 262 Value *getSimpleValue() const {263 assert(isSimpleValue() && "Wrong accessor");264 return Val;265 }266 267 LoadInst *getCoercedLoadValue() const {268 assert(isCoercedLoadValue() && "Wrong accessor");269 return cast<LoadInst>(Val);270 }271 272 MemIntrinsic *getMemIntrinValue() const {273 assert(isMemIntrinValue() && "Wrong accessor");274 return cast<MemIntrinsic>(Val);275 }276 277 SelectInst *getSelectValue() const {278 assert(isSelectValue() && "Wrong accessor");279 return cast<SelectInst>(Val);280 }281 282 /// Emit code at the specified insertion point to adjust the value defined283 /// here to the specified type. This handles various coercion cases.284 Value *MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt) const;285};286 287/// Represents an AvailableValue which can be rematerialized at the end of288/// the associated BasicBlock.289struct llvm::gvn::AvailableValueInBlock {290 /// BB - The basic block in question.291 BasicBlock *BB = nullptr;292 293 /// AV - The actual available value.294 AvailableValue AV;295 296 static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV) {297 AvailableValueInBlock Res;298 Res.BB = BB;299 Res.AV = std::move(AV);300 return Res;301 }302 303 static AvailableValueInBlock get(BasicBlock *BB, Value *V,304 unsigned Offset = 0) {305 return get(BB, AvailableValue::get(V, Offset));306 }307 308 static AvailableValueInBlock getUndef(BasicBlock *BB) {309 return get(BB, AvailableValue::getUndef());310 }311 312 static AvailableValueInBlock getSelect(BasicBlock *BB, SelectInst *Sel,313 Value *V1, Value *V2) {314 return get(BB, AvailableValue::getSelect(Sel, V1, V2));315 }316 317 /// Emit code at the end of this block to adjust the value defined here to318 /// the specified type. This handles various coercion cases.319 Value *MaterializeAdjustedValue(LoadInst *Load) const {320 return AV.MaterializeAdjustedValue(Load, BB->getTerminator());321 }322};323 324//===----------------------------------------------------------------------===//325// ValueTable Internal Functions326//===----------------------------------------------------------------------===//327 328GVNPass::Expression GVNPass::ValueTable::createExpr(Instruction *I) {329 Expression E;330 E.Ty = I->getType();331 E.Opcode = I->getOpcode();332 if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(I)) {333 // gc.relocate is 'special' call: its second and third operands are334 // not real values, but indices into statepoint's argument list.335 // Use the refered to values for purposes of identity.336 E.VarArgs.push_back(lookupOrAdd(GCR->getOperand(0)));337 E.VarArgs.push_back(lookupOrAdd(GCR->getBasePtr()));338 E.VarArgs.push_back(lookupOrAdd(GCR->getDerivedPtr()));339 } else {340 for (Use &Op : I->operands())341 E.VarArgs.push_back(lookupOrAdd(Op));342 }343 if (I->isCommutative()) {344 // Ensure that commutative instructions that only differ by a permutation345 // of their operands get the same value number by sorting the operand value346 // numbers. Since commutative operands are the 1st two operands it is more347 // efficient to sort by hand rather than using, say, std::sort.348 assert(I->getNumOperands() >= 2 && "Unsupported commutative instruction!");349 if (E.VarArgs[0] > E.VarArgs[1])350 std::swap(E.VarArgs[0], E.VarArgs[1]);351 E.Commutative = true;352 }353 354 if (auto *C = dyn_cast<CmpInst>(I)) {355 // Sort the operand value numbers so x<y and y>x get the same value number.356 CmpInst::Predicate Predicate = C->getPredicate();357 if (E.VarArgs[0] > E.VarArgs[1]) {358 std::swap(E.VarArgs[0], E.VarArgs[1]);359 Predicate = CmpInst::getSwappedPredicate(Predicate);360 }361 E.Opcode = (C->getOpcode() << 8) | Predicate;362 E.Commutative = true;363 } else if (auto *IVI = dyn_cast<InsertValueInst>(I)) {364 E.VarArgs.append(IVI->idx_begin(), IVI->idx_end());365 } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) {366 ArrayRef<int> ShuffleMask = SVI->getShuffleMask();367 E.VarArgs.append(ShuffleMask.begin(), ShuffleMask.end());368 } else if (auto *CB = dyn_cast<CallBase>(I)) {369 E.Attrs = CB->getAttributes();370 }371 372 return E;373}374 375GVNPass::Expression GVNPass::ValueTable::createCmpExpr(376 unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) {377 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&378 "Not a comparison!");379 Expression E;380 E.Ty = CmpInst::makeCmpResultType(LHS->getType());381 E.VarArgs.push_back(lookupOrAdd(LHS));382 E.VarArgs.push_back(lookupOrAdd(RHS));383 384 // Sort the operand value numbers so x<y and y>x get the same value number.385 if (E.VarArgs[0] > E.VarArgs[1]) {386 std::swap(E.VarArgs[0], E.VarArgs[1]);387 Predicate = CmpInst::getSwappedPredicate(Predicate);388 }389 E.Opcode = (Opcode << 8) | Predicate;390 E.Commutative = true;391 return E;392}393 394GVNPass::Expression395GVNPass::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) {396 assert(EI && "Not an ExtractValueInst?");397 Expression E;398 E.Ty = EI->getType();399 E.Opcode = 0;400 401 WithOverflowInst *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());402 if (WO != nullptr && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {403 // EI is an extract from one of our with.overflow intrinsics. Synthesize404 // a semantically equivalent expression instead of an extract value405 // expression.406 E.Opcode = WO->getBinaryOp();407 E.VarArgs.push_back(lookupOrAdd(WO->getLHS()));408 E.VarArgs.push_back(lookupOrAdd(WO->getRHS()));409 return E;410 }411 412 // Not a recognised intrinsic. Fall back to producing an extract value413 // expression.414 E.Opcode = EI->getOpcode();415 for (Use &Op : EI->operands())416 E.VarArgs.push_back(lookupOrAdd(Op));417 418 append_range(E.VarArgs, EI->indices());419 420 return E;421}422 423GVNPass::Expression GVNPass::ValueTable::createGEPExpr(GetElementPtrInst *GEP) {424 Expression E;425 Type *PtrTy = GEP->getType()->getScalarType();426 const DataLayout &DL = GEP->getDataLayout();427 unsigned BitWidth = DL.getIndexTypeSizeInBits(PtrTy);428 SmallMapVector<Value *, APInt, 4> VariableOffsets;429 APInt ConstantOffset(BitWidth, 0);430 if (GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset)) {431 // Convert into offset representation, to recognize equivalent address432 // calculations that use different type encoding.433 LLVMContext &Context = GEP->getContext();434 E.Opcode = GEP->getOpcode();435 E.Ty = nullptr;436 E.VarArgs.push_back(lookupOrAdd(GEP->getPointerOperand()));437 for (const auto &[V, Scale] : VariableOffsets) {438 E.VarArgs.push_back(lookupOrAdd(V));439 E.VarArgs.push_back(lookupOrAdd(ConstantInt::get(Context, Scale)));440 }441 if (!ConstantOffset.isZero())442 E.VarArgs.push_back(443 lookupOrAdd(ConstantInt::get(Context, ConstantOffset)));444 } else {445 // If converting to offset representation fails (for scalable vectors),446 // fall back to type-based implementation.447 E.Opcode = GEP->getOpcode();448 E.Ty = GEP->getSourceElementType();449 for (Use &Op : GEP->operands())450 E.VarArgs.push_back(lookupOrAdd(Op));451 }452 return E;453}454 455//===----------------------------------------------------------------------===//456// ValueTable External Functions457//===----------------------------------------------------------------------===//458 459GVNPass::ValueTable::ValueTable() = default;460GVNPass::ValueTable::ValueTable(const ValueTable &) = default;461GVNPass::ValueTable::ValueTable(ValueTable &&) = default;462GVNPass::ValueTable::~ValueTable() = default;463GVNPass::ValueTable &464GVNPass::ValueTable::operator=(const GVNPass::ValueTable &Arg) = default;465 466/// add - Insert a value into the table with a specified value number.467void GVNPass::ValueTable::add(Value *V, uint32_t Num) {468 ValueNumbering.insert(std::make_pair(V, Num));469 if (PHINode *PN = dyn_cast<PHINode>(V))470 NumberingPhi[Num] = PN;471}472 473/// Include the incoming memory state into the hash of the expression for the474/// given instruction. If the incoming memory state is:475/// * LiveOnEntry, add the value number of the entry block,476/// * a MemoryPhi, add the value number of the basic block corresponding to that477/// MemoryPhi,478/// * a MemoryDef, add the value number of the memory setting instruction.479void GVNPass::ValueTable::addMemoryStateToExp(Instruction *I, Expression &Exp) {480 assert(MSSA && "addMemoryStateToExp should not be called without MemorySSA");481 assert(MSSA->getMemoryAccess(I) && "Instruction does not access memory");482 MemoryAccess *MA = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(I);483 Exp.VarArgs.push_back(lookupOrAdd(MA));484}485 486uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) {487 // FIXME: Currently the calls which may access the thread id may488 // be considered as not accessing the memory. But this is489 // problematic for coroutines, since coroutines may resume in a490 // different thread. So we disable the optimization here for the491 // correctness. However, it may block many other correct492 // optimizations. Revert this one when we detect the memory493 // accessing kind more precisely.494 if (C->getFunction()->isPresplitCoroutine()) {495 ValueNumbering[C] = NextValueNumber;496 return NextValueNumber++;497 }498 499 // Do not combine convergent calls since they implicitly depend on the set of500 // threads that is currently executing, and they might be in different basic501 // blocks.502 if (C->isConvergent()) {503 ValueNumbering[C] = NextValueNumber;504 return NextValueNumber++;505 }506 507 if (AA->doesNotAccessMemory(C)) {508 Expression Exp = createExpr(C);509 uint32_t E = assignExpNewValueNum(Exp).first;510 ValueNumbering[C] = E;511 return E;512 }513 514 if (MD && AA->onlyReadsMemory(C)) {515 Expression Exp = createExpr(C);516 auto [E, IsValNumNew] = assignExpNewValueNum(Exp);517 if (IsValNumNew) {518 ValueNumbering[C] = E;519 return E;520 }521 522 MemDepResult LocalDep = MD->getDependency(C);523 524 if (!LocalDep.isDef() && !LocalDep.isNonLocal()) {525 ValueNumbering[C] = NextValueNumber;526 return NextValueNumber++;527 }528 529 if (LocalDep.isDef()) {530 // For masked load/store intrinsics, the local_dep may actually be531 // a normal load or store instruction.532 CallInst *LocalDepCall = dyn_cast<CallInst>(LocalDep.getInst());533 534 if (!LocalDepCall || LocalDepCall->arg_size() != C->arg_size()) {535 ValueNumbering[C] = NextValueNumber;536 return NextValueNumber++;537 }538 539 for (unsigned I = 0, E = C->arg_size(); I < E; ++I) {540 uint32_t CVN = lookupOrAdd(C->getArgOperand(I));541 uint32_t LocalDepCallVN = lookupOrAdd(LocalDepCall->getArgOperand(I));542 if (CVN != LocalDepCallVN) {543 ValueNumbering[C] = NextValueNumber;544 return NextValueNumber++;545 }546 }547 548 uint32_t V = lookupOrAdd(LocalDepCall);549 ValueNumbering[C] = V;550 return V;551 }552 553 // Non-local case.554 const MemoryDependenceResults::NonLocalDepInfo &Deps =555 MD->getNonLocalCallDependency(C);556 // FIXME: Move the checking logic to MemDep!557 CallInst *CDep = nullptr;558 559 // Check to see if we have a single dominating call instruction that is560 // identical to C.561 for (const NonLocalDepEntry &I : Deps) {562 if (I.getResult().isNonLocal())563 continue;564 565 // We don't handle non-definitions. If we already have a call, reject566 // instruction dependencies.567 if (!I.getResult().isDef() || CDep != nullptr) {568 CDep = nullptr;569 break;570 }571 572 CallInst *NonLocalDepCall = dyn_cast<CallInst>(I.getResult().getInst());573 // FIXME: All duplicated with non-local case.574 if (NonLocalDepCall && DT->properlyDominates(I.getBB(), C->getParent())) {575 CDep = NonLocalDepCall;576 continue;577 }578 579 CDep = nullptr;580 break;581 }582 583 if (!CDep) {584 ValueNumbering[C] = NextValueNumber;585 return NextValueNumber++;586 }587 588 if (CDep->arg_size() != C->arg_size()) {589 ValueNumbering[C] = NextValueNumber;590 return NextValueNumber++;591 }592 for (unsigned I = 0, E = C->arg_size(); I < E; ++I) {593 uint32_t CVN = lookupOrAdd(C->getArgOperand(I));594 uint32_t CDepVN = lookupOrAdd(CDep->getArgOperand(I));595 if (CVN != CDepVN) {596 ValueNumbering[C] = NextValueNumber;597 return NextValueNumber++;598 }599 }600 601 uint32_t V = lookupOrAdd(CDep);602 ValueNumbering[C] = V;603 return V;604 }605 606 if (MSSA && IsMSSAEnabled && AA->onlyReadsMemory(C)) {607 Expression Exp = createExpr(C);608 addMemoryStateToExp(C, Exp);609 auto [V, _] = assignExpNewValueNum(Exp);610 ValueNumbering[C] = V;611 return V;612 }613 614 ValueNumbering[C] = NextValueNumber;615 return NextValueNumber++;616}617 618/// Returns the value number for the specified load or store instruction.619uint32_t GVNPass::ValueTable::computeLoadStoreVN(Instruction *I) {620 if (!MSSA || !IsMSSAEnabled) {621 ValueNumbering[I] = NextValueNumber;622 return NextValueNumber++;623 }624 625 Expression Exp;626 Exp.Ty = I->getType();627 Exp.Opcode = I->getOpcode();628 for (Use &Op : I->operands())629 Exp.VarArgs.push_back(lookupOrAdd(Op));630 addMemoryStateToExp(I, Exp);631 632 auto [V, _] = assignExpNewValueNum(Exp);633 ValueNumbering[I] = V;634 return V;635}636 637/// Returns true if a value number exists for the specified value.638bool GVNPass::ValueTable::exists(Value *V) const {639 return ValueNumbering.contains(V);640}641 642uint32_t GVNPass::ValueTable::lookupOrAdd(MemoryAccess *MA) {643 return MSSA->isLiveOnEntryDef(MA) || isa<MemoryPhi>(MA)644 ? lookupOrAdd(MA->getBlock())645 : lookupOrAdd(cast<MemoryUseOrDef>(MA)->getMemoryInst());646}647 648/// lookupOrAdd - Returns the value number for the specified value, assigning649/// it a new number if it did not have one before.650uint32_t GVNPass::ValueTable::lookupOrAdd(Value *V) {651 DenseMap<Value *, uint32_t>::iterator VI = ValueNumbering.find(V);652 if (VI != ValueNumbering.end())653 return VI->second;654 655 auto *I = dyn_cast<Instruction>(V);656 if (!I) {657 ValueNumbering[V] = NextValueNumber;658 if (isa<BasicBlock>(V))659 NumberingBB[NextValueNumber] = cast<BasicBlock>(V);660 return NextValueNumber++;661 }662 663 Expression Exp;664 switch (I->getOpcode()) {665 case Instruction::Call:666 return lookupOrAddCall(cast<CallInst>(I));667 case Instruction::FNeg:668 case Instruction::Add:669 case Instruction::FAdd:670 case Instruction::Sub:671 case Instruction::FSub:672 case Instruction::Mul:673 case Instruction::FMul:674 case Instruction::UDiv:675 case Instruction::SDiv:676 case Instruction::FDiv:677 case Instruction::URem:678 case Instruction::SRem:679 case Instruction::FRem:680 case Instruction::Shl:681 case Instruction::LShr:682 case Instruction::AShr:683 case Instruction::And:684 case Instruction::Or:685 case Instruction::Xor:686 case Instruction::ICmp:687 case Instruction::FCmp:688 case Instruction::Trunc:689 case Instruction::ZExt:690 case Instruction::SExt:691 case Instruction::FPToUI:692 case Instruction::FPToSI:693 case Instruction::UIToFP:694 case Instruction::SIToFP:695 case Instruction::FPTrunc:696 case Instruction::FPExt:697 case Instruction::PtrToInt:698 case Instruction::PtrToAddr:699 case Instruction::IntToPtr:700 case Instruction::AddrSpaceCast:701 case Instruction::BitCast:702 case Instruction::Select:703 case Instruction::Freeze:704 case Instruction::ExtractElement:705 case Instruction::InsertElement:706 case Instruction::ShuffleVector:707 case Instruction::InsertValue:708 Exp = createExpr(I);709 break;710 case Instruction::GetElementPtr:711 Exp = createGEPExpr(cast<GetElementPtrInst>(I));712 break;713 case Instruction::ExtractValue:714 Exp = createExtractvalueExpr(cast<ExtractValueInst>(I));715 break;716 case Instruction::PHI:717 ValueNumbering[V] = NextValueNumber;718 NumberingPhi[NextValueNumber] = cast<PHINode>(V);719 return NextValueNumber++;720 case Instruction::Load:721 case Instruction::Store:722 return computeLoadStoreVN(I);723 default:724 ValueNumbering[V] = NextValueNumber;725 return NextValueNumber++;726 }727 728 uint32_t E = assignExpNewValueNum(Exp).first;729 ValueNumbering[V] = E;730 return E;731}732 733/// Returns the value number of the specified value. Fails if734/// the value has not yet been numbered.735uint32_t GVNPass::ValueTable::lookup(Value *V, bool Verify) const {736 DenseMap<Value *, uint32_t>::const_iterator VI = ValueNumbering.find(V);737 if (Verify) {738 assert(VI != ValueNumbering.end() && "Value not numbered?");739 return VI->second;740 }741 return (VI != ValueNumbering.end()) ? VI->second : 0;742}743 744/// Returns the value number of the given comparison,745/// assigning it a new number if it did not have one before. Useful when746/// we deduced the result of a comparison, but don't immediately have an747/// instruction realizing that comparison to hand.748uint32_t GVNPass::ValueTable::lookupOrAddCmp(unsigned Opcode,749 CmpInst::Predicate Predicate,750 Value *LHS, Value *RHS) {751 Expression Exp = createCmpExpr(Opcode, Predicate, LHS, RHS);752 return assignExpNewValueNum(Exp).first;753}754 755/// Remove all entries from the ValueTable.756void GVNPass::ValueTable::clear() {757 ValueNumbering.clear();758 ExpressionNumbering.clear();759 NumberingPhi.clear();760 NumberingBB.clear();761 PhiTranslateTable.clear();762 NextValueNumber = 1;763 Expressions.clear();764 ExprIdx.clear();765 NextExprNumber = 0;766}767 768/// Remove a value from the value numbering.769void GVNPass::ValueTable::erase(Value *V) {770 uint32_t Num = ValueNumbering.lookup(V);771 ValueNumbering.erase(V);772 // If V is PHINode, V <--> value number is an one-to-one mapping.773 if (isa<PHINode>(V))774 NumberingPhi.erase(Num);775 else if (isa<BasicBlock>(V))776 NumberingBB.erase(Num);777}778 779/// verifyRemoved - Verify that the value is removed from all internal data780/// structures.781void GVNPass::ValueTable::verifyRemoved(const Value *V) const {782 assert(!ValueNumbering.contains(V) &&783 "Inst still occurs in value numbering map!");784}785 786//===----------------------------------------------------------------------===//787// LeaderMap External Functions788//===----------------------------------------------------------------------===//789 790/// Push a new Value to the LeaderTable onto the list for its value number.791void GVNPass::LeaderMap::insert(uint32_t N, Value *V, const BasicBlock *BB) {792 LeaderListNode &Curr = NumToLeaders[N];793 if (!Curr.Entry.Val) {794 Curr.Entry.Val = V;795 Curr.Entry.BB = BB;796 return;797 }798 799 LeaderListNode *Node = TableAllocator.Allocate<LeaderListNode>();800 Node->Entry.Val = V;801 Node->Entry.BB = BB;802 Node->Next = Curr.Next;803 Curr.Next = Node;804}805 806/// Scan the list of values corresponding to a given807/// value number, and remove the given instruction if encountered.808void GVNPass::LeaderMap::erase(uint32_t N, Instruction *I,809 const BasicBlock *BB) {810 LeaderListNode *Prev = nullptr;811 LeaderListNode *Curr = &NumToLeaders[N];812 813 while (Curr && (Curr->Entry.Val != I || Curr->Entry.BB != BB)) {814 Prev = Curr;815 Curr = Curr->Next;816 }817 818 if (!Curr)819 return;820 821 if (Prev) {822 Prev->Next = Curr->Next;823 } else {824 if (!Curr->Next) {825 Curr->Entry.Val = nullptr;826 Curr->Entry.BB = nullptr;827 } else {828 LeaderListNode *Next = Curr->Next;829 Curr->Entry.Val = Next->Entry.Val;830 Curr->Entry.BB = Next->Entry.BB;831 Curr->Next = Next->Next;832 }833 }834}835 836void GVNPass::LeaderMap::verifyRemoved(const Value *V) const {837 // Walk through the value number scope to make sure the instruction isn't838 // ferreted away in it.839 for (const auto &I : NumToLeaders) {840 (void)I;841 assert(I.second.Entry.Val != V && "Inst still in value numbering scope!");842 assert(843 std::none_of(leader_iterator(&I.second), leader_iterator(nullptr),844 [=](const LeaderTableEntry &E) { return E.Val == V; }) &&845 "Inst still in value numbering scope!");846 }847}848 849//===----------------------------------------------------------------------===//850// GVN Pass851//===----------------------------------------------------------------------===//852 853bool GVNPass::isPREEnabled() const {854 return Options.AllowPRE.value_or(GVNEnablePRE);855}856 857bool GVNPass::isLoadPREEnabled() const {858 return Options.AllowLoadPRE.value_or(GVNEnableLoadPRE);859}860 861bool GVNPass::isLoadInLoopPREEnabled() const {862 return Options.AllowLoadInLoopPRE.value_or(GVNEnableLoadInLoopPRE);863}864 865bool GVNPass::isLoadPRESplitBackedgeEnabled() const {866 return Options.AllowLoadPRESplitBackedge.value_or(867 GVNEnableSplitBackedgeInLoadPRE);868}869 870bool GVNPass::isMemDepEnabled() const {871 return Options.AllowMemDep.value_or(GVNEnableMemDep);872}873 874bool GVNPass::isMemorySSAEnabled() const {875 return Options.AllowMemorySSA.value_or(GVNEnableMemorySSA);876}877 878PreservedAnalyses GVNPass::run(Function &F, FunctionAnalysisManager &AM) {879 // FIXME: The order of evaluation of these 'getResult' calls is very880 // significant! Re-ordering these variables will cause GVN when run alone to881 // be less effective! We should fix memdep and basic-aa to not exhibit this882 // behavior, but until then don't change the order here.883 auto &AC = AM.getResult<AssumptionAnalysis>(F);884 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);885 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);886 auto &AA = AM.getResult<AAManager>(F);887 auto *MemDep =888 isMemDepEnabled() ? &AM.getResult<MemoryDependenceAnalysis>(F) : nullptr;889 auto &LI = AM.getResult<LoopAnalysis>(F);890 auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(F);891 if (isMemorySSAEnabled() && !MSSA) {892 assert(!MemDep &&893 "On-demand computation of MemSSA implies that MemDep is disabled!");894 MSSA = &AM.getResult<MemorySSAAnalysis>(F);895 }896 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);897 bool Changed = runImpl(F, AC, DT, TLI, AA, MemDep, LI, &ORE,898 MSSA ? &MSSA->getMSSA() : nullptr);899 if (!Changed)900 return PreservedAnalyses::all();901 PreservedAnalyses PA;902 PA.preserve<DominatorTreeAnalysis>();903 PA.preserve<TargetLibraryAnalysis>();904 if (MSSA)905 PA.preserve<MemorySSAAnalysis>();906 PA.preserve<LoopAnalysis>();907 return PA;908}909 910void GVNPass::printPipeline(911 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {912 static_cast<PassInfoMixin<GVNPass> *>(this)->printPipeline(913 OS, MapClassName2PassName);914 915 OS << '<';916 if (Options.AllowPRE != std::nullopt)917 OS << (*Options.AllowPRE ? "" : "no-") << "pre;";918 if (Options.AllowLoadPRE != std::nullopt)919 OS << (*Options.AllowLoadPRE ? "" : "no-") << "load-pre;";920 if (Options.AllowLoadPRESplitBackedge != std::nullopt)921 OS << (*Options.AllowLoadPRESplitBackedge ? "" : "no-")922 << "split-backedge-load-pre;";923 if (Options.AllowMemDep != std::nullopt)924 OS << (*Options.AllowMemDep ? "" : "no-") << "memdep;";925 if (Options.AllowMemorySSA != std::nullopt)926 OS << (*Options.AllowMemorySSA ? "" : "no-") << "memoryssa";927 OS << '>';928}929 930void GVNPass::salvageAndRemoveInstruction(Instruction *I) {931 salvageKnowledge(I, AC);932 salvageDebugInfo(*I);933 removeInstruction(I);934}935 936#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)937LLVM_DUMP_METHOD void GVNPass::dump(DenseMap<uint32_t, Value *> &Map) const {938 errs() << "{\n";939 for (const auto &[Num, Exp] : Map) {940 errs() << Num << "\n";941 Exp->dump();942 }943 errs() << "}\n";944}945#endif946 947enum class AvailabilityState : char {948 /// We know the block *is not* fully available. This is a fixpoint.949 Unavailable = 0,950 /// We know the block *is* fully available. This is a fixpoint.951 Available = 1,952 /// We do not know whether the block is fully available or not,953 /// but we are currently speculating that it will be.954 /// If it would have turned out that the block was, in fact, not fully955 /// available, this would have been cleaned up into an Unavailable.956 SpeculativelyAvailable = 2,957};958 959/// Return true if we can prove that the value960/// we're analyzing is fully available in the specified block. As we go, keep961/// track of which blocks we know are fully alive in FullyAvailableBlocks. This962/// map is actually a tri-state map with the following values:963/// 0) we know the block *is not* fully available.964/// 1) we know the block *is* fully available.965/// 2) we do not know whether the block is fully available or not, but we are966/// currently speculating that it will be.967static bool IsValueFullyAvailableInBlock(968 BasicBlock *BB,969 DenseMap<BasicBlock *, AvailabilityState> &FullyAvailableBlocks) {970 SmallVector<BasicBlock *, 32> Worklist;971 std::optional<BasicBlock *> UnavailableBB;972 973 // The number of times we didn't find an entry for a block in a map and974 // optimistically inserted an entry marking block as speculatively available.975 unsigned NumNewNewSpeculativelyAvailableBBs = 0;976 977#ifndef NDEBUG978 SmallPtrSet<BasicBlock *, 32> NewSpeculativelyAvailableBBs;979 SmallVector<BasicBlock *, 32> AvailableBBs;980#endif981 982 Worklist.emplace_back(BB);983 while (!Worklist.empty()) {984 BasicBlock *CurrBB = Worklist.pop_back_val(); // LoadFO - depth-first!985 // Optimistically assume that the block is Speculatively Available and check986 // to see if we already know about this block in one lookup.987 std::pair<DenseMap<BasicBlock *, AvailabilityState>::iterator, bool> IV =988 FullyAvailableBlocks.try_emplace(989 CurrBB, AvailabilityState::SpeculativelyAvailable);990 AvailabilityState &State = IV.first->second;991 992 // Did the entry already exist for this block?993 if (!IV.second) {994 if (State == AvailabilityState::Unavailable) {995 UnavailableBB = CurrBB;996 break; // Backpropagate unavailability info.997 }998 999#ifndef NDEBUG1000 AvailableBBs.emplace_back(CurrBB);1001#endif1002 continue; // Don't recurse further, but continue processing worklist.1003 }1004 1005 // No entry found for block.1006 ++NumNewNewSpeculativelyAvailableBBs;1007 bool OutOfBudget = NumNewNewSpeculativelyAvailableBBs > MaxBBSpeculations;1008 1009 // If we have exhausted our budget, mark this block as unavailable.1010 // Also, if this block has no predecessors, the value isn't live-in here.1011 if (OutOfBudget || pred_empty(CurrBB)) {1012 MaxBBSpeculationCutoffReachedTimes += (int)OutOfBudget;1013 State = AvailabilityState::Unavailable;1014 UnavailableBB = CurrBB;1015 break; // Backpropagate unavailability info.1016 }1017 1018 // Tentatively consider this block as speculatively available.1019#ifndef NDEBUG1020 NewSpeculativelyAvailableBBs.insert(CurrBB);1021#endif1022 // And further recurse into block's predecessors, in depth-first order!1023 Worklist.append(pred_begin(CurrBB), pred_end(CurrBB));1024 }1025 1026#if LLVM_ENABLE_STATS1027 IsValueFullyAvailableInBlockNumSpeculationsMax.updateMax(1028 NumNewNewSpeculativelyAvailableBBs);1029#endif1030 1031 // If the block isn't marked as fixpoint yet1032 // (the Unavailable and Available states are fixpoints).1033 auto MarkAsFixpointAndEnqueueSuccessors =1034 [&](BasicBlock *BB, AvailabilityState FixpointState) {1035 auto It = FullyAvailableBlocks.find(BB);1036 if (It == FullyAvailableBlocks.end())1037 return; // Never queried this block, leave as-is.1038 switch (AvailabilityState &State = It->second) {1039 case AvailabilityState::Unavailable:1040 case AvailabilityState::Available:1041 return; // Don't backpropagate further, continue processing worklist.1042 case AvailabilityState::SpeculativelyAvailable: // Fix it!1043 State = FixpointState;1044#ifndef NDEBUG1045 assert(NewSpeculativelyAvailableBBs.erase(BB) &&1046 "Found a speculatively available successor leftover?");1047#endif1048 // Queue successors for further processing.1049 Worklist.append(succ_begin(BB), succ_end(BB));1050 return;1051 }1052 };1053 1054 if (UnavailableBB) {1055 // Okay, we have encountered an unavailable block.1056 // Mark speculatively available blocks reachable from UnavailableBB as1057 // unavailable as well. Paths are terminated when they reach blocks not in1058 // FullyAvailableBlocks or they are not marked as speculatively available.1059 Worklist.clear();1060 Worklist.append(succ_begin(*UnavailableBB), succ_end(*UnavailableBB));1061 while (!Worklist.empty())1062 MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),1063 AvailabilityState::Unavailable);1064 }1065 1066#ifndef NDEBUG1067 Worklist.clear();1068 for (BasicBlock *AvailableBB : AvailableBBs)1069 Worklist.append(succ_begin(AvailableBB), succ_end(AvailableBB));1070 while (!Worklist.empty())1071 MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),1072 AvailabilityState::Available);1073 1074 assert(NewSpeculativelyAvailableBBs.empty() &&1075 "Must have fixed all the new speculatively available blocks.");1076#endif1077 1078 return !UnavailableBB;1079}1080 1081/// If the specified OldValue exists in ValuesPerBlock, replace its value with1082/// NewValue.1083static void replaceValuesPerBlockEntry(1084 SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock, Value *OldValue,1085 Value *NewValue) {1086 for (AvailableValueInBlock &V : ValuesPerBlock) {1087 if (V.AV.Val == OldValue)1088 V.AV.Val = NewValue;1089 if (V.AV.isSelectValue()) {1090 if (V.AV.V1 == OldValue)1091 V.AV.V1 = NewValue;1092 if (V.AV.V2 == OldValue)1093 V.AV.V2 = NewValue;1094 }1095 }1096}1097 1098/// Given a set of loads specified by ValuesPerBlock,1099/// construct SSA form, allowing us to eliminate Load. This returns the value1100/// that should be used at Load's definition site.1101static Value *1102ConstructSSAForLoadSet(LoadInst *Load,1103 SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,1104 GVNPass &GVN) {1105 // Check for the fully redundant, dominating load case. In this case, we can1106 // just use the dominating value directly.1107 if (ValuesPerBlock.size() == 1 &&1108 GVN.getDominatorTree().properlyDominates(ValuesPerBlock[0].BB,1109 Load->getParent())) {1110 assert(!ValuesPerBlock[0].AV.isUndefValue() &&1111 "Dead BB dominate this block");1112 return ValuesPerBlock[0].MaterializeAdjustedValue(Load);1113 }1114 1115 // Otherwise, we have to construct SSA form.1116 SmallVector<PHINode*, 8> NewPHIs;1117 SSAUpdater SSAUpdate(&NewPHIs);1118 SSAUpdate.Initialize(Load->getType(), Load->getName());1119 1120 for (const AvailableValueInBlock &AV : ValuesPerBlock) {1121 BasicBlock *BB = AV.BB;1122 1123 if (AV.AV.isUndefValue())1124 continue;1125 1126 if (SSAUpdate.HasValueForBlock(BB))1127 continue;1128 1129 // If the value is the load that we will be eliminating, and the block it's1130 // available in is the block that the load is in, then don't add it as1131 // SSAUpdater will resolve the value to the relevant phi which may let it1132 // avoid phi construction entirely if there's actually only one value.1133 if (BB == Load->getParent() &&1134 ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() == Load) ||1135 (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() == Load)))1136 continue;1137 1138 SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(Load));1139 }1140 1141 // Perform PHI construction.1142 return SSAUpdate.GetValueInMiddleOfBlock(Load->getParent());1143}1144 1145Value *AvailableValue::MaterializeAdjustedValue(LoadInst *Load,1146 Instruction *InsertPt) const {1147 Value *Res;1148 Type *LoadTy = Load->getType();1149 const DataLayout &DL = Load->getDataLayout();1150 if (isSimpleValue()) {1151 Res = getSimpleValue();1152 if (Res->getType() != LoadTy) {1153 Res = getValueForLoad(Res, Offset, LoadTy, InsertPt, Load->getFunction());1154 1155 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset1156 << " " << *getSimpleValue() << '\n'1157 << *Res << '\n'1158 << "\n\n\n");1159 }1160 } else if (isCoercedLoadValue()) {1161 LoadInst *CoercedLoad = getCoercedLoadValue();1162 if (CoercedLoad->getType() == LoadTy && Offset == 0) {1163 Res = CoercedLoad;1164 combineMetadataForCSE(CoercedLoad, Load, false);1165 } else {1166 Res = getValueForLoad(CoercedLoad, Offset, LoadTy, InsertPt,1167 Load->getFunction());1168 // We are adding a new user for this load, for which the original1169 // metadata may not hold. Additionally, the new load may have a different1170 // size and type, so their metadata cannot be combined in any1171 // straightforward way.1172 // Drop all metadata that is not known to cause immediate UB on violation,1173 // unless the load has !noundef, in which case all metadata violations1174 // will be promoted to UB.1175 // TODO: We can combine noalias/alias.scope metadata here, because it is1176 // independent of the load type.1177 if (!CoercedLoad->hasMetadata(LLVMContext::MD_noundef))1178 CoercedLoad->dropUnknownNonDebugMetadata(1179 {LLVMContext::MD_dereferenceable,1180 LLVMContext::MD_dereferenceable_or_null,1181 LLVMContext::MD_invariant_load, LLVMContext::MD_invariant_group});1182 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset1183 << " " << *getCoercedLoadValue() << '\n'1184 << *Res << '\n'1185 << "\n\n\n");1186 }1187 } else if (isMemIntrinValue()) {1188 Res = getMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy,1189 InsertPt, DL);1190 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset1191 << " " << *getMemIntrinValue() << '\n'1192 << *Res << '\n'1193 << "\n\n\n");1194 } else if (isSelectValue()) {1195 // Introduce a new value select for a load from an eligible pointer select.1196 SelectInst *Sel = getSelectValue();1197 assert(V1 && V2 && "both value operands of the select must be present");1198 Res =1199 SelectInst::Create(Sel->getCondition(), V1, V2, "", Sel->getIterator());1200 // We use the DebugLoc from the original load here, as this instruction1201 // materializes the value that would previously have been loaded.1202 cast<SelectInst>(Res)->setDebugLoc(Load->getDebugLoc());1203 } else {1204 llvm_unreachable("Should not materialize value from dead block");1205 }1206 assert(Res && "failed to materialize?");1207 return Res;1208}1209 1210static bool isLifetimeStart(const Instruction *Inst) {1211 if (const IntrinsicInst* II = dyn_cast<IntrinsicInst>(Inst))1212 return II->getIntrinsicID() == Intrinsic::lifetime_start;1213 return false;1214}1215 1216/// Assuming To can be reached from both From and Between, does Between lie on1217/// every path from From to To?1218static bool liesBetween(const Instruction *From, Instruction *Between,1219 const Instruction *To, const DominatorTree *DT) {1220 if (From->getParent() == Between->getParent())1221 return DT->dominates(From, Between);1222 SmallPtrSet<BasicBlock *, 1> Exclusion;1223 Exclusion.insert(Between->getParent());1224 return !isPotentiallyReachable(From, To, &Exclusion, DT);1225}1226 1227static const Instruction *findMayClobberedPtrAccess(LoadInst *Load,1228 const DominatorTree *DT) {1229 Value *PtrOp = Load->getPointerOperand();1230 if (!PtrOp->hasUseList())1231 return nullptr;1232 1233 Instruction *OtherAccess = nullptr;1234 1235 for (auto *U : PtrOp->users()) {1236 if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U))) {1237 auto *I = cast<Instruction>(U);1238 if (I->getFunction() == Load->getFunction() && DT->dominates(I, Load)) {1239 // Use the most immediately dominating value.1240 if (OtherAccess) {1241 if (DT->dominates(OtherAccess, I))1242 OtherAccess = I;1243 else1244 assert(U == OtherAccess || DT->dominates(I, OtherAccess));1245 } else1246 OtherAccess = I;1247 }1248 }1249 }1250 1251 if (OtherAccess)1252 return OtherAccess;1253 1254 // There is no dominating use, check if we can find a closest non-dominating1255 // use that lies between any other potentially available use and Load.1256 for (auto *U : PtrOp->users()) {1257 if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U))) {1258 auto *I = cast<Instruction>(U);1259 if (I->getFunction() == Load->getFunction() &&1260 isPotentiallyReachable(I, Load, nullptr, DT)) {1261 if (OtherAccess) {1262 if (liesBetween(OtherAccess, I, Load, DT)) {1263 OtherAccess = I;1264 } else if (!liesBetween(I, OtherAccess, Load, DT)) {1265 // These uses are both partially available at Load were it not for1266 // the clobber, but neither lies strictly after the other.1267 OtherAccess = nullptr;1268 break;1269 } // else: keep current OtherAccess since it lies between U and1270 // Load.1271 } else {1272 OtherAccess = I;1273 }1274 }1275 }1276 }1277 1278 return OtherAccess;1279}1280 1281/// Try to locate the three instruction involved in a missed1282/// load-elimination case that is due to an intervening store.1283static void reportMayClobberedLoad(LoadInst *Load, MemDepResult DepInfo,1284 const DominatorTree *DT,1285 OptimizationRemarkEmitter *ORE) {1286 using namespace ore;1287 1288 OptimizationRemarkMissed R(DEBUG_TYPE, "LoadClobbered", Load);1289 R << "load of type " << NV("Type", Load->getType()) << " not eliminated"1290 << setExtraArgs();1291 1292 const Instruction *OtherAccess = findMayClobberedPtrAccess(Load, DT);1293 if (OtherAccess)1294 R << " in favor of " << NV("OtherAccess", OtherAccess);1295 1296 R << " because it is clobbered by " << NV("ClobberedBy", DepInfo.getInst());1297 1298 ORE->emit(R);1299}1300 1301// Find non-clobbered value for Loc memory location in extended basic block1302// (chain of basic blocks with single predecessors) starting From instruction.1303static Value *findDominatingValue(const MemoryLocation &Loc, Type *LoadTy,1304 Instruction *From, AAResults *AA) {1305 uint32_t NumVisitedInsts = 0;1306 BasicBlock *FromBB = From->getParent();1307 BatchAAResults BatchAA(*AA);1308 for (BasicBlock *BB = FromBB; BB; BB = BB->getSinglePredecessor())1309 for (auto *Inst = BB == FromBB ? From : BB->getTerminator();1310 Inst != nullptr; Inst = Inst->getPrevNode()) {1311 // Stop the search if limit is reached.1312 if (++NumVisitedInsts > MaxNumVisitedInsts)1313 return nullptr;1314 if (isModSet(BatchAA.getModRefInfo(Inst, Loc)))1315 return nullptr;1316 if (auto *LI = dyn_cast<LoadInst>(Inst))1317 if (LI->getPointerOperand() == Loc.Ptr && LI->getType() == LoadTy)1318 return LI;1319 }1320 return nullptr;1321}1322 1323std::optional<AvailableValue>1324GVNPass::AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,1325 Value *Address) {1326 assert(Load->isUnordered() && "rules below are incorrect for ordered access");1327 assert(DepInfo.isLocal() && "expected a local dependence");1328 1329 Instruction *DepInst = DepInfo.getInst();1330 1331 const DataLayout &DL = Load->getDataLayout();1332 if (DepInfo.isClobber()) {1333 // If the dependence is to a store that writes to a superset of the bits1334 // read by the load, we can extract the bits we need for the load from the1335 // stored value.1336 if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {1337 // Can't forward from non-atomic to atomic without violating memory model.1338 if (Address && Load->isAtomic() <= DepSI->isAtomic()) {1339 int Offset =1340 analyzeLoadFromClobberingStore(Load->getType(), Address, DepSI, DL);1341 if (Offset != -1)1342 return AvailableValue::get(DepSI->getValueOperand(), Offset);1343 }1344 }1345 1346 // Check to see if we have something like this:1347 // load i32* P1348 // load i8* (P+1)1349 // if we have this, replace the later with an extraction from the former.1350 if (LoadInst *DepLoad = dyn_cast<LoadInst>(DepInst)) {1351 // If this is a clobber and L is the first instruction in its block, then1352 // we have the first instruction in the entry block.1353 // Can't forward from non-atomic to atomic without violating memory model.1354 if (DepLoad != Load && Address &&1355 Load->isAtomic() <= DepLoad->isAtomic()) {1356 Type *LoadType = Load->getType();1357 int Offset = -1;1358 1359 // If MD reported clobber, check it was nested.1360 if (DepInfo.isClobber() &&1361 canCoerceMustAliasedValueToLoad(DepLoad, LoadType,1362 DepLoad->getFunction())) {1363 const auto ClobberOff = MD->getClobberOffset(DepLoad);1364 // GVN has no deal with a negative offset.1365 Offset = (ClobberOff == std::nullopt || *ClobberOff < 0)1366 ? -11367 : *ClobberOff;1368 }1369 if (Offset == -1)1370 Offset =1371 analyzeLoadFromClobberingLoad(LoadType, Address, DepLoad, DL);1372 if (Offset != -1)1373 return AvailableValue::getLoad(DepLoad, Offset);1374 }1375 }1376 1377 // If the clobbering value is a memset/memcpy/memmove, see if we can1378 // forward a value on from it.1379 if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {1380 if (Address && !Load->isAtomic()) {1381 int Offset = analyzeLoadFromClobberingMemInst(Load->getType(), Address,1382 DepMI, DL);1383 if (Offset != -1)1384 return AvailableValue::getMI(DepMI, Offset);1385 }1386 }1387 1388 // Nothing known about this clobber, have to be conservative.1389 LLVM_DEBUG(1390 // fast print dep, using operator<< on instruction is too slow.1391 dbgs() << "GVN: load "; Load->printAsOperand(dbgs());1392 dbgs() << " is clobbered by " << *DepInst << '\n';);1393 if (ORE->allowExtraAnalysis(DEBUG_TYPE))1394 reportMayClobberedLoad(Load, DepInfo, DT, ORE);1395 1396 return std::nullopt;1397 }1398 assert(DepInfo.isDef() && "follows from above");1399 1400 // Loading the alloca -> undef.1401 // Loading immediately after lifetime begin -> undef.1402 if (isa<AllocaInst>(DepInst) || isLifetimeStart(DepInst))1403 return AvailableValue::get(UndefValue::get(Load->getType()));1404 1405 if (Constant *InitVal =1406 getInitialValueOfAllocation(DepInst, TLI, Load->getType()))1407 return AvailableValue::get(InitVal);1408 1409 if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) {1410 // Reject loads and stores that are to the same address but are of1411 // different types if we have to. If the stored value is convertable to1412 // the loaded value, we can reuse it.1413 if (!canCoerceMustAliasedValueToLoad(S->getValueOperand(), Load->getType(),1414 S->getFunction()))1415 return std::nullopt;1416 1417 // Can't forward from non-atomic to atomic without violating memory model.1418 if (S->isAtomic() < Load->isAtomic())1419 return std::nullopt;1420 1421 return AvailableValue::get(S->getValueOperand());1422 }1423 1424 if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) {1425 // If the types mismatch and we can't handle it, reject reuse of the load.1426 // If the stored value is larger or equal to the loaded value, we can reuse1427 // it.1428 if (!canCoerceMustAliasedValueToLoad(LD, Load->getType(),1429 LD->getFunction()))1430 return std::nullopt;1431 1432 // Can't forward from non-atomic to atomic without violating memory model.1433 if (LD->isAtomic() < Load->isAtomic())1434 return std::nullopt;1435 1436 return AvailableValue::getLoad(LD);1437 }1438 1439 // Check if load with Addr dependent from select can be converted to select1440 // between load values. There must be no instructions between the found1441 // loads and DepInst that may clobber the loads.1442 if (auto *Sel = dyn_cast<SelectInst>(DepInst)) {1443 assert(Sel->getType() == Load->getPointerOperandType());1444 auto Loc = MemoryLocation::get(Load);1445 Value *V1 =1446 findDominatingValue(Loc.getWithNewPtr(Sel->getTrueValue()),1447 Load->getType(), DepInst, getAliasAnalysis());1448 if (!V1)1449 return std::nullopt;1450 Value *V2 =1451 findDominatingValue(Loc.getWithNewPtr(Sel->getFalseValue()),1452 Load->getType(), DepInst, getAliasAnalysis());1453 if (!V2)1454 return std::nullopt;1455 return AvailableValue::getSelect(Sel, V1, V2);1456 }1457 1458 // Unknown def - must be conservative.1459 LLVM_DEBUG(1460 // fast print dep, using operator<< on instruction is too slow.1461 dbgs() << "GVN: load "; Load->printAsOperand(dbgs());1462 dbgs() << " has unknown def " << *DepInst << '\n';);1463 return std::nullopt;1464}1465 1466void GVNPass::AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,1467 AvailValInBlkVect &ValuesPerBlock,1468 UnavailBlkVect &UnavailableBlocks) {1469 // Filter out useless results (non-locals, etc). Keep track of the blocks1470 // where we have a value available in repl, also keep track of whether we see1471 // dependencies that produce an unknown value for the load (such as a call1472 // that could potentially clobber the load).1473 for (const auto &Dep : Deps) {1474 BasicBlock *DepBB = Dep.getBB();1475 MemDepResult DepInfo = Dep.getResult();1476 1477 if (DeadBlocks.count(DepBB)) {1478 // Dead dependent mem-op disguise as a load evaluating the same value1479 // as the load in question.1480 ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB));1481 continue;1482 }1483 1484 if (!DepInfo.isLocal()) {1485 UnavailableBlocks.push_back(DepBB);1486 continue;1487 }1488 1489 // The address being loaded in this non-local block may not be the same as1490 // the pointer operand of the load if PHI translation occurs. Make sure1491 // to consider the right address.1492 if (auto AV = AnalyzeLoadAvailability(Load, DepInfo, Dep.getAddress())) {1493 // subtlety: because we know this was a non-local dependency, we know1494 // it's safe to materialize anywhere between the instruction within1495 // DepInfo and the end of it's block.1496 ValuesPerBlock.push_back(1497 AvailableValueInBlock::get(DepBB, std::move(*AV)));1498 } else {1499 UnavailableBlocks.push_back(DepBB);1500 }1501 }1502 1503 assert(Deps.size() == ValuesPerBlock.size() + UnavailableBlocks.size() &&1504 "post condition violation");1505}1506 1507/// Given the following code, v1 is partially available on some edges, but not1508/// available on the edge from PredBB. This function tries to find if there is1509/// another identical load in the other successor of PredBB.1510///1511/// v0 = load %addr1512/// br %LoadBB1513///1514/// LoadBB:1515/// v1 = load %addr1516/// ...1517///1518/// PredBB:1519/// ...1520/// br %cond, label %LoadBB, label %SuccBB1521///1522/// SuccBB:1523/// v2 = load %addr1524/// ...1525///1526LoadInst *GVNPass::findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,1527 LoadInst *Load) {1528 // For simplicity we handle a Pred has 2 successors only.1529 auto *Term = Pred->getTerminator();1530 if (Term->getNumSuccessors() != 2 || Term->isSpecialTerminator())1531 return nullptr;1532 auto *SuccBB = Term->getSuccessor(0);1533 if (SuccBB == LoadBB)1534 SuccBB = Term->getSuccessor(1);1535 if (!SuccBB->getSinglePredecessor())1536 return nullptr;1537 1538 unsigned int NumInsts = MaxNumInsnsPerBlock;1539 for (Instruction &Inst : *SuccBB) {1540 if (Inst.isDebugOrPseudoInst())1541 continue;1542 if (--NumInsts == 0)1543 return nullptr;1544 1545 if (!Inst.isIdenticalTo(Load))1546 continue;1547 1548 MemDepResult Dep = MD->getDependency(&Inst);1549 // If an identical load doesn't depends on any local instructions, it can1550 // be safely moved to PredBB.1551 // Also check for the implicit control flow instructions. See the comments1552 // in PerformLoadPRE for details.1553 if (Dep.isNonLocal() && !ICF->isDominatedByICFIFromSameBlock(&Inst))1554 return cast<LoadInst>(&Inst);1555 1556 // Otherwise there is something in the same BB clobbers the memory, we can't1557 // move this and later load to PredBB.1558 return nullptr;1559 }1560 1561 return nullptr;1562}1563 1564void GVNPass::eliminatePartiallyRedundantLoad(1565 LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,1566 MapVector<BasicBlock *, Value *> &AvailableLoads,1567 MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad) {1568 for (const auto &AvailableLoad : AvailableLoads) {1569 BasicBlock *UnavailableBlock = AvailableLoad.first;1570 Value *LoadPtr = AvailableLoad.second;1571 1572 auto *NewLoad = new LoadInst(1573 Load->getType(), LoadPtr, Load->getName() + ".pre", Load->isVolatile(),1574 Load->getAlign(), Load->getOrdering(), Load->getSyncScopeID(),1575 UnavailableBlock->getTerminator()->getIterator());1576 NewLoad->setDebugLoc(Load->getDebugLoc());1577 if (MSSAU) {1578 auto *NewAccess = MSSAU->createMemoryAccessInBB(1579 NewLoad, nullptr, NewLoad->getParent(), MemorySSA::BeforeTerminator);1580 if (auto *NewDef = dyn_cast<MemoryDef>(NewAccess))1581 MSSAU->insertDef(NewDef, /*RenameUses=*/true);1582 else1583 MSSAU->insertUse(cast<MemoryUse>(NewAccess), /*RenameUses=*/true);1584 }1585 1586 // Transfer the old load's AA tags to the new load.1587 AAMDNodes Tags = Load->getAAMetadata();1588 if (Tags)1589 NewLoad->setAAMetadata(Tags);1590 1591 if (auto *MD = Load->getMetadata(LLVMContext::MD_invariant_load))1592 NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);1593 if (auto *InvGroupMD = Load->getMetadata(LLVMContext::MD_invariant_group))1594 NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);1595 if (auto *RangeMD = Load->getMetadata(LLVMContext::MD_range))1596 NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);1597 if (auto *AccessMD = Load->getMetadata(LLVMContext::MD_access_group))1598 if (LI->getLoopFor(Load->getParent()) == LI->getLoopFor(UnavailableBlock))1599 NewLoad->setMetadata(LLVMContext::MD_access_group, AccessMD);1600 1601 // We do not propagate the old load's debug location, because the new1602 // load now lives in a different BB, and we want to avoid a jumpy line1603 // table.1604 // FIXME: How do we retain source locations without causing poor debugging1605 // behavior?1606 1607 // Add the newly created load.1608 ValuesPerBlock.push_back(1609 AvailableValueInBlock::get(UnavailableBlock, NewLoad));1610 MD->invalidateCachedPointerInfo(LoadPtr);1611 LLVM_DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n');1612 1613 // For PredBB in CriticalEdgePredAndLoad we need to replace the uses of old1614 // load instruction with the new created load instruction.1615 if (CriticalEdgePredAndLoad) {1616 auto It = CriticalEdgePredAndLoad->find(UnavailableBlock);1617 if (It != CriticalEdgePredAndLoad->end()) {1618 ++NumPRELoadMoved2CEPred;1619 ICF->insertInstructionTo(NewLoad, UnavailableBlock);1620 LoadInst *OldLoad = It->second;1621 combineMetadataForCSE(NewLoad, OldLoad, false);1622 OldLoad->replaceAllUsesWith(NewLoad);1623 replaceValuesPerBlockEntry(ValuesPerBlock, OldLoad, NewLoad);1624 if (uint32_t ValNo = VN.lookup(OldLoad, false))1625 LeaderTable.erase(ValNo, OldLoad, OldLoad->getParent());1626 removeInstruction(OldLoad);1627 }1628 }1629 }1630 1631 // Perform PHI construction.1632 Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);1633 // ConstructSSAForLoadSet is responsible for combining metadata.1634 ICF->removeUsersOf(Load);1635 Load->replaceAllUsesWith(V);1636 if (isa<PHINode>(V))1637 V->takeName(Load);1638 if (Instruction *I = dyn_cast<Instruction>(V))1639 I->setDebugLoc(Load->getDebugLoc());1640 if (V->getType()->isPtrOrPtrVectorTy())1641 MD->invalidateCachedPointerInfo(V);1642 ORE->emit([&]() {1643 return OptimizationRemark(DEBUG_TYPE, "LoadPRE", Load)1644 << "load eliminated by PRE";1645 });1646 salvageAndRemoveInstruction(Load);1647}1648 1649bool GVNPass::PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,1650 UnavailBlkVect &UnavailableBlocks) {1651 // Okay, we have *some* definitions of the value. This means that the value1652 // is available in some of our (transitive) predecessors. Lets think about1653 // doing PRE of this load. This will involve inserting a new load into the1654 // predecessor when it's not available. We could do this in general, but1655 // prefer to not increase code size. As such, we only do this when we know1656 // that we only have to insert *one* load (which means we're basically moving1657 // the load, not inserting a new one).1658 1659 SmallPtrSet<BasicBlock *, 4> Blockers(llvm::from_range, UnavailableBlocks);1660 1661 // Let's find the first basic block with more than one predecessor. Walk1662 // backwards through predecessors if needed.1663 BasicBlock *LoadBB = Load->getParent();1664 BasicBlock *TmpBB = LoadBB;1665 1666 // Check that there is no implicit control flow instructions above our load in1667 // its block. If there is an instruction that doesn't always pass the1668 // execution to the following instruction, then moving through it may become1669 // invalid. For example:1670 //1671 // int arr[LEN];1672 // int index = ???;1673 // ...1674 // guard(0 <= index && index < LEN);1675 // use(arr[index]);1676 //1677 // It is illegal to move the array access to any point above the guard,1678 // because if the index is out of bounds we should deoptimize rather than1679 // access the array.1680 // Check that there is no guard in this block above our instruction.1681 bool MustEnsureSafetyOfSpeculativeExecution =1682 ICF->isDominatedByICFIFromSameBlock(Load);1683 1684 while (TmpBB->getSinglePredecessor()) {1685 TmpBB = TmpBB->getSinglePredecessor();1686 if (TmpBB == LoadBB) // Infinite (unreachable) loop.1687 return false;1688 if (Blockers.count(TmpBB))1689 return false;1690 1691 // If any of these blocks has more than one successor (i.e. if the edge we1692 // just traversed was critical), then there are other paths through this1693 // block along which the load may not be anticipated. Hoisting the load1694 // above this block would be adding the load to execution paths along1695 // which it was not previously executed.1696 if (TmpBB->getTerminator()->getNumSuccessors() != 1)1697 return false;1698 1699 // Check that there is no implicit control flow in a block above.1700 MustEnsureSafetyOfSpeculativeExecution =1701 MustEnsureSafetyOfSpeculativeExecution || ICF->hasICF(TmpBB);1702 }1703 1704 assert(TmpBB);1705 LoadBB = TmpBB;1706 1707 // Check to see how many predecessors have the loaded value fully1708 // available.1709 MapVector<BasicBlock *, Value *> PredLoads;1710 DenseMap<BasicBlock *, AvailabilityState> FullyAvailableBlocks;1711 for (const AvailableValueInBlock &AV : ValuesPerBlock)1712 FullyAvailableBlocks[AV.BB] = AvailabilityState::Available;1713 for (BasicBlock *UnavailableBB : UnavailableBlocks)1714 FullyAvailableBlocks[UnavailableBB] = AvailabilityState::Unavailable;1715 1716 // The edge from Pred to LoadBB is a critical edge will be splitted.1717 SmallVector<BasicBlock *, 4> CriticalEdgePredSplit;1718 // The edge from Pred to LoadBB is a critical edge, another successor of Pred1719 // contains a load can be moved to Pred. This data structure maps the Pred to1720 // the movable load.1721 MapVector<BasicBlock *, LoadInst *> CriticalEdgePredAndLoad;1722 for (BasicBlock *Pred : predecessors(LoadBB)) {1723 // If any predecessor block is an EH pad that does not allow non-PHI1724 // instructions before the terminator, we can't PRE the load.1725 if (Pred->getTerminator()->isEHPad()) {1726 LLVM_DEBUG(1727 dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"1728 << Pred->getName() << "': " << *Load << '\n');1729 return false;1730 }1731 1732 if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks)) {1733 continue;1734 }1735 1736 if (Pred->getTerminator()->getNumSuccessors() != 1) {1737 if (isa<IndirectBrInst>(Pred->getTerminator())) {1738 LLVM_DEBUG(1739 dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"1740 << Pred->getName() << "': " << *Load << '\n');1741 return false;1742 }1743 1744 if (LoadBB->isEHPad()) {1745 LLVM_DEBUG(1746 dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"1747 << Pred->getName() << "': " << *Load << '\n');1748 return false;1749 }1750 1751 // Do not split backedge as it will break the canonical loop form.1752 if (!isLoadPRESplitBackedgeEnabled())1753 if (DT->dominates(LoadBB, Pred)) {1754 LLVM_DEBUG(1755 dbgs()1756 << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"1757 << Pred->getName() << "': " << *Load << '\n');1758 return false;1759 }1760 1761 if (LoadInst *LI = findLoadToHoistIntoPred(Pred, LoadBB, Load))1762 CriticalEdgePredAndLoad[Pred] = LI;1763 else1764 CriticalEdgePredSplit.push_back(Pred);1765 } else {1766 // Only add the predecessors that will not be split for now.1767 PredLoads[Pred] = nullptr;1768 }1769 }1770 1771 // Decide whether PRE is profitable for this load.1772 unsigned NumInsertPreds = PredLoads.size() + CriticalEdgePredSplit.size();1773 unsigned NumUnavailablePreds = NumInsertPreds +1774 CriticalEdgePredAndLoad.size();1775 assert(NumUnavailablePreds != 0 &&1776 "Fully available value should already be eliminated!");1777 (void)NumUnavailablePreds;1778 1779 // If we need to insert new load in multiple predecessors, reject it.1780 // FIXME: If we could restructure the CFG, we could make a common pred with1781 // all the preds that don't have an available Load and insert a new load into1782 // that one block.1783 if (NumInsertPreds > 1)1784 return false;1785 1786 // Now we know where we will insert load. We must ensure that it is safe1787 // to speculatively execute the load at that points.1788 if (MustEnsureSafetyOfSpeculativeExecution) {1789 if (CriticalEdgePredSplit.size())1790 if (!isSafeToSpeculativelyExecute(Load, &*LoadBB->getFirstNonPHIIt(), AC,1791 DT))1792 return false;1793 for (auto &PL : PredLoads)1794 if (!isSafeToSpeculativelyExecute(Load, PL.first->getTerminator(), AC,1795 DT))1796 return false;1797 for (auto &CEP : CriticalEdgePredAndLoad)1798 if (!isSafeToSpeculativelyExecute(Load, CEP.first->getTerminator(), AC,1799 DT))1800 return false;1801 }1802 1803 // Split critical edges, and update the unavailable predecessors accordingly.1804 for (BasicBlock *OrigPred : CriticalEdgePredSplit) {1805 BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);1806 assert(!PredLoads.count(OrigPred) && "Split edges shouldn't be in map!");1807 PredLoads[NewPred] = nullptr;1808 LLVM_DEBUG(dbgs() << "Split critical edge " << OrigPred->getName() << "->"1809 << LoadBB->getName() << '\n');1810 }1811 1812 for (auto &CEP : CriticalEdgePredAndLoad)1813 PredLoads[CEP.first] = nullptr;1814 1815 // Check if the load can safely be moved to all the unavailable predecessors.1816 bool CanDoPRE = true;1817 const DataLayout &DL = Load->getDataLayout();1818 SmallVector<Instruction*, 8> NewInsts;1819 for (auto &PredLoad : PredLoads) {1820 BasicBlock *UnavailablePred = PredLoad.first;1821 1822 // Do PHI translation to get its value in the predecessor if necessary. The1823 // returned pointer (if non-null) is guaranteed to dominate UnavailablePred.1824 // We do the translation for each edge we skipped by going from Load's block1825 // to LoadBB, otherwise we might miss pieces needing translation.1826 1827 // If all preds have a single successor, then we know it is safe to insert1828 // the load on the pred (?!?), so we can insert code to materialize the1829 // pointer if it is not available.1830 Value *LoadPtr = Load->getPointerOperand();1831 BasicBlock *Cur = Load->getParent();1832 while (Cur != LoadBB) {1833 PHITransAddr Address(LoadPtr, DL, AC);1834 LoadPtr = Address.translateWithInsertion(Cur, Cur->getSinglePredecessor(),1835 *DT, NewInsts);1836 if (!LoadPtr) {1837 CanDoPRE = false;1838 break;1839 }1840 Cur = Cur->getSinglePredecessor();1841 }1842 1843 if (LoadPtr) {1844 PHITransAddr Address(LoadPtr, DL, AC);1845 LoadPtr = Address.translateWithInsertion(LoadBB, UnavailablePred, *DT,1846 NewInsts);1847 }1848 // If we couldn't find or insert a computation of this phi translated value,1849 // we fail PRE.1850 if (!LoadPtr) {1851 LLVM_DEBUG(dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "1852 << *Load->getPointerOperand() << "\n");1853 CanDoPRE = false;1854 break;1855 }1856 1857 PredLoad.second = LoadPtr;1858 }1859 1860 if (!CanDoPRE) {1861 while (!NewInsts.empty()) {1862 // Erase instructions generated by the failed PHI translation before1863 // trying to number them. PHI translation might insert instructions1864 // in basic blocks other than the current one, and we delete them1865 // directly, as salvageAndRemoveInstruction only allows removing from the1866 // current basic block.1867 NewInsts.pop_back_val()->eraseFromParent();1868 }1869 // HINT: Don't revert the edge-splitting as following transformation may1870 // also need to split these critical edges.1871 return !CriticalEdgePredSplit.empty();1872 }1873 1874 // Okay, we can eliminate this load by inserting a reload in the predecessor1875 // and using PHI construction to get the value in the other predecessors, do1876 // it.1877 LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOAD: " << *Load << '\n');1878 LLVM_DEBUG(if (!NewInsts.empty()) dbgs() << "INSERTED " << NewInsts.size()1879 << " INSTS: " << *NewInsts.back()1880 << '\n');1881 1882 // Assign value numbers to the new instructions.1883 for (Instruction *I : NewInsts) {1884 // Instructions that have been inserted in predecessor(s) to materialize1885 // the load address do not retain their original debug locations. Doing1886 // so could lead to confusing (but correct) source attributions.1887 I->updateLocationAfterHoist();1888 1889 // FIXME: We really _ought_ to insert these value numbers into their1890 // parent's availability map. However, in doing so, we risk getting into1891 // ordering issues. If a block hasn't been processed yet, we would be1892 // marking a value as AVAIL-IN, which isn't what we intend.1893 VN.lookupOrAdd(I);1894 }1895 1896 eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, PredLoads,1897 &CriticalEdgePredAndLoad);1898 ++NumPRELoad;1899 return true;1900}1901 1902bool GVNPass::performLoopLoadPRE(LoadInst *Load,1903 AvailValInBlkVect &ValuesPerBlock,1904 UnavailBlkVect &UnavailableBlocks) {1905 const Loop *L = LI->getLoopFor(Load->getParent());1906 // TODO: Generalize to other loop blocks that dominate the latch.1907 if (!L || L->getHeader() != Load->getParent())1908 return false;1909 1910 BasicBlock *Preheader = L->getLoopPreheader();1911 BasicBlock *Latch = L->getLoopLatch();1912 if (!Preheader || !Latch)1913 return false;1914 1915 Value *LoadPtr = Load->getPointerOperand();1916 // Must be available in preheader.1917 if (!L->isLoopInvariant(LoadPtr))1918 return false;1919 1920 // We plan to hoist the load to preheader without introducing a new fault.1921 // In order to do it, we need to prove that we cannot side-exit the loop1922 // once loop header is first entered before execution of the load.1923 if (ICF->isDominatedByICFIFromSameBlock(Load))1924 return false;1925 1926 BasicBlock *LoopBlock = nullptr;1927 for (auto *Blocker : UnavailableBlocks) {1928 // Blockers from outside the loop are handled in preheader.1929 if (!L->contains(Blocker))1930 continue;1931 1932 // Only allow one loop block. Loop header is not less frequently executed1933 // than each loop block, and likely it is much more frequently executed. But1934 // in case of multiple loop blocks, we need extra information (such as block1935 // frequency info) to understand whether it is profitable to PRE into1936 // multiple loop blocks.1937 if (LoopBlock)1938 return false;1939 1940 // Do not sink into inner loops. This may be non-profitable.1941 if (L != LI->getLoopFor(Blocker))1942 return false;1943 1944 // Blocks that dominate the latch execute on every single iteration, maybe1945 // except the last one. So PREing into these blocks doesn't make much sense1946 // in most cases. But the blocks that do not necessarily execute on each1947 // iteration are sometimes much colder than the header, and this is when1948 // PRE is potentially profitable.1949 if (DT->dominates(Blocker, Latch))1950 return false;1951 1952 // Make sure that the terminator itself doesn't clobber.1953 if (Blocker->getTerminator()->mayWriteToMemory())1954 return false;1955 1956 LoopBlock = Blocker;1957 }1958 1959 if (!LoopBlock)1960 return false;1961 1962 // Make sure the memory at this pointer cannot be freed, therefore we can1963 // safely reload from it after clobber.1964 if (LoadPtr->canBeFreed())1965 return false;1966 1967 // TODO: Support critical edge splitting if blocker has more than 1 successor.1968 MapVector<BasicBlock *, Value *> AvailableLoads;1969 AvailableLoads[LoopBlock] = LoadPtr;1970 AvailableLoads[Preheader] = LoadPtr;1971 1972 LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOOP LOAD: " << *Load << '\n');1973 eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, AvailableLoads,1974 /*CriticalEdgePredAndLoad*/ nullptr);1975 ++NumPRELoopLoad;1976 return true;1977}1978 1979static void reportLoadElim(LoadInst *Load, Value *AvailableValue,1980 OptimizationRemarkEmitter *ORE) {1981 using namespace ore;1982 1983 ORE->emit([&]() {1984 return OptimizationRemark(DEBUG_TYPE, "LoadElim", Load)1985 << "load of type " << NV("Type", Load->getType()) << " eliminated"1986 << setExtraArgs() << " in favor of "1987 << NV("InfavorOfValue", AvailableValue);1988 });1989}1990 1991/// Attempt to eliminate a load whose dependencies are1992/// non-local by performing PHI construction.1993bool GVNPass::processNonLocalLoad(LoadInst *Load) {1994 // Non-local speculations are not allowed under asan.1995 if (Load->getParent()->getParent()->hasFnAttribute(1996 Attribute::SanitizeAddress) ||1997 Load->getParent()->getParent()->hasFnAttribute(1998 Attribute::SanitizeHWAddress))1999 return false;2000 2001 // Step 1: Find the non-local dependencies of the load.2002 LoadDepVect Deps;2003 MD->getNonLocalPointerDependency(Load, Deps);2004 2005 // If we had to process more than one hundred blocks to find the2006 // dependencies, this load isn't worth worrying about. Optimizing2007 // it will be too expensive.2008 unsigned NumDeps = Deps.size();2009 if (NumDeps > MaxNumDeps)2010 return false;2011 2012 // If we had a phi translation failure, we'll have a single entry which is a2013 // clobber in the current block. Reject this early.2014 if (NumDeps == 1 &&2015 !Deps[0].getResult().isDef() && !Deps[0].getResult().isClobber()) {2016 LLVM_DEBUG(dbgs() << "GVN: non-local load "; Load->printAsOperand(dbgs());2017 dbgs() << " has unknown dependencies\n";);2018 return false;2019 }2020 2021 bool Changed = false;2022 // If this load follows a GEP, see if we can PRE the indices before analyzing.2023 if (GetElementPtrInst *GEP =2024 dyn_cast<GetElementPtrInst>(Load->getOperand(0))) {2025 for (Use &U : GEP->indices())2026 if (Instruction *I = dyn_cast<Instruction>(U.get()))2027 Changed |= performScalarPRE(I);2028 }2029 2030 // Step 2: Analyze the availability of the load.2031 AvailValInBlkVect ValuesPerBlock;2032 UnavailBlkVect UnavailableBlocks;2033 AnalyzeLoadAvailability(Load, Deps, ValuesPerBlock, UnavailableBlocks);2034 2035 // If we have no predecessors that produce a known value for this load, exit2036 // early.2037 if (ValuesPerBlock.empty())2038 return Changed;2039 2040 // Step 3: Eliminate fully redundancy.2041 //2042 // If all of the instructions we depend on produce a known value for this2043 // load, then it is fully redundant and we can use PHI insertion to compute2044 // its value. Insert PHIs and remove the fully redundant value now.2045 if (UnavailableBlocks.empty()) {2046 LLVM_DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *Load << '\n');2047 2048 // Perform PHI construction.2049 Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);2050 // ConstructSSAForLoadSet is responsible for combining metadata.2051 ICF->removeUsersOf(Load);2052 Load->replaceAllUsesWith(V);2053 2054 if (isa<PHINode>(V))2055 V->takeName(Load);2056 if (Instruction *I = dyn_cast<Instruction>(V))2057 // If instruction I has debug info, then we should not update it.2058 // Also, if I has a null DebugLoc, then it is still potentially incorrect2059 // to propagate Load's DebugLoc because Load may not post-dominate I.2060 if (Load->getDebugLoc() && Load->getParent() == I->getParent())2061 I->setDebugLoc(Load->getDebugLoc());2062 if (V->getType()->isPtrOrPtrVectorTy())2063 MD->invalidateCachedPointerInfo(V);2064 ++NumGVNLoad;2065 reportLoadElim(Load, V, ORE);2066 salvageAndRemoveInstruction(Load);2067 return true;2068 }2069 2070 // Step 4: Eliminate partial redundancy.2071 if (!isPREEnabled() || !isLoadPREEnabled())2072 return Changed;2073 if (!isLoadInLoopPREEnabled() && LI->getLoopFor(Load->getParent()))2074 return Changed;2075 2076 if (performLoopLoadPRE(Load, ValuesPerBlock, UnavailableBlocks) ||2077 PerformLoadPRE(Load, ValuesPerBlock, UnavailableBlocks))2078 return true;2079 2080 return Changed;2081}2082 2083bool GVNPass::processAssumeIntrinsic(AssumeInst *IntrinsicI) {2084 Value *V = IntrinsicI->getArgOperand(0);2085 2086 if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {2087 if (Cond->isZero()) {2088 Type *Int8Ty = Type::getInt8Ty(V->getContext());2089 Type *PtrTy = PointerType::get(V->getContext(), 0);2090 // Insert a new store to null instruction before the load to indicate that2091 // this code is not reachable. FIXME: We could insert unreachable2092 // instruction directly because we can modify the CFG.2093 auto *NewS =2094 new StoreInst(PoisonValue::get(Int8Ty), Constant::getNullValue(PtrTy),2095 IntrinsicI->getIterator());2096 if (MSSAU) {2097 const MemoryUseOrDef *FirstNonDom = nullptr;2098 const auto *AL =2099 MSSAU->getMemorySSA()->getBlockAccesses(IntrinsicI->getParent());2100 2101 // If there are accesses in the current basic block, find the first one2102 // that does not come before NewS. The new memory access is inserted2103 // after the found access or before the terminator if no such access is2104 // found.2105 if (AL) {2106 for (const auto &Acc : *AL) {2107 if (auto *Current = dyn_cast<MemoryUseOrDef>(&Acc))2108 if (!Current->getMemoryInst()->comesBefore(NewS)) {2109 FirstNonDom = Current;2110 break;2111 }2112 }2113 }2114 2115 auto *NewDef =2116 FirstNonDom ? MSSAU->createMemoryAccessBefore(2117 NewS, nullptr,2118 const_cast<MemoryUseOrDef *>(FirstNonDom))2119 : MSSAU->createMemoryAccessInBB(2120 NewS, nullptr,2121 NewS->getParent(), MemorySSA::BeforeTerminator);2122 2123 MSSAU->insertDef(cast<MemoryDef>(NewDef), /*RenameUses=*/false);2124 }2125 }2126 if (isAssumeWithEmptyBundle(*IntrinsicI)) {2127 salvageAndRemoveInstruction(IntrinsicI);2128 return true;2129 }2130 return false;2131 }2132 2133 if (isa<Constant>(V)) {2134 // If it's not false, and constant, it must evaluate to true. This means our2135 // assume is assume(true), and thus, pointless, and we don't want to do2136 // anything more here.2137 return false;2138 }2139 2140 Constant *True = ConstantInt::getTrue(V->getContext());2141 return propagateEquality(V, True, IntrinsicI);2142}2143 2144static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {2145 patchReplacementInstruction(I, Repl);2146 I->replaceAllUsesWith(Repl);2147}2148 2149/// Attempt to eliminate a load, first by eliminating it2150/// locally, and then attempting non-local elimination if that fails.2151bool GVNPass::processLoad(LoadInst *L) {2152 if (!MD)2153 return false;2154 2155 // This code hasn't been audited for ordered or volatile memory access.2156 if (!L->isUnordered())2157 return false;2158 2159 if (L->getType()->isTokenLikeTy())2160 return false;2161 2162 if (L->use_empty()) {2163 salvageAndRemoveInstruction(L);2164 return true;2165 }2166 2167 // ... to a pointer that has been loaded from before...2168 MemDepResult Dep = MD->getDependency(L);2169 2170 // If it is defined in another block, try harder.2171 if (Dep.isNonLocal())2172 return processNonLocalLoad(L);2173 2174 // Only handle the local case below.2175 if (!Dep.isLocal()) {2176 // This might be a NonFuncLocal or an Unknown.2177 LLVM_DEBUG(2178 // fast print dep, using operator<< on instruction is too slow.2179 dbgs() << "GVN: load "; L->printAsOperand(dbgs());2180 dbgs() << " has unknown dependence\n";);2181 return false;2182 }2183 2184 auto AV = AnalyzeLoadAvailability(L, Dep, L->getPointerOperand());2185 if (!AV)2186 return false;2187 2188 Value *AvailableValue = AV->MaterializeAdjustedValue(L, L);2189 2190 // MaterializeAdjustedValue is responsible for combining metadata.2191 ICF->removeUsersOf(L);2192 L->replaceAllUsesWith(AvailableValue);2193 if (MSSAU)2194 MSSAU->removeMemoryAccess(L);2195 ++NumGVNLoad;2196 reportLoadElim(L, AvailableValue, ORE);2197 salvageAndRemoveInstruction(L);2198 // Tell MDA to reexamine the reused pointer since we might have more2199 // information after forwarding it.2200 if (MD && AvailableValue->getType()->isPtrOrPtrVectorTy())2201 MD->invalidateCachedPointerInfo(AvailableValue);2202 return true;2203}2204 2205// Attempt to process masked loads which have loaded from2206// masked stores with the same mask2207bool GVNPass::processMaskedLoad(IntrinsicInst *I) {2208 if (!MD)2209 return false;2210 MemDepResult Dep = MD->getDependency(I);2211 Instruction *DepInst = Dep.getInst();2212 if (!DepInst || !Dep.isLocal() || !Dep.isDef())2213 return false;2214 2215 Value *Mask = I->getOperand(1);2216 Value *Passthrough = I->getOperand(2);2217 Value *StoreVal;2218 if (!match(DepInst,2219 m_MaskedStore(m_Value(StoreVal), m_Value(), m_Specific(Mask))) ||2220 StoreVal->getType() != I->getType())2221 return false;2222 2223 // Remove the load but generate a select for the passthrough2224 Value *OpToForward = llvm::SelectInst::Create(Mask, StoreVal, Passthrough, "",2225 I->getIterator());2226 2227 ICF->removeUsersOf(I);2228 I->replaceAllUsesWith(OpToForward);2229 salvageAndRemoveInstruction(I);2230 ++NumGVNLoad;2231 return true;2232}2233 2234/// Return a pair the first field showing the value number of \p Exp and the2235/// second field showing whether it is a value number newly created.2236std::pair<uint32_t, bool>2237GVNPass::ValueTable::assignExpNewValueNum(Expression &Exp) {2238 uint32_t &E = ExpressionNumbering[Exp];2239 bool CreateNewValNum = !E;2240 if (CreateNewValNum) {2241 Expressions.push_back(Exp);2242 if (ExprIdx.size() < NextValueNumber + 1)2243 ExprIdx.resize(NextValueNumber * 2);2244 E = NextValueNumber;2245 ExprIdx[NextValueNumber++] = NextExprNumber++;2246 }2247 return {E, CreateNewValNum};2248}2249 2250/// Return whether all the values related with the same \p num are2251/// defined in \p BB.2252bool GVNPass::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB,2253 GVNPass &GVN) {2254 return all_of(2255 GVN.LeaderTable.getLeaders(Num),2256 [=](const LeaderMap::LeaderTableEntry &L) { return L.BB == BB; });2257}2258 2259/// Wrap phiTranslateImpl to provide caching functionality.2260uint32_t GVNPass::ValueTable::phiTranslate(const BasicBlock *Pred,2261 const BasicBlock *PhiBlock,2262 uint32_t Num, GVNPass &GVN) {2263 auto FindRes = PhiTranslateTable.find({Num, Pred});2264 if (FindRes != PhiTranslateTable.end())2265 return FindRes->second;2266 uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, GVN);2267 PhiTranslateTable.insert({{Num, Pred}, NewNum});2268 return NewNum;2269}2270 2271// Return true if the value number \p Num and NewNum have equal value.2272// Return false if the result is unknown.2273bool GVNPass::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum,2274 const BasicBlock *Pred,2275 const BasicBlock *PhiBlock,2276 GVNPass &GVN) {2277 CallInst *Call = nullptr;2278 auto Leaders = GVN.LeaderTable.getLeaders(Num);2279 for (const auto &Entry : Leaders) {2280 Call = dyn_cast<CallInst>(Entry.Val);2281 if (Call && Call->getParent() == PhiBlock)2282 break;2283 }2284 2285 if (AA->doesNotAccessMemory(Call))2286 return true;2287 2288 if (!MD || !AA->onlyReadsMemory(Call))2289 return false;2290 2291 MemDepResult LocalDep = MD->getDependency(Call);2292 if (!LocalDep.isNonLocal())2293 return false;2294 2295 const MemoryDependenceResults::NonLocalDepInfo &Deps =2296 MD->getNonLocalCallDependency(Call);2297 2298 // Check to see if the Call has no function local clobber.2299 for (const NonLocalDepEntry &D : Deps) {2300 if (D.getResult().isNonFuncLocal())2301 return true;2302 }2303 return false;2304}2305 2306/// Translate value number \p Num using phis, so that it has the values of2307/// the phis in BB.2308uint32_t GVNPass::ValueTable::phiTranslateImpl(const BasicBlock *Pred,2309 const BasicBlock *PhiBlock,2310 uint32_t Num, GVNPass &GVN) {2311 // See if we can refine the value number by looking at the PN incoming value2312 // for the given predecessor.2313 if (PHINode *PN = NumberingPhi[Num]) {2314 if (PN->getParent() != PhiBlock)2315 return Num;2316 for (unsigned I = 0; I != PN->getNumIncomingValues(); ++I) {2317 if (PN->getIncomingBlock(I) != Pred)2318 continue;2319 if (uint32_t TransVal = lookup(PN->getIncomingValue(I), false))2320 return TransVal;2321 }2322 return Num;2323 }2324 2325 if (BasicBlock *BB = NumberingBB[Num]) {2326 assert(MSSA && "NumberingBB is non-empty only when using MemorySSA");2327 // Value numbers of basic blocks are used to represent memory state in2328 // load/store instructions and read-only function calls when said state is2329 // set by a MemoryPhi.2330 if (BB != PhiBlock)2331 return Num;2332 MemoryPhi *MPhi = MSSA->getMemoryAccess(BB);2333 for (unsigned i = 0, N = MPhi->getNumIncomingValues(); i != N; ++i) {2334 if (MPhi->getIncomingBlock(i) != Pred)2335 continue;2336 MemoryAccess *MA = MPhi->getIncomingValue(i);2337 if (auto *PredPhi = dyn_cast<MemoryPhi>(MA))2338 return lookupOrAdd(PredPhi->getBlock());2339 if (MSSA->isLiveOnEntryDef(MA))2340 return lookupOrAdd(&BB->getParent()->getEntryBlock());2341 return lookupOrAdd(cast<MemoryUseOrDef>(MA)->getMemoryInst());2342 }2343 llvm_unreachable(2344 "CFG/MemorySSA mismatch: predecessor not found among incoming blocks");2345 }2346 2347 // If there is any value related with Num is defined in a BB other than2348 // PhiBlock, it cannot depend on a phi in PhiBlock without going through2349 // a backedge. We can do an early exit in that case to save compile time.2350 if (!areAllValsInBB(Num, PhiBlock, GVN))2351 return Num;2352 2353 if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)2354 return Num;2355 Expression Exp = Expressions[ExprIdx[Num]];2356 2357 for (unsigned I = 0; I < Exp.VarArgs.size(); I++) {2358 // For InsertValue and ExtractValue, some varargs are index numbers2359 // instead of value numbers. Those index numbers should not be2360 // translated.2361 if ((I > 1 && Exp.Opcode == Instruction::InsertValue) ||2362 (I > 0 && Exp.Opcode == Instruction::ExtractValue) ||2363 (I > 1 && Exp.Opcode == Instruction::ShuffleVector))2364 continue;2365 Exp.VarArgs[I] = phiTranslate(Pred, PhiBlock, Exp.VarArgs[I], GVN);2366 }2367 2368 if (Exp.Commutative) {2369 assert(Exp.VarArgs.size() >= 2 && "Unsupported commutative instruction!");2370 if (Exp.VarArgs[0] > Exp.VarArgs[1]) {2371 std::swap(Exp.VarArgs[0], Exp.VarArgs[1]);2372 uint32_t Opcode = Exp.Opcode >> 8;2373 if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)2374 Exp.Opcode = (Opcode << 8) |2375 CmpInst::getSwappedPredicate(2376 static_cast<CmpInst::Predicate>(Exp.Opcode & 255));2377 }2378 }2379 2380 if (uint32_t NewNum = ExpressionNumbering[Exp]) {2381 if (Exp.Opcode == Instruction::Call && NewNum != Num)2382 return areCallValsEqual(Num, NewNum, Pred, PhiBlock, GVN) ? NewNum : Num;2383 return NewNum;2384 }2385 return Num;2386}2387 2388/// Erase stale entry from phiTranslate cache so phiTranslate can be computed2389/// again.2390void GVNPass::ValueTable::eraseTranslateCacheEntry(2391 uint32_t Num, const BasicBlock &CurrBlock) {2392 for (const BasicBlock *Pred : predecessors(&CurrBlock))2393 PhiTranslateTable.erase({Num, Pred});2394}2395 2396// In order to find a leader for a given value number at a2397// specific basic block, we first obtain the list of all Values for that number,2398// and then scan the list to find one whose block dominates the block in2399// question. This is fast because dominator tree queries consist of only2400// a few comparisons of DFS numbers.2401Value *GVNPass::findLeader(const BasicBlock *BB, uint32_t Num) {2402 auto Leaders = LeaderTable.getLeaders(Num);2403 if (Leaders.empty())2404 return nullptr;2405 2406 Value *Val = nullptr;2407 for (const auto &Entry : Leaders) {2408 if (DT->dominates(Entry.BB, BB)) {2409 Val = Entry.Val;2410 if (isa<Constant>(Val))2411 return Val;2412 }2413 }2414 2415 return Val;2416}2417 2418/// There is an edge from 'Src' to 'Dst'. Return2419/// true if every path from the entry block to 'Dst' passes via this edge. In2420/// particular 'Dst' must not be reachable via another edge from 'Src'.2421static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E,2422 DominatorTree *DT) {2423 // While in theory it is interesting to consider the case in which Dst has2424 // more than one predecessor, because Dst might be part of a loop which is2425 // only reachable from Src, in practice it is pointless since at the time2426 // GVN runs all such loops have preheaders, which means that Dst will have2427 // been changed to have only one predecessor, namely Src.2428 const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();2429 assert((!Pred || Pred == E.getStart()) &&2430 "No edge between these basic blocks!");2431 return Pred != nullptr;2432}2433 2434void GVNPass::assignBlockRPONumber(Function &F) {2435 BlockRPONumber.clear();2436 uint32_t NextBlockNumber = 1;2437 ReversePostOrderTraversal<Function *> RPOT(&F);2438 for (BasicBlock *BB : RPOT)2439 BlockRPONumber[BB] = NextBlockNumber++;2440 InvalidBlockRPONumbers = false;2441}2442 2443/// The given values are known to be equal in every use2444/// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with2445/// 'RHS' everywhere in the scope. Returns whether a change was made.2446/// The Root may either be a basic block edge (for conditions) or an2447/// instruction (for assumes).2448bool GVNPass::propagateEquality(2449 Value *LHS, Value *RHS,2450 const std::variant<BasicBlockEdge, Instruction *> &Root) {2451 SmallVector<std::pair<Value*, Value*>, 4> Worklist;2452 Worklist.push_back(std::make_pair(LHS, RHS));2453 bool Changed = false;2454 SmallVector<const BasicBlock *> DominatedBlocks;2455 if (const BasicBlockEdge *Edge = std::get_if<BasicBlockEdge>(&Root)) {2456 // For speed, compute a conservative fast approximation to2457 // DT->dominates(Root, Root.getEnd());2458 if (isOnlyReachableViaThisEdge(*Edge, DT))2459 DominatedBlocks.push_back(Edge->getEnd());2460 } else {2461 Instruction *I = std::get<Instruction *>(Root);2462 for (const auto *Node : DT->getNode(I->getParent())->children())2463 DominatedBlocks.push_back(Node->getBlock());2464 }2465 2466 while (!Worklist.empty()) {2467 std::pair<Value*, Value*> Item = Worklist.pop_back_val();2468 LHS = Item.first; RHS = Item.second;2469 2470 if (LHS == RHS)2471 continue;2472 assert(LHS->getType() == RHS->getType() && "Equality but unequal types!");2473 2474 // Don't try to propagate equalities between constants.2475 if (isa<Constant>(LHS) && isa<Constant>(RHS))2476 continue;2477 2478 // Prefer a constant on the right-hand side, or an Argument if no constants.2479 if (isa<Constant>(LHS) || (isa<Argument>(LHS) && !isa<Constant>(RHS)))2480 std::swap(LHS, RHS);2481 assert((isa<Argument>(LHS) || isa<Instruction>(LHS)) && "Unexpected value!");2482 const DataLayout &DL =2483 isa<Argument>(LHS)2484 ? cast<Argument>(LHS)->getParent()->getDataLayout()2485 : cast<Instruction>(LHS)->getDataLayout();2486 2487 // If there is no obvious reason to prefer the left-hand side over the2488 // right-hand side, ensure the longest lived term is on the right-hand side,2489 // so the shortest lived term will be replaced by the longest lived.2490 // This tends to expose more simplifications.2491 uint32_t LVN = VN.lookupOrAdd(LHS);2492 if ((isa<Argument>(LHS) && isa<Argument>(RHS)) ||2493 (isa<Instruction>(LHS) && isa<Instruction>(RHS))) {2494 // Move the 'oldest' value to the right-hand side, using the value number2495 // as a proxy for age.2496 uint32_t RVN = VN.lookupOrAdd(RHS);2497 if (LVN < RVN) {2498 std::swap(LHS, RHS);2499 LVN = RVN;2500 }2501 }2502 2503 // If value numbering later sees that an instruction in the scope is equal2504 // to 'LHS' then ensure it will be turned into 'RHS'. In order to preserve2505 // the invariant that instructions only occur in the leader table for their2506 // own value number (this is used by removeFromLeaderTable), do not do this2507 // if RHS is an instruction (if an instruction in the scope is morphed into2508 // LHS then it will be turned into RHS by the next GVN iteration anyway, so2509 // using the leader table is about compiling faster, not optimizing better).2510 // The leader table only tracks basic blocks, not edges. Only add to if we2511 // have the simple case where the edge dominates the end.2512 if (!isa<Instruction>(RHS) && canReplacePointersIfEqual(LHS, RHS, DL))2513 for (const BasicBlock *BB : DominatedBlocks)2514 LeaderTable.insert(LVN, RHS, BB);2515 2516 // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope. As2517 // LHS always has at least one use that is not dominated by Root, this will2518 // never do anything if LHS has only one use.2519 if (!LHS->hasOneUse()) {2520 // Create a callback that captures the DL.2521 auto CanReplacePointersCallBack = [&DL](const Use &U, const Value *To) {2522 return canReplacePointersInUseIfEqual(U, To, DL);2523 };2524 unsigned NumReplacements;2525 if (const BasicBlockEdge *Edge = std::get_if<BasicBlockEdge>(&Root))2526 NumReplacements = replaceDominatedUsesWithIf(2527 LHS, RHS, *DT, *Edge, CanReplacePointersCallBack);2528 else2529 NumReplacements = replaceDominatedUsesWithIf(2530 LHS, RHS, *DT, std::get<Instruction *>(Root),2531 CanReplacePointersCallBack);2532 2533 if (NumReplacements > 0) {2534 Changed = true;2535 NumGVNEqProp += NumReplacements;2536 // Cached information for anything that uses LHS will be invalid.2537 if (MD)2538 MD->invalidateCachedPointerInfo(LHS);2539 }2540 }2541 2542 // Now try to deduce additional equalities from this one. For example, if2543 // the known equality was "(A != B)" == "false" then it follows that A and B2544 // are equal in the scope. Only boolean equalities with an explicit true or2545 // false RHS are currently supported.2546 if (!RHS->getType()->isIntegerTy(1))2547 // Not a boolean equality - bail out.2548 continue;2549 ConstantInt *CI = dyn_cast<ConstantInt>(RHS);2550 if (!CI)2551 // RHS neither 'true' nor 'false' - bail out.2552 continue;2553 // Whether RHS equals 'true'. Otherwise it equals 'false'.2554 bool IsKnownTrue = CI->isMinusOne();2555 bool IsKnownFalse = !IsKnownTrue;2556 2557 // If "A && B" is known true then both A and B are known true. If "A || B"2558 // is known false then both A and B are known false.2559 Value *A, *B;2560 if ((IsKnownTrue && match(LHS, m_LogicalAnd(m_Value(A), m_Value(B)))) ||2561 (IsKnownFalse && match(LHS, m_LogicalOr(m_Value(A), m_Value(B))))) {2562 Worklist.push_back(std::make_pair(A, RHS));2563 Worklist.push_back(std::make_pair(B, RHS));2564 continue;2565 }2566 2567 // If we are propagating an equality like "(A == B)" == "true" then also2568 // propagate the equality A == B. When propagating a comparison such as2569 // "(A >= B)" == "true", replace all instances of "A < B" with "false".2570 if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {2571 Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1);2572 2573 // If "A == B" is known true, or "A != B" is known false, then replace2574 // A with B everywhere in the scope. For floating point operations, we2575 // have to be careful since equality does not always imply equivalance.2576 if (Cmp->isEquivalence(IsKnownFalse))2577 Worklist.push_back(std::make_pair(Op0, Op1));2578 2579 // If "A >= B" is known true, replace "A < B" with false everywhere.2580 CmpInst::Predicate NotPred = Cmp->getInversePredicate();2581 Constant *NotVal = ConstantInt::get(Cmp->getType(), IsKnownFalse);2582 // Since we don't have the instruction "A < B" immediately to hand, work2583 // out the value number that it would have and use that to find an2584 // appropriate instruction (if any).2585 uint32_t NextNum = VN.getNextUnusedValueNumber();2586 uint32_t Num = VN.lookupOrAddCmp(Cmp->getOpcode(), NotPred, Op0, Op1);2587 // If the number we were assigned was brand new then there is no point in2588 // looking for an instruction realizing it: there cannot be one!2589 if (Num < NextNum) {2590 for (const auto &Entry : LeaderTable.getLeaders(Num)) {2591 // Only look at leaders that either dominate the start of the edge,2592 // or are dominated by the end. This check is not necessary for2593 // correctness, it only discards cases for which the following2594 // use replacement will not work anyway.2595 if (const BasicBlockEdge *Edge = std::get_if<BasicBlockEdge>(&Root)) {2596 if (!DT->dominates(Entry.BB, Edge->getStart()) &&2597 !DT->dominates(Edge->getEnd(), Entry.BB))2598 continue;2599 } else {2600 auto *InstBB = std::get<Instruction *>(Root)->getParent();2601 if (!DT->dominates(Entry.BB, InstBB) &&2602 !DT->dominates(InstBB, Entry.BB))2603 continue;2604 }2605 2606 Value *NotCmp = Entry.Val;2607 if (NotCmp && isa<Instruction>(NotCmp)) {2608 unsigned NumReplacements;2609 if (const BasicBlockEdge *Edge = std::get_if<BasicBlockEdge>(&Root))2610 NumReplacements =2611 replaceDominatedUsesWith(NotCmp, NotVal, *DT, *Edge);2612 else2613 NumReplacements = replaceDominatedUsesWith(2614 NotCmp, NotVal, *DT, std::get<Instruction *>(Root));2615 Changed |= NumReplacements > 0;2616 NumGVNEqProp += NumReplacements;2617 // Cached information for anything that uses NotCmp will be invalid.2618 if (MD)2619 MD->invalidateCachedPointerInfo(NotCmp);2620 }2621 }2622 }2623 // Ensure that any instruction in scope that gets the "A < B" value number2624 // is replaced with false.2625 // The leader table only tracks basic blocks, not edges. Only add to if we2626 // have the simple case where the edge dominates the end.2627 for (const BasicBlock *BB : DominatedBlocks)2628 LeaderTable.insert(Num, NotVal, BB);2629 2630 continue;2631 }2632 2633 // Propagate equalities that results from truncation with no unsigned wrap2634 // like (trunc nuw i64 %v to i1) == "true" or (trunc nuw i64 %v to i1) ==2635 // "false"2636 if (match(LHS, m_NUWTrunc(m_Value(A)))) {2637 Worklist.emplace_back(A, ConstantInt::get(A->getType(), IsKnownTrue));2638 continue;2639 }2640 2641 if (match(LHS, m_Not(m_Value(A)))) {2642 Worklist.emplace_back(A, ConstantInt::get(A->getType(), !IsKnownTrue));2643 continue;2644 }2645 }2646 2647 return Changed;2648}2649 2650/// When calculating availability, handle an instruction2651/// by inserting it into the appropriate sets.2652bool GVNPass::processInstruction(Instruction *I) {2653 // If the instruction can be easily simplified then do so now in preference2654 // to value numbering it. Value numbering often exposes redundancies, for2655 // example if it determines that %y is equal to %x then the instruction2656 // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.2657 const DataLayout &DL = I->getDataLayout();2658 if (Value *V = simplifyInstruction(I, {DL, TLI, DT, AC})) {2659 bool Changed = false;2660 if (!I->use_empty()) {2661 // Simplification can cause a special instruction to become not special.2662 // For example, devirtualization to a willreturn function.2663 ICF->removeUsersOf(I);2664 I->replaceAllUsesWith(V);2665 Changed = true;2666 }2667 if (isInstructionTriviallyDead(I, TLI)) {2668 salvageAndRemoveInstruction(I);2669 Changed = true;2670 }2671 if (Changed) {2672 if (MD && V->getType()->isPtrOrPtrVectorTy())2673 MD->invalidateCachedPointerInfo(V);2674 ++NumGVNSimpl;2675 return true;2676 }2677 }2678 2679 if (auto *Assume = dyn_cast<AssumeInst>(I))2680 return processAssumeIntrinsic(Assume);2681 2682 if (LoadInst *Load = dyn_cast<LoadInst>(I)) {2683 if (processLoad(Load))2684 return true;2685 2686 unsigned Num = VN.lookupOrAdd(Load);2687 LeaderTable.insert(Num, Load, Load->getParent());2688 return false;2689 }2690 2691 if (match(I, m_Intrinsic<Intrinsic::masked_load>()) &&2692 processMaskedLoad(cast<IntrinsicInst>(I)))2693 return true;2694 2695 // For conditional branches, we can perform simple conditional propagation on2696 // the condition value itself.2697 if (BranchInst *BI = dyn_cast<BranchInst>(I)) {2698 if (!BI->isConditional())2699 return false;2700 2701 if (isa<Constant>(BI->getCondition()))2702 return processFoldableCondBr(BI);2703 2704 Value *BranchCond = BI->getCondition();2705 BasicBlock *TrueSucc = BI->getSuccessor(0);2706 BasicBlock *FalseSucc = BI->getSuccessor(1);2707 // Avoid multiple edges early.2708 if (TrueSucc == FalseSucc)2709 return false;2710 2711 BasicBlock *Parent = BI->getParent();2712 bool Changed = false;2713 2714 Value *TrueVal = ConstantInt::getTrue(TrueSucc->getContext());2715 BasicBlockEdge TrueE(Parent, TrueSucc);2716 Changed |= propagateEquality(BranchCond, TrueVal, TrueE);2717 2718 Value *FalseVal = ConstantInt::getFalse(FalseSucc->getContext());2719 BasicBlockEdge FalseE(Parent, FalseSucc);2720 Changed |= propagateEquality(BranchCond, FalseVal, FalseE);2721 2722 return Changed;2723 }2724 2725 // For switches, propagate the case values into the case destinations.2726 if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {2727 Value *SwitchCond = SI->getCondition();2728 BasicBlock *Parent = SI->getParent();2729 bool Changed = false;2730 2731 // Remember how many outgoing edges there are to every successor.2732 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;2733 for (BasicBlock *Succ : successors(Parent))2734 ++SwitchEdges[Succ];2735 2736 for (const auto &Case : SI->cases()) {2737 BasicBlock *Dst = Case.getCaseSuccessor();2738 // If there is only a single edge, propagate the case value into it.2739 if (SwitchEdges.lookup(Dst) == 1) {2740 BasicBlockEdge E(Parent, Dst);2741 Changed |= propagateEquality(SwitchCond, Case.getCaseValue(), E);2742 }2743 }2744 return Changed;2745 }2746 2747 // Instructions with void type don't return a value, so there's2748 // no point in trying to find redundancies in them.2749 if (I->getType()->isVoidTy())2750 return false;2751 2752 uint32_t NextNum = VN.getNextUnusedValueNumber();2753 unsigned Num = VN.lookupOrAdd(I);2754 2755 // Allocations are always uniquely numbered, so we can save time and memory2756 // by fast failing them.2757 if (isa<AllocaInst>(I) || I->isTerminator() || isa<PHINode>(I)) {2758 LeaderTable.insert(Num, I, I->getParent());2759 return false;2760 }2761 2762 // If the number we were assigned was a brand new VN, then we don't2763 // need to do a lookup to see if the number already exists2764 // somewhere in the domtree: it can't!2765 if (Num >= NextNum) {2766 LeaderTable.insert(Num, I, I->getParent());2767 return false;2768 }2769 2770 // Perform fast-path value-number based elimination of values inherited from2771 // dominators.2772 Value *Repl = findLeader(I->getParent(), Num);2773 if (!Repl) {2774 // Failure, just remember this instance for future use.2775 LeaderTable.insert(Num, I, I->getParent());2776 return false;2777 }2778 2779 if (Repl == I) {2780 // If I was the result of a shortcut PRE, it might already be in the table2781 // and the best replacement for itself. Nothing to do.2782 return false;2783 }2784 2785 // Remove it!2786 patchAndReplaceAllUsesWith(I, Repl);2787 if (MD && Repl->getType()->isPtrOrPtrVectorTy())2788 MD->invalidateCachedPointerInfo(Repl);2789 salvageAndRemoveInstruction(I);2790 return true;2791}2792 2793/// runOnFunction - This is the main transformation entry point for a function.2794bool GVNPass::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,2795 const TargetLibraryInfo &RunTLI, AAResults &RunAA,2796 MemoryDependenceResults *RunMD, LoopInfo &LI,2797 OptimizationRemarkEmitter *RunORE, MemorySSA *MSSA) {2798 AC = &RunAC;2799 DT = &RunDT;2800 VN.setDomTree(DT);2801 TLI = &RunTLI;2802 VN.setAliasAnalysis(&RunAA);2803 MD = RunMD;2804 ImplicitControlFlowTracking ImplicitCFT;2805 ICF = &ImplicitCFT;2806 this->LI = &LI;2807 VN.setMemDep(MD);2808 VN.setMemorySSA(MSSA);2809 ORE = RunORE;2810 InvalidBlockRPONumbers = true;2811 MemorySSAUpdater Updater(MSSA);2812 MSSAU = MSSA ? &Updater : nullptr;2813 2814 bool Changed = false;2815 bool ShouldContinue = true;2816 2817 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);2818 // Merge unconditional branches, allowing PRE to catch more2819 // optimization opportunities.2820 for (BasicBlock &BB : make_early_inc_range(F)) {2821 bool RemovedBlock = MergeBlockIntoPredecessor(&BB, &DTU, &LI, MSSAU, MD);2822 if (RemovedBlock)2823 ++NumGVNBlocks;2824 2825 Changed |= RemovedBlock;2826 }2827 DTU.flush();2828 2829 unsigned Iteration = 0;2830 while (ShouldContinue) {2831 LLVM_DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n");2832 (void) Iteration;2833 ShouldContinue = iterateOnFunction(F);2834 Changed |= ShouldContinue;2835 ++Iteration;2836 }2837 2838 if (isPREEnabled()) {2839 // Fabricate val-num for dead-code in order to suppress assertion in2840 // performPRE().2841 assignValNumForDeadCode();2842 bool PREChanged = true;2843 while (PREChanged) {2844 PREChanged = performPRE(F);2845 Changed |= PREChanged;2846 }2847 }2848 2849 // FIXME: Should perform GVN again after PRE does something. PRE can move2850 // computations into blocks where they become fully redundant. Note that2851 // we can't do this until PRE's critical edge splitting updates memdep.2852 // Actually, when this happens, we should just fully integrate PRE into GVN.2853 2854 cleanupGlobalSets();2855 // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each2856 // iteration.2857 DeadBlocks.clear();2858 2859 if (MSSA && VerifyMemorySSA)2860 MSSA->verifyMemorySSA();2861 2862 return Changed;2863}2864 2865bool GVNPass::processBlock(BasicBlock *BB) {2866 if (DeadBlocks.count(BB))2867 return false;2868 2869 bool ChangedFunction = false;2870 2871 // Since we may not have visited the input blocks of the phis, we can't2872 // use our normal hash approach for phis. Instead, simply look for2873 // obvious duplicates. The first pass of GVN will tend to create2874 // identical phis, and the second or later passes can eliminate them.2875 SmallPtrSet<PHINode *, 8> PHINodesToRemove;2876 ChangedFunction |= EliminateDuplicatePHINodes(BB, PHINodesToRemove);2877 for (PHINode *PN : PHINodesToRemove) {2878 removeInstruction(PN);2879 }2880 for (Instruction &Inst : make_early_inc_range(*BB))2881 ChangedFunction |= processInstruction(&Inst);2882 return ChangedFunction;2883}2884 2885// Instantiate an expression in a predecessor that lacked it.2886bool GVNPass::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,2887 BasicBlock *Curr, unsigned int ValNo) {2888 // Because we are going top-down through the block, all value numbers2889 // will be available in the predecessor by the time we need them. Any2890 // that weren't originally present will have been instantiated earlier2891 // in this loop.2892 bool Success = true;2893 for (unsigned I = 0, E = Instr->getNumOperands(); I != E; ++I) {2894 Value *Op = Instr->getOperand(I);2895 if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op))2896 continue;2897 // This could be a newly inserted instruction, in which case, we won't2898 // find a value number, and should give up before we hurt ourselves.2899 // FIXME: Rewrite the infrastructure to let it easier to value number2900 // and process newly inserted instructions.2901 if (!VN.exists(Op)) {2902 Success = false;2903 break;2904 }2905 uint32_t TValNo =2906 VN.phiTranslate(Pred, Curr, VN.lookup(Op), *this);2907 if (Value *V = findLeader(Pred, TValNo)) {2908 Instr->setOperand(I, V);2909 } else {2910 Success = false;2911 break;2912 }2913 }2914 2915 // Fail out if we encounter an operand that is not available in2916 // the PRE predecessor. This is typically because of loads which2917 // are not value numbered precisely.2918 if (!Success)2919 return false;2920 2921 Instr->insertBefore(Pred->getTerminator()->getIterator());2922 Instr->setName(Instr->getName() + ".pre");2923 Instr->setDebugLoc(Instr->getDebugLoc());2924 2925 ICF->insertInstructionTo(Instr, Pred);2926 2927 unsigned Num = VN.lookupOrAdd(Instr);2928 VN.add(Instr, Num);2929 2930 // Update the availability map to include the new instruction.2931 LeaderTable.insert(Num, Instr, Pred);2932 return true;2933}2934 2935bool GVNPass::performScalarPRE(Instruction *CurInst) {2936 if (isa<AllocaInst>(CurInst) || CurInst->isTerminator() ||2937 isa<PHINode>(CurInst) || CurInst->getType()->isVoidTy() ||2938 CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() ||2939 CurInst->getType()->isTokenLikeTy())2940 return false;2941 2942 // Don't do PRE on compares. The PHI would prevent CodeGenPrepare from2943 // sinking the compare again, and it would force the code generator to2944 // move the i1 from processor flags or predicate registers into a general2945 // purpose register.2946 if (isa<CmpInst>(CurInst))2947 return false;2948 2949 // Don't do PRE on GEPs. The inserted PHI would prevent CodeGenPrepare from2950 // sinking the addressing mode computation back to its uses. Extending the2951 // GEP's live range increases the register pressure, and therefore it can2952 // introduce unnecessary spills.2953 //2954 // This doesn't prevent Load PRE. PHI translation will make the GEP available2955 // to the load by moving it to the predecessor block if necessary.2956 if (isa<GetElementPtrInst>(CurInst))2957 return false;2958 2959 if (auto *CallB = dyn_cast<CallBase>(CurInst)) {2960 // We don't currently value number ANY inline asm calls.2961 if (CallB->isInlineAsm())2962 return false;2963 }2964 2965 uint32_t ValNo = VN.lookup(CurInst);2966 2967 // Look for the predecessors for PRE opportunities. We're2968 // only trying to solve the basic diamond case, where2969 // a value is computed in the successor and one predecessor,2970 // but not the other. We also explicitly disallow cases2971 // where the successor is its own predecessor, because they're2972 // more complicated to get right.2973 unsigned NumWith = 0;2974 unsigned NumWithout = 0;2975 BasicBlock *PREPred = nullptr;2976 BasicBlock *CurrentBlock = CurInst->getParent();2977 2978 // Update the RPO numbers for this function.2979 if (InvalidBlockRPONumbers)2980 assignBlockRPONumber(*CurrentBlock->getParent());2981 2982 SmallVector<std::pair<Value *, BasicBlock *>, 8> PredMap;2983 for (BasicBlock *P : predecessors(CurrentBlock)) {2984 // We're not interested in PRE where blocks with predecessors that are2985 // not reachable.2986 if (!DT->isReachableFromEntry(P)) {2987 NumWithout = 2;2988 break;2989 }2990 // It is not safe to do PRE when P->CurrentBlock is a loop backedge.2991 assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) &&2992 "Invalid BlockRPONumber map.");2993 if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock]) {2994 NumWithout = 2;2995 break;2996 }2997 2998 uint32_t TValNo = VN.phiTranslate(P, CurrentBlock, ValNo, *this);2999 Value *PredV = findLeader(P, TValNo);3000 if (!PredV) {3001 PredMap.push_back(std::make_pair(static_cast<Value *>(nullptr), P));3002 PREPred = P;3003 ++NumWithout;3004 } else if (PredV == CurInst) {3005 // CurInst dominates this predecessor.3006 NumWithout = 2;3007 break;3008 } else {3009 PredMap.push_back(std::make_pair(PredV, P));3010 ++NumWith;3011 }3012 }3013 3014 // Don't do PRE when it might increase code size, i.e. when3015 // we would need to insert instructions in more than one pred.3016 if (NumWithout > 1 || NumWith == 0)3017 return false;3018 3019 // We may have a case where all predecessors have the instruction,3020 // and we just need to insert a phi node. Otherwise, perform3021 // insertion.3022 Instruction *PREInstr = nullptr;3023 3024 if (NumWithout != 0) {3025 if (!isSafeToSpeculativelyExecute(CurInst)) {3026 // It is only valid to insert a new instruction if the current instruction3027 // is always executed. An instruction with implicit control flow could3028 // prevent us from doing it. If we cannot speculate the execution, then3029 // PRE should be prohibited.3030 if (ICF->isDominatedByICFIFromSameBlock(CurInst))3031 return false;3032 }3033 3034 // Don't do PRE across indirect branch.3035 if (isa<IndirectBrInst>(PREPred->getTerminator()))3036 return false;3037 3038 // We can't do PRE safely on a critical edge, so instead we schedule3039 // the edge to be split and perform the PRE the next time we iterate3040 // on the function.3041 unsigned SuccNum = GetSuccessorNumber(PREPred, CurrentBlock);3042 if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {3043 ToSplit.push_back(std::make_pair(PREPred->getTerminator(), SuccNum));3044 return false;3045 }3046 // We need to insert somewhere, so let's give it a shot.3047 PREInstr = CurInst->clone();3048 if (!performScalarPREInsertion(PREInstr, PREPred, CurrentBlock, ValNo)) {3049 // If we failed insertion, make sure we remove the instruction.3050#ifndef NDEBUG3051 verifyRemoved(PREInstr);3052#endif3053 PREInstr->deleteValue();3054 return false;3055 }3056 }3057 3058 // Either we should have filled in the PRE instruction, or we should3059 // not have needed insertions.3060 assert(PREInstr != nullptr || NumWithout == 0);3061 3062 ++NumGVNPRE;3063 3064 // Create a PHI to make the value available in this block.3065 PHINode *Phi = PHINode::Create(CurInst->getType(), PredMap.size(),3066 CurInst->getName() + ".pre-phi");3067 Phi->insertBefore(CurrentBlock->begin());3068 for (auto &[V, BB] : PredMap) {3069 if (V) {3070 // If we use an existing value in this phi, we have to patch the original3071 // value because the phi will be used to replace a later value.3072 patchReplacementInstruction(CurInst, V);3073 Phi->addIncoming(V, BB);3074 } else3075 Phi->addIncoming(PREInstr, PREPred);3076 }3077 3078 VN.add(Phi, ValNo);3079 // After creating a new PHI for ValNo, the phi translate result for ValNo will3080 // be changed, so erase the related stale entries in phi translate cache.3081 VN.eraseTranslateCacheEntry(ValNo, *CurrentBlock);3082 LeaderTable.insert(ValNo, Phi, CurrentBlock);3083 Phi->setDebugLoc(CurInst->getDebugLoc());3084 CurInst->replaceAllUsesWith(Phi);3085 if (MD && Phi->getType()->isPtrOrPtrVectorTy())3086 MD->invalidateCachedPointerInfo(Phi);3087 LeaderTable.erase(ValNo, CurInst, CurrentBlock);3088 3089 LLVM_DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');3090 removeInstruction(CurInst);3091 ++NumGVNInstr;3092 3093 return true;3094}3095 3096/// Perform a purely local form of PRE that looks for diamond3097/// control flow patterns and attempts to perform simple PRE at the join point.3098bool GVNPass::performPRE(Function &F) {3099 bool Changed = false;3100 for (BasicBlock *CurrentBlock : depth_first(&F.getEntryBlock())) {3101 // Nothing to PRE in the entry block.3102 if (CurrentBlock == &F.getEntryBlock())3103 continue;3104 3105 // Don't perform PRE on an EH pad.3106 if (CurrentBlock->isEHPad())3107 continue;3108 3109 for (BasicBlock::iterator BI = CurrentBlock->begin(),3110 BE = CurrentBlock->end();3111 BI != BE;) {3112 Instruction *CurInst = &*BI++;3113 Changed |= performScalarPRE(CurInst);3114 }3115 }3116 3117 if (splitCriticalEdges())3118 Changed = true;3119 3120 return Changed;3121}3122 3123/// Split the critical edge connecting the given two blocks, and return3124/// the block inserted to the critical edge.3125BasicBlock *GVNPass::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {3126 // GVN does not require loop-simplify, do not try to preserve it if it is not3127 // possible.3128 BasicBlock *BB = SplitCriticalEdge(3129 Pred, Succ,3130 CriticalEdgeSplittingOptions(DT, LI, MSSAU).unsetPreserveLoopSimplify());3131 if (BB) {3132 if (MD)3133 MD->invalidateCachedPredecessors();3134 InvalidBlockRPONumbers = true;3135 }3136 return BB;3137}3138 3139/// Split critical edges found during the previous3140/// iteration that may enable further optimization.3141bool GVNPass::splitCriticalEdges() {3142 if (ToSplit.empty())3143 return false;3144 3145 bool Changed = false;3146 do {3147 std::pair<Instruction *, unsigned> Edge = ToSplit.pop_back_val();3148 Changed |= SplitCriticalEdge(Edge.first, Edge.second,3149 CriticalEdgeSplittingOptions(DT, LI, MSSAU)) !=3150 nullptr;3151 } while (!ToSplit.empty());3152 if (Changed) {3153 if (MD)3154 MD->invalidateCachedPredecessors();3155 InvalidBlockRPONumbers = true;3156 }3157 return Changed;3158}3159 3160/// Executes one iteration of GVN.3161bool GVNPass::iterateOnFunction(Function &F) {3162 cleanupGlobalSets();3163 3164 // Top-down walk of the dominator tree.3165 bool Changed = false;3166 // Needed for value numbering with phi construction to work.3167 // RPOT walks the graph in its constructor and will not be invalidated during3168 // processBlock.3169 ReversePostOrderTraversal<Function *> RPOT(&F);3170 3171 for (BasicBlock *BB : RPOT)3172 Changed |= processBlock(BB);3173 3174 return Changed;3175}3176 3177void GVNPass::cleanupGlobalSets() {3178 VN.clear();3179 LeaderTable.clear();3180 BlockRPONumber.clear();3181 ICF->clear();3182 InvalidBlockRPONumbers = true;3183}3184 3185void GVNPass::removeInstruction(Instruction *I) {3186 VN.erase(I);3187 if (MD) MD->removeInstruction(I);3188 if (MSSAU)3189 MSSAU->removeMemoryAccess(I);3190#ifndef NDEBUG3191 verifyRemoved(I);3192#endif3193 ICF->removeInstruction(I);3194 I->eraseFromParent();3195}3196 3197/// Verify that the specified instruction does not occur in our3198/// internal data structures.3199void GVNPass::verifyRemoved(const Instruction *Inst) const {3200 VN.verifyRemoved(Inst);3201 LeaderTable.verifyRemoved(Inst);3202}3203 3204/// BB is declared dead, which implied other blocks become dead as well. This3205/// function is to add all these blocks to "DeadBlocks". For the dead blocks'3206/// live successors, update their phi nodes by replacing the operands3207/// corresponding to dead blocks with UndefVal.3208void GVNPass::addDeadBlock(BasicBlock *BB) {3209 SmallVector<BasicBlock *, 4> NewDead;3210 SmallSetVector<BasicBlock *, 4> DF;3211 3212 NewDead.push_back(BB);3213 while (!NewDead.empty()) {3214 BasicBlock *D = NewDead.pop_back_val();3215 if (DeadBlocks.count(D))3216 continue;3217 3218 // All blocks dominated by D are dead.3219 SmallVector<BasicBlock *, 8> Dom;3220 DT->getDescendants(D, Dom);3221 DeadBlocks.insert_range(Dom);3222 3223 // Figure out the dominance-frontier(D).3224 for (BasicBlock *B : Dom) {3225 for (BasicBlock *S : successors(B)) {3226 if (DeadBlocks.count(S))3227 continue;3228 3229 bool AllPredDead = true;3230 for (BasicBlock *P : predecessors(S))3231 if (!DeadBlocks.count(P)) {3232 AllPredDead = false;3233 break;3234 }3235 3236 if (!AllPredDead) {3237 // S could be proved dead later on. That is why we don't update phi3238 // operands at this moment.3239 DF.insert(S);3240 } else {3241 // While S is not dominated by D, it is dead by now. This could take3242 // place if S already have a dead predecessor before D is declared3243 // dead.3244 NewDead.push_back(S);3245 }3246 }3247 }3248 }3249 3250 // For the dead blocks' live successors, update their phi nodes by replacing3251 // the operands corresponding to dead blocks with UndefVal.3252 for (BasicBlock *B : DF) {3253 if (DeadBlocks.count(B))3254 continue;3255 3256 // First, split the critical edges. This might also create additional blocks3257 // to preserve LoopSimplify form and adjust edges accordingly.3258 SmallVector<BasicBlock *, 4> Preds(predecessors(B));3259 for (BasicBlock *P : Preds) {3260 if (!DeadBlocks.count(P))3261 continue;3262 3263 if (is_contained(successors(P), B) &&3264 isCriticalEdge(P->getTerminator(), B)) {3265 if (BasicBlock *S = splitCriticalEdges(P, B))3266 DeadBlocks.insert(P = S);3267 }3268 }3269 3270 // Now poison the incoming values from the dead predecessors.3271 for (BasicBlock *P : predecessors(B)) {3272 if (!DeadBlocks.count(P))3273 continue;3274 for (PHINode &Phi : B->phis()) {3275 Phi.setIncomingValueForBlock(P, PoisonValue::get(Phi.getType()));3276 if (MD)3277 MD->invalidateCachedPointerInfo(&Phi);3278 }3279 }3280 }3281}3282 3283// If the given branch is recognized as a foldable branch (i.e. conditional3284// branch with constant condition), it will perform following analyses and3285// transformation.3286// 1) If the dead out-coming edge is a critical-edge, split it. Let3287// R be the target of the dead out-coming edge.3288// 1) Identify the set of dead blocks implied by the branch's dead outcoming3289// edge. The result of this step will be {X| X is dominated by R}3290// 2) Identify those blocks which haves at least one dead predecessor. The3291// result of this step will be dominance-frontier(R).3292// 3) Update the PHIs in DF(R) by replacing the operands corresponding to3293// dead blocks with "UndefVal" in an hope these PHIs will optimized away.3294//3295// Return true iff *NEW* dead code are found.3296bool GVNPass::processFoldableCondBr(BranchInst *BI) {3297 if (!BI || BI->isUnconditional())3298 return false;3299 3300 // If a branch has two identical successors, we cannot declare either dead.3301 if (BI->getSuccessor(0) == BI->getSuccessor(1))3302 return false;3303 3304 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());3305 if (!Cond)3306 return false;3307 3308 BasicBlock *DeadRoot =3309 Cond->getZExtValue() ? BI->getSuccessor(1) : BI->getSuccessor(0);3310 if (DeadBlocks.count(DeadRoot))3311 return false;3312 3313 if (!DeadRoot->getSinglePredecessor())3314 DeadRoot = splitCriticalEdges(BI->getParent(), DeadRoot);3315 3316 addDeadBlock(DeadRoot);3317 return true;3318}3319 3320// performPRE() will trigger assert if it comes across an instruction without3321// associated val-num. As it normally has far more live instructions than dead3322// instructions, it makes more sense just to "fabricate" a val-number for the3323// dead code than checking if instruction involved is dead or not.3324void GVNPass::assignValNumForDeadCode() {3325 for (BasicBlock *BB : DeadBlocks) {3326 for (Instruction &Inst : *BB) {3327 unsigned ValNum = VN.lookupOrAdd(&Inst);3328 LeaderTable.insert(ValNum, &Inst, BB);3329 }3330 }3331}3332 3333class llvm::gvn::GVNLegacyPass : public FunctionPass {3334public:3335 static char ID; // Pass identification, replacement for typeid.3336 3337 explicit GVNLegacyPass(bool MemDepAnalysis = GVNEnableMemDep,3338 bool MemSSAAnalysis = GVNEnableMemorySSA)3339 : FunctionPass(ID), Impl(GVNOptions()3340 .setMemDep(MemDepAnalysis)3341 .setMemorySSA(MemSSAAnalysis)) {3342 initializeGVNLegacyPassPass(*PassRegistry::getPassRegistry());3343 }3344 3345 bool runOnFunction(Function &F) override {3346 if (skipFunction(F))3347 return false;3348 3349 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();3350 if (Impl.isMemorySSAEnabled() && !MSSAWP)3351 MSSAWP = &getAnalysis<MemorySSAWrapperPass>();3352 3353 return Impl.runImpl(3354 F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),3355 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),3356 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),3357 getAnalysis<AAResultsWrapperPass>().getAAResults(),3358 Impl.isMemDepEnabled()3359 ? &getAnalysis<MemoryDependenceWrapperPass>().getMemDep()3360 : nullptr,3361 getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),3362 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(),3363 MSSAWP ? &MSSAWP->getMSSA() : nullptr);3364 }3365 3366 void getAnalysisUsage(AnalysisUsage &AU) const override {3367 AU.addRequired<AssumptionCacheTracker>();3368 AU.addRequired<DominatorTreeWrapperPass>();3369 AU.addRequired<TargetLibraryInfoWrapperPass>();3370 AU.addRequired<LoopInfoWrapperPass>();3371 if (Impl.isMemDepEnabled())3372 AU.addRequired<MemoryDependenceWrapperPass>();3373 AU.addRequired<AAResultsWrapperPass>();3374 AU.addPreserved<DominatorTreeWrapperPass>();3375 AU.addPreserved<GlobalsAAWrapperPass>();3376 AU.addPreserved<TargetLibraryInfoWrapperPass>();3377 AU.addPreserved<LoopInfoWrapperPass>();3378 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();3379 AU.addPreserved<MemorySSAWrapperPass>();3380 if (Impl.isMemorySSAEnabled())3381 AU.addRequired<MemorySSAWrapperPass>();3382 }3383 3384private:3385 GVNPass Impl;3386};3387 3388char GVNLegacyPass::ID = 0;3389 3390INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)3391INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)3392INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)3393INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)3394INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)3395INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)3396INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)3397INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)3398INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)3399INITIALIZE_PASS_END(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)3400 3401// The public interface to this file...3402FunctionPass *llvm::createGVNPass() { return new GVNLegacyPass(); }3403