comEngine_feasability.c File Reference

#include <stdio.h>
#include <ctype.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "resources.h"
#include "misc.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "text-util.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
#include "polyedre.h"
#include "phrase_tools.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "effects-convex.h"
#include "phrase_distribution.h"
#include "comEngine.h"
#include "phrase.h"

Include dependency graph for comEngine_feasability.c:

Go to the source code of this file.

Macros
#define	LESSER_DIRECTION   4
#define	GREATER_DIRECTION   1
#define	ZERO_DIRECTION   2
#define	ANY_DIRECTION   7
#define	NO_DIRECTION   0

Functions
static bool	check_distribution_feasability (statement stat)
static bool	check_for_conflict (reference ref)
static list	local_syntax_to_reference_list (syntax s, list lr)
list	comEngine_expression_to_reference_list (expression e, list lr)
	conversion of an expression into a list of references; references are appended to list lr as they are encountered; array references are added before their index expressions are scanned; More...
static void	has_loop_inside_rwt (statement stat, bool *bHasLoopInside)
static bool	has_loop_inside (statement stat)
static void	fill_gRefToEncLoop (statement stat)
static void	fill_gRefToEncLoop_loop (statement stat)
static void	fill_gRefToEncLoop_call (statement stat)
static void	fill_gRefToEncLoop_test (statement stat)
static bool	entity_in_ref_list (entity searchedEnt, list lRef)
static int	find_or_create_fifo_from_ref (reference ref, bool bReadAct, hash_table refToFifo, int inc)
static void	compute_fifo_from_ref (reference ref, bool bReadAct, int inc)
static void	attach_ref_to_stat (reference callRef, statement stat, hash_table pTable, bool firstRef, int inc)
static bool	check_loop_distribution_feasability (statement stat)
bool	code_has_write_eff_ref_p (reference ref, statement stat)
list	reference_indices_entity_list (reference ref)
static bool	is_good_direction_p (Ptsg sg, int loopLev, bool bReadIsSource)
static statement	find_common_loop (list n1, list n2, list *lWLoops)
static bool	attach_ref_to_loop (reference callRef, statement inStat, bool firstRef, list lIndRef)
static bool	process_ref_list (list lCallRef, bool firstRef, statement inStat)
static bool	check_call_distribution_feasability (statement inStat)
static bool	check_test_distribution_feasability (statement inStat)
bool	comEngine_feasability (statement externalized_code, graph dg)

Variables
static int	gIfCount = 0
static hash_table	gRefToEncLoop
static list	lLoop
static list	glIndUsed
static graph	gDg
static statement	g_externalized_code
static int	vertex_to_direction [3] = {LESSER_DIRECTION, ZERO_DIRECTION, GREATER_DIRECTION}
static int	ray_to_direction [3] = {LESSER_DIRECTION, NO_DIRECTION, GREATER_DIRECTION}
static int	line_to_direction [3] = {ANY_DIRECTION, NO_DIRECTION, ANY_DIRECTION}
static char *	direction_to_representation [8] = {"?", "<", "=", "<=", ">", "*", ">=", "*"}

Macro Definition Documentation

ANY_DIRECTION

#define ANY_DIRECTION   7

Definition at line 626 of file comEngine_feasability.c.

GREATER_DIRECTION

#define GREATER_DIRECTION   1

Definition at line 624 of file comEngine_feasability.c.

LESSER_DIRECTION

#define LESSER_DIRECTION   4

Definition at line 623 of file comEngine_feasability.c.

NO_DIRECTION

#define NO_DIRECTION   0

Definition at line 627 of file comEngine_feasability.c.

ZERO_DIRECTION

#define ZERO_DIRECTION   2

Definition at line 625 of file comEngine_feasability.c.

Function Documentation

attach_ref_to_loop()

static bool attach_ref_to_loop ( reference  callRef, statement  inStat, bool  firstRef, list  lIndRef  )

static

Definition at line 884 of file comEngine_feasability.c.

{
  //printf("callRef\n");
  //print_reference(callRef);printf("\n");
 
  MAPL(lLoopStat,
  {
    statement loopStat = STATEMENT(CAR(lLoopStat));
 
    bool attachToThisLoop = false;
    entity loopIndex = loop_index(statement_loop(loopStat));
 
    // If the indices of the reference callRef contains the index
    // of the loop loopStat, then let us try to attach the reference
    // to this loop.
    MAP(REFERENCE, indRef,
    {
      if(same_entity_p(loopIndex, reference_variable(indRef)))
        {
          attachToThisLoop = true;
          break;
        }
 
    }, lIndRef);
 
    // If callRef is involved in a data dependency that prevents
    // the pipeline, then let us attach the reference to the
    // stat where it is used and not to a loop
    if(check_for_conflict(callRef))
      {
        attach_ref_to_stat(callRef, inStat, gStatToRef,
                           firstRef, 1);
 
        if(gIfCount != 0)
          {
            pips_internal_error("conflict with reference: %s",
                                reference_to_string(callRef));
 
            return false;
          }
        break;
      }
 
    // If the reference must be attached to this loop, let us do this.
    if(attachToThisLoop)
      {
        attach_ref_to_stat(callRef, loopStat, gLoopToRef,
                           firstRef, 1);
 
        break;
      }
 
    if(loopStat == STATEMENT(CAR(gen_last(lLoop))))
      {
        attach_ref_to_stat(callRef, STATEMENT(CAR(gen_last(lLoop))), gStatToRef,
                           firstRef, 1);
        break;
      }
 
  }, lLoop);
 
  return true;
}

