[ Content | Sidebar ]

Christmas Common

May 6th, 2015

It’s been ages since I last went adventuring in the Chilterns so this May Day holiday I headed off to cheerfully named village of Christmas Common. The long day out had the useful side-effect of distracting me from worrying about the flat I was trying to buy. (I didn’t get it: some cash buyer paid £20k over the already steep asking price; the London property market is bonkers.)

You probably don’t remember but a few years ago I posted about a ruined church I discovered on my travels. Well it seems persons unknown have decided to erect fences and un-ruin it! Honestly I think I preferred it before but I’ll wait and see what they do with it…

ruined_church_scale

Boris Sighting

April 27th, 2015

Out in Uxbridge buying lunch today who did I see but the almighty God-Emperor of Great Britain and prospective MP, Boris Johnson!

boris_scale

In real life he’s somewhat shorter and paler than I imagined. Unfortunately I was so overcome with awe I didn’t go up and get my photo taken with him before the minder hustled him away. Shame, as it would have been my greatest celebrity encounter since Mandeville.

Stratford-upon-Avon

April 19th, 2015

Sunny spring Saturday? Sounds like time for an epic adventure! I hadn’t been to the Cotswolds since my adventure to Cheltenham nearly a year ago so it was high time for another visit. I caught the train to Kingham on the edge of Oxfordshire and planned to walk to Stratford-upon-Avon.

I was hampered a bit by a mild bout of hay fever. It doesn’t normally affect me so the pollen density must have been abnormally high. You can see all the wild flowers blooming in the photo below.

pillar_scale

My trip wasn’t entirely successful. The first failure was my usual inability to estimate distance from a map, or perhaps an overestimation of my walking speed. This led to a daft semi-circular detour at the start as I decided to “make a day of it”. The second failure came after lunch when I got a bit lost and walked a mile or more in the wrong direction; dangerously close to the Clarkson/Murdoch/Cameron hive of Chipping Norton. Thirdly, due to the complexity of getting home from Stratford my last sensible connecting train was at 19:37, which was cutting it a bit tight.

So, with about an hour until the train and another five miles to Stratford I decided to cheat and catch a well-timed bus the rest of the way.

Although my first foray into Warwickshire didn’t go quite to plan I think the idea is sound and the route was pleasant so maybe I’ll have another go later in the year.

Stratford itself on first appearances is a generic English market town. Here’s the clock tower where I hopped off the bus.

stratford_scale

I’m sure there was something significant about Stratford… oh year… SHAKESPEARE! I spent 15 minutes madly running around following signs to “Shakespeare’s birthplace”. I expected to find an old building with a plaque or something but instead I found a large brick museum. Hmm. I assumed the actual birthplace must be embedded within, snapped a nearby “old” building, and hurried off for the train. But it turns out that old building was Shakespeare’s birthplace! Win.

not_shakespere_scale

Brecon Beacons

April 12th, 2015

I had a couple of days off work last week and thought I’d go adventuring further afield. So I backed up my tent and headed for the nearest mountain range in the Brecon Beacons. I only had one full day so I tried to plan a route visiting as many peaks as possible. Or, to paraphrase Julie Andrews:

k30uc

Several small streams were also forded. I did a rough circle from Brecon where I was staying up into the mountains, along the ridge line and back again. There was also an abortive exploration south towards Merthyr Tydfil but I decided it was getting a bit late.

The first half of the route was totally deserted. I stood on the first summit and couldn’t see another human. Near the highest peak it got a bit touristy however.

Weather was sunny all day but a bit hazy as you can see from the photo below. Predictably forgot to take sun cream but at least I had my adventuring hat.

mountain_scale

Overall, a super fun day out! Wish I’d stayed longer but maybe I can plan another Wales trip later in the year.

New Code Generator

April 6th, 2015

I haven’t written much about my VHDL compiler recently and there has been little public GitHub activity. This is because I’ve spent the last six months completely rewriting the way the back-end code generation works and I finally merged the result back into the master branch last week. This rather lengthy post attempts to explain what I’ve done.

