LlvmGenerator.py 40.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
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

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)
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
159
    global g
    g = GlobalState(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
170
    # Initialize states enum
    for name in process.mapping.iterkeys():
        if not name.endswith('START'):
171
172
            cons = core.Constant.int(g.i32, len(g.states))
            g.states[name] = cons
173

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

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

dbarbera's avatar
dbarbera committed
186
187
188
    # Declare timer set/reset functions
    for timer in process.timers:
        # TODO: Should be uint?
189
190
        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
191

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

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

205
206
    # Generate internal procedures
    for proc in process.content.inner_procedures:
207
        generate(proc)
208

209
    # Generate process functions
dbarbera's avatar
dbarbera committed
210
211
    generate_runtr_func(process)
    generate_startup_func(process)
212

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

dbarbera's avatar
dbarbera committed
217
218
    g.module.verify()

dbarbera's avatar
dbarbera committed
219
    with open(g.name + '.ll', 'w') as ll_file:
dbarbera's avatar
dbarbera committed
220
        ll_file.write(str(g.module))
221
222


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

dbarbera's avatar
dbarbera committed
227
    open_scope()
228

229
230
231
232
233
    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
234
    g.builder = core.Builder.new(entry_block)
235
236

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

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

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

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

    # exit
dbarbera's avatar
dbarbera committed
264
265
    g.builder.position_at_end(exit_block)
    g.builder.ret_void()
266

dbarbera's avatar
dbarbera committed
267
268
269
270
271
272
273
274
275
    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
276
    close_scope()
277

278
279
280
281
    func.verify()
    return func


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

dbarbera's avatar
dbarbera committed
286
    open_scope()
287

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

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

297
298
    g.builder.call(g.funcs['run_transition'], [core.Constant.int(g.i32, 0)])
    g.builder.ret_void()
Maxime Perrotin's avatar
Maxime Perrotin committed
299

dbarbera's avatar
dbarbera committed
300
    close_scope()
301

302
303
    func.verify()
    return func
Maxime Perrotin's avatar
Maxime Perrotin committed
304
305


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

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

dbarbera's avatar
dbarbera committed
315
    open_scope()
316

317
318
    entry_block = func.append_basic_block('entry')
    exit_block = func.append_basic_block('exit')
319
    g.builder = core.Builder.new(entry_block)
320

321
    g_state_val = g.builder.load(g.global_scope.resolve('state'))
322
    switch = g.builder.switch(g_state_val, exit_block)
323

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

        # TODO: Nested states

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

343
        g.builder.ret_void()
344

345
346
    g.builder.position_at_end(exit_block)
    g.builder.ret_void()
347

dbarbera's avatar
dbarbera committed
348
    close_scope()
349

350
351
352
    func.verify()


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

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

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

        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
387
388


dbarbera's avatar
dbarbera committed
389
def generate_write(params):
dbarbera's avatar
dbarbera committed
390
    ''' Generate the code for the write operator '''
391
    zero = core.Constant.int(g.i32, 0)
392
393
394
    for param in params:
        basic_ty = find_basic_type(param.exprType)
        expr_val = expression(param)
395

396
        if basic_ty.kind in ['IntegerType', 'Integer32Type']:
dbarbera's avatar
dbarbera committed
397
            fmt_val = get_string_cons('% d')
398
            fmt_ptr = g.builder.gep(fmt_val, [zero, zero])
dbarbera's avatar
dbarbera committed
399
            g.builder.call(g.funcs['printf'], [fmt_ptr, expr_val])
400
        elif basic_ty.kind == 'RealType':
dbarbera's avatar
dbarbera committed
401
            fmt_val = get_string_cons('% .14E')
402
            fmt_ptr = g.builder.gep(fmt_val, [zero, zero])
dbarbera's avatar
dbarbera committed
403
            g.builder.call(g.funcs['printf'], [fmt_ptr, expr_val])
404
        elif basic_ty.kind == 'BooleanType':
dbarbera's avatar
dbarbera committed
405
            true_str_val = get_string_cons('TRUE')
406
            true_str_ptr = g.builder.gep(true_str_val, [zero, zero])
dbarbera's avatar
dbarbera committed
407
            false_str_val = get_string_cons('FALSE')
408
409
            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
410
            g.builder.call(g.funcs['printf'], [str_ptr])
dbarbera's avatar
dbarbera committed
411
412
        elif basic_ty.kind == 'StringType':
            expr_ptr = g.builder.gep(expr_val, [zero, zero])
dbarbera's avatar
dbarbera committed
413
            g.builder.call(g.funcs['printf'], [expr_ptr])
414
415
416
417
        else:
            raise NotImplementedError


dbarbera's avatar
dbarbera committed
418
def generate_writeln(params):
419
    ''' Generate the code for the writeln operator '''
dbarbera's avatar
dbarbera committed
420
    generate_write(params)
421
422

    zero = core.Constant.int(g.i32, 0)
dbarbera's avatar
dbarbera committed
423
    str_cons = get_string_cons('\n')
424
    str_ptr = g.builder.gep(str_cons, [zero, zero])
dbarbera's avatar
dbarbera committed
425
    g.builder.call(g.funcs['printf'], [str_ptr])
dbarbera's avatar
dbarbera committed
426
427


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

    g.builder.call(reset_func, [])
dbarbera's avatar
dbarbera committed
435
436


dbarbera's avatar
dbarbera committed
437
def generate_set_timer(params):
dbarbera's avatar
dbarbera committed
438
    ''' Generate the code for the set timer operator '''
dbarbera's avatar
dbarbera committed
439
    timer_expr, timer_id = params
440
    set_func_name = 'set_%s' % timer_id.value[0]
dbarbera's avatar
dbarbera committed
441
442
443
444
445
446
447
448
    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
449
450
451
452


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


@generate.register(ogAST.TaskInformalText)
def _task_informal_text(task):
    ''' Generate comments for informal text '''
dbarbera's avatar
dbarbera committed
461
    pass
Maxime Perrotin's avatar
Maxime Perrotin committed
462
463
464
465


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


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

    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
514
    close_scope()
dbarbera's avatar
dbarbera committed
515
516


dbarbera's avatar
dbarbera committed
517
def generate_for_iterable(loop):
dbarbera's avatar
dbarbera committed
518
    ''' Generate the code for a for x in iterable loop'''
dbarbera's avatar
dbarbera committed
519
520
521
522
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
555
556
557
558
559
560
561
562
563
564
565
566
567
568
    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)
    generate_assign(var_ptr, g.builder.load(g.builder.gep(array_ptr, [g.zero, idx_var])))
    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
