LCOV - code coverage report
Current view: top level - monetdb5/optimizer - opt_commonTerms.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 92 104 88.5 %
Date: 2021-10-13 02:24:04 Functions: 2 2 100.0 %

          Line data    Source code
       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 - 2021 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             : /* The key for finding common terms is that they share variables.
      18             :  * Therefore we skip all constants, except for a constant only situation.
      19             :  */
      20             : 
      21             : /*
      22             :  * Speed up simple insert operations by skipping the common terms.
      23             : */
      24             : 
      25             : static int
      26             : isProjectConst(InstrPtr p)
      27             : {
      28      128668 :         if (getModuleId(p)== algebraRef && getFunctionId(p)== projectRef)
      29             :                 return TRUE;
      30             :         return FALSE;
      31             : }
      32             : 
      33             : static int
      34     7381769 : hashInstruction(MalBlkPtr mb, InstrPtr p)
      35             : {
      36             :         int i;
      37    13546526 :         for ( i = p->argc - 1 ; i >= p->retc; i--)
      38    13286706 :                 if (! isVarConstant(mb,getArg(p,i)) )
      39     7121949 :                         return getArg(p,i);
      40      259820 :         if (isVarConstant(mb,getArg(p, p->retc)) )
      41      259820 :                 return p->retc;
      42             :         return -1;
      43             : }
      44             : 
      45             : str
      46      353098 : OPTcommonTermsImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
      47             : {
      48             :         int i, j, k, barrier= 0, bailout = 0;
      49             :         InstrPtr p, q;
      50             :         int actions = 0;
      51             :         int limit, slimit;
      52             :         int duplicate;
      53             :         int *alias = NULL;
      54             :         int *hash = NULL, h;
      55             :         int *list = NULL;
      56             :         str msg = MAL_SUCCEED;
      57             : 
      58             :         InstrPtr *old = NULL;
      59             : 
      60             :         /* catch simple insert operations */
      61      353098 :         if( isSimpleSQL(mb)){
      62      203899 :                 goto wrapup;
      63             :         }
      64             : 
      65             :         (void) cntxt;
      66             :         (void) stk;
      67      149199 :         alias = (int*) GDKzalloc(sizeof(int) * mb->vtop);
      68      149199 :         list = (int*) GDKzalloc(sizeof(int) * mb->stop);
      69      149199 :         hash = (int*) GDKzalloc(sizeof(int) * mb->vtop);
      70      149199 :         if ( alias == NULL || list == NULL || hash == NULL){
      71           0 :                 msg = createException(MAL,"optimizer.commonTerms", SQLSTATE(HY013) MAL_MALLOC_FAIL);
      72           0 :                 goto wrapup;
      73             :         }
      74             : 
      75      149199 :         old = mb->stmt;
      76      149199 :         limit = mb->stop;
      77      149199 :         slimit = mb->ssize;
      78      149199 :         if ( newMalBlkStmt(mb, mb->ssize) < 0) {
      79           0 :                 msg = createException(MAL,"optimizer.commonTerms", SQLSTATE(HY013) MAL_MALLOC_FAIL);
      80             :                 old = NULL;
      81           0 :                 goto wrapup;
      82             :         }
      83             : 
      84    11605605 :         for ( i = 0; i < limit; i++) {
      85    11605605 :                 p = old[i];
      86             :                 duplicate = 0;
      87             : 
      88    62927341 :                 for ( k = 0; k < p->argc; k++)
      89    51321736 :                         if ( alias[getArg(p,k)] )
      90      149056 :                                 getArg(p,k) = alias[getArg(p,k)];
      91             : 
      92    11605605 :                 if (p->token == ENDsymbol){
      93      149199 :                         pushInstruction(mb,p);
      94             :                         /* wrap up the remainder */
      95     4621947 :                         for(i++; i<limit; i++)
      96     4472748 :                                 if( old[i])
      97     4472748 :                                         pushInstruction(mb,old[i]);
      98             :                         break;
      99             :                 }
     100             :                 /*
     101             :                  * Any barrier block signals the end of this optimizer,
     102             :                  * because the impact of the block can affect the common code eliminated.
     103             :                  */
     104    11456406 :                 barrier |= (p->barrier== BARRIERsymbol || p->barrier== CATCHsymbol || p->barrier == RETURNsymbol);
     105             :                 /*
     106             :                  * Also block further optimization when you have seen an assert().
     107             :                  * This works particularly for SQL, because it is not easy to track
     108             :                  * the BAT identifier aliases to look for updates. The sql.assert
     109             :                  * at least tells us that an update is planned.
     110             :                  * Like all optimizer decisions, it is safe to stop.
     111             :                  */
     112    11456406 :                 barrier |= getFunctionId(p) == assertRef;
     113    11456406 :                 if (barrier || p->token == NOOPsymbol || p->token == ASSIGNsymbol) {
     114      178111 :                         TRC_DEBUG(MAL_OPTIMIZER, "Skipped[%d]: %d %d\n", i, barrier, p->retc == p->argc);
     115      178111 :                         pushInstruction(mb,p);
     116      178109 :                         continue;
     117             :                 }
     118             : 
     119             :                 /* when we enter a barrier block, we should ditch all previous instructions from consideration */
     120    11278295 :                 if( p->barrier== BARRIERsymbol || p->barrier== CATCHsymbol || p->barrier == RETURNsymbol){
     121           0 :                         memset(list, 0, sizeof(int) * mb->stop);
     122           0 :                         memset(hash, 0, sizeof(int) * mb->vtop);
     123             :                 }
     124             :                 /* side-effect producing operators can never be replaced */
     125             :                 /* the same holds for function calls without an argument, it is unclear where the results comes from (e.g. clock()) */
     126    11278295 :                 if ( mayhaveSideEffects(cntxt, mb, p,TRUE) || p->argc == p->retc){
     127     1619457 :                         TRC_DEBUG(MAL_OPTIMIZER, "Skipped[%d] side-effect: %d\n", i, p->retc == p->argc);
     128     1619457 :                         pushInstruction(mb,p);
     129     1619457 :                         continue;
     130             :                 }
     131             :                 /* simple SQL bind operations need not be merged, they are cheap and/or can be duplicated eliminated elsewhere cheaper */
     132     9658843 :                 if( getModuleId(p) == sqlRef && getFunctionId(p) != tidRef){
     133     2277074 :                         pushInstruction(mb,p);
     134     2277074 :                         continue;
     135             :                 }
     136             : 
     137             :                 /* from here we have a candidate to look for a match */
     138             : 
     139     7381769 :                 h = hashInstruction(mb, p);
     140             : 
     141     7381769 :                 TRC_DEBUG(MAL_OPTIMIZER, "Candidate[%d] look at list[%d] => %d\n", i, h, hash[h]);
     142     7381769 :                 traceInstruction(MAL_OPTIMIZER, mb, 0, p, LIST_MAL_ALL);
     143             : 
     144     7381769 :                 if( h < 0){
     145           0 :                         pushInstruction(mb,p);
     146           0 :                         continue;
     147             :                 }
     148             : 
     149             :                 bailout = 1024 ;  // don't run over long collision list
     150             :                 /* Look into the hash structure for matching instructions */
     151    11965750 :                 for (j = hash[h];  j > 0 && bailout-- > 0  ; j = list[j])
     152     4699967 :                         if ( (q= getInstrPtr(mb,j)) && getFunctionId(q) == getFunctionId(p) && getModuleId(q) == getModuleId(p)){
     153     3944850 :                                 TRC_DEBUG(MAL_OPTIMIZER, "Candidate[%d->%d] %d %d :%d %d %d=%d %d %d %d\n",
     154             :                                         j, list[j],
     155             :                                         hasSameSignature(mb, p, q),
     156             :                                         hasSameArguments(mb, p, q),
     157             :                                         q->token != ASSIGNsymbol ,
     158             :                                         list[getArg(q,q->argc-1)],i,
     159             :                                         !hasCommonResults(p, q),
     160             :                                         !isUnsafeFunction(q),
     161             :                                         !isUpdateInstruction(q),
     162             :                                         isLinearFlow(q));
     163     3944850 :                                 traceInstruction(MAL_OPTIMIZER, mb, 0, q, LIST_MAL_ALL);
     164             : 
     165             :                                 /*
     166             :                                  * Simple assignments are not replaced either. They should be
     167             :                                  * handled by the alias removal part. All arguments should
     168             :                                  * be assigned their value before instruction p.
     169             :                                  */
     170     4073520 :                                 if ( hasSameArguments(mb, p, q) &&
     171      257340 :                                          hasSameSignature(mb, p, q) &&
     172      257338 :                                          !hasCommonResults(p, q) &&
     173      257336 :                                          !isUnsafeFunction(q) &&
     174      128668 :                                          !isUpdateInstruction(q) &&
     175      115986 :                                          !isProjectConst(q) && /* disable project(x,val), as its used for the result of case statements */
     176      115986 :                                          isLinearFlow(q)
     177             :                                         ) {
     178      115986 :                                         if (safetyBarrier(p, q) ){
     179           0 :                                                 TRC_DEBUG(MAL_OPTIMIZER, "Safety barrier reached\n");
     180             :                                                 break;
     181             :                                         }
     182             :                                         duplicate = 1;
     183      115986 :                                         clrFunction(p);
     184      115986 :                                         p->argc = p->retc;
     185      233021 :                                         for (k = 0; k < q->retc; k++){
     186      117035 :                                                 alias[getArg(p,k)] = getArg(q,k);
     187             :                                                 /* we know the arguments fit so the instruction can safely be patched */
     188      117035 :                                                 p= addArgument(mb,p, getArg(q,k));
     189             :                                         }
     190             : 
     191      115986 :                                         TRC_DEBUG(MAL_OPTIMIZER, "Modified expression %d -> %d ", getArg(p,0), getArg(p,1));
     192      115986 :                                         traceInstruction(MAL_OPTIMIZER, mb, 0, p, LIST_MAL_ALL);
     193             : 
     194      115986 :                                         actions++;
     195      115986 :                                         break; /* end of search */
     196             :                                 }
     197             :                         }
     198             : 
     199      755117 :                         else if(isUpdateInstruction(p)){
     200           0 :                                 TRC_DEBUG(MAL_OPTIMIZER, "Skipped: %d %d\n", mayhaveSideEffects(cntxt, mb, q, TRUE) , isUpdateInstruction(p));
     201           0 :                                 traceInstruction(MAL_OPTIMIZER, mb, 0, q, LIST_MAL_ALL);
     202             :                         }
     203             : 
     204     7381769 :                 if (duplicate){
     205      115986 :                         pushInstruction(mb,p);
     206      115986 :                         continue;
     207             :                 }
     208             :                 /* update the hash structure with another candidate for re-use */
     209     7265783 :                 TRC_DEBUG(MAL_OPTIMIZER, "Update hash[%d] - look at arg '%d' hash '%d' list '%d'\n", i, getArg(p,p->argc-1), h, hash[h]);
     210     7265783 :                 traceInstruction(MAL_OPTIMIZER, mb, 0, p, LIST_MAL_ALL);
     211             : 
     212     7265783 :                 if ( !mayhaveSideEffects(cntxt, mb, p, TRUE) && p->argc != p->retc &&  isLinearFlow(p) && !isUnsafeFunction(p) && !isUpdateInstruction(p)){
     213     7265779 :                         list[i] = hash[h];
     214     7265779 :                         hash[h] = i;
     215     7265779 :                         pushInstruction(mb,p);
     216             :                 }
     217             :         }
     218    28430988 :         for(; i<slimit; i++)
     219    28281789 :                 if( old[i])
     220           0 :                         pushInstruction(mb,old[i]);
     221             :         /* Defense line against incorrect plans */
     222      149199 :         if( actions > 0){
     223       10616 :                 msg = chkTypes(cntxt->usermodule, mb, FALSE);
     224       10616 :                 if (!msg)
     225       10616 :                         msg = chkFlow(mb);
     226       10616 :                 if (!msg)
     227       10616 :                         msg = chkDeclarations(mb);
     228             :         }
     229      138583 : wrapup:
     230             :         /* keep actions taken as a fake argument*/
     231      353098 :         (void) pushInt(mb, pci, actions);
     232             : 
     233      353098 :         if(alias) GDKfree(alias);
     234      353098 :         if(list) GDKfree(list);
     235      353098 :         if(hash) GDKfree(hash);
     236      353098 :         if(old) GDKfree(old);
     237      353098 :         return msg;
     238             : }

Generated by: LCOV version 1.14