References attach_ref_to_stat(), CAR, check_for_conflict(), gen_last(), gIfCount, gLoopToRef, gStatToRef, lLoop, loop_index, MAP, MAPL, pips_internal_error, REFERENCE, reference_to_string(), reference_variable, same_entity_p(), STATEMENT, and statement_loop().

Referenced by process_ref_list().

Here is the call graph for this function:

Here is the caller graph for this function:

attach_ref_to_stat()

static void attach_ref_to_stat ( reference  callRef, statement  stat, hash_table  pTable, bool  firstRef, int  inc  )

static

Definition at line 381 of file comEngine_feasability.c.

{
  list lRef = hash_get(pTable, stat);
 
  // If no association is in the hash_table pTable, then
  // initialize the list that will contains the associations
  if(lRef == HASH_UNDEFINED_VALUE)
    {
      lRef = NIL;
    }
 
  // Go through the list of association for this statement
  // to see if the reference is already associated to this statement or not
  bool alreadyAttached = false;
  MAP(REFERENCE, curRef,
  {
    if(!reference_equal_p(callRef, curRef))
      continue;
 
    string effAction1 = hash_get(gRefToEff, (reference)curRef);
 
    pips_assert("effAction1 != HASH_UNDEFINED_VALUE",
                effAction1 != HASH_UNDEFINED_VALUE);
 
    if((!strcmp(effAction1, R_EFFECT) && !firstRef) ||
       (!strcmp(effAction1, W_EFFECT) && firstRef))
      {
        alreadyAttached = true;
      }
  }, lRef);
 
  //printf("put %d\n", inc);
  //print_reference(callRef);
  //printf("\n");
 
  // If the reference is not yet associated to the statement,
  // then do it.
  if(!alreadyAttached)
    {
      lRef = gen_nconc(lRef, CONS(REFERENCE, callRef, NIL));
      hash_put(pTable, stat, lRef);
    }
 
  // Store the effect of the reference in gRefToEff
  if(firstRef)
    {
      hash_put(gRefToEff, callRef, W_EFFECT);
    }
  else
    {
      hash_put(gRefToEff, callRef, R_EFFECT);
    }
 
  // Create or find the fifo associated to the reference callRef
  compute_fifo_from_ref(callRef, !firstRef, inc);
}

References compute_fifo_from_ref(), CONS, gen_nconc(), gRefToEff, hash_get(), hash_put(), HASH_UNDEFINED_VALUE, MAP, NIL, pips_assert, R_EFFECT, REFERENCE, reference_equal_p(), and W_EFFECT.

Referenced by attach_ref_to_loop(), check_loop_distribution_feasability(), and process_ref_list().

Here is the call graph for this function:

Here is the caller graph for this function:

check_call_distribution_feasability()

static bool check_call_distribution_feasability ( statement  inStat )

static

Definition at line 1049 of file comEngine_feasability.c.

{
  list lCallRef = NIL;
 
  call curCall = instruction_call(statement_instruction(inStat));
 
  bool firstRef = true;
 
  MAP(EXPRESSION, exp,
  {
    list old = lCallRef;
    list new = NIL;
    new = comEngine_expression_to_reference_list(exp, new);
 
    lCallRef = gen_concatenate(old, new);
 
    gen_free_list(old);
    gen_free_list(new);
 
  }, call_arguments(curCall));
 
  bool success = process_ref_list(lCallRef, firstRef, inStat);
 
  gen_free_list(lCallRef);
 
  return success;
}

References call_arguments, comEngine_expression_to_reference_list(), exp, EXPRESSION, gen_concatenate(), gen_free_list(), instruction_call, MAP, NIL, process_ref_list(), and statement_instruction.

Referenced by check_distribution_feasability().

Here is the call graph for this function:

Here is the caller graph for this function:

check_distribution_feasability()

static bool check_distribution_feasability ( statement  stat )

static

Definition at line 1132 of file comEngine_feasability.c.

{
  bool success = true;
  instruction instr = statement_instruction(stat);
 
  switch(instruction_tag(instr))
    {
    case is_instruction_sequence:
      {
        MAP(STATEMENT, curStat,
        {
          success &= check_distribution_feasability(curStat);
 
        }, sequence_statements(instruction_sequence(instr)));
        break;
      }
    case is_instruction_loop:
      {
        success = check_loop_distribution_feasability(stat);
        break;
      }
    case is_instruction_call:
      {
        success = check_call_distribution_feasability(stat);
        break;
      }
    case is_instruction_test:
      {
        success = check_test_distribution_feasability(stat);
        break;
      }
    default:
      {
        success = false;
        break;
      }
    }
 
  return success;
}

References check_call_distribution_feasability(), check_loop_distribution_feasability(), check_test_distribution_feasability(), instruction_sequence, instruction_tag, is_instruction_call, is_instruction_loop, is_instruction_sequence, is_instruction_test, MAP, sequence_statements, STATEMENT, and statement_instruction.

Referenced by check_loop_distribution_feasability(), check_test_distribution_feasability(), and comEngine_feasability().

Here is the call graph for this function:

Here is the caller graph for this function:

check_for_conflict()

static bool check_for_conflict ( reference  ref )

static

rintf("conf\n"); printf("read\n"); print_reference(readRef);printf("\n"); printf("write\n"); print_reference(writeRef);printf("\n");

Definition at line 734 of file comEngine_feasability.c.