569

dbarbera's avatar
dbarbera committed
570

dbarbera's avatar
dbarbera committed
571
572
573
@singledispatch
def reference(prim):
    ''' Generate a variable reference '''
dbarbera's avatar
flake8    
dbarbera committed
574
    raise TypeError('Unsupported reference: ' + str(prim))
dbarbera's avatar
dbarbera committed
575
576
577
578
579
580
581
582
583
584
585


@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 '''
586
    var_name = prim.value[0].lower()
dbarbera's avatar
dbarbera committed
587
588
589
590
591
592
593
    var_ptr = g.scope.resolve(str(var_name))

    if not prim.value:
        return var_ptr

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

dbarbera's avatar
dbarbera committed
594
595
596
597
598
599
600
601
602
    for elem in prim.value[1:]:
        if type(elem) == dict:
            if 'index' in elem:
                idx_val = expression(elem['index'][0])
                var_ptr = g.builder.gep(var_ptr, [zero_cons, zero_cons, idx_val])
            else:
                raise NotImplementedError
        else:
            var_ty = var_ptr.type
dbarbera's avatar
dbarbera committed
603
604
605
606
607
608
609
610
611
612
613
614
            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))
                field_ptr = g.builder.gep(var_ptr, [zero_cons, field_idx_cons])
                var_ptr = field_ptr
            elif var_ty.pointee.name in g.unions:
                union = g.unions[var_ty.pointee.name]
                _, field_ty = union.kind(elem)
                field_ptr = g.builder.gep(var_ptr, [zero_cons, core.Constant.int(g.i32, 1)])
                var_ptr = g.builder.bitcast(field_ptr, core.Type.pointer(field_ty))
            else:
                raise NotImplementedError
dbarbera's avatar
dbarbera committed
615
616
    return var_ptr

Maxime Perrotin's avatar
Maxime Perrotin committed
617
618
619

@singledispatch
def expression(expr):
dbarbera's avatar
dbarbera committed
620
    ''' Generate the code for Expression-classes '''
Maxime Perrotin's avatar
Maxime Perrotin committed
621
622
623
624
    raise TypeError('Unsupported expression: ' + str(expr))


@expression.register(ogAST.PrimVariable)
Maxime Perrotin's avatar
Maxime Perrotin committed
625
def _primary_variable(prim):
dbarbera's avatar
dbarbera committed
626
627
628
    ''' 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
