1 /************************************************************************
2  ************************************************************************
3     FAUST compiler
4     Copyright (C) 2003-2018 GRAME, Centre National de Creation Musicale
5     ---------------------------------------------------------------------
6     This program is free software; you can redistribute it and/or modify
7     it under the terms of the GNU General Public License as published by
8     the Free Software Foundation; either version 2 of the License, or
9     (at your option) any later version.
10 
11     This program is distributed in the hope that it will be useful,
12     but WITHOUT ANY WARRANTY; without even the implied warranty of
13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14     GNU General Public License for more details.
15 
16     You should have received a copy of the GNU General Public License
17     along with this program; if not, write to the Free Software
18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19  ************************************************************************
20  ************************************************************************/
21 
22 #ifndef _CODE_LOOP_H
23 #define _CODE_LOOP_H
24 
25 #include <list>
26 #include <map>
27 #include <set>
28 #include <string>
29 #include <vector>
30 
31 #include "fir_function_builder.hh"
32 #include "garbageable.hh"
33 #include "list.hh"
34 #include "tree.hh"
35 
36 // Loop internal code
37 
38 /*
39 
40 On a des boucles indépendantes qui seront "connectées" avec des vecteurs
41 
42 On voudrait pouvoir connecter des boucles et supprimer les vecteurs intermédiaires.
43 
44 On part d'un DAG de loops, on veut pouvoir:
45 
46 - mettre ce DAG sur la forme d'une sequence de boucle (tri topologique)
47 - "fusionner" toutes les boucles en une seule, donc en gros extraire le code des boucles et le fusionner
48 
49 Scalarisation d'une boucle:
50 
51 - identifier tous les vecteurs d'entrée et de sortie
52 - transformer les vecteurs en scalaire
53 - transformer les accès (Load/Store) en accès scalaire
54 
55 */
56 
57 class CodeLoop;
58 
59 typedef set<CodeLoop*> lclset;
60 typedef vector<lclset> lclgraph;
61 
62 class CodeLoop : public virtual Garbageable {
63     friend class CodeContainer;
64 
65    private:
66     bool            fIsRecursive;    ///< recursive loops can't be SIMDed
67     Tree            fRecSymbolSet;   ///< recursive loops define a set of recursive symbol
68     CodeLoop* const fEnclosingLoop;  ///< Loop from which this one originated
69     int             fSize;           ///< number of iterations of the loop
70     int             fOrder;          ///< used during topological sort
71     int             fIndex;
72 
73     BlockInst* fPreInst;
74     BlockInst* fComputeInst;
75     BlockInst* fPostInst;
76 
77     string fLoopIndex;
78 
79     int             fUseCount;    ///< how many loops depend on this one
80     list<CodeLoop*> fExtraLoops;  ///< extra loops that where in sequences
81 
82     set<Tree>      fRecDependencies;           ///< Loops having recursive dependencies must be merged
83     set<CodeLoop*> fBackwardLoopDependencies;  ///< Loops that must be computed before this one
84     set<CodeLoop*> fForwardLoopDependencies;   ///< Loops that will be computed after this one
85 
pushBlock(BlockInst * block,BlockInst * loop)86     void pushBlock(BlockInst* block, BlockInst* loop)
87     {
88         list<StatementInst*>::const_iterator it;
89         for (it = block->fCode.begin(); it != block->fCode.end(); it++) {
90             loop->pushBackInst((*it));
91         }
92     }
93 
94     bool isEmpty();  ///< true when the loop doesn't contain any line of code
95 
96     void absorb(CodeLoop* l);  ///< absorb a loop inside this one
97     void concat(CodeLoop* l);
98 
99     // Graph sorting
100     static void setOrder(CodeLoop* l, int order, lclgraph& V);
101     static void setLevel(int order, const lclset& T1, lclset& T2, lclgraph& V);
102     static void resetOrder(CodeLoop* l, set<CodeLoop*>& visited);
103 
104    public:
105     ///< create a recursive loop
CodeLoop(Tree recsymbol,CodeLoop * encl,const string & index_name,int size=0)106     CodeLoop(Tree recsymbol, CodeLoop* encl, const string& index_name, int size = 0)
107         : fIsRecursive(true),
108           fRecSymbolSet(singleton(recsymbol)),
109           fEnclosingLoop(encl),
110           fSize(size),
111           fOrder(-1),
112           fIndex(-1),
113           fPreInst(new BlockInst()),
114           fComputeInst(new BlockInst()),
115           fPostInst(new BlockInst()),
116           fLoopIndex(index_name),
117           fUseCount(0)
118     {
119     }
120 
121     ///< create a non recursive loop
CodeLoop(CodeLoop * encl,const string & index_name,int size=0)122     CodeLoop(CodeLoop* encl, const string& index_name, int size = 0)
123         : fIsRecursive(false),
124           fRecSymbolSet(gGlobal->nil),
125           fEnclosingLoop(encl),
126           fSize(size),
127           fOrder(-1),
128           fIndex(-1),
129           fPreInst(new BlockInst()),
130           fComputeInst(new BlockInst()),
131           fPostInst(new BlockInst()),
132           fLoopIndex(index_name),
133           fUseCount(0)
134     {
135     }
136 
pushPreComputeDSPMethod(StatementInst * inst)137     StatementInst* pushPreComputeDSPMethod(StatementInst* inst)
138     {
139         fPreInst->pushBackInst(inst);
140         return inst;
141     }
pushComputeDSPMethod(StatementInst * inst)142     StatementInst* pushComputeDSPMethod(StatementInst* inst)
143     {
144         fComputeInst->pushBackInst(inst);
145         return inst;
146     }
pushPostComputeDSPMethod(StatementInst * inst)147     StatementInst* pushPostComputeDSPMethod(StatementInst* inst)
148     {
149         fPostInst->pushBackInst(inst);
150         return inst;
151     }
152 
isRecursive()153     bool isRecursive() { return fIsRecursive; }
154 
getIndex()155     int getIndex() { return fIndex; }
156 
getForwardLoopDependencies()157     set<CodeLoop*>& getForwardLoopDependencies() { return fForwardLoopDependencies; }
getBackwardLoopDependencies()158     set<CodeLoop*>& getBackwardLoopDependencies() { return fBackwardLoopDependencies; }
159 
getLoopIndex()160     ValueInst* getLoopIndex() { return InstBuilder::genLoadLoopVar(fLoopIndex); }
161 
162     ForLoopInst* generateScalarLoop(const string& counter, bool loop_var_in_bytes = false);
163 
164     // For Rust backend
165     SimpleForLoopInst* generateSimpleScalarLoop(const string& counter);
166     IteratorForLoopInst* generateSimpleScalarLoop(const std::vector<string>& iterators);
167 
168     BlockInst* generateOneSample();
169 
170     void generateDAGScalarLoop(BlockInst* block, DeclareVarInst* count, bool omp);
171 
transform(DispatchVisitor * visitor)172     void transform(DispatchVisitor* visitor)
173     {
174         // Transform extra loops
175         for (list<CodeLoop*>::const_iterator s = fExtraLoops.begin(); s != fExtraLoops.end(); s++) {
176             (*s)->transform(visitor);
177         }
178         fPreInst->accept(visitor);
179         fComputeInst->accept(visitor);
180         fPostInst->accept(visitor);
181     }
182 
183     bool hasRecDependencyIn(Tree S);  ///< returns true is this loop has recursive dependencies
addBackwardDependency(CodeLoop * ls)184     void addBackwardDependency(CodeLoop* ls) { fBackwardLoopDependencies.insert(ls); }
185 
186     static void sortGraph(CodeLoop* root, lclgraph& V);
187     static void computeUseCount(CodeLoop* l);
188     static void groupSeqLoops(CodeLoop* l, set<CodeLoop*>& visited);
189 };
190 
191 #endif
192