LCOV - code coverage report
Current view: top level - monetdb5/optimizer - opt_reorder.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 69 81 85.2 %
Date: 2021-10-13 02:24:04 Functions: 1 1 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             : /*
      10             :  * The dataflow reorder
      11             :  * MAL programs are largely logical descriptions of an execution plan.
      12             :  * After the mitosis and mergetable optimizers we have a large program, which when
      13             :  * executed as is, does not necessarily benefit from the locality
      14             :  * of data and operations. The problem is that the execution plan is
      15             :  * a DAG for which a topological order should be found that
      16             :  * minimizes the life time of variables and maximizes parallel execution.
      17             :  * This is an NP hard optimization problem. Therefore, we have
      18             :  * to rely on an affordable heuristic steps.
      19             :  *
      20             :  * The reorder optimizer transfers the breadth-first plans of
      21             :  * the mergetable into a multi-phase execution plan.
      22             :  * This increases cohesion for parallel execution.
      23             :  * A subquery is processed completely as quickly as possible.
      24             :  * Only when the subquery is stalled for available input, the
      25             :  * threads may start working on another subquery.
      26             :  *
      27             :  */
      28             : #include "monetdb_config.h"
      29             : #include "opt_reorder.h"
      30             : #include "mal_instruction.h"
      31             : #include "mal_interpreter.h"
      32             : #include "opt_mitosis.h"
      33             : 
      34             : 
      35             : /* Insert the instruction immediately after a previous instruction that
      36             :  * generated an argument needed.
      37             :  * If non can be found, add it to the end.
      38             :  * Be aware of side-effect instructions, they may not be skipped.
      39             :  */
      40             : str
      41      353097 : OPTreorderImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
      42             : {
      43             :         int i,j,k, blkcnt = 1, pc = 0, actions = 0;
      44             :         InstrPtr p= NULL, *old = NULL;
      45             :         int limit, slimit, *depth = NULL;
      46             :         str msg = MAL_SUCCEED;
      47      353097 :         InstrPtr *blocks[MAXSLICES] = {0};
      48      353097 :         int top[MAXSLICES] = {0};
      49      353097 :         int barriers[MAXSLICES] = {0}, btop = 0, off = 0;
      50             : 
      51   361924425 :         for(i=0; i< MAXSLICES; i++)
      52   361571328 :                 top[i] = 0;
      53      353097 :         if( isOptimizerUsed(mb, pci, mitosisRef) <= 0){
      54        1735 :                 goto wrapup;
      55             :         }
      56             :         (void) cntxt;
      57             :         (void) stk;
      58             : 
      59      351362 :         limit= mb->stop;
      60      351362 :         slimit= mb->ssize;
      61      351362 :         old = mb->stmt;
      62             : 
      63      351362 :         depth = (int*) GDKzalloc(mb->vtop * sizeof(int));
      64      351362 :         if( depth == NULL){
      65           0 :                 throw(MAL,"optimizer.reorder", SQLSTATE(HY013) MAL_MALLOC_FAIL);
      66             :         }
      67             : 
      68      351362 :         if ( newMalBlkStmt(mb, mb->ssize) < 0) {
      69           0 :                 GDKfree(depth);
      70           0 :                 throw(MAL,"optimizer.reorder", SQLSTATE(HY013) MAL_MALLOC_FAIL);
      71             :         }
      72             : 
      73             :         actions = 1;
      74             :         /* Mark the parameters as constants as beloning to depth 0; */
      75     9973879 :         for( i =0; i< limit; i++){
      76     9973879 :                 p = old[i];
      77     9973879 :                 if( !p) {
      78             :                         //mnstr_printf(cntxt->fdout, "empty stmt:pc %d \n", i);
      79           0 :                         continue;
      80             :                 }
      81     9973879 :                 if( p->token == ENDsymbol)
      82             :                         break;
      83             :                 k = off;
      84     9622517 :                 if( getModuleId(p) == sqlRef && getFunctionId(p) == tidRef && p->argc == 6){
      85      145357 :                         if (depth[getArg(p,0)] == 0){
      86      145357 :                                 k =  getVarConstant(mb, getArg(p, p->argc-2)).val.ival;
      87      145357 :                                 assert( k < MAXSLICES);
      88      145357 :                                 depth[getArg(p,0)] = k;
      89      145357 :                                 depth[getArg(p,p->retc)] = k; /* keep order of mvc input var */
      90             :                         }
      91             :                 } else
      92     9477160 :                 if( getModuleId(p) == sqlRef && getFunctionId(p) == bindRef && p->argc == 8){
      93      567902 :                         if (depth[getArg(p,0)] == 0){
      94      567902 :                                 k =  getVarConstant(mb, getArg(p, p->argc-2)).val.ival;
      95      567902 :                                 assert( k < MAXSLICES);
      96      567902 :                                 depth[getArg(p,0)] = k;
      97      567902 :                                 depth[getArg(p,p->retc)] = k; /* keep order of mvc input var */
      98             :                         }
      99             :                 } else {
     100    41130587 :                         for(j= p->retc; j <p->argc; j++){
     101    32221329 :                                 if (depth[getArg(p,j)] > k)
     102             :                                         k = depth[getArg(p,j)];
     103             :                         }
     104     8909258 :                         assert( k < MAXSLICES);
     105    19028473 :                         for(j=0; j< p->retc; j++)
     106    10119215 :                                 if( depth[getArg(p,j)] == 0)
     107    10119205 :                                         depth[getArg(p,j)] = k;
     108             :                         /* In addition to the input variables of the statements al statements within a barrier also
     109             :                          * depend on the barriers variable */
     110     8909258 :                         if (blockStart(p)) {
     111         662 :                                 assert(btop < MAXSLICES);
     112         662 :                                 barriers[btop++] = k;
     113             :                                 off = k;
     114             :                         }
     115     8909258 :                         if (blockExit(p)) {
     116             :                                 off = 0;
     117         662 :                                 if (btop--)
     118         662 :                                         off = barriers[btop];
     119             :                         }
     120             :                 }
     121             : 
     122     9622517 :                 if( top[k] == 0){
     123      459075 :                         blocks[k] = GDKzalloc(limit * sizeof(InstrPtr));
     124      459075 :                         if( blocks[k] == NULL){
     125           0 :                                 for(i=0; i< blkcnt; i++)
     126           0 :                                         if( top[i])
     127           0 :                                                 GDKfree(blocks[i]);
     128           0 :                                 GDKfree(depth);
     129           0 :                                 GDKfree(old);
     130           0 :                                 throw(MAL,"optimizer.reorder", SQLSTATE(HY013) MAL_MALLOC_FAIL);
     131             :                         }
     132             :                 }
     133     9622517 :                 blocks[k][top[k]] = p;
     134     9622517 :                 top[k]= top[k] +1;
     135             :                 //mnstr_printf(cntxt->fdout, "block[%d] :%d:",i, k);
     136             :                 //printInstruction(cntxt->fdout, mb, stk, p, LIST_MAL_DEBUG);
     137             :                 if( k > blkcnt)
     138             :                         blkcnt = k;
     139             :         }
     140             : 
     141     1124168 :         for(k =0; k <= blkcnt; k++)
     142    10395319 :                 for(j=0; j < top[k]; j++){
     143     9622513 :                         p =  blocks[k][j];
     144     9622513 :                         p->pc = pc++;
     145     9622513 :                         pushInstruction(mb, p);
     146             :                 }
     147             : 
     148    11243551 :         for(; i<limit; i++)
     149    10892189 :                 if (old[i])
     150    10892189 :                         pushInstruction(mb,old[i]);
     151    74419334 :         for(; i<slimit; i++)
     152    74067972 :                 if (old[i])
     153           0 :                         pushInstruction(mb, old[i]);
     154             : 
     155             :         /* Defense line against incorrect plans */
     156      351362 :         msg = chkTypes(cntxt->usermodule, mb, FALSE);
     157      351362 :         if (!msg)
     158      351362 :                 msg = chkFlow(mb);
     159      351362 :         if (!msg)
     160      351362 :                 msg = chkDeclarations(mb);
     161             :         /* keep all actions taken as a post block comment */
     162             :         //mnstr_printf(cntxt->fdout,"REORDER RESULT ");
     163             :         //printFunction(cntxt->fdout, mb, 0, LIST_MAL_ALL);
     164           0 : wrapup:
     165     1129373 :         for(i=0; i<= blkcnt; i++)
     166      776276 :                 if( top[i])
     167      459075 :                         GDKfree(blocks[i]);
     168             : 
     169             :         /* keep actions taken as a fake argument*/
     170      353097 :         (void) pushInt(mb, pci, actions);
     171      353097 :         GDKfree(depth);
     172      353097 :         GDKfree(old);
     173      353097 :         return msg;
     174             : }
     175             : 

Generated by: LCOV version 1.14