Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/LoopVersioning.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LoopVersioning.cpp - Utility to version a loop ---------------------===//
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
// This file defines a utility class to perform loop versioning.  The versioned
10
// loop speculates that otherwise may-aliasing memory accesses don't overlap and
11
// emits checks to prove this.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "llvm/Transforms/Utils/LoopVersioning.h"
16
#include "llvm/Analysis/LoopAccessAnalysis.h"
17
#include "llvm/Analysis/LoopInfo.h"
18
#include "llvm/Analysis/ScalarEvolutionExpander.h"
19
#include "llvm/IR/Dominators.h"
20
#include "llvm/IR/MDBuilder.h"
21
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
22
#include "llvm/Transforms/Utils/Cloning.h"
23
24
using namespace llvm;
25
26
static cl::opt<bool>
27
    AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),
28
                    cl::Hidden,
29
                    cl::desc("Add no-alias annotation for instructions that "
30
                             "are disambiguated by memchecks"));
31
32
LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
33
                               DominatorTree *DT, ScalarEvolution *SE,
34
                               bool UseLAIChecks)
35
    : VersionedLoop(L), NonVersionedLoop(nullptr), LAI(LAI), LI(LI), DT(DT),
36
2.53k
      SE(SE) {
37
2.53k
  assert(L->getExitBlock() && "No single exit block");
38
2.53k
  assert(L->isLoopSimplifyForm() && "Loop is not in loop-simplify form");
39
2.53k
  if (UseLAIChecks) {
40
2.50k
    setAliasChecks(LAI.getRuntimePointerChecking()->getChecks());
41
2.50k
    setSCEVChecks(LAI.getPSE().getUnionPredicate());
42
2.50k
  }
43
2.53k
}
44
45
void LoopVersioning::setAliasChecks(
46
2.53k
    SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks) {
47
2.53k
  AliasChecks = std::move(Checks);
48
2.53k
}
49
50
2.53k
void LoopVersioning::setSCEVChecks(SCEVUnionPredicate Check) {
51
2.53k
  Preds = std::move(Check);
52
2.53k
}
53
54
void LoopVersioning::versionLoop(
55
47
    const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
56
47
  Instruction *FirstCheckInst;
57
47
  Instruction *MemRuntimeCheck;
58
47
  Value *SCEVRuntimeCheck;
59
47
  Value *RuntimeCheck = nullptr;
60
47
61
47
  // Add the memcheck in the original preheader (this is empty initially).
62
47
  BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader();
63
47
  std::tie(FirstCheckInst, MemRuntimeCheck) =
64
47
      LAI.addRuntimeChecks(RuntimeCheckBB->getTerminator(), AliasChecks);
65
47
66
47
  const SCEVUnionPredicate &Pred = LAI.getPSE().getUnionPredicate();
67
47
  SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
68
47
                   "scev.check");
69
47
  SCEVRuntimeCheck =
70
47
      Exp.expandCodeForPredicate(&Pred, RuntimeCheckBB->getTerminator());
71
47
  auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck);
72
47
73
47
  // Discard the SCEV runtime check if it is always true.
74
47
  if (CI && 
CI->isZero()29
)
75
29
    SCEVRuntimeCheck = nullptr;
76
47
77
47
  if (MemRuntimeCheck && 
SCEVRuntimeCheck31
) {
78
2
    RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck,
79
2
                                          SCEVRuntimeCheck, "lver.safe");
80
2
    if (auto *I = dyn_cast<Instruction>(RuntimeCheck))
81
2
      I->insertBefore(RuntimeCheckBB->getTerminator());
82
2
  } else
83
45
    RuntimeCheck = MemRuntimeCheck ? 
MemRuntimeCheck29
:
SCEVRuntimeCheck16
;
84
47
85
47
  assert(RuntimeCheck && "called even though we don't need "
86
47
                         "any runtime checks");
87
47
88
47
  // Rename the block to make the IR more readable.
89
47
  RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +
90
47
                          ".lver.check");
91
47
92
47
  // Create empty preheader for the loop (and after cloning for the
93
47
  // non-versioned loop).
94
47
  BasicBlock *PH =
95
47
      SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI);
96
47
  PH->setName(VersionedLoop->getHeader()->getName() + ".ph");
97
47
98
47
  // Clone the loop including the preheader.
99
47
  //
100
47
  // FIXME: This does not currently preserve SimplifyLoop because the exit
101
47
  // block is a join between the two loops.
102
47
  SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
103
47
  NonVersionedLoop =
104
47
      cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
105
47
                             ".lver.orig", LI, DT, NonVersionedLoopBlocks);
106
47
  remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
107
47
108
47
  // Insert the conditional branch based on the result of the memchecks.
109
47
  Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
110
47
  BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
111
47
                     VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm);