{
  //printf("check_for_conflict:\n");
  //print_reference(ref);printf("\n");
  MAP(VERTEX, a_vertex, 
  {
    MAP(SUCCESSOR, suc,
    {
      MAP(CONFLICT, c, 
      {
        effect sourceEff = conflict_source(c);
        effect sinkEff = conflict_sink(c);
 
        // If this is a read-read or a write-write dependence,
        // then there is no problem
        if((effect_read_p(sourceEff) &&
            effect_read_p(sinkEff)) ||
           (effect_write_p(sourceEff) &&
            effect_write_p(sinkEff)))
          continue;
 
        reference readRef = effect_any_reference(conflict_source(c));
        reference writeRef = effect_any_reference(conflict_sink(c));
 
        if(effect_read_p(sourceEff))
          {
            readRef = effect_any_reference(sourceEff);
            writeRef = effect_any_reference(sinkEff);
          }
        else
          {
            writeRef = effect_any_reference(sourceEff);
            readRef = effect_any_reference(sinkEff);
          }
 
        // If this conflict does not involve ref,
        // let us not consider this conflict
        if((readRef != ref) &&
           (writeRef != ref))
          continue;
 
        // If there is a conflict but that the references are
        // equal then the conflict does not prevent the pipeline
        if(reference_equal_p(readRef, writeRef))
          continue;
 
        list lReadLoop = hash_get(gRefToEncLoop, readRef);
        list lWriteLoop = hash_get(gRefToEncLoop, writeRef);
 
        pips_assert("lReadLoop != HASH_UNDEFINED_VALUE",
                    lReadLoop != HASH_UNDEFINED_VALUE);
 
        pips_assert("lWriteLoop != HASH_UNDEFINED_VALUE",
                    lWriteLoop != HASH_UNDEFINED_VALUE);
 
        /*printf("conf\n");
        printf("read\n");
        print_reference(readRef);printf("\n");
        printf("write\n");
        print_reference(writeRef);printf("\n");
        */
        //print_reference(effect_any_reference(sourceEff));printf("\n");
        //print_reference(effect_any_reference(sinkEff));printf("\n");
 
        // If the conflict cone is not undefined, let us study it.
        if(conflict_cone(c) != cone_undefined)
          {
            int maxLevel = -1;
 
            MAPL(pl,
            {
                if(maxLevel == -1)
                  {
                    maxLevel = INT(CAR(pl));
                  }
                else if(INT(CAR(pl)) > maxLevel)
                  {
                    maxLevel = INT(CAR(pl));
                  }
 
            }, cone_levels(conflict_cone(c)));
 
            pips_assert("maxLevel != -1", maxLevel != -1);
 
            Ptsg gs = (Ptsg)cone_generating_system(conflict_cone(c));
            if (!SG_UNDEFINED_P(gs))
              {
                // If the conflict does not prevent the pipeline then continue
                if(is_good_direction_p(gs, maxLevel,
                                       (readRef == effect_any_reference(sourceEff))))
                  {
                    sg_fprint_as_ddv(stdout, gs);
                    continue;
                  }
              }
          }
 
        statement lastRLoop = statement_undefined;
        statement lastWLoop = statement_undefined;
 
        if(lReadLoop != NIL)
          {
            lastRLoop = STATEMENT(CAR(gen_last(lReadLoop)));
          }
 
        if(lWriteLoop != NIL)
          {
            lastWLoop = STATEMENT(CAR(gen_last(lWriteLoop)));
          }
 
        // If there is a conflict but that the references invloved are in to 
        // different nested loops, then let us consider that there is no conflicts
        // but let us put a bubble in the pipeline.
        if(lastRLoop != lastWLoop)
          {
            list lWLoops = NIL;
 
            statement comLoop = find_common_loop(lReadLoop, lWriteLoop, &lWLoops);
 
            if((comLoop != lastRLoop) &&
               (comLoop != lastWLoop))
              {
                pips_assert("lWLoops != NIL", lWLoops != NIL);
 
                // Let us put a bubble in the pipeline
                hash_put(gLoopToSync, STATEMENT(CAR(lWLoops)), (void *)true);
 
                gen_free_list(lWLoops);
                continue;
              }
 
            gen_free_list(lWLoops);
          }
 
        // If we got here, it means there is a true conflict.
        return true;
 
      }, dg_arc_label_conflicts(successor_arc_label(suc)));
 
    }, vertex_successors(a_vertex));
 
  },graph_vertices(gDg));
 
  return false;
}

References CAR, cone_generating_system, cone_levels, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, dg_arc_label_conflicts, effect_any_reference, effect_read_p, effect_write_p, find_common_loop(), gDg, gen_free_list(), gen_last(), gLoopToSync, graph_vertices, gRefToEncLoop, hash_get(), hash_put(), HASH_UNDEFINED_VALUE, INT, is_good_direction_p(), MAP, MAPL, NIL, pips_assert, pl, ref, reference_equal_p(), sg_fprint_as_ddv(), SG_UNDEFINED_P, STATEMENT, statement_undefined, SUCCESSOR, successor_arc_label, VERTEX, and vertex_successors.

Referenced by attach_ref_to_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

check_loop_distribution_feasability()

static bool check_loop_distribution_feasability ( statement  stat )

static

Definition at line 443 of file comEngine_feasability.c.

