Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/LoopUtils.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
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 common loop utility functions.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/Transforms/Utils/LoopUtils.h"
14
#include "llvm/ADT/ScopeExit.h"
15
#include "llvm/Analysis/AliasAnalysis.h"
16
#include "llvm/Analysis/BasicAliasAnalysis.h"
17
#include "llvm/Analysis/DomTreeUpdater.h"
18
#include "llvm/Analysis/GlobalsModRef.h"
19
#include "llvm/Analysis/InstructionSimplify.h"
20
#include "llvm/Analysis/LoopInfo.h"
21
#include "llvm/Analysis/LoopPass.h"
22
#include "llvm/Analysis/MemorySSAUpdater.h"
23
#include "llvm/Analysis/MustExecute.h"
24
#include "llvm/Analysis/ScalarEvolution.h"
25
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
26
#include "llvm/Analysis/ScalarEvolutionExpander.h"
27
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
28
#include "llvm/Analysis/TargetTransformInfo.h"
29
#include "llvm/Analysis/ValueTracking.h"
30
#include "llvm/IR/DIBuilder.h"
31
#include "llvm/IR/Dominators.h"
32
#include "llvm/IR/Instructions.h"
33
#include "llvm/IR/IntrinsicInst.h"
34
#include "llvm/IR/Module.h"
35
#include "llvm/IR/PatternMatch.h"
36
#include "llvm/IR/ValueHandle.h"
37
#include "llvm/Pass.h"
38
#include "llvm/Support/Debug.h"
39
#include "llvm/Support/KnownBits.h"
40
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
41
42
using namespace llvm;
43
using namespace llvm::PatternMatch;
44
45
#define DEBUG_TYPE "loop-utils"
46
47
static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
48
49
bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
50
                                   MemorySSAUpdater *MSSAU,
51
1.97M
                                   bool PreserveLCSSA) {
52
1.97M
  bool Changed = false;
53
1.97M
54
1.97M
  // We re-use a vector for the in-loop predecesosrs.
55
1.97M
  SmallVector<BasicBlock *, 4> InLoopPredecessors;
56
1.97M
57
2.55M
  auto RewriteExit = [&](BasicBlock *BB) {
58
2.55M
    assert(InLoopPredecessors.empty() &&
59
2.55M
           "Must start with an empty predecessors list!");
60
2.55M
    auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });
61
2.55M
62
2.55M
    // See if there are any non-loop predecessors of this exit block and
63
2.55M
    // keep track of the in-loop predecessors.
64
2.55M
    bool IsDedicatedExit = true;
65
2.55M
    for (auto *PredBB : predecessors(BB))
66
8.05M
      if (L->contains(PredBB)) {
67
2.85M
        if (isa<IndirectBrInst>(PredBB->getTerminator()))
68
467
          // We cannot rewrite exiting edges from an indirectbr.
69
467
          return false;
70
2.85M
        if (isa<CallBrInst>(PredBB->getTerminator()))
71
12
          // We cannot rewrite exiting edges from a callbr.
72
12
          return false;
73
2.85M
74
2.85M
        InLoopPredecessors.push_back(PredBB);
75
5.20M
      } else {
76
5.20M
        IsDedicatedExit = false;
77
5.20M
      }
78
2.55M
79
2.55M
    assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
80
2.55M
81
2.55M
    // Nothing to do if this is already a dedicated exit.
82
2.55M
    if (IsDedicatedExit)
83
1.77M
      return false;
84
773k
85
773k
    auto *NewExitBB = SplitBlockPredecessors(
86
773k
        BB, InLoopPredecessors, ".loopexit", DT, LI, MSSAU, PreserveLCSSA);
87
773k
88
773k
    if (!NewExitBB)
89
773k
      LLVM_DEBUG(
90
773k
          dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
91
773k
                 << *L << "\n");
92
773k
    else
93
773k
      LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
94
773k
                        << NewExitBB->getName() << "\n");
95
773k
    return true;
96
773k
  };
97
1.97M
98
1.97M
  // Walk the exit blocks directly rather than building up a data structure for
99
1.97M
  // them, but only visit each one once.
100
1.97M
  SmallPtrSet<BasicBlock *, 4> Visited;
101
1.97M
  for (auto *BB : L->blocks())
102
15.3M
    
for (auto *SuccBB : successors(BB))9.05M
{
103
15.3M
      // We're looking for exit blocks so skip in-loop successors.
104
15.3M
      if (L->contains(SuccBB))
105
12.6M
        continue;
106
2.73M
107
2.73M
      // Visit each exit block exactly once.
108
2.73M
      if (!Visited.insert(SuccBB).second)
109
185k
        continue;
110
2.55M
111
2.55M
      Changed |= RewriteExit(SuccBB);
112
2.55M
    }
113
1.97M
114
1.97M
  return Changed;
115
1.97M
}
116
117
/// Returns the instructions that use values defined in the loop.
118
74
SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
119
74
  SmallVector<Instruction *, 8> UsedOutside;
120
74
121
74
  for (auto *Block : L->getBlocks())
122
132
    // FIXME: I believe that this could use copy_if if the Inst reference could
123
132
    // be adapted into a pointer.
124
1.97k
    
for (auto &Inst : *Block)132
{
125
1.97k
      auto Users = Inst.users();
126
2.74k
      if (
any_of(Users, [&](User *U) 1.97k
{
127
2.74k
            auto *Use = cast<Instruction>(U);
128
2.74k
            return !L->contains(Use->getParent());
129
2.74k
          }))
130
34
        UsedOutside.push_back(&Inst);
131
1.97k
    }
132
74
133
74
  return UsedOutside;
134
74
}
135
136
162k
void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
137
162k
  // By definition, all loop passes need the LoopInfo analysis and the
138
162k
  // Dominator tree it depends on. Because they all participate in the loop
139
162k
  // pass manager, they must also preserve these.
140
162k
  AU.addRequired<DominatorTreeWrapperPass>();
141
162k
  AU.addPreserved<DominatorTreeWrapperPass>();
142
162k
  AU.addRequired<LoopInfoWrapperPass>();
