New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Quoted statements in terralib.select are mishandled #99

Open
paniq opened this Issue Jun 22, 2015 · 3 comments

Comments

Projects
None yet
2 participants
@paniq

paniq commented Jun 22, 2015

I ran into an issue with my work-in-progress Lisp-based code generator yesterday (where I try to generate a function completely from expressions using quote in) when I noticed that statements injected with expressions via quote in do not get handled properly if the expression is a branch of a ternary conditional (terralib.select).

The first time I encountered the problem, an assignment that was executed within an expression in a select inside a while block was always executed rather than being tied to the select branch. In the minimum reproduce however, the statement was completely ignored. Both behaviors are wrong.

I tested the bug with the current trunk and it's still there.

I understand that select just resolves to llvm's select statement internally, but I would expect that if the branching expressions come with statements, terra falls back to generating an analog if else structure.

Here's the minimum reproduce demonstrating the problem (or as minimal as I could make it):

local select = terralib.select
local function quote_select(cond, a, b)
    return quote
    in
        select([ cond] , [ a ], [ b ])
    end
end

local function quote_in(stmtlist, expr)
    return quote
        [ stmtlist ]
    in
        [ expr ]
    end
end

local function quote_assign(sym, value)
    return quote
        [sym] = [value]
    end
end

local function quote_var(sym, init)
    return quote
        var [ sym ] = [ init ]
    end
end

local function quote_return(expr)
    return quote
        return [ expr ]
    end
end

local function quote_op(opname, operands)
    return `operator(opname, operands)
end

local function new_function(rtype, args, stmtlist)
    args = args or {}
    rtype = rtype or {}
    stmtlist = stmtlist or terralib.newlist()
    return terra([args]) : rtype
        [ stmtlist ]
    end
end

local x = symbol(bool, "x")
local y = symbol(int, "y")
local k = symbol(int, "k")
local test = new_function(int, { x, y }, {
    -- var k = y
    quote_var(k, y),
    -- return (k + terralib.select(x, { k = k + y } 1, 2))
    quote_return(quote_op("+",
        {
            k,
            quote_select(x, 
                quote_in(
                    {
                        -- this statement is ignored, but shouldn't
                        quote_assign(k, quote_op("+", {k, y})),
                    },
                    1
                    ),
                2)
        }))
})

-- disassembly shows k = k + y is never included
test:disas()
--[[
define i32 @"$anon (terratest.lua:44)"(i1 zeroext, i32) {
entry:
  %2 = select i1 %0, i32 1, i32 2
  %3 = add i32 %2, %1
  ret i32 %3
}

definition  {bool,int32} -> int32
assembly for function at address 0x7fd8bbf91070
0x7fd8bbf91070(+0):     cmp DIL, 1
0x7fd8bbf91074(+4):     adc ESI, 0
0x7fd8bbf91077(+7):     lea EAX, DWORD PTR [ESI + 1]
0x7fd8bbf9107b(+11):        ret
--]]

-- succeeds
assert(test(false,7) == 9)
-- should return 7+7+1 = 15, fails
assert(test(true,7) == 15)
@zdevito

This comment has been minimized.

Owner

zdevito commented Jun 22, 2015

This is a case where many low level languages leave the behavior undefined
because the precise semantics are tricky. In the expression,

return k + terralib.select(x,[quote k = k + y in 1 end], 2)

the value of the first 'k' is read before it is updated later in the
expression.
In, C/C++ this behavior (updating a variable in the same expression it is
used) is just left undefined:
return k + (x) ? (++k,1) : 2

On Sun, Jun 21, 2015 at 10:24 PM, Leonard Ritter notifications@github.com
wrote:

I ran into an issue with my work-in-progress Lisp-based code generator
yesterday (where I try to generate a function completely from expressions
using quote in) when I noticed that statements injected with expressions
via quote in do not get handled properly if the expression is a branch of
a ternary conditional (terralib.select).

The first time I encountered the problem, an assignment that was executed
within an expression in a select that was of a while block was always
executed rather than being tied to the select branch. In the minimum
reproduce however, the statement was completely ignored. Both behaviors are
wrong.

I tested the bug with the current trunk and it's still there.

Now I understand that select internally just resolves to llvm's select
statement, but I would expect that if the branching expressions come with
statements, terra falls back to generating an analog if-else structure.

Here's the minimum reproduce demonstrating the problem (or as minimal as I
could make it):

local select = terralib.selectlocal function quote_select(cond, a, b)
return quote
in
select([ cond] , [ a ], [ b ])
endend
local function quote_in(stmtlist, expr)
return quote
[ stmtlist ]
in
[ expr ]
endend
local function quote_assign(sym, value)
return quote
[sym] = [value]
endend
local function quote_var(sym, init)
return quote
var [ sym ] = [ init ]
endend
local function quote_return(expr)
return quote
return [ expr ]
endend
local function quote_op(opname, operands)
return `operator(opname, operands)end
local function new_function(rtype, args, stmtlist)
args = args or {}
rtype = rtype or {}
stmtlist = stmtlist or terralib.newlist()
return terra([args]) : rtype
[ stmtlist ]
endend
local x = symbol(bool, "x")local y = symbol(int, "y")local k = symbol(int, "k")local test = new_function(int, { x, y }, {
-- var k = y
quote_var(k, y),
-- return (k + terralib.select(x, { k = k + y } 1, 2))
quote_return(quote_op("+",
{
k,
quote_select(x,
quote_in(
{
-- this statement is ignored, but shouldn't
quote_assign(k, quote_op("+", {k, y})),
},
1
),
2)
}))
})
-- disassembly shows k = k + y is never included
test:disas()--[[define i32 @"$anon (terratest.lua:44)"(i1 zeroext, i32) {entry: %2 = select i1 %0, i32 1, i32 2 %3 = add i32 %2, %1 ret i32 %3}definition {bool,int32} -> int32assembly for function at address 0x7fd8bbf910700x7fd8bbf91070(+0): cmp DIL, 10x7fd8bbf91074(+4): adc ESI, 00x7fd8bbf91077(+7): lea EAX, DWORD PTR [ESI + 1]0x7fd8bbf9107b(+11): ret--]]
-- succeedsassert(test(false,7) == 9)-- should return 7+7+1 = 15, failsassert(test(true,7) == 15)