There were numerous problems with the old code generator. Before the rewrite cgen.c was a 7000 line behemoth that took VHDL syntax trees at one end and produced a complete LLVM module at the other. It dealt with everything from the minutiae of memory layout and branch prediction hints, to how to implement displays for nested sub-programs, to high level VHDL rules for things like bounds checking.

It was also bordering unmaintainable as it had started life as a small toy project to learn LLVM and slowly accreted features and optimisations as I implemented more and more of VHDL. There were several bugs in it that were just too painful to fix.

It was also very difficult to test: most of the rest of the modules are tested using the check C unit test framework but I couldn’t find any way to do this with the LLVM output. Instead the code generator is tested indirectly by the regression tests that run through the full compiler and simulator: this makes it hard to test for small specific features, like optimisations.

I also had several other plans for VHDL-specific optimisations and unifying the elaboration-time evaluator with the code generator that just weren’t tractable with the current system. For example the old code generator threw away most VHDL type information early on and reduced variables and signals to LLVM’s 8, 16, 32, or 64-bit integers which misses many opportunities to eliminate bounds checks.

So I finally decided to rewrite it using a scheme I’d been toying with for a while. The back end is now based around a new intermediate form called “V-code” after the P-code of Pascal. A new “lowering” phase in lower.c translates VHDL syntax trees into V-code and the code generator in cgen.c translates V-code into LLVM.

The intention of the lowering phase is to translate VHDL into something executable without getting bogged down with implementation concerns. The code generation phase focusses on generating efficient LLVM bitcode without worrying about high-level features.

I wanted V-code to be higher-level than LLVM – so that I could express VHDL features like signals, processes suspending, bounds checking etc. – but lower level than VHDL so I could hide complexities such as array directions, aggregates, non-zero-based indices, and so on.

I think the V-code language I ended up with fits this pretty well. The model is infinite register single static assignment just like LLVM but simplified in many ways – for example there are no phi nodes. V-code is strongly typed having both “normal” types such as integers, pointers, records, and arrays and VHDL-specific types such as signals, accesses, and files.

Unlike many similar intermediate languages where integer types are a certain bit width, in V-code integer registers have two ranges associated with them: a static “type” range and a dynamic “bound” range. For example, consider the following snippet:

subtype small_int is integer range 1 to 10;
 
function get_bit(x : bit_vector(1 to 20);
                 n : small_int) return bit is
    variable i : integer := n;
begin
    return x(i + 1);
end function;

If we compile this with the --dump-vcode argument the compiler will output the V-code:

Name       WORK.PACK.GET_BIT$JQuWORK.PACK.SMALL_INT;
Kind       function
Context    WORK.PACK-body
Blocks     1
Registers  12
Types      9
Variables  1
  I                                     // -2^31..2^31-1 
Result     0..1
Parameters 2
  r0    X                               // @<0..1> => 0..1 
  r1    N                               // -2^31..2^31-1 => 1..10 
Begin
   0: // Elided bounds check for r1 
      I := store r1
      r3 := const 1                     // -2^31..2^31-1 => 1 
      r4 := add r1 + r3                 // -2^31..2^31-1 => 2..11 
      // Elided bounds check for r4 
      r8 := sub r4 - r3                 // -2^31..2^31-1 => 1..10 
      r9 := cast r8                     // # => 1..10 
      r10 := add r0 + r9                // @<0..1> => 0..1 
      r11 := load indirect r10          // 0..1 
      // Elided bounds check for r11 
      return r11

The comments after each register definition give the type range and the bound range after a “=>” if different. The parameter N represented by register r1 has a type range of -2^31..2^31-1 as it’s a subtype of INTEGER but a bound range of 1..10 which means the compiler can assume its value is always within this range.

Here the old code generator would have inserted three bounds checks: one on the array access and two trivial subtype checks on I‘s initial value and the returned value. The new code generator can eliminate all three as indicated by the “Elided bounds check for …” comments.

The interesting case is the array access: the expression I + 1 ends up in register r4. This has type range -2^31..2^31-1 again so it’ll be represented by a 32-bit integer but the bound range is 2..11 which is calculated from the range of the LHS (1..10) and the RHS (1..1). When we compare this against the array range 1..20 we know this check can never fail and so skip it.