{
  bool success = true;
 
  loop curLoop = statement_loop(stat);
 
  entity index = loop_index(curLoop);
  range lpRange = loop_range(curLoop);
  statement body = loop_body(curLoop);
 
  expression rgLower = range_lower(lpRange);
  expression rgUpper = range_upper(lpRange);
  expression rgIncr = range_increment(lpRange);
 
  list lLowerRef = NIL;
  list lUpperRef = NIL;
  list lIncrRef = NIL;
 
  lLowerRef = expression_to_reference_list(rgLower, lLowerRef);
  lUpperRef = expression_to_reference_list(rgUpper, lUpperRef);
  lIncrRef = expression_to_reference_list(rgIncr, lIncrRef);
 
  list bodyEff = load_cumulated_rw_effects_list(body);
 
  // The same index cannot be used in several loops
  if(gen_in_list_p(index, glIndUsed))
    {
      pips_internal_error("loop index used in several loops: %s",
                 entity_user_name(index));
      return false;
    }
  glIndUsed = CONS(ENTITY, index, glIndUsed);
 
  // A reference that is used in range_lower, range_upper or 
  // range_increment of a loop cannot be written in the body of the loop
  MAP(EFFECT, eff,
  {
    if(action_write_p(effect_action(eff)))
      {
        if(same_entity_p(index, effect_entity(eff)))
          {
            success = false;
            break;
          }
 
        if(entity_in_ref_list(effect_entity(eff), lLowerRef) ||
           entity_in_ref_list(effect_entity(eff), lUpperRef) ||
           entity_in_ref_list(effect_entity(eff), lIncrRef))
          {
            success = false;
            break;
          }
      }
  }, bodyEff);
 
  if(!same_expression_p(rgIncr, int_to_expression(1)) ||
     !same_expression_p(rgLower, int_to_expression(0)))
    {
      success = false;
 
      gen_free_list(lLowerRef);
      gen_free_list(lUpperRef);
      gen_free_list(lIncrRef);
 
      return success;
    }
 
  MAP(REFERENCE, curRef,
  {
    // If a reference, used in the range_lower of a loop,
    // is an array or has a written effect in the code to export,
    // then the exportation is not feasible
    if((gen_length(reference_indices(curRef)) != 0) ||
       code_has_write_eff_ref_p(curRef, g_externalized_code))
      {
        success = false;
        break;
      }
 
    attach_ref_to_stat(curRef, g_externalized_code, gStatToRef,
                       false, 1);
 
  }, lLowerRef);
 
  MAP(REFERENCE, curRef,
  {
    // If a reference, used in the range_upper of a loop,
    // is an array or has a written effect in the code to export,
    // then the exportation is not feasible
    if((gen_length(reference_indices(curRef)) != 0) ||
       code_has_write_eff_ref_p(curRef, g_externalized_code))
      {
        success = false;
        break;
      }
 
    attach_ref_to_stat(curRef, g_externalized_code, gStatToRef,
                       false, 1);
 
  }, lUpperRef);
 
  gen_free_list(lLowerRef);
  gen_free_list(lUpperRef);
  gen_free_list(lIncrRef);
 
  // Add the current loop to the loop list
  lLoop = CONS(STATEMENT, stat, lLoop);
 
  success = check_distribution_feasability(body);
 
  // Remove the current loop from the loop list
  gen_remove(&lLoop, stat);
 
  return success;
}

References action_write_p, attach_ref_to_stat(), check_distribution_feasability(), code_has_write_eff_ref_p(), CONS, EFFECT, effect_action, effect_entity(), ENTITY, entity_in_ref_list(), entity_user_name(), expression_to_reference_list(), g_externalized_code, gen_free_list(), gen_in_list_p(), gen_length(), gen_remove(), glIndUsed, gStatToRef, int_to_expression(), lLoop, load_cumulated_rw_effects_list(), loop_body, loop_index, loop_range, MAP, NIL, pips_internal_error, range_increment, range_lower, range_upper, REFERENCE, reference_indices, same_entity_p(), same_expression_p(), STATEMENT, and statement_loop().

Referenced by check_distribution_feasability().

Here is the call graph for this function:

Here is the caller graph for this function:

check_test_distribution_feasability()

static bool check_test_distribution_feasability ( statement  inStat )

static

Definition at line 1080 of file comEngine_feasability.c.

{
  test curTest = statement_test(inStat);
 
  // If the test statement has at least one loop inside, then
  // the compilation is impossbile.
  if(has_loop_inside(inStat))
    {
      return false;
    }
 
  list lCondRef = NIL;
  lCondRef = comEngine_expression_to_reference_list(test_condition(curTest), lCondRef);
 
  bool firstRef = false;
 
  // Process the condition
  if(!process_ref_list(lCondRef, firstRef, inStat))
    {
      return false;
    }
 
  gen_free_list(lCondRef);
 
  gIfCount++;
 
  // Process the true statement 
  if(test_true(curTest) != statement_undefined)
    {
      if(!check_distribution_feasability(test_true(curTest)))
        {
          return false;
        }
    }
 
  // Process the false statement 
  if(test_false(curTest) != statement_undefined)
    {
      if(!check_distribution_feasability(test_false(curTest)))
        {
          return false;
        }
    }
 
  gIfCount--;
 
  return true;
}

References check_distribution_feasability(), comEngine_expression_to_reference_list(), gen_free_list(), gIfCount, has_loop_inside(), NIL, process_ref_list(), statement_test(), statement_undefined, test_condition, test_false, and test_true.

Referenced by check_distribution_feasability().

Here is the call graph for this function:

Here is the caller graph for this function:

code_has_write_eff_ref_p()

bool code_has_write_eff_ref_p	(	reference	ref,
		statement	stat
	)

Parameters

ref	ef
stat	tat

Definition at line 563 of file comEngine_feasability.c.

{
   bool actionWrite = false;
 
   MAP(EFFECT, f, 
   {
      bool effEntIsIndex = false;
      entity effEnt = effect_entity(f);
 
      MAP(STATEMENT,loopStat,
      {
        entity index = loop_index(statement_loop(loopStat));
 
        if(same_entity_p(index, effEnt))
          {
            effEntIsIndex = true;
          }
 
      }, lLoop);
 
      if(effEntIsIndex)
        {
          continue;
        }
 
      if(action_write_p(effect_action(f)) && 
         same_entity_p(reference_variable(ref), effEnt))
        {
          actionWrite = true;
        }
 
   }, load_cumulated_rw_effects_list(stat));
 
   return actionWrite;
}

