reduced eval memory usage

6 files changed, 148 insertions, 51 deletions

diff --git a/README.md b/README.md
index bc93423..c27d967 100644
--- a/README.md
+++ b/README.md
@@ -68,20 +68,6 @@ See `LICENSE` for the GNU General Public License.
 ##### Why?
 This improves compilation speeds (especially from scratch), since you don't have to include headers a bunch of times for each translation unit. This is more of a problem in C++, where, for example, doing `#include <map>` ends up turning into 25,000 lines after preprocessing. All of toc's source code, which includes most of the C standard library, at the time of this writing (Dec 2019) is only 22,000 lines after preprocessing; imagine including all of that once for each translation unit which includes `map`. It also obviates the need for fancy build systems like CMake.
 
-#### "New" features
-
-Here are all the C99 features which `toc` depends on (I might have forgotten some...):
-
-- Declare anywhere
-- `inttypes.h`
-- Non-constant struct literal initializers (e.g. `int x[2] = {y, z};`)
-- Flexible array members
-- `snprintf`
-
-And here are all of its (mandatory) C11 features:
-
-- Anonymous structures/unions
-
 #### More
 
 See `main.c` for a bit more information.
diff --git a/allocator.c b/allocator.c
index a731928..59dc350 100644
--- a/allocator.c
+++ b/allocator.c
@@ -21,9 +21,6 @@ OTHER DEALINGS IN THE SOFTWARE.
 For more information, please refer to <http://unlicense.org/>
 */
 
-static void *err_malloc(size_t bytes);
-static void *err_calloc(size_t n, size_t sz);
-static void *err_realloc(void *prev, size_t new_size);
 #ifdef TOC_DEBUG
 //#define NO_ALLOCATOR 1 /* useful for debugging; valgrind checks writing past the end of a malloc, but that won't work with an allocator */
 #endif