143
162k
  AU.addPreserved<LoopInfoWrapperPass>();
144
162k
145
162k
  // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
146
162k
  // here because users shouldn't directly get them from this header.
147
162k
  extern char &LoopSimplifyID;
148
162k
  extern char &LCSSAID;
149
162k
  AU.addRequiredID(LoopSimplifyID);
150
162k
  AU.addPreservedID(LoopSimplifyID);
151
162k
  AU.addRequiredID(LCSSAID);
152
162k
  AU.addPreservedID(LCSSAID);
153
162k
  // This is used in the LPPassManager to perform LCSSA verification on passes
154
162k
  // which preserve lcssa form
155
162k
  AU.addRequired<LCSSAVerificationPass>();
156
162k
  AU.addPreserved<LCSSAVerificationPass>();
157
162k
158
162k
  // Loop passes are designed to run inside of a loop pass manager which means
159
162k
  // that any function analyses they require must be required by the first loop
160
162k
  // pass in the manager (so that it is computed before the loop pass manager
161
162k
  // runs) and preserved by all loop pasess in the manager. To make this
162
162k
  // reasonably robust, the set needed for most loop passes is maintained here.
163
162k
  // If your loop pass requires an analysis not listed here, you will need to
164
162k
  // carefully audit the loop pass manager nesting structure that results.
165
162k
  AU.addRequired<AAResultsWrapperPass>();
166
162k
  AU.addPreserved<AAResultsWrapperPass>();
167
162k
  AU.addPreserved<BasicAAWrapperPass>();
168
162k
  AU.addPreserved<GlobalsAAWrapperPass>();
169
162k
  AU.addPreserved<SCEVAAWrapperPass>();
170
162k
  AU.addRequired<ScalarEvolutionWrapperPass>();
171
162k
  AU.addPreserved<ScalarEvolutionWrapperPass>();
