LlvmGenerator.py 43.2 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
dbarbera's avatar
dbarbera committed
23
from llvm import core, ee
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

dbarbera's avatar
dbarbera committed
33
# Global context
34
35
36
g = None


dbarbera's avatar
dbarbera committed
37
class Context():
38
    def __init__(self, process):
dbarbera's avatar
dbarbera committed
39
40
        self.name = str(process.processName)
        self.module = core.Module.new(self.name)
dbarbera's avatar
dbarbera committed
41
        self.target_data = ee.TargetData.new(self.module.data_layout)
42
43
        self.dataview = process.dataview

44
45
        self.scope = Scope()
        self.global_scope = self.scope
46
        self.states = {}
dbarbera's avatar
dbarbera committed
47
        self.structs = {}
dbarbera's avatar
dbarbera committed
48
        self.unions = {}
49
        self.strings = {}
dbarbera's avatar
dbarbera committed
50
        self.funcs = {}
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)

dbarbera's avatar
dbarbera committed
65
66
67
68
        # Initialize common constants
        self.zero = core.Constant.int(self.i32, 0)
        self.one = core.Constant.int(self.i32, 1)

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

dbarbera's avatar
dbarbera committed
73
        self.funcs['memcpy'] = core.Function.intrinsic(
74
75
            self.module,
            core.INTR_MEMCPY,
76
77
            [self.i8_ptr, self.i8_ptr, self.i64]
        )
Maxime Perrotin's avatar
Maxime Perrotin committed
78

79
80
81
82
83
84
        self.funcs['powi'] = core.Function.intrinsic(
            self.module,
            core.INTR_POWI,
            [self.double]
        )

dbarbera's avatar
dbarbera committed
85
86
87
88
89
90
        self.funcs['fabs'] = core.Function.intrinsic(
            self.module,
            core.INTR_FABS,
            [self.double]
        )

dbarbera's avatar
dbarbera committed
91

92
93
class StructType():
    def __init__(self, name, field_names, field_types):
dbarbera's avatar
dbarbera committed
94
        self.name = name
95
96
97
98
99
        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
100
101


dbarbera's avatar
dbarbera committed
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class UnionType():
    def __init__(self, name, field_names, field_types):
        self.name = name
        self.field_names = field_names
        self.field_types = field_types
        # Unions are represented a struct with a field indicating the index of its type
        # and a byte array with the size of the biggest type in the union
        self.size = max([g.target_data.size(ty) for ty in field_types])
        self.ty = core.Type.struct([g.i32, core.Type.array(g.i8, self.size)], name)

    def kind(self, name):
        idx = self.field_names.index(name)
        return (idx, self.field_types[idx])


117
118
119
class Scope:
    def __init__(self, parent=None):
        self.vars = {}
dbarbera's avatar
dbarbera committed
120
        self.labels = {}
121
122
123
124
125
126
127
128
129
130
131
132
        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:
dbarbera's avatar
dbarbera committed
133
            raise NameError("name '%s' is not defined" % name)
134

dbarbera's avatar
dbarbera committed
135
136
137
138
139
140
141
142
143
    def label(self, name):
        name = name.lower()
        label_block = self.labels.get(name)
        if not label_block:
            func = g.builder.basic_block.function
            label_block = func.append_basic_block(name)
            self.labels[name] = label_block
        return label_block

dbarbera's avatar
dbarbera committed
144

Maxime Perrotin's avatar
Maxime Perrotin committed
145
146
147
148
@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
149

dbarbera's avatar
dbarbera committed
150

Maxime Perrotin's avatar
Maxime Perrotin committed
151
152
153
# Processing of the AST
@generate.register(ogAST.Process)
def _process(process):
dbarbera's avatar
dbarbera committed
154
    ''' Generate LLVM IR code '''
dbarbera's avatar
dbarbera committed
155
156
    process_name = str(process.processName)
    LOG.info('Generating LLVM IR code for process ' + process_name)
157

158
    global g
dbarbera's avatar
dbarbera committed
159
    g = Context(process)
160

dbarbera's avatar
dbarbera committed
161
162
163
164
165
166
    # 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
167

168
169
    # Initialize states
    for name, val in process.mapping.viewitems():
170
        if not name.endswith('START'):
171
172
173
174
175
            cons_val = core.Constant.int(g.i32, len(g.states))
            g.states[name] = cons_val
        elif name != 'START':
            cons_val = core.Constant.int(g.i32, val)
            g.states[name] = cons_val
176

177
    # Generate state var
178
179
    state_cons = g.module.add_global_variable(g.i32, 'state')
    state_cons.initializer = core.Constant.int(g.i32, -1)
180
    g.scope.define('state', state_cons)
181

182
183
    # Generare process-level vars
    for name, (ty, expr) in process.variables.viewitems():
dbarbera's avatar
dbarbera committed
184
        var_ty = generate_type(ty)
185
        global_var = g.module.add_global_variable(var_ty, str(name))
