public inbox for gcc@gcc.gnu.org
 help / color / mirror / Atom feed
* GSoC (Make cp-demangle non-recursive)
@ 2022-03-27 12:21 Juan Scerri
  2022-04-07 15:24 ` Martin Jambor
  0 siblings, 1 reply; 6+ messages in thread
From: Juan Scerri @ 2022-03-27 12:21 UTC (permalink / raw)
  To: gcc

Hello,

Lately, I have been working on a way to implement recursion on the heap to
deal with
the limits associated with recursion on the stack. If a good implementation
is reached
that should allow us to convert the code.

I have implemented the data structure and I have written a simple factorial
function
using the data structure. Currently, no error handling is being done.

Any guidance on what is expected with regards to error handling and how
errors should be
dealt with (push up the call stack or terminate the program?) would be
greatly appreciated.

Moreover, any feedback on the current way the data structure
is implemented and the code used to implement the simple factorial function
would be appreciated.

The current issue I have with this method is that it is really complex to
write a
function using the data structure to implement recursion on the heap. Plus
it requires
dealing and understanding the control flow of the function very well.

Any ideas on how I can make this, as much as possible, a drop in
replacement would be helpful.

The code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define GET_FRAME_AS(work, frame_type) ((struct frame_type **)&work.frame)

enum d_work_type {
  CALL,
  RET,
};

struct d_work {
  /* Type of work (RET or CALL). */
  enum d_work_type type;
  /* Type of RET work. */
  unsigned int ret_type;
  /* Pointer to function frame. */
  void *frame;
};

/* Stack of operations to do after traversing a full branch. */
struct d_work_stack {
  /* Base pointer. */
  struct d_work *bp;
  /* Current length of data on the stack. */
  size_t len;
  /* Allocated size of buffer. */
  size_t alc;
  /* Set to 1 if we had a memory allocation failure. */
  int allocation_failure;
};

static inline struct d_work d_new_work(enum d_work_type type,
                                       unsigned int ret_work, void *frame) {
  return (struct d_work){type, ret_work, frame};
}

static inline void d_work_stack_resize(struct d_work_stack *dws, size_t
need) {
  size_t newalc;
  struct d_work *newbp;

  if (dws->allocation_failure)
    return;

  /* Start allocation at two bytes to avoid any possibility of confusion
     with the special value of 1 used as a return to indicate
     allocation failures.  */
  newalc = dws->alc > 0 ? dws->alc : 2;

  while (newalc < need)
    newalc <<= 1;

  newbp = (struct d_work *)realloc(dws->bp, newalc * sizeof(struct d_work));

  if (newbp == NULL) {
    free(dws->bp);
    dws->bp = NULL;
    dws->len = 0;
    dws->alc = 0;
    dws->allocation_failure = 1;

    return;
  }

  dws->bp = newbp;
  dws->alc = newalc;
}

static void d_work_stack_init(struct d_work_stack *dws, size_t estimate) {
  dws->bp = NULL;
  dws->len = 0;
  dws->alc = 0;
  dws->allocation_failure = 0;

  if (estimate > 0)
    d_work_stack_resize(dws, estimate);
}

static void d_work_stack_push(struct d_work_stack *dws, struct d_work dw) {
  size_t need = dws->len + 1;

  if (need > dws->alc)
    d_work_stack_resize(dws, need);

  if (dws->allocation_failure)
    return;

  dws->bp[(dws->len)++] = dw;
}

static int d_work_stack_peek(struct d_work_stack *dws, struct d_work *pdw) {
  if (dws->len == 0)
    return -1;

  *pdw = dws->bp[dws->len - 1];

  return dws->len; /* Return the number of elements. */
}

static int d_work_stack_pop(struct d_work_stack *dws, struct d_work *pdw) {
  if (dws->len == 0)
    return -1;

  *pdw = dws->bp[--(dws->len)];

  return dws->len; /* Return how many elements are left. */
}

static void d_work_stack_deinit(struct d_work_stack *dws) {
  if (dws->bp != NULL) {
    free(dws->bp);
    dws->bp = NULL;
  }

  dws->len = 0;
  dws->alc = 0;
  dws->allocation_failure = 0;
}

/*
 * This section of the code will contain examples of recursive
 * code implemented pseudo-recursively using the heap.
 */

/* Recursive implementation of factorial. */
long r_factorial(long n) {
  long ret; // Return of the function.
  long res; // Result of a recursive call.

  if (n == 0 || n == 1) {
    ret = 1;
  } else {
    res = r_factorial(n - 1);
    ret = n * res;
  }

  return ret;
}

struct p_factorial_frame {
  long n;
  long ret;
  long res;
};

enum p_factorial_ret_types { MULT_RET };

/* Pseudo-recursive implementation of factorial. */
long p_factorial(long n) {
  /* Return variable. */
  long ret;

  /* Setup the work stack. */
  struct d_work_stack work_stack;
  d_work_stack_init(&work_stack, 16);

  /* Initial frame. */
  struct p_factorial_frame *initial_frame =
      malloc(sizeof(struct p_factorial_frame));
  initial_frame->n = n;
  d_work_stack_push(&work_stack, d_new_work(CALL, 0, initial_frame));

  /*
   * These will be used to access work without a lot of
   * difficulty.
   */
  struct d_work current_work;
  struct d_work peek_work;

  /* Pointer to frame pointer for ease of writing. */
  struct p_factorial_frame **current_frame;
  struct p_factorial_frame **peek_frame;

  /*
   * When we get the final element we do not modify current_work
   * hence all we need to do is take the the ret value from the
   * block and free the state variable in current_work.
   */
  while (d_work_stack_pop(&work_stack, &current_work) != -1) {
    current_frame = GET_FRAME_AS(current_work, p_factorial_frame);

    if (current_work.type == CALL) {
      if ((*current_frame)->n == 0 || (*current_frame)->n == 1) {
        (*current_frame)->ret = 1;

        // Modify previous stack frame if it is present.
        if (d_work_stack_peek(&work_stack, &peek_work) != -1) {
          peek_frame = GET_FRAME_AS(peek_work, p_factorial_frame);
          (*peek_frame)->res = (*current_frame)->ret;
        }
      } else {
        /*
         * Make a new return frame, copy the current frame and
         * push onto the stack.
         */
        struct p_factorial_frame *ret_frame =
            malloc(sizeof(struct p_factorial_frame));
        memcpy(ret_frame, *current_frame, sizeof(struct p_factorial_frame));
        d_work_stack_push(&work_stack, d_new_work(RET, MULT_RET,
ret_frame));

        /*
         * Make a new call frame, copy the change function
         * parameter and push onto the stack.
         */
        struct p_factorial_frame *call_frame =
            malloc(sizeof(struct p_factorial_frame));
        call_frame->n = (*current_frame)->n - 1;
        d_work_stack_push(&work_stack, d_new_work(CALL, 0, call_frame));
      }
    } else {
      switch (current_work.ret_type) {
      case MULT_RET:
        (*current_frame)->ret = (*current_frame)->n * (*current_frame)->res;
        break;
      }

      // Modify the previous stack frame if it is present.
      if (d_work_stack_peek(&work_stack, &peek_work) != -1) {
        peek_frame = GET_FRAME_AS(peek_work, p_factorial_frame);
        (*peek_frame)->res = (*current_frame)->ret;
      }
    }

    /*
     * Do not free the last frame because that will be freed. At
     * the end.
     */
    if (work_stack.len > 0) {
      free(*(current_frame));
    }
  }

  ret = (*GET_FRAME_AS(current_work, p_factorial_frame))->ret;

  /*
   * Freeing of the last stack frame and freeing of the whole
   * stack
   */
  free(*GET_FRAME_AS(current_work, p_factorial_frame));
  d_work_stack_deinit(&work_stack);

  return ret;
}

int main(void) {
  long n = p_factorial(0);
  printf("%ld\n", n);

  long n2 = p_factorial(1);
  printf("%ld\n", n2);

  long n3 = p_factorial(5);
  printf("%ld\n", n3);

  return 0;
}

^ permalink raw reply	[flat|nested] 6+ messages in thread
* GSoC (Make cp-demangle non-recursive)
@ 2022-02-26 10:34 Juan Scerri
  2022-02-26 16:31 ` Juan Scerri
  2022-03-02 18:37 ` Martin Jambor
  0 siblings, 2 replies; 6+ messages in thread
From: Juan Scerri @ 2022-02-26 10:34 UTC (permalink / raw)
  To: gcc

To whom this may concern,

Firstly, I will introduce myself. I am Juan Scerri and I am a student at
the University of Malta studying Computer Science and Mathematics for my
undergraduate degree.
I am currently in my first year of studies, which is technically my first
formal introduction to GNU/Linux. However, I have been using GNU/Linux for
over a year. I am
mostly interested in programming which involves compilers, operating
systems and things of a similar sort.

I have looked at the selected project ideas by the GCC team and one of the
problems which has caught my attention is making cp-demangle non-recursive.
I am interested in this particular problem because as stated in the "Before
you apply" section it is one of the selected problems which do not require
extensive
knowledge of the compiler theory (which I will be doing in my 3rd year of
studies). However, I do understand the aim of the project.

Any guidance would be much appreciated.

If I was no clear in any way do hesitate to contact me.

Regards,
Juan Scerri

^ permalink raw reply	[flat|nested] 6+ messages in thread
end of thread, other threads:[~2022-04-07 15:24 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-03-27 12:21 GSoC (Make cp-demangle non-recursive) Juan Scerri
2022-04-07 15:24 ` Martin Jambor
  -- strict thread matches above, loose matches on Subject: below --
2022-02-26 10:34 Juan Scerri
2022-02-26 16:31 ` Juan Scerri
2022-03-02 18:37 ` Martin Jambor
     [not found]   ` <CACJSivvYgNG+C2Y5ph=4yv5y0iaV+Ak7=vh3FGD7W6eQADxk9w@mail.gmail.com>
2022-03-09 16:15     ` Martin Jambor

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).