1951 lines · cpp
1//===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This pass performs a simple dominator tree walk that eliminates trivially10// redundant instructions.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/Transforms/Scalar/EarlyCSE.h"15#include "llvm/ADT/DenseMapInfo.h"16#include "llvm/ADT/Hashing.h"17#include "llvm/ADT/STLExtras.h"18#include "llvm/ADT/ScopedHashTable.h"19#include "llvm/ADT/SmallVector.h"20#include "llvm/ADT/Statistic.h"21#include "llvm/Analysis/AssumptionCache.h"22#include "llvm/Analysis/GlobalsModRef.h"23#include "llvm/Analysis/GuardUtils.h"24#include "llvm/Analysis/InstructionSimplify.h"25#include "llvm/Analysis/MemorySSA.h"26#include "llvm/Analysis/MemorySSAUpdater.h"27#include "llvm/Analysis/TargetLibraryInfo.h"28#include "llvm/Analysis/TargetTransformInfo.h"29#include "llvm/Analysis/ValueTracking.h"30#include "llvm/IR/BasicBlock.h"31#include "llvm/IR/Constants.h"32#include "llvm/IR/Dominators.h"33#include "llvm/IR/Function.h"34#include "llvm/IR/InstrTypes.h"35#include "llvm/IR/Instruction.h"36#include "llvm/IR/Instructions.h"37#include "llvm/IR/IntrinsicInst.h"38#include "llvm/IR/LLVMContext.h"39#include "llvm/IR/PassManager.h"40#include "llvm/IR/PatternMatch.h"41#include "llvm/IR/Type.h"42#include "llvm/IR/Value.h"43#include "llvm/InitializePasses.h"44#include "llvm/Pass.h"45#include "llvm/Support/Allocator.h"46#include "llvm/Support/AtomicOrdering.h"47#include "llvm/Support/Casting.h"48#include "llvm/Support/Debug.h"49#include "llvm/Support/DebugCounter.h"50#include "llvm/Support/RecyclingAllocator.h"51#include "llvm/Support/raw_ostream.h"52#include "llvm/Transforms/Scalar.h"53#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"54#include "llvm/Transforms/Utils/Local.h"55#include <cassert>56#include <deque>57#include <memory>58#include <utility>59 60using namespace llvm;61using namespace llvm::PatternMatch;62 63#define DEBUG_TYPE "early-cse"64 65STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");66STATISTIC(NumCSE, "Number of instructions CSE'd");67STATISTIC(NumCSECVP, "Number of compare instructions CVP'd");68STATISTIC(NumCSELoad, "Number of load instructions CSE'd");69STATISTIC(NumCSECall, "Number of call instructions CSE'd");70STATISTIC(NumCSEGEP, "Number of GEP instructions CSE'd");71STATISTIC(NumDSE, "Number of trivial dead stores removed");72 73DEBUG_COUNTER(CSECounter, "early-cse",74 "Controls which instructions are removed");75 76static cl::opt<unsigned> EarlyCSEMssaOptCap(77 "earlycse-mssa-optimization-cap", cl::init(500), cl::Hidden,78 cl::desc("Enable imprecision in EarlyCSE in pathological cases, in exchange "79 "for faster compile. Caps the MemorySSA clobbering calls."));80 81static cl::opt<bool> EarlyCSEDebugHash(82 "earlycse-debug-hash", cl::init(false), cl::Hidden,83 cl::desc("Perform extra assertion checking to verify that SimpleValue's hash "84 "function is well-behaved w.r.t. its isEqual predicate"));85 86//===----------------------------------------------------------------------===//87// SimpleValue88//===----------------------------------------------------------------------===//89 90namespace {91 92/// Struct representing the available values in the scoped hash table.93struct SimpleValue {94 Instruction *Inst;95 96 SimpleValue(Instruction *I) : Inst(I) {97 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");98 }99 100 bool isSentinel() const {101 return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||102 Inst == DenseMapInfo<Instruction *>::getTombstoneKey();103 }104 105 static bool canHandle(Instruction *Inst) {106 // This can only handle non-void readnone functions.107 // Also handled are constrained intrinsic that look like the types108 // of instruction handled below (UnaryOperator, etc.).109 if (CallInst *CI = dyn_cast<CallInst>(Inst)) {110 if (Function *F = CI->getCalledFunction()) {111 switch (F->getIntrinsicID()) {112 case Intrinsic::experimental_constrained_fadd:113 case Intrinsic::experimental_constrained_fsub:114 case Intrinsic::experimental_constrained_fmul:115 case Intrinsic::experimental_constrained_fdiv:116 case Intrinsic::experimental_constrained_frem:117 case Intrinsic::experimental_constrained_fptosi:118 case Intrinsic::experimental_constrained_sitofp:119 case Intrinsic::experimental_constrained_fptoui:120 case Intrinsic::experimental_constrained_uitofp:121 case Intrinsic::experimental_constrained_fcmp:122 case Intrinsic::experimental_constrained_fcmps: {123 auto *CFP = cast<ConstrainedFPIntrinsic>(CI);124 if (CFP->getExceptionBehavior() &&125 CFP->getExceptionBehavior() == fp::ebStrict)126 return false;127 // Since we CSE across function calls we must not allow128 // the rounding mode to change.129 if (CFP->getRoundingMode() &&130 CFP->getRoundingMode() == RoundingMode::Dynamic)131 return false;132 return true;133 }134 }135 }136 return CI->doesNotAccessMemory() &&137 // FIXME: Currently the calls which may access the thread id may138 // be considered as not accessing the memory. But this is139 // problematic for coroutines, since coroutines may resume in a140 // different thread. So we disable the optimization here for the141 // correctness. However, it may block many other correct142 // optimizations. Revert this one when we detect the memory143 // accessing kind more precisely.144 !CI->getFunction()->isPresplitCoroutine();145 }146 return isa<CastInst>(Inst) || isa<UnaryOperator>(Inst) ||147 isa<BinaryOperator>(Inst) || isa<CmpInst>(Inst) ||148 isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||149 isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||150 isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst) ||151 isa<FreezeInst>(Inst);152 }153};154 155} // end anonymous namespace156 157template <> struct llvm::DenseMapInfo<SimpleValue> {158 static inline SimpleValue getEmptyKey() {159 return DenseMapInfo<Instruction *>::getEmptyKey();160 }161 162 static inline SimpleValue getTombstoneKey() {163 return DenseMapInfo<Instruction *>::getTombstoneKey();164 }165 166 static unsigned getHashValue(SimpleValue Val);167 static bool isEqual(SimpleValue LHS, SimpleValue RHS);168};169 170/// Match a 'select' including an optional 'not's of the condition.171static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond, Value *&A,172 Value *&B,173 SelectPatternFlavor &Flavor) {174 // Return false if V is not even a select.175 if (!match(V, m_Select(m_Value(Cond), m_Value(A), m_Value(B))))176 return false;177 178 // Look through a 'not' of the condition operand by swapping A/B.179 Value *CondNot;180 if (match(Cond, m_Not(m_Value(CondNot)))) {181 Cond = CondNot;182 std::swap(A, B);183 }184 185 // Match canonical forms of min/max. We are not using ValueTracking's186 // more powerful matchSelectPattern() because it may rely on instruction flags187 // such as "nsw". That would be incompatible with the current hashing188 // mechanism that may remove flags to increase the likelihood of CSE.189 190 Flavor = SPF_UNKNOWN;191 CmpPredicate Pred;192 193 if (!match(Cond, m_ICmp(Pred, m_Specific(A), m_Specific(B)))) {194 // Check for commuted variants of min/max by swapping predicate.195 // If we do not match the standard or commuted patterns, this is not a196 // recognized form of min/max, but it is still a select, so return true.197 if (!match(Cond, m_ICmp(Pred, m_Specific(B), m_Specific(A))))198 return true;199 Pred = ICmpInst::getSwappedPredicate(Pred);200 }201 202 switch (Pred) {203 case CmpInst::ICMP_UGT: Flavor = SPF_UMAX; break;204 case CmpInst::ICMP_ULT: Flavor = SPF_UMIN; break;205 case CmpInst::ICMP_SGT: Flavor = SPF_SMAX; break;206 case CmpInst::ICMP_SLT: Flavor = SPF_SMIN; break;207 // Non-strict inequalities.208 case CmpInst::ICMP_ULE: Flavor = SPF_UMIN; break;209 case CmpInst::ICMP_UGE: Flavor = SPF_UMAX; break;210 case CmpInst::ICMP_SLE: Flavor = SPF_SMIN; break;211 case CmpInst::ICMP_SGE: Flavor = SPF_SMAX; break;212 default: break;213 }214 215 return true;216}217 218static unsigned hashCallInst(CallInst *CI) {219 // Don't CSE convergent calls in different basic blocks, because they220 // implicitly depend on the set of threads that is currently executing.221 if (CI->isConvergent()) {222 return hash_combine(CI->getOpcode(), CI->getParent(),223 hash_combine_range(CI->operand_values()));224 }225 return hash_combine(CI->getOpcode(),226 hash_combine_range(CI->operand_values()));227}228 229static unsigned getHashValueImpl(SimpleValue Val) {230 Instruction *Inst = Val.Inst;231 // Hash in all of the operands as pointers.232 if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {233 Value *LHS = BinOp->getOperand(0);234 Value *RHS = BinOp->getOperand(1);235 if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))236 std::swap(LHS, RHS);237 238 return hash_combine(BinOp->getOpcode(), LHS, RHS);239 }240 241 if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {242 // Compares can be commuted by swapping the comparands and243 // updating the predicate. Choose the form that has the244 // comparands in sorted order, or in the case of a tie, the245 // one with the lower predicate.246 Value *LHS = CI->getOperand(0);247 Value *RHS = CI->getOperand(1);248 CmpInst::Predicate Pred = CI->getPredicate();249 CmpInst::Predicate SwappedPred = CI->getSwappedPredicate();250 if (std::tie(LHS, Pred) > std::tie(RHS, SwappedPred)) {251 std::swap(LHS, RHS);252 Pred = SwappedPred;253 }254 return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);255 }256 257 // Hash general selects to allow matching commuted true/false operands.258 SelectPatternFlavor SPF;259 Value *Cond, *A, *B;260 if (matchSelectWithOptionalNotCond(Inst, Cond, A, B, SPF)) {261 // Hash min/max (cmp + select) to allow for commuted operands.262 // Min/max may also have non-canonical compare predicate (eg, the compare for263 // smin may use 'sgt' rather than 'slt'), and non-canonical operands in the264 // compare.265 // TODO: We should also detect FP min/max.266 if (SPF == SPF_SMIN || SPF == SPF_SMAX ||267 SPF == SPF_UMIN || SPF == SPF_UMAX) {268 if (A > B)269 std::swap(A, B);270 return hash_combine(Inst->getOpcode(), SPF, A, B);271 }272 273 // Hash general selects to allow matching commuted true/false operands.274 275 // If we do not have a compare as the condition, just hash in the condition.276 CmpPredicate Pred;277 Value *X, *Y;278 if (!match(Cond, m_Cmp(Pred, m_Value(X), m_Value(Y))))279 return hash_combine(Inst->getOpcode(), Cond, A, B);280 281 // Similar to cmp normalization (above) - canonicalize the predicate value:282 // select (icmp Pred, X, Y), A, B --> select (icmp InvPred, X, Y), B, A283 if (CmpInst::getInversePredicate(Pred) < Pred) {284 Pred = CmpInst::getInversePredicate(Pred);285 std::swap(A, B);286 }287 return hash_combine(Inst->getOpcode(),288 static_cast<CmpInst::Predicate>(Pred), X, Y, A, B);289 }290 291 if (CastInst *CI = dyn_cast<CastInst>(Inst))292 return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));293 294 if (FreezeInst *FI = dyn_cast<FreezeInst>(Inst))295 return hash_combine(FI->getOpcode(), FI->getOperand(0));296 297 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))298 return hash_combine(EVI->getOpcode(), EVI->getOperand(0),299 hash_combine_range(EVI->indices()));300 301 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))302 return hash_combine(IVI->getOpcode(), IVI->getOperand(0),303 IVI->getOperand(1), hash_combine_range(IVI->indices()));304 305 assert((isa<CallInst>(Inst) || isa<ExtractElementInst>(Inst) ||306 isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||307 isa<UnaryOperator>(Inst) || isa<FreezeInst>(Inst)) &&308 "Invalid/unknown instruction");309 310 // Handle intrinsics with commutative operands.311 auto *II = dyn_cast<IntrinsicInst>(Inst);312 if (II && II->isCommutative() && II->arg_size() >= 2) {313 Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1);314 if (LHS > RHS)315 std::swap(LHS, RHS);316 return hash_combine(317 II->getOpcode(), LHS, RHS,318 hash_combine_range(drop_begin(II->operand_values(), 2)));319 }320 321 // gc.relocate is 'special' call: its second and third operands are322 // not real values, but indices into statepoint's argument list.323 // Get values they point to.324 if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(Inst))325 return hash_combine(GCR->getOpcode(), GCR->getOperand(0),326 GCR->getBasePtr(), GCR->getDerivedPtr());327 328 // Don't CSE convergent calls in different basic blocks, because they329 // implicitly depend on the set of threads that is currently executing.330 if (CallInst *CI = dyn_cast<CallInst>(Inst))331 return hashCallInst(CI);332 333 // Mix in the opcode.334 return hash_combine(Inst->getOpcode(),335 hash_combine_range(Inst->operand_values()));336}337 338unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {339#ifndef NDEBUG340 // If -earlycse-debug-hash was specified, return a constant -- this341 // will force all hashing to collide, so we'll exhaustively search342 // the table for a match, and the assertion in isEqual will fire if343 // there's a bug causing equal keys to hash differently.344 if (EarlyCSEDebugHash)345 return 0;346#endif347 return getHashValueImpl(Val);348}349 350static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS) {351 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;352 353 if (LHS.isSentinel() || RHS.isSentinel())354 return LHSI == RHSI;355 356 if (LHSI->getOpcode() != RHSI->getOpcode())357 return false;358 if (LHSI->isIdenticalToWhenDefined(RHSI, /*IntersectAttrs=*/true)) {359 // Convergent calls implicitly depend on the set of threads that is360 // currently executing, so conservatively return false if they are in361 // different basic blocks.362 if (CallInst *CI = dyn_cast<CallInst>(LHSI);363 CI && CI->isConvergent() && LHSI->getParent() != RHSI->getParent())364 return false;365 366 return true;367 }368 369 // If we're not strictly identical, we still might be a commutable instruction370 if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {371 if (!LHSBinOp->isCommutative())372 return false;373 374 assert(isa<BinaryOperator>(RHSI) &&375 "same opcode, but different instruction type?");376 BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);377 378 // Commuted equality379 return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&380 LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);381 }382 if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {383 assert(isa<CmpInst>(RHSI) &&384 "same opcode, but different instruction type?");385 CmpInst *RHSCmp = cast<CmpInst>(RHSI);386 // Commuted equality387 return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&388 LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&389 LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();390 }391 392 auto *LII = dyn_cast<IntrinsicInst>(LHSI);393 auto *RII = dyn_cast<IntrinsicInst>(RHSI);394 if (LII && RII && LII->getIntrinsicID() == RII->getIntrinsicID() &&395 LII->isCommutative() && LII->arg_size() >= 2) {396 return LII->getArgOperand(0) == RII->getArgOperand(1) &&397 LII->getArgOperand(1) == RII->getArgOperand(0) &&398 std::equal(LII->arg_begin() + 2, LII->arg_end(),399 RII->arg_begin() + 2, RII->arg_end()) &&400 LII->hasSameSpecialState(RII, /*IgnoreAlignment=*/false,401 /*IntersectAttrs=*/true);402 }403 404 // See comment above in `getHashValue()`.405 if (const GCRelocateInst *GCR1 = dyn_cast<GCRelocateInst>(LHSI))406 if (const GCRelocateInst *GCR2 = dyn_cast<GCRelocateInst>(RHSI))407 return GCR1->getOperand(0) == GCR2->getOperand(0) &&408 GCR1->getBasePtr() == GCR2->getBasePtr() &&409 GCR1->getDerivedPtr() == GCR2->getDerivedPtr();410 411 // Min/max can occur with commuted operands, non-canonical predicates,412 // and/or non-canonical operands.413 // Selects can be non-trivially equivalent via inverted conditions and swaps.414 SelectPatternFlavor LSPF, RSPF;415 Value *CondL, *CondR, *LHSA, *RHSA, *LHSB, *RHSB;416 if (matchSelectWithOptionalNotCond(LHSI, CondL, LHSA, LHSB, LSPF) &&417 matchSelectWithOptionalNotCond(RHSI, CondR, RHSA, RHSB, RSPF)) {418 if (LSPF == RSPF) {419 // TODO: We should also detect FP min/max.420 if (LSPF == SPF_SMIN || LSPF == SPF_SMAX ||421 LSPF == SPF_UMIN || LSPF == SPF_UMAX)422 return ((LHSA == RHSA && LHSB == RHSB) ||423 (LHSA == RHSB && LHSB == RHSA));424 425 // select Cond, A, B <--> select not(Cond), B, A426 if (CondL == CondR && LHSA == RHSA && LHSB == RHSB)427 return true;428 }429 430 // If the true/false operands are swapped and the conditions are compares431 // with inverted predicates, the selects are equal:432 // select (icmp Pred, X, Y), A, B <--> select (icmp InvPred, X, Y), B, A433 //434 // This also handles patterns with a double-negation in the sense of not +435 // inverse, because we looked through a 'not' in the matching function and436 // swapped A/B:437 // select (cmp Pred, X, Y), A, B <--> select (not (cmp InvPred, X, Y)), B, A438 //439 // This intentionally does NOT handle patterns with a double-negation in440 // the sense of not + not, because doing so could result in values441 // comparing442 // as equal that hash differently in the min/max cases like:443 // select (cmp slt, X, Y), X, Y <--> select (not (not (cmp slt, X, Y))), X, Y444 // ^ hashes as min ^ would not hash as min445 // In the context of the EarlyCSE pass, however, such cases never reach446 // this code, as we simplify the double-negation before hashing the second447 // select (and so still succeed at CSEing them).448 if (LHSA == RHSB && LHSB == RHSA) {449 CmpPredicate PredL, PredR;450 Value *X, *Y;451 if (match(CondL, m_Cmp(PredL, m_Value(X), m_Value(Y))) &&452 match(CondR, m_Cmp(PredR, m_Specific(X), m_Specific(Y))) &&453 CmpInst::getInversePredicate(PredL) == PredR)454 return true;455 }456 }457 458 return false;459}460 461bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {462 // These comparisons are nontrivial, so assert that equality implies463 // hash equality (DenseMap demands this as an invariant).464 bool Result = isEqualImpl(LHS, RHS);465 assert(!Result || (LHS.isSentinel() && LHS.Inst == RHS.Inst) ||466 getHashValueImpl(LHS) == getHashValueImpl(RHS));467 return Result;468}469 470//===----------------------------------------------------------------------===//471// CallValue472//===----------------------------------------------------------------------===//473 474namespace {475 476/// Struct representing the available call values in the scoped hash477/// table.478struct CallValue {479 Instruction *Inst;480 481 CallValue(Instruction *I) : Inst(I) {482 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");483 }484 485 bool isSentinel() const {486 return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||487 Inst == DenseMapInfo<Instruction *>::getTombstoneKey();488 }489 490 static bool canHandle(Instruction *Inst) {491 CallInst *CI = dyn_cast<CallInst>(Inst);492 if (!CI || (!CI->onlyReadsMemory() && !CI->onlyWritesMemory()) ||493 // FIXME: Currently the calls which may access the thread id may494 // be considered as not accessing the memory. But this is495 // problematic for coroutines, since coroutines may resume in a496 // different thread. So we disable the optimization here for the497 // correctness. However, it may block many other correct498 // optimizations. Revert this one when we detect the memory499 // accessing kind more precisely.500 CI->getFunction()->isPresplitCoroutine())501 return false;502 return true;503 }504};505 506} // end anonymous namespace507 508template <> struct llvm::DenseMapInfo<CallValue> {509 static inline CallValue getEmptyKey() {510 return DenseMapInfo<Instruction *>::getEmptyKey();511 }512 513 static inline CallValue getTombstoneKey() {514 return DenseMapInfo<Instruction *>::getTombstoneKey();515 }516 517 static unsigned getHashValue(CallValue Val);518 static bool isEqual(CallValue LHS, CallValue RHS);519};520 521unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {522 Instruction *Inst = Val.Inst;523 524 // Hash all of the operands as pointers and mix in the opcode.525 return hashCallInst(cast<CallInst>(Inst));526}527 528bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {529 if (LHS.isSentinel() || RHS.isSentinel())530 return LHS.Inst == RHS.Inst;531 532 CallInst *LHSI = cast<CallInst>(LHS.Inst);533 CallInst *RHSI = cast<CallInst>(RHS.Inst);534 535 // Convergent calls implicitly depend on the set of threads that is536 // currently executing, so conservatively return false if they are in537 // different basic blocks.538 if (LHSI->isConvergent() && LHSI->getParent() != RHSI->getParent())539 return false;540 541 return LHSI->isIdenticalToWhenDefined(RHSI, /*IntersectAttrs=*/true);542}543 544//===----------------------------------------------------------------------===//545// GEPValue546//===----------------------------------------------------------------------===//547 548namespace {549 550struct GEPValue {551 Instruction *Inst;552 std::optional<int64_t> ConstantOffset;553 554 GEPValue(Instruction *I) : Inst(I) {555 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");556 }557 558 GEPValue(Instruction *I, std::optional<int64_t> ConstantOffset)559 : Inst(I), ConstantOffset(ConstantOffset) {560 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");561 }562 563 bool isSentinel() const {564 return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||565 Inst == DenseMapInfo<Instruction *>::getTombstoneKey();566 }567 568 static bool canHandle(Instruction *Inst) {569 return isa<GetElementPtrInst>(Inst);570 }571};572 573} // namespace574 575template <> struct llvm::DenseMapInfo<GEPValue> {576 static inline GEPValue getEmptyKey() {577 return DenseMapInfo<Instruction *>::getEmptyKey();578 }579 580 static inline GEPValue getTombstoneKey() {581 return DenseMapInfo<Instruction *>::getTombstoneKey();582 }583 584 static unsigned getHashValue(const GEPValue &Val);585 static bool isEqual(const GEPValue &LHS, const GEPValue &RHS);586};587 588unsigned DenseMapInfo<GEPValue>::getHashValue(const GEPValue &Val) {589 auto *GEP = cast<GetElementPtrInst>(Val.Inst);590 if (Val.ConstantOffset.has_value())591 return hash_combine(GEP->getOpcode(), GEP->getPointerOperand(),592 Val.ConstantOffset.value());593 return hash_combine(GEP->getOpcode(),594 hash_combine_range(GEP->operand_values()));595}596 597bool DenseMapInfo<GEPValue>::isEqual(const GEPValue &LHS, const GEPValue &RHS) {598 if (LHS.isSentinel() || RHS.isSentinel())599 return LHS.Inst == RHS.Inst;600 auto *LGEP = cast<GetElementPtrInst>(LHS.Inst);601 auto *RGEP = cast<GetElementPtrInst>(RHS.Inst);602 if (LGEP->getPointerOperand() != RGEP->getPointerOperand())603 return false;604 if (LHS.ConstantOffset.has_value() && RHS.ConstantOffset.has_value())605 return LHS.ConstantOffset.value() == RHS.ConstantOffset.value();606 return LGEP->isIdenticalToWhenDefined(RGEP);607}608 609//===----------------------------------------------------------------------===//610// EarlyCSE implementation611//===----------------------------------------------------------------------===//612 613namespace {614 615/// A simple and fast domtree-based CSE pass.616///617/// This pass does a simple depth-first walk over the dominator tree,618/// eliminating trivially redundant instructions and using instsimplify to619/// canonicalize things as it goes. It is intended to be fast and catch obvious620/// cases so that instcombine and other passes are more effective. It is621/// expected that a later pass of GVN will catch the interesting/hard cases.622class EarlyCSE {623public:624 const TargetLibraryInfo &TLI;625 const TargetTransformInfo &TTI;626 DominatorTree &DT;627 AssumptionCache &AC;628 const SimplifyQuery SQ;629 MemorySSA *MSSA;630 std::unique_ptr<MemorySSAUpdater> MSSAUpdater;631 632 using AllocatorTy =633 RecyclingAllocator<BumpPtrAllocator,634 ScopedHashTableVal<SimpleValue, Value *>>;635 using ScopedHTType =636 ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,637 AllocatorTy>;638 639 /// A scoped hash table of the current values of all of our simple640 /// scalar expressions.641 ///642 /// As we walk down the domtree, we look to see if instructions are in this:643 /// if so, we replace them with what we find, otherwise we insert them so644 /// that dominated values can succeed in their lookup.645 ScopedHTType AvailableValues;646 647 /// A scoped hash table of the current values of previously encountered648 /// memory locations.649 ///650 /// This allows us to get efficient access to dominating loads or stores when651 /// we have a fully redundant load. In addition to the most recent load, we652 /// keep track of a generation count of the read, which is compared against653 /// the current generation count. The current generation count is incremented654 /// after every possibly writing memory operation, which ensures that we only655 /// CSE loads with other loads that have no intervening store. Ordering656 /// events (such as fences or atomic instructions) increment the generation657 /// count as well; essentially, we model these as writes to all possible658 /// locations. Note that atomic and/or volatile loads and stores can be659 /// present the table; it is the responsibility of the consumer to inspect660 /// the atomicity/volatility if needed.661 struct LoadValue {662 Instruction *DefInst = nullptr;663 unsigned Generation = 0;664 int MatchingId = -1;665 bool IsAtomic = false;666 bool IsLoad = false;667 668 LoadValue() = default;669 LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,670 bool IsAtomic, bool IsLoad)671 : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),672 IsAtomic(IsAtomic), IsLoad(IsLoad) {}673 };674 675 using LoadMapAllocator =676 RecyclingAllocator<BumpPtrAllocator,677 ScopedHashTableVal<Value *, LoadValue>>;678 using LoadHTType =679 ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,680 LoadMapAllocator>;681 682 LoadHTType AvailableLoads;683 684 // A scoped hash table mapping memory locations (represented as typed685 // addresses) to generation numbers at which that memory location became686 // (henceforth indefinitely) invariant.687 using InvariantMapAllocator =688 RecyclingAllocator<BumpPtrAllocator,689 ScopedHashTableVal<MemoryLocation, unsigned>>;690 using InvariantHTType =691 ScopedHashTable<MemoryLocation, unsigned, DenseMapInfo<MemoryLocation>,692 InvariantMapAllocator>;693 InvariantHTType AvailableInvariants;694 695 /// A scoped hash table of the current values of read-only call696 /// values.697 ///698 /// It uses the same generation count as loads.699 using CallHTType =700 ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>;701 CallHTType AvailableCalls;702 703 using GEPMapAllocatorTy =704 RecyclingAllocator<BumpPtrAllocator,705 ScopedHashTableVal<GEPValue, Value *>>;706 using GEPHTType = ScopedHashTable<GEPValue, Value *, DenseMapInfo<GEPValue>,707 GEPMapAllocatorTy>;708 GEPHTType AvailableGEPs;709 710 /// This is the current generation of the memory value.711 unsigned CurrentGeneration = 0;712 713 /// Set up the EarlyCSE runner for a particular function.714 EarlyCSE(const DataLayout &DL, const TargetLibraryInfo &TLI,715 const TargetTransformInfo &TTI, DominatorTree &DT,716 AssumptionCache &AC, MemorySSA *MSSA)717 : TLI(TLI), TTI(TTI), DT(DT), AC(AC), SQ(DL, &TLI, &DT, &AC), MSSA(MSSA),718 MSSAUpdater(std::make_unique<MemorySSAUpdater>(MSSA)) {}719 720 bool run();721 722private:723 unsigned ClobberCounter = 0;724 // Almost a POD, but needs to call the constructors for the scoped hash725 // tables so that a new scope gets pushed on. These are RAII so that the726 // scope gets popped when the NodeScope is destroyed.727 class NodeScope {728 public:729 NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,730 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,731 GEPHTType &AvailableGEPs)732 : Scope(AvailableValues), LoadScope(AvailableLoads),733 InvariantScope(AvailableInvariants), CallScope(AvailableCalls),734 GEPScope(AvailableGEPs) {}735 NodeScope(const NodeScope &) = delete;736 NodeScope &operator=(const NodeScope &) = delete;737 738 private:739 ScopedHTType::ScopeTy Scope;740 LoadHTType::ScopeTy LoadScope;741 InvariantHTType::ScopeTy InvariantScope;742 CallHTType::ScopeTy CallScope;743 GEPHTType::ScopeTy GEPScope;744 };745 746 // Contains all the needed information to create a stack for doing a depth747 // first traversal of the tree. This includes scopes for values, loads, and748 // calls as well as the generation. There is a child iterator so that the749 // children do not need to be store separately.750 class StackNode {751 public:752 StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,753 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,754 GEPHTType &AvailableGEPs, unsigned cg, DomTreeNode *n,755 DomTreeNode::const_iterator child,756 DomTreeNode::const_iterator end)757 : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),758 EndIter(end),759 Scopes(AvailableValues, AvailableLoads, AvailableInvariants,760 AvailableCalls, AvailableGEPs) {}761 StackNode(const StackNode &) = delete;762 StackNode &operator=(const StackNode &) = delete;763 764 // Accessors.765 unsigned currentGeneration() const { return CurrentGeneration; }766 unsigned childGeneration() const { return ChildGeneration; }767 void childGeneration(unsigned generation) { ChildGeneration = generation; }768 DomTreeNode *node() { return Node; }769 DomTreeNode::const_iterator childIter() const { return ChildIter; }770 771 DomTreeNode *nextChild() {772 DomTreeNode *child = *ChildIter;773 ++ChildIter;774 return child;775 }776 777 DomTreeNode::const_iterator end() const { return EndIter; }778 bool isProcessed() const { return Processed; }779 void process() { Processed = true; }780 781 private:782 unsigned CurrentGeneration;783 unsigned ChildGeneration;784 DomTreeNode *Node;785 DomTreeNode::const_iterator ChildIter;786 DomTreeNode::const_iterator EndIter;787 NodeScope Scopes;788 bool Processed = false;789 };790 791 /// Wrapper class to handle memory instructions, including loads,792 /// stores and intrinsic loads and stores defined by the target.793 class ParseMemoryInst {794 public:795 ParseMemoryInst(Instruction *Inst, const TargetTransformInfo &TTI)796 : Inst(Inst) {797 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {798 IntrID = II->getIntrinsicID();799 if (TTI.getTgtMemIntrinsic(II, Info))800 return;801 if (isHandledNonTargetIntrinsic(IntrID)) {802 switch (IntrID) {803 case Intrinsic::masked_load:804 Info.PtrVal = Inst->getOperand(0);805 Info.MatchingId = Intrinsic::masked_load;806 Info.ReadMem = true;807 Info.WriteMem = false;808 Info.IsVolatile = false;809 break;810 case Intrinsic::masked_store:811 Info.PtrVal = Inst->getOperand(1);812 // Use the ID of masked load as the "matching id". This will813 // prevent matching non-masked loads/stores with masked ones814 // (which could be done), but at the moment, the code here815 // does not support matching intrinsics with non-intrinsics,816 // so keep the MatchingIds specific to masked instructions817 // for now (TODO).818 Info.MatchingId = Intrinsic::masked_load;819 Info.ReadMem = false;820 Info.WriteMem = true;821 Info.IsVolatile = false;822 break;823 }824 }825 }826 }827 828 Instruction *get() { return Inst; }829 const Instruction *get() const { return Inst; }830 831 bool isLoad() const {832 if (IntrID != 0)833 return Info.ReadMem;834 return isa<LoadInst>(Inst);835 }836 837 bool isStore() const {838 if (IntrID != 0)839 return Info.WriteMem;840 return isa<StoreInst>(Inst);841 }842 843 bool isAtomic() const {844 if (IntrID != 0)845 return Info.Ordering != AtomicOrdering::NotAtomic;846 return Inst->isAtomic();847 }848 849 bool isUnordered() const {850 if (IntrID != 0)851 return Info.isUnordered();852 853 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {854 return LI->isUnordered();855 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {856 return SI->isUnordered();857 }858 // Conservative answer859 return !Inst->isAtomic();860 }861 862 bool isVolatile() const {863 if (IntrID != 0)864 return Info.IsVolatile;865 866 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {867 return LI->isVolatile();868 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {869 return SI->isVolatile();870 }871 // Conservative answer872 return true;873 }874 875 bool isInvariantLoad() const {876 if (auto *LI = dyn_cast<LoadInst>(Inst))877 return LI->hasMetadata(LLVMContext::MD_invariant_load);878 return false;879 }880 881 bool isValid() const { return getPointerOperand() != nullptr; }882 883 // For regular (non-intrinsic) loads/stores, this is set to -1. For884 // intrinsic loads/stores, the id is retrieved from the corresponding885 // field in the MemIntrinsicInfo structure. That field contains886 // non-negative values only.887 int getMatchingId() const {888 if (IntrID != 0)889 return Info.MatchingId;890 return -1;891 }892 893 Value *getPointerOperand() const {894 if (IntrID != 0)895 return Info.PtrVal;896 return getLoadStorePointerOperand(Inst);897 }898 899 Type *getValueType() const {900 // TODO: handle target-specific intrinsics.901 return Inst->getAccessType();902 }903 904 bool mayReadFromMemory() const {905 if (IntrID != 0)906 return Info.ReadMem;907 return Inst->mayReadFromMemory();908 }909 910 bool mayWriteToMemory() const {911 if (IntrID != 0)912 return Info.WriteMem;913 return Inst->mayWriteToMemory();914 }915 916 private:917 Intrinsic::ID IntrID = 0;918 MemIntrinsicInfo Info;919 Instruction *Inst;920 };921 922 // This function is to prevent accidentally passing a non-target923 // intrinsic ID to TargetTransformInfo.924 static bool isHandledNonTargetIntrinsic(Intrinsic::ID ID) {925 switch (ID) {926 case Intrinsic::masked_load:927 case Intrinsic::masked_store:928 return true;929 }930 return false;931 }932 static bool isHandledNonTargetIntrinsic(const Value *V) {933 if (auto *II = dyn_cast<IntrinsicInst>(V))934 return isHandledNonTargetIntrinsic(II->getIntrinsicID());935 return false;936 }937 938 bool processNode(DomTreeNode *Node);939 940 bool handleBranchCondition(Instruction *CondInst, const BranchInst *BI,941 const BasicBlock *BB, const BasicBlock *Pred);942 943 Value *getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,944 unsigned CurrentGeneration);945 946 bool overridingStores(const ParseMemoryInst &Earlier,947 const ParseMemoryInst &Later);948 949 Value *getOrCreateResult(Instruction *Inst, Type *ExpectedType,950 bool CanCreate) const {951 // TODO: We could insert relevant casts on type mismatch.952 // The load or the store's first operand.953 Value *V;954 if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {955 switch (II->getIntrinsicID()) {956 case Intrinsic::masked_load:957 V = II;958 break;959 case Intrinsic::masked_store:960 V = II->getOperand(0);961 break;962 default:963 return TTI.getOrCreateResultFromMemIntrinsic(II, ExpectedType,964 CanCreate);965 }966 } else {967 V = isa<LoadInst>(Inst) ? Inst : cast<StoreInst>(Inst)->getValueOperand();968 }969 970 return V->getType() == ExpectedType ? V : nullptr;971 }972 973 /// Return true if the instruction is known to only operate on memory974 /// provably invariant in the given "generation".975 bool isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt);976 977 bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,978 Instruction *EarlierInst, Instruction *LaterInst);979 980 bool isNonTargetIntrinsicMatch(const IntrinsicInst *Earlier,981 const IntrinsicInst *Later) {982 auto IsSubmask = [](const Value *Mask0, const Value *Mask1) {983 // Is Mask0 a submask of Mask1?984 if (Mask0 == Mask1)985 return true;986 if (isa<UndefValue>(Mask0) || isa<UndefValue>(Mask1))987 return false;988 auto *Vec0 = dyn_cast<ConstantVector>(Mask0);989 auto *Vec1 = dyn_cast<ConstantVector>(Mask1);990 if (!Vec0 || !Vec1)991 return false;992 if (Vec0->getType() != Vec1->getType())993 return false;994 for (int i = 0, e = Vec0->getNumOperands(); i != e; ++i) {995 Constant *Elem0 = Vec0->getOperand(i);996 Constant *Elem1 = Vec1->getOperand(i);997 auto *Int0 = dyn_cast<ConstantInt>(Elem0);998 if (Int0 && Int0->isZero())999 continue;1000 auto *Int1 = dyn_cast<ConstantInt>(Elem1);1001 if (Int1 && !Int1->isZero())1002 continue;1003 if (isa<UndefValue>(Elem0) || isa<UndefValue>(Elem1))1004 return false;1005 if (Elem0 == Elem1)1006 continue;1007 return false;1008 }1009 return true;1010 };1011 auto PtrOp = [](const IntrinsicInst *II) {1012 if (II->getIntrinsicID() == Intrinsic::masked_load)1013 return II->getOperand(0);1014 if (II->getIntrinsicID() == Intrinsic::masked_store)1015 return II->getOperand(1);1016 llvm_unreachable("Unexpected IntrinsicInst");1017 };1018 auto MaskOp = [](const IntrinsicInst *II) {1019 if (II->getIntrinsicID() == Intrinsic::masked_load)1020 return II->getOperand(1);1021 if (II->getIntrinsicID() == Intrinsic::masked_store)1022 return II->getOperand(2);1023 llvm_unreachable("Unexpected IntrinsicInst");1024 };1025 auto ThruOp = [](const IntrinsicInst *II) {1026 if (II->getIntrinsicID() == Intrinsic::masked_load)1027 return II->getOperand(2);1028 llvm_unreachable("Unexpected IntrinsicInst");1029 };1030 1031 if (PtrOp(Earlier) != PtrOp(Later))1032 return false;1033 1034 Intrinsic::ID IDE = Earlier->getIntrinsicID();1035 Intrinsic::ID IDL = Later->getIntrinsicID();1036 // We could really use specific intrinsic classes for masked loads1037 // and stores in IntrinsicInst.h.1038 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_load) {1039 // Trying to replace later masked load with the earlier one.1040 // Check that the pointers are the same, and1041 // - masks and pass-throughs are the same, or1042 // - replacee's pass-through is "undef" and replacer's mask is a1043 // super-set of the replacee's mask.1044 if (MaskOp(Earlier) == MaskOp(Later) && ThruOp(Earlier) == ThruOp(Later))1045 return true;1046 if (!isa<UndefValue>(ThruOp(Later)))1047 return false;1048 return IsSubmask(MaskOp(Later), MaskOp(Earlier));1049 }1050 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_load) {1051 // Trying to replace a load of a stored value with the store's value.1052 // Check that the pointers are the same, and1053 // - load's mask is a subset of store's mask, and1054 // - load's pass-through is "undef".1055 if (!IsSubmask(MaskOp(Later), MaskOp(Earlier)))1056 return false;1057 return isa<UndefValue>(ThruOp(Later));1058 }1059 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_store) {1060 // Trying to remove a store of the loaded value.1061 // Check that the pointers are the same, and1062 // - store's mask is a subset of the load's mask.1063 return IsSubmask(MaskOp(Later), MaskOp(Earlier));1064 }1065 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_store) {1066 // Trying to remove a dead store (earlier).1067 // Check that the pointers are the same,1068 // - the to-be-removed store's mask is a subset of the other store's1069 // mask.1070 return IsSubmask(MaskOp(Earlier), MaskOp(Later));1071 }1072 return false;1073 }1074 1075 void removeMSSA(Instruction &Inst) {1076 if (!MSSA)1077 return;1078 if (VerifyMemorySSA)1079 MSSA->verifyMemorySSA();1080 // Removing a store here can leave MemorySSA in an unoptimized state by1081 // creating MemoryPhis that have identical arguments and by creating1082 // MemoryUses whose defining access is not an actual clobber. The phi case1083 // is handled by MemorySSA when passing OptimizePhis = true to1084 // removeMemoryAccess. The non-optimized MemoryUse case is lazily updated1085 // by MemorySSA's getClobberingMemoryAccess.1086 MSSAUpdater->removeMemoryAccess(&Inst, true);1087 }1088};1089 1090} // end anonymous namespace1091 1092/// Determine if the memory referenced by LaterInst is from the same heap1093/// version as EarlierInst.1094/// This is currently called in two scenarios:1095///1096/// load p1097/// ...1098/// load p1099///1100/// and1101///1102/// x = load p1103/// ...1104/// store x, p1105///1106/// in both cases we want to verify that there are no possible writes to the1107/// memory referenced by p between the earlier and later instruction.1108bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,1109 unsigned LaterGeneration,1110 Instruction *EarlierInst,1111 Instruction *LaterInst) {1112 // Check the simple memory generation tracking first.1113 if (EarlierGeneration == LaterGeneration)1114 return true;1115 1116 if (!MSSA)1117 return false;1118 1119 // If MemorySSA has determined that one of EarlierInst or LaterInst does not1120 // read/write memory, then we can safely return true here.1121 // FIXME: We could be more aggressive when checking doesNotAccessMemory(),1122 // onlyReadsMemory(), mayReadFromMemory(), and mayWriteToMemory() in this pass1123 // by also checking the MemorySSA MemoryAccess on the instruction. Initial1124 // experiments suggest this isn't worthwhile, at least for C/C++ code compiled1125 // with the default optimization pipeline.1126 auto *EarlierMA = MSSA->getMemoryAccess(EarlierInst);1127 if (!EarlierMA)1128 return true;1129 auto *LaterMA = MSSA->getMemoryAccess(LaterInst);1130 if (!LaterMA)1131 return true;1132 1133 // Since we know LaterDef dominates LaterInst and EarlierInst dominates1134 // LaterInst, if LaterDef dominates EarlierInst then it can't occur between1135 // EarlierInst and LaterInst and neither can any other write that potentially1136 // clobbers LaterInst.1137 MemoryAccess *LaterDef;1138 if (ClobberCounter < EarlyCSEMssaOptCap) {1139 LaterDef = MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);1140 ClobberCounter++;1141 } else1142 LaterDef = LaterMA->getDefiningAccess();1143 1144 return MSSA->dominates(LaterDef, EarlierMA);1145}1146 1147bool EarlyCSE::isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt) {1148 // A location loaded from with an invariant_load is assumed to *never* change1149 // within the visible scope of the compilation.1150 if (auto *LI = dyn_cast<LoadInst>(I))1151 if (LI->hasMetadata(LLVMContext::MD_invariant_load))1152 return true;1153 1154 auto MemLocOpt = MemoryLocation::getOrNone(I);1155 if (!MemLocOpt)1156 // "target" intrinsic forms of loads aren't currently known to1157 // MemoryLocation::get. TODO1158 return false;1159 MemoryLocation MemLoc = *MemLocOpt;1160 if (!AvailableInvariants.count(MemLoc))1161 return false;1162 1163 // Is the generation at which this became invariant older than the1164 // current one?1165 return AvailableInvariants.lookup(MemLoc) <= GenAt;1166}1167 1168bool EarlyCSE::handleBranchCondition(Instruction *CondInst,1169 const BranchInst *BI, const BasicBlock *BB,1170 const BasicBlock *Pred) {1171 assert(BI->isConditional() && "Should be a conditional branch!");1172 assert(BI->getCondition() == CondInst && "Wrong condition?");1173 assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);1174 auto *TorF = (BI->getSuccessor(0) == BB)1175 ? ConstantInt::getTrue(BB->getContext())1176 : ConstantInt::getFalse(BB->getContext());1177 auto MatchBinOp = [](Instruction *I, unsigned Opcode, Value *&LHS,1178 Value *&RHS) {1179 if (Opcode == Instruction::And &&1180 match(I, m_LogicalAnd(m_Value(LHS), m_Value(RHS))))1181 return true;1182 else if (Opcode == Instruction::Or &&1183 match(I, m_LogicalOr(m_Value(LHS), m_Value(RHS))))1184 return true;1185 return false;1186 };1187 // If the condition is AND operation, we can propagate its operands into the1188 // true branch. If it is OR operation, we can propagate them into the false1189 // branch.1190 unsigned PropagateOpcode =1191 (BI->getSuccessor(0) == BB) ? Instruction::And : Instruction::Or;1192 1193 bool MadeChanges = false;1194 SmallVector<Instruction *, 4> WorkList;1195 SmallPtrSet<Instruction *, 4> Visited;1196 WorkList.push_back(CondInst);1197 while (!WorkList.empty()) {1198 Instruction *Curr = WorkList.pop_back_val();1199 1200 AvailableValues.insert(Curr, TorF);1201 LLVM_DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"1202 << Curr->getName() << "' as " << *TorF << " in "1203 << BB->getName() << "\n");1204 if (!DebugCounter::shouldExecute(CSECounter)) {1205 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");1206 } else {1207 // Replace all dominated uses with the known value.1208 if (unsigned Count = replaceDominatedUsesWith(Curr, TorF, DT,1209 BasicBlockEdge(Pred, BB))) {1210 NumCSECVP += Count;1211 MadeChanges = true;1212 }1213 }1214 1215 Value *LHS, *RHS;1216 if (MatchBinOp(Curr, PropagateOpcode, LHS, RHS))1217 for (auto *Op : { LHS, RHS })1218 if (Instruction *OPI = dyn_cast<Instruction>(Op))1219 if (SimpleValue::canHandle(OPI) && Visited.insert(OPI).second)1220 WorkList.push_back(OPI);1221 }1222 1223 return MadeChanges;1224}1225 1226Value *EarlyCSE::getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,1227 unsigned CurrentGeneration) {1228 if (InVal.DefInst == nullptr)1229 return nullptr;1230 if (InVal.MatchingId != MemInst.getMatchingId())1231 return nullptr;1232 // We don't yet handle removing loads with ordering of any kind.1233 if (MemInst.isVolatile() || !MemInst.isUnordered())1234 return nullptr;1235 // We can't replace an atomic load with one which isn't also atomic.1236 if (MemInst.isLoad() && !InVal.IsAtomic && MemInst.isAtomic())1237 return nullptr;1238 // The value V returned from this function is used differently depending1239 // on whether MemInst is a load or a store. If it's a load, we will replace1240 // MemInst with V, if it's a store, we will check if V is the same as the1241 // available value.1242 bool MemInstMatching = !MemInst.isLoad();1243 Instruction *Matching = MemInstMatching ? MemInst.get() : InVal.DefInst;1244 Instruction *Other = MemInstMatching ? InVal.DefInst : MemInst.get();1245 1246 // For stores check the result values before checking memory generation1247 // (otherwise isSameMemGeneration may crash).1248 Value *Result =1249 MemInst.isStore()1250 ? getOrCreateResult(Matching, Other->getType(), /*CanCreate=*/false)1251 : nullptr;1252 if (MemInst.isStore() && InVal.DefInst != Result)1253 return nullptr;1254 1255 // Deal with non-target memory intrinsics.1256 bool MatchingNTI = isHandledNonTargetIntrinsic(Matching);1257 bool OtherNTI = isHandledNonTargetIntrinsic(Other);1258 if (OtherNTI != MatchingNTI)1259 return nullptr;1260 if (OtherNTI && MatchingNTI) {1261 if (!isNonTargetIntrinsicMatch(cast<IntrinsicInst>(InVal.DefInst),1262 cast<IntrinsicInst>(MemInst.get())))1263 return nullptr;1264 }1265 1266 if (!isOperatingOnInvariantMemAt(MemInst.get(), InVal.Generation) &&1267 !isSameMemGeneration(InVal.Generation, CurrentGeneration, InVal.DefInst,1268 MemInst.get()))1269 return nullptr;1270 1271 if (!Result)1272 Result = getOrCreateResult(Matching, Other->getType(), /*CanCreate=*/true);1273 return Result;1274}1275 1276static void combineIRFlags(Instruction &From, Value *To) {1277 if (auto *I = dyn_cast<Instruction>(To)) {1278 // If I being poison triggers UB, there is no need to drop those1279 // flags. Otherwise, only retain flags present on both I and Inst.1280 // TODO: Currently some fast-math flags are not treated as1281 // poison-generating even though they should. Until this is fixed,1282 // always retain flags present on both I and Inst for floating point1283 // instructions.1284 if (isa<FPMathOperator>(I) ||1285 (I->hasPoisonGeneratingFlags() && !programUndefinedIfPoison(I)))1286 I->andIRFlags(&From);1287 }1288 if (isa<CallBase>(&From) && isa<CallBase>(To)) {1289 // NB: Intersection of attrs between InVal.first and Inst is overly1290 // conservative. Since we only CSE readonly functions that have the same1291 // memory state, we can preserve (or possibly in some cases combine)1292 // more attributes. Likewise this implies when checking equality of1293 // callsite for CSEing, we can probably ignore more attributes.1294 // Generally poison generating attributes need to be handled with more1295 // care as they can create *new* UB if preserved/combined and violated.1296 // Attributes that imply immediate UB on the other hand would have been1297 // violated either way.1298 bool Success =1299 cast<CallBase>(To)->tryIntersectAttributes(cast<CallBase>(&From));1300 assert(Success && "Failed to intersect attributes in callsites that "1301 "passed identical check");1302 // For NDEBUG Compile.1303 (void)Success;1304 }1305}1306 1307bool EarlyCSE::overridingStores(const ParseMemoryInst &Earlier,1308 const ParseMemoryInst &Later) {1309 // Can we remove Earlier store because of Later store?1310 1311 assert(Earlier.isUnordered() && !Earlier.isVolatile() &&1312 "Violated invariant");1313 if (Earlier.getPointerOperand() != Later.getPointerOperand())1314 return false;1315 if (!Earlier.getValueType() || !Later.getValueType() ||1316 Earlier.getValueType() != Later.getValueType())1317 return false;1318 if (Earlier.getMatchingId() != Later.getMatchingId())1319 return false;1320 // At the moment, we don't remove ordered stores, but do remove1321 // unordered atomic stores. There's no special requirement (for1322 // unordered atomics) about removing atomic stores only in favor of1323 // other atomic stores since we were going to execute the non-atomic1324 // one anyway and the atomic one might never have become visible.1325 if (!Earlier.isUnordered() || !Later.isUnordered())1326 return false;1327 1328 // Deal with non-target memory intrinsics.1329 bool ENTI = isHandledNonTargetIntrinsic(Earlier.get());1330 bool LNTI = isHandledNonTargetIntrinsic(Later.get());1331 if (ENTI && LNTI)1332 return isNonTargetIntrinsicMatch(cast<IntrinsicInst>(Earlier.get()),1333 cast<IntrinsicInst>(Later.get()));1334 1335 // Because of the check above, at least one of them is false.1336 // For now disallow matching intrinsics with non-intrinsics,1337 // so assume that the stores match if neither is an intrinsic.1338 return ENTI == LNTI;1339}1340 1341bool EarlyCSE::processNode(DomTreeNode *Node) {1342 bool Changed = false;1343 BasicBlock *BB = Node->getBlock();1344 1345 // If this block has a single predecessor, then the predecessor is the parent1346 // of the domtree node and all of the live out memory values are still current1347 // in this block. If this block has multiple predecessors, then they could1348 // have invalidated the live-out memory values of our parent value. For now,1349 // just be conservative and invalidate memory if this block has multiple1350 // predecessors.1351 if (!BB->getSinglePredecessor())1352 ++CurrentGeneration;1353 1354 // If this node has a single predecessor which ends in a conditional branch,1355 // we can infer the value of the branch condition given that we took this1356 // path. We need the single predecessor to ensure there's not another path1357 // which reaches this block where the condition might hold a different1358 // value. Since we're adding this to the scoped hash table (like any other1359 // def), it will have been popped if we encounter a future merge block.1360 if (BasicBlock *Pred = BB->getSinglePredecessor()) {1361 auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());1362 if (BI && BI->isConditional()) {1363 auto *CondInst = dyn_cast<Instruction>(BI->getCondition());1364 if (CondInst && SimpleValue::canHandle(CondInst))1365 Changed |= handleBranchCondition(CondInst, BI, BB, Pred);1366 }1367 }1368 1369 /// LastStore - Keep track of the last non-volatile store that we saw... for1370 /// as long as there in no instruction that reads memory. If we see a store1371 /// to the same location, we delete the dead store. This zaps trivial dead1372 /// stores which can occur in bitfield code among other things.1373 Instruction *LastStore = nullptr;1374 1375 // See if any instructions in the block can be eliminated. If so, do it. If1376 // not, add them to AvailableValues.1377 for (Instruction &Inst : make_early_inc_range(*BB)) {1378 // Dead instructions should just be removed.1379 if (isInstructionTriviallyDead(&Inst, &TLI)) {1380 LLVM_DEBUG(dbgs() << "EarlyCSE DCE: " << Inst << '\n');1381 if (!DebugCounter::shouldExecute(CSECounter)) {1382 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");1383 continue;1384 }1385 1386 salvageKnowledge(&Inst, &AC);1387 salvageDebugInfo(Inst);1388 removeMSSA(Inst);1389 Inst.eraseFromParent();1390 Changed = true;1391 ++NumSimplify;1392 continue;1393 }1394 1395 // Skip assume intrinsics, they don't really have side effects (although1396 // they're marked as such to ensure preservation of control dependencies),1397 // and this pass will not bother with its removal. However, we should mark1398 // its condition as true for all dominated blocks.1399 if (auto *Assume = dyn_cast<AssumeInst>(&Inst)) {1400 auto *CondI = dyn_cast<Instruction>(Assume->getArgOperand(0));1401 if (CondI && SimpleValue::canHandle(CondI)) {1402 LLVM_DEBUG(dbgs() << "EarlyCSE considering assumption: " << Inst1403 << '\n');1404 AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));1405 } else1406 LLVM_DEBUG(dbgs() << "EarlyCSE skipping assumption: " << Inst << '\n');1407 continue;1408 }1409 1410 // Likewise, noalias intrinsics don't actually write.1411 if (match(&Inst,1412 m_Intrinsic<Intrinsic::experimental_noalias_scope_decl>())) {1413 LLVM_DEBUG(dbgs() << "EarlyCSE skipping noalias intrinsic: " << Inst1414 << '\n');1415 continue;1416 }1417 1418 // Skip sideeffect intrinsics, for the same reason as assume intrinsics.1419 if (match(&Inst, m_Intrinsic<Intrinsic::sideeffect>())) {1420 LLVM_DEBUG(dbgs() << "EarlyCSE skipping sideeffect: " << Inst << '\n');1421 continue;1422 }1423 1424 // Skip pseudoprobe intrinsics, for the same reason as assume intrinsics.1425 if (match(&Inst, m_Intrinsic<Intrinsic::pseudoprobe>())) {1426 LLVM_DEBUG(dbgs() << "EarlyCSE skipping pseudoprobe: " << Inst << '\n');1427 continue;1428 }1429 1430 // We can skip all invariant.start intrinsics since they only read memory,1431 // and we can forward values across it. For invariant starts without1432 // invariant ends, we can use the fact that the invariantness never ends to1433 // start a scope in the current generaton which is true for all future1434 // generations. Also, we dont need to consume the last store since the1435 // semantics of invariant.start allow us to perform DSE of the last1436 // store, if there was a store following invariant.start. Consider:1437 //1438 // store 30, i8* p1439 // invariant.start(p)1440 // store 40, i8* p1441 // We can DSE the store to 30, since the store 40 to invariant location p1442 // causes undefined behaviour.1443 if (match(&Inst, m_Intrinsic<Intrinsic::invariant_start>())) {1444 // If there are any uses, the scope might end.1445 if (!Inst.use_empty())1446 continue;1447 MemoryLocation MemLoc =1448 MemoryLocation::getForArgument(&cast<CallInst>(Inst), 1, TLI);1449 // Don't start a scope if we already have a better one pushed1450 if (!AvailableInvariants.count(MemLoc))1451 AvailableInvariants.insert(MemLoc, CurrentGeneration);1452 continue;1453 }1454 1455 if (isGuard(&Inst)) {1456 if (auto *CondI =1457 dyn_cast<Instruction>(cast<CallInst>(Inst).getArgOperand(0))) {1458 if (SimpleValue::canHandle(CondI)) {1459 // Do we already know the actual value of this condition?1460 if (auto *KnownCond = AvailableValues.lookup(CondI)) {1461 // Is the condition known to be true?1462 if (isa<ConstantInt>(KnownCond) &&1463 cast<ConstantInt>(KnownCond)->isOne()) {1464 LLVM_DEBUG(dbgs()1465 << "EarlyCSE removing guard: " << Inst << '\n');1466 salvageKnowledge(&Inst, &AC);1467 removeMSSA(Inst);1468 Inst.eraseFromParent();1469 Changed = true;1470 continue;1471 } else1472 // Use the known value if it wasn't true.1473 cast<CallInst>(Inst).setArgOperand(0, KnownCond);1474 }1475 // The condition we're on guarding here is true for all dominated1476 // locations.1477 AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));1478 }1479 }1480 1481 // Guard intrinsics read all memory, but don't write any memory.1482 // Accordingly, don't update the generation but consume the last store (to1483 // avoid an incorrect DSE).1484 LastStore = nullptr;1485 continue;1486 }1487 1488 // If the instruction can be simplified (e.g. X+0 = X) then replace it with1489 // its simpler value.1490 if (Value *V = simplifyInstruction(&Inst, SQ)) {1491 LLVM_DEBUG(dbgs() << "EarlyCSE Simplify: " << Inst << " to: " << *V1492 << '\n');1493 if (!DebugCounter::shouldExecute(CSECounter)) {1494 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");1495 } else {1496 bool Killed = false;1497 if (!Inst.use_empty()) {1498 Inst.replaceAllUsesWith(V);1499 Changed = true;1500 }1501 if (isInstructionTriviallyDead(&Inst, &TLI)) {1502 salvageKnowledge(&Inst, &AC);1503 removeMSSA(Inst);1504 Inst.eraseFromParent();1505 Changed = true;1506 Killed = true;1507 }1508 if (Changed)1509 ++NumSimplify;1510 if (Killed)1511 continue;1512 }1513 }1514 1515 // Make sure stores prior to a potential unwind are not removed, as the1516 // caller may read the memory.1517 if (Inst.mayThrow())1518 LastStore = nullptr;1519 1520 // If this is a simple instruction that we can value number, process it.1521 if (SimpleValue::canHandle(&Inst)) {1522 if ([[maybe_unused]] auto *CI = dyn_cast<ConstrainedFPIntrinsic>(&Inst)) {1523 assert(CI->getExceptionBehavior() != fp::ebStrict &&1524 "Unexpected ebStrict from SimpleValue::canHandle()");1525 assert((!CI->getRoundingMode() ||1526 CI->getRoundingMode() != RoundingMode::Dynamic) &&1527 "Unexpected dynamic rounding from SimpleValue::canHandle()");1528 }1529 // See if the instruction has an available value. If so, use it.1530 if (Value *V = AvailableValues.lookup(&Inst)) {1531 LLVM_DEBUG(dbgs() << "EarlyCSE CSE: " << Inst << " to: " << *V1532 << '\n');1533 if (!DebugCounter::shouldExecute(CSECounter)) {1534 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");1535 continue;1536 }1537 combineIRFlags(Inst, V);1538 Inst.replaceAllUsesWith(V);1539 salvageKnowledge(&Inst, &AC);1540 removeMSSA(Inst);1541 Inst.eraseFromParent();1542 Changed = true;1543 ++NumCSE;1544 continue;1545 }1546 1547 // Otherwise, just remember that this value is available.1548 AvailableValues.insert(&Inst, &Inst);1549 continue;1550 }1551 1552 ParseMemoryInst MemInst(&Inst, TTI);1553 // If this is a non-volatile load, process it.1554 if (MemInst.isValid() && MemInst.isLoad()) {1555 // (conservatively) we can't peak past the ordering implied by this1556 // operation, but we can add this load to our set of available values1557 if (MemInst.isVolatile() || !MemInst.isUnordered()) {1558 LastStore = nullptr;1559 ++CurrentGeneration;1560 }1561 1562 if (MemInst.isInvariantLoad()) {1563 // If we pass an invariant load, we know that memory location is1564 // indefinitely constant from the moment of first dereferenceability.1565 // We conservatively treat the invariant_load as that moment. If we1566 // pass a invariant load after already establishing a scope, don't1567 // restart it since we want to preserve the earliest point seen.1568 auto MemLoc = MemoryLocation::get(&Inst);1569 if (!AvailableInvariants.count(MemLoc))1570 AvailableInvariants.insert(MemLoc, CurrentGeneration);1571 }1572 1573 // If we have an available version of this load, and if it is the right1574 // generation or the load is known to be from an invariant location,1575 // replace this instruction.1576 //1577 // If either the dominating load or the current load are invariant, then1578 // we can assume the current load loads the same value as the dominating1579 // load.1580 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());1581 if (Value *Op = getMatchingValue(InVal, MemInst, CurrentGeneration)) {1582 LLVM_DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << Inst1583 << " to: " << *InVal.DefInst << '\n');1584 if (!DebugCounter::shouldExecute(CSECounter)) {1585 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");1586 continue;1587 }1588 if (InVal.IsLoad)1589 if (auto *I = dyn_cast<Instruction>(Op))1590 combineMetadataForCSE(I, &Inst, false);1591 if (!Inst.use_empty())1592 Inst.replaceAllUsesWith(Op);1593 salvageKnowledge(&Inst, &AC);1594 removeMSSA(Inst);1595 Inst.eraseFromParent();1596 Changed = true;1597 ++NumCSELoad;1598 continue;1599 }1600 1601 // Otherwise, remember that we have this instruction.1602 AvailableLoads.insert(MemInst.getPointerOperand(),1603 LoadValue(&Inst, CurrentGeneration,1604 MemInst.getMatchingId(),1605 MemInst.isAtomic(),1606 MemInst.isLoad()));1607 LastStore = nullptr;1608 continue;1609 }1610 1611 // If this instruction may read from memory, forget LastStore. Load/store1612 // intrinsics will indicate both a read and a write to memory. The target1613 // may override this (e.g. so that a store intrinsic does not read from1614 // memory, and thus will be treated the same as a regular store for1615 // commoning purposes).1616 if (Inst.mayReadFromMemory() &&1617 !(MemInst.isValid() && !MemInst.mayReadFromMemory()))1618 LastStore = nullptr;1619 1620 // If this is a read-only or write-only call, process it. Skip store1621 // MemInsts, as they will be more precisely handled later on. Also skip1622 // memsets, as DSE may be able to optimize them better by removing the1623 // earlier rather than later store.1624 if (CallValue::canHandle(&Inst) &&1625 (!MemInst.isValid() || !MemInst.isStore()) && !isa<MemSetInst>(&Inst)) {1626 // If we have an available version of this call, and if it is the right1627 // generation, replace this instruction.1628 std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(&Inst);1629 if (InVal.first != nullptr &&1630 isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,1631 &Inst) &&1632 InVal.first->mayReadFromMemory() == Inst.mayReadFromMemory()) {1633 LLVM_DEBUG(dbgs() << "EarlyCSE CSE CALL: " << Inst1634 << " to: " << *InVal.first << '\n');1635 if (!DebugCounter::shouldExecute(CSECounter)) {1636 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");1637 continue;1638 }1639 combineIRFlags(Inst, InVal.first);1640 if (!Inst.use_empty())1641 Inst.replaceAllUsesWith(InVal.first);1642 salvageKnowledge(&Inst, &AC);1643 removeMSSA(Inst);1644 Inst.eraseFromParent();1645 Changed = true;1646 ++NumCSECall;1647 continue;1648 }1649 1650 // Increase memory generation for writes. Do this before inserting1651 // the call, so it has the generation after the write occurred.1652 if (Inst.mayWriteToMemory())1653 ++CurrentGeneration;1654 1655 // Otherwise, remember that we have this instruction.1656 AvailableCalls.insert(&Inst, std::make_pair(&Inst, CurrentGeneration));1657 continue;1658 }1659 1660 // Compare GEP instructions based on offset.1661 if (GEPValue::canHandle(&Inst)) {1662 auto *GEP = cast<GetElementPtrInst>(&Inst);1663 APInt Offset = APInt(SQ.DL.getIndexTypeSizeInBits(GEP->getType()), 0);1664 GEPValue GEPVal(GEP, GEP->accumulateConstantOffset(SQ.DL, Offset)1665 ? Offset.trySExtValue()1666 : std::nullopt);1667 if (Value *V = AvailableGEPs.lookup(GEPVal)) {1668 LLVM_DEBUG(dbgs() << "EarlyCSE CSE GEP: " << Inst << " to: " << *V1669 << '\n');1670 combineIRFlags(Inst, V);1671 Inst.replaceAllUsesWith(V);1672 salvageKnowledge(&Inst, &AC);1673 removeMSSA(Inst);1674 Inst.eraseFromParent();1675 Changed = true;1676 ++NumCSEGEP;1677 continue;1678 }1679 1680 // Otherwise, just remember that we have this GEP.1681 AvailableGEPs.insert(GEPVal, &Inst);1682 continue;1683 }1684 1685 // A release fence requires that all stores complete before it, but does1686 // not prevent the reordering of following loads 'before' the fence. As a1687 // result, we don't need to consider it as writing to memory and don't need1688 // to advance the generation. We do need to prevent DSE across the fence,1689 // but that's handled above.1690 if (auto *FI = dyn_cast<FenceInst>(&Inst))1691 if (FI->getOrdering() == AtomicOrdering::Release) {1692 assert(Inst.mayReadFromMemory() && "relied on to prevent DSE above");1693 continue;1694 }1695 1696 // write back DSE - If we write back the same value we just loaded from1697 // the same location and haven't passed any intervening writes or ordering1698 // operations, we can remove the write. The primary benefit is in allowing1699 // the available load table to remain valid and value forward past where1700 // the store originally was.1701 if (MemInst.isValid() && MemInst.isStore()) {1702 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());1703 if (InVal.DefInst &&1704 InVal.DefInst ==1705 getMatchingValue(InVal, MemInst, CurrentGeneration)) {1706 LLVM_DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << Inst << '\n');1707 if (!DebugCounter::shouldExecute(CSECounter)) {1708 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");1709 continue;1710 }1711 salvageKnowledge(&Inst, &AC);1712 removeMSSA(Inst);1713 Inst.eraseFromParent();1714 Changed = true;1715 ++NumDSE;1716 // We can avoid incrementing the generation count since we were able1717 // to eliminate this store.1718 continue;1719 }1720 }1721 1722 // Okay, this isn't something we can CSE at all. Check to see if it is1723 // something that could modify memory. If so, our available memory values1724 // cannot be used so bump the generation count.1725 if (Inst.mayWriteToMemory()) {1726 ++CurrentGeneration;1727 1728 if (MemInst.isValid() && MemInst.isStore()) {1729 // We do a trivial form of DSE if there are two stores to the same1730 // location with no intervening loads. Delete the earlier store.1731 if (LastStore) {1732 if (overridingStores(ParseMemoryInst(LastStore, TTI), MemInst)) {1733 LLVM_DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore1734 << " due to: " << Inst << '\n');1735 if (!DebugCounter::shouldExecute(CSECounter)) {1736 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");1737 } else {1738 salvageKnowledge(&Inst, &AC);1739 removeMSSA(*LastStore);1740 LastStore->eraseFromParent();1741 Changed = true;1742 ++NumDSE;1743 LastStore = nullptr;1744 }1745 }1746 // fallthrough - we can exploit information about this store1747 }1748 1749 // Okay, we just invalidated anything we knew about loaded values. Try1750 // to salvage *something* by remembering that the stored value is a live1751 // version of the pointer. It is safe to forward from volatile stores1752 // to non-volatile loads, so we don't have to check for volatility of1753 // the store.1754 AvailableLoads.insert(MemInst.getPointerOperand(),1755 LoadValue(&Inst, CurrentGeneration,1756 MemInst.getMatchingId(),1757 MemInst.isAtomic(),1758 MemInst.isLoad()));1759 1760 // Remember that this was the last unordered store we saw for DSE. We1761 // don't yet handle DSE on ordered or volatile stores since we don't1762 // have a good way to model the ordering requirement for following1763 // passes once the store is removed. We could insert a fence, but1764 // since fences are slightly stronger than stores in their ordering,1765 // it's not clear this is a profitable transform. Another option would1766 // be to merge the ordering with that of the post dominating store.1767 if (MemInst.isUnordered() && !MemInst.isVolatile())1768 LastStore = &Inst;1769 else1770 LastStore = nullptr;1771 }1772 }1773 }1774 1775 return Changed;1776}1777 1778bool EarlyCSE::run() {1779 // Note, deque is being used here because there is significant performance1780 // gains over vector when the container becomes very large due to the1781 // specific access patterns. For more information see the mailing list1782 // discussion on this:1783 // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html1784 std::deque<StackNode *> nodesToProcess;1785 1786 bool Changed = false;1787 1788 // Process the root node.1789 nodesToProcess.push_back(new StackNode(1790 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,1791 AvailableGEPs, CurrentGeneration, DT.getRootNode(),1792 DT.getRootNode()->begin(), DT.getRootNode()->end()));1793 1794 assert(!CurrentGeneration && "Create a new EarlyCSE instance to rerun it.");1795 1796 // Process the stack.1797 while (!nodesToProcess.empty()) {1798 // Grab the first item off the stack. Set the current generation, remove1799 // the node from the stack, and process it.1800 StackNode *NodeToProcess = nodesToProcess.back();1801 1802 // Initialize class members.1803 CurrentGeneration = NodeToProcess->currentGeneration();1804 1805 // Check if the node needs to be processed.1806 if (!NodeToProcess->isProcessed()) {1807 // Process the node.1808 Changed |= processNode(NodeToProcess->node());1809 NodeToProcess->childGeneration(CurrentGeneration);1810 NodeToProcess->process();1811 } else if (NodeToProcess->childIter() != NodeToProcess->end()) {1812 // Push the next child onto the stack.1813 DomTreeNode *child = NodeToProcess->nextChild();1814 nodesToProcess.push_back(new StackNode(1815 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,1816 AvailableGEPs, NodeToProcess->childGeneration(), child,1817 child->begin(), child->end()));1818 } else {1819 // It has been processed, and there are no more children to process,1820 // so delete it and pop it off the stack.1821 delete NodeToProcess;1822 nodesToProcess.pop_back();1823 }1824 } // while (!nodes...)1825 1826 return Changed;1827}1828 1829PreservedAnalyses EarlyCSEPass::run(Function &F,1830 FunctionAnalysisManager &AM) {1831 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);1832 auto &TTI = AM.getResult<TargetIRAnalysis>(F);1833 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);1834 auto &AC = AM.getResult<AssumptionAnalysis>(F);1835 auto *MSSA =1836 UseMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA() : nullptr;1837 1838 EarlyCSE CSE(F.getDataLayout(), TLI, TTI, DT, AC, MSSA);1839 1840 if (!CSE.run())1841 return PreservedAnalyses::all();1842 1843 PreservedAnalyses PA;1844 PA.preserveSet<CFGAnalyses>();1845 if (UseMemorySSA)1846 PA.preserve<MemorySSAAnalysis>();1847 return PA;1848}1849 1850void EarlyCSEPass::printPipeline(1851 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {1852 static_cast<PassInfoMixin<EarlyCSEPass> *>(this)->printPipeline(1853 OS, MapClassName2PassName);1854 OS << '<';1855 if (UseMemorySSA)1856 OS << "memssa";1857 OS << '>';1858}1859 1860namespace {1861 1862/// A simple and fast domtree-based CSE pass.1863///1864/// This pass does a simple depth-first walk over the dominator tree,1865/// eliminating trivially redundant instructions and using instsimplify to1866/// canonicalize things as it goes. It is intended to be fast and catch obvious1867/// cases so that instcombine and other passes are more effective. It is1868/// expected that a later pass of GVN will catch the interesting/hard cases.1869template<bool UseMemorySSA>1870class EarlyCSELegacyCommonPass : public FunctionPass {1871public:1872 static char ID;1873 1874 EarlyCSELegacyCommonPass() : FunctionPass(ID) {1875 if (UseMemorySSA)1876 initializeEarlyCSEMemSSALegacyPassPass(*PassRegistry::getPassRegistry());1877 else1878 initializeEarlyCSELegacyPassPass(*PassRegistry::getPassRegistry());1879 }1880 1881 bool runOnFunction(Function &F) override {1882 if (skipFunction(F))1883 return false;1884 1885 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);1886 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);1887 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();1888 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);1889 auto *MSSA =1890 UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() : nullptr;1891 1892 EarlyCSE CSE(F.getDataLayout(), TLI, TTI, DT, AC, MSSA);1893 1894 return CSE.run();1895 }1896 1897 void getAnalysisUsage(AnalysisUsage &AU) const override {1898 AU.addRequired<AssumptionCacheTracker>();1899 AU.addRequired<DominatorTreeWrapperPass>();1900 AU.addRequired<TargetLibraryInfoWrapperPass>();1901 AU.addRequired<TargetTransformInfoWrapperPass>();1902 if (UseMemorySSA) {1903 AU.addRequired<AAResultsWrapperPass>();1904 AU.addRequired<MemorySSAWrapperPass>();1905 AU.addPreserved<MemorySSAWrapperPass>();1906 }1907 AU.addPreserved<GlobalsAAWrapperPass>();1908 AU.addPreserved<AAResultsWrapperPass>();1909 AU.setPreservesCFG();1910 }1911};1912 1913} // end anonymous namespace1914 1915using EarlyCSELegacyPass = EarlyCSELegacyCommonPass</*UseMemorySSA=*/false>;1916 1917template<>1918char EarlyCSELegacyPass::ID = 0;1919 1920INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,1921 false)1922INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)1923INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)1924INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)1925INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)1926INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)1927 1928using EarlyCSEMemSSALegacyPass =1929 EarlyCSELegacyCommonPass</*UseMemorySSA=*/true>;1930 1931template<>1932char EarlyCSEMemSSALegacyPass::ID = 0;1933 1934FunctionPass *llvm::createEarlyCSEPass(bool UseMemorySSA) {1935 if (UseMemorySSA)1936 return new EarlyCSEMemSSALegacyPass();1937 else1938 return new EarlyCSELegacyPass();1939}1940 1941INITIALIZE_PASS_BEGIN(EarlyCSEMemSSALegacyPass, "early-cse-memssa",1942 "Early CSE w/ MemorySSA", false, false)1943INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)1944INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)1945INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)1946INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)1947INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)1948INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)1949INITIALIZE_PASS_END(EarlyCSEMemSSALegacyPass, "early-cse-memssa",1950 "Early CSE w/ MemorySSA", false, false)1951