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