Any code that has a nested loop where the inner loop breaks out of the outer loop, compiles wrong using single-path code.
The code could look something like this:

outer:
while(..) {
  while(..) {
    ..
    if(..) {
      break outer;
    }
  }
}

An example program that exhibits this problem is the Dijkstra program from the tacle benchmark.

The problem is caused by the way predicate register allocation is performed. In RAInfo, when a loop is encountered, all predicates are spilled such that the loop has all predicate register available for it single-path code. However, this doesn't account for cases as the above, since the inner loop would need to edit the outer loop's predicate to be able to disable it when the break happens. In the current implementation, the break assumes the outer loop's predicate is in a register, which it never is.

There are 2 possible solutions:

1. Fix it in-place by taking this case into account. This would probably require significant reimplementation to remove the whole-sale spilling before each loop and edit the register allocation to no longer work on the FCFG only but also take inner loops into account (currently, register allocation ignores inner loops because the whole-sale spilling is assumed).
2. We don't fix it in-place but instead defer a fix to when we move the single-path transformation to before register allocation. This would allow us to offload predicate register allocation to LLVM entirely, which would fix this issue as a by-product.

Using the modulo operand is the likely reason for bugs with some programs as we do not have a customized version of it. It results in platin failures and single-path failures because it has an unbounded loop.

This issue tracks fixing this. The best solution is providing our own modulo function in Compiler-RT (umodXi3).

In Single-Path/SPScope.cpp, the order of blocks is decided by getBlocksTopoOrd. While this is a valid order, it is not always optimial, since there is no guarantee that the produced topological order minimizes the highest number of live predicates.

We should therefore implement a better block order algorithm that tries to minimize the highest number of live predicates. This should produce faster code, since less instructions are then needed for loading/spilling from the stack.

Additionally, the current topological sort is not deterministic (given the same program, the sort might be different for different compilations) probably because std::maps are used, whose keys are block addresses that change with every compile.
The new algorithm should be deterministic to make debugging easier.

The compiler in the current version does not compile the C code in the Patmos hardware. Example issues:

error: unknown argument: ‘-mpatmos-disable-vliw’

        : “$r1”, “$r2", “$r3”,          \
         ^
ethlib/tte.c:484:3: error: unknown register name ‘$r1’ in asm

Trying to divide uint64_t will result in Platin complaining there is an unbounded loop.

Example program:

#include <stdio.h> 
#include <stdint.h>
#include <inttypes.h>

uint32_t test_fn (uint32_t x, uint32_t y)  __attribute__ ((noinline));

int main () {
	uint32_t x, y;
	scanf("%" SCNd32 "\n", &x);
	scanf("%" SCNd32 "\n", &y);
	printf("%d\n", (int) test_fn(x, y));
	return 0;
}

uint32_t test_fn (uint32_t x, uint32_t y) {
	return x / y;
}

Trying to analyze the resulting binary for WCET of test_fn will make Platin complain.

Looking into compiler-rt, I see that there is a dedicated function for 32-bit division in the Patmos builtins, but not for 64-bit.
This means the default one is used, which of-course doesn't include loop bounds.

Solution is to implement 64-bit division for Patmos in compile-rt such that it works out of the box.

I get following error:

/tmp/hello2-588b69.bc.o:/tmp/hello2-81e00f.opt.bc:function _start: error: undefined reference to '_loader_baseaddr'
/tmp/hello2-588b69.bc.o:/tmp/hello2-81e00f.opt.bc:function _start: error: undefined reference to '_loader_off'
patmos-clang-3.4: error: link  via llvm-link, opt and llc command failed with exit code 1 (use -v to see invocation)

I can provide a .zip file with the code that leads to this issue. But maybe someone has seen this before.

All program tests under llvm/test/CodeGen/Patmos/programs currently return i32.
This is not optimal, since (on at least Linux) that returned values is truncated by the terminal into only 8 bits.
Because of this, all tests are designed to return values between 0 and 255 to ensure sensible return codes to be checked.

We should change the setup such that all tests return i8.