//===- DeadStoreElimination.cpp - MemorySSA Backed Dead Store Elimination -===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // The code below implements dead store elimination using MemorySSA. It uses // the following general approach: given a MemoryDef, walk upwards to find // clobbering MemoryDefs that may be killed by the starting def. Then check // that there are no uses that may read the location of the original MemoryDef // in between both MemoryDefs. A bit more concretely: // // For all MemoryDefs StartDef: // 1. Get the next dominating clobbering MemoryDef (MaybeDeadAccess) by walking // upwards. // 2. Check that there are no reads between MaybeDeadAccess and the StartDef by // checking all uses starting at MaybeDeadAccess and walking until we see // StartDef. // 3. For each found CurrentDef, check that: // 1. There are no barrier instructions between CurrentDef and StartDef (like // throws or stores with ordering constraints). // 2. StartDef is executed whenever CurrentDef is executed. // 3. StartDef completely overwrites CurrentDef. // 4. Erase CurrentDef from the function and MemorySSA. // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/DeadStoreElimination.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryLocation.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DebugInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/Value.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/DebugCounter.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/AssumeBundleBuilder.h" #include "llvm/Transforms/Utils/BuildLibCalls.h" #include "llvm/Transforms/Utils/Local.h" #include <algorithm> #include <cassert> #include <cstdint> #include <iterator> #include <map> #include <optional> #include <utility> usingnamespacellvm; usingnamespacePatternMatch; #define DEBUG_TYPE … STATISTIC(NumRemainingStores, "Number of stores remaining after DSE"); STATISTIC(NumRedundantStores, "Number of redundant stores deleted"); STATISTIC(NumFastStores, "Number of stores deleted"); STATISTIC(NumFastOther, "Number of other instrs removed"); STATISTIC(NumCompletePartials, "Number of stores dead by later partials"); STATISTIC(NumModifiedStores, "Number of stores modified"); STATISTIC(NumCFGChecks, "Number of stores modified"); STATISTIC(NumCFGTries, "Number of stores modified"); STATISTIC(NumCFGSuccess, "Number of stores modified"); STATISTIC(NumGetDomMemoryDefPassed, "Number of times a valid candidate is returned from getDomMemoryDef"); STATISTIC(NumDomMemDefChecks, "Number iterations check for reads in getDomMemoryDef"); DEBUG_COUNTER(MemorySSACounter, "dse-memoryssa", "Controls which MemoryDefs are eliminated."); static cl::opt<bool> EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking", cl::init(true), cl::Hidden, cl::desc("Enable partial-overwrite tracking in DSE")); static cl::opt<bool> EnablePartialStoreMerging("enable-dse-partial-store-merging", cl::init(true), cl::Hidden, cl::desc("Enable partial store merging in DSE")); static cl::opt<unsigned> MemorySSAScanLimit("dse-memoryssa-scanlimit", cl::init(150), cl::Hidden, cl::desc("The number of memory instructions to scan for " "dead store elimination (default = 150)")); static cl::opt<unsigned> MemorySSAUpwardsStepLimit( "dse-memoryssa-walklimit", cl::init(90), cl::Hidden, cl::desc("The maximum number of steps while walking upwards to find " "MemoryDefs that may be killed (default = 90)")); static cl::opt<unsigned> MemorySSAPartialStoreLimit( "dse-memoryssa-partial-store-limit", cl::init(5), cl::Hidden, cl::desc("The maximum number candidates that only partially overwrite the " "killing MemoryDef to consider" " (default = 5)")); static cl::opt<unsigned> MemorySSADefsPerBlockLimit( "dse-memoryssa-defs-per-block-limit", cl::init(5000), cl::Hidden, cl::desc("The number of MemoryDefs we consider as candidates to eliminated " "other stores per basic block (default = 5000)")); static cl::opt<unsigned> MemorySSASameBBStepCost( "dse-memoryssa-samebb-cost", cl::init(1), cl::Hidden, cl::desc( "The cost of a step in the same basic block as the killing MemoryDef" "(default = 1)")); static cl::opt<unsigned> MemorySSAOtherBBStepCost("dse-memoryssa-otherbb-cost", cl::init(5), cl::Hidden, cl::desc("The cost of a step in a different basic " "block than the killing MemoryDef" "(default = 5)")); static cl::opt<unsigned> MemorySSAPathCheckLimit( "dse-memoryssa-path-check-limit", cl::init(50), cl::Hidden, cl::desc("The maximum number of blocks to check when trying to prove that " "all paths to an exit go through a killing block (default = 50)")); // This flags allows or disallows DSE to optimize MemorySSA during its // traversal. Note that DSE optimizing MemorySSA may impact other passes // downstream of the DSE invocation and can lead to issues not being // reproducible in isolation (i.e. when MemorySSA is built from scratch). In // those cases, the flag can be used to check if DSE's MemorySSA optimizations // impact follow-up passes. static cl::opt<bool> OptimizeMemorySSA("dse-optimize-memoryssa", cl::init(true), cl::Hidden, cl::desc("Allow DSE to optimize memory accesses.")); //===----------------------------------------------------------------------===// // Helper functions //===----------------------------------------------------------------------===// OverlapIntervalsTy; InstOverlapIntervalsTy; /// Returns true if the end of this instruction can be safely shortened in /// length. static bool isShortenableAtTheEnd(Instruction *I) { … } /// Returns true if the beginning of this instruction can be safely shortened /// in length. static bool isShortenableAtTheBeginning(Instruction *I) { … } static std::optional<TypeSize> getPointerSize(const Value *V, const DataLayout &DL, const TargetLibraryInfo &TLI, const Function *F) { … } namespace { enum OverwriteResult { … }; } // end anonymous namespace /// Check if two instruction are masked stores that completely /// overwrite one another. More specifically, \p KillingI has to /// overwrite \p DeadI. static OverwriteResult isMaskedStoreOverwrite(const Instruction *KillingI, const Instruction *DeadI, BatchAAResults &AA) { … } /// Return 'OW_Complete' if a store to the 'KillingLoc' location completely /// overwrites a store to the 'DeadLoc' location, 'OW_End' if the end of the /// 'DeadLoc' location is completely overwritten by 'KillingLoc', 'OW_Begin' /// if the beginning of the 'DeadLoc' location is overwritten by 'KillingLoc'. /// 'OW_PartialEarlierWithFullLater' means that a dead (big) store was /// overwritten by a killing (smaller) store which doesn't write outside the big /// store's memory locations. Returns 'OW_Unknown' if nothing can be determined. /// NOTE: This function must only be called if both \p KillingLoc and \p /// DeadLoc belong to the same underlying object with valid \p KillingOff and /// \p DeadOff. static OverwriteResult isPartialOverwrite(const MemoryLocation &KillingLoc, const MemoryLocation &DeadLoc, int64_t KillingOff, int64_t DeadOff, Instruction *DeadI, InstOverlapIntervalsTy &IOL) { … } /// Returns true if the memory which is accessed by the second instruction is not /// modified between the first and the second instruction. /// Precondition: Second instruction must be dominated by the first /// instruction. static bool memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI, BatchAAResults &AA, const DataLayout &DL, DominatorTree *DT) { … } static void shortenAssignment(Instruction *Inst, Value *OriginalDest, uint64_t OldOffsetInBits, uint64_t OldSizeInBits, uint64_t NewSizeInBits, bool IsOverwriteEnd) { … } static bool tryToShorten(Instruction *DeadI, int64_t &DeadStart, uint64_t &DeadSize, int64_t KillingStart, uint64_t KillingSize, bool IsOverwriteEnd) { … } static bool tryToShortenEnd(Instruction *DeadI, OverlapIntervalsTy &IntervalMap, int64_t &DeadStart, uint64_t &DeadSize) { … } static bool tryToShortenBegin(Instruction *DeadI, OverlapIntervalsTy &IntervalMap, int64_t &DeadStart, uint64_t &DeadSize) { … } static Constant * tryToMergePartialOverlappingStores(StoreInst *KillingI, StoreInst *DeadI, int64_t KillingOffset, int64_t DeadOffset, const DataLayout &DL, BatchAAResults &AA, DominatorTree *DT) { … } namespace { // Returns true if \p I is an intrinsic that does not read or write memory. bool isNoopIntrinsic(Instruction *I) { … } // Check if we can ignore \p D for DSE. bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller) { … } // A memory location wrapper that represents a MemoryLocation, `MemLoc`, // defined by `MemDef`. struct MemoryLocationWrapper { … }; // A memory def wrapper that represents a MemoryDef and the MemoryLocation(s) // defined by this MemoryDef. struct MemoryDefWrapper { … }; struct DSEState { … }; std::pair<bool, bool> DSEState::eliminateDeadDefs(const MemoryLocationWrapper &KillingLocWrapper) { … } bool DSEState::eliminateDeadDefs(const MemoryDefWrapper &KillingDefWrapper) { … } static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT, PostDominatorTree &PDT, const TargetLibraryInfo &TLI, const LoopInfo &LI) { … } } // end anonymous namespace //===----------------------------------------------------------------------===// // DSE Pass //===----------------------------------------------------------------------===// PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) { … }
Codebase Browser
llvm