186
        global_var.initializer = core.Constant.null(var_ty)
187
        g.scope.define(str(name).lower(), global_var)
188

dbarbera's avatar
dbarbera committed
189
190
191
    # Declare timer set/reset functions
    for timer in process.timers:
        # TODO: Should be uint?
192
193
        decl_func("set_%s" % str(timer), g.void, [g.i32_ptr], True)
        decl_func("reset_%s" % str(timer), g.void, [], True)
dbarbera's avatar
dbarbera committed
194

195
    # Declare output signal functions
dbarbera's avatar
dbarbera committed
196
    for signal in process.output_signals:
197
        if 'type' in signal:
dbarbera's avatar
dbarbera committed
198
            param_tys = [core.Type.pointer(generate_type(signal['type']))]
199
200
        else:
            param_tys = []
201
        decl_func(str(signal['name']), g.void, param_tys, True)
dbarbera's avatar
dbarbera committed
202

203
    # Declare external procedures functions
dbarbera's avatar
dbarbera committed
204
    for proc in [proc for proc in process.procedures if proc.external]:
dbarbera's avatar
dbarbera committed
205
        param_tys = [core.Type.pointer(generate_type(p['type'])) for p in proc.fpar]
206
        decl_func(str(proc.inputString), g.void, param_tys, True)
dbarbera's avatar
dbarbera committed
207

208
209
    # Generate internal procedures
    for proc in process.content.inner_procedures:
210
        generate(proc)
211

212
    # Generate process functions
dbarbera's avatar
dbarbera committed
213
214
    generate_runtr_func(process)
    generate_startup_func(process)
215

216
217
    # Generate input signals
    for signal in process.input_signals:
dbarbera's avatar
dbarbera committed
218
        generate_input_signal(signal, mapping[signal['name']])
219

dbarbera's avatar
dbarbera committed
220
221
    g.module.verify()

dbarbera's avatar
dbarbera committed
222
    with open(g.name + '.ll', 'w') as ll_file:
dbarbera's avatar
dbarbera committed
223
        ll_file.write(str(g.module))
224
225


dbarbera's avatar
dbarbera committed
226
def generate_runtr_func(process):
dbarbera's avatar
dbarbera committed
227
    ''' Generate code for the run_transition function '''
228
    func = decl_func('run_transition', g.void, [g.i32])
229

dbarbera's avatar
dbarbera committed
230
    open_scope()
231

232
233
234
235
236
    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
237
    g.builder = core.Builder.new(entry_block)
238
239

    # entry
dbarbera's avatar
dbarbera committed
240
    id_ptr = g.builder.alloca(g.i32, None, 'id')
241
    g.scope.define('id', id_ptr)
dbarbera's avatar
dbarbera committed
242
243
    g.builder.store(func.args[0], id_ptr)
    g.builder.branch(cond_block)
244
245

    # cond
dbarbera's avatar
dbarbera committed
246
    g.builder.position_at_end(cond_block)
247
    no_tr_cons = core.Constant.int(g.i32, -1)
248
249
    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
250
    g.builder.cbranch(cond_val, body_block, exit_block)
251
252

    # body
dbarbera's avatar
dbarbera committed
253
254
    g.builder.position_at_end(body_block)
    switch = g.builder.switch(func.args[0], exit_block)
255
256
257
258

    # transitions
    for idx, tr in enumerate(process.transitions):
        tr_block = func.append_basic_block('tr%d' % idx)
259
        const = core.Constant.int(g.i32, idx)
260
        switch.add_case(const, tr_block)
dbarbera's avatar
dbarbera committed
261
        g.builder.position_at_end(tr_block)
262
        generate(tr)
dbarbera's avatar
dbarbera committed
263
264
        if not g.builder.basic_block.terminator:
            g.builder.branch(cond_block)
265
266

    # exit
dbarbera's avatar
dbarbera committed
267
268
    g.builder.position_at_end(exit_block)
    g.builder.ret_void()
269

dbarbera's avatar
dbarbera committed
270
271
272
273
274
275
276
277
278
    Helper.inner_labels_to_floating(process)
    for label in process.content.floating_labels:
        generate(label)

    # TODO: Use defined cond_block instead?
    next_tr_label_block = g.scope.label('next_transition')
    g.builder.position_at_end(next_tr_label_block)
    g.builder.branch(cond_block)

dbarbera's avatar
dbarbera committed
279
    close_scope()
280

281
282
283
284
    func.verify()
    return func


dbarbera's avatar
dbarbera committed
285
def generate_startup_func(process):
dbarbera's avatar
dbarbera committed
286
    ''' Generate code for the startup function '''
287
    func = decl_func(g.name + '_startup', g.void, [])
288

dbarbera's avatar
dbarbera committed
289
    open_scope()
290

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

294
295
296
    # Initialize process level variables
    for name, (ty, expr) in process.variables.viewitems():
        if expr:
dbarbera's avatar
dbarbera committed
297
            global_var = g.scope.resolve(str(name))
dbarbera's avatar
dbarbera committed
298
            generate_assign(global_var, expression(expr))
299

300
301
    g.builder.call(g.funcs['run_transition'], [core.Constant.int(g.i32, 0)])
    g.builder.ret_void()
Maxime Perrotin's avatar
Maxime Perrotin committed
302

dbarbera's avatar
dbarbera committed
303
    close_scope()
304

305
306
    func.verify()
    return func
Maxime Perrotin's avatar
Maxime Perrotin committed
307
308


dbarbera's avatar
dbarbera committed
309
def generate_input_signal(signal, inputs):
dbarbera's avatar
dbarbera committed
310
    ''' Generate code for an input signal '''
dbarbera's avatar
dbarbera committed
311
    func_name = g.name + "_" + str(signal['name'])
312
313
    param_tys = []
    if 'type' in signal:
dbarbera's avatar
dbarbera committed
314
        param_tys.append(core.Type.pointer(generate_type(signal['type'])))
315
316

    func = decl_func(func_name, g.void, param_tys)
317

dbarbera's avatar
dbarbera committed
318
    open_scope()
319

320
321
    entry_block = func.append_basic_block('entry')
    exit_block = func.append_basic_block('exit')
322
    g.builder = core.Builder.new(entry_block)
323

324
    g_state_val = g.builder.load(g.global_scope.resolve('state'))
325
    switch = g.builder.switch(g_state_val, exit_block)
326

327
    for state_name, state_id in g.states.iteritems():
328
329
        state_block = func.append_basic_block('state_%s' % str(state_name))
        switch.add_case(state_id, state_block)
330
        g.builder.position_at_end(state_block)
331
332
333

        # TODO: Nested states

334
335
336
        input = inputs.get(state_name)
        if input:
            for var_name in input.parameters:
dbarbera's avatar
dbarbera committed
337
                var_ptr = g.scope.resolve(str(var_name))
338
339
340
341
                if is_struct_ptr(var_ptr):
                    generate_assign(var_ptr, func.args[0])
                else:
                    generate_assign(var_ptr, g.builder.load(func.args[0]))
342
            if input.transition:
343
                id_val = core.Constant.int(g.i32, input.transition_id)
344
                g.builder.call(g.funcs['run_transition'], [id_val])
345

346
        g.builder.ret_void()
347

348
349
    g.builder.position_at_end(exit_block)
    g.builder.ret_void()
350

dbarbera's avatar
dbarbera committed
351
    close_scope()
352

353
354
355
    func.verify()


