# Tag Info

22

Other reason for compilers to produce assembly rather than proper machine code are: The symbolic addresses used by assemblers instead of hard-coding machine addresses make code relocation much easier. Linking code may involve safety checks such as type-checking, and that's easier to do with symbolic names. Small changes in machine code are easier to ...

15

A compiler does usually convert high-level code directly to machine language, but it can be built in a modular way so that one back-end emits machine code and the other assembly code (like GCC). The code generation phase produces "code" which is some internal representation of machine code, which then has to be converted to a usable format like machine ...

11

Historically a number of notable compilers did output machine code directly. There are some difficulties with doing so, however. Generally someone who's trying to confirm that a compiler is working correctly will find it easier to examine assembly-code output than machine code. Further, it's possible (and was historically common) to use a one-pass C or ...

6

The first pass can't resolve any forward jumps. For example: cmp r1, 0 bne label add r2, r3, r4 label: add r3, r4, r5 On the first pass, when the assembler gets to the bne label instruction, it doesn't know how far the branch needs to jump because it hasn't seen label yet. On the second pass, it knows where all the branch targets are ...

5

A binary code is a set of vectors in $\mathbb{F}_2^n$ for some $n$. Presumably the context in which you encountered this construction is a motivation for it. It's a particular case of a more general construction known as a Cayley graph, though perhaps this particular case has a specific name. You are right that all arithmetic is done in $\mathbb{F}_2$. There ...

5

Update Based on your comment, I'm not concerned so much about switch statement being inefficient as I am by the fact that the switch statement exists at all. , I think that I understand the question better now. And the answer is that you want currying to be applied on the first execution. As a quick explanation of currying, consider a mathematical ...

4

In general when we talk about code generation (or model-to-model transformation in general), clearly defined semantics is quite important, since such transformations usually make sense when both the source and the target model semantically match according to some criteria. For example, programmers might describe the behaviour of a program with a formal ...

4

Yes and no. Yes, you could structure a compiler this way, but most of the benefits you are hoping for would not materialize. There may be some benefits, such as a powerful compile-time meta-language. There are also costs like a complete loss of the ability to make meaningful guarantees about code that isn't completely self-contained (e.g. takes in objects ...

3

The book "A Retargetable C Compiler: Design and Implementation" by Christopher Fraser and David Hanson gives some detail on how they lower switch statements to a combination of conditional branches and jump tables. They cite prior work that their technique builds on, so it would be a good start for a literature survey. There should be nothing particular to ...

3

Microcode instruction sets typically have more fields than ordinary instruction sets. Sometimes this is called wide word, as a very long instruction can offer access to multiple hardware components in the same cycle for many operations to be performed in parallel. In simpler microcoded systems, instead of being wide in the extreme, the numerous (smaller) ...

3

The transformation to CPS style converts from r = foo_direct(...); bar(r); to foo_cps(..., bar); If you want to go backwards, I think the following works. In CPS, every function call will have a continuation as its last argument. So, at each function call site, you find the continuation and unwind it. In other words, foo_cps(..., ct); gets ...

3

I did some additional research to answer this question but find nothing better suited. To do reverse of CPS to direct programming you have to assign functions to variables, this makes direct structural code. Automated and well described technique comes from compilers - SSA (Single Static Assignment). This has additional bonus like compacting code and ...

3

Depends. For the purpose of formal analysis, this is usually below our threshold of modelling. Just make a reasonable assumption, or forbid syntactic sugar in your model syntax. Note that, if you are analysing at this level of detail, working with higher-level languages can be painful. If you want to follow Donald Knuth's lead, fix a (manageable) machine ...

3

Automatic parallelization in the most general terms is extracting a dependency graph from the execution sequence of the program and executing distinct paths in this graph in parallel with synchronization introduced at the nodes of the graph where the paths merge. Our ability to extract the dependency information varies depending on the programming language ...

2

I agree with Raphael, don't look too far for a precise meaning of those terms. AFAIK, there is none. (And that rule is also true for terms which have a precise meaning, often the same word in used with a different precise meaning in different contexts). A compiler converts a human-readable codes to object codes, I'd say that compiler is used for ...

2