172
162k
}
173
174
/// Manually defined generic "LoopPass" dependency initialization. This is used
175
/// to initialize the exact set of passes from above in \c
176
/// getLoopAnalysisUsage. It can be used within a loop pass's initialization
177
/// with:
178
///
179
///   INITIALIZE_PASS_DEPENDENCY(LoopPass)
180
///
181
/// As-if "LoopPass" were a pass.
182
678k
void llvm::initializeLoopPassPass(PassRegistry &Registry) {
183
678k
  INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
184
678k
  INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
185
678k
  INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
186
678k
  INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
187
678k
  INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
188
678k
  INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
189
678k
  INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
190
678k
  INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
191
678k
  INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
192
678k
}
193
194
/// Find string metadata for loop
195
///
196
/// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
197
/// operand or null otherwise.  If the string metadata is not found return
198
/// Optional's not-a-value.
199
Optional<const MDOperand *> llvm::findStringMetadataForLoop(const Loop *TheLoop,
200
1.27M
                                                            StringRef Name) {
201
1.27M
  MDNode *MD = findOptionMDForLoop(TheLoop, Name);
202
1.27M
  if (!MD)
203
1.26M
    return None;
204
11.1k
  switch (MD->getNumOperands()) {
205
11.1k
  case 1:
206
0
    return nullptr;
207
11.1k
  case 2:
208
11.1k
    return &MD->getOperand(1);
209
11.1k
  default:
210
0
    llvm_unreachable("loop metadata has 0 or 1 operand");
211
11.1k
  }
212
11.1k
}
213
214
static Optional<bool> getOptionalBoolLoopAttribute(const Loop *TheLoop,
215
4.27M
                                                   StringRef Name) {
216
4.27M
  MDNode *MD = findOptionMDForLoop(TheLoop, Name);
217
4.27M
  if (!MD)
218
4.25M
    return None;
219
22.4k
  switch (MD->getNumOperands()) {
220
22.4k
  case 1:
221
1.18k
    // When the value is absent it is interpreted as 'attribute set'.
222
1.18k
    return true;
223
22.4k
  case 2:
224
21.2k
    if (ConstantInt *IntMD =
225
21.2k
            mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
226
21.2k
      return IntMD->getZExtValue();
227
0
    return true;
228
0
  }
229
0
  llvm_unreachable("unexpected number of options");
230
0
}
231
232
4.09M
static bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) {
233
4.09M
  return getOptionalBoolLoopAttribute(TheLoop, Name).getValueOr(false);
234
4.09M
}
235
236
llvm::Optional<int> llvm::getOptionalIntLoopAttribute(Loop *TheLoop,
237
1.12M
                                                      StringRef Name) {
238
1.12M
  const MDOperand *AttrMD =
239
1.12M
      findStringMetadataForLoop(TheLoop, Name).getValueOr(nullptr);
240
1.12M
  if (!AttrMD)
241
1.11M
    return None;
242
11.1k
243
11.1k
  ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
244
11.1k
  if (!IntMD)
245
0
    return None;
246
11.1k
247
11.1k
  return IntMD->getSExtValue();
248
11.1k
}
249
250
Optional<MDNode *> llvm::makeFollowupLoopID(
251
    MDNode *OrigLoopID, ArrayRef<StringRef> FollowupOptions,
252
38.1k
    const char *InheritOptionsExceptPrefix, bool AlwaysNew) {
253
38.1k
  if (!OrigLoopID) {
254
33.5k
    if (AlwaysNew)
255
13
      return nullptr;
256
33.5k
    return None;
257
33.5k
  }
258
4.65k
259
4.65k
  assert(OrigLoopID->getOperand(0) == OrigLoopID);
260
4.65k
261
4.65k
  bool InheritAllAttrs = !InheritOptionsExceptPrefix;
262
4.65k
  bool InheritSomeAttrs =
263
4.65k
      InheritOptionsExceptPrefix && InheritOptionsExceptPrefix[0] != '\0';
264
4.65k
  SmallVector<Metadata *, 8> MDs;
265
4.65k
  MDs.push_back(nullptr);
266
4.65k
267
4.65k
  bool Changed = false;
268
4.65k
  if (InheritAllAttrs || InheritSomeAttrs) {
269
5
    for (const MDOperand &Existing : drop_begin(OrigLoopID->operands(), 1)) {
270
5
      MDNode *Op = cast<MDNode>(Existing.get());
271
5
272
5
      auto InheritThisAttribute = [InheritSomeAttrs,
273
5
                                   InheritOptionsExceptPrefix](MDNode *Op) {
274
5
        if (!InheritSomeAttrs)
275
0
          return false;
276
5
277
5
        // Skip malformatted attribute metadata nodes.
278
5
        if (Op->getNumOperands() == 0)
279
0
          return true;
280
5
        Metadata *NameMD = Op->getOperand(0).get();
281
5
        if (!isa<MDString>(NameMD))
282
0
          return true;
283
5
        StringRef AttrName = cast<MDString>(NameMD)->getString();
284
5
285
5
        // Do not inherit excluded attributes.
286
5
        return !AttrName.startswith(InheritOptionsExceptPrefix);
287
5
      };
288
5
289
5
      if (InheritThisAttribute(Op))
290
0
        MDs.push_back(Op);
291
5
      else
292
5
        Changed = true;
293
5
    }
294
4.65k
  } else {
295
4.65k
    // Modified if we dropped at least one attribute.
296
4.65k
    Changed = OrigLoopID->getNumOperands() > 1;
297
4.65k
  }
298
4.65k
299
4.65k
  bool HasAnyFollowup = false;
300
9.31k
  for (StringRef OptionName : FollowupOptions) {
301
9.31k
    MDNode *FollowupNode = findOptionMDForLoopID(OrigLoopID, OptionName);
302
9.31k
    if (!FollowupNode)
303
9.28k
      continue;
304
26
305
26
    HasAnyFollowup = true;
306
26
    for (const MDOperand &Option : drop_begin(FollowupNode->operands(), 1)) {
307
26
      MDs.push_back(Option.get());
308
26
      Changed = true;
309
26
    }
310
26
  }
311
4.65k
312
4.65k
  // Attributes of the followup loop not specified explicity, so signal to the
313
4.65k
  // transformation pass to add suitable attributes.
314
4.65k
  if (!AlwaysNew && 
!HasAnyFollowup4.65k
)
315
4.64k
    return None;
316
13
317
13
  // If no attributes were added or remove, the previous loop Id can be reused.
318
13
  if (!AlwaysNew && 
!Changed12
)
319
0
    return OrigLoopID;
320
13
321
13
  // No attributes is equivalent to having no !llvm.loop metadata at all.
322
13
  if (MDs.size() == 1)
323
0
    return nullptr;
324
13
325
13
  // Build the new loop ID.
326
13
  MDTuple *FollowupLoopID = MDNode::get(OrigLoopID->getContext(), MDs);
327
13
  FollowupLoopID->replaceOperandWith(0, FollowupLoopID);
328
13
  return FollowupLoopID;
329
13
}
330
331
1.63M
bool llvm::hasDisableAllTransformsHint(const Loop *L) {
332
1.63M
  return getBooleanLoopAttribute(L, LLVMLoopDisableNonforced);
333
1.63M
}
334
335
575k
TransformationMode llvm::hasUnrollTransformation(Loop *L) {
336
575k
  if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable"))
337
1.13k
    return TM_SuppressedByUser;
338
573k
339
573k
  Optional<int> Count =
340
573k
      getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count");
341
573k
  if (Count.hasValue())
342
26
    return Count.getValue() == 1 ? 
TM_SuppressedByUser4
:
TM_ForcedByUser22
;
343
573k
344
573k
  if (getBooleanLoopAttribute(L, "llvm.loop.unroll.enable"))
345
11
    return TM_ForcedByUser;
346
573k
347
573k
  if (getBooleanLoopAttribute(L, "llvm.loop.unroll.full"))
348
14
    return TM_ForcedByUser;
349
573k
350
573k
  if (hasDisableAllTransformsHint(L))
351
1
    return TM_Disable;
352
573k
353
573k
  return TM_Unspecified;
354
573k
}
355
356
184k
TransformationMode llvm::hasUnrollAndJamTransformation(Loop *L) {
357
184k
  if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.disable"))
358
2
    return TM_SuppressedByUser;
359
184k
360
184k
  Optional<int> Count =
361
184k
      getOptionalIntLoopAttribute(L, "llvm.loop.unroll_and_jam.count");
362
184k
  if (Count.hasValue())
363
4
    return Count.getValue() == 1 ? 
TM_SuppressedByUser0
: TM_ForcedByUser;
364
184k
365
184k
  if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.enable"))
366
11
    return TM_ForcedByUser;
367
184k
368
184k
  if (hasDisableAllTransformsHint(L))
369
1
    return TM_Disable;
370
184k
371
184k
  return TM_Unspecified;
372
184k
}
373
374
184k
TransformationMode llvm::hasVectorizeTransformation(Loop *L) {
375
184k
  Optional<bool> Enable =
376
184k
      getOptionalBoolLoopAttribute(L, "llvm.loop.vectorize.enable");
377
184k
378
184k
  if (Enable == false)
379
11
    return TM_SuppressedByUser;
380
184k
381
184k
  Optional<int> VectorizeWidth =
382
184k
      getOptionalIntLoopAttribute(L, "llvm.loop.vectorize.width");
383
184k
  Optional<int> InterleaveCount =
384
184k
      getOptionalIntLoopAttribute(L, "llvm.loop.interleave.count");
385
184k
386
184k
  // 'Forcing' vector width and interleave count to one effectively disables
387
184k
  // this tranformation.
388
184k
  if (Enable == true && 
VectorizeWidth == 118
&&
InterleaveCount == 11
)
389
0
    return TM_SuppressedByUser;
390
184k
391
184k
  if (getBooleanLoopAttribute(L, "llvm.loop.isvectorized"))
392
21.2k
    return TM_Disable;
393
163k
394
163k
  if (Enable == true)
395
17
    return TM_ForcedByUser;
396
163k
397
163k
  if (VectorizeWidth == 1 && 
InterleaveCount == 15.56k
)
398
5.56k
    return TM_Disable;
399
157k
400
157k
  if (VectorizeWidth > 1 || InterleaveCount > 1)
401
0
    return TM_Enable;
402
157k
403
157k
  if (hasDisableAllTransformsHint(L))
404
0
    return TM_Disable;
405
157k
406
157k
  return TM_Unspecified;
407
157k
}
408
409
184k
TransformationMode llvm::hasDistributeTransformation(Loop *L) {
410
184k
  if (getBooleanLoopAttribute(L, "llvm.loop.distribute.enable"))
411
4
    return TM_ForcedByUser;
412
184k
413
184k
  if (hasDisableAllTransformsHint(L))
414
0
    return TM_Disable;
415
184k
416
184k
  return TM_Unspecified;
417
184k
}
418
419
8
TransformationMode llvm::hasLICMVersioningTransformation(Loop *L) {
420
8
  if (getBooleanLoopAttribute(L, "llvm.loop.licm_versioning.disable"))
421
1
    return TM_SuppressedByUser;
422
7
423
7
  if (hasDisableAllTransformsHint(L))
424
0
    return TM_Disable;
425
7
426
7
  return TM_Unspecified;
427
7
}
428
429
/// Does a BFS from a given node to all of its children inside a given loop.
430
/// The returned vector of nodes includes the starting point.
431
SmallVector<DomTreeNode *, 16>
432
608k
llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) {
433
608k
  SmallVector<DomTreeNode *, 16> Worklist;
434
3.58M
  auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
435
3.58M
    // Only include subregions in the top level loop.
436
3.58M
    BasicBlock *BB = DTN->getBlock();
437
3.58M
    if (CurLoop->contains(BB))
438
2.76M
      Worklist.push_back(DTN);
439
3.58M
  };