References action_write_p, EFFECT, effect_action, effect_entity(), f(), lLoop, load_cumulated_rw_effects_list(), loop_index, MAP, ref, reference_variable, same_entity_p(), STATEMENT, and statement_loop().

Referenced by check_loop_distribution_feasability(), phrase_check_reference(), and process_ref_list().

Here is the call graph for this function:

Here is the caller graph for this function:

comEngine_expression_to_reference_list()

list comEngine_expression_to_reference_list	(	expression	e,
		list	lr
	)

conversion of an expression into a list of references; references are appended to list lr as they are encountered; array references are added before their index expressions are scanned;

comEngine_feasability.c

references to functions and constants (which are encoded as null-ary functions) are not recorded

Parameters

lr

r

Definition at line 100 of file comEngine_feasability.c.

{
    syntax s = expression_syntax(e);
    lr = local_syntax_to_reference_list(s, lr);
    return lr;
}

References expression_syntax, and local_syntax_to_reference_list().

Referenced by check_call_distribution_feasability(), check_test_distribution_feasability(), fill_gRefToEncLoop_call(), fill_gRefToEncLoop_test(), generate_code_call(), HRE_distribute_call(), HRE_distribute_test(), local_syntax_to_reference_list(), and reference_indices_entity_list().

Here is the call graph for this function:

Here is the caller graph for this function:

comEngine_feasability()

bool comEngine_feasability	(	statement	externalized_code,
		graph	dg
	)

Parameters

externalized_code	xternalized_code
dg	g

Definition at line 1177 of file comEngine_feasability.c.

{
  bool success = false;
 
  // Initialize some global variables
  gDg = dg;
  g_externalized_code = externalized_code;
  gIfCount = 0;
  gRefToEncLoop = hash_table_make(hash_pointer, 0);
  lLoop = NIL;
  glIndUsed = NIL;
 
  hash_dont_warn_on_redefinition();
 
  // Fill the hash_table gRefToEncLoop
  fill_gRefToEncLoop(externalized_code);
 
  pips_assert("lLoop == NIL", lLoop == NIL);
 
  // Perform the actual analysis
  success = check_distribution_feasability(externalized_code);
 
  hash_warn_on_redefinition();
 
  // Free some global variables
  HASH_MAP(curRef, curLoopList,
  {
    gen_free_list(curLoopList);
  }, gRefToEncLoop);
  hash_table_free(gRefToEncLoop);
  gen_free_list(glIndUsed);
 
  return success;
}

References check_distribution_feasability(), dg, fill_gRefToEncLoop(), g_externalized_code, gDg, gen_free_list(), gIfCount, glIndUsed, gRefToEncLoop, hash_dont_warn_on_redefinition(), HASH_MAP, hash_pointer, hash_table_free(), hash_table_make(), hash_warn_on_redefinition(), lLoop, NIL, and pips_assert.

Referenced by comEngine_distribute_code().

Here is the call graph for this function:

Here is the caller graph for this function:

compute_fifo_from_ref()

static void compute_fifo_from_ref ( reference  ref, bool  bReadAct, int  inc  )

static

Definition at line 367 of file comEngine_feasability.c.

{
  intptr_t fifoNum = 0;
 
  fifoNum = find_or_create_fifo_from_ref(ref, bReadAct, gRefToFifo, inc);
 
  hash_put(gRefToHREFifo, ref, (void *)fifoNum);
}

References find_or_create_fifo_from_ref(), gRefToFifo, gRefToHREFifo, hash_put(), intptr_t, and ref.

Referenced by attach_ref_to_stat().

Here is the call graph for this function:

Here is the caller graph for this function:

entity_in_ref_list()

static bool entity_in_ref_list ( entity  searchedEnt, list  lRef  )

static

Definition at line 296 of file comEngine_feasability.c.

{
  MAP(REFERENCE, ref,
  {
    entity ent = reference_variable(ref);
 
    if(same_entity_p(ent, searchedEnt))
      {
        return true;
      }
  }, lRef);
 
  return false;
}

References MAP, ref, REFERENCE, reference_variable, and same_entity_p().

Referenced by check_loop_distribution_feasability().

Here is the call graph for this function:

Here is the caller graph for this function:

fill_gRefToEncLoop()

static void fill_gRefToEncLoop ( statement  stat )

static

Definition at line 255 of file comEngine_feasability.c.

{
  instruction instr = statement_instruction(stat);
 
  switch(instruction_tag(instr))
    {
    case is_instruction_sequence:
      {
        MAP(STATEMENT, curStat,
        {
          fill_gRefToEncLoop(curStat);
 
        }, sequence_statements(instruction_sequence(instr)));
        break;
      }
    case is_instruction_loop:
      {
        fill_gRefToEncLoop_loop(stat);
        break;
      }
    case is_instruction_call:
      {
        fill_gRefToEncLoop_call(stat);
        break;
      }
    case is_instruction_test:
      {
        fill_gRefToEncLoop_test(stat);
        break;
      }
    default:
      {
        break;
      }
    }
}

References fill_gRefToEncLoop_call(), fill_gRefToEncLoop_loop(), fill_gRefToEncLoop_test(), instruction_sequence, instruction_tag, is_instruction_call, is_instruction_loop, is_instruction_sequence, is_instruction_test, MAP, sequence_statements, STATEMENT, and statement_instruction.

