LlvmGenerator.py 30.5 KB
Newer Older
Maxime Perrotin's avatar
Maxime Perrotin committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
    OpenGEODE - A tiny SDL Editor for TASTE

    This module generates LLVM IR code from SDL process models, allowing
    generation of a binary application without an intermediate language.
    LLVM also allows for various code verification, analysis, and optimization.

    The design is based on the Ada code generator. Check it for details.

    Copyright (c) 2012-2013 European Space Agency

    Designed and implemented by Maxime Perrotin

    Contact: maxime.perrotin@esa.int
"""

import logging
21

Maxime Perrotin's avatar
Maxime Perrotin committed
22
from singledispatch import singledispatch
23
from llvm import core
Maxime Perrotin's avatar
Maxime Perrotin committed
24
25

import ogAST
Maxime Perrotin's avatar
Maxime Perrotin committed
26
import Helper
Maxime Perrotin's avatar
Maxime Perrotin committed
27
28
29

LOG = logging.getLogger(__name__)

Maxime Perrotin's avatar
Maxime Perrotin committed
30
31
__all__ = ['generate']

Maxime Perrotin's avatar
Maxime Perrotin committed
32

33
34
35
36
37
38
# Global state
g = None


class GlobalState():
    def __init__(self, process):
dbarbera's avatar
dbarbera committed
39
40
        self.name = str(process.processName)
        self.module = core.Module.new(self.name)
41
42
        self.dataview = process.dataview

43
44
        self.scope = Scope()
        self.global_scope = self.scope
45
        self.states = {}
dbarbera's avatar
dbarbera committed
46
        self.structs = {}
47
        self.strings = {}
dbarbera's avatar
dbarbera committed
48
        self.funcs = {}
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

        # Initialize built-in types
        self.i1 = core.Type.int(1)
        self.i8 = core.Type.int(8)
        self.i32 = core.Type.int(32)
        self.i64 = core.Type.int(64)
        self.void = core.Type.void()
        self.double = core.Type.double()
        self.i1_ptr = core.Type.pointer(self.i1)
        self.i8_ptr = core.Type.pointer(self.i8)
        self.i32_ptr = core.Type.pointer(self.i32)
        self.i64_ptr = core.Type.pointer(self.i64)
        self.double_ptr = core.Type.pointer(self.double)

        # Intialize built-in functions
        ty = core.Type.function(self.void, [core.Type.pointer(self.i8)], True)
dbarbera's avatar
dbarbera committed
65
        self.funcs['printf'] = self.module.add_function(ty, 'printf')
66

dbarbera's avatar
dbarbera committed
67
        self.funcs['memcpy'] = core.Function.intrinsic(
68
69
70
            self.module, core.INTR_MEMCPY,
            [self.i8_ptr, self.i8_ptr, self.i64]
        )
Maxime Perrotin's avatar
Maxime Perrotin committed
71

dbarbera's avatar
dbarbera committed
72

73
74
class StructType():
    def __init__(self, name, field_names, field_types):
dbarbera's avatar
dbarbera committed
75
        self.name = name
76
77
78
79
80
        self.field_names = field_names
        self.ty = core.Type.struct(field_types, self.name)

    def idx(self, field_name):
        return self.field_names.index(field_name)
dbarbera's avatar
dbarbera committed
81
82


83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class Scope:
    def __init__(self, parent=None):
        self.vars = {}
        self.parent = parent

    def define(self, name, var):
        self.vars[name.lower()] = var

    def resolve(self, name):
        var = self.vars.get(name.lower())
        if var:
            return var
        if self.parent:
            return self.parent.resolve(name)
        else:
            raise NameError

dbarbera's avatar
dbarbera committed
100

Maxime Perrotin's avatar
Maxime Perrotin committed
101
102
103
104
@singledispatch
def generate(ast):
    ''' Generate the code for an item of the AST '''
    raise TypeError('[Backend] Unsupported AST construct')
Maxime Perrotin's avatar
Maxime Perrotin committed
105

dbarbera's avatar
dbarbera committed
106

Maxime Perrotin's avatar
Maxime Perrotin committed
107
108
109
# Processing of the AST
@generate.register(ogAST.Process)
def _process(process):
dbarbera's avatar
dbarbera committed
110
    ''' Generate LLVM IR code '''
111
    LOG.info('Generating LLVM IR code for process ' + str(process.processName))
112

113
114
    global g
    g = GlobalState(process)
115

dbarbera's avatar
dbarbera committed
116
117
118
119
120
121
    # In case model has nested states, flatten everything
    Helper.flatten(process)

    # Make an maping {input: {state: transition...}} in order to easily
    # generate the lookup tables for the state machine runtime
    mapping = Helper.map_input_state(process)
Maxime Perrotin's avatar
Maxime Perrotin committed
122

123
124
125
    # Initialize states enum
    for name in process.mapping.iterkeys():
        if not name.endswith('START'):
126
127
            cons = core.Constant.int(g.i32, len(g.states))
            g.states[name] = cons
128

129
    # Generate state var
130
131
    state_cons = g.module.add_global_variable(g.i32, 'state')
    state_cons.initializer = core.Constant.int(g.i32, -1)
132
    g.scope.define('state', state_cons)
133

134
135
136
    # Generare process-level vars
    for name, (ty, expr) in process.variables.viewitems():
        var_ty = _generate_type(ty)
137
        global_var = g.module.add_global_variable(var_ty, str(name))
138
        global_var.initializer = core.Constant.null(var_ty)
139
        g.scope.define(str(name).lower(), global_var)
140

dbarbera's avatar
dbarbera committed
141
142
    # Initialize output signals
    for signal in process.output_signals:
143
144
145
146
        if 'type' in signal:
            param_tys = [core.Type.pointer(_generate_type(signal['type']))]
        else:
            param_tys = []
147
        func_ty = core.Type.function(g.void, param_tys)
dbarbera's avatar
dbarbera committed
148
149
150
        func_name = str(signal['name'])
        func = core.Function.new(g.module, func_ty, func_name)
        g.funcs[func_name.lower()] = func
dbarbera's avatar
dbarbera committed
151
152
153
154

    # Initialize external procedures
    for proc in [proc for proc in process.procedures if proc.external]:
        param_tys = [core.Type.pointer(_generate_type(p['type'])) for p in proc.fpar]
155
        func_ty = core.Type.function(g.void, param_tys)
dbarbera's avatar
dbarbera committed
156
157
158
        func_name = str(proc.inputString)
        func = core.Function.new(g.module, func_ty, func_name)
        g.funcs[func_name.lower()] = func
dbarbera's avatar
dbarbera committed
159

160
161
    # Generate internal procedures
    for proc in process.content.inner_procedures:
162
        generate(proc)
163

164
    # Generate process functions
165
    _generate_runtr_func(process)
166
    _generate_startup_func(process)
167

168
169
170
171
    # Generate input signals
    for signal in process.input_signals:
        _generate_input_signal(signal, mapping[signal['name']])

dbarbera's avatar
dbarbera committed
172
173
    g.module.verify()

dbarbera's avatar
dbarbera committed
174
    with open(g.name  + '.ll', 'w') as ll_file:
dbarbera's avatar
dbarbera committed
175
        ll_file.write(str(g.module))
176
177
178


def _generate_runtr_func(process):
dbarbera's avatar
dbarbera committed
179
    ''' Generate code for the run_transition function '''
180
    func_name = 'run_transition'
181
182
    func_type = core.Type.function(g.void, [g.i32])
    func = core.Function.new(g.module, func_type, func_name)
183
    g.funcs[func_name] = func
184

185
186
    _push_scope()

187
188
189
190
191
    entry_block = func.append_basic_block('entry')
    cond_block = func.append_basic_block('cond')
    body_block = func.append_basic_block('body')
    exit_block = func.append_basic_block('exit')

dbarbera's avatar
dbarbera committed
192
    g.builder = core.Builder.new(entry_block)
193
194

    # entry
dbarbera's avatar
dbarbera committed
195
    id_ptr = g.builder.alloca(g.i32, None, 'id')
196
    g.scope.define('id', id_ptr)
dbarbera's avatar
dbarbera committed
197
198
    g.builder.store(func.args[0], id_ptr)
    g.builder.branch(cond_block)
199
200

    # cond
dbarbera's avatar
dbarbera committed
201
    g.builder.position_at_end(cond_block)
202
    no_tr_cons = core.Constant.int(g.i32, -1)
203
204
    id_val = g.builder.load(id_ptr)
    cond_val = g.builder.icmp(core.ICMP_NE, id_val, no_tr_cons, 'cond')
dbarbera's avatar
dbarbera committed
205
    g.builder.cbranch(cond_val, body_block, exit_block)
206
207

    # body
dbarbera's avatar
dbarbera committed
208
209
    g.builder.position_at_end(body_block)
    switch = g.builder.switch(func.args[0], exit_block)
210
211
212
213

    # transitions
    for idx, tr in enumerate(process.transitions):
        tr_block = func.append_basic_block('tr%d' % idx)
214
        const = core.Constant.int(g.i32, idx)
215
        switch.add_case(const, tr_block)
dbarbera's avatar
dbarbera committed
216
        g.builder.position_at_end(tr_block)
217
        generate(tr)
dbarbera's avatar
dbarbera committed
218
        g.builder.branch(cond_block)
219
220

    # exit
dbarbera's avatar
dbarbera committed
221
222
    g.builder.position_at_end(exit_block)
    g.builder.ret_void()
223

224
225
    _pop_scope()

226
227
228
229
    func.verify()
    return func


230
def _generate_startup_func(process):
dbarbera's avatar
dbarbera committed
231
    ''' Generate code for the startup function '''
dbarbera's avatar
dbarbera committed
232
    func_name = g.name + '_startup'
233
234
    func_type = core.Type.function(g.void, [])
    func = core.Function.new(g.module, func_type, func_name)
235
    g.funcs[func_name] = func
236

237
238
    _push_scope()

239
    entry_block = func.append_basic_block('entry')
240
    g.builder = core.Builder.new(entry_block)
241

242
243
244
    # Initialize process level variables
    for name, (ty, expr) in process.variables.viewitems():
        if expr:
245
            global_var = _resolve(str(name))
246
247
            _generate_assign(global_var, expression(expr))

248
249
    g.builder.call(g.funcs['run_transition'], [core.Constant.int(g.i32, 0)])
    g.builder.ret_void()
Maxime Perrotin's avatar
Maxime Perrotin committed
250

251
252
    _pop_scope()

253
254
    func.verify()
    return func
Maxime Perrotin's avatar
Maxime Perrotin committed
255
256


257
def _generate_input_signal(signal, inputs):
dbarbera's avatar
dbarbera committed
258
    ''' Generate code for an input signal '''
dbarbera's avatar
dbarbera committed
259
    func_name = g.name + "_" + str(signal['name'])
260
261
262
    param_tys = []
    if 'type' in signal:
        param_tys.append(core.Type.pointer(_generate_type(signal['type'])))
263
264
    func_type = core.Type.function(g.void, param_tys)
    func = core.Function.new(g.module, func_type, func_name)
dbarbera's avatar
dbarbera committed
265
    g.funcs[func_name.lower()] = func
266

267
268
    _push_scope()

269
270
    entry_block = func.append_basic_block('entry')
    exit_block = func.append_basic_block('exit')
271
    g.builder = core.Builder.new(entry_block)
272

273
    g_state_val = g.builder.load(g.global_scope.resolve('state'))
274
    switch = g.builder.switch(g_state_val, exit_block)
275

276
    for state_name, state_id in g.states.iteritems():
277
278
        state_block = func.append_basic_block('state_%s' % str(state_name))
        switch.add_case(state_id, state_block)
279
        g.builder.position_at_end(state_block)
280
281
282

        # TODO: Nested states

283
284
285
        input = inputs.get(state_name)
        if input:
            for var_name in input.parameters:
286
                var_val = g.scope.resolve(str(var_name))
287
288
                _generate_assign(var_val, func.args[0])
            if input.transition:
289
                id_val = core.Constant.int(g.i32, input.transition_id)
290
                g.builder.call(g.funcs['run_transition'], [id_val])
291

292
        g.builder.ret_void()
293

294
295
    g.builder.position_at_end(exit_block)
    g.builder.ret_void()
296

297
298
    _pop_scope()

299
300
301
    func.verify()


Maxime Perrotin's avatar
Maxime Perrotin committed
302
303
304
305
@generate.register(ogAST.Output)
@generate.register(ogAST.ProcedureCall)
def _call_external_function(output):
    ''' Generate the code of a set of output or procedure call statement '''
306
    zero = core.Constant.int(g.i32, 0)
dbarbera's avatar
dbarbera committed
307
308
309
    for out in output.output:
        name = out['outputName'].lower()

310
        if name == 'write':
dbarbera's avatar
dbarbera committed
311
312
            _generate_write(out['params'])
            continue
313
314
315
        elif name == 'writeln':
            _generate_writeln(out['params'])
            continue
dbarbera's avatar
dbarbera committed
316
317
318
319
320
321
322
        elif name == 'reset_timer':
            _generate_reset_timer(out['params'])
            continue
        elif name == 'set_timer':
            _generate_set_timer(out['params'])
            continue

dbarbera's avatar
dbarbera committed
323
        func = g.funcs[str(name).lower()]
324
325
326
327
328
329
330
331
332
333
334
335
336

        params = []
        for p in out.get('params', []):
            p_val = expression(p)
            # Pass by reference
            if p_val.type.kind != core.TYPE_POINTER:
                p_var = g.builder.alloca(p_val.type, None)
                g.builder.store(p_val, p_var)
                params.append(p_var)
            else:
                params.append(p_val)

        g.builder.call(func, params)
dbarbera's avatar
dbarbera committed
337
338
339
340


def _generate_write(params):
    ''' Generate the code for the write operator '''
341
    zero = core.Constant.int(g.i32, 0)
342
343
344
    for param in params:
        basic_ty = find_basic_type(param.exprType)
        expr_val = expression(param)
345
346
347
348

        if basic_ty.kind != 'StringType' and expr_val.type.kind == core.TYPE_POINTER:
            expr_val = g.builder.load(expr_val)

349
        if basic_ty.kind == 'IntegerType':
350
            fmt_val = _get_string_cons('% d')
351
            fmt_ptr = g.builder.gep(fmt_val, [zero, zero])
dbarbera's avatar
dbarbera committed
352
            g.builder.call(g.funcs['printf'], [fmt_ptr, expr_val])
353
        elif basic_ty.kind == 'RealType':
354
            fmt_val = _get_string_cons('% .14E')
355
            fmt_ptr = g.builder.gep(fmt_val, [zero, zero])
dbarbera's avatar
dbarbera committed
356
            g.builder.call(g.funcs['printf'], [fmt_ptr, expr_val])
357
        elif basic_ty.kind == 'BooleanType':
358
            true_str_val = _get_string_cons('TRUE')
359
            true_str_ptr = g.builder.gep(true_str_val, [zero, zero])
360
            false_str_val = _get_string_cons('FALSE')
361
362
            false_str_ptr = g.builder.gep(false_str_val, [zero, zero])
            str_ptr = g.builder.select(expr_val, true_str_ptr, false_str_ptr)
dbarbera's avatar
dbarbera committed
363
            g.builder.call(g.funcs['printf'], [str_ptr])
dbarbera's avatar
dbarbera committed
364
365
        elif basic_ty.kind == 'StringType':
            expr_ptr = g.builder.gep(expr_val, [zero, zero])
dbarbera's avatar
dbarbera committed
366
            g.builder.call(g.funcs['printf'], [expr_ptr])
367
368
369
370
371
372
373
        else:
            raise NotImplementedError


def _generate_writeln(params):
    ''' Generate the code for the writeln operator '''
    _generate_write(params)
374
375

    zero = core.Constant.int(g.i32, 0)
376
    str_cons = _get_string_cons('\n')
377
    str_ptr = g.builder.gep(str_cons, [zero, zero])
dbarbera's avatar
dbarbera committed
378
    g.builder.call(g.funcs['printf'], [str_ptr])
dbarbera's avatar
dbarbera committed
379
380
381
382
383
384
385
386
387


def _generate_reset_timer(params):
    ''' Generate the code for the reset timer operator '''
    raise NotImplementedError


def _generate_set_timer(params):
    ''' Generate the code for the set timer operator '''
388
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
389
390
391
392


@generate.register(ogAST.TaskAssign)
def _task_assign(task):
dbarbera's avatar
dbarbera committed
393
    ''' Generate the code of a list of assignments '''
394
395
    for expr in task.elems:
        expression(expr)
Maxime Perrotin's avatar
Maxime Perrotin committed
396
397
398
399
400


@generate.register(ogAST.TaskInformalText)
def _task_informal_text(task):
    ''' Generate comments for informal text '''
401
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
402
403
404
405


@generate.register(ogAST.TaskForLoop)
def _task_forloop(task):
dbarbera's avatar
dbarbera committed
406
    ''' Generate the code for a for loop '''
dbarbera's avatar
dbarbera committed
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
    for loop in task.elems:
        if loop['range']:
            _generate_for_range(loop)
        else:
            _generate_for_iterable(loop)


def _generate_for_range(loop):
    ''' Generate the code for a for x in range loop '''
    func = g.builder.basic_block.function
    cond_block = func.append_basic_block('for:cond')
    body_block = func.append_basic_block('for:body')
    inc_block = func.append_basic_block('for:inc')
    end_block = func.append_basic_block('')

    _push_scope()

    loop_var = g.builder.alloca(g.i32, None, str(loop['var']))
    g.scope.define(str(loop['var']), loop_var)

    if loop['range']['start']:
        start_val = expression(loop['range']['start'])
        if type(loop['range']['start']) in [ogAST.PrimPath, ogAST.PrimVariable]:
            start_val = g.builder.load(start_val)
        g.builder.store(start_val, loop_var)
    else:
        g.builder.store(core.Constant.int(g.i32, 0), loop_var)

    stop_val = expression(loop['range']['stop'])
    if type(loop['range']['stop']) in [ogAST.PrimPath, ogAST.PrimVariable]:
        stop_val = g.builder.load(stop_val)
    g.builder.branch(cond_block)

    g.builder.position_at_end(cond_block)
    loop_val = g.builder.load(loop_var)
    cond_val = g.builder.icmp(core.ICMP_SLT, loop_val, stop_val)
    g.builder.cbranch(cond_val, body_block, end_block)

    g.builder.position_at_end(body_block)
    generate(loop['transition'])
    g.builder.branch(inc_block)

    g.builder.position_at_end(inc_block)
    step_val = core.Constant.int(g.i32, loop['range']['step'])
    loop_val = g.builder.load(loop_var)
    temp_val = g.builder.add(loop_val, step_val)
    g.builder.store(temp_val, loop_var)
    g.builder.branch(cond_block)

    g.builder.position_at_end(end_block)

    _pop_scope()


def _generate_for_iterable(loop):
    ''' Generate the code for a for x in iterable loop'''
463
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
464

dbarbera's avatar
dbarbera committed
465

Maxime Perrotin's avatar
Maxime Perrotin committed
466
467
468
469
# ------ expressions --------

@singledispatch
def expression(expr):
dbarbera's avatar
dbarbera committed
470
    ''' Generate the code for Expression-classes '''
Maxime Perrotin's avatar
Maxime Perrotin committed
471
472
473
474
    raise TypeError('Unsupported expression: ' + str(expr))


@expression.register(ogAST.PrimVariable)
Maxime Perrotin's avatar
Maxime Perrotin committed
475
def _primary_variable(prim):
dbarbera's avatar
dbarbera committed
476
    ''' Generate the code for a single variable reference '''
477
    return g.scope.resolve(str(prim.value[0]))
Maxime Perrotin's avatar
Maxime Perrotin committed
478
479


Maxime Perrotin's avatar
Maxime Perrotin committed
480
@expression.register(ogAST.PrimPath)
dbarbera's avatar
dbarbera committed
481
def _prim_path(prim):
dbarbera's avatar
dbarbera committed
482
    ''' Generate the code for an of an element list (path) '''
dbarbera's avatar
dbarbera committed
483

484
    var_ptr = g.scope.resolve(str(prim.value.pop(0)))
dbarbera's avatar
dbarbera committed
485
486

    if not prim.value:
487
        return var_ptr
dbarbera's avatar
dbarbera committed
488
489
490
491
492
493
494
495
496
497
498
499
500

    zero_cons = core.Constant.int(g.i32, 0)

    for field_name in prim.value:
        var_ty = var_ptr.type
        if var_ty.kind == core.TYPE_POINTER and var_ty.pointee.kind == core.TYPE_STRUCT:
            struct = g.structs[var_ty.pointee.name]
            field_idx_cons = core.Constant.int(g.i32, struct.idx(field_name))
            field_ptr = g.builder.gep(var_ptr, [zero_cons, field_idx_cons])
            var_ptr = field_ptr
        else:
            raise NotImplementedError

501
    return var_ptr
Maxime Perrotin's avatar
Maxime Perrotin committed
502
503


Maxime Perrotin's avatar
Maxime Perrotin committed
504
505
506
507
508
509
510
511
512
513
514
515
@expression.register(ogAST.ExprPlus)
@expression.register(ogAST.ExprMul)
@expression.register(ogAST.ExprMinus)
@expression.register(ogAST.ExprEq)
@expression.register(ogAST.ExprNeq)
@expression.register(ogAST.ExprGt)
@expression.register(ogAST.ExprGe)
@expression.register(ogAST.ExprLt)
@expression.register(ogAST.ExprLe)
@expression.register(ogAST.ExprDiv)
@expression.register(ogAST.ExprMod)
@expression.register(ogAST.ExprRem)
dbarbera's avatar
dbarbera committed
516
517
def _basic(expr):
    ''' Generate the code for an arithmetic of relational expression '''
518
519
    lefttmp = expression(expr.left)
    righttmp = expression(expr.right)
520
521

    # load the value of the expression if it is a pointer
522
    if lefttmp.type.kind == core.TYPE_POINTER:
523
        lefttmp = g.builder.load(lefttmp, 'lefttmp')
524
    if righttmp.type.kind == core.TYPE_POINTER:
dbarbera's avatar
dbarbera committed
525
        righttmp = g.builder.load(righttmp, 'righttmp')
526
527
528
529
530
531

    if lefttmp.type.kind != righttmp.type.kind:
        raise NotImplementedError

    if lefttmp.type.kind == core.TYPE_INTEGER:
        if expr.operand == '+':
532
            return g.builder.add(lefttmp, righttmp, 'addtmp')
533
        elif expr.operand == '-':
534
            return g.builder.sub(lefttmp, righttmp, 'subtmp')
535
        elif expr.operand == '*':
536
            return g.builder.mul(lefttmp, righttmp, 'multmp')
537
        elif expr.operand == '/':
538
            return g.builder.sdiv(lefttmp, righttmp, 'divtmp')
539
        elif expr.operand == 'mod':
540
            # l mod r == (((l rem r) + r) rem r)
541
542
543
            remtmp = g.builder.srem(lefttmp, righttmp)
            addtmp = g.builder.add(remtmp, righttmp)
            return g.builder.srem(addtmp, righttmp, 'modtmp')
544
        elif expr.operand == 'rem':
545
            return g.builder.srem(lefttmp, righttmp, 'remtmp')
546
        elif expr.operand == '<':
547
            return g.builder.icmp(core.ICMP_SLT, lefttmp, righttmp, 'lttmp')
548
        elif expr.operand == '<=':
549
            return g.builder.icmp(core.ICMP_SLE, lefttmp, righttmp, 'letmp')
550
        elif expr.operand == '=':
551
            return g.builder.icmp(core.ICMP_EQ, lefttmp, righttmp, 'eqtmp')
552
        elif expr.operand == '/=':
553
            return g.builder.icmp(core.ICMP_NE, lefttmp, righttmp, 'netmp')
554
        elif expr.operand == '>=':
555
            return g.builder.icmp(core.ICMP_SGE, lefttmp, righttmp, 'getmp')
556
        elif expr.operand == '>':
557
            return g.builder.icmp(core.ICMP_SGT, lefttmp, righttmp, 'gttmp')
558
559
560
561
        else:
            raise NotImplementedError
    elif lefttmp.type.kind == core.TYPE_DOUBLE:
        if expr.operand == '+':
562
            return g.builder.fadd(lefttmp, righttmp, 'addtmp')
563
        elif expr.operand == '-':
564
            return g.builder.fsub(lefttmp, righttmp, 'subtmp')
565
        elif expr.operand == '*':
566
            return g.builder.fmul(lefttmp, righttmp, 'multmp')
567
        elif expr.operand == '/':
568
            return g.builder.fdiv(lefttmp, righttmp, 'divtmp')
569
        elif expr.operand == '<':
570
            return g.builder.fcmp(core.FCMP_OLT, lefttmp, righttmp, 'lttmp')
571
        elif expr.operand == '<=':
572
            return g.builder.fcmp(core.FCMP_OLE, lefttmp, righttmp, 'letmp')
573
        elif expr.operand == '=':
574
            return g.builder.fcmp(core.FCMP_OEQ, lefttmp, righttmp, 'eqtmp')
575
        elif expr.operand == '/=':
576
            return g.builder.fcmp(core.FCMP_ONE, lefttmp, righttmp, 'netmp')
577
        elif expr.operand == '>=':
578
            return g.builder.fcmp(core.FCMP_OGE, lefttmp, righttmp, 'getmp')
579
        elif expr.operand == '>':
580
            return g.builder.fcmp(core.FCMP_OGT, lefttmp, righttmp, 'gttmp')
581
582
        else:
            raise NotImplementedError
583
    else:
584
        raise NotImplementedError
585

Maxime Perrotin's avatar
Maxime Perrotin committed
586

587
588
@expression.register(ogAST.ExprAssign)
def _assign(expr):
dbarbera's avatar
dbarbera committed
589
    ''' Generate the code for an assign expression '''
590
591
    left = expression(expr.left)
    right = expression(expr.right)
592

593
594
    _generate_assign(left, right)
    return left
595

596
597
598
599
600

def _generate_assign(left, right):
    ''' Generate code for an assign from two LLVM values'''
    # This is extracted as an standalone function because is used by
    # multiple generation rules
601
    if left.type.pointee.kind == core.TYPE_STRUCT:
602
603
        size = core.Constant.sizeof(left.type.pointee)
        align = core.Constant.int(g.i32, 0)
604
        volatile = core.Constant.int(g.i1, 0)
605

606
607
        right_ptr = g.builder.bitcast(right, g.i8_ptr)
        left_ptr = g.builder.bitcast(left, g.i8_ptr)
608

dbarbera's avatar
dbarbera committed
609
        g.builder.call(g.funcs['memcpy'], [left_ptr, right_ptr, size, align, volatile])
610
    else:
611
612
        if right.type.kind == core.TYPE_POINTER:
            right = g.builder.load(right)
613
        g.builder.store(right, left)
dbarbera's avatar
dbarbera committed
614

Maxime Perrotin's avatar
Maxime Perrotin committed
615

Maxime Perrotin's avatar
Maxime Perrotin committed
616
617
618
@expression.register(ogAST.ExprOr)
@expression.register(ogAST.ExprAnd)
@expression.register(ogAST.ExprXor)
dbarbera's avatar
dbarbera committed
619
620
def _logical(expr):
    ''' Generate the code for a logical expression '''
dbarbera's avatar
dbarbera committed
621
622
623
624
625
626
627
628
629
    lefttmp = expression(expr.left)
    righttmp = expression(expr.right)

    ty = find_basic_type(expr.exprType)
    if ty.kind != 'BooleanType':
        raise NotImplementedError

    # load the value of the expression if it is a pointer
    if lefttmp.type.kind == core.TYPE_POINTER:
630
        lefttmp = g.builder.load(lefttmp, 'lefttmp')
dbarbera's avatar
dbarbera committed
631
    if righttmp.type.kind == core.TYPE_POINTER:
dbarbera's avatar
dbarbera committed
632
        righttmp = g.builder.load(righttmp, 'righttmp')
dbarbera's avatar
dbarbera committed
633

dbarbera's avatar
dbarbera committed
634
635
636
    if expr.operand == 'and':
        return g.builder.and_(lefttmp, righttmp, 'andtmp')
    elif expr.operand == 'or':
637
        return g.builder.or_(lefttmp, righttmp, 'ortmp')
dbarbera's avatar
dbarbera committed
638
    else:
639
        return g.builder.xor(lefttmp, righttmp, 'xortmp')
dbarbera's avatar
dbarbera committed
640

Maxime Perrotin's avatar
Maxime Perrotin committed
641

Maxime Perrotin's avatar
Maxime Perrotin committed
642
@expression.register(ogAST.ExprAppend)
Maxime Perrotin's avatar
Maxime Perrotin committed
643
644
def _append(expr):
    ''' Generate code for the APPEND construct: a // b '''
645
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
646
647


Maxime Perrotin's avatar
Maxime Perrotin committed
648
@expression.register(ogAST.ExprIn)
Maxime Perrotin's avatar
Maxime Perrotin committed
649
def _expr_in(expr):
dbarbera's avatar
dbarbera committed
650
    ''' Generate the code for an in expression '''
651
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
652
653


Maxime Perrotin's avatar
Maxime Perrotin committed
654
@expression.register(ogAST.PrimEnumeratedValue)
Maxime Perrotin's avatar
Maxime Perrotin committed
655
656
def _enumerated_value(primary):
    ''' Generate code for an enumerated value '''
dbarbera's avatar
dbarbera committed
657
658
659
    enumerant = primary.value[0].replace('_', '-')
    basic_ty = find_basic_type(primary.exprType)
    return core.Constant.int(g.i32, basic_ty.EnumValues[enumerant].IntValue)
Maxime Perrotin's avatar
Maxime Perrotin committed
660
661


Maxime Perrotin's avatar
Maxime Perrotin committed
662
@expression.register(ogAST.PrimChoiceDeterminant)
Maxime Perrotin's avatar
Maxime Perrotin committed
663
664
def _choice_determinant(primary):
    ''' Generate code for a choice determinant (enumerated) '''
665
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
666
667


Maxime Perrotin's avatar
Maxime Perrotin committed
668
@expression.register(ogAST.PrimInteger)
669
670
def _integer(primary):
    ''' Generate code for a raw integer value  '''
671
    return core.Constant.int(g.i32, primary.value[0])
672
673


Maxime Perrotin's avatar
Maxime Perrotin committed
674
@expression.register(ogAST.PrimReal)
675
676
def _real(primary):
    ''' Generate code for a raw real value  '''
677
    return core.Constant.real(g.double, primary.value[0])
678
679


Maxime Perrotin's avatar
Maxime Perrotin committed
680
@expression.register(ogAST.PrimBoolean)
681
682
def _boolean(primary):
    ''' Generate code for a raw boolean value  '''
dbarbera's avatar
dbarbera committed
683
    if primary.value[0].lower() == 'true':
684
        return core.Constant.int(g.i1, 1)
dbarbera's avatar
dbarbera committed
685
    else:
686
        return core.Constant.int(g.i1, 0)
Maxime Perrotin's avatar
Maxime Perrotin committed
687
688


Maxime Perrotin's avatar
Maxime Perrotin committed
689
@expression.register(ogAST.PrimEmptyString)
Maxime Perrotin's avatar
Maxime Perrotin committed
690
691
def _empty_string(primary):
    ''' Generate code for an empty SEQUENCE OF: {} '''
692
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
693
694


Maxime Perrotin's avatar
Maxime Perrotin committed
695
@expression.register(ogAST.PrimStringLiteral)
Maxime Perrotin's avatar
Maxime Perrotin committed
696
697
def _string_literal(primary):
    ''' Generate code for a string (Octet String) '''
dbarbera's avatar
dbarbera committed
698
    return _get_string_cons(str(primary.value[1:-1]))
Maxime Perrotin's avatar
Maxime Perrotin committed
699
700


Maxime Perrotin's avatar
Maxime Perrotin committed
701
@expression.register(ogAST.PrimConstant)
Maxime Perrotin's avatar
Maxime Perrotin committed
702
703
def _constant(primary):
    ''' Generate code for a reference to an ASN.1 constant '''
704
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
705
706


Maxime Perrotin's avatar
Maxime Perrotin committed
707
@expression.register(ogAST.PrimMantissaBaseExp)
Maxime Perrotin's avatar
Maxime Perrotin committed
708
709
def _mantissa_base_exp(primary):
    ''' Generate code for a Real with Mantissa-base-Exponent representation '''
710
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
711
712


Maxime Perrotin's avatar
Maxime Perrotin committed
713
@expression.register(ogAST.PrimIfThenElse)
dbarbera's avatar
dbarbera committed
714
def _if_then_else(ifthen):
dbarbera's avatar
dbarbera committed
715
    ''' Generate the code for ternary operator '''
716
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
717
718


Maxime Perrotin's avatar
Maxime Perrotin committed
719
@expression.register(ogAST.PrimSequence)
Maxime Perrotin's avatar
Maxime Perrotin committed
720
def _sequence(seq):
dbarbera's avatar
dbarbera committed
721
    ''' Generate the code for an ASN.1 SEQUENCE '''
dbarbera's avatar
dbarbera committed
722
723
724
725
726
727
728
729
730
731
732
    struct = g.structs[seq.exprType.ReferencedTypeName]
    struct_ptr = g.builder.alloca(struct.ty)
    zero_cons = core.Constant.int(g.i32, 0)

    for field_name, field_expr in seq.value.viewitems():
        field_val = expression(field_expr)
        field_idx_cons = core.Constant.int(g.i32, struct.idx(field_name))
        field_ptr = g.builder.gep(struct_ptr, [zero_cons, field_idx_cons])
        g.builder.store(field_val, field_ptr)

    return struct_ptr
Maxime Perrotin's avatar
Maxime Perrotin committed
733
734


Maxime Perrotin's avatar
Maxime Perrotin committed
735
@expression.register(ogAST.PrimSequenceOf)
Maxime Perrotin's avatar
Maxime Perrotin committed
736
def _sequence_of(seqof):
dbarbera's avatar
dbarbera committed
737
    ''' Generate the code for an ASN.1 SEQUENCE OF '''
738
    ty = _generate_type(seqof.exprType)
739
740
741
    struct_ptr = g.builder.alloca(ty)
    zero_cons = core.Constant.int(g.i32, 0)
    array_ptr = g.builder.gep(struct_ptr, [zero_cons, zero_cons])
742
743

    for idx, expr in enumerate(seqof.value):
744
        idx_cons = core.Constant.int(g.i32, idx)
745
        expr_val = expression(expr)
746
747
        pos_ptr = g.builder.gep(array_ptr, [zero_cons, idx_cons])
        g.builder.store(expr_val, pos_ptr)
748
749

    return struct_ptr
Maxime Perrotin's avatar
Maxime Perrotin committed
750
751


Maxime Perrotin's avatar
Maxime Perrotin committed
752
@expression.register(ogAST.PrimChoiceItem)
Maxime Perrotin's avatar
Maxime Perrotin committed
753
def _choiceitem(choice):
dbarbera's avatar
dbarbera committed
754
    ''' Generate the code for a CHOICE expression '''
755
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
756
757
758
759


@generate.register(ogAST.Decision)
def _decision(dec):
dbarbera's avatar
dbarbera committed
760
    ''' Generate the code for a decision '''
761
    func = g.builder.basic_block.function
dbarbera's avatar
dbarbera committed
762
763
764
765

    ans_cond_blocks = [func.append_basic_block('ans_cond') for ans in dec.answers]
    end_block = func.append_basic_block('end')

766
    g.builder.branch(ans_cond_blocks[0])
dbarbera's avatar
dbarbera committed
767
768
769
770
771

    for idx, ans in enumerate(dec.answers):
        ans_cond_block = ans_cond_blocks[idx]
        if ans.transition:
            ans_tr_block = func.append_basic_block('ans_tr')
772
        g.builder.position_at_end(ans_cond_block)
dbarbera's avatar
dbarbera committed
773
774

        if ans.kind == 'constant':
dbarbera's avatar
dbarbera committed
775
            next_block = ans_cond_blocks[idx+1] if idx < len(ans_cond_blocks)-1 else end_block
dbarbera's avatar
dbarbera committed
776
777
778
779
780
781

            expr = ans.openRangeOp()
            expr.left = dec.question
            expr.right = ans.constant
            expr_val = expression(expr)

782
783
784
            true_cons = core.Constant.int(g.i1, 1)
            cond_val = g.builder.icmp(core.ICMP_EQ, expr_val, true_cons)
            g.builder.cbranch(cond_val, ans_tr_block if ans.transition else end_block, next_block)
dbarbera's avatar
dbarbera committed
785
786
        elif ans.kind == 'else':
            if ans.transition:
787
                g.builder.branch(ans_tr_block)
dbarbera's avatar
dbarbera committed
788
            else:
789
                g.builder.branch(end_block)
dbarbera's avatar
dbarbera committed
790
791
792
793
        else:
            raise NotImplementedError

        if ans.transition:
794
            g.builder.position_at_end(ans_tr_block)
dbarbera's avatar
dbarbera committed
795
            generate(ans.transition)
796
            g.builder.branch(end_block)
dbarbera's avatar
dbarbera committed
797

798
    g.builder.position_at_end(end_block)
Maxime Perrotin's avatar
Maxime Perrotin committed
799
800
801
802


@generate.register(ogAST.Label)
def _label(tr):
dbarbera's avatar
dbarbera committed
803
    ''' TGenerate the code for a Label '''
804
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
805
806
807
808


@generate.register(ogAST.Transition)
def _transition(tr):
dbarbera's avatar
dbarbera committed
809
    ''' Generate the code for a transition '''
810
811
812
813
814
815
    for action in tr.actions:
        generate(action)
        if isinstance(action, ogAST.Label):
            return
    if tr.terminator:
        _generate_terminator(tr.terminator)
816
817


818
def _generate_terminator(term):
dbarbera's avatar
dbarbera committed
819
    ''' Generate the code for a transition termiantor '''
820
    if term.label:
821
        raise NotImplementedError
822
823
824
    if term.kind == 'next_state':
        state = term.inputString.lower()
        if state.strip() != '-':
825
            next_id_cons = core.Constant.int(g.i32, term.next_id)
826
            g.builder.store(next_id_cons, g.scope.resolve('id'))
827
            if term.next_id == -1:
828
                state_ptr = g.global_scope.resolve('state')
829
830
                state_id_cons = g.states[state]
                g.builder.store(state_id_cons, state_ptr)
831
        else:
832
            raise NotImplementedError
833
    elif term.kind == 'join':
834
        raise NotImplementedError
835
    elif term.kind == 'stop':
836
        raise NotImplementedError
837
    elif term.kind == 'return':
838
839
840
841
842
843
844
845
        if term.next_id == -1 and term.return_expr:
            g.builder.ret(expression(term.return_expr))
        elif term.next_id == -1:
            g.builder.ret_void()
        else:
            next_id_cons = core.Constant.int(g.i32, term.next_id)
            g.builder.store(next_id_cons, g.scope.resolve('id'))
            g.builder.ret_void()
Maxime Perrotin's avatar
Maxime Perrotin committed
846
847
848
849


@generate.register(ogAST.Floating_label)
def _floating_label(label):
dbarbera's avatar
dbarbera committed
850
    ''' Generate the code for a floating label '''
851
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
852
853
854
855
856


@generate.register(ogAST.Procedure)
def _inner_procedure(proc):
    ''' Generate the code for a procedure '''
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
    func_name = str(proc.inputString)
    param_tys = [core.Type.pointer(_generate_type(p['type'])) for p in proc.fpar]
    func_ty = core.Type.function(g.void, param_tys)
    func = core.Function.new(g.module, func_ty, func_name)
    g.funcs[func_name] = func

    _push_scope()

    for arg, param in zip(func.args, proc.fpar):
        g.scope.define(str(param['name']), arg)

    entry_block = func.append_basic_block('entry')
    g.builder = core.Builder.new(entry_block)

    for name, (ty, expr) in proc.variables.viewitems():
        raise NotImplementedError

    generate(proc.content.start.transition)

    for label in proc.content.floating_labels:
        raise NotImplementedError

    _pop_scope()

    func.verify()
dbarbera's avatar
dbarbera committed
882
883
884


def _generate_type(ty):
885
    ''' Generate the equivalent LLVM type of a ASN.1 type '''
dbarbera's avatar
dbarbera committed
886
887
    basic_ty = find_basic_type(ty)
    if basic_ty.kind == 'IntegerType':
888
        return g.i32
dbarbera's avatar
dbarbera committed
889
    elif basic_ty.kind == 'BooleanType':
890
        return g.i1
dbarbera's avatar
dbarbera committed
891
    elif basic_ty.kind == 'RealType':
892
        return g.double
893
    elif basic_ty.kind == 'SequenceOfType':
dbarbera's avatar
dbarbera committed
894
895
        if ty.ReferencedTypeName in g.structs:
            return g.structs[ty.ReferencedTypeName].ty
896
897
898
899
900
901
902
903

        min_size =