440
608k
441
608k
  AddRegionToWorklist(N);
442
608k
443
3.37M
  for (size_t I = 0; I < Worklist.size(); 
I++2.76M
)
444
2.76M
    for (DomTreeNode *Child : Worklist[I]->getChildren())
445
2.97M
      AddRegionToWorklist(Child);
446
608k
447
608k
  return Worklist;
448
608k
}
449
450
void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
451
                          ScalarEvolution *SE = nullptr,
452
15.0k
                          LoopInfo *LI = nullptr) {
453
15.0k
  assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
454
15.0k
  auto *Preheader = L->getLoopPreheader();
455
15.0k
  assert(Preheader && "Preheader should exist!");
456
15.0k
457
15.0k
  // Now that we know the removal is safe, remove the loop by changing the
458
15.0k
  // branch from the preheader to go to the single exit block.
459
15.0k
  //
460
15.0k
  // Because we're deleting a large chunk of code at once, the sequence in which
461
15.0k
  // we remove things is very important to avoid invalidation issues.
462
15.0k
463
15.0k
  // Tell ScalarEvolution that the loop is deleted. Do this before
464
15.0k
  // deleting the loop so that ScalarEvolution can look at the loop
465
15.0k
  // to determine what it needs to clean up.
466
15.0k
  if (SE)
467
15.0k
    SE->forgetLoop(L);
468
15.0k
469
15.0k
  auto *ExitBlock = L->getUniqueExitBlock();
470
15.0k
  assert(ExitBlock && "Should have a unique exit block!");
471
15.0k
  assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
472
15.0k
473
15.0k
  auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
474
15.0k
  assert(OldBr && "Preheader must end with a branch");
475
15.0k
  assert(OldBr->isUnconditional() && "Preheader must have a single successor");
476
15.0k
  // Connect the preheader to the exit block. Keep the old edge to the header
477
15.0k
  // around to perform the dominator tree update in two separate steps
478
15.0k
  // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
479
15.0k
  // preheader -> header.
480
15.0k
  //
481
15.0k
  //
482
15.0k
  // 0.  Preheader          1.  Preheader           2.  Preheader
483
15.0k
  //        |                    |   |                   |
484
15.0k
  //        V                    |   V                   |
485
15.0k
  //      Header <--\            | Header <--\           | Header <--\
486
15.0k
  //       |  |     |            |  |  |     |           |  |  |     |
487
15.0k
  //       |  V     |            |  |  V     |           |  |  V     |
488
15.0k
  //       | Body --/            |  | Body --/           |  | Body --/
489
15.0k
  //       V                     V  V                    V  V
490
15.0k
  //      Exit                   Exit                    Exit
491
15.0k
  //
492
15.0k
  // By doing this is two separate steps we can perform the dominator tree
493
15.0k
  // update without using the batch update API.
494
15.0k
  //
495
15.0k
  // Even when the loop is never executed, we cannot remove the edge from the
496
15.0k
  // source block to the exit block. Consider the case where the unexecuted loop
497
15.0k
  // branches back to an outer loop. If we deleted the loop and removed the edge
498
15.0k
  // coming to this inner loop, this will break the outer loop structure (by
499
15.0k
  // deleting the backedge of the outer loop). If the outer loop is indeed a
500
15.0k
  // non-loop, it will be deleted in a future iteration of loop deletion pass.
501
15.0k
  IRBuilder<> Builder(OldBr);
502
15.0k
  Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
503
15.0k
  // Remove the old branch. The conditional branch becomes a new terminator.
504
15.0k
  OldBr->eraseFromParent();
505
15.0k
506
15.0k
  // Rewrite phis in the exit block to get their inputs from the Preheader
507
15.0k
  // instead of the exiting block.
508
15.0k
  for (PHINode &P : ExitBlock->phis()) {
509
31
    // Set the zero'th element of Phi to be from the preheader and remove all
510
31
    // other incoming values. Given the loop has dedicated exits, all other
511
31
    // incoming values must be from the exiting blocks.
512
31
    int PredIndex = 0;
513
31
    P.setIncomingBlock(PredIndex, Preheader);
514
31
    // Removes all incoming values from all other exiting blocks (including
515
31
    // duplicate values from an exiting block).
516
31
    // Nuke all entries except the zero'th entry which is the preheader entry.
517
31
    // NOTE! We need to remove Incoming Values in the reverse order as done
518
31
    // below, to keep the indices valid for deletion (removeIncomingValues
519
31
    // updates getNumIncomingValues and shifts all values down into the operand
520
31
    // being deleted).
521
44
    for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; 
++i13
)
522
13
      P.removeIncomingValue(e - i, false);
523
31
524
31
    assert((P.getNumIncomingValues() == 1 &&
525
31
            P.getIncomingBlock(PredIndex) == Preheader) &&
526
31
           "Should have exactly one value and that's from the preheader!");
527
31
  }