Referenced by comEngine_feasability(), fill_gRefToEncLoop_loop(), and fill_gRefToEncLoop_test().

Here is the call graph for this function:

Here is the caller graph for this function:

fill_gRefToEncLoop_call()

static void fill_gRefToEncLoop_call ( statement  stat )

static

Definition at line 192 of file comEngine_feasability.c.

{
  list lCallRef = NIL;
 
  call curCall = instruction_call(statement_instruction(stat));
 
  MAP(EXPRESSION, exp,
  {
    list old = lCallRef;
    list new = NIL;
    new = comEngine_expression_to_reference_list(exp, new);
 
    lCallRef = gen_concatenate(old, new);
 
    gen_free_list(old);
    gen_free_list(new);
 
  }, call_arguments(curCall));
 
  MAP(REFERENCE, callRef,
  {
    hash_put(gRefToEncLoop, callRef, gen_copy_seq(lLoop));
  }, lCallRef);
 
  gen_free_list(lCallRef);
}

References call_arguments, comEngine_expression_to_reference_list(), exp, EXPRESSION, gen_concatenate(), gen_copy_seq(), gen_free_list(), gRefToEncLoop, hash_put(), instruction_call, lLoop, MAP, NIL, REFERENCE, and statement_instruction.

Referenced by fill_gRefToEncLoop().

Here is the call graph for this function:

Here is the caller graph for this function:

fill_gRefToEncLoop_loop()

static void fill_gRefToEncLoop_loop ( statement  stat )

static

Definition at line 176 of file comEngine_feasability.c.

{
  loop curLoop = statement_loop(stat);
 
  statement body = loop_body(curLoop);
 
  lLoop = gen_nconc(lLoop, CONS(STATEMENT, stat, NIL));
 
  fill_gRefToEncLoop(body);
 
  gen_remove(&lLoop, stat);
}

References CONS, fill_gRefToEncLoop(), gen_nconc(), gen_remove(), lLoop, loop_body, NIL, STATEMENT, and statement_loop().

Referenced by fill_gRefToEncLoop().

Here is the call graph for this function:

Here is the caller graph for this function:

fill_gRefToEncLoop_test()

static void fill_gRefToEncLoop_test ( statement  stat )

static

Definition at line 222 of file comEngine_feasability.c.

{
  test curTest = statement_test(stat);
 
  list lCondRef = NIL;
  lCondRef = comEngine_expression_to_reference_list(test_condition(curTest), lCondRef);
 
  MAP(REFERENCE, condRef,
  {
    if(gen_length(reference_indices(condRef)) != 0)
      {
        hash_put(gRefToEncLoop, condRef, gen_copy_seq(lLoop));
      }
  }, lCondRef);
 
  if(test_true(curTest) != statement_undefined)
    {
      fill_gRefToEncLoop(test_true(curTest));
    }
 
  if(test_false(curTest) != statement_undefined)
    {
      fill_gRefToEncLoop(test_false(curTest));
    }
 
  gen_free_list(lCondRef);
}

References comEngine_expression_to_reference_list(), fill_gRefToEncLoop(), gen_copy_seq(), gen_free_list(), gen_length(), gRefToEncLoop, hash_put(), lLoop, MAP, NIL, REFERENCE, reference_indices, statement_test(), statement_undefined, test_condition, test_false, and test_true.

Referenced by fill_gRefToEncLoop().

Here is the call graph for this function:

Here is the caller graph for this function:

find_common_loop()

static statement find_common_loop ( list  n1, list  n2, list *  lWLoops  )

static

Definition at line 703 of file comEngine_feasability.c.

{
  statement comLoop = statement_undefined;
 
  statement lastLoop = statement_undefined;
 
  while (n1 != NIL && n2 != NIL) {
    if (STATEMENT(CAR(n1)) != STATEMENT(CAR(n2)))
      {
        break;
      }
    lastLoop = STATEMENT(CAR(n1));
    n1 = CDR(n1); 
    n2 = CDR(n2);
  }
 
  while(n2 != NIL)
    {
      *lWLoops = gen_nconc(*lWLoops, CONS(STATEMENT, STATEMENT(CAR(n2)), NIL));
      n2 = CDR(n2);
    }
 
 
  comLoop = lastLoop;
 
  return comLoop;
}

References CAR, CDR, CONS, gen_nconc(), NIL, STATEMENT, and statement_undefined.

Referenced by check_for_conflict().

Here is the call graph for this function:

Here is the caller graph for this function:

find_or_create_fifo_from_ref()

static int find_or_create_fifo_from_ref ( reference  ref, bool  bReadAct, hash_table  refToFifo, int  inc  )

static

Definition at line 316 of file comEngine_feasability.c.

{
  pips_assert("true", bReadAct==bReadAct);
  intptr_t fifoNum = -1;
 
  // Goes through the hash_table refToFifo to see if
  // a fifo is already associated with the reference ref.
  HASH_MAP(curRef,
           buff,
  {
    if(reference_equal_p(curRef, ref))
      {
        fifoNum = (intptr_t)buff;
        break;
      }
  }, refToFifo);
 
  // If no fifo is associated to ref, then create one
  if(fifoNum == -1)
    {
      //printf("create %d\n", (int) fifoNum);
      //print_reference(ref);printf("\n");
      static int numFifo = 1;
 
      fifoNum = numFifo;
      numFifo += inc;
 
      hash_put(refToFifo, ref, (void *)fifoNum);
    }
  // else a fifo already exists, so just store the value
  // in refToFifo
  else
    {
      //printf("put %d\n", (int) fifoNum);
      //print_reference(ref);printf("\n");
 
      hash_put(refToFifo, ref, (void *)fifoNum);
    }
 
  //printf("real fifoNum %d\n", fifoNum);
 
  return fifoNum;
}

References HASH_MAP, hash_put(), intptr_t, pips_assert, ref, and reference_equal_p().

Referenced by compute_fifo_from_ref().

Here is the call graph for this function:

Here is the caller graph for this function:

has_loop_inside()

static bool has_loop_inside ( statement  stat )

static

Definition at line 161 of file comEngine_feasability.c.

{
  bool bHasLoopInside = false;
 
  gen_context_recurse(stat, &bHasLoopInside,
    statement_domain, gen_true2, has_loop_inside_rwt);
 
  return bHasLoopInside;
}

References gen_context_recurse, gen_true2(), has_loop_inside_rwt(), and statement_domain.

Referenced by check_test_distribution_feasability().

Here is the call graph for this function:

Here is the caller graph for this function:

has_loop_inside_rwt()

static void has_loop_inside_rwt ( statement  stat, bool *  bHasLoopInside  )

static

Definition at line 141 of file comEngine_feasability.c.

{
  instruction instr = statement_instruction(stat);
 
  switch(instruction_tag(instr))
    {
    case is_instruction_loop:
    case is_instruction_forloop:
    case is_instruction_whileloop:
      *bHasLoopInside = true;
      break;
    default:
      break;
    }
}

References instruction_tag, is_instruction_forloop, is_instruction_loop, is_instruction_whileloop, and statement_instruction.

Referenced by has_loop_inside().

Here is the caller graph for this function:

is_good_direction_p()

static bool is_good_direction_p ( Ptsg  sg, int  loopLev, bool  bReadIsSource  )

static

For each coordinate

For all vertices

For all rays

For all lines

Definition at line 641 of file comEngine_feasability.c.

{
    Pbase c = BASE_NULLE;
    int ddv = 0;
 
    int counter = 1;
    string dir = "";
 
    /* For each coordinate */
    for(c=sg->base; !BASE_NULLE_P(c); c = c->succ) {
        Psommet v;
        Pray_dte r;
        Pray_dte l;
 
        /* For all vertices */
        for(v=sg_sommets(sg); v!= NULL; v = v->succ) {
            ddv |= vertex_to_direction[1+value_sign(vect_coeff(vecteur_var(c), v->vecteur))];
        }
 
        /* For all rays */
        for(r=sg_rayons(sg); r!= NULL; r = r->succ) {
            ddv |= ray_to_direction[1+value_sign(vect_coeff(vecteur_var(c), r->vecteur))];
        }
 
        /* For all lines */
        for(l=sg_droites(sg); l!= NULL; l = l->succ) {
            ddv |= line_to_direction[1+value_sign(vect_coeff(vecteur_var(c), l->vecteur))];
        }
 
        if(counter == loopLev)
          {
            dir = direction_to_representation[ddv];
            break;
          }
 
        counter++;
    }
 
    if(((!strcmp(dir, "<")) ||
        (!strcmp(dir, "<="))) &&
       bReadIsSource)
      {
        return true;
      }
    else if(((!strcmp(dir, ">")) ||
             (!strcmp(dir, ">="))) &&
            !bReadIsSource)
      {
        return true;
      }
    else if(!strcmp(dir, "="))
      {
        return false;
      }
 
    return false;
}

References type_sg::base, BASE_NULLE, BASE_NULLE_P, direction_to_representation, line_to_direction, ray_to_direction, sg, sg_droites, sg_rayons, sg_sommets, rdte::succ, typ_som::succ, Svecteur::succ, value_sign, vect_coeff(), rdte::vecteur, typ_som::vecteur, vecteur_var, and vertex_to_direction.

Referenced by check_for_conflict().

Here is the call graph for this function:

Here is the caller graph for this function:

local_syntax_to_reference_list()

static list local_syntax_to_reference_list ( syntax  s, list  lr  )

static

Definition at line 109 of file comEngine_feasability.c.

{
    switch(syntax_tag(s)) {
    case is_syntax_reference:
        lr = gen_nconc(lr, CONS(REFERENCE, syntax_reference(s), NIL));
        break;
    case is_syntax_range:
        lr = comEngine_expression_to_reference_list(range_lower(syntax_range(s)), lr);
        lr = comEngine_expression_to_reference_list(range_upper(syntax_range(s)), lr);
        lr = comEngine_expression_to_reference_list(range_increment(syntax_range(s)),
                                          lr);
        break;
    case is_syntax_call:
        MAPL(ce, {
            expression e = EXPRESSION(CAR(ce));
            lr = comEngine_expression_to_reference_list(e, lr);
            },
             call_arguments(syntax_call(s)));
        break;
    default:
        pips_internal_error("illegal tag %d", 
                   syntax_tag(s));
 
    }
    return lr;
}

References call_arguments, CAR, comEngine_expression_to_reference_list(), CONS, EXPRESSION, gen_nconc(), is_syntax_call, is_syntax_range, is_syntax_reference, MAPL, NIL, pips_internal_error, range_increment, range_lower, range_upper, REFERENCE, syntax_call, syntax_range, syntax_reference, and syntax_tag.

Referenced by comEngine_expression_to_reference_list().

Here is the call graph for this function:

Here is the caller graph for this function:

process_ref_list()

static bool process_ref_list ( list  lCallRef, bool  firstRef, statement  inStat  )

static

rintf("call ref\n"); print_reference(callRef); printf("\n");

Definition at line 953 of file comEngine_feasability.c.

