From 2f6d42351ac4c1d72762a9193c1c8abdb79f2d77 Mon Sep 17 00:00:00 2001 From: Elena Demikhovsky Date: Mon, 15 Dec 2014 14:09:53 +0000 Subject: [PATCH] Sink store based on alias analysis - by Ella Bolshinsky The alias analysis is used define whether the given instruction is a barrier for store sinking. For 2 identical stores, following instructions are checked in the both basic blocks, to determine whether they are sinking barriers. http://reviews.llvm.org/D6420 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@224247 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/AliasAnalysis.h | 27 ++++--- lib/Analysis/AliasAnalysis.cpp | 21 +++--- lib/Transforms/IPO/ArgumentPromotion.cpp | 3 +- .../Scalar/MergedLoadStoreMotion.cpp | 75 +++++++++---------- 4 files changed, 63 insertions(+), 63 deletions(-) diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index 9bfa0459027..763f3729881 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -502,7 +502,7 @@ public: /// /// canBasicBlockModify - Return true if it is possible for execution of the - /// specified basic block to modify the value pointed to by Ptr. + /// specified basic block to modify the location Loc. bool canBasicBlockModify(const BasicBlock &BB, const Location &Loc); /// canBasicBlockModify - A convenience wrapper. @@ -510,17 +510,20 @@ public: return canBasicBlockModify(BB, Location(P, Size)); } - /// canInstructionRangeModify - Return true if it is possible for the - /// execution of the specified instructions to modify the value pointed to by - /// Ptr. The instructions to consider are all of the instructions in the - /// range of [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. - bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, - const Location &Loc); - - /// canInstructionRangeModify - A convenience wrapper. - bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, - const Value *Ptr, uint64_t Size) { - return canInstructionRangeModify(I1, I2, Location(Ptr, Size)); + /// canInstructionRangeModRef - Return true if it is possible for the + /// execution of the specified instructions to mod\ref (according to the + /// mode) the location Loc. The instructions to consider are all + /// of the instructions in the range of [I1,I2] INCLUSIVE. + /// I1 and I2 must be in the same basic block. + bool canInstructionRangeModRef(const Instruction &I1, + const Instruction &I2, const Location &Loc, + const ModRefResult Mode); + + /// canInstructionRangeModRef - A convenience wrapper. + bool canInstructionRangeModRef(const Instruction &I1, + const Instruction &I2, const Value *Ptr, + uint64_t Size, const ModRefResult Mode) { + return canInstructionRangeModRef(I1, I2, Location(Ptr, Size), Mode); } //===--------------------------------------------------------------------===// diff --git a/lib/Analysis/AliasAnalysis.cpp b/lib/Analysis/AliasAnalysis.cpp index 5171a456745..6eea8177418 100644 --- a/lib/Analysis/AliasAnalysis.cpp +++ b/lib/Analysis/AliasAnalysis.cpp @@ -483,21 +483,22 @@ uint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) { } /// canBasicBlockModify - Return true if it is possible for execution of the -/// specified basic block to modify the value pointed to by Ptr. +/// specified basic block to modify the location Loc. /// bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, const Location &Loc) { - return canInstructionRangeModify(BB.front(), BB.back(), Loc); + return canInstructionRangeModRef(BB.front(), BB.back(), Loc, Mod); } -/// canInstructionRangeModify - Return true if it is possible for the execution -/// of the specified instructions to modify the value pointed to by Ptr. The -/// instructions to consider are all of the instructions in the range of [I1,I2] -/// INCLUSIVE. I1 and I2 must be in the same basic block. -/// -bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, +/// canInstructionRangeModRef - Return true if it is possible for the +/// execution of the specified instructions to mod\ref (according to the +/// mode) the location Loc. The instructions to consider are all +/// of the instructions in the range of [I1,I2] INCLUSIVE. +/// I1 and I2 must be in the same basic block. +bool AliasAnalysis::canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, - const Location &Loc) { + const Location &Loc, + const ModRefResult Mode) { assert(I1.getParent() == I2.getParent() && "Instructions not in same basic block!"); BasicBlock::const_iterator I = &I1; @@ -505,7 +506,7 @@ bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, ++E; // Convert from inclusive to exclusive range. for (; I != E; ++I) // Check every instruction in range - if (getModRefInfo(I, Loc) & Mod) + if (getModRefInfo(I, Loc) & Mode) return true; return false; } diff --git a/lib/Transforms/IPO/ArgumentPromotion.cpp b/lib/Transforms/IPO/ArgumentPromotion.cpp index c4706e89fab..32820229386 100644 --- a/lib/Transforms/IPO/ArgumentPromotion.cpp +++ b/lib/Transforms/IPO/ArgumentPromotion.cpp @@ -554,7 +554,8 @@ bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg, BasicBlock *BB = Load->getParent(); AliasAnalysis::Location Loc = AA.getLocation(Load); - if (AA.canInstructionRangeModify(BB->front(), *Load, Loc)) + if (AA.canInstructionRangeModRef(BB->front(), *Load, Loc, + AliasAnalysis::Mod)) return false; // Pointer is invalidated! // Now check every path from the entry block to the load for transparency. diff --git a/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp b/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp index 8281c59c590..8509713b336 100644 --- a/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp +++ b/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp @@ -143,7 +143,9 @@ private: // Routines for sinking stores StoreInst *canSinkFromBlock(BasicBlock *BB, StoreInst *SI); PHINode *getPHIOperand(BasicBlock *BB, StoreInst *S0, StoreInst *S1); - bool isStoreSinkBarrier(Instruction *Inst); + bool isStoreSinkBarrierInRange(const Instruction& Start, + const Instruction& End, + AliasAnalysis::Location Loc); bool sinkStore(BasicBlock *BB, StoreInst *SinkCand, StoreInst *ElseInst); bool mergeStores(BasicBlock *BB); // The mergeLoad/Store algorithms could have Size0 * Size1 complexity, @@ -239,7 +241,7 @@ bool MergedLoadStoreMotion::isLoadHoistBarrierInRange(const Instruction& Start, const Instruction& End, LoadInst* LI) { AliasAnalysis::Location Loc = AA->getLocation(LI); - return AA->canInstructionRangeModify(Start, End, Loc); + return AA->canInstructionRangeModRef(Start, End, Loc, AliasAnalysis::Mod); } /// @@ -389,26 +391,19 @@ bool MergedLoadStoreMotion::mergeLoads(BasicBlock *BB) { } /// -/// \brief True when instruction is sink barrier for a store -/// -bool MergedLoadStoreMotion::isStoreSinkBarrier(Instruction *Inst) { - // FIXME: Conservatively let a load instruction block the store. - // Use alias analysis instead. - if (isa(Inst)) - return true; - if (isa(Inst)) - return true; - if (isa(Inst) && !isa(Inst)) - return true; - // Note: mayHaveSideEffects covers all instructions that could - // trigger a change to state. Eg. in-flight stores have to be executed - // before ordered loads or fences, calls could invoke functions that store - // data to memory etc. - if (!isa(Inst) && Inst->mayHaveSideEffects()) { - return true; - } - DEBUG(dbgs() << "No Sink Barrier\n"); - return false; +/// \brief True when instruction is a sink barrier for a store +/// located in Loc +/// +/// Whenever an instruction could possibly read or modify the +/// value being stored or protect against the store from +/// happening it is considered a sink barrier. +/// + +bool MergedLoadStoreMotion::isStoreSinkBarrierInRange(const Instruction& Start, + const Instruction& End, + AliasAnalysis::Location + Loc) { + return AA->canInstructionRangeModRef(Start, End, Loc, AliasAnalysis::Ref); } /// @@ -416,27 +411,28 @@ bool MergedLoadStoreMotion::isStoreSinkBarrier(Instruction *Inst) { /// /// \return The store in \p when it is safe to sink. Otherwise return Null. /// -StoreInst *MergedLoadStoreMotion::canSinkFromBlock(BasicBlock *BB, - StoreInst *SI) { - StoreInst *I = 0; - DEBUG(dbgs() << "can Sink? : "; SI->dump(); dbgs() << "\n"); - for (BasicBlock::reverse_iterator RBI = BB->rbegin(), RBE = BB->rend(); +StoreInst *MergedLoadStoreMotion::canSinkFromBlock(BasicBlock *BB1, + StoreInst *Store0) { + DEBUG(dbgs() << "can Sink? : "; Store0->dump(); dbgs() << "\n"); + for (BasicBlock::reverse_iterator RBI = BB1->rbegin(), RBE = BB1->rend(); RBI != RBE; ++RBI) { Instruction *Inst = &*RBI; - // Only move loads if they are used in the block. - if (isStoreSinkBarrier(Inst)) - break; - if (isa(Inst)) { - AliasAnalysis::Location LocSI = AA->getLocation(SI); - AliasAnalysis::Location LocInst = AA->getLocation((StoreInst *)Inst); - if (AA->isMustAlias(LocSI, LocInst)) { - I = (StoreInst *)Inst; - break; - } + if (!isa(Inst)) + continue; + + StoreInst *Store1 = cast(Inst); + BasicBlock *BB0 = Store0->getParent(); + + AliasAnalysis::Location Loc0 = AA->getLocation(Store0); + AliasAnalysis::Location Loc1 = AA->getLocation(Store1); + if (AA->isMustAlias(Loc0, Loc1) && Store0->isSameOperationAs(Store1) && + !isStoreSinkBarrierInRange(*Store1, BB1->back(), Loc1) && + !isStoreSinkBarrierInRange(*Store0, BB0->back(), Loc0)) { + return Store1; } } - return I; + return nullptr; } /// @@ -548,8 +544,7 @@ bool MergedLoadStoreMotion::mergeStores(BasicBlock *T) { Instruction *I = &*RBI; ++RBI; - if (isStoreSinkBarrier(I)) - break; + // Sink move non-simple (atomic, volatile) stores if (!isa(I)) continue; -- 2.34.1