629
630


Maxime Perrotin's avatar
Maxime Perrotin committed
631
@expression.register(ogAST.PrimPath)
dbarbera's avatar
dbarbera committed
632
def _prim_path(prim):
dbarbera's avatar
dbarbera committed
633
    ''' Generate the code for an of path expression '''
634
635
636
637
638
639
640
641
642
    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
643
644
645
646
647
648
649
    name = prim.value[0].lower()
    if name in specops_generators:
        generator = specops_generators[name]
        return generator(prim.value[1]['procParams'])

    return generate_access(prim)

650

dbarbera's avatar
dbarbera committed
651
652
def generate_access(prim):
    ''' Generate the code for an access '''
dbarbera's avatar
dbarbera committed
653
654
    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
655
656


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


def generate_present(params):
dbarbera's avatar
dbarbera committed
665
    ''' Generate the code for the built-in present operation'''
666
667
668
669
    raise NotImplementedError


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

dbarbera's avatar
dbarbera committed
673
674
675
    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
676
677
        return g.builder.fptosi(res_val, g.i32)
    else:
dbarbera's avatar
dbarbera committed
678
        return g.builder.call(g.funcs['fabs'], [expr_val])
679
680
681


def generate_fix(params):
dbarbera's avatar
dbarbera committed
682
    ''' Generate the code for the built-in fix operation'''
dbarbera's avatar
dbarbera committed
683
684
    expr_val = expression(params[0])
    return g.builder.fptosi(expr_val, g.i32)
685
686
687


def generate_float(params):
dbarbera's avatar
dbarbera committed
688
    ''' Generate the code for the built-in float operation'''
dbarbera's avatar
dbarbera committed
689
690
    expr_val = expression(params[0])
    return g.builder.sitofp(expr_val, g.double)
691
692
693


def generate_power(params):
dbarbera's avatar
dbarbera committed
694
    ''' Generate the code for the built-in power operation'''
695
696
697
698
699
700
701
702
703
704
705
    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
706
707
708
709
710
711
712
713
714
715
716
717
@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
718
719
def _basic(expr):
    ''' Generate the code for an arithmetic of relational expression '''
720
721
    lefttmp = expression(expr.left)
    righttmp = expression(expr.right)
722

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

Maxime Perrotin's avatar
Maxime Perrotin committed
779

780
781
@expression.register(ogAST.ExprAssign)
def _assign(expr):
dbarbera's avatar
dbarbera committed
782
    ''' Generate the code for an assign expression '''
dbarbera's avatar
dbarbera committed
783
    generate_assign(reference(expr.left), expression(expr.right))
784

785

