LLVM: lib/Transforms/Utils/LoopUnroll.cpp Source File

LoopUnroll.cpp

1//===-- UnrollLoop.cpp - Loop unrolling utilities -------------------------===//

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 implements some loop unrolling utilities. It does not define any

10// actual pass or policy, but provides a single function to perform loop

11// unrolling.

12//

13// The process of unrolling can produce extraneous basic blocks linked with

14// unconditional branches. This will be corrected in the future.

15//

16//===----------------------------------------------------------------------===//

17

18#include "llvm/ADT/ArrayRef.h"

19#include "llvm/ADT/DenseMap.h"

20#include "llvm/ADT/STLExtras.h"

21#include "llvm/ADT/ScopedHashTable.h"

22#include "llvm/ADT/SetVector.h"

23#include "llvm/ADT/SmallVector.h"

24#include "llvm/ADT/Statistic.h"

25#include "llvm/ADT/StringRef.h"

26#include "llvm/ADT/Twine.h"

27#include "llvm/Analysis/AliasAnalysis.h"

28#include "llvm/Analysis/AssumptionCache.h"

29#include "llvm/Analysis/DomTreeUpdater.h"

30#include "llvm/Analysis/InstructionSimplify.h"

31#include "llvm/Analysis/LoopInfo.h"

32#include "llvm/Analysis/LoopIterator.h"

33#include "llvm/Analysis/MemorySSA.h"

34#include "llvm/Analysis/OptimizationRemarkEmitter.h"

35#include "llvm/Analysis/ScalarEvolution.h"

36#include "llvm/IR/BasicBlock.h"

37#include "llvm/IR/CFG.h"

38#include "llvm/IR/Constants.h"

39#include "llvm/IR/DebugInfoMetadata.h"

40#include "llvm/IR/DebugLoc.h"

41#include "llvm/IR/DiagnosticInfo.h"

42#include "llvm/IR/Dominators.h"

43#include "llvm/IR/Function.h"

44#include "llvm/IR/IRBuilder.h"

45#include "llvm/IR/Instruction.h"

46#include "llvm/IR/Instructions.h"

47#include "llvm/IR/IntrinsicInst.h"

48#include "llvm/IR/Metadata.h"

49#include "llvm/IR/PatternMatch.h"

50#include "llvm/IR/Use.h"

51#include "llvm/IR/User.h"

52#include "llvm/IR/ValueHandle.h"

53#include "llvm/IR/ValueMap.h"

54#include "llvm/Support/Casting.h"

55#include "llvm/Support/CommandLine.h"

56#include "llvm/Support/Debug.h"

57#include "llvm/Support/GenericDomTree.h"

58#include "llvm/Support/raw_ostream.h"

59#include "llvm/Transforms/Utils/BasicBlockUtils.h"

60#include "llvm/Transforms/Utils/Cloning.h"

61#include "llvm/Transforms/Utils/Local.h"

62#include "llvm/Transforms/Utils/LoopSimplify.h"

63#include "llvm/Transforms/Utils/LoopUtils.h"

64#include "llvm/Transforms/Utils/SimplifyIndVar.h"

65#include "llvm/Transforms/Utils/UnrollLoop.h"

66#include "llvm/Transforms/Utils/ValueMapper.h"

67#include <assert.h>

68#include <numeric>

69#include <type_traits>

70#include <vector>

71

72namespace llvm {

73class DataLayout;

74class Value;

75} // namespace llvm

76

77using namespace llvm;

78

79 #define DEBUG_TYPE "loop-unroll"

80

81// TODO: Should these be here or in LoopUnroll?

82 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");

83 STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");

84 STATISTIC(NumUnrolledNotLatch, "Number of loops unrolled without a conditional "

85 "latch (completely or otherwise)");

86

87static cl::opt<bool>

88 UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden,

89 cl::desc("Allow runtime unrolled loops to be unrolled "

90 "with epilog instead of prolog."));

91

92static cl::opt<bool>

93 UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden,

