1274955Ssvnmir//===- MergedLoadStoreMotion.cpp - merge and hoist/sink load/stores -------===// 2274955Ssvnmir// 3274955Ssvnmir// The LLVM Compiler Infrastructure 4274955Ssvnmir// 5274955Ssvnmir// This file is distributed under the University of Illinois Open Source 6274955Ssvnmir// License. See LICENSE.TXT for details. 7274955Ssvnmir// 8274955Ssvnmir//===----------------------------------------------------------------------===// 9274955Ssvnmir// 10274955Ssvnmir//! \file 11274955Ssvnmir//! \brief This pass performs merges of loads and stores on both sides of a 12274955Ssvnmir// diamond (hammock). It hoists the loads and sinks the stores. 13274955Ssvnmir// 14274955Ssvnmir// The algorithm iteratively hoists two loads to the same address out of a 15274955Ssvnmir// diamond (hammock) and merges them into a single load in the header. Similar 16274955Ssvnmir// it sinks and merges two stores to the tail block (footer). The algorithm 17274955Ssvnmir// iterates over the instructions of one side of the diamond and attempts to 18274955Ssvnmir// find a matching load/store on the other side. It hoists / sinks when it 19274955Ssvnmir// thinks it safe to do so. This optimization helps with eg. hiding load 20274955Ssvnmir// latencies, triggering if-conversion, and reducing static code size. 21274955Ssvnmir// 22274955Ssvnmir//===----------------------------------------------------------------------===// 23274955Ssvnmir// 24274955Ssvnmir// 25274955Ssvnmir// Example: 26274955Ssvnmir// Diamond shaped code before merge: 27274955Ssvnmir// 28274955Ssvnmir// header: 29274955Ssvnmir// br %cond, label %if.then, label %if.else 30277320Sdim// + + 31277320Sdim// + + 32277320Sdim// + + 33274955Ssvnmir// if.then: if.else: 34274955Ssvnmir// %lt = load %addr_l %le = load %addr_l 35274955Ssvnmir// <use %lt> <use %le> 36274955Ssvnmir// <...> <...> 37274955Ssvnmir// store %st, %addr_s store %se, %addr_s 38274955Ssvnmir// br label %if.end br label %if.end 39277320Sdim// + + 40277320Sdim// + + 41277320Sdim// + + 42274955Ssvnmir// if.end ("footer"): 43274955Ssvnmir// <...> 44274955Ssvnmir// 45274955Ssvnmir// Diamond shaped code after merge: 46274955Ssvnmir// 47274955Ssvnmir// header: 48274955Ssvnmir// %l = load %addr_l 49274955Ssvnmir// br %cond, label %if.then, label %if.else 50277320Sdim// + + 51277320Sdim// + + 52277320Sdim// + + 53274955Ssvnmir// if.then: if.else: 54274955Ssvnmir// <use %l> <use %l> 55274955Ssvnmir// <...> <...> 56274955Ssvnmir// br label %if.end br label %if.end 57277320Sdim// + + 58277320Sdim// + + 59277320Sdim// + + 60274955Ssvnmir// if.end ("footer"): 61274955Ssvnmir// %s.sink = phi [%st, if.then], [%se, if.else] 62274955Ssvnmir// <...> 63274955Ssvnmir// store %s.sink, %addr_s 64274955Ssvnmir// <...> 65274955Ssvnmir// 66274955Ssvnmir// 67274955Ssvnmir//===----------------------- TODO -----------------------------------------===// 68274955Ssvnmir// 69274955Ssvnmir// 1) Generalize to regions other than diamonds 70274955Ssvnmir// 2) Be more aggressive merging memory operations 71274955Ssvnmir// Note that both changes require register pressure control 72274955Ssvnmir// 73274955Ssvnmir//===----------------------------------------------------------------------===// 74274955Ssvnmir 75274955Ssvnmir#include "llvm/Transforms/Scalar.h" 76274955Ssvnmir#include "llvm/ADT/SetVector.h" 77274955Ssvnmir#include "llvm/ADT/SmallPtrSet.h" 78274955Ssvnmir#include "llvm/ADT/Statistic.h" 79274955Ssvnmir#include "llvm/Analysis/AliasAnalysis.h" 80274955Ssvnmir#include "llvm/Analysis/CFG.h" 81296417Sdim#include "llvm/Analysis/GlobalsModRef.h" 82274955Ssvnmir#include "llvm/Analysis/Loads.h" 83274955Ssvnmir#include "llvm/Analysis/MemoryBuiltins.h" 84274955Ssvnmir#include "llvm/Analysis/MemoryDependenceAnalysis.h" 85288943Sdim#include "llvm/Analysis/TargetLibraryInfo.h" 86274955Ssvnmir#include "llvm/IR/Metadata.h" 87274955Ssvnmir#include "llvm/IR/PatternMatch.h" 88274955Ssvnmir#include "llvm/Support/Allocator.h" 89274955Ssvnmir#include "llvm/Support/CommandLine.h" 90274955Ssvnmir#include "llvm/Support/Debug.h" 91288943Sdim#include "llvm/Support/raw_ostream.h" 92274955Ssvnmir#include "llvm/Transforms/Utils/BasicBlockUtils.h" 93274955Ssvnmir#include "llvm/Transforms/Utils/SSAUpdater.h" 94274955Ssvnmir#include <vector> 95296417Sdim 96274955Ssvnmirusing namespace llvm; 97274955Ssvnmir 98274955Ssvnmir#define DEBUG_TYPE "mldst-motion" 99274955Ssvnmir 100274955Ssvnmir//===----------------------------------------------------------------------===// 101274955Ssvnmir// MergedLoadStoreMotion Pass 102274955Ssvnmir//===----------------------------------------------------------------------===// 103274955Ssvnmir 104274955Ssvnmirnamespace { 105274955Ssvnmirclass MergedLoadStoreMotion : public FunctionPass { 106274955Ssvnmir AliasAnalysis *AA; 107274955Ssvnmir MemoryDependenceAnalysis *MD; 108274955Ssvnmir 109274955Ssvnmirpublic: 110274955Ssvnmir static char ID; // Pass identification, replacement for typeid 111296417Sdim MergedLoadStoreMotion() 112274955Ssvnmir : FunctionPass(ID), MD(nullptr), MagicCompileTimeControl(250) { 113274955Ssvnmir initializeMergedLoadStoreMotionPass(*PassRegistry::getPassRegistry()); 114274955Ssvnmir } 115274955Ssvnmir 116274955Ssvnmir bool runOnFunction(Function &F) override; 117274955Ssvnmir 118274955Ssvnmirprivate: 119274955Ssvnmir // This transformation requires dominator postdominator info 120274955Ssvnmir void getAnalysisUsage(AnalysisUsage &AU) const override { 121296417Sdim AU.setPreservesCFG(); 122288943Sdim AU.addRequired<TargetLibraryInfoWrapperPass>(); 123296417Sdim AU.addRequired<AAResultsWrapperPass>(); 124296417Sdim AU.addPreserved<GlobalsAAWrapperPass>(); 125288943Sdim AU.addPreserved<MemoryDependenceAnalysis>(); 126274955Ssvnmir } 127274955Ssvnmir 128274955Ssvnmir // Helper routines 129274955Ssvnmir 130274955Ssvnmir /// 131274955Ssvnmir /// \brief Remove instruction from parent and update memory dependence 132274955Ssvnmir /// analysis. 133274955Ssvnmir /// 134274955Ssvnmir void removeInstruction(Instruction *Inst); 135274955Ssvnmir BasicBlock *getDiamondTail(BasicBlock *BB); 136274955Ssvnmir bool isDiamondHead(BasicBlock *BB); 137274955Ssvnmir // Routines for hoisting loads 138280031Sdim bool isLoadHoistBarrierInRange(const Instruction& Start, 139280031Sdim const Instruction& End, 140280031Sdim LoadInst* LI); 141274955Ssvnmir LoadInst *canHoistFromBlock(BasicBlock *BB, LoadInst *LI); 142274955Ssvnmir void hoistInstruction(BasicBlock *BB, Instruction *HoistCand, 143274955Ssvnmir Instruction *ElseInst); 144274955Ssvnmir bool isSafeToHoist(Instruction *I) const; 145274955Ssvnmir bool hoistLoad(BasicBlock *BB, LoadInst *HoistCand, LoadInst *ElseInst); 146274955Ssvnmir bool mergeLoads(BasicBlock *BB); 147274955Ssvnmir // Routines for sinking stores 148274955Ssvnmir StoreInst *canSinkFromBlock(BasicBlock *BB, StoreInst *SI); 149274955Ssvnmir PHINode *getPHIOperand(BasicBlock *BB, StoreInst *S0, StoreInst *S1); 150288943Sdim bool isStoreSinkBarrierInRange(const Instruction &Start, 151288943Sdim const Instruction &End, MemoryLocation Loc); 152274955Ssvnmir bool sinkStore(BasicBlock *BB, StoreInst *SinkCand, StoreInst *ElseInst); 153274955Ssvnmir bool mergeStores(BasicBlock *BB); 154274955Ssvnmir // The mergeLoad/Store algorithms could have Size0 * Size1 complexity, 155274955Ssvnmir // where Size0 and Size1 are the #instructions on the two sides of 156274955Ssvnmir // the diamond. The constant chosen here is arbitrary. Compiler Time 157274955Ssvnmir // Control is enforced by the check Size0 * Size1 < MagicCompileTimeControl. 158274955Ssvnmir const int MagicCompileTimeControl; 159274955Ssvnmir}; 160274955Ssvnmir 161274955Ssvnmirchar MergedLoadStoreMotion::ID = 0; 162296417Sdim} // anonymous namespace 163274955Ssvnmir 164274955Ssvnmir/// 165274955Ssvnmir/// \brief createMergedLoadStoreMotionPass - The public interface to this file. 166274955Ssvnmir/// 167274955SsvnmirFunctionPass *llvm::createMergedLoadStoreMotionPass() { 168274955Ssvnmir return new MergedLoadStoreMotion(); 169274955Ssvnmir} 170274955Ssvnmir 171274955SsvnmirINITIALIZE_PASS_BEGIN(MergedLoadStoreMotion, "mldst-motion", 172274955Ssvnmir "MergedLoadStoreMotion", false, false) 173274955SsvnmirINITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) 174288943SdimINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 175296417SdimINITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 176296417SdimINITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) 177274955SsvnmirINITIALIZE_PASS_END(MergedLoadStoreMotion, "mldst-motion", 178274955Ssvnmir "MergedLoadStoreMotion", false, false) 179274955Ssvnmir 180274955Ssvnmir/// 181274955Ssvnmir/// \brief Remove instruction from parent and update memory dependence analysis. 182274955Ssvnmir/// 183274955Ssvnmirvoid MergedLoadStoreMotion::removeInstruction(Instruction *Inst) { 184274955Ssvnmir // Notify the memory dependence analysis. 185274955Ssvnmir if (MD) { 186274955Ssvnmir MD->removeInstruction(Inst); 187274955Ssvnmir if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) 188274955Ssvnmir MD->invalidateCachedPointerInfo(LI->getPointerOperand()); 189274955Ssvnmir if (Inst->getType()->getScalarType()->isPointerTy()) { 190274955Ssvnmir MD->invalidateCachedPointerInfo(Inst); 191274955Ssvnmir } 192274955Ssvnmir } 193274955Ssvnmir Inst->eraseFromParent(); 194274955Ssvnmir} 195274955Ssvnmir 196274955Ssvnmir/// 197274955Ssvnmir/// \brief Return tail block of a diamond. 198274955Ssvnmir/// 199274955SsvnmirBasicBlock *MergedLoadStoreMotion::getDiamondTail(BasicBlock *BB) { 200274955Ssvnmir assert(isDiamondHead(BB) && "Basic block is not head of a diamond"); 201274955Ssvnmir BranchInst *BI = (BranchInst *)(BB->getTerminator()); 202274955Ssvnmir BasicBlock *Succ0 = BI->getSuccessor(0); 203274955Ssvnmir BasicBlock *Tail = Succ0->getTerminator()->getSuccessor(0); 204274955Ssvnmir return Tail; 205274955Ssvnmir} 206274955Ssvnmir 207274955Ssvnmir/// 208274955Ssvnmir/// \brief True when BB is the head of a diamond (hammock) 209274955Ssvnmir/// 210274955Ssvnmirbool MergedLoadStoreMotion::isDiamondHead(BasicBlock *BB) { 211274955Ssvnmir if (!BB) 212274955Ssvnmir return false; 213274955Ssvnmir if (!isa<BranchInst>(BB->getTerminator())) 214274955Ssvnmir return false; 215274955Ssvnmir if (BB->getTerminator()->getNumSuccessors() != 2) 216274955Ssvnmir return false; 217274955Ssvnmir 218274955Ssvnmir BranchInst *BI = (BranchInst *)(BB->getTerminator()); 219274955Ssvnmir BasicBlock *Succ0 = BI->getSuccessor(0); 220274955Ssvnmir BasicBlock *Succ1 = BI->getSuccessor(1); 221274955Ssvnmir 222274955Ssvnmir if (!Succ0->getSinglePredecessor() || 223274955Ssvnmir Succ0->getTerminator()->getNumSuccessors() != 1) 224274955Ssvnmir return false; 225274955Ssvnmir if (!Succ1->getSinglePredecessor() || 226274955Ssvnmir Succ1->getTerminator()->getNumSuccessors() != 1) 227274955Ssvnmir return false; 228274955Ssvnmir 229274955Ssvnmir BasicBlock *Tail = Succ0->getTerminator()->getSuccessor(0); 230274955Ssvnmir // Ignore triangles. 231274955Ssvnmir if (Succ1->getTerminator()->getSuccessor(0) != Tail) 232274955Ssvnmir return false; 233274955Ssvnmir return true; 234274955Ssvnmir} 235274955Ssvnmir 236274955Ssvnmir/// 237274955Ssvnmir/// \brief True when instruction is a hoist barrier for a load 238274955Ssvnmir/// 239274955Ssvnmir/// Whenever an instruction could possibly modify the value 240274955Ssvnmir/// being loaded or protect against the load from happening 241274955Ssvnmir/// it is considered a hoist barrier. 242274955Ssvnmir/// 243280031Sdimbool MergedLoadStoreMotion::isLoadHoistBarrierInRange(const Instruction& Start, 244280031Sdim const Instruction& End, 245280031Sdim LoadInst* LI) { 246288943Sdim MemoryLocation Loc = MemoryLocation::get(LI); 247296417Sdim return AA->canInstructionRangeModRef(Start, End, Loc, MRI_Mod); 248274955Ssvnmir} 249274955Ssvnmir 250274955Ssvnmir/// 251274955Ssvnmir/// \brief Decide if a load can be hoisted 252274955Ssvnmir/// 253274955Ssvnmir/// When there is a load in \p BB to the same address as \p LI 254274955Ssvnmir/// and it can be hoisted from \p BB, return that load. 255274955Ssvnmir/// Otherwise return Null. 256274955Ssvnmir/// 257280031SdimLoadInst *MergedLoadStoreMotion::canHoistFromBlock(BasicBlock *BB1, 258280031Sdim LoadInst *Load0) { 259274955Ssvnmir 260280031Sdim for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end(); BBI != BBE; 261274955Ssvnmir ++BBI) { 262296417Sdim Instruction *Inst = &*BBI; 263274955Ssvnmir 264274955Ssvnmir // Only merge and hoist loads when their result in used only in BB 265280031Sdim if (!isa<LoadInst>(Inst) || Inst->isUsedOutsideOfBlock(BB1)) 266274955Ssvnmir continue; 267274955Ssvnmir 268280031Sdim LoadInst *Load1 = dyn_cast<LoadInst>(Inst); 269280031Sdim BasicBlock *BB0 = Load0->getParent(); 270280031Sdim 271288943Sdim MemoryLocation Loc0 = MemoryLocation::get(Load0); 272288943Sdim MemoryLocation Loc1 = MemoryLocation::get(Load1); 273280031Sdim if (AA->isMustAlias(Loc0, Loc1) && Load0->isSameOperationAs(Load1) && 274280031Sdim !isLoadHoistBarrierInRange(BB1->front(), *Load1, Load1) && 275280031Sdim !isLoadHoistBarrierInRange(BB0->front(), *Load0, Load0)) { 276280031Sdim return Load1; 277274955Ssvnmir } 278274955Ssvnmir } 279280031Sdim return nullptr; 280274955Ssvnmir} 281274955Ssvnmir 282274955Ssvnmir/// 283274955Ssvnmir/// \brief Merge two equivalent instructions \p HoistCand and \p ElseInst into 284274955Ssvnmir/// \p BB 285274955Ssvnmir/// 286274955Ssvnmir/// BB is the head of a diamond 287274955Ssvnmir/// 288274955Ssvnmirvoid MergedLoadStoreMotion::hoistInstruction(BasicBlock *BB, 289274955Ssvnmir Instruction *HoistCand, 290274955Ssvnmir Instruction *ElseInst) { 291274955Ssvnmir DEBUG(dbgs() << " Hoist Instruction into BB \n"; BB->dump(); 292274955Ssvnmir dbgs() << "Instruction Left\n"; HoistCand->dump(); dbgs() << "\n"; 293274955Ssvnmir dbgs() << "Instruction Right\n"; ElseInst->dump(); dbgs() << "\n"); 294274955Ssvnmir // Hoist the instruction. 295274955Ssvnmir assert(HoistCand->getParent() != BB); 296274955Ssvnmir 297274955Ssvnmir // Intersect optional metadata. 298274955Ssvnmir HoistCand->intersectOptionalDataWith(ElseInst); 299296417Sdim HoistCand->dropUnknownNonDebugMetadata(); 300274955Ssvnmir 301274955Ssvnmir // Prepend point for instruction insert 302274955Ssvnmir Instruction *HoistPt = BB->getTerminator(); 303274955Ssvnmir 304274955Ssvnmir // Merged instruction 305274955Ssvnmir Instruction *HoistedInst = HoistCand->clone(); 306274955Ssvnmir 307274955Ssvnmir // Hoist instruction. 308274955Ssvnmir HoistedInst->insertBefore(HoistPt); 309274955Ssvnmir 310274955Ssvnmir HoistCand->replaceAllUsesWith(HoistedInst); 311274955Ssvnmir removeInstruction(HoistCand); 312274955Ssvnmir // Replace the else block instruction. 313274955Ssvnmir ElseInst->replaceAllUsesWith(HoistedInst); 314274955Ssvnmir removeInstruction(ElseInst); 315274955Ssvnmir} 316274955Ssvnmir 317274955Ssvnmir/// 318274955Ssvnmir/// \brief Return true if no operand of \p I is defined in I's parent block 319274955Ssvnmir/// 320274955Ssvnmirbool MergedLoadStoreMotion::isSafeToHoist(Instruction *I) const { 321274955Ssvnmir BasicBlock *Parent = I->getParent(); 322274955Ssvnmir for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 323274955Ssvnmir Instruction *Instr = dyn_cast<Instruction>(I->getOperand(i)); 324274955Ssvnmir if (Instr && Instr->getParent() == Parent) 325274955Ssvnmir return false; 326274955Ssvnmir } 327274955Ssvnmir return true; 328274955Ssvnmir} 329274955Ssvnmir 330274955Ssvnmir/// 331274955Ssvnmir/// \brief Merge two equivalent loads and GEPs and hoist into diamond head 332274955Ssvnmir/// 333274955Ssvnmirbool MergedLoadStoreMotion::hoistLoad(BasicBlock *BB, LoadInst *L0, 334274955Ssvnmir LoadInst *L1) { 335274955Ssvnmir // Only one definition? 336274955Ssvnmir Instruction *A0 = dyn_cast<Instruction>(L0->getPointerOperand()); 337274955Ssvnmir Instruction *A1 = dyn_cast<Instruction>(L1->getPointerOperand()); 338274955Ssvnmir if (A0 && A1 && A0->isIdenticalTo(A1) && isSafeToHoist(A0) && 339274955Ssvnmir A0->hasOneUse() && (A0->getParent() == L0->getParent()) && 340274955Ssvnmir A1->hasOneUse() && (A1->getParent() == L1->getParent()) && 341274955Ssvnmir isa<GetElementPtrInst>(A0)) { 342274955Ssvnmir DEBUG(dbgs() << "Hoist Instruction into BB \n"; BB->dump(); 343274955Ssvnmir dbgs() << "Instruction Left\n"; L0->dump(); dbgs() << "\n"; 344274955Ssvnmir dbgs() << "Instruction Right\n"; L1->dump(); dbgs() << "\n"); 345274955Ssvnmir hoistInstruction(BB, A0, A1); 346274955Ssvnmir hoistInstruction(BB, L0, L1); 347274955Ssvnmir return true; 348274955Ssvnmir } else 349274955Ssvnmir return false; 350274955Ssvnmir} 351274955Ssvnmir 352274955Ssvnmir/// 353274955Ssvnmir/// \brief Try to hoist two loads to same address into diamond header 354274955Ssvnmir/// 355274955Ssvnmir/// Starting from a diamond head block, iterate over the instructions in one 356274955Ssvnmir/// successor block and try to match a load in the second successor. 357274955Ssvnmir/// 358274955Ssvnmirbool MergedLoadStoreMotion::mergeLoads(BasicBlock *BB) { 359274955Ssvnmir bool MergedLoads = false; 360274955Ssvnmir assert(isDiamondHead(BB)); 361274955Ssvnmir BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 362274955Ssvnmir BasicBlock *Succ0 = BI->getSuccessor(0); 363274955Ssvnmir BasicBlock *Succ1 = BI->getSuccessor(1); 364274955Ssvnmir // #Instructions in Succ1 for Compile Time Control 365274955Ssvnmir int Size1 = Succ1->size(); 366274955Ssvnmir int NLoads = 0; 367274955Ssvnmir for (BasicBlock::iterator BBI = Succ0->begin(), BBE = Succ0->end(); 368274955Ssvnmir BBI != BBE;) { 369296417Sdim Instruction *I = &*BBI; 370274955Ssvnmir ++BBI; 371274955Ssvnmir 372274955Ssvnmir // Only move non-simple (atomic, volatile) loads. 373280031Sdim LoadInst *L0 = dyn_cast<LoadInst>(I); 374280031Sdim if (!L0 || !L0->isSimple() || L0->isUsedOutsideOfBlock(Succ0)) 375274955Ssvnmir continue; 376274955Ssvnmir 377274955Ssvnmir ++NLoads; 378274955Ssvnmir if (NLoads * Size1 >= MagicCompileTimeControl) 379274955Ssvnmir break; 380274955Ssvnmir if (LoadInst *L1 = canHoistFromBlock(Succ1, L0)) { 381274955Ssvnmir bool Res = hoistLoad(BB, L0, L1); 382274955Ssvnmir MergedLoads |= Res; 383274955Ssvnmir // Don't attempt to hoist above loads that had not been hoisted. 384274955Ssvnmir if (!Res) 385274955Ssvnmir break; 386274955Ssvnmir } 387274955Ssvnmir } 388274955Ssvnmir return MergedLoads; 389274955Ssvnmir} 390274955Ssvnmir 391274955Ssvnmir/// 392280031Sdim/// \brief True when instruction is a sink barrier for a store 393280031Sdim/// located in Loc 394280031Sdim/// 395280031Sdim/// Whenever an instruction could possibly read or modify the 396280031Sdim/// value being stored or protect against the store from 397280031Sdim/// happening it is considered a sink barrier. 398280031Sdim/// 399288943Sdimbool MergedLoadStoreMotion::isStoreSinkBarrierInRange(const Instruction &Start, 400288943Sdim const Instruction &End, 401288943Sdim MemoryLocation Loc) { 402296417Sdim return AA->canInstructionRangeModRef(Start, End, Loc, MRI_ModRef); 403274955Ssvnmir} 404274955Ssvnmir 405274955Ssvnmir/// 406274955Ssvnmir/// \brief Check if \p BB contains a store to the same address as \p SI 407274955Ssvnmir/// 408274955Ssvnmir/// \return The store in \p when it is safe to sink. Otherwise return Null. 409274955Ssvnmir/// 410280031SdimStoreInst *MergedLoadStoreMotion::canSinkFromBlock(BasicBlock *BB1, 411280031Sdim StoreInst *Store0) { 412280031Sdim DEBUG(dbgs() << "can Sink? : "; Store0->dump(); dbgs() << "\n"); 413280031Sdim BasicBlock *BB0 = Store0->getParent(); 414280031Sdim for (BasicBlock::reverse_iterator RBI = BB1->rbegin(), RBE = BB1->rend(); 415274955Ssvnmir RBI != RBE; ++RBI) { 416274955Ssvnmir Instruction *Inst = &*RBI; 417274955Ssvnmir 418280031Sdim if (!isa<StoreInst>(Inst)) 419280031Sdim continue; 420280031Sdim 421280031Sdim StoreInst *Store1 = cast<StoreInst>(Inst); 422280031Sdim 423288943Sdim MemoryLocation Loc0 = MemoryLocation::get(Store0); 424288943Sdim MemoryLocation Loc1 = MemoryLocation::get(Store1); 425280031Sdim if (AA->isMustAlias(Loc0, Loc1) && Store0->isSameOperationAs(Store1) && 426280031Sdim !isStoreSinkBarrierInRange(*(std::next(BasicBlock::iterator(Store1))), 427280031Sdim BB1->back(), Loc1) && 428280031Sdim !isStoreSinkBarrierInRange(*(std::next(BasicBlock::iterator(Store0))), 429280031Sdim BB0->back(), Loc0)) { 430280031Sdim return Store1; 431274955Ssvnmir } 432274955Ssvnmir } 433280031Sdim return nullptr; 434274955Ssvnmir} 435274955Ssvnmir 436274955Ssvnmir/// 437274955Ssvnmir/// \brief Create a PHI node in BB for the operands of S0 and S1 438274955Ssvnmir/// 439274955SsvnmirPHINode *MergedLoadStoreMotion::getPHIOperand(BasicBlock *BB, StoreInst *S0, 440274955Ssvnmir StoreInst *S1) { 441274955Ssvnmir // Create a phi if the values mismatch. 442296417Sdim PHINode *NewPN = nullptr; 443274955Ssvnmir Value *Opd1 = S0->getValueOperand(); 444274955Ssvnmir Value *Opd2 = S1->getValueOperand(); 445274955Ssvnmir if (Opd1 != Opd2) { 446274955Ssvnmir NewPN = PHINode::Create(Opd1->getType(), 2, Opd2->getName() + ".sink", 447296417Sdim &BB->front()); 448274955Ssvnmir NewPN->addIncoming(Opd1, S0->getParent()); 449274955Ssvnmir NewPN->addIncoming(Opd2, S1->getParent()); 450296417Sdim if (MD && NewPN->getType()->getScalarType()->isPointerTy()) 451296417Sdim MD->invalidateCachedPointerInfo(NewPN); 452274955Ssvnmir } 453274955Ssvnmir return NewPN; 454274955Ssvnmir} 455274955Ssvnmir 456274955Ssvnmir/// 457274955Ssvnmir/// \brief Merge two stores to same address and sink into \p BB 458274955Ssvnmir/// 459274955Ssvnmir/// Also sinks GEP instruction computing the store address 460274955Ssvnmir/// 461274955Ssvnmirbool MergedLoadStoreMotion::sinkStore(BasicBlock *BB, StoreInst *S0, 462274955Ssvnmir StoreInst *S1) { 463274955Ssvnmir // Only one definition? 464274955Ssvnmir Instruction *A0 = dyn_cast<Instruction>(S0->getPointerOperand()); 465274955Ssvnmir Instruction *A1 = dyn_cast<Instruction>(S1->getPointerOperand()); 466274955Ssvnmir if (A0 && A1 && A0->isIdenticalTo(A1) && A0->hasOneUse() && 467274955Ssvnmir (A0->getParent() == S0->getParent()) && A1->hasOneUse() && 468274955Ssvnmir (A1->getParent() == S1->getParent()) && isa<GetElementPtrInst>(A0)) { 469274955Ssvnmir DEBUG(dbgs() << "Sink Instruction into BB \n"; BB->dump(); 470274955Ssvnmir dbgs() << "Instruction Left\n"; S0->dump(); dbgs() << "\n"; 471274955Ssvnmir dbgs() << "Instruction Right\n"; S1->dump(); dbgs() << "\n"); 472274955Ssvnmir // Hoist the instruction. 473274955Ssvnmir BasicBlock::iterator InsertPt = BB->getFirstInsertionPt(); 474274955Ssvnmir // Intersect optional metadata. 475274955Ssvnmir S0->intersectOptionalDataWith(S1); 476296417Sdim S0->dropUnknownNonDebugMetadata(); 477274955Ssvnmir 478274955Ssvnmir // Create the new store to be inserted at the join point. 479274955Ssvnmir StoreInst *SNew = (StoreInst *)(S0->clone()); 480274955Ssvnmir Instruction *ANew = A0->clone(); 481296417Sdim SNew->insertBefore(&*InsertPt); 482274955Ssvnmir ANew->insertBefore(SNew); 483274955Ssvnmir 484274955Ssvnmir assert(S0->getParent() == A0->getParent()); 485274955Ssvnmir assert(S1->getParent() == A1->getParent()); 486274955Ssvnmir 487274955Ssvnmir PHINode *NewPN = getPHIOperand(BB, S0, S1); 488274955Ssvnmir // New PHI operand? Use it. 489274955Ssvnmir if (NewPN) 490274955Ssvnmir SNew->setOperand(0, NewPN); 491274955Ssvnmir removeInstruction(S0); 492274955Ssvnmir removeInstruction(S1); 493274955Ssvnmir A0->replaceAllUsesWith(ANew); 494274955Ssvnmir removeInstruction(A0); 495274955Ssvnmir A1->replaceAllUsesWith(ANew); 496274955Ssvnmir removeInstruction(A1); 497274955Ssvnmir return true; 498274955Ssvnmir } 499274955Ssvnmir return false; 500274955Ssvnmir} 501274955Ssvnmir 502274955Ssvnmir/// 503274955Ssvnmir/// \brief True when two stores are equivalent and can sink into the footer 504274955Ssvnmir/// 505274955Ssvnmir/// Starting from a diamond tail block, iterate over the instructions in one 506274955Ssvnmir/// predecessor block and try to match a store in the second predecessor. 507274955Ssvnmir/// 508274955Ssvnmirbool MergedLoadStoreMotion::mergeStores(BasicBlock *T) { 509274955Ssvnmir 510274955Ssvnmir bool MergedStores = false; 511274955Ssvnmir assert(T && "Footer of a diamond cannot be empty"); 512274955Ssvnmir 513274955Ssvnmir pred_iterator PI = pred_begin(T), E = pred_end(T); 514274955Ssvnmir assert(PI != E); 515274955Ssvnmir BasicBlock *Pred0 = *PI; 516274955Ssvnmir ++PI; 517274955Ssvnmir BasicBlock *Pred1 = *PI; 518274955Ssvnmir ++PI; 519274955Ssvnmir // tail block of a diamond/hammock? 520274955Ssvnmir if (Pred0 == Pred1) 521274955Ssvnmir return false; // No. 522274955Ssvnmir if (PI != E) 523274955Ssvnmir return false; // No. More than 2 predecessors. 524274955Ssvnmir 525274955Ssvnmir // #Instructions in Succ1 for Compile Time Control 526274955Ssvnmir int Size1 = Pred1->size(); 527274955Ssvnmir int NStores = 0; 528274955Ssvnmir 529274955Ssvnmir for (BasicBlock::reverse_iterator RBI = Pred0->rbegin(), RBE = Pred0->rend(); 530274955Ssvnmir RBI != RBE;) { 531274955Ssvnmir 532274955Ssvnmir Instruction *I = &*RBI; 533274955Ssvnmir ++RBI; 534280031Sdim 535274955Ssvnmir // Sink move non-simple (atomic, volatile) stores 536274955Ssvnmir if (!isa<StoreInst>(I)) 537274955Ssvnmir continue; 538274955Ssvnmir StoreInst *S0 = (StoreInst *)I; 539274955Ssvnmir if (!S0->isSimple()) 540274955Ssvnmir continue; 541274955Ssvnmir 542274955Ssvnmir ++NStores; 543274955Ssvnmir if (NStores * Size1 >= MagicCompileTimeControl) 544274955Ssvnmir break; 545274955Ssvnmir if (StoreInst *S1 = canSinkFromBlock(Pred1, S0)) { 546274955Ssvnmir bool Res = sinkStore(T, S0, S1); 547274955Ssvnmir MergedStores |= Res; 548274955Ssvnmir // Don't attempt to sink below stores that had to stick around 549274955Ssvnmir // But after removal of a store and some of its feeding 550274955Ssvnmir // instruction search again from the beginning since the iterator 551274955Ssvnmir // is likely stale at this point. 552274955Ssvnmir if (!Res) 553274955Ssvnmir break; 554274955Ssvnmir else { 555274955Ssvnmir RBI = Pred0->rbegin(); 556274955Ssvnmir RBE = Pred0->rend(); 557274955Ssvnmir DEBUG(dbgs() << "Search again\n"; Instruction *I = &*RBI; I->dump()); 558274955Ssvnmir } 559274955Ssvnmir } 560274955Ssvnmir } 561274955Ssvnmir return MergedStores; 562274955Ssvnmir} 563296417Sdim 564274955Ssvnmir/// 565274955Ssvnmir/// \brief Run the transformation for each function 566274955Ssvnmir/// 567274955Ssvnmirbool MergedLoadStoreMotion::runOnFunction(Function &F) { 568288943Sdim MD = getAnalysisIfAvailable<MemoryDependenceAnalysis>(); 569296417Sdim AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 570274955Ssvnmir 571274955Ssvnmir bool Changed = false; 572274955Ssvnmir DEBUG(dbgs() << "Instruction Merger\n"); 573274955Ssvnmir 574274955Ssvnmir // Merge unconditional branches, allowing PRE to catch more 575274955Ssvnmir // optimization opportunities. 576274955Ssvnmir for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) { 577296417Sdim BasicBlock *BB = &*FI++; 578274955Ssvnmir 579274955Ssvnmir // Hoist equivalent loads and sink stores 580274955Ssvnmir // outside diamonds when possible 581274955Ssvnmir if (isDiamondHead(BB)) { 582274955Ssvnmir Changed |= mergeLoads(BB); 583274955Ssvnmir Changed |= mergeStores(getDiamondTail(BB)); 584274955Ssvnmir } 585274955Ssvnmir } 586274955Ssvnmir return Changed; 587274955Ssvnmir} 588