1 00:00:03,012 --> 00:00:08,040 In this video, we're going to look at another global analysis called liveness 2 00:00:08,040 --> 00:00:14,045 analysis. So, in the past several videos we've looked at a procedure for globally 3 00:00:14,045 --> 00:00:19,029 propagating constants through a control flow graph And let's, here's, here's one 4 00:00:19,029 --> 00:00:24,019 of the control flow graphs we've been looking at and recall that this algorithm 5 00:00:24,019 --> 00:00:29,004 that we discussed would be sufficient to show that we could replace this use of x 6 00:00:29,004 --> 00:00:34,027 here by the constant three. And once we do that. This assignment x might no longer be 7 00:00:34,027 --> 00:00:39,019 useful. It might not be used anywhere And so we could potentially delete this 8 00:00:39,019 --> 00:00:43,098 statement from the program And that would be a real optimization, an important 9 00:00:43,098 --> 00:00:48,095 optimization to do. However, we can only do that if x is not used elsewhere in the 10 00:00:48,095 --> 00:00:55,071 program. So let's be a little more careful about what we mean by saying that x is not 11 00:00:55,071 --> 00:01:01,031 used. So down here is a use of x, a reference to x, in a statement. And, 12 00:01:01,031 --> 00:01:07,090 clearly this particular reference to x, is, use, picking up the value that's 13 00:01:07,090 --> 00:01:14,024 defined by this right x here. So, we say that the right of x here, is live. This 14 00:01:14,024 --> 00:01:20,091 one is live. Okay, And what that means is that the value may be used in the future. 15 00:01:20,091 --> 00:01:27,029 So, live, equals, may be used. In the future, Okay? So the value written to x at 16 00:01:27,029 --> 00:01:32,023 this line of code maybe used by some subsequent instruction And here it's not 17 00:01:32,023 --> 00:01:37,043 just that it may be used. It's actually guaranteed to be used because there's only 18 00:01:37,043 --> 00:01:41,081 one path. And that one path has a reference to x on it before there's 19 00:01:41,081 --> 00:01:46,094 another assignment to x. Okay? So this particular value of x as written here is 20 00:01:46,094 --> 00:01:52,014 guaranteed to be used. But in general we don't require that. We just mean there has 21 00:01:52,014 --> 00:01:57,040 to be a possibility that it will be used. Now in contrast let's take a look at this. 22 00:01:57,040 --> 00:02:03,084 Other statement in this example, Here, we assign x a value three but this assignment 23 00:02:03,084 --> 00:02:09,033 x, this value of x is never used. This one, is dead. Alright? Because the value 24 00:02:09,033 --> 00:02:14,036 three here is overwritten by the value four before there's any use of, the 25 00:02:14,036 --> 00:02:19,046 variable x, Okay? So this particular right to x will never see the light of day. 26 00:02:19,046 --> 00:02:25,002 It'll never get used by any part of the program. And we say that it is dead. So, 27 00:02:25,002 --> 00:02:31,023 to summarize a variable x is live as a statement S if, there exist some statement 28 00:02:31,023 --> 00:02:36,066 that uses x. Okay. So, some other statement S prime that uses x, and there 29 00:02:36,066 --> 00:02:43,032 is some path from S to S prime and there is no intervening assignments on that path 30 00:02:43,032 --> 00:02:49,037 to x. Alright? So, there needs to be an assignment to x, at some statement S there 31 00:02:49,037 --> 00:02:54,813 is some path through the program that reaches a read of x. Add sum statement to 32 00:02:54,813 --> 00:03:02,044 S prime, and along that path, there is no right to x, Okay? And if this situation 33 00:03:02,044 --> 00:03:09,015 arises, then we say that this value written in this first statement s is live. 34 00:03:09,058 --> 00:03:14,031 Now if a value is not live, then it is dead. And a statement that assigns to x is 35 00:03:14,031 --> 00:03:18,074 going to be dead code if x is dead after the assignment. So, if we know that 36 00:03:18,074 --> 00:03:23,000 immediately after the assignment, immediately after this assignment to x, 37 00:03:23,192 --> 00:03:28,009 there is no possibility that a value of x will be used in the future. Well then the 38 00:03:28,009 --> 00:03:32,076 assignment was useless, and the entire statement can be removed. Alright, So dead 39 00:03:32,076 --> 00:03:37,019 assignments can be deleted from the program, But notice that in order to do 40 00:03:37,019 --> 00:03:41,063 that we have to have the liveness information. We need to know whether x is 41 00:03:41,063 --> 00:03:47,011 dead at this point. So, once again, what we want to do is to have global 42 00:03:47,011 --> 00:03:51,030 information about the control flow graph. In this case, the property is whether x 43 00:03:51,030 --> 00:03:55,048 will be used in the future. We want to make that information local to a specific 44 00:03:55,048 --> 00:03:59,056 point in the program, so we can make a local optimization decision. Alright, And 45 00:03:59,056 --> 00:04:03,085 just like for constant propagation, we're going to define in a, an algorithm for 46 00:04:03,085 --> 00:04:07,098 performing liveness analysis And it's going to follow the same framework. If 47 00:04:07,098 --> 00:04:11,096 we're going to express liveness in terms of information transferred between 48 00:04:11,096 --> 00:04:15,099 adjacent statements, just as we did for copy of constant propagation And it's 49 00:04:15,099 --> 00:04:20,000 gonna turn out that liveness is actually quite, If it's simpler, or somewhat 50 00:04:20,000 --> 00:04:24,022 simpler, than constant propagation, since it's just a Boolean property. Eh, you 51 00:04:24,022 --> 00:04:29,063 know, it's either true of false. Alright So let's take a look at some of the rules 52 00:04:29,085 --> 00:04:36,005 for liveness. So here, we're defining what it means for x to be live at this point 53 00:04:36,005 --> 00:04:41,088 here. So we're immediately after p is x live And it's going to be live. Remember 54 00:04:41,088 --> 00:04:47,085 what the intuition is. The intuition is that a, the variable x is live right after 55 00:04:47,085 --> 00:04:53,098 p if the value of x is used on some path. On one of the paths that begin at p. 56 00:04:53,098 --> 00:04:58,042 Alright, And so, in order to know whether it's live, we're going to take the 57 00:04:58,060 --> 00:05:03,046 liveness information at each of the input points. So that would be here, here, here, 58 00:05:03,046 --> 00:05:08,003 and here. So each of the successor statements after p And we're gonna ask, is 59 00:05:08,003 --> 00:05:12,076 x live at any of those points? So it's just a big or over the liveness of x and 60 00:05:12,077 --> 00:05:18,083 all of the successors of p And that's the liveness of x at the out of p. Next, let's 61 00:05:18,083 --> 00:05:23,005 consider the effect of individual statements on the liveness of x. So, the 62 00:05:23,005 --> 00:05:27,010 first rule is, that if we have a statement, and it reads the value of x, 63 00:05:27,010 --> 00:05:31,043 Okay? So here, we have an assignment statement, and on the right hand side, it 64 00:05:31,043 --> 00:05:36,032 refers to x, so its reading x Then, x is live Before that statement. Clearly, x is 65 00:05:36,032 --> 00:05:41,069 just about to be used on the end of this statement, and so x is live at that point. 66 00:05:41,069 --> 00:05:46,040 Alright? So if a statement, or if, [inaudible], if a statement reads the 67 00:05:46,040 --> 00:05:51,090 value of x, then the in of that statement, x, is true. Sorry, the liveness of x is 68 00:05:51,090 --> 00:05:59,055 true. A second case is when a statement writes the value of x So here we have an 69 00:05:59,055 --> 00:06:05,080 assignment to x And the rest of the statement does not refer x Does not read 70 00:06:05,080 --> 00:06:12,079 the value of x. So there's no x in E. Okay So in this situation x is not live before 71 00:06:12,079 --> 00:06:18,083 the statement. X is not live or we can say that x is dead Before the statement And 72 00:06:18,083 --> 00:06:23,014 why is that? Well, we're overriding the value of x, so whatever value, x had 73 00:06:23,014 --> 00:06:27,034 before this statement is never gonna be read. Okay, Because the ee here, the 74 00:06:27,034 --> 00:06:32,005 right-hand side of the assignment, doesn't refer to x And, so, immediately before the 75 00:06:32,005 --> 00:06:36,088 statement, the current value of x is never gonna be used in the future. And so x is 76 00:06:36,088 --> 00:06:43,000 dead at that point. And finally, the last case is what if we have a statement that 77 00:06:43,000 --> 00:06:49,026 does not refer to x? Okay, So it neither reads no r writes x. Well, then whatever 78 00:06:49,026 --> 00:06:55,093 the line this is of x after the statement, it has the same liveness, before this 79 00:06:55,093 --> 00:07:05,017 statement. So if x is live here. Then x will be live here. Okay, and similarly, if 80 00:07:05,017 --> 00:07:10,077 x is dead After the statement. Then x must be dead before the statement. And that's 81 00:07:10,077 --> 00:07:15,124 because x if x is not use in the future after the statement S then it still want 82 00:07:15,124 --> 00:07:21,020 be use in the future before the statement S. Since the statement S neither reads nor 83 00:07:21,020 --> 00:07:25,065 write x. So those are the only four rules and now I can give the algorithm. So 84 00:07:25,065 --> 00:07:30,064 initially we left the liveness information for x be false at all program points And 85 00:07:30,064 --> 00:07:35,045 then we repeat the following until all the statements satisfy the rules one through 86 00:07:35,045 --> 00:07:40,032 four, and just has it's the same algorithm that we used for constant propagation. We 87 00:07:40,032 --> 00:07:44,097 pick some statement where the information is inconsistent and then up, update the 88 00:07:44,097 --> 00:07:50,046 information at that statement with the appropriate rule. So let's do a simple 89 00:07:50,046 --> 00:07:58,023 example, something with a loop. So let's begin, say by initializing x to zero, and 90 00:07:58,023 --> 00:08:05,062 then what should our loop body do? Well, we can check whether x is equal to ten, 91 00:08:05,062 --> 00:08:12,073 and if it is, we'll, we'll exit, the loop And let's assume that x is dead on exit. 92 00:08:12,073 --> 00:08:19,049 So x is not refer to outside of the loop. In other wise if x is not ten Then we will 93 00:08:19,049 --> 00:08:25,092 increment x and we'll branch back to the top of the loop. So this is a very, very 94 00:08:25,092 --> 00:08:31,096 silly little program. It just counts to ten and then exits. Well let's do the 95 00:08:31,096 --> 00:08:38,079 lightness now to see where x is life. So since x is dead here on exit it's clearly 96 00:08:38,079 --> 00:08:44,072 gonna be dead on the out Of, of this, conditional on this branch, Okay? So I 97 00:08:44,072 --> 00:08:50,042 should say that x is not live. So we're using [inaudible] here, so that's x's, 98 00:08:50,044 --> 00:08:57,065 liveness would be false And we're assuming And x is also, not live everyplace else, 99 00:08:57,065 --> 00:09:03,050 initially. Okay And so, there's a program point in there, also Where the liveness of 100 00:09:03,050 --> 00:09:08,043 x is false. Okay, So now, let's propagate the information. Well, so here we have 101 00:09:08,043 --> 00:09:13,056 read of x. And let me switch colors here. So here we have a read of x. So in fact 102 00:09:13,076 --> 00:09:19,002 the information's inconsistent here because ri ght before this statement since 103 00:09:19,002 --> 00:09:24,028 we have a read of x, x must be live. So in fact, x is live at this point. Now notice 104 00:09:24,028 --> 00:09:29,074 that this statement both reads and writes x. Okay? But the rule that says x is live 105 00:09:29,074 --> 00:09:35,337 before, when we do a read, takes priority here Because, the read happens before the 106 00:09:35,337 --> 00:09:41,012 write. So we'll read the old value of x, before we write the new value of x, Okay. 107 00:09:41,012 --> 00:09:46,060 So the old value of x does get used, and that's why x is live immediately before 108 00:09:46,060 --> 00:09:51,097 this statement. Okay, so then here's another, read of x. Okay, so on the, so 109 00:09:51,097 --> 00:09:58,027 the point immediately before this when I left out one program point here, x is also 110 00:09:58,027 --> 00:10:03,054 Y. Okay, And then following edges backwards, well, that means x is gonna be 111 00:10:03,054 --> 00:10:09,040 live on the back edge of the loop And it's also gonna be live by going into the 112 00:10:09,040 --> 00:10:14,077 initialization block. Alright? Now we come back around here and we see that we're 113 00:10:14,077 --> 00:10:19,091 done 'cause x is already known to be, live within the loop body. And now, live, x is 114 00:10:19,091 --> 00:10:24,051 also live here And then the question is, you know, what about this point on, the 115 00:10:24,051 --> 00:10:29,047 entrance, at the entrance to the control flow graph? Well, there's a right of x And 116 00:10:29,047 --> 00:10:34,025 with no read of x on the right-hand side. So, in fact, x, is not live on entry to 117 00:10:34,025 --> 00:10:38,091 this control flow graph. So in fact, x is dead at this point. So whatever value x 118 00:10:38,091 --> 00:10:43,046 has when we enter the control flow graph, it will never be used in the future. 119 00:10:43,046 --> 00:10:48,020 Alright, and so that is The correct [inaudible] in this information for every 120 00:10:48,020 --> 00:10:54,028 program point in this example. Now another thing you can see from our little example 121 00:10:54,028 --> 00:11:00,034 is that values change from false to true, but not the other way around. So every 122 00:11:00,034 --> 00:11:06,055 value starts at false, and it can change at most once. To say that the value is 123 00:11:06,055 --> 00:11:12,052 actually live, the property becomes true, and then it won't ever change back to 124 00:11:12,052 --> 00:11:17,084 false again. So, going back to orderings, We only have two values in this analysis, 125 00:11:17,084 --> 00:11:21,086 false and true And the ordering is that false is less than true. Okay, And we 126 00:11:21,086 --> 00:11:26,019 know, so everything starts at the lowest possible element of the ordering and they 127 00:11:26,019 --> 00:11:30,047 only move up, and so they can be promoted to true, but no t vice versa And so since 128 00:11:30,047 --> 00:11:34,054 each value can only change once, termination is guaranteed. That eventually 129 00:11:34,054 --> 00:11:38,061 we're guaranteed to have consistent information throughout the control flow 130 00:11:38,061 --> 00:11:45,012 graph, and the analysis will terminate. To wrap up and summarize our discussion of 131 00:11:45,012 --> 00:11:49,055 the global analysis of control flow graphs, we've talked about two kinds of 132 00:11:49,055 --> 00:11:53,092 analysis in the past several videos. Constant propagation is what is called a 133 00:11:53,092 --> 00:11:58,058 forwards analysis Because information is pushed from the inputs to the outputs. So 134 00:11:58,058 --> 00:12:03,039 if you think about a control flow graph. What happens in control flow analysis is 135 00:12:03,039 --> 00:12:08,004 that information flows in this direction. It flows in the same direction as 136 00:12:08,004 --> 00:12:13,036 computation. If I have a constant up here x is assigned constant down here, and x is 137 00:12:13,036 --> 00:12:18,044 used later on and that constant will flow forward to the uses. Okay So information 138 00:12:18,044 --> 00:12:22,096 flows in the same direction as computation. Liveness on the other hand is 139 00:12:22,096 --> 00:12:27,067 a backwards analysis. Information is pushed from outputs back towards inputs. 140 00:12:27,067 --> 00:12:33,012 So here in this example and let me change colors. Here we see that x is live before 141 00:12:33,012 --> 00:12:38,028 the statement. And that liveness gets propagated in the other direction. It gets 142 00:12:38,028 --> 00:12:43,025 propagated [inaudible] against the control, against the flow, of execution, 143 00:12:43,025 --> 00:12:48,055 backwards towards the beginning of the program. So they're many other kinds of 144 00:12:48,055 --> 00:12:52,088 global flow analysis in the literature. The constant propagation analysis and the 145 00:12:52,088 --> 00:12:56,095 liveness analysis are two of the most important. There is a number of others 146 00:12:56,095 --> 00:13:01,012 that are also very important and many, many more that people have investigated. 147 00:13:01,027 --> 00:13:05,023 Almost all these analyses can be classified as either forward or backward. 148 00:13:05,023 --> 00:13:09,035 There are some analyses and some important ones that are neither forward nor 149 00:13:09,035 --> 00:13:13,073 backward. That information is basically pushed in both directions. And the other 150 00:13:13,073 --> 00:13:18,001 thing is that the, almost all the analyses in the literature that do global flow 151 00:13:18,001 --> 00:13:21,095 analysis anyway also follow this methodology of local Rules that relay 152 00:13:21,095 --> 00:13:26,062 information between adjacent program points. So it, it's the local rules part 153 00:13:26,062 --> 00:13:30,632 that's important. So we break down the complicate d problem of analyzing an 154 00:13:30,632 --> 00:13:35,349 entire control flow graph into a collection of rules that only do ver, 155 00:13:35,349 --> 00:13:38,005 propagate information very, very locally.