528
15.0k
529
15.0k
  // Disconnect the loop body by branching directly to its exit.
530
15.0k
  Builder.SetInsertPoint(Preheader->getTerminator());
531
15.0k
  Builder.CreateBr(ExitBlock);
532
15.0k
  // Remove the old branch.
533
15.0k
  Preheader->getTerminator()->eraseFromParent();
534
15.0k
535
15.0k
  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
536
15.0k
  if (DT) {
537
15.0k
    // Update the dominator tree by informing it about the new edge from the
538
15.0k
    // preheader to the exit and the removed edge.
539
15.0k
    DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock},
540
15.0k
                      {DominatorTree::Delete, Preheader, L->getHeader()}});
541
15.0k
  }
542
15.0k
543
15.0k
  // Use a map to unique and a vector to guarantee deterministic ordering.
544
15.0k
  llvm::SmallDenseSet<std::pair<DIVariable *, DIExpression *>, 4> DeadDebugSet;
545
15.0k
  llvm::SmallVector<DbgVariableIntrinsic *, 4> DeadDebugInst;
546
15.0k
547
15.0k
  // Given LCSSA form is satisfied, we should not have users of instructions
548
15.0k
  // within the dead loop outside of the loop. However, LCSSA doesn't take
549
15.0k
  // unreachable uses into account. We handle them here.
550
15.0k
  // We could do it after drop all references (in this case all users in the
551
15.0k
  // loop will be already eliminated and we have less work to do but according
552
15.0k
  // to API doc of User::dropAllReferences only valid operation after dropping
553
15.0k
  // references, is deletion. So let's substitute all usages of
554
15.0k
  // instruction from the loop with undef value of corresponding type first.
555
15.0k
  for (auto *Block : L->blocks())
556
76.4k
    
for (Instruction &I : *Block)15.6k
{
557
76.4k
      auto *Undef = UndefValue::get(I.getType());
558
152k
      for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E;) {
559
75.8k
        Use &U = *UI;
560
75.8k
        ++UI;
561
75.8k
        if (auto *Usr = dyn_cast<Instruction>(U.getUser()))
562
75.8k
          if (L->contains(Usr->getParent()))
563
75.8k
            continue;
564
1
        // If we have a DT then we can check that uses outside a loop only in
565
1
        // unreachable block.
566
1
        if (DT)
567
1
          assert(!DT->isReachableFromEntry(U) &&
568
1
                 "Unexpected user in reachable block");
569
1
        U.set(Undef);
570
1
      }
571
76.4k
      auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I);
572
76.4k
      if (!DVI)
573
76.4k
        continue;
574
3
      auto Key = DeadDebugSet.find({DVI->getVariable(), DVI->getExpression()});
575
3
      if (Key != DeadDebugSet.end())
576
1
        continue;
577
2
      DeadDebugSet.insert({DVI->getVariable(), DVI->getExpression()});
578
2
      DeadDebugInst.push_back(DVI);
579
2
    }
580
15.0k
581
15.0k
  // After the loop has been deleted all the values defined and modified
582
15.0k
  // inside the loop are going to be unavailable.
583
15.0k
  // Since debug values in the loop have been deleted, inserting an undef
584
15.0k
  // dbg.value truncates the range of any dbg.value before the loop where the
585
15.0k
  // loop used to be. This is particularly important for constant values.
586
15.0k
  DIBuilder DIB(*ExitBlock->getModule());
587
15.0k
  Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI();
588
15.0k
  assert(InsertDbgValueBefore &&
589
15.0k
         "There should be a non-PHI instruction in exit block, else these "
590
15.0k
         "instructions will have no parent.");
591
15.0k
  for (auto *DVI : DeadDebugInst)
592
2
    DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()),
593
2
                                DVI->getVariable(), DVI->getExpression(),
594
2
                                DVI->getDebugLoc(), InsertDbgValueBefore);
595
15.0k
596
15.0k
  // Remove the block from the reference counting scheme, so that we can
597
15.0k
  // delete it freely later.
598
15.0k
  for (auto *Block : L->blocks())
599
15.6k
    Block->dropAllReferences();
600
15.0k
601
15.0k
  if (LI) {
602
15.0k
    // Erase the instructions and the blocks without having to worry
603
15.0k
    // about ordering because we already dropped the references.
604
15.0k
    // NOTE: This iteration is safe because erasing the block does not remove
605
15.0k
    // its entry from the loop's block list.  We do that in the next section.
606
15.0k
    for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
607
30.6k
         LpI != LpE; 
++LpI15.6k
)
608
15.6k
      (*LpI)->eraseFromParent();
609
15.0k
610
15.0k
    // Finally, the blocks from loopinfo.  This has to happen late because
611
15.0k
    // otherwise our loop iterators won't work.
612
15.0k
613
15.0k
    SmallPtrSet<BasicBlock *, 8> blocks;
614
15.0k
    blocks.insert(L->block_begin(), L->block_end());
615
15.0k
    for (BasicBlock *BB : blocks)
616
15.6k
      LI->removeBlock(BB);
617
15.0k
618
15.0k
    // The last step is to update LoopInfo now that we've eliminated this loop.
619
15.0k
    LI->erase(L);
620
15.0k
  }
