Pointer-induced aliasing: A problem classification

A?iasing occurs at some program point during execu-tion when two or more names exist for the same loca-tion. We have isolated various programming language mechanisms which create aliases. We have classified the complexity of the fllas problem induced by each mech-anism alone and in combination, as AfP-hard, comple-ment tip-hard, or polynomial (’P). We present our problem classification, give an overview of our proof that finding interprocedural aliases in the presence of single level pointers is in 7, and present a represent tive proof for the NP-hard problems.