112
47
  OrigTerm->eraseFromParent();
113
47
114
47
  // The loops merge in the original exit block.  This is now dominated by the
115
47
  // memchecking block.
116
47
  DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
117
47
118
47
  // Adds the necessary PHI nodes for the versioned loops based on the
119
47
  // loop-defined values used outside of the loop.
120
47
  addPHINodes(DefsUsedOutside);
121
47
}
122
123
void LoopVersioning::addPHINodes(
124
47
    const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
125
47
  BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
126
47
  assert(PHIBlock && "No single successor to loop exit block");
127
47
  PHINode *PN;
128
47
129
47
  // First add a single-operand PHI for each DefsUsedOutside if one does not
130
47
  // exists yet.
131
47
  for (auto *Inst : DefsUsedOutside) {
132
34
    // See if we have a single-operand PHI with the value defined by the
133
34
    // original loop.
134
108
    for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); 
++I74
) {
135
106
      if (PN->getIncomingValue(0) == Inst)
136
32
        break;
137
106
    }
138
34
    // If not create it.
139
34
    if (!PN) {
140
2
      PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
141
2
                           &PHIBlock->front());
142
2
      SmallVector<User*, 8> UsersToUpdate;
143
2
      for (User *U : Inst->users())
144
5
        if (!VersionedLoop->contains(cast<Instruction>(U)->getParent()))
145
3
          UsersToUpdate.push_back(U);
146
2
      for (User *U : UsersToUpdate)
147
3
        U->replaceUsesOfWith(Inst, PN);
148
2
      PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
149
2
    }
150
34
  }
151
47
152
47
  // Then for each PHI add the operand for the edge from the cloned loop.
153
84
  for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); 
++I37
) {
154
37
    assert(PN->getNumOperands() == 1 &&
155
37
           "Exit block should only have on predecessor");
156
37
157
37
    // If the definition was cloned used that otherwise use the same value.
158
37
    Value *ClonedValue = PN->getIncomingValue(0);
159
37
    auto Mapped = VMap.find(ClonedValue);
160
37
    if (Mapped != VMap.end())
161
35
      ClonedValue = Mapped->second;
162
37
163
37
    PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());
164
37
  }
165
47
}
166
167
2.52k
void LoopVersioning::prepareNoAliasMetadata() {
168
2.52k
  // We need to turn the no-alias relation between pointer checking groups into
169
2.52k
  // no-aliasing annotations between instructions.
170
2.52k
  //
171
2.52k
  // We accomplish this by mapping each pointer checking group (a set of
172
2.52k
  // pointers memchecked together) to an alias scope and then also mapping each
173
2.52k
  // group to the list of scopes it can't alias.
174
2.52k
175
2.52k
  const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking();
176
2.52k
  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
177
2.52k
178
2.52k
  // First allocate an aliasing scope for each pointer checking group.
179
2.52k
  //
180
2.52k
  // While traversing through the checking groups in the loop, also create a
181
2.52k
  // reverse map from pointers to the pointer checking group they were assigned
182
2.52k
  // to.
183
2.52k
  MDBuilder MDB(Context);
184
2.52k
  MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");
185
2.52k
186
5.79k
  for (const auto &Group : RtPtrChecking->CheckingGroups) {
187
5.79k
    GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
188
5.79k
189
5.79k
    for (unsigned PtrIdx : Group.Members)
190
6.75k
      PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;
191
5.79k
  }
192
2.52k
193
2.52k
  // Go through the checks and for each pointer group, collect the scopes for
194
2.52k
  // each non-aliasing pointer group.
195
2.52k
  DenseMap<const RuntimePointerChecking::CheckingPtrGroup *,
196
2.52k
           SmallVector<Metadata *, 4>>
197
2.52k
      GroupToNonAliasingScopes;
198
2.52k
199
2.52k
  for (const auto &Check : AliasChecks)
200
3.40k
    GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);
201
2.52k
202
2.52k
  // Finally, transform the above to actually map to scope list which is what
203
2.52k
  // the metadata uses.
204
2.52k
205
2.52k
  for (auto Pair : GroupToNonAliasingScopes)
206
2.67k
    GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);
