1 //===-- HardwareLoops.cpp - Target Independent Hardware Loops --*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 /// Insert hardware loop intrinsics into loops which are deemed profitable by
10 /// the target, by querying TargetTransformInfo. A hardware loop comprises of
11 /// two intrinsics: one, outside the loop, to set the loop iteration count and
12 /// another, in the exit block, to decrement the counter. The decremented value
13 /// can either be carried through the loop via a phi or handled in some opaque
14 /// way by the target.
16 //===----------------------------------------------------------------------===//
18 #include "llvm/Pass.h"
19 #include "llvm/PassRegistry.h"
20 #include "llvm/PassSupport.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Analysis/AssumptionCache.h"
23 #include "llvm/Analysis/LoopInfo.h"
24 #include "llvm/Analysis/ScalarEvolution.h"
25 #include "llvm/Analysis/ScalarEvolutionExpander.h"
26 #include "llvm/Analysis/TargetTransformInfo.h"
27 #include "llvm/CodeGen/Passes.h"
28 #include "llvm/CodeGen/TargetPassConfig.h"
29 #include "llvm/IR/BasicBlock.h"
30 #include "llvm/IR/DataLayout.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/Constants.h"
33 #include "llvm/IR/IRBuilder.h"
34 #include "llvm/IR/Instructions.h"
35 #include "llvm/IR/IntrinsicInst.h"
36 #include "llvm/IR/Value.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Transforms/Scalar.h"
39 #include "llvm/Transforms/Utils.h"
40 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
41 #include "llvm/Transforms/Utils/Local.h"
42 #include "llvm/Transforms/Utils/LoopUtils.h"
44 #define DEBUG_TYPE "hardware-loops"
46 #define HW_LOOPS_NAME "Hardware Loop Insertion"
51 ForceHardwareLoops("force-hardware-loops", cl::Hidden
, cl::init(false),
52 cl::desc("Force hardware loops intrinsics to be inserted"));
56 "force-hardware-loop-phi", cl::Hidden
, cl::init(false),
57 cl::desc("Force hardware loop counter to be updated through a phi"));
60 ForceNestedLoop("force-nested-hardware-loop", cl::Hidden
, cl::init(false),
61 cl::desc("Force allowance of nested hardware loops"));
63 static cl::opt
<unsigned>
64 LoopDecrement("hardware-loop-decrement", cl::Hidden
, cl::init(1),
65 cl::desc("Set the loop decrement value"));
67 static cl::opt
<unsigned>
68 CounterBitWidth("hardware-loop-counter-bitwidth", cl::Hidden
, cl::init(32),
69 cl::desc("Set the loop counter bitwidth"));
73 "force-hardware-loop-guard", cl::Hidden
, cl::init(false),
74 cl::desc("Force generation of loop guard intrinsic"));
76 STATISTIC(NumHWLoops
, "Number of loops converted to hardware loops");
80 using TTI
= TargetTransformInfo
;
82 class HardwareLoops
: public FunctionPass
{
86 HardwareLoops() : FunctionPass(ID
) {
87 initializeHardwareLoopsPass(*PassRegistry::getPassRegistry());
90 bool runOnFunction(Function
&F
) override
;
92 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
93 AU
.addRequired
<LoopInfoWrapperPass
>();
94 AU
.addPreserved
<LoopInfoWrapperPass
>();
95 AU
.addRequired
<DominatorTreeWrapperPass
>();
96 AU
.addPreserved
<DominatorTreeWrapperPass
>();
97 AU
.addRequired
<ScalarEvolutionWrapperPass
>();
98 AU
.addRequired
<AssumptionCacheTracker
>();
99 AU
.addRequired
<TargetTransformInfoWrapperPass
>();
102 // Try to convert the given Loop into a hardware loop.
103 bool TryConvertLoop(Loop
*L
);
105 // Given that the target believes the loop to be profitable, try to
107 bool TryConvertLoop(HardwareLoopInfo
&HWLoopInfo
);
110 ScalarEvolution
*SE
= nullptr;
111 LoopInfo
*LI
= nullptr;
112 const DataLayout
*DL
= nullptr;
113 const TargetTransformInfo
*TTI
= nullptr;
114 DominatorTree
*DT
= nullptr;
115 bool PreserveLCSSA
= false;
116 AssumptionCache
*AC
= nullptr;
117 TargetLibraryInfo
*LibInfo
= nullptr;
119 bool MadeChange
= false;
123 // Expand the trip count scev into a value that we can use.
124 Value
*InitLoopCount();
126 // Insert the set_loop_iteration intrinsic.
127 void InsertIterationSetup(Value
*LoopCountInit
);
129 // Insert the loop_decrement intrinsic.
130 void InsertLoopDec();
132 // Insert the loop_decrement_reg intrinsic.
133 Instruction
*InsertLoopRegDec(Value
*EltsRem
);
135 // If the target requires the counter value to be updated in the loop,
136 // insert a phi to hold the value. The intended purpose is for use by
137 // loop_decrement_reg.
138 PHINode
*InsertPHICounter(Value
*NumElts
, Value
*EltsRem
);
140 // Create a new cmp, that checks the returned value of loop_decrement*,
141 // and update the exit branch to use it.
142 void UpdateBranch(Value
*EltsRem
);
145 HardwareLoop(HardwareLoopInfo
&Info
, ScalarEvolution
&SE
,
146 const DataLayout
&DL
) :
147 SE(SE
), DL(DL
), L(Info
.L
), M(L
->getHeader()->getModule()),
148 ExitCount(Info
.ExitCount
),
149 CountType(Info
.CountType
),
150 ExitBranch(Info
.ExitBranch
),
151 LoopDecrement(Info
.LoopDecrement
),
152 UsePHICounter(Info
.CounterInReg
),
153 UseLoopGuard(Info
.PerformEntryTest
) { }
159 const DataLayout
&DL
;
162 const SCEV
*ExitCount
= nullptr;
163 Type
*CountType
= nullptr;
164 BranchInst
*ExitBranch
= nullptr;
165 Value
*LoopDecrement
= nullptr;
166 bool UsePHICounter
= false;
167 bool UseLoopGuard
= false;
168 BasicBlock
*BeginBB
= nullptr;
172 char HardwareLoops::ID
= 0;
174 bool HardwareLoops::runOnFunction(Function
&F
) {
178 LLVM_DEBUG(dbgs() << "HWLoops: Running on " << F
.getName() << "\n");
180 LI
= &getAnalysis
<LoopInfoWrapperPass
>().getLoopInfo();
181 SE
= &getAnalysis
<ScalarEvolutionWrapperPass
>().getSE();
182 DT
= &getAnalysis
<DominatorTreeWrapperPass
>().getDomTree();
183 TTI
= &getAnalysis
<TargetTransformInfoWrapperPass
>().getTTI(F
);
184 DL
= &F
.getParent()->getDataLayout();
185 auto *TLIP
= getAnalysisIfAvailable
<TargetLibraryInfoWrapperPass
>();
186 LibInfo
= TLIP
? &TLIP
->getTLI(F
) : nullptr;
187 PreserveLCSSA
= mustPreserveAnalysisID(LCSSAID
);
188 AC
= &getAnalysis
<AssumptionCacheTracker
>().getAssumptionCache(F
);
191 for (LoopInfo::iterator I
= LI
->begin(), E
= LI
->end(); I
!= E
; ++I
) {
193 if (!L
->getParentLoop())
200 // Return true if the search should stop, which will be when an inner loop is
201 // converted and the parent loop doesn't support containing a hardware loop.
202 bool HardwareLoops::TryConvertLoop(Loop
*L
) {
203 // Process nested loops first.
204 for (Loop::iterator I
= L
->begin(), E
= L
->end(); I
!= E
; ++I
)
205 if (TryConvertLoop(*I
))
206 return true; // Stop search.
208 HardwareLoopInfo
HWLoopInfo(L
);
209 if (!HWLoopInfo
.canAnalyze(*LI
))
212 if (TTI
->isHardwareLoopProfitable(L
, *SE
, *AC
, LibInfo
, HWLoopInfo
) ||
213 ForceHardwareLoops
) {
215 // Allow overriding of the counter width and loop decrement value.
216 if (CounterBitWidth
.getNumOccurrences())
217 HWLoopInfo
.CountType
=
218 IntegerType::get(M
->getContext(), CounterBitWidth
);
220 if (LoopDecrement
.getNumOccurrences())
221 HWLoopInfo
.LoopDecrement
=
222 ConstantInt::get(HWLoopInfo
.CountType
, LoopDecrement
);
224 MadeChange
|= TryConvertLoop(HWLoopInfo
);
225 return MadeChange
&& (!HWLoopInfo
.IsNestingLegal
&& !ForceNestedLoop
);
231 bool HardwareLoops::TryConvertLoop(HardwareLoopInfo
&HWLoopInfo
) {
233 Loop
*L
= HWLoopInfo
.L
;
234 LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: " << *L
);
236 if (!HWLoopInfo
.isHardwareLoopCandidate(*SE
, *LI
, *DT
, ForceNestedLoop
,
237 ForceHardwareLoopPHI
))
241 (HWLoopInfo
.ExitBlock
&& HWLoopInfo
.ExitBranch
&& HWLoopInfo
.ExitCount
) &&
242 "Hardware Loop must have set exit info.");
244 BasicBlock
*Preheader
= L
->getLoopPreheader();
246 // If we don't have a preheader, then insert one.
248 Preheader
= InsertPreheaderForLoop(L
, DT
, LI
, nullptr, PreserveLCSSA
);
252 HardwareLoop
HWLoop(HWLoopInfo
, *SE
, *DL
);
258 void HardwareLoop::Create() {
259 LLVM_DEBUG(dbgs() << "HWLoops: Converting loop..\n");
261 Value
*LoopCountInit
= InitLoopCount();
265 InsertIterationSetup(LoopCountInit
);
267 if (UsePHICounter
|| ForceHardwareLoopPHI
) {
268 Instruction
*LoopDec
= InsertLoopRegDec(LoopCountInit
);
269 Value
*EltsRem
= InsertPHICounter(LoopCountInit
, LoopDec
);
270 LoopDec
->setOperand(0, EltsRem
);
271 UpdateBranch(LoopDec
);
275 // Run through the basic blocks of the loop and see if any of them have dead
276 // PHIs that can be removed.
277 for (auto I
: L
->blocks())
281 static bool CanGenerateTest(Loop
*L
, Value
*Count
) {
282 BasicBlock
*Preheader
= L
->getLoopPreheader();
283 if (!Preheader
->getSinglePredecessor())
286 BasicBlock
*Pred
= Preheader
->getSinglePredecessor();
287 if (!isa
<BranchInst
>(Pred
->getTerminator()))
290 auto *BI
= cast
<BranchInst
>(Pred
->getTerminator());
291 if (BI
->isUnconditional() || !isa
<ICmpInst
>(BI
->getCondition()))
294 // Check that the icmp is checking for equality of Count and zero and that
295 // a non-zero value results in entering the loop.
296 auto ICmp
= cast
<ICmpInst
>(BI
->getCondition());
297 LLVM_DEBUG(dbgs() << " - Found condition: " << *ICmp
<< "\n");
298 if (!ICmp
->isEquality())
301 auto IsCompareZero
= [](ICmpInst
*ICmp
, Value
*Count
, unsigned OpIdx
) {
302 if (auto *Const
= dyn_cast
<ConstantInt
>(ICmp
->getOperand(OpIdx
)))
303 return Const
->isZero() && ICmp
->getOperand(OpIdx
^ 1) == Count
;
307 if (!IsCompareZero(ICmp
, Count
, 0) && !IsCompareZero(ICmp
, Count
, 1))
310 unsigned SuccIdx
= ICmp
->getPredicate() == ICmpInst::ICMP_NE
? 0 : 1;
311 if (BI
->getSuccessor(SuccIdx
) != Preheader
)
317 Value
*HardwareLoop::InitLoopCount() {
318 LLVM_DEBUG(dbgs() << "HWLoops: Initialising loop counter value:\n");
319 // Can we replace a conditional branch with an intrinsic that sets the
320 // loop counter and tests that is not zero?
322 SCEVExpander
SCEVE(SE
, DL
, "loopcnt");
323 if (!ExitCount
->getType()->isPointerTy() &&
324 ExitCount
->getType() != CountType
)
325 ExitCount
= SE
.getZeroExtendExpr(ExitCount
, CountType
);
327 ExitCount
= SE
.getAddExpr(ExitCount
, SE
.getOne(CountType
));
329 // If we're trying to use the 'test and set' form of the intrinsic, we need
330 // to replace a conditional branch that is controlling entry to the loop. It
331 // is likely (guaranteed?) that the preheader has an unconditional branch to
332 // the loop header, so also check if it has a single predecessor.
333 if (SE
.isLoopEntryGuardedByCond(L
, ICmpInst::ICMP_NE
, ExitCount
,
334 SE
.getZero(ExitCount
->getType()))) {
335 LLVM_DEBUG(dbgs() << " - Attempting to use test.set counter.\n");
336 UseLoopGuard
|= ForceGuardLoopEntry
;
338 UseLoopGuard
= false;
340 BasicBlock
*BB
= L
->getLoopPreheader();
341 if (UseLoopGuard
&& BB
->getSinglePredecessor() &&
342 cast
<BranchInst
>(BB
->getTerminator())->isUnconditional())
343 BB
= BB
->getSinglePredecessor();
345 if (!isSafeToExpandAt(ExitCount
, BB
->getTerminator(), SE
)) {
346 LLVM_DEBUG(dbgs() << "- Bailing, unsafe to expand ExitCount "
347 << *ExitCount
<< "\n");
351 Value
*Count
= SCEVE
.expandCodeFor(ExitCount
, CountType
,
352 BB
->getTerminator());
354 // FIXME: We've expanded Count where we hope to insert the counter setting
355 // intrinsic. But, in the case of the 'test and set' form, we may fallback to
356 // the just 'set' form and in which case the insertion block is most likely
357 // different. It means there will be instruction(s) in a block that possibly
358 // aren't needed. The isLoopEntryGuardedByCond is trying to avoid this issue,
359 // but it's doesn't appear to work in all cases.
361 UseLoopGuard
= UseLoopGuard
&& CanGenerateTest(L
, Count
);
362 BeginBB
= UseLoopGuard
? BB
: L
->getLoopPreheader();
363 LLVM_DEBUG(dbgs() << " - Loop Count: " << *Count
<< "\n"
364 << " - Expanded Count in " << BB
->getName() << "\n"
365 << " - Will insert set counter intrinsic into: "
366 << BeginBB
->getName() << "\n");
370 void HardwareLoop::InsertIterationSetup(Value
*LoopCountInit
) {
371 IRBuilder
<> Builder(BeginBB
->getTerminator());
372 Type
*Ty
= LoopCountInit
->getType();
373 Intrinsic::ID ID
= UseLoopGuard
?
374 Intrinsic::test_set_loop_iterations
: Intrinsic::set_loop_iterations
;
375 Function
*LoopIter
= Intrinsic::getDeclaration(M
, ID
, Ty
);
376 Value
*SetCount
= Builder
.CreateCall(LoopIter
, LoopCountInit
);
378 // Use the return value of the intrinsic to control the entry of the loop.
380 assert((isa
<BranchInst
>(BeginBB
->getTerminator()) &&
381 cast
<BranchInst
>(BeginBB
->getTerminator())->isConditional()) &&
382 "Expected conditional branch");
383 auto *LoopGuard
= cast
<BranchInst
>(BeginBB
->getTerminator());
384 LoopGuard
->setCondition(SetCount
);
385 if (LoopGuard
->getSuccessor(0) != L
->getLoopPreheader())
386 LoopGuard
->swapSuccessors();
388 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop counter: "
389 << *SetCount
<< "\n");
392 void HardwareLoop::InsertLoopDec() {
393 IRBuilder
<> CondBuilder(ExitBranch
);
396 Intrinsic::getDeclaration(M
, Intrinsic::loop_decrement
,
397 LoopDecrement
->getType());
398 Value
*Ops
[] = { LoopDecrement
};
399 Value
*NewCond
= CondBuilder
.CreateCall(DecFunc
, Ops
);
400 Value
*OldCond
= ExitBranch
->getCondition();
401 ExitBranch
->setCondition(NewCond
);
403 // The false branch must exit the loop.
404 if (!L
->contains(ExitBranch
->getSuccessor(0)))
405 ExitBranch
->swapSuccessors();
407 // The old condition may be dead now, and may have even created a dead PHI
408 // (the original induction variable).
409 RecursivelyDeleteTriviallyDeadInstructions(OldCond
);
411 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *NewCond
<< "\n");
414 Instruction
* HardwareLoop::InsertLoopRegDec(Value
*EltsRem
) {
415 IRBuilder
<> CondBuilder(ExitBranch
);
418 Intrinsic::getDeclaration(M
, Intrinsic::loop_decrement_reg
,
419 { EltsRem
->getType(), EltsRem
->getType(),
420 LoopDecrement
->getType()
422 Value
*Ops
[] = { EltsRem
, LoopDecrement
};
423 Value
*Call
= CondBuilder
.CreateCall(DecFunc
, Ops
);
425 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *Call
<< "\n");
426 return cast
<Instruction
>(Call
);
429 PHINode
* HardwareLoop::InsertPHICounter(Value
*NumElts
, Value
*EltsRem
) {
430 BasicBlock
*Preheader
= L
->getLoopPreheader();
431 BasicBlock
*Header
= L
->getHeader();
432 BasicBlock
*Latch
= ExitBranch
->getParent();
433 IRBuilder
<> Builder(Header
->getFirstNonPHI());
434 PHINode
*Index
= Builder
.CreatePHI(NumElts
->getType(), 2);
435 Index
->addIncoming(NumElts
, Preheader
);
436 Index
->addIncoming(EltsRem
, Latch
);
437 LLVM_DEBUG(dbgs() << "HWLoops: PHI Counter: " << *Index
<< "\n");
441 void HardwareLoop::UpdateBranch(Value
*EltsRem
) {
442 IRBuilder
<> CondBuilder(ExitBranch
);
444 CondBuilder
.CreateICmpNE(EltsRem
, ConstantInt::get(EltsRem
->getType(), 0));
445 Value
*OldCond
= ExitBranch
->getCondition();
446 ExitBranch
->setCondition(NewCond
);
448 // The false branch must exit the loop.
449 if (!L
->contains(ExitBranch
->getSuccessor(0)))
450 ExitBranch
->swapSuccessors();
452 // The old condition may be dead now, and may have even created a dead PHI
453 // (the original induction variable).
454 RecursivelyDeleteTriviallyDeadInstructions(OldCond
);
457 INITIALIZE_PASS_BEGIN(HardwareLoops
, DEBUG_TYPE
, HW_LOOPS_NAME
, false, false)
458 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass
)
459 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass
)
460 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass
)
461 INITIALIZE_PASS_END(HardwareLoops
, DEBUG_TYPE
, HW_LOOPS_NAME
, false, false)
463 FunctionPass
*llvm::createHardwareLoopsPass() { return new HardwareLoops(); }