Method for determining the set of variables that may be ambiguously defined at a point in a computer program

• US 6,031,994 A
• Filed: 04/01/1997
• Issued: 02/29/2000
• Est. Priority Date: 04/01/1997
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Radigan, Jim J.
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US08/831,159
• Time in Patent Office: 1,064 Days
• Field of Search: 395/709
• US Class Current: 717/152
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis

Abstract

A computer implemented method for determining the set of variables that may be ambiguously defined at a point in a computer program includes first placing all variables contained in at least a portion of the computer program into the set. Next, a definition of a variable in at least a portion of the computer program is located. Then, if the definition unambiguously defines the variable, then the variable is removed from the set. Otherwise, if the definition is an ambiguous definition, then all the variables contained in the portion of the computer program are placed into the set.

Claims

1. A computer implemented method of determining the set of variables that may be ambiguously defined at a point in a computer program, the method comprising:

(a) placing all variables contained in at least a portion of the computer program into the set;

(b) locating a definition of a variable in at least a portion of the computer program;

(c) if the definition unambiguously defines the variable, then removing the variable from the set; and

(d) if the definition is an ambiguous definition, then placing all the variables contained in the at least a portion of the computer program into the set.

2. The method of claim 1 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a subroutine in the set.

3. The method of claim 1 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a basic block in the set.

4. The method of claim 1 further comprising storing the set in a data structure.

5. The method of claim 1 further comprising storing the set in a vector.

6. The method of claim 1 further comprising storing the set in a bit vector.

7. A computer implemented method of determining the set of variables that may be ambiguously defined at a point just after a specified definition in a computer program, the method comprising:

(a) placing all variables contained in at least a portion of a computer program into the set;

(b) locating a definition of a variable in the at least a portion of a computer program;

(c) if the definition unambiguously defines the variable, then removing the variable from the set;

(d) if the definition is an ambiguous definition, then placing all variables contained in the at least a portion of the computer program into the set; and

(e) repeating acts (b) through (d) until the definition is the specified definition.

8. The method of claim 7 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a subroutine in the set.

9. The method of claim 7 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a basic block in the set.

10. The method of claim 7 further comprising storing the set in a data structure.

11. The method of claim 7 further comprising storing the set in a vector.

12. The method of claim 7 further comprising storing the set in a bit vector.

13. A computer implemented method of determining the set of variables that may be ambiguously defined at a point just before a specified definition in a computer program, the method comprising:

(a) placing all variables contained in at least a portion of a computer program into the set;

(b) locating a definition of a variable in the at least a portion of a computer program;

(c) if the definition is not the specified definition, then

(i) if the definition unambiguously defines the variable, then removing the variable from the set;

(ii) if the definition is an ambiguous definition, then placing all variables contained in the at least a portion of the computer program into the set; and

(d) repeating acts (b) and (c) until the definition is the specified definition.

14. The method of claim 13 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a subroutine in the set.

15. The method of claim 13 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a basic block in the set.

16. The method of claim 13 further comprising storing the set in a data structure.

17. The method of claim 13 further comprising storing the set in a vector.

18. The method of claim 13 further comprising storing the set in a bit vector.

19. A computer implemented method of determining a first set of variables that may be ambiguously defined at a point just prior to the first statement in a basic block of a computer program, the method comprising:

(a) determining a second set of variables that may be ambiguously defined at a point just after the last statement in the basic block;

(b) determining a third set of variables that are unambiguously defined at a point just after the last statement in the basic block;

(c) setting a fourth set of variables that may be ambiguously defined at a point just after the basic block equal to the second set; and

(d) iteratively solving for the first set and the fourth set.

20. The method of claim 19 wherein the iteratively solving for the first set and fourth set includes:

(i) setting the first set equal to the union of the respective fourth sets for each predecessor basic block of the basic block; and

(ii) setting the fourth set equal to the union of the second set and the difference of the first set and the third set.

21. A computer implemented method of determining a first set of variables that may be ambiguously defined at a point just prior to the first statement in a basic block or a computer program, the method comprising:

(a) determining a second set of variables that may be ambiguously defined at a point just after the last statement in the basic block;

(b) setting a third set of variables that may be ambiguously defined at a point just after a basic block equal to the second set; and

(c) iteratively solving for the first set and the third set.

22. The method of claim 21, wherein the act of iteratively solving for the first set and the third set includes:

(i) setting the first set equal to the union of the respective third set for each predecessor basic block of the basic block; and

(ii) setting the fourth set equal to the union of the second set and the difference of the first set and the complement of third set.

23. A program storage device readable by a general purpose computer, the program storage device encoding statements for a method for determining the set of variables that may be ambiguously defined at a point in a computer program, the method comprising:

(a) placing all variables contained in at least a portion of the computer program into the set;

(b) locating a definition of a variable in at least a portion of the computer program;

(c) if the definition unambiguously defines the variable, then removing the variable from the set; and

(d) if the definition is an ambiguous definition, then placing all the variables contained in the at least a portion of the computer program into the set.

24. The device of claim 23 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a subroutine in the set.

25. The device of claim 23 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a basic block in the set.

26. The device of claim 23 further comprising storing the set in a data structure.

27. The device of claim 23 further comprising storing the set in a vector.

28. The device of claim 23 further comprising storing the set in a bit vector.

29. A program storage device readable by a general purpose computer, the program storage device encoding statements for a method of determining the set of variables that may be ambiguously defined at a point just after a specified definition in a computer program, the method comprising:

(a) placing all variables contained in at least a portion of a computer program into the set;

(b) locating a definition of a variable in the at least a portion of a computer program;

(c) if the definition unambiguously defines the variable, then removing the variable from the set;

(d) if the definition is an ambiguous definition, then placing all variables contained in the at least a portion of the computer program into the set; and

(e) repeating acts (b) through (d) until the definition is the specified definition.

30. The device of claim 29 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a subroutine in the set.

31. The device of claim 29 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a basic block in the set.

32. The device of claim 29 further comprising storing the set in a data structure.

33. The device of claim 29 further comprising storing the set in a vector.

34. The device of claim 29 further comprising storing the set in a bit vector.

35. A program storage device readable by a general purpose computer, the program storage device encoding a method of determining the set of variables that may be ambiguously defined at a point just before a specified definition in a computer program, the method comprising:

(a) placing all variables contained in at least a portion of a computer program into the set;

(b) locating a definition of a variable in the at least a portion of a computer program;

(c) if the definition is not the specified definition, then

(i) if the definition unambiguously defines the variable, then removing the variable from the set;

(ii) if the definition is an ambiguous definition, then placing all variables contained in the at least a portion of the computer program into the set; and

(d) repeating acts (b) and (c) until the definition is the specified definition.

36. The device of claim 35 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a subroutine in the set.

37. The device of claim 35 wherein the act of placing all variables contained in the at least a portion of the computer program includes placing all variables in a basic block in the set.

38. The device of claim 35 further comprising storing the set in a data structure.

39. The device of claim 35 further comprising storing the set in a vector.

40. The device of claim 35 further comprising storing the set in a bit vector.

41. A program storage device readable by a general purpose computer, the program storage device encoding statements for a method of determining a first set of variables that may be ambiguously defined at a point just prior to the first statement in a basic block of a computer program, the method comprising:

(a) determining a second set of variables that may be ambiguously defined at a point just after the last statement in the basic block;

(b) determining a third set of variables that are unambiguously defined at a point just after the last statement in the basic block;

(c) setting a fourth set of variables that may be ambiguously defined at a point just after the basic block equal to the second set; and

(d) iteratively solving for the first set and the fourth set.

42. The device of claim 41 wherein the iteratively solving for the first set and fourth set includes:

(i) setting the first set equal to the union of the respective fourth sets for each predecessor basic block of the basic block; and

(ii) setting the fourth set equal to the union of the second set and the difference of the first set and the third set.

43. A program storage device readable by a general purpose computer, the program storage device encoding a method of determining a first set of variables that may be ambiguously defined at a point just prior to the first statement in a basic block or a computer program, the method comprising:

(a) determining a second set of variables that may be ambiguously defined at a point just after the last statement in the basic block;

(b) setting a third set of variables that may be ambiguously defined at a point just after a basic block equal to the second set; and

(c) iteratively solving for the first set and the third set.

44. The method of claim 43, wherein the act of iteratively solving for the first set and the third set includes:

(i) setting the first set equal to the union of the respective third set for each predecessor basic block of the basic block; and

(ii) setting the fourth set equal to the union of the second set and the difference of the first set and the complement of third set.