[pure-lang-svn] SF.net SVN: pure-lang: [129] pure/trunk
Status: Beta
Brought to you by:
agraef
Menu
▾
▴
[pure-lang-svn] SF.net SVN: pure-lang: [129] pure/trunk
|
From: <ag...@us...> - 2008-05-25 05:42:39
|
Revision: 129
http://pure-lang.svn.sourceforge.net/pure-lang/?rev=129&view=rev
Author: agraef
Date: 2008-05-24 22:42:48 -0700 (Sat, 24 May 2008)
Log Message:
-----------
Make toplevel if-then-else properly tail-recursive.
Modified Paths:
--------------
pure/trunk/ChangeLog
pure/trunk/interpreter.cc
pure/trunk/interpreter.hh
pure/trunk/test/test004.log
pure/trunk/test/test004.pure
Modified: pure/trunk/ChangeLog
===================================================================
--- pure/trunk/ChangeLog 2008-05-24 19:58:42 UTC (rev 128)
+++ pure/trunk/ChangeLog 2008-05-25 05:42:48 UTC (rev 129)
@@ -1,3 +1,11 @@
+2008-05-25 Albert Graef <Dr....@t-...>
+
+ * interpreter.cc: Make toplevel if-then-else properly
+ tail-recursive. Thus, e.g., the following function will now run in
+ constant stack space: count x = if x<=0 then x else count (x-1);
+ This also works with nested if-then-else constructs, as long as
+ they form the right-hand side of an equation.
+
2008-05-24 Albert Graef <Dr....@t-...>
* interpreter.cc, runtime.cc: Fix more memory allocation bugs in
Modified: pure/trunk/interpreter.cc
===================================================================
--- pure/trunk/interpreter.cc 2008-05-24 19:58:42 UTC (rev 128)
+++ pure/trunk/interpreter.cc 2008-05-25 05:42:48 UTC (rev 129)
@@ -3197,6 +3197,15 @@
return 0;
}
+void interpreter::toplevel_codegen(expr x)
+{
+ assert(!x.is_null());
+ if (x.tag() == EXPR::COND)
+ toplevel_cond(x.xval1(), x.xval2(), x.xval3());
+ else
+ act_env().CreateRet(codegen(x));
+}
+
Value *interpreter::codegen(expr x)
{
assert(!x.is_null());
@@ -3487,6 +3496,40 @@
return phi;
}
+void interpreter::toplevel_cond(expr x, expr y, expr z)
+{
+ // emit tail-recursive code for a toplevel if-then-else
+ Env& f = act_env();
+ assert(f.f!=0);
+ // emit the code for x
+ Value *iv = 0;
+ if (x.ttag() == EXPR::INT)
+ // optimize the case that x is an ::int (constant or application)
+ iv = get_int(x);
+ else if (x.ttag() != 0) {
+ // wrong type of constant; raise an exception
+ // XXXTODO: we might want to optionally invoke the debugger here
+ unwind(symtab.failed_cond_sym().f);
+ return;
+ } else
+ // typeless expression, will be checked at runtime
+ iv = get_int(x);
+ // emit the condition (turn the previous result into a flag)
+ Value *condv = f.builder.CreateICmpNE(iv, Zero, "cond");
+ // create the basic blocks for the branches
+ BasicBlock *thenbb = new BasicBlock("then");
+ BasicBlock *elsebb = new BasicBlock("else");
+ // create the branch instruction and emit the 'then' block
+ f.builder.CreateCondBr(condv, thenbb, elsebb);
+ f.f->getBasicBlockList().push_back(thenbb);
+ f.builder.SetInsertPoint(thenbb);
+ toplevel_codegen(y);
+ // emit the 'else' block
+ f.f->getBasicBlockList().push_back(elsebb);
+ f.builder.SetInsertPoint(elsebb);
+ toplevel_codegen(z);
+}
+
// Other value boxes. These just call primitives in the runtime which take
// care of constructing these values.
@@ -4321,11 +4364,11 @@
f.f->getBasicBlockList().push_back(matchedbb);
f.builder.SetInsertPoint(matchedbb);
#if DEBUG>1
- if (!f.name.empty()) { ostringstream msg;
- msg << "exit " << f.name << ", result: " << pm->r[0].rhs;
- debug(msg.str().c_str()); }
+ if (!f.name.empty()) { ostringstream msg;
+ msg << "exit " << f.name << ", result: " << pm->r[0].rhs;
+ debug(msg.str().c_str()); }
#endif
- f.CreateRet(codegen(pm->r[0].rhs));
+ toplevel_codegen(pm->r[0].rhs);
} else {
// build the initial stack of expressions to be matched
list<Value*>xs;
@@ -4607,7 +4650,7 @@
msg << "exit " << f.name << ", result: " << rr.rhs;
debug(msg.str().c_str()); }
#endif
- f.CreateRet(codegen(rr.rhs));
+ toplevel_codegen(rr.rhs);
break;
}
// check the guard
@@ -4647,7 +4690,7 @@
msg << "exit " << f.name << ", result: " << rr.rhs;
debug(msg.str().c_str()); }
#endif
- f.CreateRet(codegen(rr.rhs));
+ toplevel_codegen(rr.rhs);
rulebb = nextbb;
}
if (f.fmap.size() > 1) f.fmap_idx = 0;
Modified: pure/trunk/interpreter.hh
===================================================================
--- pure/trunk/interpreter.hh 2008-05-24 19:58:42 UTC (rev 128)
+++ pure/trunk/interpreter.hh 2008-05-25 05:42:48 UTC (rev 129)
@@ -416,6 +416,7 @@
pure_expr *doeval(expr x, pure_expr*& e);
pure_expr *dodefn(env vars, expr lhs, expr rhs, pure_expr*& e);
llvm::Value *codegen(expr x);
+ void toplevel_codegen(expr x);
llvm::Value *builtin_codegen(expr x);
llvm::Value *get_int(expr x);
llvm::Value *get_double(expr x);
@@ -428,6 +429,7 @@
llvm::Value *call(llvm::Value *x);
llvm::Value *apply(llvm::Value *x, llvm::Value *y);
llvm::Value *cond(expr x, expr y, expr z);
+ void toplevel_cond(expr x, expr y, expr z);
llvm::Value *fbox(Env& f, bool thunked = false);
llvm::Value *cbox(int32_t tag);
llvm::Value *ibox(llvm::Value *i);
Modified: pure/trunk/test/test004.log
===================================================================
--- pure/trunk/test/test004.log 2008-05-24 19:58:42 UTC (rev 128)
+++ pure/trunk/test/test004.log 2008-05-25 05:42:48 UTC (rev 129)
@@ -75,6 +75,15 @@
}
count2 100;
0
+count3 n/*0:1*/::int = if n/*0:1*/<=0 then n/*0:1*/ else count3 (n/*0:1*/-1);
+{
+ rule #0: count3 n::int = if n<=0 then n else count3 (n-1)
+ state 0: #0
+ <var>::int state 1
+ state 1: #0
+}
+count3 100;
+0
test x/*0:1*/::int = t/*0*/ x/*0:1*/ with t n/*0:1*/::int = t/*1*/ (-n/*0:1*/) if n/*0:1*/<0; t n/*0:1*/::int = u/*0*/ (n/*0:1*/+2) with u _/*0:1*/ = n/*1:1*/+1 {
rule #0: u _ = n+1
state 0: #0
Modified: pure/trunk/test/test004.pure
===================================================================
--- pure/trunk/test/test004.pure 2008-05-24 19:58:42 UTC (rev 128)
+++ pure/trunk/test/test004.pure 2008-05-25 05:42:48 UTC (rev 129)
@@ -35,12 +35,17 @@
count2 n::int = n if n<=0;
= count2 (n-1) otherwise;
-// This should always work.
count2 100;
-// Again, this should work if proper tail calls are supported, no matter what
-// your stack size is.
//count2 10000000;
+// Definitions involving toplevel if-then-else are properly tail-recursive as
+// well.
+
+count3 n::int = if n<=0 then n else count3 (n-1);
+
+count3 100;
+//count3 10000000;
+
// Trivial tail-recursive local function which passes an environment to
// another local function. Note that the callee can never be tail-called in
// such a situation because it needs the extra environment parameter which is
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