Maxime Perrotin's avatar
Maxime Perrotin committed
356
357
358
359
@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 '''
dbarbera's avatar
dbarbera committed
360
361
362
    for out in output.output:
        name = out['outputName'].lower()

363
        if name == 'write':
dbarbera's avatar
dbarbera committed
364
            generate_write(out['params'])
dbarbera's avatar
dbarbera committed
365
            continue
366
        elif name == 'writeln':
dbarbera's avatar
dbarbera committed
367
            generate_writeln(out['params'])
368
            continue
dbarbera's avatar
dbarbera committed
369
        elif name == 'reset_timer':
dbarbera's avatar
dbarbera committed
370
            generate_reset_timer(out['params'])
dbarbera's avatar
dbarbera committed
371
372
            continue
        elif name == 'set_timer':
dbarbera's avatar
dbarbera committed
373
            generate_set_timer(out['params'])
dbarbera's avatar
dbarbera committed
374
375
            continue

dbarbera's avatar
dbarbera committed
376
        func = g.funcs[str(name).lower()]
377
378
379
380
381
382
383
384
385
386
387
388
389

        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
390
391


dbarbera's avatar
dbarbera committed
392
def generate_write(params):
dbarbera's avatar
dbarbera committed
393
    ''' Generate the code for the write operator '''
394
395
396
    for param in params:
        basic_ty = find_basic_type(param.exprType)
        expr_val = expression(param)
397

398
        if basic_ty.kind in ['IntegerType', 'Integer32Type']:
dbarbera's avatar
dbarbera committed
399
            fmt_val = get_string_cons('% d')
dbarbera's avatar
dbarbera committed
400
            fmt_ptr = g.builder.gep(fmt_val, [g.zero, g.zero])
dbarbera's avatar
dbarbera committed
401
            g.builder.call(g.funcs['printf'], [fmt_ptr, expr_val])
402
        elif basic_ty.kind == 'RealType':
dbarbera's avatar
dbarbera committed
403
            fmt_val = get_string_cons('% .14E')
dbarbera's avatar
dbarbera committed
404
            fmt_ptr = g.builder.gep(fmt_val, [g.zero, g.zero])
dbarbera's avatar
dbarbera committed
405
            g.builder.call(g.funcs['printf'], [fmt_ptr, expr_val])
406
        elif basic_ty.kind == 'BooleanType':
dbarbera's avatar
dbarbera committed
407
            true_str_val = get_string_cons('TRUE')
dbarbera's avatar
dbarbera committed
408
            true_str_ptr = g.builder.gep(true_str_val, [g.zero, g.zero])
dbarbera's avatar
dbarbera committed
409
            false_str_val = get_string_cons('FALSE')
dbarbera's avatar
dbarbera committed
410
            false_str_ptr = g.builder.gep(false_str_val, [g.zero, g.zero])
411
            str_ptr = g.builder.select(expr_val, true_str_ptr, false_str_ptr)
dbarbera's avatar
dbarbera committed
412
            g.builder.call(g.funcs['printf'], [str_ptr])
dbarbera's avatar
dbarbera committed
413
414
415
416
417
        elif basic_ty.kind in ['StringType', 'OctetStringType']:
            fmt_val = get_string_cons('%s')
            fmt_ptr = g.builder.gep(fmt_val, [g.zero, g.zero])
            arr_ptr = g.builder.gep(expr_val, [g.zero, g.one])
            g.builder.call(g.funcs['printf'], [fmt_ptr, arr_ptr])
418
419
420
421
        else:
            raise NotImplementedError


dbarbera's avatar
dbarbera committed
422
def generate_writeln(params):
423
    ''' Generate the code for the writeln operator '''
dbarbera's avatar
dbarbera committed
424
    generate_write(params)
425
426

    zero = core.Constant.int(g.i32, 0)
dbarbera's avatar
dbarbera committed
427
    str_cons = get_string_cons('\n')
428
    str_ptr = g.builder.gep(str_cons, [zero, zero])
dbarbera's avatar
dbarbera committed
429
    g.builder.call(g.funcs['printf'], [str_ptr])
dbarbera's avatar
dbarbera committed
430
431


dbarbera's avatar
dbarbera committed
432
def generate_reset_timer(params):
dbarbera's avatar
dbarbera committed
433
    ''' Generate the code for the reset timer operator '''
dbarbera's avatar
dbarbera committed
434
    timer_id = params[0]
435
    reset_func_name = 'reset_%s' % timer_id.value[0]
dbarbera's avatar
dbarbera committed
436
437
438
    reset_func = g.funcs[reset_func_name.lower()]

    g.builder.call(reset_func, [])
dbarbera's avatar
dbarbera committed
439
440


dbarbera's avatar
dbarbera committed
441
def generate_set_timer(params):
dbarbera's avatar
dbarbera committed
442
    ''' Generate the code for the set timer operator '''
dbarbera's avatar
dbarbera committed
443
    timer_expr, timer_id = params
444
    set_func_name = 'set_%s' % timer_id.value[0]
dbarbera's avatar
dbarbera committed
445
446
447
448
449
450
451
452
    set_func = g.funcs[set_func_name.lower()]

    expr_val = expression(timer_expr)

    tmp_ptr = g.builder.alloca(expr_val.type)
    g.builder.store(expr_val, tmp_ptr)

    g.builder.call(set_func, [tmp_ptr])
Maxime Perrotin's avatar
Maxime Perrotin committed
453
454
455
456


@generate.register(ogAST.TaskAssign)
def _task_assign(task):
dbarbera's avatar
dbarbera committed
457
    ''' Generate the code of a list of assignments '''
458
459
    for expr in task.elems:
        expression(expr)
Maxime Perrotin's avatar
Maxime Perrotin committed
460
461
462
463
464


@generate.register(ogAST.TaskInformalText)
def _task_informal_text(task):
    ''' Generate comments for informal text '''
dbarbera's avatar
dbarbera committed
465
    pass
Maxime Perrotin's avatar
Maxime Perrotin committed
466
467
468
469


@generate.register(ogAST.TaskForLoop)
def _task_forloop(task):
dbarbera's avatar
dbarbera committed
470
    ''' Generate the code for a for loop '''
dbarbera's avatar
dbarbera committed
471
472
    for loop in task.elems:
        if loop['range']:
dbarbera's avatar
dbarbera committed
473
            generate_for_range(loop)
dbarbera's avatar
dbarbera committed
474
        else:
dbarbera's avatar
dbarbera committed
475
            generate_for_iterable(loop)
dbarbera's avatar
dbarbera committed
476
477


dbarbera's avatar
dbarbera committed
478
def generate_for_range(loop):
dbarbera's avatar
dbarbera committed
479
480
481
482
483
484
485
    ''' 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('')

dbarbera's avatar
dbarbera committed
486
    open_scope()
dbarbera's avatar
dbarbera committed
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517

    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'])
        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'])
    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)

dbarbera's avatar
dbarbera committed
518
    close_scope()
dbarbera's avatar
dbarbera committed
519
520


dbarbera's avatar
dbarbera committed
521
def generate_for_iterable(loop):
dbarbera's avatar
dbarbera committed
522
    ''' Generate the code for a for x in iterable loop'''
