exclusions.c

intel ipp4.1性能库的一些例子。

/*********************************************************************
 * File: exclusions.c
 * Description: routines for calculating exclusion relations
 *
 * Author: Joerg Hoffmann 1998
 *
 *********************************************************************/ 
/*********************************************************************
 * (C) Copyright 1998 Albert Ludwigs University Freiburg
 *     Institute of Computer Science
 *
 * All rights reserved. Use of this software is permitted for 
 * non-commercial research purposes, and it may be copied only 
 * for that use.  All copies must include this copyright message.
 * This software is made available AS IS, and neither the authors
 * nor the  Albert Ludwigs University Freiburg make any warranty
 * about the software or its performance. 
 *********************************************************************/
/*********************************************************************
 *
 * NOTE: the commentaries in this file, sparse as they are, are all
 *       in German, cause these are thoughts that I had while working
 *       on some really tedious parts of the code (potential effects...)
 * 
 *       If you have problems understanding the code (like I do when I have
 *       a look at it now), contact me at:
 *       
 *       [e-mail]
 *
 *       and I'll be happy to answer your questions, if I can...
 *
 **********************************************************************/






#include "ipp.h"

#include "output.h"
#include "utilities.h"
#include "memory.h"

#include "exclusions.h"







/*************************************
 * SIMPLE HELPERS, SHOULD BE MACROS. *
 *************************************/








void MAKE_OPS_EXCLUSIVE( int time, OpNode *o1, OpNode *o2 ) 

{

  (o1->info_at[time]->exclusives)[o2->uid_block] |= o2->uid_mask;
  (o2->info_at[time]->exclusives)[o1->uid_block] |= o1->uid_mask;

}

void MAKE_FTS_EXCLUSIVE( int time, FtNode *f1, FtNode *f2 )

{

  BitVector *v1, *v2;

  v1 = ( ( f2->positive ) ? f1->info_at[time]->pos_exclusives :
	 f1->info_at[time]->neg_exclusives );
  v2 = ( ( f1->positive ) ? f2->info_at[time]->pos_exclusives :
	 f2->info_at[time]->neg_exclusives );
  v1[f2->uid_block] |= f2->uid_mask;
  v2[f1->uid_block] |= f1->uid_mask;

}
							
void MAKE_OPS_UNEXCLUSIVE( int time, OpNode *o1, OpNode *o2 )

{

  (o1->info_at[time]->exclusives)[o2->uid_block] &= ~(o2->uid_mask);
  (o2->info_at[time]->exclusives)[o1->uid_block] &= ~(o1->uid_mask);

}

void MAKE_FTS_UNEXCLUSIVE( int time, FtNode *f1, FtNode *f2 )

{

  BitVector *v1, *v2;

  v1 = ( ( f2->positive ) ? f1->info_at[time]->pos_exclusives :
	 f1->info_at[time]->neg_exclusives );
  v2 = ( ( f1->positive ) ? f2->info_at[time]->pos_exclusives :
	 f2->info_at[time]->neg_exclusives );

  v1[f2->uid_block] &= ~(f2->uid_mask);
  v2[f1->uid_block] &= ~(f1->uid_mask);

}



Bool ARE_MUTEX_OPS( int time, OpNode *o1, OpNode *o2 )

{

  if ( o1->info_at[time]->exclusives[o2->uid_block] & o2->uid_mask ) {
    return TRUE;
  } else {
    return FALSE;
  }

}


Bool ARE_MUTEX_FTS( int time, FtNode *f1, FtNode *f2 )

{

  BitVector *a = ( f2->positive ) ?
    f1->info_at[time]->pos_exclusives :
    f1->info_at[time]->neg_exclusives;

  if ( a[f2->uid_block] & f2->uid_mask ) {
    return TRUE;
  } else {
    return FALSE;
  }

}


void SET_ADDERS( int time, FtNode *ft ) 

{

  EfEdge *e;

  ft->info_at[time]->adders = new_excl_bit_vector( gop_vector_length_at[time-1] );
  if ( ft->noop ) {
    (ft->info_at[time]->adders)[ft->noop->uid_block] |= ft->noop->uid_mask;
  }
  for ( e = ft->adders; e; e = e->next ) {
    if ( e->ef->info_at[time-1]->is_dummy ) continue;
    (ft->info_at[time]->adders)[e->ef->op->uid_block] |= e->ef->op->uid_mask;
  }
  ft->info_at[time]->adders_pointer = ft->adders;

}









/*****************************************************************
 * THE TWO MAIN FUNCIONS, CALLED FROM BUILD_GRAPH_EVOLUTION_STEP *        
 *****************************************************************/










void find_mutex_ops( int time )