94 cl::desc("Verify domtree after unrolling"),

95#ifdef EXPENSIVE_CHECKS

96 cl::init(true)

97#else

98 cl::init(false)

99#endif

100 );

101

102static cl::opt<bool>

103 UnrollVerifyLoopInfo("unroll-verify-loopinfo", cl::Hidden,

104 cl::desc("Verify loopinfo after unrolling"),

105#ifdef EXPENSIVE_CHECKS

106 cl::init(true)

107#else

108 cl::init(false)

109#endif

110 );

111

112 static cl::opt<bool> UnrollAddParallelReductions(

113 "unroll-add-parallel-reductions", cl::init(false), cl::Hidden,

114 cl::desc("Allow unrolling to add parallel reduction phis."));

115

116/// Check if unrolling created a situation where we need to insert phi nodes to

117/// preserve LCSSA form.

118/// \param Blocks is a vector of basic blocks representing unrolled loop.

119/// \param L is the outer loop.

120/// It's possible that some of the blocks are in L, and some are not. In this

121/// case, if there is a use is outside L, and definition is inside L, we need to

122/// insert a phi-node, otherwise LCSSA will be broken.

123/// The function is just a helper function for llvm::UnrollLoop that returns

124/// true if this situation occurs, indicating that LCSSA needs to be fixed.

145

146/// Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary

147/// and adds a mapping from the original loop to the new loop to NewLoops.

148/// Returns nullptr if no new loop was created and a pointer to the

149/// original loop OriginalBB was part of otherwise.

178

179/// The function chooses which type of unroll (epilog or prolog) is more

180/// profitabale.

181/// Epilog unroll is more profitable when there is PHI that starts from

182/// constant. In this case epilog will leave PHI start from constant,

183/// but prolog will convert it to non-constant.

184///

185/// loop:

186/// PN = PHI [I, Latch], [CI, PreHeader]

187/// I = foo(PN)

188/// ...

189///

190/// Epilog unroll case.

191/// loop:

192/// PN = PHI [I2, Latch], [CI, PreHeader]

193/// I1 = foo(PN)

194/// I2 = foo(I1)

195/// ...

196/// Prolog unroll case.

197/// NewPN = PHI [PrologI, Prolog], [CI, PreHeader]

198/// loop:

199/// PN = PHI [I2, Latch], [NewPN, PreHeader]

200/// I1 = foo(PN)

201/// I2 = foo(I1)

202/// ...

203///

214

222

255

275

340

341/// Perform some cleanup and simplifications on loops after unrolling. It is

342/// useful to simplify the IV's in the new loop, as well as do a quick

343/// simplify/dce pass of the instructions.

421

422// Loops containing convergent instructions that are uncontrolled or controlled

423// from outside the loop must have a count that divides their TripMultiple.

424LLVM_ATTRIBUTE_USED

441

442/// Unroll the given loop by Count. The loop must be in LCSSA form. Unrolling

443/// can only fail when the loop's latch block is not terminated by a conditional

444/// branch instruction. However, if the trip count (and multiple) are not known,

445/// loop unrolling will mostly produce more code that is no faster.

446///

447/// If Runtime is true then UnrollLoop will try to insert a prologue or

448/// epilogue that ensures the latch has a trip multiple of Count. UnrollLoop

449/// will not runtime-unroll the loop if computing the run-time trip count will

450/// be expensive and AllowExpensiveTripCount is false.

451///

452/// The LoopInfo Analysis that is passed will be kept consistent.

453///

454/// This utility preserves LoopInfo. It will also preserve ScalarEvolution and

455/// DominatorTree if they are non-null.

456///

457/// If RemainderLoop is non-null, it will receive the remainder loop (if

458/// required and not fully unrolled).

459LoopUnrollResult

1225

1226/// Given an llvm.loop loop id metadata node, returns the loop hint metadata

1227/// node with the given name (for example, "llvm.loop.unroll.count"). If no

1228/// such metadata node exists, then nullptr is returned.

1248

1249std::optional<RecurrenceDescriptor>