dbarbera's avatar
dbarbera committed
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
    seqof_asn1ty = find_basic_type(loop['list'].exprType)
    if seqof_asn1ty.Min != seqof_asn1ty.Min:
        raise NotImplementedError

    func = g.builder.basic_block.function

    # block for loading the value from the secuence
    # at the current index, incrementing the index afterwards
    load_block = func.append_basic_block('forin:load')
    # block for the body of the loop
    body_block = func.append_basic_block('forin:body')
    # block for checking if should loop again or terminate
    cond_block = func.append_basic_block('forin:cond')
    end_block = func.append_basic_block('')

    open_scope()

    idx_ptr = g.builder.alloca(g.i32)
    g.builder.store(core.Constant.int(g.i32, 0), idx_ptr)
    seqof_struct_ptr = expression(loop['list'])
    array_ptr = g.builder.gep(seqof_struct_ptr, [g.zero, g.zero])
    element_typ = array_ptr.type.pointee.element
    array_len_val = core.Constant.int(g.i32, array_ptr.type.pointee.count)

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

    g.builder.branch(load_block)

    # load block
    g.builder.position_at_end(load_block)
    idx_var = g.builder.load(idx_ptr)
555
556
557
558
    if element_typ.kind == core.TYPE_STRUCT:
        generate_assign(var_ptr, g.builder.gep(array_ptr, [g.zero, idx_var]))
    else:
        generate_assign(var_ptr, g.builder.load(g.builder.gep(array_ptr, [g.zero, idx_var])))
dbarbera's avatar
dbarbera committed
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
    g.builder.branch(body_block)

    # body block
    g.builder.position_at_end(body_block)
    generate(loop['transition'])
    g.builder.branch(cond_block)

    # cond block
    g.builder.position_at_end(cond_block)
    tmp_val = g.builder.add(idx_var, g.one)
    g.builder.store(tmp_val, idx_ptr)
    cond_val = g.builder.icmp(core.ICMP_SLT, tmp_val, array_len_val)
    g.builder.cbranch(cond_val, load_block, end_block)

    g.builder.position_at_end(end_block)

    close_scope()
Maxime Perrotin's avatar
Maxime Perrotin committed
576

dbarbera's avatar
dbarbera committed
577

dbarbera's avatar
dbarbera committed
578
579
580
@singledispatch
def reference(prim):
    ''' Generate a variable reference '''
dbarbera's avatar
flake8    
dbarbera committed
581
    raise TypeError('Unsupported reference: ' + str(prim))
dbarbera's avatar
dbarbera committed
582
583
584
585
586
587
588
589
590
591
592


@reference.register(ogAST.PrimVariable)
def _prim_var_reference(prim):
    ''' Generate a primary variable reference '''
    return g.scope.resolve(str(prim.value[0]))


@reference.register(ogAST.PrimPath)
def _prim_path_reference(prim):
    ''' Generate a primary path reference '''
593
    var_name = prim.value[0].lower()
dbarbera's avatar
dbarbera committed
594
595
596
597
598
    var_ptr = g.scope.resolve(str(var_name))

    if not prim.value:
        return var_ptr

dbarbera's avatar
dbarbera committed
599
600
601
602
    for elem in prim.value[1:]:
        if type(elem) == dict:
            if 'index' in elem:
                idx_val = expression(elem['index'][0])
603
                var_ptr = g.builder.gep(var_ptr, [g.zero, g.zero, idx_val])
dbarbera's avatar
dbarbera committed
604
605
606
607
            else:
                raise NotImplementedError
        else:
            var_ty = var_ptr.type
dbarbera's avatar
dbarbera committed
608
609
610
            if var_ty.pointee.name in g.structs:
                struct = g.structs[var_ty.pointee.name]
                field_idx_cons = core.Constant.int(g.i32, struct.idx(elem))
611
                field_ptr = g.builder.gep(var_ptr, [g.zero, field_idx_cons])
dbarbera's avatar
dbarbera committed
612
613
614
615
                var_ptr = field_ptr
            elif var_ty.pointee.name in g.unions:
                union = g.unions[var_ty.pointee.name]
                _, field_ty = union.kind(elem)
616
                field_ptr = g.builder.gep(var_ptr, [g.zero, g.one])
dbarbera's avatar
dbarbera committed
617
618
619
                var_ptr = g.builder.bitcast(field_ptr, core.Type.pointer(field_ty))
            else:
                raise NotImplementedError
dbarbera's avatar
dbarbera committed
620
621
    return var_ptr

Maxime Perrotin's avatar
Maxime Perrotin committed
622
623
624

@singledispatch
def expression(expr):
dbarbera's avatar
dbarbera committed
625
    ''' Generate the code for Expression-classes '''
Maxime Perrotin's avatar
Maxime Perrotin committed
626
627
628
629
    raise TypeError('Unsupported expression: ' + str(expr))


