MergedLoadStoreMotion.cpp Source File (original) (raw)

89using namespace llvm;

91#define DEBUG_TYPE "mldst-motion"

93namespace {

97class MergedLoadStoreMotion {

100

101

102

103

104 const int MagicCompileTimeControl = 250;

105

106 const bool SplitFooterBB;

107public:

108 MergedLoadStoreMotion(bool SplitFooterBB) : SplitFooterBB(SplitFooterBB) {}

110

111private:

114

117 bool isStoreSinkBarrierInRange(const Instruction &Start,

123};

124}

125

126

127

128

130 assert(isDiamondHead(BB) && "Basic block is not head of a diamond");

132}

133

134

135

136

137bool MergedLoadStoreMotion::isDiamondHead(BasicBlock *BB) {

138 if (!BB)

139 return false;

141 if (!BI || !BI->isConditional())

142 return false;

143

144 BasicBlock *Succ0 = BI->getSuccessor(0);

145 BasicBlock *Succ1 = BI->getSuccessor(1);

146

148 return false;

150 return false;

151

154

155 if (!Succ0Succ || !Succ1Succ || Succ0Succ != Succ1Succ)

156 return false;

157 return true;

158}

159

160

161

162

163

164

165

166

167

168

169bool MergedLoadStoreMotion::isStoreSinkBarrierInRange(const Instruction &Start,

170 const Instruction &End,

171 MemoryLocation Loc) {

172 for (const Instruction &Inst :

174 if (Inst.mayThrow())

175 return true;

177}

178

179

180

181

182

183

184StoreInst *MergedLoadStoreMotion::canSinkFromBlock(BasicBlock *BB1,

185 StoreInst *Store0) {

188 for (Instruction &Inst : reverse(*BB1)) {

190 if (!Store1)

191 continue;

192

195

197 !isStoreSinkBarrierInRange(*Store1->getNextNode(), BB1->back(), Loc1) &&

198 !isStoreSinkBarrierInRange(*Store0->getNextNode(), BB0->back(), Loc0) &&

202 Store1->getValueOperand()->getType(),

204 return Store1;

205 }

206 return nullptr;

207}

208

209

210

211

212PHINode *MergedLoadStoreMotion::getPHIOperand(BasicBlock *BB, StoreInst *S0,

213 StoreInst *S1) {

214

216 Value *Opd2 = S1->getValueOperand();

217 if (Opd1 == Opd2)

218 return nullptr;

219

221 NewPN->insertBefore(BB->begin());

222 NewPN->applyMergedLocation(S0->getDebugLoc(), S1->getDebugLoc());

223 NewPN->addIncoming(Opd1, S0->getParent());

224 NewPN->addIncoming(Opd2, S1->getParent());

225 return NewPN;

226}

227

228

229

230

231bool MergedLoadStoreMotion::canSinkStoresAndGEPs(StoreInst *S0,

232 StoreInst *S1) const {

234 return true;

237 return GEP0 && GEP1 && GEP0->isIdenticalTo(GEP1) && GEP0->hasOneUse() &&

238 (GEP0->getParent() == S0->getParent()) && GEP1->hasOneUse() &&

239 (GEP1->getParent() == S1->getParent());

240}

241

242

243

244

245

246

247void MergedLoadStoreMotion::sinkStoresAndGEPs(BasicBlock *BB, StoreInst *S0,

248 StoreInst *S1) {

250 Value *Ptr1 = S1->getPointerOperand();

251

253 dbgs() << "Instruction Left\n"; S0->dump(); dbgs() << "\n";

254 dbgs() << "Instruction Right\n"; S1->dump(); dbgs() << "\n");

255

257

259

263

264

265

267 auto Cast = Builder.CreateBitOrPointerCast(S0->getValueOperand(),

268 S1->getValueOperand()->getType());

270

271

274

275 if (PHINode *NewPN = getPHIOperand(BB, S0, S1))

278 S1->eraseFromParent();

279

280 if (Ptr0 != Ptr1) {

287 GEP0->replaceAllUsesWith(GEPNew);

288 GEP0->eraseFromParent();

289 GEP1->replaceAllUsesWith(GEPNew);

290 GEP1->eraseFromParent();

291 }

292}

293

294

295

296

297

298

299

300bool MergedLoadStoreMotion::mergeStores(BasicBlock *HeadBB) {

301

302 bool MergedStores = false;

303 BasicBlock *TailBB = getDiamondTail(HeadBB);

305 assert(SinkBB && "Footer of a diamond cannot be empty");

306

308 assert(SI != succ_end(HeadBB) && "Diamond head cannot have zero successors");

310 ++SI;

311 assert(SI != succ_end(HeadBB) && "Diamond head cannot have single successor");

313

314 if (Pred0 == Pred1)

315 return false;

316

318 return false;

319

321 int Size1 = std::distance(InstsNoDbg.begin(), InstsNoDbg.end());

322 int NStores = 0;

323

325 RBI != RBE;) {

326

328 ++RBI;

329

330

333 continue;

334

335 ++NStores;

336 if (NStores * Size1 >= MagicCompileTimeControl)

337 break;

338 if (StoreInst *S1 = canSinkFromBlock(Pred1, S0)) {

339 if (!canSinkStoresAndGEPs(S0, S1))

340

341

342

343

344 break;

345

347

348

350 if (!SinkBB)

351 break;

352 }

353

354 MergedStores = true;

355 sinkStoresAndGEPs(SinkBB, S0, S1);

356 RBI = Pred0->rbegin();

357 RBE = Pred0->rend();

359 }

360 }

361 return MergedStores;

362}

363

364bool MergedLoadStoreMotion::run(Function &F, AliasAnalysis &AA) {

365 this->AA = &AA;

366

369

370

371

372

373

375

376

377 if (isDiamondHead(&BB))

378 Changed |= mergeStores(&BB);

380}

381

382PreservedAnalyses

384 MergedLoadStoreMotion Impl(Options.SplitFooterBB);

386 if (!Impl.run(F, AA))

388

390 if (!Options.SplitFooterBB)

392 return PA;

393}

394

398 OS, MapClassName2PassName);

399 OS << '<';

400 OS << (Options.SplitFooterBB ? "" : "no-") << "split-footer-bb";

401 OS << '>';

402}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This is the interface for a simple mod/ref and alias analysis over globals.

This pass performs merges of loads and stores on both sides of a.

A manager for alias analyses.

bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)

A trivial helper function to check to see if the specified pointers are must-alias.

LLVM_ABI bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, const MemoryLocation &Loc, const ModRefInfo Mode)

Check if it is possible for the execution of the specified instructions to mod(according to the mode)...

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

LLVM_ABI const_iterator getFirstInsertionPt() const

Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...

reverse_iterator rbegin()

LLVM_ABI iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const

Return a const iterator range over the instructions in the block, skipping any debug instructions.

const Instruction & back() const

LLVM_ABI const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor block.

InstListType::reverse_iterator reverse_iterator

LLVM_ABI const BasicBlock * getSingleSuccessor() const

Return the successor of this block if it has a single successor.

InstListType::iterator iterator

Instruction iterators...

LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const

Return true if this block has N predecessors or more.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Represents analyses that only rely on functions' control flow.

static LLVM_ABI bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)

Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.

LLVM_ABI Instruction * clone() const

Create a copy of 'this' instruction that is identical in all ways except the following:

LLVM_ABI void mergeDIAssignID(ArrayRef< const Instruction * > SourceInstructions)

Merge the DIAssignID metadata from this instruction and those attached to instructions in SourceInstr...

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI void andIRFlags(const Value *V)

Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.

LLVM_ABI bool hasSameSpecialState(const Instruction *I2, bool IgnoreAlignment=false, bool IntersectAttrs=false) const LLVM_READONLY

This function determines if the speficied instruction has the same "special" characteristics as the c...

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified position.

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)

Merge 2 debug locations and apply it to the Instruction.

LLVM_ABI const DataLayout & getDataLayout() const

Get the data layout of the module this instruction belongs to.

LLVM_DUMP_METHOD void dump() const

Representation for a specific memory location.

static LLVM_ABI MemoryLocation get(const LoadInst *LI)

Return a location with information about the memory reference by the given instruction.

void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)

Definition MergedLoadStoreMotion.cpp:395

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition MergedLoadStoreMotion.cpp:383

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserveSet()

Mark an analysis set as preserved.

An instruction for storing to memory.

Value * getValueOperand()

Value * getPointerOperand()

StringRef - Represent a constant reference to a string, i.e.

void setOperand(unsigned i, Value *Val)

Type * getType() const

All values are typed, get the type of this value.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

LLVM_ABI void dump() const

Support for debugging, callable in GDB: V->dump()

An efficient, type-erasing, non-owning reference to a callable.

const ParentTy * getParent() const

self_iterator getIterator()

NodeTy * getNextNode()

Get the next node, or nullptr for the list tail.

This class implements an extremely fast bulk output stream that can only output to a stream.

Abstract Attribute helper functions.

@ BasicBlock

Various leaf nodes.

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

auto reverse(ContainerTy &&C)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)

LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)

Combine the metadata of two instructions so that K can replace J.

LLVM_ABI BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)

This method introduces at least one new basic block into the function and moves some of the predecess...

IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >

RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

SuccIterator< Instruction, BasicBlock > succ_iterator

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

AAResults AliasAnalysis

Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.

A CRTP mix-in to automatically provide informational APIs needed for passes.