{
  list lIndRef = NIL;
 
  MAP(REFERENCE, callRef,
  {
 
    if(gen_length(reference_indices(callRef)) == 0)
      {
        // If a loop index is used in some call or test statement,
        // then the compilation is impossible
        MAP(STATEMENT,loopStat,
        {
          if(same_entity_p(loop_index(statement_loop(loopStat)),
                           reference_variable(callRef)))
            {
              pips_internal_error("loop index must not vary in the code: %s",
                         reference_to_string(callRef));
 
              return false;
            }
 
        }, lLoop);
 
        lIndRef = NIL;
 
        // Attach callRef to the suitable statement
        if(lLoop == NIL)
          {
            attach_ref_to_stat(callRef, g_externalized_code, gStatToRef,
                               firstRef, 1);
          }
        else
          {
            if(!attach_ref_to_loop(callRef, inStat, firstRef, lIndRef))
              {
                gen_free_list(lIndRef);
                return false;
              }
          }
 
        firstRef = false;
        continue;
      }
 
    /*printf("call ref\n");
    print_reference(callRef);
    printf("\n");
    */
    lIndRef = reference_indices_entity_list(callRef);
 
    MAP(REFERENCE, indRef,
    {
      // If one reference contained in callRef indices is an
      // array reference or that the reference is written in
      // the code to compile, then the compilation is impossible
      if((gen_length(reference_indices(indRef)) != 0) ||
         code_has_write_eff_ref_p(indRef, g_externalized_code))
        {
          gen_free_list(lIndRef);
 
          pips_internal_error("%s is not a valid reference",
                     reference_to_string(callRef));
 
          return false;
        }
 
    }, lIndRef);
 
    // Attach callRef to the suitable statement
    if(lLoop == NIL)
      {
        attach_ref_to_stat(callRef, g_externalized_code, gStatToRef,
                           firstRef, 1);
      }
    else
      {
        if(!attach_ref_to_loop(callRef, inStat, firstRef, lIndRef))
          {
            gen_free_list(lIndRef);
            return false;
          }
      }
 
    gen_free_list(lIndRef);
 
    firstRef = false;
 
  }, lCallRef);
 
  return true;
}

References attach_ref_to_loop(), attach_ref_to_stat(), code_has_write_eff_ref_p(), g_externalized_code, gen_free_list(), gen_length(), gStatToRef, lLoop, loop_index, MAP, NIL, pips_internal_error, REFERENCE, reference_indices, reference_indices_entity_list(), reference_to_string(), reference_variable, same_entity_p(), STATEMENT, and statement_loop().

Referenced by check_call_distribution_feasability(), and check_test_distribution_feasability().

Here is the call graph for this function:

Here is the caller graph for this function:

reference_indices_entity_list()

list reference_indices_entity_list

(

reference

ref

)

Parameters

ref

ef

Definition at line 603 of file comEngine_feasability.c.

{
  list lIndRef = NIL;
 
  MAP(EXPRESSION, index,
  {
    list old = lIndRef;
    list new = NIL;
    new = comEngine_expression_to_reference_list(index, new);
 
    lIndRef = gen_concatenate(old, new);
 
    gen_free_list(old);
    gen_free_list(new);
 
  }, reference_indices(ref));
 
  return lIndRef;
}

References comEngine_expression_to_reference_list(), EXPRESSION, gen_concatenate(), gen_free_list(), MAP, NIL, ref, and reference_indices.

Referenced by phrase_check_reference(), and process_ref_list().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

direction_to_representation

char* direction_to_representation[8] = {"?", "<", "=", "<=", ">", "*", ">=", "*"}

static

Definition at line 635 of file comEngine_feasability.c.

Referenced by is_good_direction_p().

g_externalized_code

statement g_externalized_code

static

Definition at line 89 of file comEngine_feasability.c.

Referenced by check_loop_distribution_feasability(), comEngine_feasability(), and process_ref_list().

gDg

graph gDg

static

Definition at line 85 of file comEngine_feasability.c.

Referenced by check_for_conflict(), and comEngine_feasability().

gIfCount

int gIfCount = 0

static

Definition at line 71 of file comEngine_feasability.c.

Referenced by attach_ref_to_loop(), check_test_distribution_feasability(), and comEngine_feasability().

glIndUsed

list glIndUsed

static

Definition at line 82 of file comEngine_feasability.c.

Referenced by check_loop_distribution_feasability(), and comEngine_feasability().

gRefToEncLoop

hash_table gRefToEncLoop

static

Definition at line 75 of file comEngine_feasability.c.

Referenced by check_for_conflict(), comEngine_feasability(), fill_gRefToEncLoop_call(), and fill_gRefToEncLoop_test().

line_to_direction

int line_to_direction[3] = {ANY_DIRECTION, NO_DIRECTION, ANY_DIRECTION}

static

Definition at line 633 of file comEngine_feasability.c.

Referenced by is_good_direction_p().

lLoop

list lLoop

static

Definition at line 79 of file comEngine_feasability.c.

Referenced by attach_ref_to_loop(), check_loop_distribution_feasability(), code_has_write_eff_ref_p(), comEngine_feasability(), fill_gRefToEncLoop_call(), fill_gRefToEncLoop_loop(), fill_gRefToEncLoop_test(), and process_ref_list().

ray_to_direction

int ray_to_direction[3] = {LESSER_DIRECTION, NO_DIRECTION, GREATER_DIRECTION}

static

Definition at line 631 of file comEngine_feasability.c.

Referenced by is_good_direction_p().

vertex_to_direction

int vertex_to_direction[3] = {LESSER_DIRECTION, ZERO_DIRECTION, GREATER_DIRECTION}

static

Definition at line 629 of file comEngine_feasability.c.

Referenced by is_good_direction_p().