Line data Source code
1 : /*
2 : * SPDX-License-Identifier: MPL-2.0
3 : *
4 : * This Source Code Form is subject to the terms of the Mozilla Public
5 : * License, v. 2.0. If a copy of the MPL was not distributed with this
6 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 : *
8 : * Copyright 2024 MonetDB Foundation;
9 : * Copyright August 2008 - 2023 MonetDB B.V.;
10 : * Copyright 1997 - July 2008 CWI.
11 : */
12 :
13 : #include "monetdb_config.h"
14 : #include "opt_commonTerms.h"
15 : #include "mal_exception.h"
16 : /*
17 : * Caveat. A lot of time was lost due to constants that are indistinguisable
18 : * at the surface level. It requires the constant optimizer to be ran first.
19 : */
20 :
21 : /* The key for finding common terms is that they share variables.
22 : * Therefore we skip all constants, except for a constant only situation.
23 : */
24 :
25 : /*
26 : * Speed up simple insert operations by skipping the common terms.
27 : */
28 :
29 : static inline bool __attribute__((__pure__))
30 148728 : isProjectConst(const InstrRecord *p)
31 : {
32 148728 : return (getModuleId(p) == algebraRef && getFunctionId(p) == projectRef);
33 : }
34 :
35 : static int __attribute__((__pure__))
36 7629641 : hashInstruction(const MalBlkRecord *mb, const InstrRecord *p)
37 : {
38 7629641 : int i;
39 20941564 : for (i = p->argc - 1; i >= p->retc; i--)
40 20598127 : if (!isVarConstant(mb, getArg(p, i)))
41 7286204 : return getArg(p, i);
42 343437 : if (isVarConstant(mb, getArg(p, p->retc)))
43 343437 : return p->retc;
44 : return -1;
45 : }
46 :
47 : str
48 483990 : OPTcommonTermsImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk,
49 : InstrPtr pci)
50 : {
51 483990 : int i, j, k, barrier = 0, bailout = 0;
52 483990 : InstrPtr p, q;
53 483990 : int actions = 0;
54 483990 : int limit, slimit;
55 483990 : int duplicate;
56 483990 : int *alias = NULL;
57 483990 : int *hash = NULL, h;
58 483990 : int *list = NULL;
59 483990 : str msg = MAL_SUCCEED;
60 :
61 483990 : InstrPtr *old = NULL;
62 :
63 : /* catch simple insert operations */
64 483990 : if (isSimpleSQL(mb)) {
65 283894 : goto wrapup;
66 : }
67 :
68 200098 : (void) cntxt;
69 200098 : (void) stk;
70 200098 : alias = (int *) GDKzalloc(sizeof(int) * mb->vtop);
71 200098 : list = (int *) GDKzalloc(sizeof(int) * mb->stop);
72 200097 : hash = (int *) GDKzalloc(sizeof(int) * mb->vtop);
73 200097 : if (alias == NULL || list == NULL || hash == NULL) {
74 0 : msg = createException(MAL, "optimizer.commonTerms",
75 : SQLSTATE(HY013) MAL_MALLOC_FAIL);
76 0 : goto wrapup;
77 : }
78 :
79 200097 : old = mb->stmt;
80 200097 : limit = mb->stop;
81 200097 : slimit = mb->ssize;
82 200097 : if (newMalBlkStmt(mb, mb->ssize) < 0) {
83 0 : msg = createException(MAL, "optimizer.commonTerms",
84 : SQLSTATE(HY013) MAL_MALLOC_FAIL);
85 0 : old = NULL;
86 0 : goto wrapup;
87 : }
88 :
89 10442995 : for (i = 0; mb->errors == NULL && i < limit; i++) {
90 10442995 : p = old[i];
91 10442995 : duplicate = 0;
92 :
93 56885748 : for (k = 0; k < p->argc; k++)
94 46442753 : if (alias[getArg(p, k)])
95 181958 : getArg(p, k) = alias[getArg(p, k)];
96 :
97 10442995 : if (p->token == ENDsymbol) {
98 200092 : pushInstruction(mb, p);
99 200091 : old[i] = NULL;
100 200091 : break;
101 : }
102 : /*
103 : * Any barrier block signals the end of this optimizer,
104 : * because the impact of the block can affect the common code eliminated.
105 : */
106 20485806 : barrier |= (p->barrier == BARRIERsymbol || p->barrier == CATCHsymbol
107 10242903 : || p->barrier == RETURNsymbol);
108 : /*
109 : * Also block further optimization when you have seen an assert().
110 : * This works particularly for SQL, because it is not easy to track
111 : * the BAT identifier aliases to look for updates. The sql.assert
112 : * at least tells us that an update is planned.
113 : * Like all optimizer decisions, it is safe to stop.
114 : */
115 10242903 : barrier |= getFunctionId(p) == assertRef;
116 10242903 : if (barrier || p->token == ASSIGNsymbol) {
117 257525 : TRC_DEBUG(MAL_OPTIMIZER, "Skipped[%d]: %d %d\n", i, barrier,
118 : p->retc == p->argc);
119 257525 : pushInstruction(mb, p);
120 257520 : old[i] = NULL;
121 257520 : continue;
122 : }
123 :
124 : /* when we enter a barrier block, we should ditch all previous instructions from consideration */
125 9985378 : if (p->barrier == BARRIERsymbol || p->barrier == CATCHsymbol
126 9985378 : || p->barrier == RETURNsymbol) {
127 0 : memset(list, 0, sizeof(int) * mb->stop);
128 0 : memset(hash, 0, sizeof(int) * mb->vtop);
129 : }
130 : /* side-effect producing operators can never be replaced */
131 : /* the same holds for function calls without an argument, it is
132 : * unclear where the results comes from (e.g. clock()) */
133 9985378 : if (mayhaveSideEffects(cntxt, mb, p, TRUE) || p->argc == p->retc) {
134 1575175 : TRC_DEBUG(MAL_OPTIMIZER, "Skipped[%d] side-effect: %d\n", i,
135 : p->retc == p->argc);
136 1575175 : pushInstruction(mb, p);
137 1575144 : old[i] = NULL;
138 1575144 : continue;
139 : }
140 : /* simple SQL bind operations need not be merged, they are cheap
141 : * and/or can be duplicated eliminated elsewhere cheaper */
142 8410440 : if (getModuleId(p) == sqlRef && (getFunctionId(p) != tidRef && getFunctionId(p) != bindRef)) {
143 576089 : pushInstruction(mb, p);
144 576089 : old[i] = NULL;
145 576089 : continue;
146 : }
147 7834351 : if (getModuleId(p) == matRef) { /* mat.packIncrement has requirement on number of instructions (or that needs an update */
148 204875 : pushInstruction(mb, p);
149 204875 : old[i] = NULL;
150 204875 : continue;
151 : }
152 :
153 : /* from here we have a candidate to look for a match */
154 :
155 7629476 : h = hashInstruction(mb, p);
156 :
157 7629476 : TRC_DEBUG(MAL_OPTIMIZER, "Candidate[%d] look at list[%d] => %d\n", i, h,
158 : hash[h]);
159 7629476 : traceInstruction(MAL_OPTIMIZER, mb, 0, p, LIST_MAL_ALL);
160 :
161 7629517 : if (h < 0) {
162 0 : pushInstruction(mb, p);
163 0 : old[i] = NULL;
164 0 : continue;
165 : }
166 :
167 7629517 : bailout = 1024; // don't run over long collision list
168 : /* Look into the hash structure for matching instructions */
169 46684539 : for (j = hash[h]; j > 0 && bailout-- > 0; j = list[j]) {
170 39188682 : if ((q = getInstrPtr(mb, j))
171 39188682 : && getFunctionId(q) == getFunctionId(p)
172 27966539 : && getModuleId(q) == getModuleId(p)) {
173 27966518 : TRC_DEBUG(MAL_OPTIMIZER,
174 : "Candidate[%d->%d] %d %d :%d %d %d=%d %d %d %d\n", j,
175 : list[j], hasSameSignature(mb, p, q),
176 : hasSameArguments(mb, p, q), q->token != ASSIGNsymbol,
177 : list[getArg(q, q->argc - 1)], i, !hasCommonResults(p,
178 : q),
179 : !isUnsafeFunction(q), !isUpdateInstruction(q),
180 : isLinearFlow(q));
181 27966518 : traceInstruction(MAL_OPTIMIZER, mb, 0, q, LIST_MAL_ALL);
182 :
183 : /*
184 : * Simple assignments are not replaced either. They should be
185 : * handled by the alias removal part. All arguments should
186 : * be assigned their value before instruction p.
187 : */
188 27966311 : if (hasSameArguments(mb, p, q)
189 148746 : && hasSameSignature(mb, p, q)
190 148728 : && !hasCommonResults(p, q)
191 148728 : && !isUnsafeFunction(q)
192 148728 : && !isUpdateInstruction(q)
193 148728 : && !isProjectConst(q) && /* disable project(x,val), as its used for the result of case statements */
194 133598 : isLinearFlow(q)) {
195 133598 : if (safetyBarrier(p, q)) {
196 0 : TRC_DEBUG(MAL_OPTIMIZER, "Safety barrier reached\n");
197 : break;
198 : }
199 133598 : duplicate = 1;
200 133598 : clrFunction(p);
201 133598 : p->argc = p->retc;
202 276765 : for (k = 0; k < q->retc; k++) {
203 143167 : alias[getArg(p, k)] = getArg(q, k);
204 : /* we know the arguments fit so the instruction can safely be patched */
205 143167 : p = pushArgument(mb, p, getArg(q, k));
206 : }
207 :
208 133598 : TRC_DEBUG(MAL_OPTIMIZER, "Modified expression %d -> %d ",
209 : getArg(p, 0), getArg(p, 1));
210 133598 : traceInstruction(MAL_OPTIMIZER, mb, 0, p, LIST_MAL_ALL);
211 :
212 133598 : actions++;
213 133598 : break; /* end of search */
214 : }
215 11222164 : } else if (isUpdateInstruction(p)) {
216 0 : TRC_DEBUG(MAL_OPTIMIZER, "Skipped: %d %d\n",
217 : mayhaveSideEffects(cntxt, mb, q, TRUE),
218 : isUpdateInstruction(p));
219 0 : traceInstruction(MAL_OPTIMIZER, mb, 0, q, LIST_MAL_ALL);
220 : }
221 : }
222 :
223 7629455 : if (duplicate) {
224 133598 : pushInstruction(mb, p);
225 133598 : old[i] = NULL;
226 133598 : continue;
227 : }
228 : /* update the hash structure with another candidate for reuse */
229 7495857 : TRC_DEBUG(MAL_OPTIMIZER,
230 : "Update hash[%d] - look at arg '%d' hash '%d' list '%d'\n", i,
231 : getArg(p, p->argc - 1), h, hash[h]);
232 7495857 : traceInstruction(MAL_OPTIMIZER, mb, 0, p, LIST_MAL_ALL);
233 :
234 7495832 : if (!mayhaveSideEffects(cntxt, mb, p, TRUE) && p->argc != p->retc
235 14991649 : && isLinearFlow(p) && !isUnsafeFunction(p)
236 7495748 : && !isUpdateInstruction(p)) {
237 7495695 : list[i] = hash[h];
238 7495695 : hash[h] = i;
239 7495695 : pushInstruction(mb, p);
240 7495674 : old[i] = NULL;
241 : }
242 : }
243 46472123 : for (; i < slimit; i++)
244 46272029 : if (old[i])
245 5070707 : pushInstruction(mb, old[i]);
246 : /* Defense line against incorrect plans */
247 200094 : if (actions > 0) {
248 10072 : msg = chkTypes(cntxt->usermodule, mb, FALSE);
249 10072 : if (!msg)
250 10072 : msg = chkFlow(mb);
251 10072 : if (!msg)
252 10072 : msg = chkDeclarations(mb);
253 : }
254 190022 : wrapup:
255 : /* keep actions taken as a fake argument */
256 483988 : (void) pushInt(mb, pci, actions);
257 :
258 483989 : if (alias)
259 200095 : GDKfree(alias);
260 483991 : if (list)
261 200097 : GDKfree(list);
262 483991 : if (hash)
263 200097 : GDKfree(hash);
264 483990 : if (old)
265 200096 : GDKfree(old);
266 483992 : return msg;
267 : }
|