621
15.0k
}
622
623
8.85k
Optional<unsigned> llvm::getLoopEstimatedTripCount(Loop *L) {
624
8.85k
  // Support loops with an exiting latch and other existing exists only
625
8.85k
  // deoptimize.
626
8.85k
627
8.85k
  // Get the branch weights for the loop's backedge.
628
8.85k
  BasicBlock *Latch = L->getLoopLatch();
629
8.85k
  if (!Latch)
630
0
    return None;
631
8.85k
  BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
632
8.85k
  if (!LatchBR || LatchBR->getNumSuccessors() != 2 || 
!L->isLoopExiting(Latch)8.84k
)
633
2
    return None;
634
8.84k
635
8.84k
  assert((LatchBR->getSuccessor(0) == L->getHeader() ||
636
8.84k
          LatchBR->getSuccessor(1) == L->getHeader()) &&
637
8.84k
         "At least one edge out of the latch must go to the header");
638
8.84k
639
8.84k
  SmallVector<BasicBlock *, 4> ExitBlocks;
640
8.84k
  L->getUniqueNonLatchExitBlocks(ExitBlocks);
641
8.84k
  if (any_of(ExitBlocks, [](const BasicBlock *EB) {
642
0
        return !EB->getTerminatingDeoptimizeCall();
643
0
      }))
644
0
    return None;
645
8.84k
646
8.84k
  // To estimate the number of times the loop body was executed, we want to
647
8.84k
  // know the number of times the backedge was taken, vs. the number of times
648
8.84k
  // we exited the loop.
649
8.84k
  uint64_t TrueVal, FalseVal;
650
8.84k
  if (!LatchBR->extractProfMetadata(TrueVal, FalseVal))
651
8.82k
    return None;
652
29
653
29
  if (!TrueVal || !FalseVal)
654
4
    return 0;
655
25
656
25
  // Divide the count of the backedge by the count of the edge exiting the loop,
657
25
  // rounding to nearest.
658
25
  if (LatchBR->getSuccessor(0) == L->getHeader())
659
10
    return (TrueVal + (FalseVal / 2)) / FalseVal;
660
15
  else
661
15
    return (FalseVal + (TrueVal / 2)) / TrueVal;
662
25
}
663
664
bool llvm::hasIterationCountInvariantInParent(Loop *InnerLoop,
665
51
                                              ScalarEvolution &SE) {
666
51
  Loop *OuterL = InnerLoop->getParentLoop();
667
51
  if (!OuterL)
668
0
    return true;
669
51
670
51
  // Get the backedge taken count for the inner loop
671
51
  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
672
51
  const SCEV *InnerLoopBECountSC = SE.getExitCount(InnerLoop, InnerLoopLatch);
673
51
  if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
674
51
      !InnerLoopBECountSC->getType()->isIntegerTy())
675
0
    return false;
676
51
677
51
  // Get whether count is invariant to the outer loop
678
51
  ScalarEvolution::LoopDisposition LD =
679
51
      SE.getLoopDisposition(InnerLoopBECountSC, OuterL);
680
51
  if (LD != ScalarEvolution::LoopInvariant)
681
1
    return false;
682
50
683
50
  return true;
684
50
}
685
686
Value *llvm::createMinMaxOp(IRBuilder<> &Builder,
687
                            RecurrenceDescriptor::MinMaxRecurrenceKind RK,
688
4.33k
                            Value *Left, Value *Right) {
689
4.33k
  CmpInst::Predicate P = CmpInst::ICMP_NE;
690
4.33k
  switch (RK) {
691
4.33k
  default:
692
0
    llvm_unreachable("Unknown min/max recurrence kind");
693
4.33k
  case RecurrenceDescriptor::MRK_UIntMin:
694
915
    P = CmpInst::ICMP_ULT;
695
915
    break;
696
4.33k
  case RecurrenceDescriptor::MRK_UIntMax:
697
917
    P = CmpInst::ICMP_UGT;
698
917
    break;
699
4.33k
  case RecurrenceDescriptor::MRK_SIntMin:
700
930
    P = CmpInst::ICMP_SLT;
701
930
    break;
702
4.33k
  case RecurrenceDescriptor::MRK_SIntMax:
703
1.00k
    P = CmpInst::ICMP_SGT;
704
1.00k
    break;
705
4.33k
  case RecurrenceDescriptor::MRK_FloatMin:
706
256
    P = CmpInst::FCMP_OLT;
707
256
    break;
708
4.33k
  case RecurrenceDescriptor::MRK_FloatMax:
709
305
    P = CmpInst::FCMP_OGT;
710
305
    break;
711
4.33k
  }
712
4.33k
713
4.33k
  // We only match FP sequences that are 'fast', so we can unconditionally
714
4.33k
  // set it on any generated instructions.
715
4.33k
  IRBuilder<>::FastMathFlagGuard FMFG(Builder);
716
4.33k
  FastMathFlags FMF;
717
4.33k
  FMF.setFast();
718
4.33k
  Builder.setFastMathFlags(FMF);
719
4.33k
720
4.33k
  Value *Cmp;
721
4.33k
  if (RK == RecurrenceDescriptor::MRK_FloatMin ||
722
4.33k
      
RK == RecurrenceDescriptor::MRK_FloatMax4.07k
)
723
561
    Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
724
3.77k
  else
725
3.77k
    Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
726
4.33k
727
4.33k
  Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
728
4.33k
  return Select;
729
4.33k
}
730
731
// Helper to generate an ordered reduction.
732
Value *
733
llvm::getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src,
734
                          unsigned Op,
735
                          RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
736
316
                          ArrayRef<Value *> RedOps) {
737
316
  unsigned VF = Src->getType()->getVectorNumElements();
738
316
739
316
  // Extract and apply reduction ops in ascending order:
740
316
  // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
741
316
  Value *Result = Acc;
742
2.67k
  for (unsigned ExtractIdx = 0; ExtractIdx != VF; 
++ExtractIdx2.35k
) {
743
2.35k
    Value *Ext =
744
2.35k
        Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));
745
2.35k
746
2.35k
    if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
747
2.35k
      Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
748
2.35k
                                   "bin.rdx");
749
2.35k
    } else {
750
0
      assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
751
0
             "Invalid min/max");
752
0
      Result = createMinMaxOp(Builder, MinMaxKind, Result, Ext);
753
0
    }
754
2.35k
755
2.35k
    if (!RedOps.empty())
756
0
      propagateIRFlags(Result, RedOps);
757
2.35k
  }
758
316
759
316
  return Result;
760
316
}
761
762
// Helper to generate a log2 shuffle reduction.
763
Value *
764
llvm::getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
765
                          RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
766
4.05k
                          ArrayRef<Value *> RedOps) {
767
4.05k
  unsigned VF = Src->getType()->getVectorNumElements();
768
4.05k
  // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
769
4.05k
  // and vector ops, reducing the set of values being computed by half each
770
4.05k
  // round.
771
4.05k
  assert(isPowerOf2_32(VF) &&
772
4.05k
         "Reduction emission only supported for pow2 vectors!");
773
4.05k
  Value *TmpVec = Src;
774
4.05k
  SmallVector<Constant *, 32> ShuffleMask(VF, nullptr);
775
16.5k
  for (unsigned i = VF; i != 1; 
i >>= 112.5k
) {
776
12.5k
    // Move the upper half of the vector to the lower half.
777
77.6k
    for (unsigned j = 0; j != i / 2; 
++j65.0k
)
778
65.0k
      ShuffleMask[j] = Builder.getInt32(i / 2 + j);
779
12.5k
780
12.5k
    // Fill the rest of the mask with undef.
781
12.5k
    std::fill(&ShuffleMask[i / 2], ShuffleMask.end(),
782
12.5k
              UndefValue::get(Builder.getInt32Ty()));
783
12.5k
784
12.5k
    Value *Shuf = Builder.CreateShuffleVector(
785
12.5k
        TmpVec, UndefValue::get(TmpVec->getType()),
786
12.5k
        ConstantVector::get(ShuffleMask), "rdx.shuf");
787
12.5k
788
12.5k
    if (Op != Instruction::ICmp && 
Op != Instruction::FCmp8.83k
) {
789
8.27k
      // The builder propagates its fast-math-flags setting.
790
8.27k
      TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf,
791
8.27k
                                   "bin.rdx");
792
8.27k
    } else {
793
4.25k
      assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
794
4.25k
             "Invalid min/max");
795
4.25k
      TmpVec = createMinMaxOp(Builder, MinMaxKind, TmpVec, Shuf);
796
4.25k
    }
797
12.5k
    if (!RedOps.empty())
798
389
      propagateIRFlags(TmpVec, RedOps);
799
12.5k
  }
800
4.05k
  // The result is in the first element of the vector.
801
4.05k
  return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