dbarbera's avatar
dbarbera committed
786
def generate_assign(left, right):
787
788
789
    ''' 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
790
    if is_struct_ptr(left):
791
792
        size = core.Constant.sizeof(left.type.pointee)
        align = core.Constant.int(g.i32, 0)
793
        volatile = core.Constant.int(g.i1, 0)
794

795
796
        right_ptr = g.builder.bitcast(right, g.i8_ptr)
        left_ptr = g.builder.bitcast(left, g.i8_ptr)
797

dbarbera's avatar
dbarbera committed
798
        g.builder.call(g.funcs['memcpy'], [left_ptr, right_ptr, size, align, volatile])
799
    else:
800
        g.builder.store(right, left)
dbarbera's avatar
dbarbera committed
801

Maxime Perrotin's avatar
Maxime Perrotin committed
802

Maxime Perrotin's avatar
Maxime Perrotin committed
803
804
805
@expression.register(ogAST.ExprOr)
@expression.register(ogAST.ExprAnd)
@expression.register(ogAST.ExprXor)
dbarbera's avatar
dbarbera committed
806
807
def _logical(expr):
    ''' Generate the code for a logical expression '''
dbarbera's avatar
dbarbera committed
808
809
810
811
812
813
814
    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
815
816
817
    if expr.operand == 'and':
        return g.builder.and_(lefttmp, righttmp, 'andtmp')
    elif expr.operand == 'or':
818
        return g.builder.or_(lefttmp, righttmp, 'ortmp')
dbarbera's avatar
dbarbera committed
819
    else:
820
        return g.builder.xor(lefttmp, righttmp, 'xortmp')
dbarbera's avatar
dbarbera committed
821

Maxime Perrotin's avatar
Maxime Perrotin committed
822

Maxime Perrotin's avatar
Maxime Perrotin committed
823
@expression.register(ogAST.ExprAppend)
Maxime Perrotin's avatar
Maxime Perrotin committed
824
825
def _append(expr):
    ''' Generate code for the APPEND construct: a // b '''
826
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
827
828


Maxime Perrotin's avatar
Maxime Perrotin committed
829
@expression.register(ogAST.ExprIn)
Maxime Perrotin's avatar
Maxime Perrotin committed
830
def _expr_in(expr):
dbarbera's avatar
dbarbera committed
831
    ''' Generate the code for an in expression '''
832
833
834
835
836
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
862
863
864
865
866
867
868
869
870
871
872
873
874
    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)
    zero_cons = core.Constant.int(g.i32, 0)

    g.builder.branch(check_block)

    g.builder.position_at_end(check_block)
    idx_val = g.builder.load(idx_ptr)
    elem_val = g.builder.load(g.builder.gep(array_ptr, [zero_cons, zero_cons, idx_val]))
    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
875
876


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


Maxime Perrotin's avatar
Maxime Perrotin committed
885
@expression.register(ogAST.PrimChoiceDeterminant)
Maxime Perrotin's avatar
Maxime Perrotin committed
886
887
def _choice_determinant(primary):
    ''' Generate code for a choice determinant (enumerated) '''
888
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
889
890


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


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


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


Maxime Perrotin's avatar
Maxime Perrotin committed
912
@expression.register(ogAST.PrimEmptyString)
Maxime Perrotin's avatar
Maxime Perrotin committed
913
914
def _empty_string(primary):
    ''' Generate code for an empty SEQUENCE OF: {} '''
915
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
916
917


Maxime Perrotin's avatar
Maxime Perrotin committed
918
@expression.register(ogAST.PrimStringLiteral)
Maxime Perrotin's avatar
Maxime Perrotin committed
919
920
def _string_literal(primary):
    ''' Generate code for a string (Octet String) '''
dbarbera's avatar
dbarbera committed
921
    return get_string_cons(str(primary.value[1:-1]))
Maxime Perrotin's avatar
Maxime Perrotin committed
922
923


Maxime Perrotin's avatar
Maxime Perrotin committed
924
@expression.register(ogAST.PrimConstant)
Maxime Perrotin's avatar
Maxime Perrotin committed
925
926
def _constant(primary):
    ''' Generate code for a reference to an ASN.1 constant '''
927
    raise NotImplementedError
Maxime Perrotin's avatar
Maxime Perrotin committed
928
929


Maxime Perrotin's avatar
Maxime Perrotin committed
930
@expression.register(ogAST.PrimMantissaBaseExp)
Maxime Perrotin's avatar
Maxime Perrotin committed
931
932
def _mantissa_base_exp