Modular and generic WCET static analysis with LLVM framework

Abstract

O cálculo do tempo do pior-caso de execução, do inglês Worst Case Execution Time (WCET) é um desafio na área de verificação de software para sistemas de tempo real. Essa análise faz parte do trabalho de escalonamento de tarefas de processos em sistemas multi-cores. A complexidade de prever esse tempo aumenta de acordo com a complexidade do hardware do sistema a ser analisado e seus componentes, já que muitas partes de uma plataforma, como pipelines e memória cache inserem variantes no tempo de execução difíceis de prever e analisar. Existem vários métodos com diferentes abordagens para se calcular o tempo de execução de um programa. Eles são principalmente baseados em análises estáticas e dinâmicas, de forma que a estática utiliza um modelo de hardware e analisa o código, enquanto a dinâmica necessita de algum simulador ou de uma plataforma real para realizar as medidas de tempo. Esse trabalho apresenta um modelo de análise estática para prever o tempo do piorcaso de execução de códigos para sistemas embarcados de tempo real. Além disso, executa, para fins de comparação, uma análise dinâmica baseado na execução dos códigos de teste em um simulador. O modelo de análise estática é desenvolvido baseado em um assembly gerado pela infra-estrutura de compilação do LLVM, que gera uma representação intermediária de código que é independente de arquitetura. O método tem o objetivo de ser escalonável e modular, isto é, quão mais precisa a análise deve ser, melhores modelos de análise devem ser implementados e usados no processo. O modelo de análise utilizado nesse trabalho possui uma abordagem clara e utiliza uma descrição de arquitetura simples exemplificando o processo. A análise dinâmica é baseada no método Monte Carlo de simulação e é executada em um simulador da arquitetura de um AVR, o Atmega128, chamado AVRORA.

The worst-case execution time (WCET) prediction is a challenge in the software verification area for real-time embedded systems. This analysis is part of the scheduling of parallelizable processes job on multi-core systems. The complexity of predict this time increases accordingly to the complexity of the target system hardware and its components, since much of this components, as pipelines and cache memory, attach hard to predict and analyze temporal variants. There are many methods with different approaches to calculate the execution time of a program and they are based mainly on static and dynamics analysis. The first takes account a hardware model and the code analysis itself, while the second needs some accurate simulator or the target platform to perform its time measurements. This work presents a static method for predicting worst-case execution time (WCET) for embedded real-time systems. Furthermore, performs, as a comparison of accuracy, a dynamic analysis, running the test codes in a simulator. The static analysis is performed based on an assembly generated by the LLVM compiler. This compilation framework generates a code intermediate representation (IR) independent of architecture. The model aims to be a modular and scalable, that means, it was build to accept different accuracy levels, depending on the accuracy of the developed hardware model and the analysis used in the process. In this work, this work analysis follows a clear approach and uses a simple architecture description for its execution. The dynamic analysis is done based on the Monte Carlo simulation method, performed over the AVR ATmega128 simulator, AVRORA.