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 : __attribute__((__pure__))
30 : static inline bool
31 151328 : isProjectConst(const InstrRecord *p)
32 : {
33 151328 : return (getModuleId(p) == algebraRef && getFunctionId(p) == projectRef);
34 : }
35 :
36 : static int __attribute__((__pure__))
37 7633218 : hashInstruction(const MalBlkRecord *mb, const InstrRecord *p)
38 : {
39 7633218 : int i;
40 20907147 : for (i = p->argc - 1; i >= p->retc; i--)
41 20564370 : if (!isVarConstant(mb, getArg(p, i)))
42 7290441 : return getArg(p, i);
43 342777 : if (isVarConstant(mb, getArg(p, p->retc)))
44 342777 : return p->retc;
45 : return -1;
46 : }
47 :
48 : str
49 495702 : OPTcommonTermsImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk,
50 : InstrPtr pci)
51 : {
52 495702 : int i, j, k, barrier = 0, bailout = 0;
53 495702 : InstrPtr p, q;
54 495702 : int actions = 0;
55 495702 : int limit, slimit;
56 495702 : int duplicate;
57 495702 : int *alias = NULL;
58 495702 : int *hash = NULL, h;
59 495702 : int *list = NULL;
60 495702 : str msg = MAL_SUCCEED;
61 :
62 495702 : InstrPtr *old = NULL;
63 :
64 : /* catch simple insert operations */
65 495702 : if (isSimpleSQL(mb)) {
66 285180 : goto wrapup;
67 : }
68 :
69 210522 : (void) cntxt;
70 210522 : (void) stk;
71 210522 : alias = (int *) GDKzalloc(sizeof(int) * mb->vtop);
72 210522 : list = (int *) GDKzalloc(sizeof(int) * mb->stop);
73 210522 : hash = (int *) GDKzalloc(sizeof(int) * mb->vtop);
74 210522 : if (alias == NULL || list == NULL || hash == NULL) {
75 0 : msg = createException(MAL, "optimizer.commonTerms",
76 : SQLSTATE(HY013) MAL_MALLOC_FAIL);
77 0 : goto wrapup;
78 : }
79 :
80 210522 : old = mb->stmt;
81 210522 : limit = mb->stop;
82 210522 : slimit = mb->ssize;
83 210522 : if (newMalBlkStmt(mb, mb->ssize) < 0) {
84 0 : msg = createException(MAL, "optimizer.commonTerms",
85 : SQLSTATE(HY013) MAL_MALLOC_FAIL);
86 0 : old = NULL;
87 0 : goto wrapup;
88 : }
89 :
90 10603232 : for (i = 0; mb->errors == NULL && i < limit; i++) {
91 10603232 : p = old[i];
92 10603232 : duplicate = 0;
93 :
94 57910153 : for (k = 0; k < p->argc; k++)
95 47306921 : if (alias[getArg(p, k)])
96 184441 : getArg(p, k) = alias[getArg(p, k)];
97 :
98 10603232 : if (p->token == ENDsymbol) {
99 210517 : pushInstruction(mb, p);
100 210514 : old[i] = NULL;
101 210514 : break;
102 : }
103 : /*
104 : * Any barrier block signals the end of this optimizer,
105 : * because the impact of the block can affect the common code eliminated.
106 : */
107 20785430 : barrier |= (p->barrier == BARRIERsymbol || p->barrier == CATCHsymbol
108 10392715 : || p->barrier == RETURNsymbol);
109 : /*
110 : * Also block further optimization when you have seen an assert().
111 : * This works particularly for SQL, because it is not easy to track
112 : * the BAT identifier aliases to look for updates. The sql.assert
113 : * at least tells us that an update is planned.
114 : * Like all optimizer decisions, it is safe to stop.
115 : */
116 10392715 : barrier |= getFunctionId(p) == assertRef;
117 10392715 : if (barrier || p->token == ASSIGNsymbol) {
118 257603 : TRC_DEBUG(MAL_OPTIMIZER, "Skipped[%d]: %d %d\n", i, barrier,
119 : p->retc == p->argc);
120 257603 : pushInstruction(mb, p);
121 257600 : old[i] = NULL;
122 257600 : continue;
123 : }
124 :
125 : /* when we enter a barrier block, we should ditch all previous instructions from consideration */
126 10135112 : if (p->barrier == BARRIERsymbol || p->barrier == CATCHsymbol
127 10135112 : || p->barrier == RETURNsymbol) {
128 0 : memset(list, 0, sizeof(int) * mb->stop);
129 0 : memset(hash, 0, sizeof(int) * mb->vtop);
130 : }
131 : /* side-effect producing operators can never be replaced */
132 : /* the same holds for function calls without an argument, it is
133 : * unclear where the results comes from (e.g. clock()) */
134 10135112 : if (mayhaveSideEffects(cntxt, mb, p, TRUE) || p->argc == p->retc) {
135 1724551 : TRC_DEBUG(MAL_OPTIMIZER, "Skipped[%d] side-effect: %d\n", i,
136 : p->retc == p->argc);
137 1724551 : pushInstruction(mb, p);
138 1724519 : old[i] = NULL;
139 1724519 : continue;
140 : }
141 : /* simple SQL bind operations need not be merged, they are cheap
142 : * and/or can be duplicated eliminated elsewhere cheaper */
143 8410842 : if (getModuleId(p) == sqlRef && (getFunctionId(p) != tidRef && getFunctionId(p) != bindRef)) {
144 573070 : pushInstruction(mb, p);
145 573070 : old[i] = NULL;
146 573070 : continue;
147 : }
148 7837772 : if (getModuleId(p) == matRef) { /* mat.packIncrement has requirement on number of instructions (or that needs an update */
149 204732 : pushInstruction(mb, p);
150 204732 : old[i] = NULL;
151 204732 : continue;
152 : }
153 :
154 : /* from here we have a candidate to look for a match */
155 :
156 7633040 : h = hashInstruction(mb, p);
157 :
158 7633040 : TRC_DEBUG(MAL_OPTIMIZER, "Candidate[%d] look at list[%d] => %d\n", i, h,
159 : hash[h]);
160 7633040 : traceInstruction(MAL_OPTIMIZER, mb, 0, p, LIST_MAL_ALL);
161 :
162 7633080 : if (h < 0) {
163 0 : pushInstruction(mb, p);
164 0 : old[i] = NULL;
165 0 : continue;
166 : }
167 :
168 7633080 : bailout = 1024; // don't run over long collision list
169 : /* Look into the hash structure for matching instructions */
170 46815479 : for (j = hash[h]; j > 0 && bailout-- > 0; j = list[j]) {
171 39318631 : if ((q = getInstrPtr(mb, j))
172 39318631 : && getFunctionId(q) == getFunctionId(p)
173 28101448 : && getModuleId(q) == getModuleId(p)) {
174 28101427 : TRC_DEBUG(MAL_OPTIMIZER,
175 : "Candidate[%d->%d] %d %d :%d %d %d=%d %d %d %d\n", j,
176 : list[j], hasSameSignature(mb, p, q),
177 : hasSameArguments(mb, p, q), q->token != ASSIGNsymbol,
178 : list[getArg(q, q->argc - 1)], i, !hasCommonResults(p,
179 : q),
180 : !isUnsafeFunction(q), !isUpdateInstruction(q),
181 : isLinearFlow(q));
182 28101427 : traceInstruction(MAL_OPTIMIZER, mb, 0, q, LIST_MAL_ALL);
183 :
184 : /*
185 : * Simple assignments are not replaced either. They should be
186 : * handled by the alias removal part. All arguments should
187 : * be assigned their value before instruction p.
188 : */
189 28100124 : if (hasSameArguments(mb, p, q)
190 151346 : && hasSameSignature(mb, p, q)
191 151328 : && !hasCommonResults(p, q)
192 151328 : && !isUnsafeFunction(q)
193 151328 : && !isUpdateInstruction(q)
194 151328 : && !isProjectConst(q) && /* disable project(x,val), as its used for the result of case statements */
195 136198 : isLinearFlow(q)) {
196 136198 : if (safetyBarrier(p, q)) {
197 0 : TRC_DEBUG(MAL_OPTIMIZER, "Safety barrier reached\n");
198 : break;
199 : }
200 136198 : duplicate = 1;
201 136198 : clrFunction(p);
202 136198 : p->argc = p->retc;
203 281934 : for (k = 0; k < q->retc; k++) {
204 145736 : alias[getArg(p, k)] = getArg(q, k);
205 : /* we know the arguments fit so the instruction can safely be patched */
206 145736 : p = pushArgument(mb, p, getArg(q, k));
207 : }
208 :
209 136198 : TRC_DEBUG(MAL_OPTIMIZER, "Modified expression %d -> %d ",
210 : getArg(p, 0), getArg(p, 1));
211 136198 : traceInstruction(MAL_OPTIMIZER, mb, 0, p, LIST_MAL_ALL);
212 :
213 136198 : actions++;
214 136198 : break; /* end of search */
215 : }
216 11217204 : } else if (isUpdateInstruction(p)) {
217 0 : TRC_DEBUG(MAL_OPTIMIZER, "Skipped: %d %d\n",
218 : mayhaveSideEffects(cntxt, mb, q, TRUE),
219 : isUpdateInstruction(p));
220 0 : traceInstruction(MAL_OPTIMIZER, mb, 0, q, LIST_MAL_ALL);
221 : }
222 : }
223 :
224 7633046 : if (duplicate) {
225 136198 : pushInstruction(mb, p);
226 136198 : old[i] = NULL;
227 136198 : continue;
228 : }
229 : /* update the hash structure with another candidate for reuse */
230 7496848 : TRC_DEBUG(MAL_OPTIMIZER,
231 : "Update hash[%d] - look at arg '%d' hash '%d' list '%d'\n", i,
232 : getArg(p, p->argc - 1), h, hash[h]);
233 7496848 : traceInstruction(MAL_OPTIMIZER, mb, 0, p, LIST_MAL_ALL);
234 :
235 7496812 : if (!mayhaveSideEffects(cntxt, mb, p, TRUE) && p->argc != p->retc
236 14993522 : && isLinearFlow(p) && !isUnsafeFunction(p)
237 7496692 : && !isUpdateInstruction(p)) {
238 7496601 : list[i] = hash[h];
239 7496601 : hash[h] = i;
240 7496601 : pushInstruction(mb, p);
241 7496599 : old[i] = NULL;
242 : }
243 : }
244 49007132 : for (; i < slimit; i++)
245 48796612 : if (old[i])
246 5383536 : pushInstruction(mb, old[i]);
247 : /* Defense line against incorrect plans */
248 210520 : if (actions > 0) {
249 10062 : msg = chkTypes(cntxt->usermodule, mb, FALSE);
250 10062 : if (!msg)
251 10062 : msg = chkFlow(mb);
252 10062 : if (!msg)
253 10062 : msg = chkDeclarations(mb);
254 : }
255 200458 : wrapup:
256 : /* keep actions taken as a fake argument */
257 495700 : (void) pushInt(mb, pci, actions);
258 :
259 495700 : if (alias)
260 210520 : GDKfree(alias);
261 495702 : if (list)
262 210522 : GDKfree(list);
263 495702 : if (hash)
264 210522 : GDKfree(hash);
265 495702 : if (old)
266 210522 : GDKfree(old);
267 495702 : return msg;
268 : }
|