If we change the return statement to this:

return x(i + 11);

Then r4 has range 11..20 and it’s possible for this array access to be out-of-bounds so the lower phase inserts a runtime check:

   0: // Elided bounds check for r1 
      I := store r1
      r3 := const 11                    // -2^31..2^31-1 => 11 
      r4 := add r1 + r3                 // -2^31..2^31-1 => 12..21 
      r5 := const 1                     // -2^31..2^31-1 => 1 
      bounds r4 in 1 .. 20
      r9 := sub r4 - r5                 // -2^31..2^31-1 => 11..20 
      r10 := cast r9                    // # => 11..20 
      r11 := add r0 + r10               // @<0..1> => 0..1 
      r12 := load indirect r11          // 0..1 
      // Elided bounds check for r12 
      return r12

As an aside, I spent a lot of time making the debug output from V-code human readable. The output is colour-coded and all register definitions are annotated with their type and bounds. I’ve wasted too much time trying to parse the LLVM bitcode textual format!

At the moment bounds propagation only occurs for certain arithmetic operations and only across a single basic block. However this seems to be effective for a large number of practical examples. Another neat side-effect of this scheme is that V-code has constant folding almost for free: a “constant” is any register with a bound range containing a single value. The emit_* functions which generate op-codes typically short-circuit and return a constant register when all their inputs are constants.

The following example shows how V-code represents VHDL-specific features like signals and process control flow.

architecture rtl of example is
    signal x : bit;
begin
    process is
    begin
        x <= '1';
        wait for 1 ps;
        x <= '0';
        wait for 2 ps;
    end process;
end architecture;

The wait-for statement here causes the process to suspend for the given amount of simulation time and then resume at the following statement. In NVC this is implemented as a jump table at the start of a function generated for a process. A wait statement stores the index of the next block in the process’s global state object and returns from the function. This works well but trying to debug the control flow of the generated LLVM can be very difficult. Instead V-code has “waiting” as a first-class control flow op-code: it looks just like a normal jump and the implementation details are hidden in the code generator.

Name       :example:line_7
Kind       process
Context    WORK.EXAMPLE.elab
Blocks     4
Registers  14
Types      8
Variables  0
Begin
   0: r0 := nets :example:x             // $<0..1> => 0..1 
      r1 := const 1                     // # => 1 
      alloc driver nets r0+r1 driven r0+r1
      return 
   1: r2 := const 0                     // -2^63..2^63-1 => 0 
      r3 := nets :example:x             // $<0..1> => 0..1 
      r4 := const 1                     // 0..1 => 1 
      // Elided bounds check for r4 
      r5 := const 0                     // -2^63..2^63-1 => 0 
      r6 := const 1                     // # => 1 
      sched waveform r3 count r6 values r4 reject r2 after r5
      r7 := const 1000                  // -2^63..2^63-1 => 1000 
      wait 2 for r7
   2: r8 := const 0                     // -2^63..2^63-1 => 0 
      r9 := nets :example:x             // $<0..1> => 0..1 
      r10 := const 0                    // 0..1 => 0 
      // Elided bounds check for r10 
      r11 := const 0                    // -2^63..2^63-1 => 0 
      r12 := const 1                    // # => 1 
      sched waveform r9 count r12 values r10 reject r8 after r11
      r13 := const 2000                 // -2^63..2^63-1 => 2000 
      wait 3 for r13
   3: jump 1

Operations on signals are also first-class: the type annotation $<0..1> means a signal of values in the range 0..1 (i.e. the bit type). The op-codes “alloc driver” and “sched waveform” handle common operations on signals without confusing the logic with implementation details (both of these are implemented as function calls into the runtime kernel).

The new structure allows me to write much more targeted unit tests. For example the new test_lower.c test suite checks the generated op-codes for a large number of small examples. This means regression tests can be written for micro-optimisations and similar tweaks that were impossible to test before.