@expression.register(ogAST.PrimVariable)
Maxime Perrotin's avatar
Maxime Perrotin committed
630
def _primary_variable(prim):
dbarbera's avatar
dbarbera committed
631
632
633
    ''' Generate the code for a variable expression '''
    var_ptr = reference(prim)
    return var_ptr if is_struct_ptr(var_ptr) else g.builder.load(var_ptr)
Maxime Perrotin's avatar
Maxime Perrotin committed
634
635


Maxime Perrotin's avatar
Maxime Perrotin committed
636
@expression.register(ogAST.PrimPath)
dbarbera's avatar
dbarbera committed
637
def _prim_path(prim):
dbarbera's avatar
dbarbera committed
638
    ''' Generate the code for an of path expression '''
639
640
641
642
643
644
645
646
647
    specops_generators = {
        'length': generate_length,
        'present': generate_present,
        'abs': generate_abs,
        'fix': generate_fix,
        'float': generate_float,
        'power': generate_power
    }

dbarbera's avatar
dbarbera committed
648
649
650
651
652
653
654
    name = prim.value[0].lower()
    if name in specops_generators:
        generator = specops_generators[name]
        return generator(prim.value[1]['procParams'])

    return generate_access(prim)

655

dbarbera's avatar
dbarbera committed
656
657
def generate_access(prim):
    ''' Generate the code for an access '''
dbarbera's avatar
dbarbera committed
658
659
    var_ptr = reference(prim)
    return var_ptr if is_struct_ptr(var_ptr) else g.builder.load(var_ptr)
Maxime Perrotin's avatar
Maxime Perrotin committed
660
661


662
def generate_length(params):
dbarbera's avatar
dbarbera committed
663
    ''' Generate the code for the built-in length operation'''
dbarbera's avatar
dbarbera committed
664
    seq_ptr = reference(params[0])
dbarbera's avatar
dbarbera committed
665
666
    arr_ty = seq_ptr.type.pointee.elements[0]
    return core.Constant.int(g.i32, arr_ty.count)
667
668
669


def generate_present(params):
dbarbera's avatar
dbarbera committed
670
    ''' Generate the code for the built-in present operation'''
671
672
673
674
    raise NotImplementedError


def generate_abs(params):
dbarbera's avatar
dbarbera committed
675
    ''' Generate the code for the built-in abs operation'''
dbarbera's avatar
dbarbera committed
676
    expr_val = expression(params[0])
dbarbera's avatar
dbarbera committed
677

dbarbera's avatar
dbarbera committed
678
679
680
    if expr_val.type.kind == core.TYPE_INTEGER:
        expr_conv = g.builder.sitofp(expr_val, g.double)
        res_val = g.builder.call(g.funcs['fabs'], [expr_conv])
dbarbera's avatar
dbarbera committed
681
682
        return g.builder.fptosi(res_val, g.i32)
    else:
dbarbera's avatar
dbarbera committed
683
        return g.builder.call(g.funcs['fabs'], [expr_val])
684
685
686


def generate_fix(params):
dbarbera's avatar
dbarbera committed
687
    ''' Generate the code for the built-in fix operation'''
dbarbera's avatar
dbarbera committed
688
689
    expr_val = expression(params[0])
    return g.builder.fptosi(expr_val, g.i32)
690
691
692


def generate_float(params):
dbarbera's avatar
dbarbera committed
693
    ''' Generate the code for the built-in float operation'''
dbarbera's avatar
dbarbera committed
694
695
    expr_val = expression(params[0])
    return g.builder.sitofp(expr_val, g.double)
696
697
698


def generate_power(params):
dbarbera's avatar
dbarbera committed
699
    ''' Generate the code for the built-in power operation'''
700
701
702
703
704
705
706
707
708
709
710
    left_val = expression(params[0])
    right_val = expression(params[1])

    if left_val.type.kind == core.TYPE_INTEGER:
        left_conv = g.builder.sitofp(left_val, g.double)
        res_val = g.builder.call(g.funcs['powi'], [left_conv, right_val])
        return g.builder.fptosi(res_val, g.i32)
    else:
        return g.builder.call(g.funcs['powi'], [left_val, right_val])


Maxime Perrotin's avatar
Maxime Perrotin committed
711
712
713
714
715
716
717
718
719
720
721
722
@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
723
724
def _basic(expr):
    ''' Generate the code for an arithmetic of relational expression '''
725
726
    lefttmp = expression(expr.left)
    righttmp = expression(expr.right)
727

728
729
    if lefttmp.type.kind == core.TYPE_INTEGER:
        if expr.operand == '+':
730
            return g.builder.add(lefttmp, righttmp, 'addtmp')
731
        elif expr.operand == '-':
732
            return g.builder.sub(lefttmp, righttmp, 'subtmp')
733
        elif expr.operand == '*':
734
            return g.builder.mul(lefttmp, righttmp, 'multmp')
735
        elif expr.operand == '/':
