Changeset: 0bc7a88e5fa7 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/0bc7a88e5fa7
Modified Files:
monetdb5/optimizer/opt_reorder.c
Branch: default
Log Message:
Perform bucket sort to finalize the reorder.
diffs (215 lines):
diff --git a/monetdb5/optimizer/opt_reorder.c b/monetdb5/optimizer/opt_reorder.c
--- a/monetdb5/optimizer/opt_reorder.c
+++ b/monetdb5/optimizer/opt_reorder.c
@@ -29,6 +29,7 @@
#include "opt_reorder.h"
#include "mal_instruction.h"
#include "mal_interpreter.h"
+#include "opt_mitosis.h"
/* Insert the instruction immediately after a previous instruction that
@@ -36,49 +37,21 @@
* If non can be found, add it to the end.
* Be aware of side-effect instructions, they may not be skipped.
*/
-static void
-insertInstruction(MalBlkPtr mb, MalStkPtr stk, InstrPtr p, int start)
-{
- int i,j,k;
- InstrPtr q;
- (void) stk;
-
- if( hasSideEffects(mb, p, FALSE)){
- pushInstruction(mb,p);
- return;
- }
- for(i = mb->stop -1; i>0 && i>start; i--)
- {
- q= getInstrPtr(mb, i);
- if( hasSideEffects(mb, q, FALSE))
- break;
- for (j=0; j< q->retc; j++){
- for(k= p->retc; k <p->argc; k++){
- if( getArg(q,j) == getArg(p,k)){
- /* found a location to
insert the new instruction */
- for(i++; i>0 && i<
mb->stop; i++){
- q=
getInstrPtr(mb,i);
- mb->stmt[i]= p;
- p = q;
- }
- pushInstruction(mb,p);
- return;
- }
- }
- }
- }
- pushInstruction(mb,p);
-}
-
str
OPTreorderImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
{
- int i,j,k, maxphase = 1, phase=0, startblk=0;
+ int i,j,k, blkcnt = 1;
InstrPtr *old = NULL;
- int limit, slimit, *used = NULL;
+ int limit, slimit, *depth = NULL;
char buf[256];
lng usec= GDKusec();
str msg = MAL_SUCCEED;
+ InstrPtr *blocks[MAXSLICES] ={0};
+ int top[MAXSLICES] ={0};
+
+ (void) blocks;
+ (void) top;
+ for(i=0; i< MAXSLICES; i++) top[i] = 0;
if( isOptimizerUsed(mb, "mitosis") <= 0){
goto wrapup;
}
@@ -89,73 +62,73 @@ OPTreorderImplementation(Client cntxt, M
slimit= mb->ssize;
old = mb->stmt;
- used = (int*) GDKzalloc(mb->vtop * sizeof(int));
- if( used == NULL){
+ depth = (int*) GDKzalloc(mb->vtop * sizeof(int));
+ if( depth == NULL){
throw(MAL,"optimizer.reorder", SQLSTATE(HY013) MAL_MALLOC_FAIL);
}
if ( newMalBlkStmt(mb, mb->ssize) < 0) {
- GDKfree(used);
+ GDKfree(depth);
throw(MAL,"optimizer.reorder", SQLSTATE(HY013) MAL_MALLOC_FAIL);
}
- /* Mark the parameters as constants as beloning to phase 1; */
+ /* Mark the parameters as constants as beloning to depth 0; */
for( i =0; i< limit; i++){
p = old[i];
- for( j= p->retc; j< p->argc; j++)
- if(i == 0 || isVarConstant(mb, getArg(p,j)))
- used[ getArg(p,j)] = maxphase;
+ if( !p) {
+ //mnstr_printf(cntxt->fdout, "empty stmt:pc %d \n", i);
+ continue;
+ }
+ if( p->token == ENDsymbol)
+ break;
+ if( getModuleId(p) == sqlRef && getFunctionId(p) == tidRef &&
p->argc == 6){
+ if (depth[getArg(p,0)] == 0){
+ k = getVarConstant(mb, getArg(p,
p->argc-2)).val.ival;
+ assert( k < MAXSLICES);
+ depth[getArg(p,0)] = k;
+ }
+ } else
+ if( getModuleId(p) == sqlRef && getFunctionId(p) == bindRef &&
p->argc == 8){
+ if (depth[getArg(p,0)] == 0){
+ k = getVarConstant(mb, getArg(p,
p->argc-2)).val.ival;
+ assert( k < MAXSLICES);
+ depth[getArg(p,0)] = k;
+ }
+ } else{
+ k = 0;
+ for(j= p->retc; j <p->argc; j++){
+ if (depth[getArg(p,j)] > k)
+ k = depth[getArg(p,j)];
+ }
+ for(j=0; j< p->retc; j++)
+ if( depth[getArg(p,j)] == 0)
+ depth[getArg(p,j)] = k;
+ }
+
+ if( top[k] == 0){
+ blocks[k] = GDKzalloc(limit * sizeof(InstrPtr));
+ if( blocks[k] == NULL){
+ for(i=0; i< blkcnt; i++)
+ if( top[i])
+ GDKfree(blocks[i]);
+ GDKfree(depth);
+ GDKfree(old);
+ throw(MAL,"optimizer.reorder", SQLSTATE(HY013)
MAL_MALLOC_FAIL);
+ }
+ }
+ blocks[k][top[k]] = p;
+ top[k]= top[k] +1;
+ //mnstr_printf(cntxt->fdout, "block[%d] :%d:",i, k);
+ //printInstruction(cntxt->fdout, mb, stk, p, LIST_MAL_DEBUG);
+ if( k > blkcnt)
+ blkcnt = k;
}
- pushInstruction(mb, old[0]);
- old[0] = 0;
- for( phase = 0; phase < maxphase; phase ++){
- startblk = mb->stop;
- for (i=1; i<limit; i++){
- p= old[i];
- if ( p == 0)
- continue;
- if( p->token == ENDsymbol)
- break;
- if( getModuleId(p) == sqlRef && getFunctionId(p) == tidRef &&
p->argc == 6){
- if (used[getArg(p,0)] == 0){
- k = getVarConstant(mb, getArg(p,
p->argc-2)).val.ival + 2;
- maxphase = getVarConstant(mb,
getArg(p, p->argc-1)).val.ival + 2;
- used[getArg(p,0)] = k;
- //mnstr_printf(cntxt->fdout, "tid : %d
%d\n", used[getArg(p,0)], maxphase);
- continue;
- }
- }
- if( getModuleId(p) == sqlRef && getFunctionId(p) == bindRef &&
p->argc == 8){
- if (used[getArg(p,0)] == 0){
- k = getVarConstant(mb, getArg(p,
p->argc-2)).val.ival + 2;
- maxphase = getVarConstant(mb,
getArg(p, p->argc-1)).val.ival + 2;
- used[getArg(p,0)] = k;
- //mnstr_printf(cntxt->fdout, "bind : %d
%d\n", used[getArg(p,0)], maxphase);
- continue;
- }
- }
- /* locate instruction that does not have a blocking variable */
- k = 0;
- for(j= 0; j<p->argc; j++){
- if( used[getArg(p,j)] > k)
- k = used[getArg(p,j)];
- }
- /* If this instruction belongs to phase */
- if ( k == phase){
- //mnstr_printf(cntxt->fdout, "inject %d pc %d max found: %d:",
phase, p->pc, k);
- //printInstruction(cntxt->fdout, mb, stk, p, LIST_MAL_DEBUG);
- //pushInstruction(mb,p);
- insertInstruction(mb, stk, p, startblk);
- old[i] = 0;
- }
- for( j = 0; j< p->retc; j++)
- if( used[getArg(p,j)] == 0){
- //mnstr_printf(cntxt->fdout, "var[%d] : %d %d\n", i,
used[getArg(p,j)], k);
- used[getArg(p,j)] = k;
- }
- }
- }
- for(i=0; i<limit; i++)
+
+ for(k =0; k <= blkcnt; k++)
+ for(j=0; j < top[k]; j++)
+ pushInstruction(mb, blocks[k][j]);
+
+ for(; i<limit; i++)
if (old[i])
pushInstruction(mb,old[i]);
for(; i<slimit; i++)
@@ -169,8 +142,13 @@ OPTreorderImplementation(Client cntxt, M
if (!msg)
msg = chkDeclarations(mb);
/* keep all actions taken as a post block comment */
+ //mnstr_printf(cntxt->fdout,"REORDER RESULT ");
+ //printFunction(cntxt->fdout, mb, 0, LIST_MAL_ALL);
wrapup:
- GDKfree(used);
+ for(i=0; i< blkcnt; i++)
+ if( top[i])
+ GDKfree(blocks[i]);
+ GDKfree(depth);
GDKfree(old);
usec = GDKusec()- usec;
snprintf(buf,256,"%-20s actions=%2d time=" LLFMT " usec","reorder",1,usec);
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list
