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_commonTerms.h"
11#include "mal_exception.h"
12 /*
13 * Caveat. A lot of time was lost due to constants that are indistinguisable
14 * at the surface level. It requires the constant optimizer to be ran first.
15 */
16
17#define HASHinstruction(X) getArg((X), (X)->argc-1)
18
19str
20OPTcommonTermsImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
21{
22 int i, j, k, barrier= 0;
23 InstrPtr p, q;
24 int actions = 0;
25 int limit, slimit;
26 int duplicate;
27 int *alias;
28 int *hash;
29 int *list;
30
31 InstrPtr *old = NULL;
32 char buf[256];
33 lng usec = GDKusec();
34 str msg = MAL_SUCCEED;
35
36 (void) cntxt;
37 (void) stk;
38 (void) pci;
39 alias = (int*) GDKzalloc(sizeof(int) * mb->vtop);
40 list = (int*) GDKzalloc(sizeof(int) * mb->stop);
41 hash = (int*) GDKzalloc(sizeof(int) * mb->vtop);
42 if ( alias == NULL || list == NULL || hash == NULL){
43 msg = createException(MAL,"optimizer.commonTerms", SQLSTATE(HY001) MAL_MALLOC_FAIL);
44 goto wrapup;
45 }
46
47 old = mb->stmt;
48 limit = mb->stop;
49 slimit = mb->ssize;
50 if ( newMalBlkStmt(mb, mb->ssize) < 0) {
51 msg = createException(MAL,"optimizer.commonTerms", SQLSTATE(HY001) MAL_MALLOC_FAIL);
52 old = NULL;
53 goto wrapup;
54 }
55
56 for ( i = 0; i < limit; i++) {
57 p = old[i];
58 duplicate = 0;
59
60 for ( k = 0; k < p->argc; k++)
61 if ( alias[getArg(p,k)] )
62 getArg(p,k) = alias[getArg(p,k)];
63
64 if (p->token == ENDsymbol){
65 pushInstruction(mb,p);
66 /* wrap up the remainder */
67 for(i++; i<limit; i++)
68 if( old[i])
69 pushInstruction(mb,old[i]);
70 break;
71 }
72 /*
73 * Any barrier block signals the end of this optimizer,
74 * because the impact of the block can affect the common code eliminated.
75 */
76 barrier |= (p->barrier== BARRIERsymbol || p->barrier== CATCHsymbol || p->barrier == RETURNsymbol);
77 /*
78 * Also block further optimization when you have seen an assert().
79 * This works particularly for SQL, because it is not easy to track
80 * the BAT identifier aliases to look for updates. The sql.assert
81 * at least tells us that an update is planned.
82 * Like all optimizer decisions, it is safe to stop.
83 */
84 barrier |= getFunctionId(p) == assertRef;
85 if (barrier || p->token == NOOPsymbol || p->token == ASSIGNsymbol) {
86
87 if( OPTdebug & OPTcommonterms){
88 fprintf(stderr, "#COMMON SKIPPED[%d] %d %d\n",i, barrier, p->retc == p->argc);
89 }
90
91 pushInstruction(mb,p);
92 continue;
93 }
94
95 /* when we enter a barrier block, we should ditch all previous instructions from consideration */
96 if( p->barrier== BARRIERsymbol || p->barrier== CATCHsymbol || p->barrier == RETURNsymbol){
97 memset(list, 0, sizeof(int) * mb->stop);
98 memset(hash, 0, sizeof(int) * mb->vtop);
99 }
100 /* side-effect producing operators can never be replaced */
101 /* the same holds for function calls without an argument, it is unclear where the results comes from (e.g. clock()) */
102 if ( mayhaveSideEffects(cntxt, mb, p,TRUE) || p->argc == p->retc){
103
104 if( OPTdebug & OPTcommonterms){
105 fprintf(stderr, "#COMMON SKIPPED[%d] side-effect %d\n", i, p->retc == p->argc);
106 }
107
108 pushInstruction(mb,p);
109 continue;
110 }
111
112 /* from here we have a candidate to look for a match */
113
114 if( OPTdebug & OPTcommonterms){
115 fprintf(stderr,"#CANDIDATE[%d] look at list[%d]=>%d\n",
116 i, HASHinstruction(p), hash[HASHinstruction(p)]);
117 fprintInstruction(stderr, mb, 0, p, LIST_MAL_ALL);
118 }
119
120 /* Look into the hash structure for matching instructions */
121 for (j = hash[HASHinstruction(p)]; j > 0 ; j = list[j])
122 if ( (q= getInstrPtr(mb,j)) && getFunctionId(q) == getFunctionId(p) && getModuleId(q) == getModuleId(p) ){
123
124 if( OPTdebug & OPTcommonterms){
125 fprintf(stderr,"#CANDIDATE[%d->%d] %d %d :%d %d %d=%d %d %d %d ",
126 j, list[j],
127 hasSameSignature(mb, p, q),
128 hasSameArguments(mb, p, q),
129 q->token != ASSIGNsymbol ,
130 list[getArg(q,q->argc-1)],i,
131 !hasCommonResults(p, q),
132 !isUnsafeFunction(q),
133 !isUpdateInstruction(q),
134 isLinearFlow(q));
135 fprintInstruction(stderr, mb, 0, q, LIST_MAL_ALL);
136 }
137
138 /*
139 * Simple assignments are not replaced either. They should be
140 * handled by the alias removal part. All arguments should
141 * be assigned their value before instruction p.
142 */
143 if ( hasSameArguments(mb, p, q) &&
144 hasSameSignature(mb, p, q) &&
145 !hasCommonResults(p, q) &&
146 !isUnsafeFunction(q) &&
147 !isUpdateInstruction(q) &&
148 isLinearFlow(q)
149 ) {
150 if (safetyBarrier(p, q) ){
151
152 if( OPTdebug & OPTcommonterms){
153 fprintf(stderr,"#safetybarrier reached\n");
154 }
155
156 break;
157 }
158 duplicate = 1;
159 clrFunction(p);
160 p->argc = p->retc;
161 for (k = 0; k < q->retc; k++){
162 alias[getArg(p,k)] = getArg(q,k);
163 p= pushArgument(mb,p, getArg(q,k));
164 }
165
166 if( OPTdebug & OPTcommonterms){
167 fprintf(stderr, "#MODIFIED EXPRESSION %d -> %d ",getArg(p,0),getArg(p,1));
168 fprintInstruction(stderr, mb, 0, p, LIST_MAL_ALL);
169 }
170
171 actions++;
172 break; /* end of search */
173 }
174 }
175
176 else if( OPTdebug & OPTcommonterms && isUpdateInstruction(p)){
177 fprintf(stderr, "#COMMON SKIPPED %d %d ", mayhaveSideEffects(cntxt, mb, q, TRUE) , isUpdateInstruction(p));
178 fprintInstruction(stderr, mb, 0, q, LIST_MAL_ALL);
179 }
180
181 if (duplicate){
182 pushInstruction(mb,p);
183 continue;
184 }
185 /* update the hash structure with another candidate for re-use */
186
187 if( OPTdebug & OPTcommonterms){
188 fprintf(stderr,"#UPDATE HASH[%d] look at arg %d hash %d list %d\n",
189 i, getArg(p,p->argc-1), HASHinstruction(p), hash[HASHinstruction(p)]);
190 fprintInstruction(stderr, mb, 0, p, LIST_MAL_ALL);
191 }
192
193 if ( !mayhaveSideEffects(cntxt, mb, p, TRUE) && p->argc != p->retc && isLinearFlow(p) && !isUnsafeFunction(p) && !isUpdateInstruction(p)){
194 list[i] = hash[HASHinstruction(p)];
195 hash[HASHinstruction(p)] = i;
196 pushInstruction(mb,p);
197 }
198 }
199 for(; i<slimit; i++)
200 if( old[i])
201 freeInstruction(old[i]);
202 /* Defense line against incorrect plans */
203 if( actions > 0){
204 chkTypes(cntxt->usermodule, mb, FALSE);
205 chkFlow(mb);
206 chkDeclarations(mb);
207 }
208 /* keep all actions taken as a post block comment */
209 usec = GDKusec()- usec;
210 snprintf(buf,256,"%-20s actions=%2d time=" LLFMT " usec","commonTerms",actions,usec);
211 newComment(mb,buf);
212 if( actions >= 0)
213 addtoMalBlkHistory(mb);
214
215 wrapup:
216 if(alias) GDKfree(alias);
217 if(list) GDKfree(list);
218 if(hash) GDKfree(hash);
219 if(old) GDKfree(old);
220 if( OPTdebug & OPTcommonterms){
221 fprintf(stderr, "#COMMONTERMS optimizer exit\n");
222 fprintFunction(stderr, mb, 0, LIST_MAL_ALL);
223 }
224 return msg;
225}
226