1//===- LoopFlatten.cpp - Loop flattening pass------------------------------===//
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 pass flattens pairs nested loops into a single loop.
10//
11// The intention is to optimise loop nests like this, which together access an
12// array linearly:
13//
14// for (int i = 0; i < N; ++i)
15// for (int j = 0; j < M; ++j)
16// f(A[i*M+j]);
17//
18// into one loop:
19//
20// for (int i = 0; i < (N*M); ++i)
21// f(A[i]);
22//
23// It can also flatten loops where the induction variables are not used in the
24// loop. This is only worth doing if the induction variables are only used in an
25// expression like i*M+j. If they had any other uses, we would have to insert a
26// div/mod to reconstruct the original values, so this wouldn't be profitable.
27//
28// We also need to prove that N*M will not overflow. The preferred solution is
29// to widen the IV, which avoids overflow checks, so that is tried first. If
30// the IV cannot be widened, then we try to determine that this new tripcount
31// expression won't overflow.
32//
33// Q: Does LoopFlatten use SCEV?
34// Short answer: Yes and no.
35//
36// Long answer:
37// For this transformation to be valid, we require all uses of the induction
38// variables to be linear expressions of the form i*M+j. The different Loop
39// APIs are used to get some loop components like the induction variable,
40// compare statement, etc. In addition, we do some pattern matching to find the
41// linear expressions and other loop components like the loop increment. The
42// latter are examples of expressions that do use the induction variable, but
43// are safe to ignore when we check all uses to be of the form i*M+j. We keep
44// track of all of this in bookkeeping struct FlattenInfo.
45// We assume the loops to be canonical, i.e. starting at 0 and increment with
46// 1. This makes RHS of the compare the loop tripcount (with the right
47// predicate). We use SCEV to then sanity check that this tripcount matches
48// with the tripcount as computed by SCEV.
49//
50//===----------------------------------------------------------------------===//
51
52#include "llvm/Transforms/Scalar/LoopFlatten.h"
53#include "ScalarOptions.h"
54
55#include "llvm/ADT/Statistic.h"
56#include "llvm/Analysis/AssumptionCache.h"
57#include "llvm/Analysis/LoopAccessAnalysis.h"
58#include "llvm/Analysis/LoopInfo.h"
59#include "llvm/Analysis/LoopNestAnalysis.h"
60#include "llvm/Analysis/MemorySSAUpdater.h"
61#include "llvm/Analysis/OptimizationRemarkEmitter.h"
62#include "llvm/Analysis/ScalarEvolution.h"
63#include "llvm/Analysis/TargetTransformInfo.h"
64#include "llvm/Analysis/ValueTracking.h"
65#include "llvm/IR/Dominators.h"
66#include "llvm/IR/Function.h"
67#include "llvm/IR/IRBuilder.h"
68#include "llvm/IR/Module.h"
69#include "llvm/IR/PatternMatch.h"
70#include "llvm/Support/Debug.h"
71#include "llvm/Support/raw_ostream.h"
72#include "llvm/Transforms/Scalar/LoopPassManager.h"
73#include "llvm/Transforms/Utils/Local.h"
74#include "llvm/Transforms/Utils/LoopUtils.h"
75#include "llvm/Transforms/Utils/LoopVersioning.h"
76#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
77#include "llvm/Transforms/Utils/SimplifyIndVar.h"
78#include <optional>
79
80using namespace llvm;
81using namespace llvm::PatternMatch;
82
83#define DEBUG_TYPE "loop-flatten"
84
85STATISTIC(NumFlattened, "Number of loops flattened");
86
87namespace {
88// We require all uses of both induction variables to match this pattern:
89//
90// (OuterPHI * InnerTripCount) + InnerPHI
91//
92// I.e., it needs to be a linear expression of the induction variables and the
93// inner loop trip count. We keep track of all different expressions on which
94// checks will be performed in this bookkeeping struct.
95//
96struct FlattenInfo {
97 const ScalarOptions &Opts;
98 Loop *OuterLoop = nullptr; // The loop pair to be flattened.
99 Loop *InnerLoop = nullptr;
100
101 PHINode *InnerInductionPHI = nullptr; // These PHINodes correspond to loop
102 PHINode *OuterInductionPHI = nullptr; // induction variables, which are
103 // expected to start at zero and
104 // increment by one on each loop.
105
106 Value *InnerTripCount = nullptr; // The product of these two tripcounts
107 Value *OuterTripCount = nullptr; // will be the new flattened loop
108 // tripcount. Also used to recognise a
109 // linear expression that will be replaced.
110
111 SmallPtrSet<Value *, 4> LinearIVUses; // Contains the linear expressions
112 // of the form i*M+j that will be
113 // replaced.
114
115 BinaryOperator *InnerIncrement = nullptr; // Uses of induction variables in
116 BinaryOperator *OuterIncrement = nullptr; // loop control statements that
117 CondBrInst *InnerBranch = nullptr; // are safe to ignore.
118
119 CondBrInst *OuterBranch = nullptr; // The instruction that needs to be
120 // updated with new tripcount.
121
122 SmallPtrSet<PHINode *, 4> InnerPHIsToTransform;
123
124 bool Widened = false; // Whether this holds the flatten info before or after
125 // widening.
126
127 PHINode *NarrowInnerInductionPHI = nullptr; // Holds the old/narrow induction
128 PHINode *NarrowOuterInductionPHI = nullptr; // phis, i.e. the Phis before IV
129 // has been applied. Used to skip
130 // checks on phi nodes.
131
132 Value *NewTripCount = nullptr; // The tripcount of the flattened loop.
133
134 FlattenInfo(Loop *OL, Loop *IL)
135 : Opts(ScalarOptions::Global), OuterLoop(OL), InnerLoop(IL) {}
136
137 bool isNarrowInductionPhi(PHINode *Phi) {
138 // This can't be the narrow phi if we haven't widened the IV first.
139 if (!Widened)
140 return false;
141 return NarrowInnerInductionPHI == Phi || NarrowOuterInductionPHI == Phi;
142 }
143 bool isInnerLoopIncrement(User *U) {
144 return InnerIncrement == U;
145 }
146 bool isOuterLoopIncrement(User *U) {
147 return OuterIncrement == U;
148 }
149 bool isInnerLoopTest(User *U) {
150 return InnerBranch->getCondition() == U;
151 }
152
153 bool checkOuterInductionPhiUsers(SmallPtrSet<Value *, 4> &ValidOuterPHIUses) {
154 for (User *U : OuterInductionPHI->users()) {
155 if (isOuterLoopIncrement(U))
156 continue;
157
158 auto IsValidOuterPHIUses = [&] (User *U) -> bool {
159 LLVM_DEBUG(dbgs() << "Found use of outer induction variable: "; U->dump());
160 if (!ValidOuterPHIUses.count(Ptr: U)) {
161 LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n");
162 return false;
163 }
164 LLVM_DEBUG(dbgs() << "Use is optimisable\n");
165 return true;
166 };
167
168 if (auto *V = dyn_cast<TruncInst>(Val: U)) {
169 for (auto *K : V->users()) {
170 if (!IsValidOuterPHIUses(K))
171 return false;
172 }
173 continue;
174 }
175
176 if (!IsValidOuterPHIUses(U))
177 return false;
178 }
179 return true;
180 }
181
182 bool matchLinearIVUser(User *U, Value *InnerTripCount,
183 SmallPtrSet<Value *, 4> &ValidOuterPHIUses) {
184 LLVM_DEBUG(dbgs() << "Checking linear i*M+j expression for: "; U->dump());
185 Value *MatchedMul = nullptr;
186 Value *MatchedItCount = nullptr;
187
188 bool IsAdd = match(V: U, P: m_c_Add(L: m_Specific(V: InnerInductionPHI),
189 R: m_Value(V&: MatchedMul))) &&
190 match(V: MatchedMul, P: m_c_Mul(L: m_Specific(V: OuterInductionPHI),
191 R: m_Value(V&: MatchedItCount)));
192
193 // Matches the same pattern as above, except it also looks for truncs
194 // on the phi, which can be the result of widening the induction variables.
195 bool IsAddTrunc =
196 match(V: U, P: m_c_Add(L: m_Trunc(Op: m_Specific(V: InnerInductionPHI)),
197 R: m_Value(V&: MatchedMul))) &&
198 match(V: MatchedMul, P: m_c_Mul(L: m_Trunc(Op: m_Specific(V: OuterInductionPHI)),
199 R: m_Value(V&: MatchedItCount)));
200
201 // Matches the pattern ptr+i*M+j, with the two additions being done via GEP.
202 bool IsGEP = match(V: U, P: m_GEP(Ops: m_GEP(Ops: m_Value(), Ops: m_Value(V&: MatchedMul)),
203 Ops: m_Specific(V: InnerInductionPHI))) &&
204 match(V: MatchedMul, P: m_c_Mul(L: m_Specific(V: OuterInductionPHI),
205 R: m_Value(V&: MatchedItCount)));
206
207 if (!MatchedItCount)
208 return false;
209
210 LLVM_DEBUG(dbgs() << "Matched multiplication: "; MatchedMul->dump());
211 LLVM_DEBUG(dbgs() << "Matched iteration count: "; MatchedItCount->dump());
212
213 // The mul should not have any other uses. Widening may leave trivially dead
214 // uses, which can be ignored.
215 if (count_if(Range: MatchedMul->users(), P: [](User *U) {
216 return !isInstructionTriviallyDead(I: cast<Instruction>(Val: U));
217 }) > 1) {
218 LLVM_DEBUG(dbgs() << "Multiply has more than one use\n");
219 return false;
220 }
221
222 // Look through extends if the IV has been widened. Don't look through
223 // extends if we already looked through a trunc.
224 if (Widened && (IsAdd || IsGEP) &&
225 (isa<SExtInst>(Val: MatchedItCount) || isa<ZExtInst>(Val: MatchedItCount))) {
226 assert(MatchedItCount->getType() == InnerInductionPHI->getType() &&
227 "Unexpected type mismatch in types after widening");
228 MatchedItCount = isa<SExtInst>(Val: MatchedItCount)
229 ? dyn_cast<SExtInst>(Val: MatchedItCount)->getOperand(i_nocapture: 0)
230 : dyn_cast<ZExtInst>(Val: MatchedItCount)->getOperand(i_nocapture: 0);
231 }
232
233 LLVM_DEBUG(dbgs() << "Looking for inner trip count: ";
234 InnerTripCount->dump());
235
236 if ((IsAdd || IsAddTrunc || IsGEP) && MatchedItCount == InnerTripCount) {
237 LLVM_DEBUG(dbgs() << "Found. This sse is optimisable\n");
238 ValidOuterPHIUses.insert(Ptr: MatchedMul);
239 LinearIVUses.insert(Ptr: U);
240 return true;
241 }
242
243 LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n");
244 return false;
245 }
246
247 bool checkInnerInductionPhiUsers(SmallPtrSet<Value *, 4> &ValidOuterPHIUses) {
248 Value *SExtInnerTripCount = InnerTripCount;
249 if (Widened &&
250 (isa<SExtInst>(Val: InnerTripCount) || isa<ZExtInst>(Val: InnerTripCount)))
251 SExtInnerTripCount = cast<Instruction>(Val: InnerTripCount)->getOperand(i: 0);
252
253 for (User *U : InnerInductionPHI->users()) {
254 LLVM_DEBUG(dbgs() << "Checking User: "; U->dump());
255 if (isInnerLoopIncrement(U)) {
256 LLVM_DEBUG(dbgs() << "Use is inner loop increment, continuing\n");
257 continue;
258 }
259
260 // After widening the IVs, a trunc instruction might have been introduced,
261 // so look through truncs.
262 if (isa<TruncInst>(Val: U)) {
263 if (!U->hasOneUse())
264 return false;
265 U = *U->user_begin();
266 }
267
268 // If the use is in the compare (which is also the condition of the inner
269 // branch) then the compare has been altered by another transformation e.g
270 // icmp ult %inc, tripcount -> icmp ult %j, tripcount-1, where tripcount is
271 // a constant. Ignore this use as the compare gets removed later anyway.
272 if (isInnerLoopTest(U)) {
273 LLVM_DEBUG(dbgs() << "Use is the inner loop test, continuing\n");
274 continue;
275 }
276
277 if (!matchLinearIVUser(U, InnerTripCount: SExtInnerTripCount, ValidOuterPHIUses)) {
278 LLVM_DEBUG(dbgs() << "Not a linear IV user\n");
279 return false;
280 }
281 LLVM_DEBUG(dbgs() << "Linear IV users found!\n");
282 }
283 return true;
284 }
285};
286} // namespace
287
288static bool
289setLoopComponents(Value *&TC, Value *&TripCount, BinaryOperator *&Increment,
290 SmallPtrSetImpl<Instruction *> &IterationInstructions) {
291 TripCount = TC;
292 IterationInstructions.insert(Ptr: Increment);
293 LLVM_DEBUG(dbgs() << "Found Increment: "; Increment->dump());
294 LLVM_DEBUG(dbgs() << "Found trip count: "; TripCount->dump());
295 LLVM_DEBUG(dbgs() << "Successfully found all loop components\n");
296 return true;
297}
298
299// Given the RHS of the loop latch compare instruction, verify with SCEV
300// that this is indeed the loop tripcount.
301// TODO: This used to be a straightforward check but has grown to be quite
302// complicated now. It is therefore worth revisiting what the additional
303// benefits are of this (compared to relying on canonical loops and pattern
304// matching).
305static bool verifyTripCount(
306 Value *RHS, Loop *L, SmallPtrSetImpl<Instruction *> &IterationInstructions,
307 PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment,
308 CondBrInst *&BackBranch, ScalarEvolution *SE, bool IsWidened) {
309 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
310 if (isa<SCEVCouldNotCompute>(Val: BackedgeTakenCount)) {
311 LLVM_DEBUG(dbgs() << "Backedge-taken count is not predictable\n");
312 return false;
313 }
314
315 // Evaluating in the trip count's type can not overflow here as the overflow
316 // checks are performed in checkOverflow, but are first tried to avoid by
317 // widening the IV.
318 const SCEV *SCEVTripCount =
319 SE->getTripCountFromExitCount(ExitCount: BackedgeTakenCount,
320 EvalTy: BackedgeTakenCount->getType(), L);
321
322 const SCEV *SCEVRHS = SE->getSCEV(V: RHS);
323 if (SCEVRHS == SCEVTripCount)
324 return setLoopComponents(TC&: RHS, TripCount, Increment, IterationInstructions);
325 ConstantInt *ConstantRHS = dyn_cast<ConstantInt>(Val: RHS);
326 if (ConstantRHS) {
327 const SCEV *BackedgeTCExt = nullptr;
328 if (IsWidened) {
329 const SCEV *SCEVTripCountExt;
330 // Find the extended backedge taken count and extended trip count using
331 // SCEV. One of these should now match the RHS of the compare.
332 BackedgeTCExt = SE->getZeroExtendExpr(Op: BackedgeTakenCount, Ty: RHS->getType());
333 SCEVTripCountExt = SE->getTripCountFromExitCount(ExitCount: BackedgeTCExt,
334 EvalTy: RHS->getType(), L);
335 if (SCEVRHS != BackedgeTCExt && SCEVRHS != SCEVTripCountExt) {
336 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n");
337 return false;
338 }
339 }
340 // If the RHS of the compare is equal to the backedge taken count we need
341 // to add one to get the trip count.
342 if (SCEVRHS == BackedgeTCExt || SCEVRHS == BackedgeTakenCount) {
343 Value *NewRHS = ConstantInt::get(Context&: ConstantRHS->getContext(),
344 V: ConstantRHS->getValue() + 1);
345 return setLoopComponents(TC&: NewRHS, TripCount, Increment,
346 IterationInstructions);
347 }
348 return setLoopComponents(TC&: RHS, TripCount, Increment, IterationInstructions);
349 }
350 // If the RHS isn't a constant then check that the reason it doesn't match
351 // the SCEV trip count is because the RHS is a ZExt or SExt instruction
352 // (and take the trip count to be the RHS).
353 if (!IsWidened) {
354 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n");
355 return false;
356 }
357 auto *TripCountInst = dyn_cast<Instruction>(Val: RHS);
358 if (!TripCountInst) {
359 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n");
360 return false;
361 }
362 if ((!isa<ZExtInst>(Val: TripCountInst) && !isa<SExtInst>(Val: TripCountInst)) ||
363 SE->getSCEV(V: TripCountInst->getOperand(i: 0)) != SCEVTripCount) {
364 LLVM_DEBUG(dbgs() << "Could not find valid extended trip count\n");
365 return false;
366 }
367 return setLoopComponents(TC&: RHS, TripCount, Increment, IterationInstructions);
368}
369
370// Finds the induction variable, increment and trip count for a simple loop that
371// we can flatten.
372static bool findLoopComponents(
373 Loop *L, SmallPtrSetImpl<Instruction *> &IterationInstructions,
374 PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment,
375 CondBrInst *&BackBranch, ScalarEvolution *SE, bool IsWidened) {
376 LLVM_DEBUG(dbgs() << "Finding components of loop: " << L->getName() << "\n");
377
378 if (!L->isLoopSimplifyForm()) {
379 LLVM_DEBUG(dbgs() << "Loop is not in normal form\n");
380 return false;
381 }
382
383 // Currently, to simplify the implementation, the Loop induction variable must
384 // start at zero and increment with a step size of one.
385 if (!L->isCanonical(SE&: *SE)) {
386 LLVM_DEBUG(dbgs() << "Loop is not canonical\n");
387 return false;
388 }
389
390 // There must be exactly one exiting block, and it must be the same at the
391 // latch.
392 BasicBlock *Latch = L->getLoopLatch();
393 if (L->getExitingBlock() != Latch) {
394 LLVM_DEBUG(dbgs() << "Exiting and latch block are different\n");
395 return false;
396 }
397
398 // Find the induction PHI. If there is no induction PHI, we can't do the
399 // transformation. TODO: could other variables trigger this? Do we have to
400 // search for the best one?
401 InductionPHI = L->getInductionVariable(SE&: *SE);
402 if (!InductionPHI) {
403 LLVM_DEBUG(dbgs() << "Could not find induction PHI\n");
404 return false;
405 }
406 LLVM_DEBUG(dbgs() << "Found induction PHI: "; InductionPHI->dump());
407
408 bool ContinueOnTrue = L->contains(BB: Latch->getTerminator()->getSuccessor(Idx: 0));
409 auto IsValidPredicate = [&](ICmpInst::Predicate Pred) {
410 if (ContinueOnTrue)
411 return Pred == CmpInst::ICMP_NE || Pred == CmpInst::ICMP_ULT;
412 else
413 return Pred == CmpInst::ICMP_EQ;
414 };
415
416 // Find Compare and make sure it is valid. getLatchCmpInst checks that the
417 // back branch of the latch is conditional.
418 ICmpInst *Compare = L->getLatchCmpInst();
419 if (!Compare || !IsValidPredicate(Compare->getUnsignedPredicate()) ||
420 Compare->hasNUsesOrMore(N: 2)) {
421 LLVM_DEBUG(dbgs() << "Could not find valid comparison\n");
422 return false;
423 }
424 BackBranch = cast<CondBrInst>(Val: Latch->getTerminator());
425 IterationInstructions.insert(Ptr: BackBranch);
426 LLVM_DEBUG(dbgs() << "Found back branch: "; BackBranch->dump());
427 IterationInstructions.insert(Ptr: Compare);
428 LLVM_DEBUG(dbgs() << "Found comparison: "; Compare->dump());
429
430 // Find increment and trip count.
431 // There are exactly 2 incoming values to the induction phi; one from the
432 // pre-header and one from the latch. The incoming latch value is the
433 // increment variable.
434 Increment =
435 cast<BinaryOperator>(Val: InductionPHI->getIncomingValueForBlock(BB: Latch));
436 if ((Compare->getOperand(i_nocapture: 0) != Increment || !Increment->hasNUses(N: 2)) &&
437 !Increment->hasNUses(N: 1)) {
438 LLVM_DEBUG(dbgs() << "Could not find valid increment\n");
439 return false;
440 }
441 // The trip count is the RHS of the compare. If this doesn't match the trip
442 // count computed by SCEV then this is because the trip count variable
443 // has been widened so the types don't match, or because it is a constant and
444 // another transformation has changed the compare (e.g. icmp ult %inc,
445 // tripcount -> icmp ult %j, tripcount-1), or both.
446 Value *RHS = Compare->getOperand(i_nocapture: 1);
447
448 return verifyTripCount(RHS, L, IterationInstructions, InductionPHI, TripCount,
449 Increment, BackBranch, SE, IsWidened);
450}
451
452static bool checkPHIs(FlattenInfo &FI, const TargetTransformInfo *TTI) {
453 // All PHIs in the inner and outer headers must either be:
454 // - The induction PHI, which we are going to rewrite as one induction in
455 // the new loop. This is already checked by findLoopComponents.
456 // - An outer header PHI with all incoming values from outside the loop.
457 // LoopSimplify guarantees we have a pre-header, so we don't need to
458 // worry about that here.
459 // - Pairs of PHIs in the inner and outer headers, which implement a
460 // loop-carried dependency that will still be valid in the new loop. To
461 // be valid, this variable must be modified only in the inner loop.
462
463 // The set of PHI nodes in the outer loop header that we know will still be
464 // valid after the transformation. These will not need to be modified (with
465 // the exception of the induction variable), but we do need to check that
466 // there are no unsafe PHI nodes.
467 SmallPtrSet<PHINode *, 4> SafeOuterPHIs;
468 SafeOuterPHIs.insert(Ptr: FI.OuterInductionPHI);
469
470 // Check that all PHI nodes in the inner loop header match one of the valid
471 // patterns.
472 for (PHINode &InnerPHI : FI.InnerLoop->getHeader()->phis()) {
473 // The induction PHIs break these rules, and that's OK because we treat
474 // them specially when doing the transformation.
475 if (&InnerPHI == FI.InnerInductionPHI)
476 continue;
477 if (FI.isNarrowInductionPhi(Phi: &InnerPHI))
478 continue;
479
480 // Each inner loop PHI node must have two incoming values/blocks - one
481 // from the pre-header, and one from the latch.
482 assert(InnerPHI.getNumIncomingValues() == 2);
483 Value *PreHeaderValue =
484 InnerPHI.getIncomingValueForBlock(BB: FI.InnerLoop->getLoopPreheader());
485 Value *LatchValue =
486 InnerPHI.getIncomingValueForBlock(BB: FI.InnerLoop->getLoopLatch());
487
488 // The incoming value from the outer loop must be the PHI node in the
489 // outer loop header, with no modifications made in the top of the outer
490 // loop.
491 PHINode *OuterPHI = dyn_cast<PHINode>(Val: PreHeaderValue);
492 if (!OuterPHI || OuterPHI->getParent() != FI.OuterLoop->getHeader()) {
493 LLVM_DEBUG(dbgs() << "value modified in top of outer loop\n");
494 return false;
495 }
496
497 // The other incoming value must come from the inner loop, without any
498 // modifications in the tail end of the outer loop. We are in LCSSA form,
499 // so this will actually be a PHI in the inner loop's exit block, which
500 // only uses values from inside the inner loop.
501 PHINode *LCSSAPHI = dyn_cast<PHINode>(
502 Val: OuterPHI->getIncomingValueForBlock(BB: FI.OuterLoop->getLoopLatch()));
503 if (!LCSSAPHI) {
504 LLVM_DEBUG(dbgs() << "could not find LCSSA PHI\n");
505 return false;
506 }
507
508 // The value used by the LCSSA PHI must be the same one that the inner
509 // loop's PHI uses.
510 if (LCSSAPHI->hasConstantValue() != LatchValue) {
511 LLVM_DEBUG(
512 dbgs() << "LCSSA PHI incoming value does not match latch value\n");
513 return false;
514 }
515
516 LLVM_DEBUG(dbgs() << "PHI pair is safe:\n");
517 LLVM_DEBUG(dbgs() << " Inner: "; InnerPHI.dump());
518 LLVM_DEBUG(dbgs() << " Outer: "; OuterPHI->dump());
519 SafeOuterPHIs.insert(Ptr: OuterPHI);
520 FI.InnerPHIsToTransform.insert(Ptr: &InnerPHI);
521 }
522
523 for (PHINode &OuterPHI : FI.OuterLoop->getHeader()->phis()) {
524 if (FI.isNarrowInductionPhi(Phi: &OuterPHI))
525 continue;
526 if (!SafeOuterPHIs.count(Ptr: &OuterPHI)) {
527 LLVM_DEBUG(dbgs() << "found unsafe PHI in outer loop: "; OuterPHI.dump());
528 return false;
529 }
530 }
531
532 LLVM_DEBUG(dbgs() << "checkPHIs: OK\n");
533 return true;
534}
535
536static bool
537checkOuterLoopInsts(FlattenInfo &FI,
538 SmallPtrSetImpl<Instruction *> &IterationInstructions,
539 const TargetTransformInfo *TTI) {
540 // Check for instructions in the outer but not inner loop. If any of these
541 // have side-effects then this transformation is not legal, and if there is
542 // a significant amount of code here which can't be optimised out that it's
543 // not profitable (as these instructions would get executed for each
544 // iteration of the inner loop).
545 InstructionCost RepeatedInstrCost = 0;
546 for (auto *B : FI.OuterLoop->getBlocks()) {
547 if (FI.InnerLoop->contains(BB: B))
548 continue;
549
550 for (auto &I : *B) {
551 if (!isa<PHINode>(Val: &I) && !I.isTerminator() &&
552 !isSafeToSpeculativelyExecute(I: &I)) {
553 LLVM_DEBUG(dbgs() << "Cannot flatten because instruction may have "
554 "side effects: ";
555 I.dump());
556 return false;
557 }
558 // The execution count of the outer loop's iteration instructions
559 // (increment, compare and branch) will be increased, but the
560 // equivalent instructions will be removed from the inner loop, so
561 // they make a net difference of zero.
562 if (IterationInstructions.count(Ptr: &I))
563 continue;
564 // The unconditional branch to the inner loop's header will turn into
565 // a fall-through, so adds no cost.
566 UncondBrInst *Br = dyn_cast<UncondBrInst>(Val: &I);
567 if (Br && Br->getSuccessor() == FI.InnerLoop->getHeader())
568 continue;
569 // Multiplies of the outer iteration variable and inner iteration
570 // count will be optimised out.
571 if (match(V: &I, P: m_c_Mul(L: m_Specific(V: FI.OuterInductionPHI),
572 R: m_Specific(V: FI.InnerTripCount))))
573 continue;
574 InstructionCost Cost =
575 TTI->getInstructionCost(U: &I, CostKind: TargetTransformInfo::TCK_SizeAndLatency);
576 LLVM_DEBUG(dbgs() << "Cost " << Cost << ": "; I.dump());
577 RepeatedInstrCost += Cost;
578 }
579 }
580
581 LLVM_DEBUG(dbgs() << "Cost of instructions that will be repeated: "
582 << RepeatedInstrCost << "\n");
583 // Bail out if flattening the loops would cause instructions in the outer
584 // loop but not in the inner loop to be executed extra times.
585 if (RepeatedInstrCost > FI.Opts.loop_flatten_cost_threshold) {
586 LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: not profitable, bailing.\n");
587 return false;
588 }
589
590 LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: OK\n");
591 return true;
592}
593
594
595
596// We require all uses of both induction variables to match this pattern:
597//
598// (OuterPHI * InnerTripCount) + InnerPHI
599//
600// Any uses of the induction variables not matching that pattern would
601// require a div/mod to reconstruct in the flattened loop, so the
602// transformation wouldn't be profitable.
603static bool checkIVUsers(FlattenInfo &FI) {
604 // Check that all uses of the inner loop's induction variable match the
605 // expected pattern, recording the uses of the outer IV.
606 SmallPtrSet<Value *, 4> ValidOuterPHIUses;
607 if (!FI.checkInnerInductionPhiUsers(ValidOuterPHIUses))
608 return false;
609
610 // Check that there are no uses of the outer IV other than the ones found
611 // as part of the pattern above.
612 if (!FI.checkOuterInductionPhiUsers(ValidOuterPHIUses))
613 return false;
614
615 LLVM_DEBUG(dbgs() << "checkIVUsers: OK\n";
616 dbgs() << "Found " << FI.LinearIVUses.size()
617 << " value(s) that can be replaced:\n";
618 for (Value *V : FI.LinearIVUses) {
619 dbgs() << " ";
620 V->dump();
621 });
622 return true;
623}
624
625// Return an OverflowResult dependant on if overflow of the multiplication of
626// InnerTripCount and OuterTripCount can be assumed not to happen.
627static OverflowResult checkOverflow(FlattenInfo &FI, DominatorTree *DT,
628 AssumptionCache *AC) {
629 Function *F = FI.OuterLoop->getHeader()->getParent();
630 const DataLayout &DL = F->getDataLayout();
631
632 // For debugging/testing.
633 if (FI.Opts.loop_flatten_assume_no_overflow)
634 return OverflowResult::NeverOverflows;
635
636 // Check if the multiply could not overflow due to known ranges of the
637 // input values.
638 OverflowResult OR = computeOverflowForUnsignedMul(
639 LHS: FI.InnerTripCount, RHS: FI.OuterTripCount,
640 SQ: SimplifyQuery(DL, DT, AC,
641 FI.OuterLoop->getLoopPreheader()->getTerminator()));
642 if (OR != OverflowResult::MayOverflow)
643 return OR;
644
645 auto CheckGEP = [&](GetElementPtrInst *GEP, Value *GEPOperand) {
646 for (Value *GEPUser : GEP->users()) {
647 auto *GEPUserInst = cast<Instruction>(Val: GEPUser);
648 if (!isa<LoadInst>(Val: GEPUserInst) &&
649 !(isa<StoreInst>(Val: GEPUserInst) && GEP == GEPUserInst->getOperand(i: 1)))
650 continue;
651 if (!isGuaranteedToExecuteForEveryIteration(I: GEPUserInst, L: FI.InnerLoop))
652 continue;
653 // The IV is used as the operand of a GEP which dominates the loop
654 // latch, and the IV is at least as wide as the address space of the
655 // GEP. In this case, the GEP would wrap around the address space
656 // before the IV increment wraps, which would be UB.
657 if (GEP->isInBounds() &&
658 GEPOperand->getType()->getIntegerBitWidth() >=
659 DL.getPointerTypeSizeInBits(GEP->getType())) {
660 LLVM_DEBUG(
661 dbgs() << "use of linear IV would be UB if overflow occurred: ";
662 GEP->dump());
663 return true;
664 }
665 }
666 return false;
667 };
668
669 // Check if any IV user is, or is used by, a GEP that would cause UB if the
670 // multiply overflows.
671 for (Value *V : FI.LinearIVUses) {
672 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: V))
673 if (GEP->getNumIndices() == 1 && CheckGEP(GEP, GEP->getOperand(i_nocapture: 1)))
674 return OverflowResult::NeverOverflows;
675 for (Value *U : V->users())
676 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: U))
677 if (CheckGEP(GEP, V))
678 return OverflowResult::NeverOverflows;
679 }
680
681 return OverflowResult::MayOverflow;
682}
683
684static bool CanFlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI,
685 ScalarEvolution *SE, AssumptionCache *AC,
686 const TargetTransformInfo *TTI) {
687 SmallPtrSet<Instruction *, 8> IterationInstructions;
688 if (!findLoopComponents(L: FI.InnerLoop, IterationInstructions,
689 InductionPHI&: FI.InnerInductionPHI, TripCount&: FI.InnerTripCount,
690 Increment&: FI.InnerIncrement, BackBranch&: FI.InnerBranch, SE, IsWidened: FI.Widened))
691 return false;
692 if (!findLoopComponents(L: FI.OuterLoop, IterationInstructions,
693 InductionPHI&: FI.OuterInductionPHI, TripCount&: FI.OuterTripCount,
694 Increment&: FI.OuterIncrement, BackBranch&: FI.OuterBranch, SE, IsWidened: FI.Widened))
695 return false;
696
697 // Both of the loop trip count values must be invariant in the outer loop
698 // (non-instructions are all inherently invariant).
699 if (!FI.OuterLoop->isLoopInvariant(V: FI.InnerTripCount)) {
700 LLVM_DEBUG(dbgs() << "inner loop trip count not invariant\n");
701 return false;
702 }
703 if (!FI.OuterLoop->isLoopInvariant(V: FI.OuterTripCount)) {
704 LLVM_DEBUG(dbgs() << "outer loop trip count not invariant\n");
705 return false;
706 }
707
708 if (!checkPHIs(FI, TTI))
709 return false;
710
711 // FIXME: it should be possible to handle different types correctly.
712 if (FI.InnerInductionPHI->getType() != FI.OuterInductionPHI->getType())
713 return false;
714
715 if (!checkOuterLoopInsts(FI, IterationInstructions, TTI))
716 return false;
717
718 // Find the values in the loop that can be replaced with the linearized
719 // induction variable, and check that there are no other uses of the inner
720 // or outer induction variable. If there were, we could still do this
721 // transformation, but we'd have to insert a div/mod to calculate the
722 // original IVs, so it wouldn't be profitable.
723 if (!checkIVUsers(FI))
724 return false;
725
726 LLVM_DEBUG(dbgs() << "CanFlattenLoopPair: OK\n");
727 return true;
728}
729
730static bool DoFlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI,
731 ScalarEvolution *SE, AssumptionCache *AC,
732 const TargetTransformInfo *TTI, LPMUpdater *U,
733 MemorySSAUpdater *MSSAU) {
734 Function *F = FI.OuterLoop->getHeader()->getParent();
735 LLVM_DEBUG(dbgs() << "Checks all passed, doing the transformation\n");
736 {
737 using namespace ore;
738 OptimizationRemark Remark(DEBUG_TYPE, "Flattened", FI.InnerLoop->getStartLoc(),
739 FI.InnerLoop->getHeader());
740 OptimizationRemarkEmitter ORE(F);
741 Remark << "Flattened into outer loop";
742 ORE.emit(OptDiag&: Remark);
743 }
744
745 if (!FI.NewTripCount) {
746 FI.NewTripCount = BinaryOperator::CreateMul(
747 V1: FI.InnerTripCount, V2: FI.OuterTripCount, Name: "flatten.tripcount",
748 InsertBefore: FI.OuterLoop->getLoopPreheader()->getTerminator()->getIterator());
749 LLVM_DEBUG(dbgs() << "Created new trip count in preheader: ";
750 FI.NewTripCount->dump());
751 }
752
753 // Fix up PHI nodes that take values from the inner loop back-edge, which
754 // we are about to remove.
755 FI.InnerInductionPHI->removeIncomingValue(BB: FI.InnerLoop->getLoopLatch());
756
757 // The old Phi will be optimised away later, but for now we can't leave
758 // leave it in an invalid state, so are updating them too.
759 for (PHINode *PHI : FI.InnerPHIsToTransform)
760 PHI->removeIncomingValue(BB: FI.InnerLoop->getLoopLatch());
761
762 // Modify the trip count of the outer loop to be the product of the two
763 // trip counts.
764 cast<User>(Val: FI.OuterBranch->getCondition())->setOperand(i: 1, Val: FI.NewTripCount);
765
766 // Replace the inner loop backedge with an unconditional branch to the exit.
767 BasicBlock *InnerExitBlock = FI.InnerLoop->getExitBlock();
768 BasicBlock *InnerExitingBlock = FI.InnerLoop->getExitingBlock();
769 Instruction *Term = InnerExitingBlock->getTerminator();
770 Instruction *BI = UncondBrInst::Create(Target: InnerExitBlock, InsertBefore: InnerExitingBlock);
771 BI->setDebugLoc(Term->getDebugLoc());
772 Term->eraseFromParent();
773
774 // Update the DomTree and MemorySSA.
775 DT->deleteEdge(From: InnerExitingBlock, To: FI.InnerLoop->getHeader());
776 if (MSSAU)
777 MSSAU->removeEdge(From: InnerExitingBlock, To: FI.InnerLoop->getHeader());
778
779 // Replace all uses of the polynomial calculated from the two induction
780 // variables with the one new one.
781 IRBuilder<> Builder(FI.OuterInductionPHI->getParent()->getTerminator());
782 for (Value *V : FI.LinearIVUses) {
783 Value *OuterValue = FI.OuterInductionPHI;
784 if (FI.Widened)
785 OuterValue = Builder.CreateTrunc(V: FI.OuterInductionPHI, DestTy: V->getType(),
786 Name: "flatten.trunciv");
787
788 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: V)) {
789 // Replace the GEP with one that uses OuterValue as the offset.
790 auto *InnerGEP = cast<GetElementPtrInst>(Val: GEP->getOperand(i_nocapture: 0));
791 Value *Base = InnerGEP->getOperand(i_nocapture: 0);
792 // When the base of the GEP doesn't dominate the outer induction phi then
793 // we need to insert the new GEP where the old GEP was.
794 if (!DT->dominates(Def: Base, User: &*Builder.GetInsertPoint()))
795 Builder.SetInsertPoint(cast<Instruction>(Val: V));
796 OuterValue =
797 Builder.CreateGEP(Ty: GEP->getSourceElementType(), Ptr: Base, IdxList: OuterValue,
798 Name: "flatten." + V->getName(),
799 NW: GEP->isInBounds() && InnerGEP->isInBounds());
800 }
801
802 LLVM_DEBUG(dbgs() << "Replacing: "; V->dump(); dbgs() << "with: ";
803 OuterValue->dump());
804 V->replaceAllUsesWith(V: OuterValue);
805 }
806
807 // Tell LoopInfo, SCEV and the pass manager that the inner loop has been
808 // deleted, and invalidate any outer loop information.
809 SE->forgetLoop(L: FI.OuterLoop);
810 SE->forgetBlockAndLoopDispositions();
811 if (U)
812 U->markLoopAsDeleted(L&: *FI.InnerLoop, Name: FI.InnerLoop->getName());
813 LI->erase(L: FI.InnerLoop);
814
815 // Increment statistic value.
816 NumFlattened++;
817
818 return true;
819}
820
821static bool CanWidenIV(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI,
822 ScalarEvolution *SE, AssumptionCache *AC,
823 const TargetTransformInfo *TTI) {
824 if (!FI.Opts.loop_flatten_widen_iv) {
825 LLVM_DEBUG(dbgs() << "Widening the IVs is disabled\n");
826 return false;
827 }
828
829 LLVM_DEBUG(dbgs() << "Try widening the IVs\n");
830 Module *M = FI.InnerLoop->getHeader()->getParent()->getParent();
831 auto &DL = M->getDataLayout();
832 auto *InnerType = FI.InnerInductionPHI->getType();
833 auto *OuterType = FI.OuterInductionPHI->getType();
834 unsigned MaxLegalSize = DL.getLargestLegalIntTypeSizeInBits();
835 auto *MaxLegalType = DL.getLargestLegalIntType(C&: M->getContext());
836
837 // If both induction types are less than the maximum legal integer width,
838 // promote both to the widest type available so we know calculating
839 // (OuterTripCount * InnerTripCount) as the new trip count is safe.
840 if (InnerType != OuterType ||
841 InnerType->getScalarSizeInBits() >= MaxLegalSize ||
842 MaxLegalType->getScalarSizeInBits() <
843 InnerType->getScalarSizeInBits() * 2) {
844 LLVM_DEBUG(dbgs() << "Can't widen the IV\n");
845 return false;
846 }
847
848 SCEVExpander Rewriter(*SE, "loopflatten");
849 SmallVector<WeakTrackingVH, 4> DeadInsts;
850 unsigned ElimExt = 0;
851 unsigned Widened = 0;
852
853 auto CreateWideIV = [&](WideIVInfo WideIV, bool &Deleted) -> bool {
854 PHINode *WidePhi =
855 createWideIV(WI: WideIV, LI, SE, Rewriter, DT, DeadInsts, NumElimExt&: ElimExt, NumWidened&: Widened,
856 HasGuards: true /* HasGuards */, UsePostIncrementRanges: true /* UsePostIncrementRanges */);
857 if (!WidePhi)
858 return false;
859 SE->forgetLoop(L: FI.OuterLoop);
860 LLVM_DEBUG(dbgs() << "Created wide phi: "; WidePhi->dump());
861 LLVM_DEBUG(dbgs() << "Deleting old phi: "; WideIV.NarrowIV->dump());
862 Deleted = RecursivelyDeleteDeadPHINode(PN: WideIV.NarrowIV);
863 return true;
864 };
865
866 bool Deleted;
867 if (!CreateWideIV({.NarrowIV: FI.InnerInductionPHI, .WidestNativeType: MaxLegalType, .IsSigned: false}, Deleted))
868 return false;
869 // Add the narrow phi to list, so that it will be adjusted later when the
870 // the transformation is performed.
871 if (!Deleted)
872 FI.InnerPHIsToTransform.insert(Ptr: FI.InnerInductionPHI);
873
874 if (!CreateWideIV({.NarrowIV: FI.OuterInductionPHI, .WidestNativeType: MaxLegalType, .IsSigned: false}, Deleted))
875 return false;
876
877 assert(Widened && "Widened IV expected");
878 FI.Widened = true;
879
880 // Save the old/narrow induction phis, which we need to ignore in CheckPHIs.
881 FI.NarrowInnerInductionPHI = FI.InnerInductionPHI;
882 FI.NarrowOuterInductionPHI = FI.OuterInductionPHI;
883
884 // After widening, rediscover all the loop components.
885 return CanFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
886}
887
888static bool FlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI,
889 ScalarEvolution *SE, AssumptionCache *AC,
890 const TargetTransformInfo *TTI, LPMUpdater *U,
891 MemorySSAUpdater *MSSAU,
892 const LoopAccessInfo &LAI) {
893 LLVM_DEBUG(
894 dbgs() << "Loop flattening running on outer loop "
895 << FI.OuterLoop->getHeader()->getName() << " and inner loop "
896 << FI.InnerLoop->getHeader()->getName() << " in "
897 << FI.OuterLoop->getHeader()->getParent()->getName() << "\n");
898
899 if (!CanFlattenLoopPair(FI, DT, LI, SE, AC, TTI))
900 return false;
901
902 // Check if we can widen the induction variables to avoid overflow checks.
903 bool CanFlatten = CanWidenIV(FI, DT, LI, SE, AC, TTI);
904
905 // It can happen that after widening of the IV, flattening may not be
906 // possible/happening, e.g. when it is deemed unprofitable. So bail here if
907 // that is the case.
908 // TODO: IV widening without performing the actual flattening transformation
909 // is not ideal. While this codegen change should not matter much, it is an
910 // unnecessary change which is better to avoid. It's unlikely this happens
911 // often, because if it's unprofitibale after widening, it should be
912 // unprofitabe before widening as checked in the first round of checks. But
913 // 'RepeatedInstructionThreshold' is set to only 2, which can probably be
914 // relaxed. Because this is making a code change (the IV widening, but not
915 // the flattening), we return true here.
916 if (FI.Widened && !CanFlatten)
917 return true;
918
919 // If we have widened and can perform the transformation, do that here.
920 if (CanFlatten)
921 return DoFlattenLoopPair(FI, DT, LI, SE, AC, TTI, U, MSSAU);
922
923 // Otherwise, if we haven't widened the IV, check if the new iteration
924 // variable might overflow. In this case, we need to version the loop, and
925 // select the original version at runtime if the iteration space is too
926 // large.
927 OverflowResult OR = checkOverflow(FI, DT, AC);
928 if (OR == OverflowResult::AlwaysOverflowsHigh ||
929 OR == OverflowResult::AlwaysOverflowsLow) {
930 LLVM_DEBUG(dbgs() << "Multiply would always overflow, so not profitable\n");
931 return false;
932 } else if (OR == OverflowResult::MayOverflow) {
933 Module *M = FI.OuterLoop->getHeader()->getParent()->getParent();
934 const DataLayout &DL = M->getDataLayout();
935 if (!FI.Opts.loop_flatten_version_loops) {
936 LLVM_DEBUG(dbgs() << "Multiply might overflow, not flattening\n");
937 return false;
938 } else if (!DL.isLegalInteger(
939 Width: FI.OuterTripCount->getType()->getScalarSizeInBits())) {
940 // If the trip count type isn't legal then it won't be possible to check
941 // for overflow using only a single multiply instruction, so don't
942 // flatten.
943 LLVM_DEBUG(
944 dbgs() << "Can't check overflow efficiently, not flattening\n");
945 return false;
946 }
947 LLVM_DEBUG(dbgs() << "Multiply might overflow, versioning loop\n");
948
949 // Version the loop. The overflow check isn't a runtime pointer check, so we
950 // pass an empty list of runtime pointer checks, causing LoopVersioning to
951 // emit 'false' as the branch condition, and add our own check afterwards.
952 BasicBlock *CheckBlock = FI.OuterLoop->getLoopPreheader();
953 ArrayRef<RuntimePointerCheck> Checks(nullptr, nullptr);
954 LoopVersioning LVer(LAI, Checks, FI.OuterLoop, LI, DT, SE, MSSAU);
955 LVer.versionLoop();
956
957 // Check for overflow by calculating the new tripcount using
958 // umul_with_overflow and then checking if it overflowed.
959 CondBrInst *Br = cast<CondBrInst>(Val: CheckBlock->getTerminator());
960 assert(match(Br->getCondition(), m_Zero()) &&
961 "Expected branch condition to be false");
962 IRBuilder<> Builder(Br);
963 Value *Call = Builder.CreateIntrinsic(
964 ID: Intrinsic::umul_with_overflow, OverloadTypes: FI.OuterTripCount->getType(),
965 Args: {FI.OuterTripCount, FI.InnerTripCount},
966 /*FMFSource=*/nullptr, Name: "flatten.mul");
967 FI.NewTripCount = Builder.CreateExtractValue(Agg: Call, Idxs: 0, Name: "flatten.tripcount");
968 Value *Overflow = Builder.CreateExtractValue(Agg: Call, Idxs: 1, Name: "flatten.overflow");
969 Br->setCondition(Overflow);
970 } else {
971 LLVM_DEBUG(dbgs() << "Multiply cannot overflow, modifying loop in-place\n");
972 }
973
974 return DoFlattenLoopPair(FI, DT, LI, SE, AC, TTI, U, MSSAU);
975}
976
977PreservedAnalyses LoopFlattenPass::run(LoopNest &LN, LoopAnalysisManager &LAM,
978 LoopStandardAnalysisResults &AR,
979 LPMUpdater &U) {
980
981 bool Changed = false;
982
983 std::optional<MemorySSAUpdater> MSSAU;
984 if (AR.MSSA) {
985 MSSAU = MemorySSAUpdater(AR.MSSA);
986 if (VerifyMemorySSA)
987 AR.MSSA->verifyMemorySSA();
988 }
989
990 // The loop flattening pass requires loops to be
991 // in simplified form, and also needs LCSSA. Running
992 // this pass will simplify all loops that contain inner loops,
993 // regardless of whether anything ends up being flattened.
994 LoopAccessInfoManager LAIM(AR.SE, AR.AA, AR.DT, AR.LI, &AR.TTI, nullptr,
995 &AR.AC);
996 for (Loop *InnerLoop : LN.getLoops()) {
997 auto *OuterLoop = InnerLoop->getParentLoop();
998 if (!OuterLoop)
999 continue;
1000 FlattenInfo FI(OuterLoop, InnerLoop);
1001 Changed |=
1002 FlattenLoopPair(FI, DT: &AR.DT, LI: &AR.LI, SE: &AR.SE, AC: &AR.AC, TTI: &AR.TTI, U: &U,
1003 MSSAU: MSSAU ? &*MSSAU : nullptr, LAI: LAIM.getInfo(L&: *OuterLoop));
1004 }
1005
1006 if (!Changed)
1007 return PreservedAnalyses::all();
1008
1009 if (AR.MSSA && VerifyMemorySSA)
1010 AR.MSSA->verifyMemorySSA();
1011
1012 auto PA = getLoopPassPreservedAnalyses();
1013 if (AR.MSSA)
1014 PA.preserve<MemorySSAAnalysis>();
1015 return PA;
1016}
1017