Overall the performance is slightly better than with the previous code generator: the bigram.vhd micro-benchmark runs about 10% faster now. This test originally spent most of its time in the runtime kernel but after I optimised that it is now dominated by the to_unsigned library function so there’s room for code generation improvements there. However, I want to spend the next month or so fixing the large number of GitHub issues that have accumulated.

Seagulls

April 5th, 2015

Seagulls! The bane of any seaside visitor. Being pooed on is not lucky, it’s very unpleasant! Here we see an idle one posing for a photo.

gull1_scale

Shortly after he flew off to join his friend. No doubt planning some form of hooliganism.

gull2_scale

Here are another pair of gulls engaging in their favourite pastime: rooting through rubbish. Note the indignant stand-offish glare from the right-hand one.

gull3_scale

Pevensey to Battle

April 5th, 2015

I tried to convince my parents of the fun of point-to-point adventuring by taking them on a family outing from Pevensey castle to the site of the battle of Hastings at the appropriately named town of “Battle”.

pevensey_scale

My first mistake was picking a rather dismal day to do it: the weather was mostly drizzle and occasionally outright rain. The second mistake was ambitiously selecting a 17 mile stretch of the 1066 Country Walk without intervening public transport for said outing. In my defence, it looked shorter on the map. Oh well, maybe I can convince them to do the Battle to Rye section in the summer.

My Tree

March 21st, 2015

A long long time ago I found an acorn next to the reservoir near our house. I carried it all the way home and planted it in my flower patch at the end of the garden. And now look: it grew into a mighty oak tree!

oak_scale

At the time I planned to build a tree house in it. Unfortunately, the growing process is considerably slower than the planning process.

Although I remember the finding and planting, I had no idea in which year this happened. My mum and I did a bit of detective work using old photographs and it definitely wasn’t there in 1993 but by 1996 it was taller than me. So I reckon it was planted in autumn 1994. Let’s hope it has another 20 years of successful growing…

Aylesbury

March 8th, 2015

Yesterday was unseasonably warm and fine so I headed off for an epic adventure from High Wycombe to previously unvisited county town of Buckinghamshire, Aylesbury. I could have followed the sensible route and headed directly north but that would have been boring. Instead I veered east to visit the pleasant Hertfordshire town of Tring and then tacked back to Aylesbury along an extension of the Grand Union canal.

Unfortunately due to my chronic inability to estimate distance I arrived in Aylesbury rather late and had to rush for a train without exploring, rendering the whole expedition somewhat pointless. What I saw of it appeared to be a larger-than-expected traditional market town. Never mind, perhaps I can return there to start a future adventure: the fabled citadel of Milton Keynes is tantalisingly close…

The highlight of the route was this viewpoint on the top of Coombe Hill. This is the highest point in the Chilterns and you can see right over the Value of Aylesbury beyond. The monument is to casualties of the Second Boer War.

hill_scale

Another pleasant surprise was Tring reservoirs where I joined the canal and you can see in the last few photos below. Walking along the causeway surrounded by water made quite a change from forests and the whole area was incredibly peaceful at the end of the day.

Nuremberg

March 5th, 2015

So after I’d been to the trade show in Nuremberg I took a day of holiday and did some sight seeing! Nuremberg has a lovely “old” town most was destroyed during the second world war and the rebuilt, although you can’t tell this immediately. Some buildings are original however, such as this cathedral and the merchant house containing the fantastic Stadtmuseum.

cathedral_scale

I spent a few hours exploring the castle which dominates the town and also has a pretty good exhibition on the history of Nuremberg as the capital of the Holy Roman Empire. The city walls and moat that surround the town are also very picturesque, but you can’t walk on top of them. :(

wall_scale

I also visited the toy museum (great) and the Albrecht-Dürer-Haus (probably better if you’re German). Both included in the museum day-pass!

On the way back I had a few hours to spare so I stopped off in Frankfurt and spent an hour wandering around in the dark and rain. There wasn’t much to see: it mostly seems to be banks and other offices. The most interesting building I saw was the office of the European Central Bank. Perhaps symbolically, one of the lights in their logo is broken.

ecb_scale