[CS61C FA20] Lecture 13.3 - Compilation, Assembly, Linking, Loading: Assembler — Transcript

Full transcript

1. 0:00and welcome back so one down three to go
2. 0:03let's take a look at what the assembler
3. 0:05does so again here we are in the big
4. 0:08picture
5. 0:08the assembler's job is to take in the
6. 0:10desk file that's that assembly language
7. 0:12program the risk five that you've
8. 0:13written that you're learning to write
9. 0:14from the last couple of weeks
10. 0:16and the goal is to produce object code.o
11. 0:19and you're going to ask yourself and
12. 0:20hopefully you'll see from this
13. 0:21why do we do this why don't we just go
14. 0:22straight from the assembler to produce
15. 0:24the actual executable you're going to
16. 0:26see what there's a two-step process and
17. 0:28it does help to have
18. 0:29a layer of linking in there we'll
19. 0:31explain that a little later
20. 0:32so again the input to the system of the
21. 0:35assembler is dot s file that's risk five
22. 0:37if you're in that isa the output is
23. 0:40object code
24. 0:41and this is gonna take contain tables
25. 0:43and really that's the reason the reason
26. 0:44we don't just go straight there because
27. 0:45we want these
28. 0:46information tables to be able and part
29. 0:48of this is to be able to have
30. 0:51lots of different lots a big program
31. 0:54broken into lots of.c files
32. 0:56each of the dot cs compiles down to dot
33. 0:58os and then those.os at the last stage
34. 1:00are linked together to make one
35. 1:01executable
36. 1:02and that is really the benefit of having
37. 1:04these three layers we'll talk about that
38. 1:05when we see that picture
39. 1:07so the assembler also is going to read
40. 1:09and use directives we'll talk about that
41. 1:10in a slide or two
42. 1:12replace the pseudo instructions you
43. 1:13learned about that last last lecture
44. 1:15the pseudo instructions like move t1 t2
45. 1:18gets replaced by the add-i
46. 1:19instruction our goal is to produce the
47. 1:22machine language.o files
48. 1:23and create create the object file so
49. 1:26what are some directives that we have
50. 1:28so some of the directors we have are
51. 1:31here listed here these five directives
52. 1:33tell the system it's not a line it's
53. 1:35like a directive it's not a lie i mean
54. 1:36it is a line it takes up a line in the
55. 1:38code but
56. 1:39it says what to do at each of these
57. 1:40stages so
58. 1:43dot text says the following from here
59. 1:45till the next time you see a directive
60. 1:47this is going to go in the text segment
61. 1:49that's the machine code that's the
62. 1:50actual code that you ran
63. 1:51you ran this down and the actual hello
64. 1:54world add one to two
65. 1:55subtract load word that is down in the
66. 1:58dot text segment
67. 2:00the dot data says to it from the the
68. 2:02following is going to be data i'm going
69. 2:04to use if you have a big array that'll
70. 2:05live in the dot data section
71. 2:08dot global with the symbol says this is
72. 2:10where this is the space
73. 2:12in the static area where the following
74. 2:14symbol is going to live
75. 2:17dot string says the following is just
76. 2:19text string
77. 2:20take it literally as that you'll see
78. 2:22that at the end of the lecture of that
79. 2:24and dot word if i want to store some
80. 2:26values there
81. 2:27some raw memory words i'm going to store
82. 2:29those in the dot word area and label it
83. 2:31as such
84. 2:33so here's we saw the first one we saw
85. 2:35the first example of a move which which
86. 2:37gets translated to an add-i that's not
87. 2:39magical you saw that before how about
88. 2:42negate
89. 2:43i take t1 and negate it it was a
90. 2:44positive 5 i want to make it negative 5.
91. 2:46kind of nice i don't worry about how to
92. 2:48do that here's how you do that you take
93. 2:50you take zero you subtract t1 from it
94. 2:53and now that's
95. 2:54zero minus t1 is negative t1 store that
96. 2:56in t0
97. 2:57same idea as negate but a little easier
98. 2:59to write in the gate than it is to write
99. 3:00the sub thing and get the maybe got the
100. 3:02order wrong i just call it negate
101. 3:04negate t1 put it in t0 next
102. 3:07load immediate li that says load this
103. 3:10immediate and directly put it into t0
104. 3:12now you can realize that that's the same
105. 3:14as saying add i immediate
106. 3:16to zero and then put into zero but it's
107. 3:18kind of nice to have just load immediate
108. 3:20directly
109. 3:21how about not this is the bitwise knot
110. 3:25this isn't not a single bit this is 32
111. 3:28bits of not
112. 3:29okay so how do you do that well you xor
113. 3:32with minus one what does minus one look
114. 3:34like
115. 3:35you know what minus one looks like in in
116. 3:38two's complement
117. 3:39yeah all ones all ones all
118. 3:42ones so you take all ones and if you xor
119. 3:45with that immediate
120. 3:46xor says if it's a zero keep it xor says
121. 3:50if it's a one
122. 3:50flip the bit so this flips the bits of
123. 3:53all of t1
124. 3:54and all of t1 bits get flipped and get
125. 3:57stored into t0
126. 3:58pretty cool so now you get to say not
127. 4:00and that's a 32-bit wise
128. 4:02knot love it branch of equal to z
129. 4:06zero if t zero
130. 4:09is zero then you branch if that's equal
131. 4:11to that so your branch of t zero is
132. 4:13equal to zero
133. 4:14i mean nice branch of the loop so here's
134. 4:16another way of saying it
135. 4:18branch of equal t zero to zero it does z
136. 4:21t zero equals zero if so branch to the
137. 4:25loop
138. 4:25same idea of saying branch of equal to
139. 4:27zero to zero just again a short shortcut
140. 4:29way of doing that i'd much rather write
141. 4:31the code on the left than the code on
142. 4:32the right
143. 4:33and that's what's nice about having
144. 4:34these pseudo instructions load address
145. 4:37so i've got an address here and i want
146. 4:40to store that in t0 where does this live
147. 4:42where does that label live load that
148. 4:44address into t0
149. 4:46sounds great well there's two ways of
150. 4:48doing it you can load
151. 4:49upper immediate which loads 20 bits into
152. 4:53t0 okay so i'm going to take the 20 bits
153. 4:55the upper 20 bits of that of that label
154. 4:58and put it into t0
155. 4:59and i said you know what now i also need
156. 5:02to stuff the lower 12 bits
157. 5:03how do i so now i've i've kind of
158. 5:05slammed in 20 bits on the high side
159. 5:07how do i store the lower 12 bits well
160. 5:10add i
161. 5:11you know this it kind of makes sense
162. 5:13right you know that there's no way
163. 5:16for me to in one instruction take 32-bit
164. 5:19not only have the instruction have the
165. 5:21register label and have the string
166. 5:22itself
167. 5:23i mean have the have the label itself
168. 5:24that doesn't make any sense so i
169. 5:26say i'm going to take the top 20 bits do
170. 5:29it in one stage and then
171. 5:30add i the lower 12 bits by saying add i
172. 5:33that to t0 and put it there so that's it
173. 5:37or
174. 5:38i could do another thing both of these
175. 5:40are similar but they're different
176. 5:41in a subtle way add upper media to the
177. 5:43pc this is a pc relative operation
178. 5:46same idea so the same the bottom is the
179. 5:48same this is the same but add
180. 5:49uppermediate is a pt
181. 5:51pc relative operation again two ways to
182. 5:53say load address one is more static
183. 5:55addressing and one is pc relative
184. 5:57addressing
185. 5:59so let's don't forget the following
186. 6:02we've got to sign extend our immediates
187. 6:04so this is an immediate
188. 6:06this is an immediate uh this is an
189. 6:08immediate here
190. 6:09this is an immediate okay those have to
191. 6:11be sign extended because
192. 6:12at i in the actual data path and when we
193. 6:15build the machine we're gonna see this
194. 6:16in the next lectures when we build the
195. 6:18machine out of this
196. 6:19i can't just add 12 bits i've got to add
197. 6:2132 bits to 32 bits to get 32 bits
198. 6:23so how do i take a 12 bit value and make
199. 6:25it 32 i've got to sign extend those guys
200. 6:28don't forget also this is another
201. 6:30important part that when i'm branching
202. 6:32i'm counting by the half words that's
203. 6:35one of the risk five features
204. 6:37some some might say miss features where
205. 6:38you're counting by the half words not
206. 6:40the words so
207. 6:42all right so now you've seen we've done
208. 6:45the first stage we should
209. 6:46replace our pseudo instructions the next
210. 6:49step is we've got to produce some
211. 6:50machine code
212. 6:51okay so the object file so what do we do
213. 6:55for my object code well if i've got some
214. 6:57simple cases the simple cases is always
215. 6:59the ads the add subtracts logical shifts
216. 7:01they're just numbers
217. 7:03we can play with that and all the
218. 7:04information i need is in the instruction
219. 7:0632 bits tells me everything i need to
220. 7:08know don't need to do much about those
221. 7:10what happens when i get to branches and
222. 7:12jumps well those are pc relative
223. 7:14okay whenever you have pc relative you
224. 7:16got to query what the pc is and then use
225. 7:17that somewhere
226. 7:18in that process so here's the nice thing
227. 7:21about that once my pseudo instructions
228. 7:23have been replaced by real ones
229. 7:24sometimes one becomes two instructions
230. 7:26you saw that before
231. 7:27once that's been done i know the
232. 7:28relative distance between where i am and
233. 7:30where
234. 7:30to where i want to go so if i have a
235. 7:33branch of equal and i need to be
236. 7:34counting by those half words
237. 7:36i can now i know exactly how far away
238. 7:39to be able to then count by half words
239. 7:41how many how many half words to jump
240. 7:42there
241. 7:43to branch there and then replace that
242. 7:45number so i actually can replace that
243. 7:46number i'm pretty happy with that
244. 7:48so those are handleable meaning at the
245. 7:49out when i'm done with when i'm done
246. 7:51with the dot oh file
247. 7:52those final values are there i don't
248. 7:53need to count wait for someone later
249. 7:55stage
250. 7:55so i can just count those numbers put
251. 7:57those numbers in that field and i'm done
252. 7:59how many half words do i need to branch
253. 8:00i'm done so that's actually easy
254. 8:02so far this is the easy case this is
255. 8:06one of the so this is one of the
256. 8:06challenges we have
257. 8:09what if i'm branching forward
258. 8:12well that's nice you can should be able
259. 8:14to branch anywhere right i should be
260. 8:15able to go here and branch there and
261. 8:16branch there
262. 8:17you know if i had a go to that's kind of
263. 8:19a different thing but the point is i
264. 8:20want to branch i want to do a branch
265. 8:21here and i have a label i want a branch
266. 8:23but what if and here's this piece of
267. 8:24code that says you know set t2 is nine
268. 8:27if two two is greater than zero set less
269. 8:30than
270. 8:30and if it's if uh if t2 is less than or
271. 8:33equal to zero go to l2
272. 8:34otherwise uh i subtract one from t2 and
273. 8:37then
274. 8:38jump back to l1 so this is a little loop
275. 8:40that does something
276. 8:42well by the time i get to here
277. 8:45by the time i get to here i'm going to
278. 8:48l2
279. 8:49if i'm walking down okay a single pass
280. 8:52i'm walking down i got here okay
281. 8:54l2 problem is i haven't seen l2 yet i'm
282. 8:57walking down
283. 8:57line one line two line three i don't
284. 8:59even know where l2 is
285. 9:01l2 min it might be an error l2 might i
286. 9:03mean maybe it was hand coded by a
287. 9:04student and it has an error and l2 was a
288. 9:06label that mistyped it
289. 9:07it's not there at all well that's going
290. 9:08to be a challenge what happens
291. 9:10when l2 is below what happens if is does
292. 9:12exist but it's below
293. 9:14well here's how we have to do we have to
294. 9:17make two passes
295. 9:18so we can't just count one by one a one
296. 9:21pass system one by one by one
297. 9:22i get to a label if i haven't seen it
298. 9:24yet if i if it's a label i've seen
299. 9:26before i get it because i've already
300. 9:27replaced these two instructions i'm
301. 9:28walking my way down i've seen it before
302. 9:30okay that's the line i can count back
303. 9:31and i got that no problem i make a note
304. 9:33of where it was i can go back
305. 9:34but if i haven't seen the label before
306. 9:36that's gonna be a challenge so one pass
307. 9:38is
308. 9:38so what we do is two passes the first
309. 9:40path well three passes the first pass is
310. 9:42replace the pseudo instructions
311. 9:43the second pass is make a note of where
312. 9:45all the labels are
313. 9:46the third pass is when i see the label
314. 9:48in the branch now i know where all the
315. 9:50labels were that was the second pass
316. 9:52i said the third there's two passes to
317. 9:54do this and the first the first sister
318. 9:56you can replace and remember the labels
319. 9:57are
320. 9:58but the idea of all this is the second
321. 10:01what we call it two passes
322. 10:03we we don't really count the replaces
323. 10:05instructions as a pass
324. 10:06we do that and now i have two full
325. 10:08passes once that's done go one remember
326. 10:10the labels
327. 10:10go two and now if i see a label i know
328. 10:13how far
329. 10:14in half words to go forward for my
330. 10:16branches okay so i've got that covered
331. 10:18second passes uh notes where the labels
332. 10:20are and then puts the number in now i
333. 10:21can
334. 10:22hardco hard code what that branch value
335. 10:24is and i'm done
336. 10:25so that's pretty cool we cover that case
337. 10:27now
338. 10:29here's an example here jump to l1 jumps
339. 10:32back
340. 10:33uh three words so that's six half i'd
341. 10:35store six there that's
342. 10:36actually minus six there and this says
343. 10:38three words forward or six half words
344. 10:40i'd store
345. 10:40plus six in that in that branch value
346. 10:43there
347. 10:44okay
348. 10:47how about this one what about pc
349. 10:49relative jumps
350. 10:50and branches so here's jump
351. 10:53offset if i say jump to this offset it's
352. 10:56a pseudo instruction it actually expands
353. 10:58to
354. 10:58jump and link zero write something to
355. 11:01zero it doesn't change it at all
356. 11:02and to that offset okay so again
357. 11:06this is great this is also
358. 11:09position independent code pic i just
359. 11:11count the number of half words between
360. 11:13the target and the jump
361. 11:14and i'm ready to go so this is a pc
362. 11:15relative jump anything that's pc
363. 11:17relative when you hear the word
364. 11:18pc relative that means position
365. 11:20independent code because my pc is
366. 11:22something that works with me i'm here
367. 11:23i'm here i'm here program kind of tells
368. 11:24me where i am
369. 11:25pc relative says relative to where i am
370. 11:26it's not absolute it's
371. 11:28relative and so those relative things
372. 11:29are great that produces position
373. 11:31independent code we love position
374. 11:32independent code
375. 11:33because i don't have to move it later i
376. 11:35can now if i if it happens to get
377. 11:37relocated someplace different it's still
378. 11:38relative to where it is and it's still
379. 11:40it's you know minus three minus three is
380. 11:42gonna be wherever if i end up moving
381. 11:43this piece of code
382. 11:44up and down in the final location it
383. 11:47doesn't matter minus three is still
384. 11:48minus three from this finger to this
385. 11:49finger
386. 11:50still is those two minus three as i move
387. 11:51it in a global position
388. 11:53in the final a dot out so that's great
389. 11:57how about a reference to static data so
390. 11:59load address
391. 12:00becomes a louis add-i um if i want
392. 12:03position independent code
393. 12:05i talked about that before i want to use
394. 12:06the add upper immediate but if i if i
395. 12:09use it louis if i use the louis add-i
396. 12:11these require the full 32-bit address
397. 12:13the final load the final resting place
398. 12:15not relative to where it is in my.o file
399. 12:17but the final resting place in a dot out
400. 12:19and that's going to be trouble so that
401. 12:20isn't position independent code at all
402. 12:22so those we can't determine yet a louie
403. 12:24added we cannot determine yet
404. 12:25we cannot add you at eyepiece add upper
405. 12:28immediate pc
406. 12:29but we can't for a louis okay so
407. 12:32here's the idea we also need
408. 12:35to build some tables sometimes dot c
409. 12:38dot c dot c dot c becomes that s dot s
410. 12:41dot s
411. 12:42and then there are some symbols that can
412. 12:43be used like an x turn
413. 12:45by another c file so i need to be able
414. 12:48to know which
415. 12:49symbols are available to me so these are
416. 12:52any labels
417. 12:54if i have a function here i want to be
418. 12:56able to jump to this function call i'm
419. 12:58going to you know call that function and
420. 12:59another guy i need to know
421. 13:00that label in this function in this
422. 13:02program can be called by this dot c
423. 13:05program okay if you're if you load
424. 13:07math.h
425. 13:08and you want to call sine you didn't
426. 13:10write sine sine lives over there in
427. 13:13math.math.lib math.a so you need to be
428. 13:15able to get a label of does sine
429. 13:17exist there as a symbol i can use so
430. 13:20every time you produce this object code
431. 13:21you have to declare
432. 13:22what are the symbols that people could
433. 13:24use could jump to could call to
434. 13:26also there's some data that i have that
435. 13:28people are using let's say i have a
436. 13:29global
437. 13:29array that's going to be used by this.c
438. 13:31file you shouldn't have to copy that
439. 13:32global right here should be able to
440. 13:33reference it so how do you reference
441. 13:35that external guy so you want to be able
442. 13:36to reference the labels
443. 13:37and some data from external files that's
444. 13:40the idea so labels and data are two
445. 13:42things that you have in your symbol
446. 13:43table
447. 13:45the relocation table is the table of
448. 13:48things that are to do
449. 13:49remember if you can directly write the
450. 13:5132 bits
451. 13:53write them out add i add just write it
452. 13:56out i have all the things i need
453. 13:57go pc relative i've got all i need go
454. 14:00after you've done that you know the two
455. 14:03passes we talked about before
456. 14:04but there are some things i need to know
457. 14:06the actual
458. 14:07absolute address of where things are and
459. 14:10i can't know that until i finally have
460. 14:11the what we call the final resting place
461. 14:13in the eight out out
462. 14:14and the final executable so the
463. 14:16relocation table says
464. 14:17this is where kind of it's almost like
465. 14:19you put in a star saying to fill in
466. 14:21later
467. 14:22the relocation table is the list of
468. 14:23things you need to fill in label
469. 14:25fill in later when you finally link them
470. 14:27together in fact that's what
471. 14:28linking means link means fix those link
472. 14:30addresses fix those
473. 14:32things like where i say to do work later
474. 14:34star do work later here
475. 14:36that's actually what the link is going
476. 14:37to do is fix those fix those links
477. 14:39so anytime i have an absolute label by a
478. 14:41jowl or jalar
479. 14:43those things or in la i need to be able
480. 14:46to know what the final location is be
481. 14:48able to load that address into it and i
482. 14:50don't it's not about relative it's not
483. 14:51the actual address in the final
484. 14:53resting place also any data in the
485. 14:56static section if i have data static
486. 14:57section i don't even know where the
487. 14:58static section is at this point at the
488. 14:59level at the level of the assembler i
489. 15:01don't even know what that static section
490. 15:02is that's the job of the linker to kind
491. 15:03of create that
492. 15:04so all of that's going to be done and
493. 15:06labeled it's going to be put on the list
494. 15:08of to-do's in my relocation table
495. 15:10okay symbol tables are things that could
496. 15:12could be called in my program things
497. 15:13that could be called or my data that's
498. 15:15going to be exportable or my labels that
499. 15:16could be called into
500. 15:17that's my symbol table my relocation
501. 15:19table are all the ones that i didn't
502. 15:20really have the final values there so
503. 15:22make a star and add them to the
504. 15:23relocation table so that somebody later
505. 15:25the linker will replace those and fix
506. 15:27those later pretty cool
507. 15:29so last slide that was a big piece this
508. 15:31is a long i'm like 15 minutes into this
509. 15:33lecture now
510. 15:34the object file format contains almost
511. 15:37by the way all four
512. 15:38file formats you've seen have a header
513. 15:39you saw ppm in your project
514. 15:41that had a header so the header is it
515. 15:43tells you kind of
516. 15:44what's the size of things like the
517. 15:46following file contains
518. 15:48the following movie contains the
519. 15:50following file contains the following
520. 15:51pieces and they live here here here and
521. 15:53here so you can just jump into those
522. 15:54guys
523. 15:55what's the text segment what's the
524. 15:56machine code what's the data i'm using
525. 15:58what's all the raw data i'm going to be
526. 16:00storing all those all those um
527. 16:02strings all those uh all the
528. 16:06hard-coded fibonacci series the
529. 16:07fibonacci of the first thousand
530. 16:08fibonacci's that's in the dot data area
531. 16:10that's stuff that's gonna be there
532. 16:11be usable it's hard-coded data put it
533. 16:13right there i have my relocation table
534. 16:15again relocation is the stuff to fix the
535. 16:18things i didn't have those absolute
536. 16:19addresses i need to be able to fix those
537. 16:20that's like the work to do
538. 16:22symbol table what are all the symbols
539. 16:23that other people can call in to me to
540. 16:24get to
541. 16:25get access to my functions or my data
542. 16:28any debugging information remember we
543. 16:29talked about the translator says hey
544. 16:31let's do some work and add more
545. 16:32debugging information that can be a ton
546. 16:33of stuff
547. 16:34so all the debugging information is also
548. 16:36in the object file format that's all dot
549. 16:37oh
550. 16:38and for example the standard file format
551. 16:40is elf and here's a link to that okay
552. 16:42next up the linker i'll see you there