[Bug middle-end/53082] New: local malloc/free optimization

[xinliangli at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53082

             Bug #: 53082
           Summary: local malloc/free optimization
    Classification: Unclassified
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassig...@gcc.gnu.org
        ReportedBy: xinlian...@gmail.com


Malloc/free pairs sometimes are used in a way that behaves like a stack memory.
The optimizer should recognize the pattern and take advantage of it. For
instance if the memory is not escaped, dead stores to the memory can be
removed. In extreme case, the malloc/free pair can be completely removed.

For instance:

for (i = 0; i < 100; i++)
  {
    int *s = (int*) malloc (sizeof(int));
    *s = 10;
    free (s);
   }

This code can be completely removed (which LLVM does).

The above can be considered as a benchmarking optimization -- see the one
appended (objinst.c in LLVM's benchmark suite).

The following more advanced optimization (which as far as I know only HP
compiler does) can also be done: coalescing multiple malloc calls into one
alloca call, and eliminating the free calls. The memory can be escaped.

for (...)
 {
   int *s1 = malloc (...);
   int *s2 = malloc (...);
   int *s3 = malloc (...);
   ...

   free(s1); free(s2); free(s3);
}

==>

for (...)
  {
     int s = alloca (...);
     s1 = s;
     s2 = s+ ..
     s3 = s+ ..

    ...
  }



// objinst.c


/* -*- mode: c -*-
 * $Id: objinst.c 36673 2007-05-03 16:55:46Z laurov $
 * http://www.bagley.org/~doug/shootout/
 */

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


enum {false, true};

#define TOGGLE \
    char state; \
    char (*value)(struct Toggle *); \
    struct Toggle *(*activate)(struct Toggle *)

#define DESTROY  free

typedef struct Toggle {
    TOGGLE;
} Toggle;

char toggle_value(Toggle *this) {
    return(this->state);
}
Toggle *toggle_activate(Toggle *this) {
    this->state = !this->state;
    return(this);
}
Toggle *init_Toggle(Toggle *this, char start_state) {
    this->state = start_state;
    this->value = toggle_value;
    this->activate = toggle_activate;
    return(this);
}
Toggle *new_Toggle(char start_state) {
    Toggle *this = (Toggle *)malloc(sizeof(Toggle));
    return(init_Toggle(this, start_state));
}


typedef struct NthToggle {
    Toggle base;
    int count_max;
    int counter;
} NthToggle;

NthToggle *nth_toggle_activate(NthToggle *this) {
    if (++this->counter >= this->count_max) {
        this->base.state = !this->base.state;
        this->counter = 0;
    }
    return(this);

}
NthToggle *init_NthToggle(NthToggle *this, int max_count) {
    this->count_max = max_count;
    this->counter = 0;
    this->base.activate = (Toggle *(*)(Toggle *))nth_toggle_activate;
    return(this);
}
NthToggle *new_NthToggle(char start_state, int max_count) {
    NthToggle *this = (NthToggle *)malloc(sizeof(NthToggle));
    this = (NthToggle *)init_Toggle((Toggle *)this, start_state);
    return(init_NthToggle(this, max_count));
}


int main(int argc, char *argv[]) {
#ifdef SMALL_PROBLEM_SIZE
#define LENGTH 7000000
#else
#define LENGTH 70000000
#endif
    int i, n = ((argc == 2) ? atoi(argv[1]) : LENGTH);
    Toggle *tog;
    NthToggle *ntog;

    tog = new_Toggle(true);
    for (i=0; i<5; i++) {
        puts((tog->activate(tog)->value(tog)) ? "true" : "false");
    }
    DESTROY(tog);
    for (i=0; i<n; i++) {
        tog = new_Toggle(true);
        DESTROY(tog);
    }

    puts("");

    ntog = new_NthToggle(true, 3);
    for (i=0; i<8; i++) {
        const char *Msg;
        if (ntog->base.activate((Toggle*)ntog)->value((Toggle*)ntog))
          Msg = "true";
        else
          Msg = "false";
        puts(Msg);
    }
    DESTROY(ntog);
    for (i=0; i<n; i++) {
        ntog = new_NthToggle(true, 3);
        DESTROY(ntog);
    }
    return 0;
}