GSoC (Make cp-demangle non-recursive)
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
#include
#include
#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
Re: Validation of adding left shift stmt at GIMPLE - [Custom GCC plugin]]
On Wed, Feb 23, 2022 at 12:52 PM Richard Biener
wrote:
>
> On Tue, Feb 22, 2022 at 2:10 PM Shubham Narlawar
> wrote:
> >
> > On Tue, Feb 22, 2022 at 3:55 PM Richard Biener
> > wrote:
> > >
> > > On Tue, Feb 22, 2022 at 8:38 AM Shubham Narlawar
> > > wrote:
> > > >
> > > > On Mon, Feb 21, 2022 at 1:02 PM Richard Biener
> > > > wrote:
> > > > >
> > > > > On Sun, Feb 20, 2022 at 11:44 PM Andrew Pinski via Gcc
> > > > > wrote:
> > > > > >
> > > > > > On Sun, Feb 20, 2022 at 10:45 AM Shubham Narlawar
> > > > > > wrote:
> > > > > > >
> > > > > > > On Sat, Feb 19, 2022 at 1:15 AM Andrew Pinski
> > > > > > > wrote:
> > > > > > > >
> > > > > > > > On Fri, Feb 18, 2022 at 11:04 AM Shubham Narlawar via Gcc
> > > > > > > > wrote:
> > > > > > > > >
> > > > > > > > > Hello,
> > > > > > > > >
> > > > > > > > > I want to know whether it is correct to add left shift
> > > > > > > > > instruction to
> > > > > > > > > a constant expression statement like "_3 + 4"?
> > > > > > > > >
> > > > > > > > > I am trying to add a left shift instruction in between below
> > > > > > > > > GIMPLE
> > > > > > > > > instructions -
> > > > > > > > >
> > > > > > > > >:
> > > > > > > > > instrn_buffer.0_1 = instrn_buffer;
> > > > > > > > > _2 = tree.cnt;
> > > > > > > > > _3 = (int) _2;
> > > > > > > > > _4 = _3 + 4;
> > > > > > > > > _5 = (unsigned int) _4;// I want to add left shift
> > > > > > > > > here
> > > > > > > > > D.2993 = __builtin_riscv_sfploadi (instrn_buffer.0_1, 0,
> > > > > > > > > _5);
> > > > > > > > > //this is "stmt"
> > > > > > > > >
> > > > > > > > > I am using this snippet in custom gcc plugin -
> > > > > > > > >
> > > > > > > > > tree lshift_tmp = make_temp_ssa_name
> > > > > > > > > (integer_type_node,
> > > > > > > > > NULL, "slli");
> > > > > > > >
> > > > > > > > A couple of things.
> > > > > > > > I Noticed you use integer_type_node here. Why not the type of
> > > > > > > > what is
> > > > > > > > being replaced?
> > > > > > > > That is the main thing I see right now.
> > > > > > >
> > > > > > > I want to apply left shift to a constant expression with 8 which
> > > > > > > is an
> > > > > > > integer. Since I am not replacing a statement, I am creating new
> > > > > > > GIMPLE statement -
> > > > > > >
> > > > > > > tree shift_amt = build_int_cst (integer_type_node, 8);
> > > > > > >
> > > > > > > Here, I am not replacing any GIMPLE statement. Is this the
> > > > > > > correct way
> > > > > > > to do this?
> > > > > > >
> > > > > > > My goal is to left shift constant expression and update its usage
> > > > > > > as below -
> > > > > > >
> > > > > > > _19 = (unsigned int) _18;
> > > > > > > D.2996 = __builtin_riscv_sfploadi (lexer.5_16, 12, _19);
> > > > > > >
> > > > > > > into
> > > > > > >
> > > > > > > _19 = (unsigned int) _18;
> > > > > > > temp = _19 << 8
> > > > > > > D.2996 = __builtin_riscv_sfploadi (lexer.5_16, 12, temp);
> > > > > > >
> > > > > > > I am storing the left shift result to the new ssa variable name
> > > > > > > "temp"
> > > > > > > and updating sfploadi parameters as expected.
> > > > > > >
> > > > > > > On doing the above, dom_walker_eliminate is prohibiting me to do
> > > > > > > the
> > > > > > > above gimple transformation. Is the above transformation complete
> > > > > > > and
> > > > > > > correct?
> > > > > >
> > > > > > I think you misunderstood me. I was saying for a left shift gimple,
> > > > > > the result type and the first operand type must be compatible
> > > > > > (signed
> > > > > > and unsigned types are not compatible). In the above case, you have:
> > > > > > integer_type_node = unsigned_int << integer_type_name .
> > > > > >
> > > > > > Does that make sense now?
> > > > >
> > > > > Btw, the error you see is still odd - please make sure to build GCC
> > > > > with
> > > > > checking enabled or run your tests with -fchecking. For further help
> > > >
> > > > Sure.
> > > >
> > > > > it might be useful to post the patch you are testing to show where
> > > > > exactly
> > > > > you are hooking into to add this statement.
> > > >
> > > > My goal is to transform below IR -
> > > >
> > > > _5 = (unsigned int) _4;
> > > > D.2993 = __builtin_riscv_* (instrn_buffer.0_1, 0, _5);
> > > >
> > > > to target IR -
> > > >
> > > > _5 = (unsigned int) _4;
> > > > lshiftamt_27 = _5 << 8;
> > > > D.2996 = __builtin_riscv_* (instrn_buffer.0_1, 0, lshiftamt_27);
> > > >
> > > > I have followed this approach to build a new GIMPLE left shift
> > > > instruction -
> > > > https://github.com/gcc-mirror/gcc/blob/0435b978f95971e139882549f5a1765c50682216/gcc/ubsan.cc#L1257
> > > >
> > > > Here is the patch which I am using -
> > > >
> > > > --Patch---
> > > > unsigned int
> > > > pass_custom_lowering::execute (function *fun)
> > > > {
> > > > /* Code for iterating over all statements of function to find
> > > > function call
gcc-12-20220327 is now available
Snapshot gcc-12-20220327 is now available on https://gcc.gnu.org/pub/gcc/snapshots/12-20220327/ and on various mirrors, see http://gcc.gnu.org/mirrors.html for details. This snapshot has been generated from the GCC 12 git branch with the following options: git://gcc.gnu.org/git/gcc.git branch master revision 08e69332881f8d28ce8b559ffba1900ae5c0d5ee You'll find: gcc-12-20220327.tar.xz Complete GCC SHA256=1d9f8b8f7f3521300aaff34ab8a3cff0fe8c45c4ae659b08af5b077d5e4ceb3e SHA1=f11be72db26a9393691201dd12e8423859a2c94b Diffs from 12-20220320 are available in the diffs/ subdirectory. When a particular snapshot is ready for public consumption the LATEST-12 link is updated and a message is sent to the gcc list. Please do not use a snapshot before it has been announced that way.