802
4.05k
}
803
804
/// Create a simple vector reduction specified by an opcode and some
805
/// flags (if generating min/max reductions).
806
Value *llvm::createSimpleTargetReduction(
807
    IRBuilder<> &Builder, const TargetTransformInfo *TTI, unsigned Opcode,
808
    Value *Src, TargetTransformInfo::ReductionFlags Flags,
809
1.22k
    ArrayRef<Value *> RedOps) {
810
1.22k
  assert(isa<VectorType>(Src->getType()) && "Type must be a vector");
811
1.22k
812
1.22k
  std::function<Value *()> BuildFunc;
813
1.22k
  using RD = RecurrenceDescriptor;
814
1.22k
  RD::MinMaxRecurrenceKind MinMaxKind = RD::MRK_Invalid;
815
1.22k
816
1.22k
  switch (Opcode) {
817
1.22k
  case Instruction::Add:
818
855
    BuildFunc = [&]() 
{ return Builder.CreateAddReduce(Src); }696
;
819
855
    break;
820
1.22k
  case Instruction::Mul:
821
39
    BuildFunc = [&]() 
{ return Builder.CreateMulReduce(Src); }0
;
822
39
    break;
823
1.22k
  case Instruction::And:
824
26
    BuildFunc = [&]() 
{ return Builder.CreateAndReduce(Src); }0
;
825
26
    break;
826
1.22k
  case Instruction::Or:
827
96
    BuildFunc = [&]() 
{ return Builder.CreateOrReduce(Src); }0
;
828
96
    break;
829
1.22k
  case Instruction::Xor:
830
8
    BuildFunc = [&]() 
{ return Builder.CreateXorReduce(Src); }0
;
831
8
    break;
832
1.22k
  case Instruction::FAdd:
833
77
    BuildFunc = [&]() {
834
0
      auto Rdx = Builder.CreateFAddReduce(
835
0
          Constant::getNullValue(Src->getType()->getVectorElementType()), Src);
836
0
      return Rdx;
837
0
    };
838
77
    break;
839
1.22k
  case Instruction::FMul:
840
3
    BuildFunc = [&]() {
841
0
      Type *Ty = Src->getType()->getVectorElementType();
842
0
      auto Rdx = Builder.CreateFMulReduce(ConstantFP::get(Ty, 1.0), Src);
843
0
      return Rdx;
844
0
    };
845
3
    break;
846
1.22k
  case Instruction::ICmp:
847
80
    if (Flags.IsMaxOp) {
848
49
      MinMaxKind = Flags.IsSigned ? 
RD::MRK_SIntMax43
:
RD::MRK_UIntMax6
;
849
49
      BuildFunc = [&]() {
850
8
        return Builder.CreateIntMaxReduce(Src, Flags.IsSigned);
851
8
      };
852
49
    } else {
853
31
      MinMaxKind = Flags.IsSigned ? 
RD::MRK_SIntMin21
:
RD::MRK_UIntMin10
;
854
31
      BuildFunc = [&]() {
855
5
        return Builder.CreateIntMinReduce(Src, Flags.IsSigned);
856
5
      };
857
31
    }
858
80
    break;
859
1.22k
  case Instruction::FCmp:
860
36
    if (Flags.IsMaxOp) {
861
24
      MinMaxKind = RD::MRK_FloatMax;
862
24
      BuildFunc = [&]() 
{ return Builder.CreateFPMaxReduce(Src, Flags.NoNaN); }0
;
863
24
    } else {
864
12
      MinMaxKind = RD::MRK_FloatMin;
865
12
      BuildFunc = [&]() 
{ return Builder.CreateFPMinReduce(Src, Flags.NoNaN); }0
;
866
12
    }
867
36
    break;
868
1.22k
  default:
869
0
    llvm_unreachable("Unhandled opcode");
870
1.22k
    
break0
;
871
1.22k
  }
872
1.22k
  if (TTI->useReductionIntrinsic(Opcode, Src->getType(), Flags))
873
709
    return BuildFunc();
874
511
  return getShuffleReduction(Builder, Src, Opcode, MinMaxKind, RedOps);
875
511
}
876
877
/// Create a vector reduction using a given recurrence descriptor.
878
Value *llvm::createTargetReduction(IRBuilder<> &B,
879
                                   const TargetTransformInfo *TTI,
880
                                   RecurrenceDescriptor &Desc, Value *Src,
881
1.05k
                                   bool NoNaN) {
882
1.05k
  // TODO: Support in-order reductions based on the recurrence descriptor.
883
1.05k
  using RD = RecurrenceDescriptor;
884
1.05k
  RD::RecurrenceKind RecKind = Desc.getRecurrenceKind();
885
1.05k
  TargetTransformInfo::ReductionFlags Flags;
886
1.05k
  Flags.NoNaN = NoNaN;
887
1.05k
888
1.05k
  // All ops in the reduction inherit fast-math-flags from the recurrence
889
1.05k
  // descriptor.
890
1.05k
  IRBuilder<>::FastMathFlagGuard FMFGuard(B);
891
1.05k
  B.setFastMathFlags(Desc.getFastMathFlags());
892
1.05k
893
1.05k
  switch (RecKind) {
894
1.05k
  case RD::RK_FloatAdd:
895
34
    return createSimpleTargetReduction(B, TTI, Instruction::FAdd, Src, Flags);
896
1.05k
  case RD::RK_FloatMult:
897
3
    return createSimpleTargetReduction(B, TTI, Instruction::FMul, Src, Flags);
898
1.05k
  case RD::RK_IntegerAdd:
899
803
    return createSimpleTargetReduction(B, TTI, Instruction::Add, Src, Flags);
900
1.05k
  case RD::RK_IntegerMult:
901
39
    return createSimpleTargetReduction(B, TTI, Instruction::Mul, Src, Flags);
902
1.05k
  case RD::RK_IntegerAnd:
903
23
    return createSimpleTargetReduction(B, TTI, Instruction::And, Src, Flags);
904
1.05k
  case RD::RK_IntegerOr:
905
84
    return createSimpleTargetReduction(B, TTI, Instruction::Or, Src, Flags);
906
1.05k
  case RD::RK_IntegerXor:
907
8
    return createSimpleTargetReduction(B, TTI, Instruction::Xor, Src, Flags);
908
1.05k
  case RD::RK_IntegerMinMax: {
909
45
    RD::MinMaxRecurrenceKind MMKind = Desc.getMinMaxRecurrenceKind();
910
45
    Flags.IsMaxOp = (MMKind == RD::MRK_SIntMax || 
MMKind == RD::MRK_UIntMax28
);
911
45
    Flags.IsSigned = (MMKind == RD::MRK_SIntMax || 
MMKind == RD::MRK_SIntMin28
);
912
45
    return createSimpleTargetReduction(B, TTI, Instruction::ICmp, Src, Flags);
913
1.05k
  }
914
1.05k
  case RD::RK_FloatMinMax: {
915
18
    Flags.IsMaxOp = Desc.getMinMaxRecurrenceKind() == RD::MRK_FloatMax;
916
18
    return createSimpleTargetReduction(B, TTI, Instruction::FCmp, Src, Flags);
917
1.05k
  }
918
1.05k
  default:
919
0
    llvm_unreachable("Unhandled RecKind");
920
1.05k
  }
921
1.05k
}
922
923
11.0k
void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue) {
924
11.0k
  auto *VecOp = dyn_cast<Instruction>(I);
925
11.0k
  if (!VecOp)
926
14
    return;
927
11.0k
  auto *Intersection = (OpValue == nullptr) ? 
dyn_cast<Instruction>(VL[0])920
928
11.0k
                                            : 
dyn_cast<Instruction>(OpValue)10.0k
;
929
11.0k
  if (!Intersection)
930
0
    return;
931
11.0k
  const unsigned Opcode = Intersection->getOpcode();
932
11.0k
  VecOp->copyIRFlags(Intersection);
933
44.4k
  for (auto *V : VL) {
934
44.4k
    auto *Instr = dyn_cast<Instruction>(V);
935
44.4k
    if (!Instr)
936
0
      continue;
937
44.4k
    if (OpValue == nullptr || 
Opcode == Instr->getOpcode()36.9k
)
938
44.4k
      VecOp->andIRFlags(V);
939
44.4k
  }
940
11.0k
}
941
942
bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L,
943
44
                                 ScalarEvolution &SE) {
944
44
  const SCEV *Zero = SE.getZero(S->getType());
945
44
  return SE.isAvailableAtLoopEntry(S, L) &&
946
44
         SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, S, Zero);
947
44
}
948
949
bool llvm::isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
950
269
                                    ScalarEvolution &SE) {
951
269
  const SCEV *Zero = SE.getZero(S->getType());
952
269
  return SE.isAvailableAtLoopEntry(S, L) &&
953
269
         SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, S, Zero);
954
269
}
955
956
bool llvm::cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
957
48
                             bool Signed) {
958
48
  unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
959
48
  APInt Min = Signed ? 
APInt::getSignedMinValue(BitWidth)26
:
960
48
    
APInt::getMinValue(BitWidth)22
;
961
48
  auto Predicate = Signed ? 
ICmpInst::ICMP_SGT26
:
ICmpInst::ICMP_UGT22
;
962
48
  return SE.isAvailableAtLoopEntry(S, L) &&
963
48
         SE.isLoopEntryGuardedByCond(L, Predicate, S,
964
48
                                     SE.getConstant(Min));
965
48
}
966
967
bool llvm::cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
968
5
                             bool Signed) {
969
5
  unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
970
5
  APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) :
971
5
    
APInt::getMaxValue(BitWidth)0
;
972
5
  auto Predicate = Signed ? ICmpInst::ICMP_SLT : 
ICmpInst::ICMP_ULT0
;
973
5
  return SE.isAvailableAtLoopEntry(S, L) &&
974
5
         SE.isLoopEntryGuardedByCond(L, Predicate, S,
975
3
                                     SE.getConstant(Max));
976
5
}