736
            return g.builder.sdiv(lefttmp, righttmp, 'divtmp')
737
        elif expr.operand == 'mod':
738
            # l mod r == (((l rem r) + r) rem r)
739
740
741
            remtmp = g.builder.srem(lefttmp, righttmp)
            addtmp = g.builder.add(remtmp, righttmp)
            return g.builder.srem(addtmp, righttmp, 'modtmp')
742
        elif expr.operand == 'rem':
743
            return g.builder.srem(lefttmp, righttmp, 'remtmp')
744
        elif expr.operand == '<':
745
            return g.builder.icmp(core.ICMP_SLT, lefttmp, righttmp, 'lttmp')
746
        elif expr.operand == '<=':
747
            return g.builder.icmp(core.ICMP_SLE, lefttmp, righttmp, 'letmp')
748
        elif expr.operand == '=':
749
            return g.builder.icmp(core.ICMP_EQ, lefttmp, righttmp, 'eqtmp')
750
        elif expr.operand == '/=':
751
            return g.builder.icmp(core.ICMP_NE, lefttmp, righttmp, 'netmp')
752
        elif expr.operand == '>=':
753
            return g.builder.icmp(core.ICMP_SGE, lefttmp, righttmp, 'getmp')
754
        elif expr.operand == '>':
755
            return g.builder.icmp(core.ICMP_SGT, lefttmp, righttmp, 'gttmp')
756
757
758
759
        else:
            raise NotImplementedError
    elif lefttmp.type.kind == core.TYPE_DOUBLE:
        if expr.operand == '+':
760
            return g.builder.fadd(lefttmp, righttmp, 'addtmp')
761
        elif expr.operand == '-':
762
            return g.builder.fsub(lefttmp, righttmp, 'subtmp')
763
        elif expr.operand == '*':
764
            return g.builder.fmul(lefttmp, righttmp, 'multmp')
765
        elif expr.operand == '/':
766
            return g.builder.fdiv(lefttmp, righttmp, 'divtmp')
767
        elif expr.operand == '<':
768
            return g.builder.fcmp(core.FCMP_OLT, lefttmp, righttmp, 'lttmp')
769
        elif expr.operand == '<=':
770
            return g.builder.fcmp(core.FCMP_OLE, lefttmp, righttmp, 'letmp')
771
        elif expr.operand == '=':
772
            return g.builder.fcmp(core.FCMP_OEQ, lefttmp, righttmp, 'eqtmp')
773
        elif expr.operand == '/=':
774
            return g.builder.fcmp(core.FCMP_ONE, lefttmp, righttmp, 'netmp')
775
        elif expr.operand == '>=':
776
            return g.builder.fcmp(core.FCMP_OGE, lefttmp, righttmp, 'getmp')
777
        elif expr.operand == '>':
778
            return g.builder.fcmp(core.FCMP_OGT, lefttmp, righttmp, 'gttmp')
779
780
        else:
            raise NotImplementedError
781
    else:
782
        raise NotImplementedError
783

Maxime Perrotin's avatar
Maxime Perrotin committed
784

785
786
@expression.register(ogAST.ExprAssign)
def _assign(expr):
dbarbera's avatar
dbarbera committed
787
    ''' Generate the code for an assign expression '''
dbarbera's avatar
dbarbera committed
788
    generate_assign(reference(expr.left), expression(expr.right))
789

790

dbarbera's avatar
dbarbera committed
791
def generate_assign(left, right):
792
793
794
    ''' Generate code for an assign from two LLVM values'''
    # This is extracted as an standalone function because is used by
    # multiple generation rules
dbarbera's avatar
dbarbera committed
795
    if is_struct_ptr(left):
796
797
        size = core.Constant.sizeof(left.type.pointee)
        align = core.Constant.int(g.i32, 0)
798
        volatile = core.Constant.int(g.i1, 0)
799

800
801
        right_ptr = g.builder.bitcast(right, g.i8_ptr)
        left_ptr = g.builder.bitcast(left, g.i8_ptr)
802

dbarbera's avatar
dbarbera committed
803
        g.builder.call(g.funcs['memcpy'], [left_ptr, right_ptr, size, align, volatile])
804
    else:
805
        g.builder.store(right, left)
dbarbera's avatar
dbarbera committed
806

Maxime Perrotin's avatar
Maxime Perrotin committed
807

Maxime Perrotin's avatar
Maxime Perrotin committed
808
809
810
@expression.register(ogAST.ExprOr)
@expression.register(ogAST.ExprAnd)
@expression.register(ogAST.ExprXor)
dbarbera's avatar
dbarbera committed
811
812
def _logical(expr):
    ''' Generate the code for a logical expression '''
dbarbera's avatar
dbarbera committed
813
814
815
816
817
818
819
    lefttmp = expression(expr.left)
    righttmp = expression(expr.right)

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

