Mercurial > lcfOS
changeset 274:ea93e0a7a31e
Move docs
| author | Windel Bouwman |
|---|---|
| date | Wed, 04 Sep 2013 17:35:06 +0200 |
| parents | 6b3a874edd6e |
| children | 6f2423df0675 |
| files | .hgignore doc/Makefile doc/compiler.rst doc/conf.py doc/design.rst doc/index.rst doc/readme_link.rst python/c3/codegenerator.py python/codegen.py python/codegenarm.py python/doc/Makefile python/doc/compiler.rst python/doc/conf.py python/doc/design.rst python/doc/index.rst python/doc/readme_link.rst python/flowgraph.py python/graph.py python/instructionselector.py python/ir/__init__.py python/ir/instruction.py python/ir/module.py python/irmach.py python/tcodegen.py python/testir.py python/transform.py python/trunner2.sh |
| diffstat | 27 files changed, 1013 insertions(+), 847 deletions(-) [+] |
line wrap: on
line diff
--- a/.hgignore Mon Sep 02 17:40:21 2013 +0200 +++ b/.hgignore Wed Sep 04 17:35:06 2013 +0200 @@ -8,5 +8,5 @@ cos/bootdisk.img cos/lcfosinitrd.img cos/kernel/kernel.map -python/doc/_build +doc/_build
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/Makefile Wed Sep 04 17:35:06 2013 +0200 @@ -0,0 +1,153 @@ +# Makefile for Sphinx documentation +# + +# You can set these variables from the command line. +SPHINXOPTS = +SPHINXBUILD = sphinx-build +PAPER = +BUILDDIR = _build + +# Internal variables. +PAPEROPT_a4 = -D latex_paper_size=a4 +PAPEROPT_letter = -D latex_paper_size=letter +ALLSPHINXOPTS = -d $(BUILDDIR)/doctrees $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) . +# the i18n builder cannot share the environment and doctrees with the others +I18NSPHINXOPTS = $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) . + +.PHONY: help clean html dirhtml singlehtml pickle json htmlhelp qthelp devhelp epub latex latexpdf text man changes linkcheck doctest gettext + +help: + @echo "Please use \`make <target>' where <target> is one of" + @echo " html to make standalone HTML files" + @echo " dirhtml to make HTML files named index.html in directories" + @echo " singlehtml to make a single large HTML file" + @echo " pickle to make pickle files" + @echo " json to make JSON files" + @echo " htmlhelp to make HTML files and a HTML help project" + @echo " qthelp to make HTML files and a qthelp project" + @echo " devhelp to make HTML files and a Devhelp project" + @echo " epub to make an epub" + @echo " latex to make LaTeX files, you can set PAPER=a4 or PAPER=letter" + @echo " latexpdf to make LaTeX files and run them through pdflatex" + @echo " text to make text files" + @echo " man to make manual pages" + @echo " texinfo to make Texinfo files" + @echo " info to make Texinfo files and run them through makeinfo" + @echo " gettext to make PO message catalogs" + @echo " changes to make an overview of all changed/added/deprecated items" + @echo " linkcheck to check all external links for integrity" + @echo " doctest to run all doctests embedded in the documentation (if enabled)" + +clean: + -rm -rf $(BUILDDIR)/* + +html: + $(SPHINXBUILD) -b html $(ALLSPHINXOPTS) $(BUILDDIR)/html + @echo + @echo "Build finished. The HTML pages are in $(BUILDDIR)/html." + +dirhtml: + $(SPHINXBUILD) -b dirhtml $(ALLSPHINXOPTS) $(BUILDDIR)/dirhtml + @echo + @echo "Build finished. The HTML pages are in $(BUILDDIR)/dirhtml." + +singlehtml: + $(SPHINXBUILD) -b singlehtml $(ALLSPHINXOPTS) $(BUILDDIR)/singlehtml + @echo + @echo "Build finished. The HTML page is in $(BUILDDIR)/singlehtml." + +pickle: + $(SPHINXBUILD) -b pickle $(ALLSPHINXOPTS) $(BUILDDIR)/pickle + @echo + @echo "Build finished; now you can process the pickle files." + +json: + $(SPHINXBUILD) -b json $(ALLSPHINXOPTS) $(BUILDDIR)/json + @echo + @echo "Build finished; now you can process the JSON files." + +htmlhelp: + $(SPHINXBUILD) -b htmlhelp $(ALLSPHINXOPTS) $(BUILDDIR)/htmlhelp + @echo + @echo "Build finished; now you can run HTML Help Workshop with the" \ + ".hhp project file in $(BUILDDIR)/htmlhelp." + +qthelp: + $(SPHINXBUILD) -b qthelp $(ALLSPHINXOPTS) $(BUILDDIR)/qthelp + @echo + @echo "Build finished; now you can run "qcollectiongenerator" with the" \ + ".qhcp project file in $(BUILDDIR)/qthelp, like this:" + @echo "# qcollectiongenerator $(BUILDDIR)/qthelp/lcfos.qhcp" + @echo "To view the help file:" + @echo "# assistant -collectionFile $(BUILDDIR)/qthelp/lcfos.qhc" + +devhelp: + $(SPHINXBUILD) -b devhelp $(ALLSPHINXOPTS) $(BUILDDIR)/devhelp + @echo + @echo "Build finished." + @echo "To view the help file:" + @echo "# mkdir -p $$HOME/.local/share/devhelp/lcfos" + @echo "# ln -s $(BUILDDIR)/devhelp $$HOME/.local/share/devhelp/lcfos" + @echo "# devhelp" + +epub: + $(SPHINXBUILD) -b epub $(ALLSPHINXOPTS) $(BUILDDIR)/epub + @echo + @echo "Build finished. The epub file is in $(BUILDDIR)/epub." + +latex: + $(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex + @echo + @echo "Build finished; the LaTeX files are in $(BUILDDIR)/latex." + @echo "Run \`make' in that directory to run these through (pdf)latex" \ + "(use \`make latexpdf' here to do that automatically)." + +latexpdf: + $(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex + @echo "Running LaTeX files through pdflatex..." + $(MAKE) -C $(BUILDDIR)/latex all-pdf + @echo "pdflatex finished; the PDF files are in $(BUILDDIR)/latex." + +text: + $(SPHINXBUILD) -b text $(ALLSPHINXOPTS) $(BUILDDIR)/text + @echo + @echo "Build finished. The text files are in $(BUILDDIR)/text." + +man: + $(SPHINXBUILD) -b man $(ALLSPHINXOPTS) $(BUILDDIR)/man + @echo + @echo "Build finished. The manual pages are in $(BUILDDIR)/man." + +texinfo: + $(SPHINXBUILD) -b texinfo $(ALLSPHINXOPTS) $(BUILDDIR)/texinfo + @echo + @echo "Build finished. The Texinfo files are in $(BUILDDIR)/texinfo." + @echo "Run \`make' in that directory to run these through makeinfo" \ + "(use \`make info' here to do that automatically)." + +info: + $(SPHINXBUILD) -b texinfo $(ALLSPHINXOPTS) $(BUILDDIR)/texinfo + @echo "Running Texinfo files through makeinfo..." + make -C $(BUILDDIR)/texinfo info + @echo "makeinfo finished; the Info files are in $(BUILDDIR)/texinfo." + +gettext: + $(SPHINXBUILD) -b gettext $(I18NSPHINXOPTS) $(BUILDDIR)/locale + @echo + @echo "Build finished. The message catalogs are in $(BUILDDIR)/locale." + +changes: + $(SPHINXBUILD) -b changes $(ALLSPHINXOPTS) $(BUILDDIR)/changes + @echo + @echo "The overview file is in $(BUILDDIR)/changes." + +linkcheck: + $(SPHINXBUILD) -b linkcheck $(ALLSPHINXOPTS) $(BUILDDIR)/linkcheck + @echo + @echo "Link check complete; look for any errors in the above output " \ + "or in $(BUILDDIR)/linkcheck/output.txt." + +doctest: + $(SPHINXBUILD) -b doctest $(ALLSPHINXOPTS) $(BUILDDIR)/doctest + @echo "Testing of doctests in the sources finished, look at the " \ + "results in $(BUILDDIR)/doctest/output.txt."
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/compiler.rst Wed Sep 04 17:35:06 2013 +0200 @@ -0,0 +1,110 @@ + + +Compiler +======== + +This chapter describes the design of the compiler. + + +Overview +-------- + +The compiler consists a frontend, mid-end and back-end. The frontend deals with +source file parsing and semantics checking. The mid-end performs optimizations. +This is optional. The back-end generates machine code. The front-end produces +intermediate code. This is a simple representation of the source. The back-end +can accept this kind of representation. This way the compiler is portable and +a front end can be constructed without having to do the rest. + +.. graphviz:: + + digraph x { + rankdir="LR" + 1 [label="c3 source file"] + 10 [label="c3 front end" ] + 11 [label="language X front end" ] + 20 [label="mid end" ] + 30 [label="back end for X86" ] + 31 [label="back end for ARM" ] + 40 [label="object file"] + 1 -> 10 + 10 -> 20 [label="IR-code"] + 11 -> 20 [label="IR-code"] + 20 -> 30 [label="IR-code"] + 20 -> 31 [label="IR-code"] + 30 -> 40 + } + +IR-code +------- +The IR-code is implemented in the ir package. + +.. autoclass:: ir.Module + +.. autoclass:: ir.Function + +.. autoclass:: ir.Block + +.. autoclass:: ir.Statement + +.. autoclass:: ir.Expression + +.. # .. inheritance-diagram:: ir.Statement + +C3 Front-end +------------ + +For the front-end a recursive descent parser is created for the c3 language. +This is a subset of the C language with some additional features. + +.. graphviz:: + + digraph c3 { + rankdir="LR" + 1 [label="source text"] + 10 [label="lexer" ] + 20 [label="parser" ] + 30 [label="semantic checks" ] + 40 [label="code generation"] + 99 [label="IR-code object"] + 1 -> 20 + 20 -> 30 + 30 -> 40 + 40 -> 99 + subgraph rel1 { + edge [dir=none] + 10 -> 20 + } + } + +.. autoclass:: c3.Builder + +.. autoclass:: c3.Parser + +.. autoclass:: c3.CodeGenerator + +Back-end +-------- + +The back-end is more complicated. There are several steps to be taken here. + +1. Instruction selection +2. register allocation +3. Peep hole optimization? +4. real code generation + +.. automodule:: codegenarm + :members: + +Instruction selection +~~~~~~~~~~~~~~~~~~~~~ + +The instruction selection phase takes care of scheduling and instruction +selection. The output of this phase is a one frame per function with a flat +list of abstract machine instructions. + +.. autoclass:: irmach.Frame + +.. autoclass:: irmach.AbstractInstruction + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/conf.py Wed Sep 04 17:35:06 2013 +0200 @@ -0,0 +1,244 @@ +#!/usr/bin/env python3 +# -*- coding: utf-8 -*- +# +# lcfos documentation build configuration file, created by +# sphinx-quickstart on Sat Aug 31 18:04:20 2013. +# +# This file is execfile()d with the current directory set to its containing dir. +# +# Note that not all possible configuration values are present in this +# autogenerated file. +# +# All configuration values have a default; values that are commented out +# serve to show the default. + +import sys, os + +# If extensions (or modules to document with autodoc) are in another directory, +# add these directories to sys.path here. If the directory is relative to the +# documentation root, use os.path.abspath to make it absolute, like shown here. +sys.path.insert(0, os.path.abspath('../python')) + +# -- General configuration ----------------------------------------------------- + +# If your documentation needs a minimal Sphinx version, state it here. +#needs_sphinx = '1.0' + +# Add any Sphinx extension module names here, as strings. They can be extensions +# coming with Sphinx (named 'sphinx.ext.*') or your custom ones. +extensions = ['sphinx.ext.graphviz', 'sphinx.ext.autodoc'] +# 'sphinx.ext.inheritance_diagram'] + +# Add any paths that contain templates here, relative to this directory. +templates_path = ['_templates'] + +# The suffix of source filenames. +source_suffix = '.rst' + +# The encoding of source files. +#source_encoding = 'utf-8-sig' + +# The master toctree document. +master_doc = 'index' + +# General information about the project. +project = 'lcfos' +copyright = '2013, Windel Bouwman' + +# The version info for the project you're documenting, acts as replacement for +# |version| and |release|, also used in various other places throughout the +# built documents. +# +# The short X.Y version. +version = '0.1' +# The full version, including alpha/beta/rc tags. +release = '0.1' + +# The language for content autogenerated by Sphinx. Refer to documentation +# for a list of supported languages. +#language = None + +# There are two options for replacing |today|: either, you set today to some +# non-false value, then it is used: +#today = '' +# Else, today_fmt is used as the format for a strftime call. +#today_fmt = '%B %d, %Y' + +# List of patterns, relative to source directory, that match files and +# directories to ignore when looking for source files. +exclude_patterns = ['_build'] + +# The reST default role (used for this markup: `text`) to use for all documents. +#default_role = None + +# If true, '()' will be appended to :func: etc. cross-reference text. +#add_function_parentheses = True + +# If true, the current module name will be prepended to all description +# unit titles (such as .. function::). +#add_module_names = True + +# If true, sectionauthor and moduleauthor directives will be shown in the +# output. They are ignored by default. +#show_authors = False + +# The name of the Pygments (syntax highlighting) style to use. +pygments_style = 'sphinx' + +# A list of ignored prefixes for module index sorting. +#modindex_common_prefix = [] + + +# -- Options for HTML output --------------------------------------------------- + +# The theme to use for HTML and HTML Help pages. See the documentation for +# a list of builtin themes. +html_theme = 'default' + +# Theme options are theme-specific and customize the look and feel of a theme +# further. For a list of options available for each theme, see the +# documentation. +#html_theme_options = {} + +# Add any paths that contain custom themes here, relative to this directory. +#html_theme_path = [] + +# The name for this set of Sphinx documents. If None, it defaults to +# "<project> v<release> documentation". +#html_title = None + +# A shorter title for the navigation bar. Default is the same as html_title. +#html_short_title = None + +# The name of an image file (relative to this directory) to place at the top +# of the sidebar. +#html_logo = None + +# The name of an image file (within the static path) to use as favicon of the +# docs. This file should be a Windows icon file (.ico) being 16x16 or 32x32 +# pixels large. +#html_favicon = None + +# Add any paths that contain custom static files (such as style sheets) here, +# relative to this directory. They are copied after the builtin static files, +# so a file named "default.css" will overwrite the builtin "default.css". +html_static_path = ['_static'] + +# If not '', a 'Last updated on:' timestamp is inserted at every page bottom, +# using the given strftime format. +#html_last_updated_fmt = '%b %d, %Y' + +# If true, SmartyPants will be used to convert quotes and dashes to +# typographically correct entities. +#html_use_smartypants = True + +# Custom sidebar templates, maps document names to template names. +#html_sidebars = {} + +# Additional templates that should be rendered to pages, maps page names to +# template names. +#html_additional_pages = {} + +# If false, no module index is generated. +#html_domain_indices = True + +# If false, no index is generated. +#html_use_index = True + +# If true, the index is split into individual pages for each letter. +#html_split_index = False + +# If true, links to the reST sources are added to the pages. +#html_show_sourcelink = True + +# If true, "Created using Sphinx" is shown in the HTML footer. Default is True. +#html_show_sphinx = True + +# If true, "(C) Copyright ..." is shown in the HTML footer. Default is True. +#html_show_copyright = True + +# If true, an OpenSearch description file will be output, and all pages will +# contain a <link> tag referring to it. The value of this option must be the +# base URL from which the finished HTML is served. +#html_use_opensearch = '' + +# This is the file name suffix for HTML files (e.g. ".xhtml"). +#html_file_suffix = None + +# Output file base name for HTML help builder. +htmlhelp_basename = 'lcfosdoc' + + +# -- Options for LaTeX output -------------------------------------------------- + +latex_elements = { +# The paper size ('letterpaper' or 'a4paper'). +#'papersize': 'letterpaper', + +# The font size ('10pt', '11pt' or '12pt'). +#'pointsize': '10pt', + +# Additional stuff for the LaTeX preamble. +#'preamble': '', +} + +# Grouping the document tree into LaTeX files. List of tuples +# (source start file, target name, title, author, documentclass [howto/manual]). +latex_documents = [ + ('index', 'lcfos.tex', 'lcfos Documentation', + 'Windel Bouwman', 'manual'), +] + +# The name of an image file (relative to this directory) to place at the top of +# the title page. +#latex_logo = None + +# For "manual" documents, if this is true, then toplevel headings are parts, +# not chapters. +#latex_use_parts = False + +# If true, show page references after internal links. +#latex_show_pagerefs = False + +# If true, show URL addresses after external links. +#latex_show_urls = False + +# Documents to append as an appendix to all manuals. +#latex_appendices = [] + +# If false, no module index is generated. +#latex_domain_indices = True + + +# -- Options for manual page output -------------------------------------------- + +# One entry per manual page. List of tuples +# (source start file, name, description, authors, manual section). +man_pages = [ + ('index', 'lcfos', 'lcfos Documentation', + ['Windel Bouwman'], 1) +] + +# If true, show URL addresses after external links. +#man_show_urls = False + + +# -- Options for Texinfo output ------------------------------------------------ + +# Grouping the document tree into Texinfo files. List of tuples +# (source start file, target name, title, author, +# dir menu entry, description, category) +texinfo_documents = [ + ('index', 'lcfos', 'lcfos Documentation', + 'Windel Bouwman', 'lcfos', 'One line description of project.', + 'Miscellaneous'), +] + +# Documents to append as an appendix to all manuals. +#texinfo_appendices = [] + +# If false, no module index is generated. +#texinfo_domain_indices = True + +# How to display URL addresses: 'footnote', 'no', or 'inline'. +#texinfo_show_urls = 'footnote'
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/design.rst Wed Sep 04 17:35:06 2013 +0200 @@ -0,0 +1,103 @@ +Design +====== + +OS +-- + +Processes / threads +~~~~~~~~~~~~~~~~~~~ + +Processes are completely seperated and fully pre-emptive. +This means a process can be unscheduled at any moment. + +Threads are co-operative. This means they yield control +voluntary. This means that mutexes and locks are not required. +This is done with the built-in language feature called tasks. + +If some heavy duty task must be performed, either way spawn +a new process, or yield frequently from this hard labour. + +tasks +~~~~~ + +Consider the following: + +.. code:: + + function int insanemath(int a) + { + while (a > 0) + { + a = a -1; + resume agent1; + } + return a - 1; + } + + task agent1() + { + start agent2; + } + + task agent2() + { + insanemath(55); + insanemath(44); + } + + task main() + { + start agent1; + join agent1; + } + + +Say to tasks are running in concurrent / parallel. + + + +Stack layout for tasks. +|| +|| +\/ ++---------+ +| return address +| locals +| ++------ +| return address +| locals +| ++--- + +Assembly code for the functions above: + +.. code:: + + .code + insanemath: + L1: + load r0, sp - 4 + cmp r0, 0 + jl L2 + dec r0 + store r0, sp - 4 + jmp L1 + L2: + ret + + agent1: + hlt? + + agent2: + hlt? + + main: + jmp agent1 + + .data + agent1_task: + dd 0 + agent2_task: + dd 0 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/index.rst Wed Sep 04 17:35:06 2013 +0200 @@ -0,0 +1,26 @@ +.. lcfos documentation master file, created by + sphinx-quickstart on Sat Aug 31 18:04:20 2013. + You can adapt this file completely to your liking, but it should at least + contain the root `toctree` directive. + +Welcome to lcfos's documentation! +================================= + +Contents: + +.. toctree:: + :maxdepth: 2 + + readme_link + design + compiler + + + +Indices and tables +================== + +* :ref:`genindex` +* :ref:`modindex` +* :ref:`search` +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/readme_link.rst Wed Sep 04 17:35:06 2013 +0200 @@ -0,0 +1,3 @@ + +.. include:: ../readme.rst +
--- a/python/c3/codegenerator.py Mon Sep 02 17:40:21 2013 +0200 +++ b/python/c3/codegenerator.py Wed Sep 04 17:35:06 2013 +0200 @@ -7,7 +7,14 @@ class CodeGenerator(ir.Builder): - """ Generates intermediate code from a package """ + """ + Generates intermediate (IR) code from a package. The entry function is + 'genModule'. The main task of this part is to rewrite complex control + structures, such as while and for loops into simple conditional + jump statements. Also complex conditional statements are simplified. + Such as 'and' and 'or' statements are rewritten in conditional jumps. + And structured datatypes are rewritten. + """ def __init__(self): self.logger = logging.getLogger('c3cgen') @@ -48,11 +55,14 @@ # TODO: handle parameters different if sym.isParameter: print('param', sym) - ir.Parameter(sym.name) - if sym.isLocal: + v = ir.Parameter(sym.name) + f.addParameter(v) + elif sym.isLocal: print('local', sym) - - v = self.newTemp() + v = self.newTemp() + else: + v = self.newTemp() + #raise NotImplementedError('{}'.format(sym)) # TODO: make this ssa here?? self.varMap[sym] = v @@ -93,6 +103,8 @@ re = self.genExprCode(code.expr) self.emit(ir.Move(self.fn.return_value, re)) self.emit(ir.Jump(self.fn.epiloog)) + b = self.newBlock() + self.setBlock(b) else: self.builder.addIns(ir.Return()) elif type(code) is astnodes.WhileStatement:
--- a/python/codegen.py Mon Sep 02 17:40:21 2013 +0200 +++ b/python/codegen.py Wed Sep 04 17:35:06 2013 +0200 @@ -20,7 +20,7 @@ print(gvar) print('TODO') for f in ircode.Functions: - for bb in f.BasicBlocks: + for bb in f.Blocks: for ins in bb.Instructions: # Instruction selection: #mi = self.tryMap(ins)
--- a/python/codegenarm.py Mon Sep 02 17:40:21 2013 +0200 +++ b/python/codegenarm.py Wed Sep 04 17:35:06 2013 +0200 @@ -8,8 +8,19 @@ from instructionselector import InstructionSelector import irmach + +class ArmFrame(irmach.Frame): + """ + Arm specific frame for functions. + """ + pass + + class ArmInstructionSelector(InstructionSelector): """ Instruction selector for the arm architecture """ + def newFrame(self, name): + return ArmFrame(name) + def munchExpr(self, e): if isinstance(e, ir.Alloc): return 0 @@ -58,9 +69,15 @@ return d elif isinstance(e, ir.Temp): return self.getTempReg(e) + elif isinstance(e, ir.Parameter): + offset = 1337 # TODO: determine offset in frame?? + d = self.newTmp() + self.emit('ldr %d0, [sp + {}]'.format(offset), dst=[d]) + return d elif isinstance(e, ir.Call): args = [self.munchExpr(a) for a in e.arguments] - self.emit('add sp, sp, 22') + frame_size = 222 # TODO: determine frame size? + self.emit('add sp, sp, {}'.format(frame_size)) # TODO: save frame for a in args: self.emit('push %s0', src=[a]) @@ -73,28 +90,31 @@ if isinstance(s, ir.Move) and isinstance(s.dst, ir.Mem): memloc = self.munchExpr(s.dst.e) val = self.munchExpr(s.src) - self.emit('str [%s0], %s1') + self.emit('str [%s0], %s1', src=[memloc, val]) elif isinstance(s, ir.Move) and isinstance(s.dst, ir.Temp): val = self.munchExpr(s.src) dreg = self.getTempReg(s.dst) self.emit('mov %d0, %s0', dst=[dreg], src=[val]) elif isinstance(s, ir.Jump): tgt = self.targets[s.target] - self.emit('jmp {}'.format(s), jumps=[tgt]) + self.emit('jmp %l0', jumps=[tgt]) elif isinstance(s, ir.CJump): a = self.munchExpr(s.a) b = self.munchExpr(s.b) self.emit('cmp %s0, %s1', src=[a, b]) ntgt = self.targets[s.lab_no] ytgt = self.targets[s.lab_yes] - jmp_ins = self.makeIns('jmp {}'.format(s.lab_no), jumps=[ntgt]) + jmp_ins = self.makeIns('jmp %l0', jumps=[ntgt]) # Explicitely add fallthrough: - self.emit('jeq {}'.format(s.lab_yes), jumps=[ytgt, jmp_ins]) + self.emit('jeq %l0', jumps=[ytgt, jmp_ins]) self.emit2(jmp_ins) + elif isinstance(s, ir.Terminator): + pass else: - raise NotImplementedError('--> {}'.format(s)) + raise NotImplementedError('Stmt --> {}'.format(s)) +# TODO: this class could be target independent: class ArmCodeGenerator: def __init__(self, outs): # TODO: schedule traces in better order. @@ -116,31 +136,42 @@ defTemps = set(defTemps) useTemps = set(useTemps) unUsed = defTemps - useTemps - #print('Unused:', unUsed) + print('Unused:', unUsed) for uu in unUsed: inslist.append(irmach.AbstractInstruction('use %s0', src=[uu])) #print(useTemps) - def generate(self, ircode, cfg_file=None, ig_file=None): - ir2 = self.ins_sel.munchProgram(ircode) - self.useUnused(ir2) - cfg = flowgraph.FlowGraph(ir2) - if cfg_file: - cfg.to_dot(cfg_file) + def allocFrame(self, f): + """ + Do register allocation for a single stack frame. + """ + ilist = f.instructions + self.useUnused(ilist) + cfg = flowgraph.FlowGraph(ilist) + f.cfg = cfg ig = registerallocator.InterferenceGraph(cfg) - if ig_file: - ig.to_dot(ig_file) + f.ig = ig regs = ['r0', 'r1', 'r2', 'r3', 'r4', 'r5', 'r6', 'r7'] ra = registerallocator.RegisterAllocator() regMap = ra.registerAllocate(ig, regs) #print(regMap) # Use allocated registers: - for i in ir2: + for i in ilist: i.src = tuple(regMap[t] for t in i.src) i.dst = tuple(regMap[t] for t in i.dst) #print(i) - return ir2 + + def generate(self, ircode): + # Munch program into a bunch of frames. One frame per function. + # Each frame has a flat list of abstract instructions. + frames = self.ins_sel.munchProgram(ircode) + self.frames = frames + for f in frames: + self.allocFrame(f) + + # TODO: Peep-hole here + # TODO: Materialize assembly + return frames -
--- a/python/doc/Makefile Mon Sep 02 17:40:21 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,153 +0,0 @@ -# Makefile for Sphinx documentation -# - -# You can set these variables from the command line. -SPHINXOPTS = -SPHINXBUILD = sphinx-build -PAPER = -BUILDDIR = _build - -# Internal variables. -PAPEROPT_a4 = -D latex_paper_size=a4 -PAPEROPT_letter = -D latex_paper_size=letter -ALLSPHINXOPTS = -d $(BUILDDIR)/doctrees $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) . -# the i18n builder cannot share the environment and doctrees with the others -I18NSPHINXOPTS = $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) . - -.PHONY: help clean html dirhtml singlehtml pickle json htmlhelp qthelp devhelp epub latex latexpdf text man changes linkcheck doctest gettext - -help: - @echo "Please use \`make <target>' where <target> is one of" - @echo " html to make standalone HTML files" - @echo " dirhtml to make HTML files named index.html in directories" - @echo " singlehtml to make a single large HTML file" - @echo " pickle to make pickle files" - @echo " json to make JSON files" - @echo " htmlhelp to make HTML files and a HTML help project" - @echo " qthelp to make HTML files and a qthelp project" - @echo " devhelp to make HTML files and a Devhelp project" - @echo " epub to make an epub" - @echo " latex to make LaTeX files, you can set PAPER=a4 or PAPER=letter" - @echo " latexpdf to make LaTeX files and run them through pdflatex" - @echo " text to make text files" - @echo " man to make manual pages" - @echo " texinfo to make Texinfo files" - @echo " info to make Texinfo files and run them through makeinfo" - @echo " gettext to make PO message catalogs" - @echo " changes to make an overview of all changed/added/deprecated items" - @echo " linkcheck to check all external links for integrity" - @echo " doctest to run all doctests embedded in the documentation (if enabled)" - -clean: - -rm -rf $(BUILDDIR)/* - -html: - $(SPHINXBUILD) -b html $(ALLSPHINXOPTS) $(BUILDDIR)/html - @echo - @echo "Build finished. The HTML pages are in $(BUILDDIR)/html." - -dirhtml: - $(SPHINXBUILD) -b dirhtml $(ALLSPHINXOPTS) $(BUILDDIR)/dirhtml - @echo - @echo "Build finished. The HTML pages are in $(BUILDDIR)/dirhtml." - -singlehtml: - $(SPHINXBUILD) -b singlehtml $(ALLSPHINXOPTS) $(BUILDDIR)/singlehtml - @echo - @echo "Build finished. The HTML page is in $(BUILDDIR)/singlehtml." - -pickle: - $(SPHINXBUILD) -b pickle $(ALLSPHINXOPTS) $(BUILDDIR)/pickle - @echo - @echo "Build finished; now you can process the pickle files." - -json: - $(SPHINXBUILD) -b json $(ALLSPHINXOPTS) $(BUILDDIR)/json - @echo - @echo "Build finished; now you can process the JSON files." - -htmlhelp: - $(SPHINXBUILD) -b htmlhelp $(ALLSPHINXOPTS) $(BUILDDIR)/htmlhelp - @echo - @echo "Build finished; now you can run HTML Help Workshop with the" \ - ".hhp project file in $(BUILDDIR)/htmlhelp." - -qthelp: - $(SPHINXBUILD) -b qthelp $(ALLSPHINXOPTS) $(BUILDDIR)/qthelp - @echo - @echo "Build finished; now you can run "qcollectiongenerator" with the" \ - ".qhcp project file in $(BUILDDIR)/qthelp, like this:" - @echo "# qcollectiongenerator $(BUILDDIR)/qthelp/lcfos.qhcp" - @echo "To view the help file:" - @echo "# assistant -collectionFile $(BUILDDIR)/qthelp/lcfos.qhc" - -devhelp: - $(SPHINXBUILD) -b devhelp $(ALLSPHINXOPTS) $(BUILDDIR)/devhelp - @echo - @echo "Build finished." - @echo "To view the help file:" - @echo "# mkdir -p $$HOME/.local/share/devhelp/lcfos" - @echo "# ln -s $(BUILDDIR)/devhelp $$HOME/.local/share/devhelp/lcfos" - @echo "# devhelp" - -epub: - $(SPHINXBUILD) -b epub $(ALLSPHINXOPTS) $(BUILDDIR)/epub - @echo - @echo "Build finished. The epub file is in $(BUILDDIR)/epub." - -latex: - $(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex - @echo - @echo "Build finished; the LaTeX files are in $(BUILDDIR)/latex." - @echo "Run \`make' in that directory to run these through (pdf)latex" \ - "(use \`make latexpdf' here to do that automatically)." - -latexpdf: - $(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex - @echo "Running LaTeX files through pdflatex..." - $(MAKE) -C $(BUILDDIR)/latex all-pdf - @echo "pdflatex finished; the PDF files are in $(BUILDDIR)/latex." - -text: - $(SPHINXBUILD) -b text $(ALLSPHINXOPTS) $(BUILDDIR)/text - @echo - @echo "Build finished. The text files are in $(BUILDDIR)/text." - -man: - $(SPHINXBUILD) -b man $(ALLSPHINXOPTS) $(BUILDDIR)/man - @echo - @echo "Build finished. The manual pages are in $(BUILDDIR)/man." - -texinfo: - $(SPHINXBUILD) -b texinfo $(ALLSPHINXOPTS) $(BUILDDIR)/texinfo - @echo - @echo "Build finished. The Texinfo files are in $(BUILDDIR)/texinfo." - @echo "Run \`make' in that directory to run these through makeinfo" \ - "(use \`make info' here to do that automatically)." - -info: - $(SPHINXBUILD) -b texinfo $(ALLSPHINXOPTS) $(BUILDDIR)/texinfo - @echo "Running Texinfo files through makeinfo..." - make -C $(BUILDDIR)/texinfo info - @echo "makeinfo finished; the Info files are in $(BUILDDIR)/texinfo." - -gettext: - $(SPHINXBUILD) -b gettext $(I18NSPHINXOPTS) $(BUILDDIR)/locale - @echo - @echo "Build finished. The message catalogs are in $(BUILDDIR)/locale." - -changes: - $(SPHINXBUILD) -b changes $(ALLSPHINXOPTS) $(BUILDDIR)/changes - @echo - @echo "The overview file is in $(BUILDDIR)/changes." - -linkcheck: - $(SPHINXBUILD) -b linkcheck $(ALLSPHINXOPTS) $(BUILDDIR)/linkcheck - @echo - @echo "Link check complete; look for any errors in the above output " \ - "or in $(BUILDDIR)/linkcheck/output.txt." - -doctest: - $(SPHINXBUILD) -b doctest $(ALLSPHINXOPTS) $(BUILDDIR)/doctest - @echo "Testing of doctests in the sources finished, look at the " \ - "results in $(BUILDDIR)/doctest/output.txt."
--- a/python/doc/compiler.rst Mon Sep 02 17:40:21 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,91 +0,0 @@ - - -Compiler -======== - -This chapter describes the design of the compiler. - - -Overview --------- - -The compiler consists a frontend, mid-end and back-end. The frontend deals with -source file parsing and semantics checking. The mid-end performs optimizations. -This is optional. The back-end generates machine code. The front-end produces -intermediate code. This is a simple representation of the source. The back-end -can accept this kind of representation. This way the compiler is portable and -a front end can be constructed without having to do the rest. - -.. graphviz:: - - - digraph x { - rankdir="LR" - 1 [label="c3 source file"] - 10 [label="c3 front end" ] - 11 [label="language X front end" ] - 20 [label="mid end" ] - 30 [label="back end for X86" ] - 31 [label="back end for ARM" ] - 40 [label="object file"] - 1 -> 10 - 10 -> 20 [label="IR-code"] - 11 -> 20 [label="IR-code"] - 20 -> 30 [label="IR-code"] - 20 -> 31 [label="IR-code"] - 30 -> 40 - } - -IR-code -------- -The IR-code is implemented in the ir package. - -.. autoclass:: ir.Module - :members: - -.. autoclass:: ir.Function - :members: - -.. autoclass:: ir.Block - :members: - -.. autoclass:: ir.Statement - :members: - -.. autoclass:: ir.Expression - :members: - -.. # .. inheritance-diagram:: ir.Statement - -Front-end ---------- - -For the front-end a recursive descent parser is created for the c3 language. -This is a subset of the C language with some additional features. - -.. automodule:: c3 - :members: - :undoc-members: - -.. autoclass:: c3.Parser - :members: - -.. autoclass:: c3.Builder - :members: - -.. autoclass:: c3.CodeGenerator - :members: - -Back-end --------- - -The back-end is more complicated. There are several steps to be taken here. - -1. Instruction selection -2. register allocation -3. Peep hole optimization? -4. real code generation - -.. automodule:: codegenarm - :members: -
--- a/python/doc/conf.py Mon Sep 02 17:40:21 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,244 +0,0 @@ -#!/usr/bin/env python3 -# -*- coding: utf-8 -*- -# -# lcfos documentation build configuration file, created by -# sphinx-quickstart on Sat Aug 31 18:04:20 2013. -# -# This file is execfile()d with the current directory set to its containing dir. -# -# Note that not all possible configuration values are present in this -# autogenerated file. -# -# All configuration values have a default; values that are commented out -# serve to show the default. - -import sys, os - -# If extensions (or modules to document with autodoc) are in another directory, -# add these directories to sys.path here. If the directory is relative to the -# documentation root, use os.path.abspath to make it absolute, like shown here. -sys.path.insert(0, os.path.abspath('..')) - -# -- General configuration ----------------------------------------------------- - -# If your documentation needs a minimal Sphinx version, state it here. -#needs_sphinx = '1.0' - -# Add any Sphinx extension module names here, as strings. They can be extensions -# coming with Sphinx (named 'sphinx.ext.*') or your custom ones. -extensions = ['sphinx.ext.graphviz', 'sphinx.ext.autodoc'] -# 'sphinx.ext.inheritance_diagram'] - -# Add any paths that contain templates here, relative to this directory. -templates_path = ['_templates'] - -# The suffix of source filenames. -source_suffix = '.rst' - -# The encoding of source files. -#source_encoding = 'utf-8-sig' - -# The master toctree document. -master_doc = 'index' - -# General information about the project. -project = 'lcfos' -copyright = '2013, Windel Bouwman' - -# The version info for the project you're documenting, acts as replacement for -# |version| and |release|, also used in various other places throughout the -# built documents. -# -# The short X.Y version. -version = '0.1' -# The full version, including alpha/beta/rc tags. -release = '0.1' - -# The language for content autogenerated by Sphinx. Refer to documentation -# for a list of supported languages. -#language = None - -# There are two options for replacing |today|: either, you set today to some -# non-false value, then it is used: -#today = '' -# Else, today_fmt is used as the format for a strftime call. -#today_fmt = '%B %d, %Y' - -# List of patterns, relative to source directory, that match files and -# directories to ignore when looking for source files. -exclude_patterns = ['_build'] - -# The reST default role (used for this markup: `text`) to use for all documents. -#default_role = None - -# If true, '()' will be appended to :func: etc. cross-reference text. -#add_function_parentheses = True - -# If true, the current module name will be prepended to all description -# unit titles (such as .. function::). -#add_module_names = True - -# If true, sectionauthor and moduleauthor directives will be shown in the -# output. They are ignored by default. -#show_authors = False - -# The name of the Pygments (syntax highlighting) style to use. -pygments_style = 'sphinx' - -# A list of ignored prefixes for module index sorting. -#modindex_common_prefix = [] - - -# -- Options for HTML output --------------------------------------------------- - -# The theme to use for HTML and HTML Help pages. See the documentation for -# a list of builtin themes. -html_theme = 'default' - -# Theme options are theme-specific and customize the look and feel of a theme -# further. For a list of options available for each theme, see the -# documentation. -#html_theme_options = {} - -# Add any paths that contain custom themes here, relative to this directory. -#html_theme_path = [] - -# The name for this set of Sphinx documents. If None, it defaults to -# "<project> v<release> documentation". -#html_title = None - -# A shorter title for the navigation bar. Default is the same as html_title. -#html_short_title = None - -# The name of an image file (relative to this directory) to place at the top -# of the sidebar. -#html_logo = None - -# The name of an image file (within the static path) to use as favicon of the -# docs. This file should be a Windows icon file (.ico) being 16x16 or 32x32 -# pixels large. -#html_favicon = None - -# Add any paths that contain custom static files (such as style sheets) here, -# relative to this directory. They are copied after the builtin static files, -# so a file named "default.css" will overwrite the builtin "default.css". -html_static_path = ['_static'] - -# If not '', a 'Last updated on:' timestamp is inserted at every page bottom, -# using the given strftime format. -#html_last_updated_fmt = '%b %d, %Y' - -# If true, SmartyPants will be used to convert quotes and dashes to -# typographically correct entities. -#html_use_smartypants = True - -# Custom sidebar templates, maps document names to template names. -#html_sidebars = {} - -# Additional templates that should be rendered to pages, maps page names to -# template names. -#html_additional_pages = {} - -# If false, no module index is generated. -#html_domain_indices = True - -# If false, no index is generated. -#html_use_index = True - -# If true, the index is split into individual pages for each letter. -#html_split_index = False - -# If true, links to the reST sources are added to the pages. -#html_show_sourcelink = True - -# If true, "Created using Sphinx" is shown in the HTML footer. Default is True. -#html_show_sphinx = True - -# If true, "(C) Copyright ..." is shown in the HTML footer. Default is True. -#html_show_copyright = True - -# If true, an OpenSearch description file will be output, and all pages will -# contain a <link> tag referring to it. The value of this option must be the -# base URL from which the finished HTML is served. -#html_use_opensearch = '' - -# This is the file name suffix for HTML files (e.g. ".xhtml"). -#html_file_suffix = None - -# Output file base name for HTML help builder. -htmlhelp_basename = 'lcfosdoc' - - -# -- Options for LaTeX output -------------------------------------------------- - -latex_elements = { -# The paper size ('letterpaper' or 'a4paper'). -#'papersize': 'letterpaper', - -# The font size ('10pt', '11pt' or '12pt'). -#'pointsize': '10pt', - -# Additional stuff for the LaTeX preamble. -#'preamble': '', -} - -# Grouping the document tree into LaTeX files. List of tuples -# (source start file, target name, title, author, documentclass [howto/manual]). -latex_documents = [ - ('index', 'lcfos.tex', 'lcfos Documentation', - 'Windel Bouwman', 'manual'), -] - -# The name of an image file (relative to this directory) to place at the top of -# the title page. -#latex_logo = None - -# For "manual" documents, if this is true, then toplevel headings are parts, -# not chapters. -#latex_use_parts = False - -# If true, show page references after internal links. -#latex_show_pagerefs = False - -# If true, show URL addresses after external links. -#latex_show_urls = False - -# Documents to append as an appendix to all manuals. -#latex_appendices = [] - -# If false, no module index is generated. -#latex_domain_indices = True - - -# -- Options for manual page output -------------------------------------------- - -# One entry per manual page. List of tuples -# (source start file, name, description, authors, manual section). -man_pages = [ - ('index', 'lcfos', 'lcfos Documentation', - ['Windel Bouwman'], 1) -] - -# If true, show URL addresses after external links. -#man_show_urls = False - - -# -- Options for Texinfo output ------------------------------------------------ - -# Grouping the document tree into Texinfo files. List of tuples -# (source start file, target name, title, author, -# dir menu entry, description, category) -texinfo_documents = [ - ('index', 'lcfos', 'lcfos Documentation', - 'Windel Bouwman', 'lcfos', 'One line description of project.', - 'Miscellaneous'), -] - -# Documents to append as an appendix to all manuals. -#texinfo_appendices = [] - -# If false, no module index is generated. -#texinfo_domain_indices = True - -# How to display URL addresses: 'footnote', 'no', or 'inline'. -#texinfo_show_urls = 'footnote'
--- a/python/doc/design.rst Mon Sep 02 17:40:21 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,103 +0,0 @@ -Design -====== - -OS --- - -Processes / threads -~~~~~~~~~~~~~~~~~~~ - -Processes are completely seperated and fully pre-emptive. -This means a process can be unscheduled at any moment. - -Threads are co-operative. This means they yield control -voluntary. This means that mutexes and locks are not required. -This is done with the built-in language feature called tasks. - -If some heavy duty task must be performed, either way spawn -a new process, or yield frequently from this hard labour. - -tasks -~~~~~ - -Consider the following: - -.. code:: - - function int insanemath(int a) - { - while (a > 0) - { - a = a -1; - resume agent1; - } - return a - 1; - } - - task agent1() - { - start agent2; - } - - task agent2() - { - insanemath(55); - insanemath(44); - } - - task main() - { - start agent1; - join agent1; - } - - -Say to tasks are running in concurrent / parallel. - - - -Stack layout for tasks. -|| -|| -\/ -+---------+ -| return address -| locals -| -+------ -| return address -| locals -| -+--- - -Assembly code for the functions above: - -.. code:: - - .code - insanemath: - L1: - load r0, sp - 4 - cmp r0, 0 - jl L2 - dec r0 - store r0, sp - 4 - jmp L1 - L2: - ret - - agent1: - hlt? - - agent2: - hlt? - - main: - jmp agent1 - - .data - agent1_task: - dd 0 - agent2_task: - dd 0 -
--- a/python/doc/index.rst Mon Sep 02 17:40:21 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,26 +0,0 @@ -.. lcfos documentation master file, created by - sphinx-quickstart on Sat Aug 31 18:04:20 2013. - You can adapt this file completely to your liking, but it should at least - contain the root `toctree` directive. - -Welcome to lcfos's documentation! -================================= - -Contents: - -.. toctree:: - :maxdepth: 2 - - readme_link - design - compiler - - - -Indices and tables -================== - -* :ref:`genindex` -* :ref:`modindex` -* :ref:`search` -
--- a/python/doc/readme_link.rst Mon Sep 02 17:40:21 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,4 +0,0 @@ - - - -.. include:: ../../readme.rst
--- a/python/flowgraph.py Mon Sep 02 17:40:21 2013 +0200 +++ b/python/flowgraph.py Wed Sep 04 17:35:06 2013 +0200 @@ -13,7 +13,12 @@ self.live_out = set() def __repr__(self): - return '{}, use={}, def={}'.format(self.ins, self.uses, self.defs) + r = '{}'.format(self.ins) + if self.uses: + r += ' uses:' + ', '.join(str(u) for u in self.uses) + if self.defs: + r += ' defs:' + ', '.join(str(d) for d in self.defs) + return r class FlowGraph(graph.Graph):
--- a/python/graph.py Mon Sep 02 17:40:21 2013 +0200 +++ b/python/graph.py Wed Sep 04 17:35:06 2013 +0200 @@ -26,12 +26,12 @@ def to_dot(self, f): """ Generate graphviz dot representation """ - print('digraph G {', file=f) + #print('digraph G {', file=f) for node in self.nodes: print('{} [label="{}" shape=box3d];'.format(id(node), node), file=f) for n, m in self.edges: print('{} -> {};'.format(id(n), id(m)), file=f) - print('}', file=f) + #print('}', file=f) class Node:
--- a/python/instructionselector.py Mon Sep 02 17:40:21 2013 +0200 +++ b/python/instructionselector.py Wed Sep 04 17:35:06 2013 +0200 @@ -25,20 +25,23 @@ # Entry point for instruction selection self.temps = genTemps() assert isinstance(p, ir.Module) - self.result = [] + self.frames = [] self.targets = {} self.tempMap = {} # Mapping from temporaries to infinite register for f in p.Functions: + # Enter a frame per function: + self.frame = self.newFrame(f.name) + self.frames.append(self.frame) # First define labels: - for bb in f.BasicBlocks: + for bb in f.Blocks: itgt = self.makeIns('{}:'.format(bb.name)) self.targets[bb] = itgt - for bb in f.BasicBlocks: + for bb in f.Blocks: self.emit2(self.targets[bb]) for i in bb.Instructions: self.munchStm(i) - bb.machIns = self.result - return self.result + #bb.machIns = self.result + return self.frames def makeIns(self, *args, **kwargs): return irmach.AbstractInstruction(*args, **kwargs) @@ -49,12 +52,17 @@ return self.emit2(i) def emit2(self, i): - self.result.append(i) + self.frame.instructions.append(i) return i + def newFrame(self, name): + raise NotImplementedError() + def munchStm(self, s): + """ Implement this in the target specific back-end """ raise NotImplementedError() def munchExpr(self, e): + """ Implement this in the target specific back-end """ raise NotImplementedError()
--- a/python/ir/__init__.py Mon Sep 02 17:40:21 2013 +0200 +++ b/python/ir/__init__.py Wed Sep 04 17:35:06 2013 +0200 @@ -1,4 +1,3 @@ -from .module import Module, Function, Block -from .instruction import * +from .module import * from .builder import Builder
--- a/python/ir/instruction.py Mon Sep 02 17:40:21 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,144 +0,0 @@ -from .module import Function - -class Expression: - pass - - -class Const(Expression): - def __init__(self, value): - self.value = value - - def __repr__(self): - return 'Constant {}'.format(self.value) - - -# Function calling: -class Call(Expression): - def __init__(self, f, arguments): - self.f = f - assert type(f) is Function - self.arguments = arguments - - def __repr__(self): - args = ','.join([str(arg) for arg in self.arguments]) - return '{}({})'.format(self.f.name, args) - - -# Data operations -class Binop(Expression): - ops = ['+', '-', '*', '/', '|', '&', '<<', '>>'] - def __init__(self, value1, operation, value2): - assert operation in Binop.ops - self.value1 = value1 - self.value2 = value2 - self.operation = operation - - def __repr__(self): - a, b = self.value1, self.value2 - return '({} {} {})'.format(a, self.operation, b) - - -def Add(a, b): - """ Convenience call """ - return Binop(a, '+', b) - - -class Alloc(Expression): - """ Allocates space on the stack """ - def __init__(self): - super().__init__() - - def __repr__(self): - return 'Alloc' - - -class Variable(Expression): - def __init__(self, offset): - self.offset = offset - - def __repr__(self): - return 'Variable' - - -class LocalVariable(Variable): - pass - - -class GlobalVariable(Variable): - pass - - -class Parameter(Variable): - pass - - -class Temp(Expression): - """ Temporary storage, same as register """ - def __init__(self, name): - self.name = name - - def __repr__(self): - return 'T_{}_'.format(self.name) - - -class Mem(Expression): - def __init__(self, e): - self.e = e - - def __repr__(self): - return '[{}]'.format(self.e) - - -class Statement: - """ Base class for all instructions. """ - pass - - -class Move(Statement): - def __init__(self, dst, src): - self.dst = dst - self.src = src - - def __repr__(self): - return '{} = {}'.format(self.dst, self.src) - - -class Exp(Statement): - def __init__(self, e): - self.e = e - - -class Label(Statement): - def __init__(self, name): - self.name = name - self.statements = [] - - def __repr__(self): - return 'LABEL {}:'.format(self.name) - - -# Branching: -class Jump(Statement): - def __init__(self, target): - self.target = target - self.Targets = [target] - - def __repr__(self): - return 'BRANCH {}'.format(self.target.name) - - -class CJump(Statement): - def __init__(self, a, cond, b, lab_yes, lab_no): - assert cond in ['==', '<', '>', '>=', '<=', '!='] - self.a = a - self.cond = cond - self.b = b - self.lab_yes = lab_yes - self.lab_no = lab_no - self.Targets = [lab_yes, lab_no] - - def __repr__(self): - return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no) - - -
--- a/python/ir/module.py Mon Sep 02 17:40:21 2013 +0200 +++ b/python/ir/module.py Wed Sep 04 17:35:06 2013 +0200 @@ -1,8 +1,24 @@ # IR-Structures: +def dumpgv(m, outf): + print('digraph G ', file=outf) + print('{', file=outf) + for f in m.Functions: + print('{} [label="{}" shape=box3d]'.format(id(f), f),file=outf) + for bb in f.Blocks: + contents = str(bb) + '\n' + contents += '\n'.join([str(i) for i in bb.Instructions]) + outf.write('{0} [shape=note label="{1}"];\n'.format(id(bb), contents)) + for successor in bb.Successors: + print('"{}" -> "{}"\n'.format(id(bb), id(successor)), file=outf) + + outf.write('"{}" -> "{}" [label="entry"]\n'.format(id(f), id(f.entry))) + print('}', file=outf) + + class Module: - """ Main container for a piece of code. """ + """ Main container of variables and functions. """ def __init__(self, name): self.name = name self.funcs = [] @@ -38,29 +54,16 @@ getFunction = findFunction def dump(self): - print(self) - for v in self.Variables: - print(' ', v) - for fn in self.Functions: - print(fn) - for bb in fn.BasicBlocks: - print(' ', bb) - for ins in bb.Instructions: - print(' ', ins) - - def dumpgv(self, outf): - outf.write('digraph G \n{\n') - for f in self.Functions: - outf.write('{0} [label="{1}" shape=box3d]\n'.format(id(f), f)) - for bb in f.BasicBlocks: - contents = str(bb) + '\n' - contents += '\n'.join([str(i) for i in bb.Instructions]) - outf.write('{0} [shape=note label="{1}"];\n'.format(id(bb), contents)) - for successor in bb.Successors: - outf.write('"{0}" -> "{1}"\n'.format(id(bb), id(successor))) - - outf.write('"{0}" -> "{1}" [label="entry"]\n'.format(id(f), id(f.entry))) - outf.write('}\n') + print(self) + indent = ' ' + for v in self.Variables: + print(indent, v) + for fn in self.Functions: + print(fn) + for bb in fn.Blocks: + print(indent+str(bb)) + for ins in bb.Instructions: + print(indent * 2 + str(ins)) # Analysis functions: def check(self): @@ -70,19 +73,24 @@ class Function: + """ + Function definition. Contains an entry block. + """ def __init__(self, name): self.name = name self.entry = Block('{}_entry'.format(name)) self.epiloog = Block('{}_epilog'.format(name)) + self.epiloog.addInstruction(Terminator()) self.arguments = [] def __repr__(self): - return 'Function {0}'.format(self.name) + args = ','.join(str(a) for a in self.arguments) + return 'Function {}({})'.format(self.name, args) def addBB(self, bb): self.bbs.append(bb) bb.parent = self - addBasicBlock = addBB + addBlock = addBB def removeBasicBlock(self, bb): self.bbs.remove(bb) @@ -110,14 +118,18 @@ return bb raise KeyError(name) - BasicBlocks = property(getBBs) + Blocks = property(getBBs) @property def Entry(self): return self.entry def check(self): - pass + for b in self.Blocks: + b.check() + + def addParameter(self, pname): + self.arguments.append(pname) def call(self, *args): varmap = {} @@ -142,6 +154,7 @@ def addInstruction(self, i): i.parent = self + assert not isinstance(self.LastInstruction, LastStatement) self.instructions.append(i) def replaceInstruction(self, i1, i2): @@ -161,7 +174,8 @@ Instructions = property(getInstructions) def getLastIns(self): - return self.instructions[-1] + if not self.Empty: + return self.instructions[-1] LastInstruction = property(getLastIns) @property @@ -190,6 +204,163 @@ raise NotImplementedError() def check(self): - pass + assert isinstance(self.LastInstruction, LastStatement) + for i in self.instructions[:-1]: + assert not isinstance(i, LastStatement) + + +# Instructions: + +class Expression: + pass + + +class Const(Expression): + def __init__(self, value): + self.value = value + + def __repr__(self): + return 'Constant {}'.format(self.value) + + +# Function calling: +class Call(Expression): + def __init__(self, f, arguments): + self.f = f + assert type(f) is Function + self.arguments = arguments + + def __repr__(self): + args = ','.join([str(arg) for arg in self.arguments]) + return '{}({})'.format(self.f.name, args) + + +# Data operations +class Binop(Expression): + ops = ['+', '-', '*', '/', '|', '&', '<<', '>>'] + def __init__(self, value1, operation, value2): + assert operation in Binop.ops + self.value1 = value1 + self.value2 = value2 + self.operation = operation + + def __repr__(self): + a, b = self.value1, self.value2 + return '({} {} {})'.format(a, self.operation, b) + + +def Add(a, b): + """ Convenience call """ + return Binop(a, '+', b) + + +class Alloc(Expression): + """ Allocates space on the stack """ + def __init__(self): + super().__init__() + + def __repr__(self): + return 'Alloc' + + +class Variable(Expression): + def __init__(self, name): + self.name = name + + def __repr__(self): + return 'Var {}'.format(self.name) + + +class LocalVariable(Variable): + pass + + +class GlobalVariable(Variable): + pass + + +class Parameter(Variable): + def __repr__(self): + return 'Param {}'.format(self.name) +class Temp(Expression): + """ Temporary storage, same as register """ + def __init__(self, name): + self.name = name + + def __repr__(self): + return 'T_{}_'.format(self.name) + + +class Mem(Expression): + def __init__(self, e): + self.e = e + + def __repr__(self): + return '[{}]'.format(self.e) + + +class Statement: + """ Base class for all instructions. """ + pass + + +class Move(Statement): + def __init__(self, dst, src): + self.dst = dst + self.src = src + + def __repr__(self): + return '{} = {}'.format(self.dst, self.src) + + +class Exp(Statement): + def __init__(self, e): + self.e = e + + +class Label(Statement): + def __init__(self, name): + self.name = name + self.statements = [] + + def __repr__(self): + return 'LABEL {}:'.format(self.name) + + +# Branching: +class LastStatement(Statement): + pass + + +class Terminator(LastStatement): + """ Instruction that terminates the terminal block """ + Targets = [] + def __repr__(self): + return 'Terminator' + + +class Jump(LastStatement): + def __init__(self, target): + self.target = target + self.Targets = [target] + + def __repr__(self): + return 'BRANCH {}'.format(self.target.name) + + +class CJump(LastStatement): + def __init__(self, a, cond, b, lab_yes, lab_no): + assert cond in ['==', '<', '>', '>=', '<=', '!='] + self.a = a + self.cond = cond + self.b = b + self.lab_yes = lab_yes + self.lab_no = lab_no + self.Targets = [lab_yes, lab_no] + + def __repr__(self): + return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no) + +
--- a/python/irmach.py Mon Sep 02 17:40:21 2013 +0200 +++ b/python/irmach.py Wed Sep 04 17:35:06 2013 +0200 @@ -7,9 +7,25 @@ Instructions are selected and scheduled at this stage. """ +class Frame: + """ + Activation record abstraction. This class contains a flattened + function. Instructions are selected and scheduled at this stage. + Frames differ per machine. + """ + def __init__(self, name): + self.name = name + self.instructions = [] + + def __repr__(self): + return 'Frame' + class AbstractInstruction: - """ Absract machine instruction """ + """ + Abstract machine instruction class. This is a very simple + abstraction of machine instructions. + """ def __init__(self, assem, src=(), dst=(), jumps=()): self.assem = assem self.src = tuple(src) @@ -17,6 +33,9 @@ self.jumps = tuple(jumps) def __repr__(self): - return self.assem + str(self.src) + str(self.dst) + s = str(self.src) if self.src else '' + d = str(self.dst) if self.dst else '' + l = str(self.jumps) if self.jumps else '' + return self.assem + s + d + l
--- a/python/tcodegen.py Mon Sep 02 17:40:21 2013 +0200 +++ b/python/tcodegen.py Wed Sep 04 17:35:06 2013 +0200 @@ -7,6 +7,7 @@ import ppci import codegenarm import outstream +import ir testsrc = """ package test2; @@ -16,7 +17,18 @@ function int insanemath(int a, int b) { var int c; - c = a + b + 1; + c = 0; + var int i; + i = 9; + while (i > 1) + { + c = a + b + 1 + c; + i = i - 1; + if (c > 90) + { + return 42; + } + } return c; } @@ -31,7 +43,7 @@ if (cee + a > b and b - a+b== 3*6-b) { var int x = a; - x = b - a + insanemath(3, 4); + x = b - a + insanemath(3, 4) - insanemath(33,2); a = x * (x + a); } else @@ -46,15 +58,44 @@ if __name__ == '__main__': diag = ppci.DiagnosticsManager() builder = c3.Builder(diag) - ir = builder.build(testsrc) - ir.dump() + irc = builder.build(testsrc) + if not irc: + diag.printErrors(testsrc) + irc.check() + irc.dump() + with open('ir.gv', 'w') as f: + ir.dumpgv(irc, f) outs = outstream.TextOutputStream() cga = codegenarm.ArmCodeGenerator(outs) - cfg_file = open('cfg.gv', 'w') - ig_file = open('ig.gv', 'w') - ir2 = cga.generate(ir, cfg_file=cfg_file, ig_file=ig_file) - cfg_file.close() - ig_file.close() - for i in ir2: - print(i) + ir2 = cga.generate(irc) + + with open('cfg.gv', 'w') as cfg_file: + print('digraph G {', file=cfg_file) + #print('edge [constraint=none]', file=cfg_file) + print('rankdir=TB', file=cfg_file) + for f in cga.frames: + print('subgraph cluster_{} {{'.format(f.name), file=cfg_file) + print('label={};'.format(f.name), file=cfg_file) + print('color=lightgrey;', file=cfg_file) + print('style=filled;', file=cfg_file) + f.cfg.to_dot(cfg_file) + print('}', file=cfg_file) + print('}', file=cfg_file) + with open('ig.gv', 'w') as ig_file: + print('digraph G {', file=ig_file) + print('edge [arrowhead=none]', file=ig_file) + for f in cga.frames: + print('subgraph cluster_{} {{'.format(f.name), file=ig_file) + print('label={};'.format(f.name), file=ig_file) + print('color=lightgrey;', file=ig_file) + print('style=filled;', file=ig_file) + f.ig.to_dot(ig_file) + print('}', file=ig_file) + print('}', file=ig_file) + + for f in ir2: + print(f) + for i in f.instructions: + print(' {}'.format(i)) +
--- a/python/testir.py Mon Sep 02 17:40:21 2013 +0200 +++ b/python/testir.py Wed Sep 04 17:35:06 2013 +0200 @@ -16,8 +16,10 @@ f = self.b.newFunction('add') self.b.setFunction(f) bb = self.b.newBlock() + self.b.emit(ir.Jump(bb)) self.b.setBlock(bb) self.b.emit(ir.Exp(ir.Const(0))) + self.b.emit(ir.Jump(f.epiloog)) self.m.check() # Run interpreter: # r = self.m.getFunction('add').call(1, 2) @@ -34,11 +36,14 @@ def testBuilder(self): f = self.b.newFunction('test') self.b.setFunction(f) - self.b.setBlock(self.b.newBlock()) + bb = self.b.newBlock() + self.b.emit(ir.Jump(bb)) + self.b.setBlock(bb) v1 = ir.Const(5) v2 = ir.Const(7) v3 = ir.Add(v1, v2) - self.cf.run(self.m) + self.b.emit(ir.Jump(f.epiloog)) + #self.cf.run(self.m) def testAdd0(self): f = self.b.newFunction('test')