1/*
2 * This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
5 *
6 * Copyright 1997 - July 2008 CWI, August 2008 - 2019 MonetDB B.V.
7 */
8
9/*
10 * The dataflow reorder
11 * MAL programs are largely logical descriptions of an execution plan.
12 * After the mitosis and mergetable optimizers we have a large program, which when
13 * executed as is, does not necessarily benefit from the locality
14 * of data and operations. The problem is that the execution plan is
15 * a DAG for which a topological order should be found that
16 * minimizes the life time of variables and maximizes parallel execution.
17 * This is an NP hard optimization problem. Therefore, we have
18 * to rely on an affordable heuristic steps.
19 *
20 * The reorder optimizer transfers the breadth-first plans of
21 * the mergetable into a depth-first traversal.
22 * This increases cohesion for parallel execution.
23 * It is performed by basic block that ends in a side-effect
24 * bearing instruction.
25 * Simply walking backward and pulling out subplans is then
26 * the way to go. This step could be optimized somewhat
27 * by giving preference to variables that are too far
28 * away in the plan from their source. It is however not
29 * explored.
30 *
31 * The secondary approach is to pull instructions to the
32 * head of the plan if the dataflow such permits.
33 * If you are not careful, you will end up with
34 * the breadth first plan again.
35 *
36 * Beware, variables can be assigned a value multiple times.
37 * The order this implies should be respected.
38 *
39 * Hidden dependencies occur als with e.g. sql.assert() calls.
40 * Reordering them may easily lead to an assertion violation.
41 * Therefore, reordering should be limited to basic blocks without
42 * side-effects.
43 */
44#include "monetdb_config.h"
45#include "opt_reorder.h"
46#include "mal_instruction.h"
47#include "mal_interpreter.h"
48/*
49 * Collect the statement dependencies in a table first
50 * This can be done in linear time in size of the program.
51 * Also check for barrier blocks. We only allow reordering
52 * for a linear plan. Future extensions could consider
53 * re-ordering basic blocks only.
54 */
55typedef struct{
56 int cnt;
57 int used;
58 int pos,pos2;
59 int stmt[FLEXIBLE_ARRAY_MEMBER];
60} *Node, NodeRecord;
61
62static void
63OPTremoveDep(Node *list, int lim)
64{
65 int i;
66
67 for (i=0; i< lim; i++)
68 if (list[i])
69 GDKfree(list[i]);
70 GDKfree(list);
71}
72
73static Node *
74OPTdependencies(Client cntxt, MalBlkPtr mb, int **Ulist)
75{
76 Node *list = (Node *) GDKzalloc(sizeof(Node) * mb->stop);
77 int *var = (int*) GDKzalloc(sizeof(int) * mb->vtop), *uselist = NULL;
78 int i,j,sz=0;
79 InstrPtr p = NULL;
80 int block = 0;
81
82 (void) cntxt;
83
84 if (list == NULL || var == NULL){
85 if (list ) GDKfree(list);
86 if (var) GDKfree(var);
87 return NULL;
88 }
89
90 for ( i=0; i< mb->stop; i++){
91 p= getInstrPtr(mb,i);
92 block |= p->barrier != 0;
93 list[i]= (Node) GDKzalloc(offsetof(NodeRecord, stmt) + sizeof(int) * p->argc);
94 if (list[i] == NULL){
95 OPTremoveDep(list, i);
96 GDKfree(var);
97 return 0;
98 }
99 list[i]->cnt = p->argc;
100 for( j=p->retc; j<p->argc; j++) {
101 list[i]->stmt[j] = var[getArg(p,j)];
102 list[var[getArg(p,j)]]->used++;
103 }
104 /* keep the assignment order */
105 for( j= 0; j < p->retc; j++) {
106 if ( var[ getArg(p,j)] ) {
107 //list[i]->stmt[j] = var [getArg(p,j)];
108 // escape we should avoid reused variables.
109 OPTremoveDep(list, i + 1);
110 GDKfree(var);
111 return 0;
112 }
113 }
114 /* remember the last assignment */
115 for( j=0; j<p->retc; j++)
116 var[getArg(p,j)] = i;
117 }
118 /*
119 * mnstr_printf(cntxt->fdout,"DEPENDENCY TABLE\n");
120 * for(i=0;i<mb->stop; i++)
121 * if( list[i]->cnt){
122 * mnstr_printf(cntxt->fdout,"%s.%s [%d,%d]",
123 * mb->stmt[i]->modname,
124 * mb->stmt[i]->fcnname, i, list[i]->used);
125 * for(j=p->retc; j< list[i]->cnt; j++)
126 * mnstr_printf(cntxt->fdout, " %d", list[i]->stmt[j]);
127 * mnstr_printf(cntxt->fdout,"\n");
128 * }
129 */
130 for(i=0;i<mb->stop; i++) {
131 list[i]->pos = sz;
132 list[i]->pos2 = sz;
133 sz += list[i]->used;
134 }
135 if( sz == 0){
136 OPTremoveDep(list, mb->stop);
137 GDKfree(var);
138 return NULL;
139 }
140 uselist = GDKzalloc(sizeof(int)*sz);
141 if (!uselist) {
142 OPTremoveDep(list, mb->stop);
143 GDKfree(var);
144 return NULL;
145 }
146
147 for(i=0;i<mb->stop; i++) {
148 if (list[i]->cnt) {
149 p= getInstrPtr(mb,i);
150 for(j=p->retc; j< list[i]->cnt; j++) {
151 uselist[list[list[i]->stmt[j]]->pos2] = i;
152 list[list[i]->stmt[j]]->pos2++;
153 }
154 }
155 }
156 /*
157 * for(i=0, sz = 0; i<mb->stop; i++) {
158 * mnstr_printf(cntxt->fdout,"%d is used by", i);
159 * for(j=0; j<list[i]->used; j++, sz++)
160 * mnstr_printf(cntxt->fdout," %d", uselist[sz]);
161 * mnstr_printf(cntxt->fdout,"\n");
162 * }
163 */
164
165 if ( block ){
166 OPTremoveDep(list, mb->stop);
167 GDKfree(uselist);
168 GDKfree(var);
169 return NULL;
170 }
171 GDKfree(var);
172 *Ulist = uselist;
173 return list;
174}
175
176static int
177OPTbreadthfirst(Client cntxt, MalBlkPtr mb, int pc, int max, InstrPtr old[], Node dep[], int *uselist)
178{
179 int i;
180 InstrPtr p;
181
182 if (pc > max)
183 return 0;
184
185 p = old[pc];
186 if (p == NULL)
187 return 0;
188
189 if (THRhighwater())
190 return -1;
191
192 for (i= p->retc; i< dep[pc]->cnt; i++)
193 if (OPTbreadthfirst(cntxt, mb, dep[pc]->stmt[i], max, old, dep, uselist) < 0)
194 return -1;
195 if (old[pc] != NULL) {
196 old[pc] = 0;
197 pushInstruction(mb, p);
198 }
199 if (getModuleId(p) == groupRef)
200 for (i = 0; i< dep[pc]->used; i++)
201 if (OPTbreadthfirst(cntxt, mb, uselist[dep[pc]->pos+i], max, old, dep, uselist) < 0)
202 return -1;
203 return 0;
204}
205
206/* SQL appends are collected to create a better dataflow block */
207/* alternatively, we should postpone all mcv-chained actions */
208static int
209OPTpostponeAppends(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
210{
211 int i,j,k=0, actions =0, last=-1;
212 InstrPtr *old, *appends;
213 int limit;
214 (void) cntxt;
215 (void) stk;
216 (void) p;
217
218 appends =(InstrPtr*) GDKzalloc(mb->ssize * sizeof(InstrPtr));
219 if( appends == NULL)
220 return 0;
221 limit= mb->stop;
222 old = mb->stmt;
223 if ( newMalBlkStmt(mb, mb->ssize) < 0) {
224 GDKfree(appends);
225 return 0;
226 }
227 for( i=0; i<limit; i++){
228 if ( getModuleId(old[i]) == sqlRef && getFunctionId(old[i]) == appendRef){
229 last = i;
230 }
231 }
232 for( i=0; i<limit; i++){
233 if ( getModuleId(old[i]) == sqlRef && getFunctionId(old[i]) == appendRef){
234 // only postpone under strict conditions
235 assert( isVarConstant(mb,getArg(old[i],2)));
236 assert( isVarConstant(mb,getArg(old[i],3)));
237 assert( isVarConstant(mb,getArg(old[i],4)));
238 if( actions )
239 pushInstruction(mb, old[i]);
240 else {
241 if (k > 0 && getArg(old[i],1) == getArg(appends[k-1],0))
242 appends[k++]= old[i];
243 else {
244 for(j=0; j<k; j++)
245 pushInstruction(mb,appends[j]);
246 pushInstruction(mb, old[i]);
247 actions++;
248 }
249 }
250 continue;
251 }
252 if ( i == last){
253 actions++;
254 for(j=0; j<k; j++)
255 pushInstruction(mb,appends[j]);
256 }
257 pushInstruction(mb,old[i]);
258 }
259 for( ; i<limit; i++){
260 pushInstruction(mb,old[i]);
261 }
262 GDKfree(appends);
263 GDKfree(old);
264 return actions;
265}
266
267str
268OPTreorderImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
269{
270 int i,j, start;
271 InstrPtr *old;
272 int limit, slimit, *uselist = NULL;
273 Node *dep;
274 char buf[256];
275 lng usec= GDKusec();
276 str msg = MAL_SUCCEED;
277
278 (void) cntxt;
279 (void) stk;
280 dep = OPTdependencies(cntxt,mb,&uselist);
281 if ( dep == NULL)
282 return MAL_SUCCEED;
283 limit= mb->stop;
284 slimit= mb->ssize;
285 old = mb->stmt;
286 if ( newMalBlkStmt(mb, mb->ssize) < 0) {
287 GDKfree(uselist);
288 OPTremoveDep(dep, limit);
289 throw(MAL,"optimizer.reorder", SQLSTATE(HY001) MAL_MALLOC_FAIL);
290 }
291
292 pushInstruction(mb,old[0]);
293 old[0]=0;
294
295 start=1;
296 for (i=1; i<limit; i++){
297 p= old[i];
298 if ( p == 0)
299 continue;
300 if( p->token == ENDsymbol)
301 break;
302 if( hasSideEffects(mb, p,FALSE) || isUnsafeFunction(p) || p->barrier ){
303 if (OPTbreadthfirst(cntxt, mb, i, i, old, dep, uselist) < 0)
304 break;
305 /* remove last instruction and keep for later */
306 if (p == mb->stmt[mb->stop-1]) {
307 p= mb->stmt[mb->stop-1];
308 mb->stmt[mb->stop-1]=0;
309 mb->stop--;
310 } else {
311 p = 0;
312 }
313 /* collect all seen sofar by backward grouping */
314 /* since p has side-effects, we should secure all seen sofar */
315 for(j=i-1; j>=start;j--) {
316
317 if( OPTdebug & OPTreorder){
318 if( old[j]){
319 fprintf(stderr,"leftover: %d",start+1);
320 fprintInstruction(stderr,mb,0,old[j],LIST_MAL_ALL);
321 }
322 }
323
324 if (OPTbreadthfirst(cntxt, mb, j, i, old, dep, uselist) < 0) {
325 i = limit; /* cause break from outer loop */
326 break;
327 }
328 }
329 if (p)
330 pushInstruction(mb,p);
331 start = i+1;
332 }
333 }
334 for(i=0; i<limit; i++)
335 if (old[i])
336 pushInstruction(mb,old[i]);
337 for(; i<slimit; i++)
338 if (old[i])
339 freeInstruction(old[i]);
340 OPTremoveDep(dep, limit);
341 GDKfree(uselist);
342 GDKfree(old);
343 (void) OPTpostponeAppends(cntxt, mb, 0, 0);
344
345 /* Defense line against incorrect plans */
346 if( 1){
347 chkTypes(cntxt->usermodule, mb, FALSE);
348 chkFlow(mb);
349 chkDeclarations(mb);
350 }
351 /* keep all actions taken as a post block comment */
352 usec = GDKusec()- usec;
353 snprintf(buf,256,"%-20s actions=%2d time=" LLFMT " usec","reorder",1,usec);
354 newComment(mb,buf);
355 addtoMalBlkHistory(mb);
356
357 if( OPTdebug & OPTreorder){
358 fprintf(stderr, "#reorder optimizer entry\n");
359 fprintFunction(stderr, mb, 0, LIST_MAL_ALL);
360 }
361 return msg;
362}
363