Skip to content

Commit 2a56dea

Browse files
1997alirezaa00917109
1997alireza
authored and
a00917109
committed
[DependenceAnalysis] Extending SIV to handle fusable loops
When there is a dependency between two memory instructions in separate fusable loops, SIV will be able to test them and compute the direction and the distance of the dependency. Two loop levels are considered fusable if they have the same tripcount and depth.
1 parent a26c3e9 commit 2a56dea

File tree

3 files changed

+791
-206
lines changed

3 files changed

+791
-206
lines changed

‎llvm/include/llvm/Analysis/DependenceAnalysis.h

Lines changed: 140 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -82,6 +82,17 @@ class LLVM_ABI Dependence {
8282
/// Dependence::DVEntry - Each level in the distance/direction vector
8383
/// has a direction (or perhaps a union of several directions), and
8484
/// perhaps a distance.
85+
/// The dependency information could be across a single loop level or across
86+
/// two separate levels that are candidates for fusion. Two levels are
87+
/// considered fusable if they can be interpreted as a single fused loop,
88+
/// i.e., have the same trip count and the same nesting depth.
89+
/// For example, loops b and c are similar and considered as fusable loops:
90+
/// for (a = ...) {
91+
/// for (b = 0; b < 10; b++) {
92+
/// }
93+
/// for (c = 0; c < 10; c++) {
94+
/// }
95+
/// }
8596
struct DVEntry {
8697
enum : unsigned char {
8798
NONE = 0,
@@ -144,12 +155,25 @@ class LLVM_ABI Dependence {
144155
/// source and destination of the dependence.
145156
virtual unsigned getLevels() const { return 0; }
146157

147-
/// getDirection - Returns the direction associated with a particular level.
148-
virtual unsigned getDirection(unsigned Level) const { return DVEntry::ALL; }
158+
/// getFusableLevels - Returns the number of fusable loops surrounding
159+
/// the source and destination of the dependence.
160+
virtual unsigned getFusableLevels() const { return 0; }
149161

150-
/// getDistance - Returns the distance (or NULL) associated with a particular
151-
/// level.
152-
virtual const SCEV *getDistance(unsigned Level) const { return nullptr; }
162+
/// getDVEntry - Returns the DV entry associated with a regular or a
163+
/// fusable level
164+
DVEntry getDVEntry(unsigned Level, bool Fusable) const;
165+
166+
/// getDirection - Returns the direction associated with a particular
167+
/// common or fusable level.
168+
virtual unsigned getDirection(unsigned Level, bool Fusable = false) const {
169+
return DVEntry::ALL;
170+
}
171+
172+
/// getDistance - Returns the distance (or NULL) associated with a
173+
/// particular common or fusable level.
174+
virtual const SCEV *getDistance(unsigned Level, bool Fusable = false) const {
175+
return nullptr;
176+
}
153177

154178
/// Check if the direction vector is negative. A negative direction
155179
/// vector means Src and Dst are reversed in the actual program.
@@ -162,21 +186,32 @@ class LLVM_ABI Dependence {
162186
virtual bool normalize(ScalarEvolution *SE) { return false; }
163187

164188
/// isPeelFirst - Returns true if peeling the first iteration from
165-
/// this loop will break this dependence.
166-
virtual bool isPeelFirst(unsigned Level) const { return false; }
189+
/// this regular or fusable loop level will break this dependence.
190+
virtual bool isPeelFirst(unsigned Level, bool Fusable = false) const {
191+
return false;
192+
}
167193

168194
/// isPeelLast - Returns true if peeling the last iteration from
169-
/// this loop will break this dependence.
170-
virtual bool isPeelLast(unsigned Level) const { return false; }
195+
/// this regular or fusable loop level will break this dependence.
196+
virtual bool isPeelLast(unsigned Level, bool Fusable = false) const {
197+
return false;
198+
}
171199

172-
/// isSplitable - Returns true if splitting this loop will break the
173-
/// dependence.
174-
virtual bool isSplitable(unsigned Level) const { return false; }
200+
/// isSplitable - Returns true if splitting the loop will break
201+
/// the dependence.
202+
virtual bool isSplitable(unsigned Level, bool Fusable = false) const {
203+
return false;
204+
}
175205

176-
/// isScalar - Returns true if a particular level is scalar; that is,
177-
/// if no subscript in the source or destination mention the induction
178-
/// variable associated with the loop at this level.
179-
virtual bool isScalar(unsigned Level) const;
206+
/// inFusableLoops - Returns true if this level is a fusable level, i.e.,
207+
/// performed across two separate loop nests that are treated like a single
208+
/// fused loop.
209+
virtual bool inFusableLoops(unsigned Level) const { return false; }
210+
211+
/// isScalar - Returns true if a particular regular or fusable level is
212+
/// scalar; that is, if no subscript in the source or destination mention
213+
/// the induction variable associated with the loop at this level.
214+
virtual bool isScalar(unsigned Level, bool Fusable = false) const;
180215

181216
/// getNextPredecessor - Returns the value of the NextPredecessor field.
182217
const Dependence *getNextPredecessor() const { return NextPredecessor; }
@@ -198,6 +233,10 @@ class LLVM_ABI Dependence {
198233
/// dump - For debugging purposes, dumps a dependence to OS.
199234
void dump(raw_ostream &OS) const;
200235

236+
/// dumpImp - For debugging purposes. Dumps a dependence to OS with or
237+
/// without considering the fusable levels.
238+
void dumpImp(raw_ostream &OS, bool Fusable = false) const;
239+
201240
protected:
202241
Instruction *Src, *Dst;
203242

@@ -238,13 +277,30 @@ class LLVM_ABI FullDependence final : public Dependence {
238277
/// source and destination of the dependence.
239278
unsigned getLevels() const override { return Levels; }
240279

280+
/// getFusableLevels - Returns the number of fusable loops surrounding
281+
/// the source and destination of the dependence.
282+
unsigned getFusableLevels() const override { return FusableLevels; }
283+
284+
/// getDVEntry - Returns the DV entry associated with a regular or a
285+
/// fusable level
286+
DVEntry getDVEntry(unsigned Level, bool Fusable) const {
287+
if (!Fusable) {
288+
assert(0 < Level && Level <= Levels && "Level out of range");
289+
return DV[Level - 1];
290+
} else {
291+
assert(Levels < Level && Level <= Levels + FusableLevels &&
292+
"Fusable level out of range");
293+
return DVFusable[Level - Levels - 1];
294+
}
295+
}
296+
241297
/// getDirection - Returns the direction associated with a particular
242-
/// level.
243-
unsigned getDirection(unsigned Level) const override;
298+
/// common or fusable level.
299+
unsigned getDirection(unsigned Level, bool Fusable = false) const override;
244300

245301
/// getDistance - Returns the distance (or NULL) associated with a
246-
/// particular level.
247-
const SCEV *getDistance(unsigned Level) const override;
302+
/// particular common or fusable level.
303+
const SCEV *getDistance(unsigned Level, bool Fusable = false) const override;
248304

249305
/// Check if the direction vector is negative. A negative direction
250306
/// vector means Src and Dst are reversed in the actual program.
@@ -257,27 +313,34 @@ class LLVM_ABI FullDependence final : public Dependence {
257313
bool normalize(ScalarEvolution *SE) override;
258314

259315
/// isPeelFirst - Returns true if peeling the first iteration from
260-
/// this loop will break this dependence.
261-
bool isPeelFirst(unsigned Level) const override;
316+
/// this regular or fusable loop level will break this dependence.
317+
bool isPeelFirst(unsigned Level, bool Fusable = false) const override;
262318

263319
/// isPeelLast - Returns true if peeling the last iteration from
264-
/// this loop will break this dependence.
265-
bool isPeelLast(unsigned Level) const override;
320+
/// this regular or fusable loop level will break this dependence.
321+
bool isPeelLast(unsigned Level, bool Fusable = false) const override;
266322

267323
/// isSplitable - Returns true if splitting the loop will break
268324
/// the dependence.
269-
bool isSplitable(unsigned Level) const override;
325+
bool isSplitable(unsigned Level, bool Fusable = false) const override;
326+
327+
/// inFusableLoops - Returns true if this level is a fusable level, i.e.,
328+
/// performed across two fusable loop nests that are treated like a single
329+
/// fused loop.
330+
bool inFusableLoops(unsigned Level) const override;
270331

271-
/// isScalar - Returns true if a particular level is scalar; that is,
272-
/// if no subscript in the source or destination mention the induction
273-
/// variable associated with the loop at this level.
274-
bool isScalar(unsigned Level) const override;
332+
/// isScalar - Returns true if a particular regular or fusable level is
333+
/// scalar; that is, if no subscript in the source or destination mention
334+
/// the induction variable associated with the loop at this level.
335+
bool isScalar(unsigned Level, bool Fusable = false) const override;
275336

276337
private:
277338
unsigned short Levels;
339+
unsigned short FusableLevels;
278340
bool LoopIndependent;
279341
bool Consistent; // Init to true, then refine.
280342
std::unique_ptr<DVEntry[]> DV;
343+
std::unique_ptr<DVEntry[]> DVFusable;
281344
friend class DependenceInfo;
282345
};
283346

@@ -406,7 +469,8 @@ class DependenceInfo {
406469
const SCEV *A;
407470
const SCEV *B;
408471
const SCEV *C;
409-
const Loop *AssociatedLoop;
472+
const Loop *AssociatedSrcLoop;
473+
const Loop *AssociatedDstLoop;
410474

411475
public:
412476
/// isEmpty - Return true if the constraint is of kind Empty.
@@ -450,19 +514,27 @@ class DependenceInfo {
450514
/// Otherwise assert.
451515
LLVM_ABI const SCEV *getD() const;
452516

453-
/// getAssociatedLoop - Returns the loop associated with this constraint.
454-
LLVM_ABI const Loop *getAssociatedLoop() const;
517+
/// getAssociatedSrcLoop - Returns the source loop associated with this
518+
/// constraint.
519+
LLVM_ABI const Loop *getAssociatedSrcLoop() const;
520+
521+
/// getAssociatedDstLoop - Returns the destination loop associated with
522+
/// this constraint.
523+
LLVM_ABI const Loop *getAssociatedDstLoop() const;
455524

456525
/// setPoint - Change a constraint to Point.
457526
LLVM_ABI void setPoint(const SCEV *X, const SCEV *Y,
458-
const Loop *CurrentLoop);
527+
const Loop *CurrentSrcLoop,
528+
const Loop *CurrentDstLoop);
459529

460530
/// setLine - Change a constraint to Line.
461531
LLVM_ABI void setLine(const SCEV *A, const SCEV *B, const SCEV *C,
462-
const Loop *CurrentLoop);
532+
const Loop *CurrentSrcLoop,
533+
const Loop *CurrentDstLoop);
463534

464535
/// setDistance - Change a constraint to Distance.
465-
LLVM_ABI void setDistance(const SCEV *D, const Loop *CurrentLoop);
536+
LLVM_ABI void setDistance(const SCEV *D, const Loop *CurrentSrcLoop,
537+
const Loop *CurrentDstLoop);
466538

467539
/// setEmpty - Change a constraint to Empty.
468540
LLVM_ABI void setEmpty();
@@ -475,6 +547,10 @@ class DependenceInfo {
475547
LLVM_ABI void dump(raw_ostream &OS) const;
476548
};
477549

550+
/// Returns true if two loops are the same or they have the same tripcount
551+
/// and depth
552+
bool areLoopsSimilar(const Loop *SrcLoop, const Loop *DstLoop) const;
553+
478554
/// establishNestingLevels - Examines the loop nesting of the Src and Dst
479555
/// instructions and establishes their shared loops. Sets the variables
480556
/// CommonLevels, SrcLevels, and MaxLevels.
@@ -525,9 +601,22 @@ class DependenceInfo {
525601
/// e - 5
526602
/// f - 6
527603
/// g - 7 = MaxLevels
604+
/// FusableLevels counts the number of levels after common levels that are
605+
/// not common but are similar, meaning that they have the same tripcount and
606+
/// depth. Assume that in this code fragment, levels c and e are similar. In
607+
/// this case only the loop nests at the next level after common levels are
608+
/// similar, and FusableLevels is set to 1. If there are similar loop nests,
609+
/// we could use the APIs with considering them as fused loops. In that case
610+
/// the level numbers for the previous code look like
611+
/// a - 1
612+
/// b - 2
613+
/// c,e - 3 = CommonLevels
614+
/// d - 4 = SrcLevels
615+
/// f - 5
616+
/// g - 6 = MaxLevels
528617
void establishNestingLevels(const Instruction *Src, const Instruction *Dst);
529618

530-
unsigned CommonLevels, SrcLevels, MaxLevels;
619+
unsigned CommonLevels, SrcLevels, MaxLevels, FusableLevels;
531620

532621
/// mapSrcLoop - Given one of the loops containing the source, return
533622
/// its level index in our numbering scheme.
@@ -652,9 +741,9 @@ class DependenceInfo {
652741
/// If there might be a dependence, returns false.
653742
/// Sets appropriate direction and distance.
654743
bool strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst,
655-
const SCEV *DstConst, const Loop *CurrentLoop,
656-
unsigned Level, FullDependence &Result,
657-
Constraint &NewConstraint) const;
744+
const SCEV *DstConst, const Loop *CurrentSrcLoop,
745+
const Loop *CurrentDstLoop, unsigned Level,
746+
FullDependence &Result, Constraint &NewConstraint) const;
658747

659748
/// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair
660749
/// (Src and Dst) for dependence.
@@ -667,9 +756,9 @@ class DependenceInfo {
667756
/// Set consistent to false.
668757
/// Marks the dependence as splitable.
669758
bool weakCrossingSIVtest(const SCEV *SrcCoeff, const SCEV *SrcConst,
670-
const SCEV *DstConst, const Loop *CurrentLoop,
671-
unsigned Level, FullDependence &Result,
672-
Constraint &NewConstraint,
759+
const SCEV *DstConst, const Loop *CurrentSrcLoop,
760+
const Loop *CurrentDstLoop, unsigned Level,
761+
FullDependence &Result, Constraint &NewConstraint,
673762
const SCEV *&SplitIter) const;
674763

675764
/// ExactSIVtest - Tests the SIV subscript pair
@@ -683,8 +772,9 @@ class DependenceInfo {
683772
/// Set consistent to false.
684773
bool exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
685774
const SCEV *SrcConst, const SCEV *DstConst,
686-
const Loop *CurrentLoop, unsigned Level,
687-
FullDependence &Result, Constraint &NewConstraint) const;
775+
const Loop *CurrentSrcLoop, const Loop *CurrentDstLoop,
776+
unsigned Level, FullDependence &Result,
777+
Constraint &NewConstraint) const;
688778

689779
/// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair
690780
/// (Src and Dst) for dependence.
@@ -697,8 +787,9 @@ class DependenceInfo {
697787
/// Set consistent to false.
698788
/// If loop peeling will break the dependence, mark appropriately.
699789
bool weakZeroSrcSIVtest(const SCEV *DstCoeff, const SCEV *SrcConst,
700-
const SCEV *DstConst, const Loop *CurrentLoop,
701-
unsigned Level, FullDependence &Result,
790+
const SCEV *DstConst, const Loop *CurrentSrcLoop,
791+
const Loop *CurrentDstLoop, unsigned Level,
792+
FullDependence &Result,
702793
Constraint &NewConstraint) const;
703794

704795
/// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair
@@ -712,8 +803,9 @@ class DependenceInfo {
712803
/// Set consistent to false.
713804
/// If loop peeling will break the dependence, mark appropriately.
714805
bool weakZeroDstSIVtest(const SCEV *SrcCoeff, const SCEV *SrcConst,
715-
const SCEV *DstConst, const Loop *CurrentLoop,
716-
unsigned Level, FullDependence &Result,
806+
const SCEV *DstConst, const Loop *CurrentSrcLoop,
807+
const Loop *CurrentDstLoop, unsigned Level,
808+
FullDependence &Result,
717809
Constraint &NewConstraint) const;
718810

719811
/// exactRDIVtest - Tests the RDIV subscript pair for dependence.

0 commit comments

Comments
 (0)