{

  OpNode *i1, *i2;
  OpPair *i, *tmp, *prev;

  BitVector *a, *b;
  int r;

  for ( i1=gall_ops_pointer; i1 != gprev_level_ops_pointer; i1=i1->next ) {
    i1->info_at[time]->exclusives = new_excl_bit_vector( gop_vector_length_at[time] );
  }
  for ( ; i1; i1=i1->next ) {
    i1->info_at[time]->exclusives = new_excl_bit_vector( gop_vector_length_at[time] );
    if ( time > 0 ) {
      a = i1->info_at[time]->exclusives;
      b = i1->info_at[time-1]->exclusives;
      for ( r = 0; r < gop_vector_length_at[time-1]; r++ ) {
	a[r] |= b[r];
      }
    }
  }

  i = gop_mutex_pairs;
  while ( i && !competing_needs( time, i->o1, i->o2 ) ) {
    MAKE_OPS_UNEXCLUSIVE( time, i->o1, i->o2 );
    tmp = i;
    i = i->next;
    free( tmp );
#ifdef MEMORY_INFO
    gexcl_memory -= sizeof( OpPair );
#endif
    gops_exclusions_count--;
  }
  gop_mutex_pairs = i;
  prev = i;
  if ( i ) i = i->next;
  while ( i ) {
    if ( !competing_needs( time, i->o1, i->o2 ) ) {
      MAKE_OPS_UNEXCLUSIVE( time, i->o1, i->o2 );
      prev->next = i->next;
      tmp = i;
      i = i->next;
      free( tmp );
#ifdef MEMORY_INFO
      gexcl_memory -= sizeof( OpPair );
#endif
      gops_exclusions_count--;
    } else {
      prev = prev->next;
      i = i->next;
    }
  }

  for ( i1 = gall_ops_pointer; i1 != gprev_level_ops_pointer; i1 = i1->next ) {
    for ( i2 = i1->next; i2; i2 = i2->next ) {
      if ( interfere( i1, i2 ) ) {
	MAKE_OPS_EXCLUSIVE( time, i1, i2 );
	gops_exclusions_count++;
	continue;
      }
      if ( noop_exclusive( i1, i2 ) ) {
	MAKE_OPS_EXCLUSIVE( time, i1, i2 );
	gops_exclusions_count++;
	continue;
      }	
      if ( !competing_needs( time, i1, i2 ) ) {
	continue;
      }
      MAKE_OPS_EXCLUSIVE( time, i1, i2 );
      gops_exclusions_count++;
      tmp = new_op_pair( i1, i2 );
      tmp->next = gop_mutex_pairs;
      gop_mutex_pairs = tmp;
    }
  }

}






void find_mutex_facts( int time )

{

  FtNode *i1, *i2;
  EfEdge *e;
  FtPair *i, *prev, *tmp;
  BitVector *a, *b;
  int r, j;

  for ( i1=gall_fts_pointer; i1 != gprev_level_fts_pointer; i1=i1->next ) {
    if ( i1->info_at[time]->is_dummy ) {
      printf( "\nein dummy in der liste ??\n\n" );
      exit( 1 );
    }
    i1->info_at[time]->adders = new_excl_bit_vector( gop_vector_length_at[time-1] );
    if ( i1->noop ) {
      (i1->info_at[time]->adders)[i1->noop->uid_block] |= i1->noop->uid_mask;
    }
    for ( e = i1->adders; e && e->ef->first_occurence == time-1; e = e->next ) {
      if ( e->ef->info_at[time-1]->is_dummy ) continue;
      (i1->info_at[time]->adders)[e->ef->op->uid_block] |= e->ef->op->uid_mask;
    }
    i1->info_at[time]->adders_pointer = i1->adders;
  }
  for ( ; i1; i1=i1->next ) {
    if ( i1->info_at[time]->is_dummy ) {
      printf( "\nein dummy in der alten liste ??\n\n" );
      exit( 1 );
    }
    if ( i1->info_at[time-1]->is_dummy ) {
      printf( "\nein ex-dummy in der alten liste ??\n\n" );
      exit( 1 );
    }
    i1->info_at[time]->adders = new_excl_bit_vector( gop_vector_length_at[time-1] );
    if ( time > 1 ) {
      /*
       * achtung! evtl. bei time > 0 die exclusives bereits kopieren;
       * wegen contradicting facts... im augenblick egal, da diese bits
       * bereits in new_ft_level_info gesetzt werden.
       */
      a = i1->info_at[time]->pos_exclusives;
      b = i1->info_at[time-1]->pos_exclusives;
      for ( r = 0; r < gft_vector_length; r++ ) {
	a[r] |= b[r];
      }
      a = i1->info_at[time]->neg_exclusives;
      b = i1->info_at[time-1]->neg_exclusives;
      for ( r = 0; r < gft_vector_length; r++ ) {
	a[r] |= b[r];
      }
      a = i1->info_at[time]->adders;
      b = i1->info_at[time-1]->adders;
      for ( r = 0; r < gop_vector_length_at[time-2]; r++ ) {
	a[r] |= b[r];
      }
    }
    if ( i1->noop ) {
      (i1->info_at[time]->adders)[i1->noop->uid_block] |= i1->noop->uid_mask;
    }
    for ( e = i1->adders; e && e->ef->first_occurence == time-1; e = e->next ) {
      if ( e->ef->info_at[time-1]->is_dummy ) continue;
      (i1->info_at[time]->adders)[e->ef->op->uid_block] |= e->ef->op->uid_mask;
    }
    i1->info_at[time]->adders_pointer = i1->adders;
  }

  i = gft_mutex_pairs;
  while ( i && !facts_are_exclusive( time, i->f1, i->f2 ) ) {
    MAKE_FTS_UNEXCLUSIVE( time, i->f1, i->f2 );
    gexclusions_count--;
    if ( i->f1->positive && i->f2->positive ) {
      gprint_exnum--;
    }
    tmp = i;
    i = i->next;