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#include "monetdb_config.h"
10#include "opt_prelude.h"
11#include "opt_macro.h"
12#include "mal_interpreter.h"
13#include "mal_instruction.h"
14
15static int
16malMatch(InstrPtr p1, InstrPtr p2)
17{
18 int i, j;
19
20 if (getFunctionId(p1) == 0 && getFunctionId(p2) != 0)
21 return 0;
22 if (getModuleId(p1) == 0 && getModuleId(p2) != 0)
23 return 0;
24 if (getModuleId(p1) != getModuleId(p2))
25 return 0;
26 if (getFunctionId(p2) == 0)
27 return 0;
28 if (getFunctionId(p1) != getFunctionId(p2))
29 return 0;
30 if (p1->retc != p2->retc)
31 return 0;
32 if (p1->argc != p2->argc)
33 return 0;
34 if (p1->barrier != p2->barrier)
35 return 0;
36 for (i = 0; i < p1->argc; i++)
37 for (j = i + 1; j < p1->argc; j++)
38 if ((getArg(p1, i) == getArg(p1, j)) != (getArg(p2, i) == getArg(p2, j)))
39 return 0;
40 return 1;
41}
42
43/*
44 * Matching a block calls for building two variable lists used.
45 * The isomorphism can be determined after-wards using a single scan.
46 * The candidate block is matched with mb starting at a given pc.
47 * The candidate block is expected to defined as a function, including
48 * a signature and end-statement. They are ignored in the comparison
49 *
50 * Beware, the variables in the block being removed, could be
51 * used furtheron in the program. [tricky to detect, todo]
52 */
53static int
54malFcnMatch(MalBlkPtr mc, MalBlkPtr mb, int pc)
55{
56 int i, j, k, lim;
57 int *cvar, *mvar;
58 int ctop = 0, mtop = 0;
59 InstrPtr p, q;
60
61 if (mb->stop - pc < mc->stop - 2)
62 return 0;
63
64 cvar = (int *) GDKmalloc(mc->vtop * mc->maxarg * sizeof(*cvar));
65 if (cvar == NULL)
66 return 0;
67 mvar = (int *) GDKmalloc(mb->vtop * mc->maxarg * sizeof(*mvar));
68 if (mvar == NULL){
69 GDKfree(cvar);
70 return 0;
71 }
72 /* also trim the return statement */
73 lim = pc + mc->stop - 3;
74 k = 1;
75 for (i = pc; i < lim; i++, k++) {
76 p = getInstrPtr(mb, i);
77 q = getInstrPtr(mc, k);
78 if (malMatch(p, q) == 0){
79 GDKfree(cvar);
80 GDKfree(mvar);
81 return 0;
82 }
83 for (j = 0; j < p->argc; j++)
84 cvar[ctop++] = getArg(p, j);
85
86 for (j = 0; j < q->argc; j++)
87 mvar[mtop++] = getArg(q, j);
88 }
89 assert(mtop == ctop); /*shouldn't happen */
90
91 for (i = 0; i < ctop; i++)
92 for (j = i + 1; j < ctop; j++)
93 if ((cvar[i] == cvar[j]) != (mvar[i] == mvar[j])) {
94 GDKfree(cvar);
95 GDKfree(mvar);
96 return 0;
97 }
98 GDKfree(cvar);
99 GDKfree(mvar);
100 return 1;
101}
102/*
103 * Macro expansions
104 * The macro expansion routine walks through the MAL code block in search
105 * for the function to be expanded.
106 * The macro expansion process is restarted at the first new instruction.
107 * A global is used to protect at (direct) recursive expansions
108 */
109#define MAXEXPANSION 256
110
111int
112inlineMALblock(MalBlkPtr mb, int pc, MalBlkPtr mc)
113{
114 int i, k, l, n;
115 InstrPtr *ns, p,q;
116 int *nv;
117
118 p = getInstrPtr(mb, pc);
119 q = getInstrPtr(mc, 0);
120 ns = GDKzalloc((l = (mb->ssize + mc->ssize + p->retc - 3)) * sizeof(InstrPtr));
121 if (ns == NULL)
122 return -1;
123 nv = (int*) GDKmalloc(mc->vtop * sizeof(int));
124 if (nv == 0){
125 GDKfree(ns);
126 return -1;
127 }
128
129 /* add all variables of the new block to the target environment */
130 for (n = 0; n < mc->vtop; n++) {
131 if (isExceptionVariable(getVarName(mc,n))) {
132 nv[n] = newVariable(mb, getVarName(mc,n), strlen(getVarName(mc,n)), TYPE_str);
133 if (isVarUDFtype(mc,n))
134 setVarUDFtype(mb,nv[n]);
135 } else if (isVarTypedef(mc,n)) {
136 nv[n] = newTypeVariable(mb,getVarType(mc,n));
137 } else if (isVarConstant(mc,n)) {
138 nv[n] = cpyConstant(mb,getVar(mc,n));
139 } else {
140 nv[n] = newTmpVariable(mb, getVarType(mc, n));
141 if (isVarUDFtype(mc,n))
142 setVarUDFtype(mb,nv[n]);
143 }
144 }
145
146 /* use an alias mapping to keep track of the actual arguments */
147 for (n = p->retc; n < p->argc; n++)
148 nv[getArg(q,n)] = getArg(p, n);
149
150 k = 0;
151 /* find the return statement of the inline function */
152 for (i = 1; i < mc->stop - 1; i++) {
153 q = mc->stmt[i];
154 if( q->barrier== RETURNsymbol || q->barrier== YIELDsymbol){
155 /* add the mapping of the return variables */
156 for(n=0; n<p->retc; n++)
157 nv[getArg(q,n)] = getArg(p,n);
158 }
159 }
160
161 /* copy the stable part */
162 for (i = 0; i < pc; i++)
163 ns[k++] = mb->stmt[i];
164
165 for (i = 1; i < mc->stop - 1; i++) {
166 q = mc->stmt[i];
167 if( q->token == ENDsymbol)
168 break;
169
170 /* copy the instruction and fix variable references */
171 ns[k] = copyInstruction(q);
172 if( ns[k] == NULL)
173 return -1;
174
175 for (n = 0; n < q->argc; n++)
176 getArg(ns[k], n) = nv[getArg(q, n)];
177
178 if (q->barrier == RETURNsymbol || q->barrier == YIELDsymbol) {
179 for(n=0; n<q->retc; n++)
180 clrVarFixed(mb,getArg(ns[k],n)); /* for typing */
181 setModuleId(ns[k],getModuleId(q));
182 setFunctionId(ns[k],getFunctionId(q));
183 ns[k]->typechk = TYPE_UNKNOWN;
184 ns[k]->barrier = 0;
185 ns[k]->token = ASSIGNsymbol;
186 }
187 k++;
188 }
189
190 /* copy the remainder of the stable part */
191 freeInstruction(p);
192 for (i = pc + 1; i < mb->stop; i++){
193 ns[k++] = mb->stmt[i];
194 }
195 /* remove any free instruction */
196 for(; i<mb->ssize; i++)
197 if( mb->stmt[i]){
198 freeInstruction(mb->stmt[i]);
199 mb->stmt[i]= 0;
200 }
201 GDKfree(mb->stmt);
202 mb->stmt = ns;
203
204 mb->ssize = l;
205 mb->stop = k;
206 GDKfree(nv);
207 return pc;
208}
209
210/*
211 * The macro processor should be careful in replacing the
212 * instruction. In particular, any RETURN or YIELD statement
213 * should be replaced by a jump. For the time being,
214 * we only allow for a single return statement at the end
215 * of the block.
216 * The semantic test is encapsulated in a routines.
217 */
218
219static str
220MACROvalidate(MalBlkPtr mb)
221{
222 int retseen = 0;
223 int i;
224 InstrPtr p = 0;
225
226 if (getArgType(mb, getInstrPtr(mb, 0), 0) == TYPE_void)
227 return MAL_SUCCEED;
228
229 for (i = 1; retseen == 0 && i < mb->stop; i++) {
230 p = getInstrPtr(mb, i);
231 retseen = p->token == RETURNsymbol || p->token == YIELDsymbol || p->barrier == RETURNsymbol || p->barrier == YIELDsymbol;
232 }
233 if (retseen && i != mb->stop - 1)
234 throw(MAL, "optimizer.MACROvalidate", SQLSTATE(HY002) MACRO_SYNTAX_ERROR);
235 return MAL_SUCCEED;
236}
237
238str
239MACROprocessor(Client cntxt, MalBlkPtr mb, Symbol t)
240{
241 InstrPtr q;
242 int i, cnt = 0, last = -1;
243 str msg = MAL_SUCCEED;
244
245 (void) cntxt;
246 if (t == NULL)
247 return msg;
248 msg = MACROvalidate(t->def);
249 if (msg)
250 return msg;
251 for (i = 0; i < mb->stop; i++) {
252 q = getInstrPtr(mb, i);
253 if (getFunctionId(q) && idcmp(getFunctionId(q), t->name) == 0 &&
254 getSignature(t)->token == FUNCTIONsymbol) {
255 if (i == last)
256 throw(MAL, "optimizer.MACROoptimizer", SQLSTATE(HY002) MACRO_DUPLICATE);
257
258 last = i;
259 i = inlineMALblock(mb, i, t->def);
260 if( i < 0)
261 throw(MAL, "optimizer.MACROoptimizer", SQLSTATE(HY001) MAL_MALLOC_FAIL);
262
263 cnt++;
264 if (cnt > MAXEXPANSION)
265 throw(MAL, "optimizer.MACROoptimizer", SQLSTATE(HY002) MACRO_TOO_DEEP);
266 }
267 }
268 return msg;
269}
270
271/*
272 * Macro inversions map a consecutive sequences of MAL instructions
273 * into a single call. Subsequent resolution will bind it with the proper
274 * function. The pattern being replaced should be a self-standing
275 * assignment. [could be improved]
276 *
277 * The function being replaced should assign the result to
278 * the signature variables. Otherwise it will be difficult
279 * to assess which result to retain.
280 */
281static int
282replaceMALblock(MalBlkPtr mb, int pc, MalBlkPtr mc)
283{
284 int i, j, k, lim;
285 InstrPtr p, q, rq;
286 int *cvar, *mvar;
287 int ctop = 0, mtop = 0;
288
289 /* collect variable map */
290 cvar = (int *) GDKmalloc(mc->vtop * mc->maxarg * sizeof(*cvar));
291 if (cvar == NULL)
292 return -1;
293 mvar = (int *) GDKmalloc(mb->vtop * mc->maxarg * sizeof(*mvar));
294 if (mvar == NULL){
295 GDKfree(cvar);
296 return -1;
297 }
298 lim = pc + mc->stop - 3;
299 k = 1;
300 for (i = pc; i < lim; i++, k++) {
301 p = getInstrPtr(mb, i);
302 q = getInstrPtr(mc, k);
303 for (j = 0; j < q->argc; j++)
304 cvar[ctop++] = getArg(q, j);
305 assert(ctop < mc->vtop *mc->maxarg);
306
307 for (j = 0; j < p->argc; j++)
308 mvar[mtop++] = getArg(p, j);
309 }
310 assert(mtop == ctop); /*shouldn't happen */
311
312 p = getInstrPtr(mb, pc);
313 q = copyInstruction(getInstrPtr(mc, 0)); /* the signature */
314 if( q == NULL)
315 return -1;
316 q->token = ASSIGNsymbol;
317 mb->stmt[pc] = q;
318
319 for (i = q->retc; i < q->argc; i++)
320 for (j = 0; j < ctop; j++)
321 if (q->argv[i] == cvar[j]) {
322 q->argv[i] = mvar[j];
323 break;
324 }
325 /* take the return expression and match the variables*/
326 rq = getInstrPtr(mc, mc->stop - 2);
327 for (i = 0; i < rq->retc; i++)
328 for (j = 0; j < ctop; j++)
329 if (rq->argv[i+rq->retc] == cvar[j]) {
330 q->argv[i] = mvar[j];
331 break;
332 }
333 freeInstruction(p);
334
335 /* strip signature, return, and end statements */
336 k = mc->stop - 3;
337 j = pc + k;
338 for (i = pc + 1; i < pc + k; i++)
339 freeInstruction(mb->stmt[i]);
340
341 for (i = pc + 1; i < mb->stop - k; i++)
342 mb->stmt[i] = mb->stmt[j++];
343
344 k = i;
345 for (; i < mb->stop; i++)
346 mb->stmt[i] = 0;
347
348 mb->stop = k;
349 GDKfree(cvar);
350 GDKfree(mvar);
351 return pc;
352}
353
354static str
355ORCAMprocessor(Client cntxt, MalBlkPtr mb, Symbol t)
356{
357 MalBlkPtr mc;
358 int i;
359 str msg = MAL_SUCCEED;
360
361 if (t == NULL )
362 return msg; /* ignore the call */
363 mc = t->def;
364 if ( mc->stop < 3)
365 return msg; /* ignore small call */
366
367 /* strip signature, return, and end statements */
368 for (i = 1; i < mb->stop - mc->stop + 3; i++)
369 if (malFcnMatch(mc, mb, i)) {
370 msg = MACROvalidate(mc);
371 if (msg == MAL_SUCCEED){
372 if( replaceMALblock(mb, i, mc) < 0)
373 throw(MAL,"orcam", SQLSTATE(HY001) MAL_MALLOC_FAIL);
374 } else
375 break;
376 }
377 chkTypes(cntxt->usermodule, mb, FALSE);
378 chkFlow(mb);
379 chkDeclarations(mb);
380 return msg;
381}
382
383str
384OPTmacroImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
385{
386 MalBlkPtr target= mb;
387 Module s;
388 Symbol t;
389 str mod,fcn;
390 int j;
391 str msg = MAL_SUCCEED;
392
393 (void) cntxt;
394 (void) stk;
395
396 if( p->argc == 3){
397 mod= getArgDefault(mb,p,1);
398 fcn= getArgDefault(mb,p,2);
399 } else {
400 mod= getArgDefault(mb,p,1);
401 fcn= getArgDefault(mb,p,2);
402 t= findSymbol(cntxt->usermodule, putName(mod), fcn);
403 if( t == 0)
404 return 0;
405 target= t->def;
406 mod= getArgDefault(mb,p,3);
407 fcn= getArgDefault(mb,p,4);
408 }
409 s = findModule(cntxt->usermodule, putName(mod));
410 if (s == 0)
411 return 0;
412 if (s->space) {
413 j = getSymbolIndex(fcn);
414 for (t = s->space[j]; t != NULL; t = t->peer)
415 if (t->def->errors == 0) {
416 if (getSignature(t)->token == FUNCTIONsymbol){
417 msg = MACROprocessor(cntxt, target, t);
418 // failures from the macro expansion are ignored
419 // They leave the scene as is
420 if ( msg)
421 freeException(msg);
422 }
423 }
424 }
425 if( OPTdebug & OPTmacros){
426 fprintf(stderr, "#MACRO optimizer exit\n");
427 fprintFunction(stderr, mb, 0, LIST_MAL_ALL);
428 }
429 return MAL_SUCCEED;
430}
431/*
432 * The optimizer call infrastructure is identical to the liners
433 * function with the exception that here we inline all possible
434 * functions, regardless their
435 */
436
437str
438OPTorcamImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
439{
440 MalBlkPtr target= mb;
441 Module s;
442 Symbol t;
443 str mod,fcn;
444 int j;
445 str msg = MAL_SUCCEED;
446
447 (void) cntxt;
448 (void) stk;
449
450 if( p->argc == 3){
451 mod= getArgDefault(mb,p,1);
452 fcn= getArgDefault(mb,p,2);
453 } else {
454 mod= getArgDefault(mb,p,1);
455 fcn= getArgDefault(mb,p,2);
456 t= findSymbol(cntxt->usermodule, putName(mod), fcn);
457 if( t == 0)
458 return 0;
459 target= t->def;
460 mod= getArgDefault(mb,p,3);
461 fcn= getArgDefault(mb,p,4);
462 }
463 s = findModule(cntxt->usermodule, putName(mod));
464 if (s == 0)
465 return 0;
466 if (s->space) {
467 j = getSymbolIndex(fcn);
468 for (t = s->space[j]; t != NULL; t = t->peer)
469 if (t->def->errors == 0) {
470 if (getSignature(t)->token == FUNCTIONsymbol) {
471 freeException(msg);
472 msg =ORCAMprocessor(cntxt, target, t);
473 }
474 }
475 }
476 if( OPTdebug & OPTmacros){
477 fprintf(stderr, "#MACRO optimizer exit\n");
478 fprintFunction(stderr, mb, 0, LIST_MAL_ALL);
479 }
480 return msg;
481}
482
483str OPTmacro(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p){
484 Symbol t;
485 str msg,mod,fcn;
486 lng clk= GDKusec();
487 char buf[256];
488 lng usec = GDKusec();
489
490 if( p ==NULL )
491 return 0;
492 removeInstruction(mb, p);
493 if( p->argc == 3){
494 mod= getArgDefault(mb,p,1);
495 fcn= getArgDefault(mb,p,2);
496 } else {
497 mod= getArgDefault(mb,p,3);
498 fcn= getArgDefault(mb,p,4);
499 }
500 t= findSymbol(cntxt->usermodule, putName(mod), fcn);
501 if( t == 0)
502 return 0;
503
504 msg = MACROvalidate(t->def);
505 if( msg)
506 return msg;
507 if( mb->errors == 0)
508 msg= OPTmacroImplementation(cntxt,mb,stk,p);
509 // similar to OPTmacro
510 if( msg) {
511 freeException(msg);
512 msg= MAL_SUCCEED;
513 }
514
515 /* Defense line against incorrect plans */
516 chkTypes(cntxt->usermodule, mb, FALSE);
517 chkFlow(mb);
518 chkDeclarations(mb);
519 usec += GDKusec() - clk;
520 /* keep all actions taken as a post block comment */
521 snprintf(buf,256,"%-20s actions= 1 time=" LLFMT " usec","macro",usec);
522 newComment(mb,buf);
523 addtoMalBlkHistory(mb);
524 if (mb->errors)
525 throw(MAL, "optimizer.macro", SQLSTATE(42000) PROGRAM_GENERAL);
526 if( OPTdebug & OPTmacros){
527 fprintf(stderr, "#MACRO optimizer exit\n");
528 fprintFunction(stderr, mb, 0, LIST_MAL_ALL);
529 }
530 return msg;
531}
532
533str OPTorcam(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p){
534 Symbol t;
535 str mod,fcn;
536 lng clk= GDKusec();
537 char buf[256];
538 lng usec = GDKusec();
539 str msg = MAL_SUCCEED;
540
541 if( p ==NULL )
542 return 0;
543 removeInstruction(mb, p);
544 if( p->argc == 3){
545 mod= getArgDefault(mb,p,1);
546 fcn= getArgDefault(mb,p,2);
547 } else {
548 mod= getArgDefault(mb,p,3);
549 fcn= getArgDefault(mb,p,4);
550 }
551 t= findSymbol(cntxt->usermodule, putName(mod), fcn);
552 if( t == 0)
553 return 0;
554
555 msg = MACROvalidate(t->def);
556 if( msg)
557 return msg;
558 if( mb->errors == 0)
559 msg= OPTorcamImplementation(cntxt,mb,stk,p);
560 if( msg)
561 return msg;
562 chkTypes(cntxt->usermodule, mb, FALSE);
563 chkFlow(mb);
564 chkDeclarations(mb);
565 usec += GDKusec() - clk;
566 /* keep all actions taken as a post block comment */
567 usec = GDKusec()- usec;
568 snprintf(buf,256,"%-20s actions= 1 time=" LLFMT " usec","orcam",usec);
569 newComment(mb,buf);
570 addtoMalBlkHistory(mb);
571 if (mb->errors)
572 throw(MAL, "optimizer.orcam", SQLSTATE(42000) PROGRAM_GENERAL);
573 if( OPTdebug & OPTmacros){
574 fprintf(stderr, "#MACRO optimizer exit\n");
575 fprintFunction(stderr, mb, 0, LIST_MAL_ALL);
576 }
577 return msg;
578}
579