207
2.52k
}
208
209
33
void LoopVersioning::annotateLoopWithNoAlias() {
210
33
  if (!AnnotateNoAlias)
211
0
    return;
212
33
213
33
  // First prepare the maps.
214
33
  prepareNoAliasMetadata();
215
33
216
33
  // Add the scope and no-alias metadata to the instructions.
217
133
  for (Instruction *I : LAI.getDepChecker().getMemoryInstructions()) {
218
133
    annotateInstWithNoAlias(I);
219
133
  }
220
33
}
221
222
void LoopVersioning::annotateInstWithNoAlias(Instruction *VersionedInst,
223
12.1k
                                             const Instruction *OrigInst) {
224
12.1k
  if (!AnnotateNoAlias)
225
0
    return;
226
12.1k
227
12.1k
  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
228
12.1k
  const Value *Ptr = isa<LoadInst>(OrigInst)
229
12.1k
                         ? 
cast<LoadInst>(OrigInst)->getPointerOperand()6.96k
230
12.1k
                         : 
cast<StoreInst>(OrigInst)->getPointerOperand()5.15k
;
231
12.1k
232
12.1k
  // Find the group for the pointer and then add the scope metadata.
233
12.1k
  auto Group = PtrToGroup.find(Ptr);
234
12.1k
  if (Group != PtrToGroup.end()) {
235
12.0k
    VersionedInst->setMetadata(
236
12.0k
        LLVMContext::MD_alias_scope,
237
12.0k
        MDNode::concatenate(
238
12.0k
            VersionedInst->getMetadata(LLVMContext::MD_alias_scope),
239
12.0k
            MDNode::get(Context, GroupToScope[Group->second])));
240
12.0k
241
12.0k
    // Add the no-alias metadata.
242
12.0k
    auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);
243
12.0k
    if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())
244
5.42k
      VersionedInst->setMetadata(
245
5.42k
          LLVMContext::MD_noalias,
246
5.42k
          MDNode::concatenate(
247
5.42k
              VersionedInst->getMetadata(LLVMContext::MD_noalias),
248
5.42k
              NonAliasingScopeList->second));
249
12.0k
  }
250
12.1k
}
251
252
namespace {
253
/// Also expose this is a pass.  Currently this is only used for
254
/// unit-testing.  It adds all memchecks necessary to remove all may-aliasing
255
/// array accesses from the loop.
256
class LoopVersioningPass : public FunctionPass {
257
public:
258
13
  LoopVersioningPass() : FunctionPass(ID) {
259
13
    initializeLoopVersioningPassPass(*PassRegistry::getPassRegistry());
260
13
  }
261
262
19
  bool runOnFunction(Function &F) override {
263
19
    auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
264
19
    auto *LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
265
19
    auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
266
19
    auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
267
19
268
19
    // Build up a worklist of inner-loops to version. This is necessary as the
269
19
    // act of versioning a loop creates new loops and can invalidate iterators
270
19
    // across the loops.
271
19
    SmallVector<Loop *, 8> Worklist;
272
19
273
19
    for (Loop *TopLevelLoop : *LI)
274
21
      for (Loop *L : depth_first(TopLevelLoop))
275
24
        // We only handle inner-most loops.
276
24
        if (L->empty())
277
21
          Worklist.push_back(L);
278
19
279
19
    // Now walk the identified inner loops.
280
19
    bool Changed = false;
281
21
    for (Loop *L : Worklist) {
282
21
      const LoopAccessInfo &LAI = LAA->getInfo(L);
283
21
      if (L->isLoopSimplifyForm() && 
!LAI.hasConvergentOp()20
&&
284
21
          
(19
LAI.getNumRuntimePointerChecks()19
||
285
19
           
!LAI.getPSE().getUnionPredicate().isAlwaysTrue()7
)) {
286
19
        LoopVersioning LVer(LAI, L, LI, DT, SE);
287
19
        LVer.versionLoop();
288
19
        LVer.annotateLoopWithNoAlias();
289
19
        Changed = true;
290
19
      }
291
21
    }
292
19
293
19
    return Changed;
294
19
  }
295
296
13
  void getAnalysisUsage(AnalysisUsage &AU) const override {
297
13
    AU.addRequired<LoopInfoWrapperPass>();
298
13
    AU.addPreserved<LoopInfoWrapperPass>();
299
13
    AU.addRequired<LoopAccessLegacyAnalysis>();
300
13
    AU.addRequired<DominatorTreeWrapperPass>();
301
13
    AU.addPreserved<DominatorTreeWrapperPass>();
302
13
    AU.addRequired<ScalarEvolutionWrapperPass>();
303
13
  }
304
305
  static char ID;
306
};
307
}
308
309
#define LVER_OPTION "loop-versioning"
310
#define DEBUG_TYPE LVER_OPTION
311
312
char LoopVersioningPass::ID;
313
static const char LVer_name[] = "Loop Versioning";
314
315
36.0k
INITIALIZE_PASS_BEGIN(LoopVersioningPass, LVER_OPTION, LVer_name, false, false)
316
36.0k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
317
36.0k
INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
318
36.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
319
36.0k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
320
36.0k
INITIALIZE_PASS_END(LoopVersioningPass, LVER_OPTION, LVer_name, false, false)
321
322
namespace llvm {
323
0
FunctionPass *createLoopVersioningPass() {
324
0
  return new LoopVersioningPass();
325
0
}
326
}