Reply to this email directly or view it on GitHub
#99.

@paniq

This comment has been minimized.

paniq commented Jun 23, 2015

I would argue that precedence and associativity always provide a deterministic result; if all operators are correctly reduced to unary/binary ops in nested parentheses, the order of processing is well defined.

C++ is in this regard not entirely comparable, because the associativity for some operators is not the same ( in Lua, almost all but two operators are left-to-right.)

My need to fix this problem has faded somewhat since it is possible to work around the problem with a solution @zdevito provided on the mailing list: https://mailman.stanford.edu/pipermail/terralang/2015-June/000441.html -- I'm listing it here for anyone running into the same problem in the future.

@paniq

This comment has been minimized.

paniq commented Jun 24, 2015

I just also realized, with the lazyselect version provided on the mailing list, that my example for the bug was flawed. k is indeed altered after the top-level + operator has read it, so the statement has no effect.

Here is a better example that compares both implementations and reproduces the bug:

local select = terralib.select
local function quote_select(cond, a, b)
    return quote
    in
        select([ cond] , [ a ], [ b ])
    end
end

local function quote_in(stmtlist, expr)
    return quote
        [ stmtlist ]
    in
        [ expr ]
    end
end

local function quote_assign(sym, value)
    return quote
        [sym] = [value]
    end
end

local function quote_var(sym, init)
    return quote
        var [ sym ] = [ init ]
    end
end

local function quote_return(expr)
    return quote
        return [ expr ]
    end
end

local lazyselect = macro(function(c,x,y)
    local T = x:gettype()
    return quote
        var r : T
        if c then
            r = x
        else
            r = y
        end
    in
        r
    end
end)

local function quote_lazyselect(condition,true_expr,false_expr)
    return quote
    in
        lazyselect(condition,true_expr,false_expr)
    end
end    

local function quote_op(opname, operands)
    return `operator(opname, operands)
end

local function new_function(rtype, args, stmtlist)
    args = args or {}
    rtype = rtype or {}
    stmtlist = stmtlist or terralib.newlist()
    return terra([args]) : rtype
        [ stmtlist ]
    end
end

local x = symbol(bool, "x")
local y = symbol(int, "y")
local k = symbol(int, "k")

-- using terralib.select, produces faulty result
local test1 = new_function(int, { x, y }, {
    -- var k = y
    quote_var(k, y),
    -- return (k + terralib.select(x, [y = k + y] y, [y = k * y] y))
    quote_return(quote_op("+",
        {
            k,
            quote_select(x, 
                quote_in(
                    {
                        quote_assign(y, quote_op("+", {k, y})),
                    },
                    y
                    ),
                quote_in(
                    {
                        quote_assign(y, quote_op("*", {k, y})),
                    },
                    y
                    ))
        }))
})

-- using terralib.lazyselect macro, produces correct result
local test2 = new_function(int, { x, y }, {
    -- var k = y
    quote_var(k, y),
    -- return (k + terralib.select(x, [y = k + y] y, [y = k * y] y))
    quote_return(quote_op("+",
        {
            k,
            quote_lazyselect(x, 
                quote_in(
                    {
                        quote_assign(y, quote_op("+", {k, y})),
                    },
                    y
                    ),
                quote_in(
                    {
                        quote_assign(y, quote_op("*", {k, y})),
                    },
                    y
                    ))
        }))
})

print(test1(false,7), test2(false,7))
print(test1(true,7), test2(true,7))

-- succeeds: 21 == 21
assert(test1(true,7) == test2(true,7))
-- fails: 105 != 56
assert(test1(false,7) == test2(false,7))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment