On Semantics Of Programming Languages:

Hamada Ali Mohamed Ali Nayel

Multi-threaded programs have many applications which are widely usedsuch as operating systems. Analyzing multi-threaded programs diersfrom sequential ones; the main feature is that many threads execute atthe same time. The eect of all other running threads must be takenin account. Type systems is a good framework for analyzing programs.This thesis focuses on the analysis of multi-threaded programs using typesystems. The rst aim of our work is to implement partial redundancyelimination for multi-threaded programs via type systems. Partial redundancyelimination is among the most powerful compiler optimization: itperforms loop invariant code motion and common subexpression elimination.The second aim is to build a static data race detector that hasthe form of type systems. Data race occurs when two threads try to accessa shared variable at the same time without a proper synchronizationand one of them is write. A detector is a software that determines if theprogram contains a data-race problem or not.The thesis is organized as follow:-In chapter 1, we present a general introduction about the work. Inchapter 2, we introduced the related work to ours. We outlines themain algorithms and basic denitions that needed. In chapter 3, wepresent a type system with optimization component which performs parviitial redundancy elimination for a multi-threaded programs. In chapter4, we designed a type system based data race detector. We presenta type system which discovers the data-race problems. We also provethe soundness of all type systems introduced through thesis. Chapter 5overview the main conclusions of the thesis and the future work that canbe contributed.