1 00:00:04,059 --> 00:00:08,075 In this video we are going to continue our discussion on global data flow analysis by 2 00:00:08,075 --> 00:00:16,038 taking a look at how global constant propagation works in detail. To begin, 3 00:00:16,038 --> 00:00:21,012 let's review what the conditions are to do global constant propagation. So to replace 4 00:00:21,012 --> 00:00:26,055 a use of a variable x by a constant k, we have to know the following property. That 5 00:00:26,055 --> 00:00:30,953 on, that on every path to the use of x, the last assignment to the variable x is, 6 00:00:30,953 --> 00:00:35,801 x equals the constant k, okay? And this has to be true again on every path to the 7 00:00:35,801 --> 00:00:43,062 use of x. Now, global constant propagation can be performed at any point where this 8 00:00:43,062 --> 00:00:47,088 property holds. What we're going to look at in this video, is the case of computing 9 00:00:47,088 --> 00:00:53,086 the property for a single variable x at all program points. So we're going to take 10 00:00:53,086 --> 00:00:56,093 one, we're going to focus on one variable x and we're going to compute whether it's 11 00:00:56,093 --> 00:01:01,083 a constant at every program point. It's easy to extend the algorithm to compute 12 00:01:01,083 --> 00:01:06,083 this property for all variables. One very simple but very efficient way to do that 13 00:01:06,083 --> 00:01:15,022 is just to repeat the computation once for each variable in the method body. The way 14 00:01:15,022 --> 00:01:19,062 we are going to compute the information that we want is to associate one of the 15 00:01:19,062 --> 00:01:25,069 following values with the variable x at every point in the program. And, let's 16 00:01:25,069 --> 00:01:32,024 start with the last one here we will assign x this special value here which is 17 00:01:32,024 --> 00:01:38,093 pronounced top if x is not a constant. So if we can't figure out whether x is a 18 00:01:38,093 --> 00:01:43,017 constant at a particular point in the program, then we'll just say x is top at 19 00:01:43,017 --> 00:01:49,078 that point. And, this is going to be our safe situation. It's always okay to say we 20 00:01:49,078 --> 00:01:53,714 don't know what the value of x is and when we say that x has a value top, and we 21 00:01:53,714 --> 00:01:58,614 could say, we, we were essentially saying we don't know whether x is a constant or 22 00:01:58,614 --> 00:02:03,002 not at this point in the program, x could have any value. Alright? Now, another 23 00:02:03,002 --> 00:02:08,020 possibility is that we will say that x is some constant c, okay? So this is a 24 00:02:08,020 --> 00:02:12,043 particular constant and if we say that x is a constant c at a program point, that 25 00:02:12,043 --> 00:02:17,025 means, in fact, at that program point, we believe o r we have proven that x is 26 00:02:17,025 --> 00:02:24,794 always that constant. Now, there is a third possibility which is not immediately 27 00:02:24,794 --> 00:02:29,768 intuitive, perhaps. But, as we will see, plays a very important role in algorithms 28 00:02:29,768 --> 00:02:35,438 for, for global constant propagation. And in fact, in all global data flow analysis, 29 00:02:35,438 --> 00:02:42,198 and that is bottom, okay? So this value is pronounced bottom and intuitively the idea 30 00:02:42,198 --> 00:02:48,827 anyway that is kind of opposite of top, alright? And the interpretation of bottom 31 00:02:48,827 --> 00:02:55,011 is going to be that this statement never executes, alright? So, when we don't know 32 00:02:55,011 --> 00:03:01,239 whether a statement is even executed at all we will say that x at that point has a 33 00:03:01,239 --> 00:03:05,536 value bottom. Meaning that, as far as we know that point in the program is never 34 00:03:05,536 --> 00:03:09,364 reached. It doesn't matter what the value of x is at that point because that 35 00:03:09,364 --> 00:03:14,461 statement never executes. Alright, so we're going to assign x one of these three 36 00:03:14,461 --> 00:03:20,430 kinds of values. Either bottom, some constant, or top. Let's begin by working 37 00:03:20,430 --> 00:03:26,990 through an example by hand and our goal is going to be for every program point to 38 00:03:26,990 --> 00:03:32,251 decide whether x could be a constant definitely not a constant, or whether we 39 00:03:32,251 --> 00:03:37,565 think that statement might not ever execute, okay? So, execution will begin at 40 00:03:37,565 --> 00:03:42,736 the top of this control flip graph. So this the entry point and before executions 41 00:03:42,736 --> 00:03:48,247 begins, we don't anything about the value of x. So, I'm not making any assumptions 42 00:03:48,247 --> 00:03:53,889 about what code came before this basic block and so to be safe, I will say that 43 00:03:53,889 --> 00:03:59,415 at this point, x has some unknown value. We don't know what the value of x is, it 44 00:03:59,415 --> 00:04:05,110 could be anything. So x = T, is the property that we want entry to the first 45 00:04:05,110 --> 00:04:10,788 basic block. Now after the assignment x = three, that was indicated there, where 46 00:04:10,788 --> 00:04:14,741 what point we're talking about. So, after the assignment x = three, we'll definitely 47 00:04:14,741 --> 00:04:19,289 will know that x is the constant three. Alright, now there's something here that's 48 00:04:19,289 --> 00:04:22,097 worth pointing out which is that our program points, the points that we're 49 00:04:22,097 --> 00:04:28,461 attaching this knowledge to or these, these facts to are in between the statem 50 00:04:28,461 --> 00:04:32,921 ents. So, when I say x = three at this program point, what I mean is that after 51 00:04:32,921 --> 00:04:38,088 x, after this assignment has executed, x = three, but before this predicate of the 52 00:04:38,088 --> 00:04:45,425 conditional has executed, I know that x = three, okay? So, the program points are in 53 00:04:45,425 --> 00:04:49,689 between statements and there's a program point before and after every statement. 54 00:04:49,689 --> 00:04:54,506 Alright, so the next thing that happens is this conditional branch. Notice that the 55 00:04:54,506 --> 00:04:58,839 branch doesn't update x, doesn't even refer to x so after the branch executes 56 00:04:58,839 --> 00:05:04,713 we'll definitely knows that x = three on both branches. Alright, now let's do the 57 00:05:04,713 --> 00:05:08,748 right hand branch. The next thing that happens is the assignment to y that would 58 00:05:08,748 --> 00:05:13,527 not affect the value of x. So after the assignment to y, we'll still know that x = 59 00:05:13,527 --> 00:05:18,084 three, alright? Now let's take a look at the left hand branch so the first thing 60 00:05:18,084 --> 00:05:22,066 that happens over here is another assignment to y. Well that won't affect 61 00:05:22,066 --> 00:05:27,719 the value of x. After the assignment of Y we'll know that x = three. And now comes 62 00:05:27,719 --> 00:05:31,801 to the assignment of x, alright. So after this assignment happens at this program 63 00:05:31,801 --> 00:05:36,002 point we're going to know that the value of x is different. We're going to know 64 00:05:36,002 --> 00:05:41,382 that x = four, alright. So, now after this statement we know x = four and after this 65 00:05:41,382 --> 00:05:47,401 statement over here we know x = three, alright? Now what do we know then about 66 00:05:47,401 --> 00:05:52,086 what happens before this statement, okay? The a = two x and I just want to point 67 00:05:52,086 --> 00:05:59,004 out here. I said that there's a program point before and after every statement And 68 00:05:59,004 --> 00:06:04,085 so this program point here, which is before this assignment to a is different 69 00:06:04,085 --> 00:06:09,599 from the program points that are after x = four and y = zero. So intuitively, after x 70 00:06:09,599 --> 00:06:15,298 = four we know that we're still on this path over here on the left and so we know 71 00:06:15,298 --> 00:06:19,692 that x = four and over here after y = zero, we still know that we're on this 72 00:06:19,692 --> 00:06:24,166 path is x = three. But, when we reach the point before a = two x, we no longer 73 00:06:24,166 --> 00:06:29,585 know which path we're coming from. This is the point of the merge of these two paths 74 00:06:29,585 --> 00:06:34,476 that both lead to this statement. And what can we say about the value of x here? 75 00:06:34,476 --> 00:06:39,346 Well, there is no constant that we can assign to x because on o ne path x is 76 00:06:39,346 --> 00:06:44,016 three and on the other path, x is four. And so what we have to say here is that 77 00:06:44,016 --> 00:06:50,027 before this assignment executes, a = x, sorry, x = T. We don't know what the value 78 00:06:50,027 --> 00:06:55,149 of x is. Another way of saying it is we know we, we don't know that x is a 79 00:06:55,149 --> 00:07:00,163 constant, alright. So, after the assignment executes it doesn't affect the 80 00:07:00,163 --> 00:07:06,569 value of x, we will also have that x = T. Now notice that once we have the global 81 00:07:06,569 --> 00:07:12,768 constant information, once we know for every program point, what the state of x 82 00:07:12,768 --> 00:07:18,231 is, it's going to be very easy to perform the optimization. We simply look at the 83 00:07:18,231 --> 00:07:23,037 information associated with the statement and then it will tell us whether x is a 84 00:07:23,037 --> 00:07:28,290 constant when that statement executes or not. And if x is a constant at that point, 85 00:07:28,290 --> 00:07:34,077 then we can replace that use of x by the constant. And crucial question of course 86 00:07:34,077 --> 00:07:39,335 is how do we compute these properties. So, we did this example by hand but how in a 87 00:07:39,335 --> 00:07:44,337 systematic fashion, an arbitrary control flow graph do we actually compute these 88 00:07:44,337 --> 00:07:49,483 properties for x for every program point? Now we're ready to talk about data flow 89 00:07:49,483 --> 00:07:54,407 analysis algorithms and there's one basic principle that you see in all of these 90 00:07:54,407 --> 00:07:59,350 algorithms that's worth mentioning right away. And that's that the analysis of a 91 00:07:59,350 --> 00:08:05,177 complicated program can be expressed as a combination of very simple rules that 92 00:08:05,177 --> 00:08:09,624 relate the change in information between adjacent statements. So we're just going 93 00:08:09,624 --> 00:08:14,350 to focus on local rules and the way we're going to build our global data flow 94 00:08:14,350 --> 00:08:19,587 analysis is actually by a combination of rules that look only at a single statement 95 00:08:19,587 --> 00:08:26,052 and its neighbors. The idea behind the rules is going to be the push or transfer 96 00:08:26,052 --> 00:08:30,089 information from one statement to the next And so for each statement s, we're going 97 00:08:30,089 --> 00:08:35,031 to compute information about the value of x immediately before and after s. Remember 98 00:08:35,031 --> 00:08:39,068 that's where, those are the program points that we want to attach information to. So 99 00:08:39,068 --> 00:08:43,052 in particular we're going to have a function C. It stands for constant 100 00:08:43,052 --> 00:08:47,047 information and C will take three arguments, takes the name of the variable, 101 00:08:47,047 --> 00:08:51,073 x. It takes the stat ement that we're talking about, the particular statement in 102 00:08:51,073 --> 00:08:56,047 the program that we're looking at. And then either in or out and this is what 103 00:08:56,047 --> 00:09:02,096 distinguishes the value of x before s executes versus the value of x after s 104 00:09:02,096 --> 00:09:07,096 executes. We're going to be defining a set of transfer functions that push 105 00:09:07,096 --> 00:09:12,097 information or transfer information from one statement to another. And in the rules 106 00:09:12,097 --> 00:09:18,016 for constant propagation we need to talk about a statement and its predecessors. So 107 00:09:18,016 --> 00:09:23,024 we're going to say that every statement s has some set of immediate predecessors p1 108 00:09:23,024 --> 00:09:28,037 through pn, alright? So, it's either of these statements that lead in one step to 109 00:09:28,037 --> 00:09:36,016 the statement s. Let's do our first rule. So we have a statement s and it has some 110 00:09:36,016 --> 00:09:42,083 set of predecessor statements, P1, P2, P3, P4. And the situation that we're 111 00:09:42,083 --> 00:09:48,596 interested in here is, let's assume that x is top at the program point after one of 112 00:09:48,596 --> 00:09:54,053 these predecessors. So, after some predecessor, it doesn't matter which one, 113 00:09:54,053 --> 00:10:01,139 if it happens that x is top at the program point after that predecessor, well, then x 114 00:10:01,139 --> 00:10:07,108 has to be top before the execution of s, okay? So that's what this rule says. It 115 00:10:07,108 --> 00:10:13,107 says if the out of any predecessor for x is top, then the in of s for x is also 116 00:10:13,107 --> 00:10:18,011 top. Alright, and this makes sense. It says that if we don't know whether x is a 117 00:10:18,011 --> 00:10:22,642 constant on some path that leads to s, well then, we don't know that x is a 118 00:10:22,642 --> 00:10:27,678 constant at s. Because for all we know, execution came down that particular, came 119 00:10:27,678 --> 00:10:33,032 from that particular predecessor and so, we can't make any prediction about whether 120 00:10:33,032 --> 00:10:38,907 s is, whether x is a constant before s executes. Now let's look at another 121 00:10:38,907 --> 00:10:44,673 situation. Let's say that x is some constant C after the execution of some 122 00:10:44,673 --> 00:10:51,248 predecessor. And that on a, after another predecessor a distinct predecessor x is a 123 00:10:51,248 --> 00:10:57,241 different constant D. So D is not equal to C. Well then what do we know about x at 124 00:10:57,241 --> 00:11:02,965 the program point before s executes? Well, we don't know anything, x has to be top, 125 00:11:02,965 --> 00:11:08,219 because we don't know which constant, s will be, since we don't know which path 126 00:11:08,219 --> 00:11:14,414 will reach s at run time. And this is the situation that we saw in the example we 127 00:11:14,414 --> 00:11:20,013 did by hand. Another possibility is that the predecessors all agree on what the 128 00:11:20,013 --> 00:11:25,426 value of x could be. So let's say that we have, you know, predecessor here and that 129 00:11:25,426 --> 00:11:30,015 after it executes x is known to be the constant C and x is known to be the 130 00:11:30,015 --> 00:11:34,858 constant C after this predecessor and x is known to be the constant C after this 131 00:11:34,858 --> 00:11:39,160 predecessor. There's one other possibility. Let's say that after this 132 00:11:39,160 --> 00:11:45,097 predecessor over here, all we know is that x is bottom, okay? And so what the rule 133 00:11:45,097 --> 00:11:50,623 says is that if we have this situation where either x has the property bottom 134 00:11:50,623 --> 00:11:55,084 after a predecessor or all the predecessors agree on the particular 135 00:11:55,084 --> 00:12:01,064 constant that x could be, then before at the program point before s executes, we 136 00:12:01,064 --> 00:12:07,114 know that x is going to guarantee to be the constant C. And if you think about it 137 00:12:07,114 --> 00:12:12,651 for a second, it's easy to see why this is correct. First of all, clearly if we come 138 00:12:12,651 --> 00:12:18,710 along one of the paths where x is known to be the constant C, since they all agree 139 00:12:18,710 --> 00:12:23,353 and then when we get to s, x will definitely have the value C. What about 140 00:12:23,353 --> 00:12:27,771 the bottom case? Well, remember what that means. That means that this statement is 141 00:12:27,771 --> 00:12:32,869 never reached so there's some predecessor P here which never executes. Which means 142 00:12:32,869 --> 00:12:37,097 if P never executes then we could never reach S along this path from P. So the 143 00:12:37,097 --> 00:12:42,441 only paths that will reach s are the ones where x is known to be a constant, 144 00:12:42,441 --> 00:12:48,269 alright? So that's why it's okay in this situation say that x, if control if 145 00:12:48,269 --> 00:12:54,257 execution reaches s at all its guaranteed to reach it in a state where x is the 146 00:12:54,257 --> 00:13:00,496 constant C. One last possibility is let's say that x is bottom for all the 147 00:13:00,496 --> 00:13:06,050 predecessors, okay? And what does that mean? Well, that means that every 148 00:13:06,050 --> 00:13:12,541 predecessor of S never executes so they're all unreachable. And therefore if every 149 00:13:12,541 --> 00:13:19,880 predecessor of x never executes s itself can never execute, and so we can conclude 150 00:13:19,880 --> 00:13:25,947 that entry to s, x is bottom. The first four rules that we just looked at relate 151 00:13:25,947 --> 00:13:30,832 the out of one statement to the in of the next. We also have to have rules that 152 00:13:30,832 --> 00:13:35,989 relate the in of a statement to the out of the same statement. So we have to push 153 00:13:35,989 --> 00:13:41,518 information from the input of a statement to the output of the same statement. So, 154 00:13:41,518 --> 00:13:46,858 once again, there are several cases. And let's take a look at an easy one first. If 155 00:13:46,858 --> 00:13:52,279 x is bottom on an entry s, if the program point before s well, that says that at 156 00:13:52,279 --> 00:13:58,392 the, that s is never reached, that s never executes. And therefore, x will be bottom 157 00:13:58,392 --> 00:14:03,245 after s, after s as well. So if the program point before s is never reached, 158 00:14:03,245 --> 00:14:08,402 the program point after s definitely can't be reached either. Another possibility is 159 00:14:08,402 --> 00:14:13,791 that we're assigning x to constant C in this statement. In that case the out of 160 00:14:13,791 --> 00:14:19,053 the statement is going to be equal to C. Alright, so it doesn't matter what the 161 00:14:19,053 --> 00:14:24,094 state of x was before the statement, after we execute the statement, x will be the 162 00:14:24,094 --> 00:14:29,086 constant C. And I should say there is a conflict with the previous rule. Okay, it 163 00:14:29,086 --> 00:14:35,027 could be that x is bottom, before the statement. So rule six, has lower priority 164 00:14:35,027 --> 00:14:40,043 than rule five. So we, so if we could say that x is bottom after the statement, we 165 00:14:40,043 --> 00:14:45,053 would prefer you to say that so rule five would be applied first, and then if rule 166 00:14:45,053 --> 00:14:50,759 five does not apply. So if x is some other constant D or x = T, then we would apply 167 00:14:50,759 --> 00:14:55,389 this rule and we would conclude that x is the constancy afterwards and that makes 168 00:14:55,389 --> 00:14:59,842 sense. If x is d or x is the, is top that means that control, as far as we know, can 169 00:14:59,842 --> 00:15:04,201 reach this statement. And then what we're saying here is that well, after the 170 00:15:04,201 --> 00:15:08,252 execution of this statement, if control can reach this statement after the 171 00:15:08,252 --> 00:15:13,517 execution of it, x is guaranteed to be the constant C. Another possibility is that we 172 00:15:13,517 --> 00:15:19,071 have an assignment to x but the right hand side is more complicated than a constant. 173 00:15:19,071 --> 00:15:24,524 So this case is for everything other than the constant assignment. Okay, so this F 174 00:15:24,524 --> 00:15:29,492 here just stands for some more complicated expression than just a simple constant. 175 00:15:29,492 --> 00:15:34,515 And in this case we, we're just going to say we don't know what the value is, we're 176 00:15:34,515 --> 00:15:39,734 not going to try to guess what the result of that computation is and we'll just say 177 00:15:39,734 --> 00:15:44,781 that x = T. X, w e don't know what the value of x is after the execution of this 178 00:15:44,781 --> 00:15:50,038 statement. And once again, rule five takes precedence so if rule five applies, then 179 00:15:50,038 --> 00:15:54,164 we would apply then, then we would use that rule instead of rule seven. But, if 180 00:15:54,164 --> 00:16:01,567 control can reach this statement, so up here x = C or x = T. Then we'll apply rule 181 00:16:01,567 --> 00:16:07,548 seven and conclude that x is top after the statement. And finally Rule eight, another 182 00:16:07,548 --> 00:16:14,559 possibility is that we're assigning to some variable other than x. And in that 183 00:16:14,559 --> 00:16:22,175 case, if x = k before the statement then we just keep that value. Okay, so whatever 184 00:16:22,175 --> 00:16:27,326 x was before the statement bottom, a constant or top, if the assignment is to 185 00:16:27,326 --> 00:16:34,100 some other variable other than x then x will have the same property after the 186 00:16:34,100 --> 00:16:40,407 statement executes. Now, we can put these rules together into an algorithm. For 187 00:16:40,407 --> 00:16:45,328 every entry point, for every entry, statement to the program, we're going to 188 00:16:45,328 --> 00:16:51,255 say on entry that we don't know anything about the value of x. So the program point 189 00:16:51,255 --> 00:16:57,386 before that entry point we're gonna say that x has an unknown value, top. And then 190 00:16:57,386 --> 00:17:03,166 everywhere else we're going to say that the value of x, is bottom, okay. And this 191 00:17:03,166 --> 00:17:08,738 is actually important so we're going, what this intuitively is doing is its saying 192 00:17:08,738 --> 00:17:13,367 well, as far as we know except for the entry point to the program, which can 193 00:17:13,367 --> 00:17:17,448 definitely be executed, we don't know whether any of the other statements in the 194 00:17:17,448 --> 00:17:22,051 control flow graph are actually ever executed and so we're going to assume 195 00:17:22,051 --> 00:17:26,134 initially, that they're not. And we're just going to say that x has the value 196 00:17:26,134 --> 00:17:31,144 bottom everywhere except at an entry point And now what we're going to do is a kind 197 00:17:31,144 --> 00:17:35,241 of constraint satisfaction algorithm. We're going to pick some statement that 198 00:17:35,241 --> 00:17:39,074 doesn't satisfy one of the rules, one through eight. And then we're going to 199 00:17:39,074 --> 00:17:44,029 update it using the appropriate rules. So we'll look for places in the control flow 200 00:17:44,029 --> 00:17:47,914 graph where the information is inconsistent according to the rules and 201 00:17:47,914 --> 00:17:53,201 then we'll update, the information to make it consistent with the rules. Let's take a 202 00:17:53,201 --> 00:17:59,364 look at our example again. So, we're going to start out by saying x = T at the entry 203 00:17:59,364 --> 00:18:04,053 point, and then we're going to have all of our other program points And let me 204 00:18:04,053 --> 00:18:09,090 indicate them here. Okay, so these are all the other program points that we have to 205 00:18:09,090 --> 00:18:14,080 be concerned with. And there again, there's a program point before and after 206 00:18:14,080 --> 00:18:26,601 every statement. And we are going to say the x = bottom for all of these. So, again 207 00:18:26,601 --> 00:18:31,413 what this means is, that as far as we know, control doesn't reach any of these 208 00:18:31,413 --> 00:18:36,068 points. We have not yet proven to ourselves that any of these statements can 209 00:18:36,068 --> 00:18:41,738 execute. And now we just look around in the program and try to find places, where 210 00:18:41,738 --> 00:18:46,092 the information is inconsistent according to the rules, and then we update the 211 00:18:46,092 --> 00:18:51,082 information. Let me switch colors here. So, when we begin, the information is 212 00:18:51,082 --> 00:18:57,227 consistent everywhere except at this first statement because if x is T before and 213 00:18:57,227 --> 00:19:01,554 we're assigning x to value three. Well, then we should not have x = bottom as the 214 00:19:01,554 --> 00:19:06,757 result. In fact this should be x = three. It should be the appropriate information 215 00:19:06,757 --> 00:19:11,659 here and once we update that, then we see that this next statement is inconsistent 216 00:19:11,659 --> 00:19:16,285 because now we know this statement is reachable. We have a statement here and 217 00:19:16,285 --> 00:19:20,934 we're concluding that the point after is not reachable which is not, not correct 218 00:19:20,934 --> 00:19:25,743 according to the rules. So that I believe that this is an application of rule eight. 219 00:19:25,743 --> 00:19:30,751 We have a statement here that doesn't refer to x as and so whatever the value of 220 00:19:30,751 --> 00:19:36,109 x was before the statement becomes the value of x after the statement so that 221 00:19:36,109 --> 00:19:42,092 becomes x = three. And then, now we can see that this information is inconsistent. 222 00:19:42,092 --> 00:19:46,822 The out of the statement here, is not consistent with the in of the statement 223 00:19:46,822 --> 00:19:51,440 here. In this case, you know, it's just one predecessor. And so, the, the value 224 00:19:51,440 --> 00:19:57,307 should be the same so x should be three. At this point And similarly x should be 225 00:19:57,307 --> 00:20:00,483 three at this point. Here we have an assignment to a variable other than x. 226 00:20:00,483 --> 00:20:05,605 That should, information should be the same before and after the statements, same 227 00:20:05,605 --> 00:20:10,441 thing here. Now we have an assignment x. The point before that assignment is 228 00:20:10,441 --> 00:20:16,603 reachable and so sin ce this is a constant assignment we should know that x is that 229 00:20:16,603 --> 00:20:22,402 constant after the assignment. So here again we have a in and out issue so the 230 00:20:22,402 --> 00:20:27,638 out of this statement is not consistent with the in of this statement. So this is 231 00:20:27,638 --> 00:20:32,245 going to have to be updated but now, what should this be? Well, we have two 232 00:20:32,245 --> 00:20:37,831 inconsistent predecessors and so this has to be top and then finally, an assignment 233 00:20:37,831 --> 00:20:43,375 to x, sorry, an assignment to a state, to a variable other than x so the information 234 00:20:43,375 --> 00:20:49,526 should just propagate across. And that, same is updated like this so now x is 235 00:20:49,526 --> 00:20:54,176 known to be top afterwards. And now, if we look around at all the program points, 236 00:20:54,176 --> 00:20:58,149 we'd see that all the information is consistent. All the rules, if you, if you, 237 00:20:58,149 --> 00:21:02,367 if you check whether the information before and after a statement or across a 238 00:21:02,367 --> 00:21:06,483 statement. I'm sorry, or between predecessors and successors is correct, 239 00:21:06,483 --> 00:21:10,035 it's correct everywhere according to the rules and so we're done.