Three address code is an intermediate language used internally by (some) compilers. What is "right" depends on the specific rules that that compiler expects/enforces. Efficiency, as you state, is normally not an issue, as the intermediate language is designed for easy massaging and ultimately traslating into efficient target code.

2

It is reasonably common nowadays that code is recompiled on occasion. For example, a JVM compiler will initially assume that some function call is not virtual (but can be proved wrong). It will then for a virtual function call generate code like "if (function implementation is what I thought it would be) then (call that implementation) else (recompile this ...

2

Unroll the loop. Instead of while true: switch on var: 1 => branch1 2 => branch2 default => branch3 replace that with an unrolled version: while true: switch on var: 1 => branch1 2 => goto loop2 default => branch3 return loop2: while true: branch2 Or, if you prefer: while true: switch on var: 1 =&...

2

Codes like 5421 and 2421 are not unique, and this is one of their advantages. For example, 2421 is self-complementing: computing the 9-complement of a digit is the same as negating its bits. In textbooks you can find tables in which the authors choose one possible code for each digit, but this choice is arbitrary, and you might find different choices in ...

2

I haven't seen anything on this but the closest I could find is Evolving Algebras: Evolving Algebras: An Attempt to Discover Semantics Evolving Algebras: Mini-Course Communicating Evolving Algebras In that mini course there are several papers outlining different aspects and applications of the Evolving Algebra. From one of them: In 1988 Yuri Gurevich ...

2

Yes, of course. $2^{f(n)}$ is asymptotically larger than $f(n)$, so you can come up with an unending sequence of larger and larger running times. The answer to your other questions are also yes, by the time hierarchy theorem.

1

I'm going to simplify your question, considering that a specific encoding for a universal Turing machine will necessarily include a method for the encoding of its programs. I'll also assume that the encoding of programs and their inputs are also interdependent, meaning that you can't define how the former is done well enough without defining how the latter ...

1

I don't know anything about it but the field as a whole is called "automatic programming", which should give you pointers of where to look.

1

There has been a lot of work in genetic programing (GP) in this vein. Automatically defined functions are a big deal in GP and figuring out how many and what kinds of ADF's you should have (the "Architecture") has been the subject of a lot of research as well. More generally some people have looked at how to use GP to create libraries that it can then work ...

1

It highly depends on what is the domain you are working on, i.e. why do you need to generate Java Source code anyway?. Can you explain better what knowledge do you have stored in your knowledge base?. The most "formal" method I can think of is by using the Java grammar and generate and abstract syntax tree as you mentioned. But it may or may not be ...

1

Use some form of metamodelling : The outputs are represented as abstract syntax trees (ASTs): and constructed by a decoder with a dynamically-determined modular structure paralleling the structure of the output tree. References Modelling homogeneous generative meta-programming Abstract Syntax Networks for Code Generation and Semantic Parsing ...

1

This looks very much like the Nearest neighbor problem. The asymptotically most efficient approach is probably computing a k-d-tree on the points in B. Constructing the tree takes $O(|B| \log |B|)$ and lookup is logarithmic, so an additional $O(|A| \log |A|)$ to find all nearest neighbours. Please not that the constant factors for the naive approach where ...

1

A compiler should be able to produce an assembler output in addition to the normal relocatable code is for the benefit of the programmer. One time I just not find the bug in a C program running on Unix System V on an LSI-11 machine. Nothing seemed to work. Finally in desperation I had the protable C compiler excrete an assembler version of its translation. ...

1

Usually compilers work internally with sequences of instructions. Each instruction will be represented by a data structure representing it's operation name, operands and so-on. When the operands are addresses those addresses will usually be symbolic references, not concrete values. Outputting assembler is relatively simple. It's pretty much a matter of ...

1

Even platforms that use the same instruction set may have different relocatable object file formats. I can think of "a.out" (early UNIX), OMF, MZ (MS-DOS EXE), NE (16-bit Windows), COFF (UNIX System V), Mach-O (OS X and iOS), and ELF (Linux and others), as well as variants of those, such as XCOFF (AIX), ECOFF (SGI), and COFF-based Portable Executable (PE) on ...

Only top voted, non community-wiki answers of a minimum length are eligible