dbarbera's avatar
dbarbera committed
820
821
822
    if expr.operand == 'and':
        return g.builder.and_(lefttmp, righttmp, 'andtmp')
    elif expr.operand == 'or':
823
        return g.builder.or_(lefttmp, righttmp, 'ortmp')
dbarbera's avatar
dbarbera committed
824
    else:
825
        return g.builder.xor(lefttmp, righttmp, 'xortmp')
dbarbera's avatar
dbarbera committed
826

Maxime Perrotin's avatar
Maxime Perrotin committed
827

Maxime Perrotin's avatar
Maxime Perrotin committed
828
@expression.register(ogAST.ExprAppend)
Maxime Perrotin's avatar
Maxime Perrotin committed
829
830
def _append(expr):
    ''' Generate code for the APPEND construct: a // b '''
831
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
832
833


Maxime Perrotin's avatar
Maxime Perrotin committed
834
@expression.register(ogAST.ExprIn)
Maxime Perrotin's avatar
Maxime Perrotin committed
835
def _expr_in(expr):
dbarbera's avatar
dbarbera committed
836
    ''' Generate the code for an in expression '''
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
    func = g.builder.basic_block.function

    next_block = func.append_basic_block('in:next')
    check_block = func.append_basic_block('in:check')
    end_block = func.append_basic_block('in:end')

    seq_asn1_ty = find_basic_type(expr.left.exprType)
    if seq_asn1_ty.Min != seq_asn1_ty.Max:
        # variable size sequence
        raise NotImplementedError

    idx_ptr = g.builder.alloca(g.i32)
    g.builder.store(core.Constant.int(g.i32, 0), idx_ptr)

    # TODO: Should be 'left' in 'right'?
    value_val = expression(expr.right)
    array_ptr = expression(expr.left)

    array_ty = array_ptr.type.pointee.elements[0]
    array_size = core.Constant.int(g.i32, array_ty.count)

    g.builder.branch(check_block)

    g.builder.position_at_end(check_block)
    idx_val = g.builder.load(idx_ptr)
862
    elem_val = g.builder.load(g.builder.gep(array_ptr, [g.zero, g.zero, idx_val]))
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
    if value_val.type.kind == core.TYPE_INTEGER:
        cond_val = g.builder.icmp(core.ICMP_EQ, value_val, elem_val)
    elif value_val.type.kind == core.TYPE_DOUBLE:
        cond_val = g.builder.fcmp(core.FCMP_OEQ, value_val, elem_val)
    else:
        raise NotImplementedError
    g.builder.cbranch(cond_val, end_block, next_block)

    g.builder.position_at_end(next_block)
    idx_tmp_val = g.builder.add(idx_val, core.Constant.int(g.i32, 1))
    g.builder.store(idx_tmp_val, idx_ptr)
    end_cond_val = g.builder.icmp(core.ICMP_SGE, idx_tmp_val, array_size)
    g.builder.cbranch(end_cond_val, end_block, check_block)

    g.builder.position_at_end(end_block)
    return cond_val
Maxime Perrotin's avatar
Maxime Perrotin committed
879
880


Maxime Perrotin's avatar
Maxime Perrotin committed
881
@expression.register(ogAST.PrimEnumeratedValue)
Maxime Perrotin's avatar
Maxime Perrotin committed
882
883
def _enumerated_value(primary):
    ''' Generate code for an enumerated value '''
dbarbera's avatar
dbarbera committed
884
885
886
    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
887
888


Maxime Perrotin's avatar
Maxime Perrotin committed
889
@expression.register(ogAST.PrimChoiceDeterminant)
Maxime Perrotin's avatar
Maxime Perrotin committed
890
891
def _choice_determinant(primary):
    ''' Generate code for a choice determinant (enumerated) '''
892
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
893
894


Maxime Perrotin's avatar
Maxime Perrotin committed
895
@expression.register(ogAST.PrimInteger)
896
897
def _integer(primary):
    ''' Generate code for a raw integer value  '''
898
    return core.Constant.int(g.i32, primary.value[0])
899
900


Maxime Perrotin's avatar
Maxime Perrotin committed
901
@expression.register(ogAST.PrimReal)
902
903
def _real(primary):
    ''' Generate code for a raw real value  '''
904
    return core.Constant.real(g.double, primary.value[0])
905
906


Maxime Perrotin's avatar
Maxime Perrotin committed
907
@expression.register(ogAST.PrimBoolean)
908
909
def _boolean(primary):
    ''' Generate code for a raw boolean value  '''
dbarbera's avatar
dbarbera committed
910
    if primary.value[0].lower() == 'true':
911
        return core.Constant.int(g.i1, 1)
dbarbera's avatar
dbarbera committed
912
    else:
913
        return core.Constant.int(g.i1, 0)
Maxime Perrotin's avatar
Maxime Perrotin committed
914
915


Maxime Perrotin's avatar
Maxime Perrotin committed
916
@expression.register(ogAST.PrimEmptyString)