Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- MergedLoadStoreMotion.cpp - merge and hoist/sink load/stores -------===//
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-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
//! \file
10
//! This pass performs merges of loads and stores on both sides of a
11
//  diamond (hammock). It hoists the loads and sinks the stores.
12
//
13
// The algorithm iteratively hoists two loads to the same address out of a
14
// diamond (hammock) and merges them into a single load in the header. Similar
15
// it sinks and merges two stores to the tail block (footer). The algorithm
16
// iterates over the instructions of one side of the diamond and attempts to
17
// find a matching load/store on the other side. It hoists / sinks when it
18
// thinks it safe to do so.  This optimization helps with eg. hiding load
19
// latencies, triggering if-conversion, and reducing static code size.
20
//
21
// NOTE: This code no longer performs load hoisting, it is subsumed by GVNHoist.
22
//
23
//===----------------------------------------------------------------------===//
24
//
25
//
26
// Example:
27
// Diamond shaped code before merge:
28
//
29
//            header:
30
//                     br %cond, label %if.then, label %if.else
31
//                        +                    +
32
//                       +                      +
33
//                      +                        +
34
//            if.then:                         if.else:
35
//               %lt = load %addr_l               %le = load %addr_l
36
//               <use %lt>                        <use %le>
37
//               <...>                            <...>
38
//               store %st, %addr_s               store %se, %addr_s
39
//               br label %if.end                 br label %if.end
40
//                     +                         +
41
//                      +                       +
42
//                       +                     +
43
//            if.end ("footer"):
44
//                     <...>
45
//
46
// Diamond shaped code after merge:
47
//
48
//            header:
49
//                     %l = load %addr_l
50
//                     br %cond, label %if.then, label %if.else
51
//                        +                    +
52
//                       +                      +
53
//                      +                        +
54
//            if.then:                         if.else:
55
//               <use %l>                         <use %l>
56
//               <...>                            <...>
57
//               br label %if.end                 br label %if.end
58
//                      +                        +
59
//                       +                      +
60
//                        +                    +
61
//            if.end ("footer"):
62
//                     %s.sink = phi [%st, if.then], [%se, if.else]
63
//                     <...>
64
//                     store %s.sink, %addr_s
65
//                     <...>
66
//
67
//
68
//===----------------------- TODO -----------------------------------------===//
69
//
70
// 1) Generalize to regions other than diamonds
71
// 2) Be more aggressive merging memory operations
72
// Note that both changes require register pressure control
73
//
74
//===----------------------------------------------------------------------===//
75
76
#include "llvm/Transforms/Scalar/MergedLoadStoreMotion.h"
77
#include "llvm/ADT/Statistic.h"
78
#include "llvm/Analysis/AliasAnalysis.h"
79
#include "llvm/Analysis/CFG.h"
80
#include "llvm/Analysis/GlobalsModRef.h"
81
#include "llvm/Analysis/Loads.h"
82
#include "llvm/Analysis/ValueTracking.h"
83
#include "llvm/IR/Metadata.h"
84
#include "llvm/Support/Debug.h"
85
#include "llvm/Support/raw_ostream.h"
86
#include "llvm/Transforms/Scalar.h"
87
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
88
89
using namespace llvm;
90
91
#define DEBUG_TYPE "mldst-motion"
92
93
namespace {
94
//===----------------------------------------------------------------------===//
95
//                         MergedLoadStoreMotion Pass
96
//===----------------------------------------------------------------------===//
97
class MergedLoadStoreMotion {
98
  AliasAnalysis *AA = nullptr;
99
100
  // The mergeLoad/Store algorithms could have Size0 * Size1 complexity,
101
  // where Size0 and Size1 are the #instructions on the two sides of
102
  // the diamond. The constant chosen here is arbitrary. Compiler Time
103
  // Control is enforced by the check Size0 * Size1 < MagicCompileTimeControl.
104
  const int MagicCompileTimeControl = 250;
105
106
public:
107
  bool run(Function &F, AliasAnalysis &AA);
108
109
private:
110
  BasicBlock *getDiamondTail(BasicBlock *BB);
111
  bool isDiamondHead(BasicBlock *BB);
112
  // Routines for sinking stores
113
  StoreInst *canSinkFromBlock(BasicBlock *BB, StoreInst *SI);
114
  PHINode *getPHIOperand(BasicBlock *BB, StoreInst *S0, StoreInst *S1);
115
  bool isStoreSinkBarrierInRange(const Instruction &Start,
116
                                 const Instruction &End, MemoryLocation Loc);
117
  bool sinkStore(BasicBlock *BB, StoreInst *SinkCand, StoreInst *ElseInst);
118
  bool mergeStores(BasicBlock *BB);
119
};
120
} // end anonymous namespace
121
122
///
123
/// Return tail block of a diamond.
124
///
125
44.3k
BasicBlock *MergedLoadStoreMotion::getDiamondTail(BasicBlock *BB) {
126
44.3k
  assert(isDiamondHead(BB) && "Basic block is not head of a diamond");
127
44.3k
  return BB->getTerminator()->getSuccessor(0)->getSingleSuccessor();
128
44.3k
}
129
130
///
131
/// True when BB is the head of a diamond (hammock)
132
///
133
2.91M
bool MergedLoadStoreMotion::isDiamondHead(BasicBlock *BB) {
134
2.91M
  if (!BB)
135
0
    return false;
136
2.91M
  auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
137
2.91M
  if (!BI || 
!BI->isConditional()2.33M
)
138
1.64M
    return false;
139
1.26M
140
1.26M
  BasicBlock *Succ0 = BI->getSuccessor(0);
141
1.26M
  BasicBlock *Succ1 = BI->getSuccessor(1);
142
1.26M
143
1.26M
  if (!Succ0->getSinglePredecessor())
144
541k
    return false;
145
727k
  if (!Succ1->getSinglePredecessor())
146
426k
    return false;
147
301k
148
301k
  BasicBlock *Succ0Succ = Succ0->getSingleSuccessor();
149
301k
  BasicBlock *Succ1Succ = Succ1->getSingleSuccessor();
150
301k
  // Ignore triangles.
151
301k
  if (!Succ0Succ || 
!Succ1Succ176k
||
Succ0Succ != Succ1Succ61.2k
)
152
256k
    return false;
153
44.3k
  return true;
154
44.3k
}
155
156
157
///
158
/// True when instruction is a sink barrier for a store
159
/// located in Loc
160
///
161
/// Whenever an instruction could possibly read or modify the
162
/// value being stored or protect against the store from
163
/// happening it is considered a sink barrier.
164
///
165
bool MergedLoadStoreMotion::isStoreSinkBarrierInRange(const Instruction &Start,
166
                                                      const Instruction &End,
167
4.68k
                                                      MemoryLocation Loc) {
168
4.68k
  for (const Instruction &Inst :
169
4.68k
       make_range(Start.getIterator(), End.getIterator()))
170
13.3k
    if (Inst.mayThrow())
171
13
      return true;
172
4.68k
  
return AA->canInstructionRangeModRef(Start, End, Loc, ModRefInfo::ModRef)4.66k
;
173
4.68k
}
174
175
///
176
/// Check if \p BB contains a store to the same address as \p SI
177
///
178
/// \return The store in \p  when it is safe to sink. Otherwise return Null.
179
///
180
StoreInst *MergedLoadStoreMotion::canSinkFromBlock(BasicBlock *BB1,
181
14.2k
                                                   StoreInst *Store0) {
182
14.2k
  LLVM_DEBUG(dbgs() << "can Sink? : "; Store0->dump(); dbgs() << "\n");
183
14.2k
  BasicBlock *BB0 = Store0->getParent();
184
69.3k
  for (Instruction &Inst : reverse(*BB1)) {
185
69.3k
    auto *Store1 = dyn_cast<StoreInst>(&Inst);
186
69.3k
    if (!Store1)
187
56.1k
      continue;
188
13.1k
189
13.1k
    MemoryLocation Loc0 = MemoryLocation::get(Store0);
190
13.1k
    MemoryLocation Loc1 = MemoryLocation::get(Store1);
191
13.1k
    if (AA->isMustAlias(Loc0, Loc1) && 
Store0->isSameOperationAs(Store1)3.09k
&&
192
13.1k
        
!isStoreSinkBarrierInRange(*Store1->getNextNode(), BB1->back(), Loc1)2.75k
&&
193
13.1k
        
!isStoreSinkBarrierInRange(*Store0->getNextNode(), BB0->back(), Loc0)1.92k
) {
194
1.77k
      return Store1;
195
1.77k
    }
196
13.1k
  }
197
14.2k
  
return nullptr12.4k
;
198
14.2k
}
199
200
///
201
/// Create a PHI node in BB for the operands of S0 and S1
202
///
203
PHINode *MergedLoadStoreMotion::getPHIOperand(BasicBlock *BB, StoreInst *S0,
204
751
                                              StoreInst *S1) {
205
751
  // Create a phi if the values mismatch.
206
751
  Value *Opd1 = S0->getValueOperand();
207
751
  Value *Opd2 = S1->getValueOperand();
208
751
  if (Opd1 == Opd2)
209
85
    return nullptr;
210
666
211
666
  auto *NewPN = PHINode::Create(Opd1->getType(), 2, Opd2->getName() + ".sink",
212
666
                                &BB->front());
213
666
  NewPN->applyMergedLocation(S0->getDebugLoc(), S1->getDebugLoc());
214
666
  NewPN->addIncoming(Opd1, S0->getParent());
215
666
  NewPN->addIncoming(Opd2, S1->getParent());
216
666
  return NewPN;
217
666
}
218
219
///
220
/// Merge two stores to same address and sink into \p BB
221
///
222
/// Also sinks GEP instruction computing the store address
223
///
224
bool MergedLoadStoreMotion::sinkStore(BasicBlock *BB, StoreInst *S0,
225
1.77k
                                      StoreInst *S1) {
226
1.77k
  // Only one definition?
227
1.77k
  auto *A0 = dyn_cast<Instruction>(S0->getPointerOperand());
228
1.77k
  auto *A1 = dyn_cast<Instruction>(S1->getPointerOperand());
229
1.77k
  if (A0 && 
A11.69k
&&
A0->isIdenticalTo(A1)1.69k
&&
A0->hasOneUse()1.63k
&&
230
1.77k
      
(A0->getParent() == S0->getParent())925
&&
A1->hasOneUse()902
&&
231
1.77k
      
(A1->getParent() == S1->getParent())846
&&
isa<GetElementPtrInst>(A0)846
) {
232
751
    LLVM_DEBUG(dbgs() << "Sink Instruction into BB \n"; BB->dump();
233
751
               dbgs() << "Instruction Left\n"; S0->dump(); dbgs() << "\n";
234
751
               dbgs() << "Instruction Right\n"; S1->dump(); dbgs() << "\n");
235
751
    // Hoist the instruction.
236
751
    BasicBlock::iterator InsertPt = BB->getFirstInsertionPt();
237
751
    // Intersect optional metadata.
238
751
    S0->andIRFlags(S1);
239
751
    S0->dropUnknownNonDebugMetadata();
240
751
241
751
    // Create the new store to be inserted at the join point.
242
751
    StoreInst *SNew = cast<StoreInst>(S0->clone());
243
751
    Instruction *ANew = A0->clone();
244
751
    SNew->insertBefore(&*InsertPt);
245
751
    ANew->insertBefore(SNew);
246
751
247
751
    assert(S0->getParent() == A0->getParent());
248
751
    assert(S1->getParent() == A1->getParent());
249
751
250
751
    // New PHI operand? Use it.
251
751
    if (PHINode *NewPN = getPHIOperand(BB, S0, S1))
252
666
      SNew->setOperand(0, NewPN);
253
751
    S0->eraseFromParent();
254
751
    S1->eraseFromParent();
255
751
    A0->replaceAllUsesWith(ANew);
256
751
    A0->eraseFromParent();
257
751
    A1->replaceAllUsesWith(ANew);
258
751
    A1->eraseFromParent();
259
751
    return true;
260
751
  }
261
1.02k
  return false;
262
1.02k
}
263
264
///
265
/// True when two stores are equivalent and can sink into the footer
266
///
267
/// Starting from a diamond tail block, iterate over the instructions in one
268
/// predecessor block and try to match a store in the second predecessor.
269
///
270
44.3k
bool MergedLoadStoreMotion::mergeStores(BasicBlock *T) {
271
44.3k
272
44.3k
  bool MergedStores = false;
273
44.3k
  assert(T && "Footer of a diamond cannot be empty");
274
44.3k
275
44.3k
  pred_iterator PI = pred_begin(T), E = pred_end(T);
276
44.3k
  assert(PI != E);
277
44.3k
  BasicBlock *Pred0 = *PI;
278
44.3k
  ++PI;
279
44.3k
  BasicBlock *Pred1 = *PI;
280
44.3k
  ++PI;
281
44.3k
  // tail block  of a diamond/hammock?
282
44.3k
  if (Pred0 == Pred1)
283
10
    return false; // No.
284
44.3k
  if (PI != E)
285
19.9k
    return false; // No. More than 2 predecessors.
286
24.3k
287
24.3k
  // #Instructions in Succ1 for Compile Time Control
288
24.3k
  auto InstsNoDbg = Pred1->instructionsWithoutDebug();
289
24.3k
  int Size1 = std::distance(InstsNoDbg.begin(), InstsNoDbg.end());
290
24.3k
  int NStores = 0;
291
24.3k
292
24.3k
  for (BasicBlock::reverse_iterator RBI = Pred0->rbegin(), RBE = Pred0->rend();
293
161k
       RBI != RBE;) {
294
138k
295
138k
    Instruction *I = &*RBI;
296
138k
    ++RBI;
297
138k
298
138k
    // Don't sink non-simple (atomic, volatile) stores.
299
138k
    auto *S0 = dyn_cast<StoreInst>(I);
300
138k
    if (!S0 || 
!S0->isSimple()14.3k
)
301
123k
      continue;
302
14.3k
303
14.3k
    ++NStores;
304
14.3k
    if (NStores * Size1 >= MagicCompileTimeControl)
305
59
      break;
306
14.2k
    if (StoreInst *S1 = canSinkFromBlock(Pred1, S0)) {
307
1.77k
      bool Res = sinkStore(T, S0, S1);
308
1.77k
      MergedStores |= Res;
309
1.77k
      // Don't attempt to sink below stores that had to stick around
310
1.77k
      // But after removal of a store and some of its feeding
311
1.77k
      // instruction search again from the beginning since the iterator
312
1.77k
      // is likely stale at this point.
313
1.77k
      if (!Res)
314
1.02k
        break;
315
751
      RBI = Pred0->rbegin();
316
751
      RBE = Pred0->rend();
317
751
      LLVM_DEBUG(dbgs() << "Search again\n"; Instruction *I = &*RBI; I->dump());
318
751
    }
319
14.2k
  }
320
24.3k
  return MergedStores;
321
24.3k
}
322
323
464k
bool MergedLoadStoreMotion::run(Function &F, AliasAnalysis &AA) {
324
464k
  this->AA = &AA;
325
464k
326
464k
  bool Changed = false;
327
464k
  LLVM_DEBUG(dbgs() << "Instruction Merger\n");
328
464k
329
464k
  // Merge unconditional branches, allowing PRE to catch more
330
464k
  // optimization opportunities.
331
3.37M
  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
332
2.91M
    BasicBlock *BB = &*FI++;
333
2.91M
334
2.91M
    // Hoist equivalent loads and sink stores
335
2.91M
    // outside diamonds when possible
336
2.91M
    if (isDiamondHead(BB)) {
337
44.3k
      Changed |= mergeStores(getDiamondTail(BB));
338
44.3k
    }
339
2.91M
  }
340
464k
  return Changed;
341
464k
}
342
343
namespace {
344
class MergedLoadStoreMotionLegacyPass : public FunctionPass {
345
public:
346
  static char ID; // Pass identification, replacement for typeid
347
13.2k
  MergedLoadStoreMotionLegacyPass() : FunctionPass(ID) {
348
13.2k
    initializeMergedLoadStoreMotionLegacyPassPass(
349
13.2k
        *PassRegistry::getPassRegistry());
350
13.2k
  }
351
352
  ///
353
  /// Run the transformation for each function
354
  ///
355
463k
  bool runOnFunction(Function &F) override {
356
463k
    if (skipFunction(F))
357
43
      return false;
358
463k
    MergedLoadStoreMotion Impl;
359
463k
    return Impl.run(F, getAnalysis<AAResultsWrapperPass>().getAAResults());
360
463k
  }
361
362
private:
363
13.2k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
364
13.2k
    AU.setPreservesCFG();
365
13.2k
    AU.addRequired<AAResultsWrapperPass>();
366
13.2k
    AU.addPreserved<GlobalsAAWrapperPass>();
367
13.2k
  }
368
};
369
370
char MergedLoadStoreMotionLegacyPass::ID = 0;
371
} // anonymous namespace
372
373
///
374
/// createMergedLoadStoreMotionPass - The public interface to this file.
375
///
376
13.2k
FunctionPass *llvm::createMergedLoadStoreMotionPass() {
377
13.2k
  return new MergedLoadStoreMotionLegacyPass();
378
13.2k
}
379
380
48.8k
INITIALIZE_PASS_BEGIN(MergedLoadStoreMotionLegacyPass, "mldst-motion",
381
48.8k
                      "MergedLoadStoreMotion", false, false)
382
48.8k
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
383
48.8k
INITIALIZE_PASS_END(MergedLoadStoreMotionLegacyPass, "mldst-motion",
384
                    "MergedLoadStoreMotion", false, false)
385
386
PreservedAnalyses
387
707
MergedLoadStoreMotionPass::run(Function &F, FunctionAnalysisManager &AM) {
388
707
  MergedLoadStoreMotion Impl;
389
707
  auto &AA = AM.getResult<AAManager>(F);
390
707
  if (!Impl.run(F, AA))
391
707
    return PreservedAnalyses::all();
392
0
393
0
  PreservedAnalyses PA;
394
0
  PA.preserveSet<CFGAnalyses>();
395
0
  PA.preserve<GlobalsAA>();
396
0
  return PA;
397
0
}