diff --git a/err.c b/err.c
index 4853966..f1a7d52 100644
--- a/err.c
+++ b/err.c
@@ -267,28 +267,59 @@ static void warn_print_(
 #define warn_print warn_print_
 #endif
 
+#ifdef MALLOC_TRACKER
+typedef struct {
+	int line;
+	size_t nallocs;
+	size_t amount;
+} AllocTrackerEntry;
+static AllocTrackerEntry eval_c[10000];
+#endif
 
-static void *err_malloc(size_t size) {
+static void *err_malloc_(size_t size
+#ifdef MALLOC_TRACKER
+	, int line, const char *file
+#endif
+) {
 	if (size == 0) return NULL;
+
 	void *ret = malloc(size);
 	if (!ret) {
 		fprintf(stderr, "Error: Out of memory.\n");
 		exit(EXIT_FAILURE);
 	}
-	
+#ifdef MALLOC_TRACKER	
+	if (streq(file, "eval.c")) {
+		AllocTrackerEntry *entry = &eval_c[line];
+		entry->line = line;
+		entry->amount += size;
+		++entry->nallocs;
+	}
+#endif
 #ifdef MALLOC_FILL
 	memset(ret, MALLOC_FILL, size);
 #endif
 	return ret;
 }
 
-static void *err_calloc(size_t n, size_t size) {
+
+static void *err_calloc_(size_t n, size_t size
+#ifdef MALLOC_TRACKER
+	, int line, const char *file
+#endif
+) {
 	if (n == 0 || size == 0) return NULL;
 	void *ret = calloc(n, size);
 	if (!ret) {
 		fprintf(stderr, "Error: Out of memory.\n");
 		exit(EXIT_FAILURE);
 	}
+#ifdef MALLOC_TRACKER	
+	if (streq(file, "eval.c")) {
+		AllocTrackerEntry *entry = &eval_c[line];
+		entry->amount += n * size;
+	}
+#endif
 	return ret;
 }
 
diff --git a/eval.c b/eval.c
index 5ba5cdd..39d96b7 100644
--- a/eval.c
+++ b/eval.c
@@ -1057,8 +1057,8 @@ static void evalr_add_val_on_stack(Evaluator *ev, Value v, Type *t) {
 	arr_add(ev->to_free, ptr);
 }
 
-/* remove and free the last value in d->val_stack */
-static void decl_remove_val(Declaration *d) {
+/* remove and free the last value in d->val_stack. if free_val_ptr is false, the last value's contents will be freed, but not its pointer. */
+static void decl_remove_val(Declaration *d, bool free_val_ptr) {
 	Type *t = &d->type;
 	Value *dval = arr_last(d->val_stack);
 	if (arr_len(d->idents) > 1) {
@@ -1072,7 +1072,7 @@ static void decl_remove_val(Declaration *d) {
 	} else {
 		val_free(*dval, t);
 	}
-	free(dval);
+	if (free_val_ptr) free(dval);
 	arr_remove_last(d->val_stack);
 }
 
@@ -1295,12 +1295,18 @@ static Status eval_expr(Evaluator *ev, Expression *e, Value *v) {
 		/* set parameter values */
 		Declaration *params = fn->params, *ret_decls = fn->ret_decls;
 		Expression *arg = e->call.arg_exprs;
-		/* @OPTIM: figure out how much memory parameters use, then allocate that much space (possibly with alloca)? */
+		size_t pbytes = arr_len(params) * sizeof(Value);
+		Value *pvals = 
+		#if ALLOCA_AVAILABLE
+			toc_alloca(pbytes);
+		#else
+			err_malloc(pbytes);
+		#endif
+		Value *pval = &pvals[0];
 		arr_foreach(params, Declaration, p) {
 			/* give each parameter its value */
 			int idx = 0;
 			bool multiple_idents = arr_len(p->idents) > 1;
-			Value *pval = err_malloc(sizeof *pval);
 			if (type_is_builtin(&p->type, BUILTIN_VARARGS)) {
 				Expression *args_end = e->call.arg_exprs + nargs;
 				/* set varargs */
@@ -1323,34 +1329,45 @@ static Status eval_expr(Evaluator *ev, Expression *e, Value *v) {
 				}
 			}
 			arr_add(p->val_stack, pval);
+			++pval;
 		}
 
-		arr_foreach(ret_decls, Declaration, d) {
-			/* give each return declaration its value */
-			int idx = 0;
-			Value ret_decl_val;
-			DeclFlags has_expr = d->flags & DECL_HAS_EXPR;
-			if (has_expr) {
-				if (!eval_expr(ev, &d->expr, &ret_decl_val))
-					return false;
-			}
-			Value *dval = err_malloc(sizeof *dval);
-			bool multiple_idents = arr_len(d->idents) > 1;
-			bool is_tuple = d->type.kind == TYPE_TUPLE;
-			arr_foreach(d->idents, Identifier, i) {
-				Value *ival = multiple_idents ? &dval->tuple[idx] : dval;
-				Type *type = is_tuple ? &d->type.tuple[idx] : &d->type;
+		size_t dbytes = arr_len(ret_decls) * sizeof(Value);
+		Value *dvals = 
+		#if ALLOCA_AVAILABLE
+			toc_alloca(dbytes);
+		#else
+			err_malloc(dbytes);
+		#endif
+		{
+			Value *dval = dvals;
+			arr_foreach(ret_decls, Declaration, d) {
+				/* give each return declaration its value */
+				int idx = 0;
+				Value ret_decl_val;
+				DeclFlags has_expr = d->flags & DECL_HAS_EXPR;
 				if (has_expr) {
-					*ival = is_tuple ? ret_decl_val.tuple[idx] : ret_decl_val;
-				} else {
-					*ival = val_zero(NULL, type);
-					evalr_add_val_on_stack(ev, *ival, type);
+					if (!eval_expr(ev, &d->expr, &ret_decl_val))
+						return false;
+				}
+				bool multiple_idents = arr_len(d->idents) > 1;
+				bool is_tuple = d->type.kind == TYPE_TUPLE;
+				arr_foreach(d->idents, Identifier, i) {
+					Value *ival = multiple_idents ? &dval->tuple[idx] : dval;
+					Type *type = is_tuple ? &d->type.tuple[idx] : &d->type;
+					if (has_expr) {
+						*ival = is_tuple ? ret_decl_val.tuple[idx] : ret_decl_val;
+					} else {
+						*ival = val_zero(NULL, type);
+						evalr_add_val_on_stack(ev, *ival, type);
+					}
+					++idx;
 				}
-				++idx;
+				if (is_tuple && has_expr)
+					free(ret_decl_val.tuple); /* we extracted the individual elements of this */
+				arr_add(d->val_stack, dval);
+				++dval;
 			}
-			if (is_tuple && has_expr)
-				free(ret_decl_val.tuple); /* we extracted the individual elements of this */
-			arr_add(d->val_stack, dval);
 		}
 
 		if (!eval_block(ev, &fn->body)) {
@@ -1394,10 +1411,16 @@ static Status eval_expr(Evaluator *ev, Expression *e, Value *v) {
 
 		/* remove parameter values */
 		arr_foreach(params, Declaration, p)
-			decl_remove_val(p);
+			decl_remove_val(p, false);
+		#if !ALLOCA_AVAILABLE
+		free(pvals);
+		#endif
 		/* remove ret decl values */
 		arr_foreach(ret_decls, Declaration, d) 
-			decl_remove_val(d);
+			decl_remove_val(d, false);
+		#if !ALLOCA_AVAILABLE
+		free(dvals);
+		#endif
 	} break;
 	case EXPR_SLICE: {
 		SliceExpr *s = &e->slice;
diff --git a/main.c b/main.c
index a612db5..65d5095 100644
--- a/main.c
+++ b/main.c
@@ -12,7 +12,6 @@ error when a template is used before it's defined
 if we do #include "foo.toc", bar; and foo.toc fails, bar should be declared as TYPE_UNKNOWN (right now it's undeclared)
 fix #foreign not at global scope - right now the cgen'd definition doesn't use the proper type
 figure out how printf is gonna work
-find out why loop with file output is really slow at compile time; try to improve it
 improve type_to_str:
 	Foo ::= struct(t::Type) {}
 	type_to_str(Foo(int))
@@ -48,6 +47,11 @@ once you have a bunch of test code:
 	-->on the contrary, should in_decls be off the allocator?
 maybe macros are just inline functions
 passing untyped expressions to macros
+
+
+@OPTIM:
+figure out how much stack space each block uses (make sure you only do the calculation one time for each block),
+	and allocate it at the start of the block, potentially with alloca (reduce number of mallocs)
 */
 
 #if defined __unix__ || (defined __APPLE__ && defined __MACH__)
@@ -123,6 +127,18 @@ static const char *replace_extension(Allocator *a, const char *filename, const c
 	}
 }
 
+#ifdef MALLOC_TRACKER
+static int compare_entries(const void *av, const void *bv) {
+	const AllocTrackerEntry *a = av, *b = bv;
+	if (a->amount > b->amount)
+		return -1;
+	else if (b->amount > a->amount)
+		return +1;
+	else
+		return 0;
+}
+#endif
+
 int main(int argc, char **argv) {
 #if BACKTRACE
 	program_name = argv[0];
@@ -336,5 +352,17 @@ int main(int argc, char **argv) {
 
 	if (verbose) printf("Cleaning up...\n");
 	allocr_free_all(&main_allocr);
+#ifdef MALLOC_TRACKER
+	qsort(eval_c, sizeof eval_c / sizeof *eval_c, sizeof *eval_c, compare_entries);
+	size_t total = 0;
+	for (size_t i = 0; i < sizeof eval_c / sizeof *eval_c; ++i) {
+		total += eval_c[i].amount;
+	}
+	printf("A total of %lu bytes were allocated by eval.c.\n", total);
+	for (size_t i = 0; i < 10; ++i) {
+		printf("Line %4d has %10lu bytes over %9lu allocations\n",
+			eval_c[i].line, (unsigned long)eval_c[i].amount, (unsigned long)eval_c[i].nallocs);
+	}
+#endif
 	return 0;
 }
diff --git a/toc.c b/toc.c
index 6f4ca1d..c931a38 100644
--- a/toc.c
+++ b/toc.c
@@ -32,6 +32,17 @@
 #endif
 #endif
 
+#ifndef NO_ALLOCA
+#ifdef  __GNUC__
+#define toc_alloca(size) __builtin_alloca(size)
+#define ALLOCA_AVAILABLE 1
+#elif defined _MSC_VER
+#include <malloc.h>
+#define toc_alloca _malloca
+#define ALLOCA_AVAILABLE 1
+#endif
+#endif
+
 
 /* use toc_alignof only for non-structs. it may be incorrect for pre-C(++)11. */
 #if (__STDC_VERSION__ >= 201112 || __cplusplus >= 201103L) && !defined __TINYC__ && !defined __OpenBSD__ && !defined __FreeBSD__
@@ -120,6 +131,27 @@ static inline bool type_is_slicechar(Type *t) {
 	return t->kind == TYPE_SLICE && type_is_builtin(t->slice, BUILTIN_CHAR);
 }
 
+//#define MALLOC_TRACKER
+
+static void *err_malloc_(size_t size
+#ifdef MALLOC_TRACKER
+	, int line, const char *file
+#endif
+);
+static void *err_calloc_(size_t n, size_t sz
+#ifdef MALLOC_TRACKER
+	, int line, const char *file
+#endif
+);
+static void *err_realloc(void *prev, size_t new_size);
+#ifdef MALLOC_TRACKER
+#define err_malloc(size) err_malloc_(size, __LINE__, __FILE__)
+#define err_calloc(n, size) err_calloc_(n, size, __LINE__, __FILE__)
+#else
+#define err_malloc err_malloc_
+#define err_calloc err_calloc_
+#endif
+
 /* utilities */
 #include "allocator.c"
 #include "misc.c"