X264 asm intro - Revision history

DoesItReallyMatter: +{{Lowercase}}

2019-03-09T20:21:48Z

+{{Lowercase}}

← Older revision		Revision as of 20:21, 9 March 2019
Line 1:		Line 1:
			{{Lowercase}}
	The discussions on this page have been edited for clarity, ease of reading, collation of later questions, and to trim out some noise. The original transcript can be found here: [[X264asm]]		The discussions on this page have been edited for clarity, ease of reading, collation of later questions, and to trim out some noise. The original transcript can be found here: [[X264asm]]

J-b at 13:58, 30 September 2013

2013-09-30T13:58:55Z

← Older revision		Revision as of 13:58, 30 September 2013
Line 269:		Line 269:
	* http://www.tommesani.com/Docs.html - Some visual representations of MMX instructions		* http://www.tommesani.com/Docs.html - Some visual representations of MMX instructions
	* http://webster.cs.ucr.edu/AoA/Windows/HTML/TheMMXInstructionSeta2.html - More visual representations of instructions		* http://webster.cs.ucr.edu/AoA/Windows/HTML/TheMMXInstructionSeta2.html - More visual representations of instructions

			[[Category:x264]]

J Darnley: Remove unnecessary
s

2011-12-17T22:52:43Z

Remove unnecessary <br>s

J Darnley: Add links to other useful pages

2011-12-17T22:18:02Z

Add links to other useful pages

← Older revision		Revision as of 22:18, 17 December 2011
Line 261:		Line 261:

	Here is something to note. The REP_RET you might have been wondering about. In short, if you have a RET after a jump, use REP_RET. Blame AMD.		Here is something to note. The REP_RET you might have been wondering about. In short, if you have a RET after a jump, use REP_RET. Blame AMD.

			== Helpful links ==
			* http://agner.org/optimize/ - PDFs containing instruction timing and a couple of related guides (mentioned above)
			* http://alien.dowling.edu/~rohit/nasmdocb.html - NASM manual, x86 instruction reference
			* http://alien.dowling.edu/~rohit/nasmdoc0.html - NASM manual, contents page
			* http://www.tortall.net/projects/yasm/manual/html/index.html - YASM manual, contents page (similar to the NASM manual)
			* http://www.tommesani.com/Docs.html - Some visual representations of MMX instructions
			* http://webster.cs.ucr.edu/AoA/Windows/HTML/TheMMXInstructionSeta2.html - More visual representations of instructions

Saintdev at 03:05, 13 December 2011

2011-12-13T03:05:28Z

Show changes

J Darnley: Lets get a table of contents in here along with some better headings

2011-12-10T16:11:54Z

Lets get a table of contents in here along with some better headings

← Older revision		Revision as of 16:11, 10 December 2011
Line 1:		Line 1:
	The discussions on this page have been edited for clarity, ease of reading, collation of later questions, and to trim out some noise. The original transcript can be found here: [[X264asm]]		The discussions on this page have been edited for clarity, ease of reading, collation of later questions, and to trim out some noise. The original transcript can be found here: [[X264asm]]

	== ~~One~~ ==		__TOC__

			== Example 1: predict_4x4_dc ==
	Open common/x86/predict-a.asm, go to predict_4x4_dc_mmxext ([http://git.videolan.org/?p=x264.git;a=blob;f=common/x86/predict-a.asm;h=a05e91beda809b5e113df8ba122496e756442df8;hb=HEAD#l292 git link]). This function does the following:		Open common/x86/predict-a.asm, go to predict_4x4_dc_mmxext ([http://git.videolan.org/?p=x264.git;a=blob;f=common/x86/predict-a.asm;h=a05e91beda809b5e113df8ba122496e756442df8;hb=HEAD#l292 git link]). This function does the following:
	<pre> A B C D		<pre> A B C D
Line 133:		Line 135:
	Finally, we RET: x264 will automatically clean up after us.		Finally, we RET: x264 will automatically clean up after us.

	== ~~Two~~ ==		== Example 2: pixel_sad ==
	Ok, next. You may have noticed that <tt>psadbw</tt> is awesome. It does like 8 things in one. Whereas abs() is typically 4 instructions on x86. <tt>psadbw</tt> does 8 subtracts, 8 absolute values on those results and then adds them up. That's 8 + 32 + 7 = 47 instructions in one (at least, 47 equivalent).		Ok, next. You may have noticed that <tt>psadbw</tt> is awesome. It does like 8 things in one. Whereas abs() is typically 4 instructions on x86. <tt>psadbw</tt> does 8 subtracts, 8 absolute values on those results and then adds them up. That's 8 + 32 + 7 = 47 instructions in one (at least, 47 equivalent).
	:<Q> why is abs() so slow?		:<Q> why is abs() so slow?
Line 207:		Line 209:
	:<A> Analysis? not really. There are intel performance counters and such on the chip but they're not magic. It might be useful to have some kind of tool to analyze asm functions. In general though, intuition is a powerful tool.		:<A> Analysis? not really. There are intel performance counters and such on the chip but they're not magic. It might be useful to have some kind of tool to analyze asm functions. In general though, intuition is a powerful tool.

	== ~~Three~~ ==		== Example 3: pixel_avg2_w16_sse2 ==
	Let's move onto something else. Open common/x86/mc-a.asm, pixel_avg2_w16_sse2 ([http://git.videolan.org/?p=x264.git;a=blob;f=common/x86/mc-a.asm;h=22fb8720c83b72bcd34b41553f4153bb62847462;hb=HEAD#l842 git link]). This function interpolates between two inputs, and outputs to an output. The interpolation is the simplest possible: (A+B+1)>>1		Let's move onto something else. Open common/x86/mc-a.asm, pixel_avg2_w16_sse2 ([http://git.videolan.org/?p=x264.git;a=blob;f=common/x86/mc-a.asm;h=22fb8720c83b72bcd34b41553f4153bb62847462;hb=HEAD#l842 git link]). This function interpolates between two inputs, and outputs to an output. The interpolation is the simplest possible: (A+B+1)>>1

J Darnley: /* Two */ Add the third discussion

2010-12-04T15:58:54Z

Two: Add the third discussion

← Older revision		Revision as of 15:58, 4 December 2010
Line 206:		Line 206:
	:<Q> Is there anything that does this automatically for you?		:<Q> Is there anything that does this automatically for you?
	:<A> Analysis? not really. There are intel performance counters and such on the chip but they're not magic. It might be useful to have some kind of tool to analyze asm functions. In general though, intuition is a powerful tool.		:<A> Analysis? not really. There are intel performance counters and such on the chip but they're not magic. It might be useful to have some kind of tool to analyze asm functions. In general though, intuition is a powerful tool.

			== Three ==
			Let's move onto something else. Open common/x86/mc-a.asm, pixel_avg2_w16_sse2 ([http://git.videolan.org/?p=x264.git;a=blob;f=common/x86/mc-a.asm;h=22fb8720c83b72bcd34b41553f4153bb62847462;hb=HEAD#l842 git link]). This function interpolates between two inputs, and outputs to an output. The interpolation is the simplest possible: (A+B+1)>>1

			Look at the function signature above: <tt>void pixel_avg2_w4( uint8_t *dst, int dst_stride</tt> etc. This function takes inputs from src1 and src2, averages them together, and writes to dst. src1 and src2 have src_stride and dst has dst_stride.
			:<Q> What's the height?
			:<A> How many lines to interpolate.

			Now this function uses xmm registers (128-bit) so it does 16 bytes at a time. All 128-bit loads must be aligned unless movdqu is used. Since our inputs are unaligned, this is a lot of movdqu.
			:<Q> What does movdqu do?
			:<A> Loads 128 bits from an unaligned source.
			:<Q> What is the difference between movdqa and movdqu?
			:<A> movdqa is for aligned data, movdqu is for unaligned data. The output is always aligned, as we control it, whereas the input is an arbitrary pointer into a reference frame and so it could be anything.
			:<Q> Why subtract r2 from r4?
			:<A> Ah, now here's a fun trick. We need to increment three pointers, right? src1, src2, dst. But src1 and src2 have the same stride, so they're being incremented by the same amount. So we can take src2 and represent it as an offset from src1. Then we only have to increment src1. One lea removed per iteration, bam.
			:<Q> And use r6 as the offset + stride?
			:<A> Yes

			Look through that function and see if there's anything you don't know about and ask questions.
			:<Q> How do you keep track of which argument is which?
			:<A> You can copy the description from w4 and annotate it.
			<pre>; void pixel_avg2_w4( uint8_t *dst (r0), int dst_stride (r1),
			; uint8_t *src1 (r2), int src_stride (r3),
			; uint8_t *src2 (r4), int height (r5) );</pre>
			:There is also a system that can be covered later which helps you keep track of registers or, well, makes it easier to.
			:<Q> pavgb, I assume, does some sort of averaging?
			:<A> Yes, (A+B+1)>>1 for each pair of input pixels.

			Now we come to one of the many jumps that exists in x86, jump if greater than, so if r5d > 0.
			:<Q> How does the jump work without a compare instruction?
			:<A> The sub sets the same flags as a cmp.
			:<Q> So why subtract two?
			:<A> It handles two rows at a time.

			Here is something to note. The REP_RET you might have been wondering about. In short, if you have a RET after a jump, use REP_RET. Blame AMD.

J Darnley: /* One */ Layout and markup changes

2010-12-03T22:41:25Z

One: Layout and markup changes

Show changes

J Darnley: /* One */ Add a small statement about the page and a link to the original

2010-12-03T21:53:45Z

One: Add a small statement about the page and a link to the original

← Older revision		Revision as of 21:53, 3 December 2010
Line 1:		Line 1:
			The discussions on this page have been edited for clarity, ease of reading, collation of later questions, and to trim out some noise. The original transcript can be found here: [[X264asm]]

	== One ==		== One ==
	Open common/x86/predict-a.asm, go to predict_4x4_dc_mmxext, [http://git.videolan.org/?p=x264.git;a=blob;f=common/x86/predict-a.asm;h=a05e91beda809b5e113df8ba122496e756442df8;hb=HEAD#l292 git link]<br>		Open common/x86/predict-a.asm, go to predict_4x4_dc_mmxext, [http://git.videolan.org/?p=x264.git;a=blob;f=common/x86/predict-a.asm;h=a05e91beda809b5e113df8ba122496e756442df8;hb=HEAD#l292 git link]<br>

J Darnley: Add second discussion

2010-12-03T21:46:30Z

Add second discussion

@@ Line 1: / Line 1: @@
 Open common/x86/predict-a.asm, go to predict_4x4_dc_mmxext, [http://git.videolan.org/?p=x264.git;a=blob;f=common/x86/predict-a.asm;h=a05e91beda809b5e113df8ba122496e756442df8;hb=HEAD#l292 git link]<br>
 This function does the following:<br>
@@ Line 131: / Line 132: @@
 Finally, we RET: x264 will automatically clean up after us.<br>

← Older revision		Revision as of 22:52, 17 December 2011
Line 18:		Line 18:
	:<A> Stride is the distance between (x,y) and (x,y+1), so to get from one row to the next.		:<A> Stride is the distance between (x,y) and (x,y+1), so to get from one row to the next.

	~~<br>~~ Now that you understand what the function does, let's look at the asm.		Now that you understand what the function does, let's look at the asm.
	<pre>cglobal predict_4x4_dc_mmxext, 1,4</pre>		<pre>cglobal predict_4x4_dc_mmxext, 1,4</pre>
	"cglobal" declares a function accessible from outside of asm. The function's name is <tt>x264_predict_4x4_dc_mmxext</tt> (the <tt>x264_</tt> is auto-added). The "1" means "we have one argument. Put it in <tt>r0</tt>.", (that argument is uint8_t src). If we had a second argument, we'd say "2" and the second one would go in <tt>r1</tt> and if we had a third, it'd go in <tt>r2</tt>, etc. So at the start of the function, <tt>r0</tt> contains uint8_t src.		"cglobal" declares a function accessible from outside of asm. The function's name is <tt>x264_predict_4x4_dc_mmxext</tt> (the <tt>x264_</tt> is auto-added). The "1" means "we have one argument. Put it in <tt>r0</tt>.", (that argument is uint8_t src). If we had a second argument, we'd say "2" and the second one would go in <tt>r1</tt> and if we had a third, it'd go in <tt>r2</tt>, etc. So at the start of the function, <tt>r0</tt> contains uint8_t src.
Line 34:		Line 34:
	:<A> Yes, which is why you can't use it.		:<A> Yes, which is why you can't use it.

	~~<br>~~ So now, this function as you can see has 4 real steps:		So now, this function as you can see has 4 real steps:

	#Sum up A through D		#Sum up A through D
Line 43:		Line 43:
	So let's see how this asm implements these.		So let's see how this asm implements these.

	~~<br>~~ First, we'll look at step 1		First, we'll look at step 1
	<pre>pxor mm7, mm7</pre>		<pre>pxor mm7, mm7</pre>
	<tt>mm7</tt> is a 64-bit register. <tt>xor</tt>, as you might know, is a nice way to zero things.		<tt>mm7</tt> is a 64-bit register. <tt>xor</tt>, as you might know, is a nice way to zero things.
Line 50:		Line 50:
	:<A> <tt>mm</tt> is 64-bit, <tt>xmm</tt> is 128-bit. The mm registers have a fixed size, only the general purpose registers are wordsize-dependant on x86		:<A> <tt>mm</tt> is 64-bit, <tt>xmm</tt> is 128-bit. The mm registers have a fixed size, only the general purpose registers are wordsize-dependant on x86

	So, now <tt>mm7</tt> is zero.~~<br>~~		So, now <tt>mm7</tt> is zero.
	<pre>movd mm0, [r0-FDEC_STRIDE]</pre>		<pre>movd mm0, [r0-FDEC_STRIDE]</pre>
	This sets <tt>mm0</tt> equal to {A,B,C,D,0,0,0,0}		This sets <tt>mm0</tt> equal to {A,B,C,D,0,0,0,0}
Line 82:		Line 82:
	:<A> This is an optimization: on 64-bit, using 32-bit versions of registers results in smaller instruction opcode sizes. So it's really just <tt>r3</tt>. <tt>r0</tt>, <tt>r1</tt>, <tt>r2</tt>, <tt>r3</tt> are the 4 that are free. So we're using <tt>r3</tt>. Note: the suffix 'd' means the 32-bit version, as opposed to the native-size version.		:<A> This is an optimization: on 64-bit, using 32-bit versions of registers results in smaller instruction opcode sizes. So it's really just <tt>r3</tt>. <tt>r0</tt>, <tt>r1</tt>, <tt>r2</tt>, <tt>r3</tt> are the 4 that are free. So we're using <tt>r3</tt>. Note: the suffix 'd' means the 32-bit version, as opposed to the native-size version.

	~~<br>~~ Get moving with part 2 of the algorithm.		Get moving with part 2 of the algorithm.

	Now <tt>r0</tt> has our source pointer, and <tt>r3</tt> has A+B+C+D. While the CPU is busy doing that, we'll go and do part 2, the E+F+G+H. Unfortunately, these bytes aren't in a straight line ("straight line" meaning "adjacent in memory"). So we can't just load EFGH and sad them. We'll have to do it the naive/slow way. So, now we're going to load E, F, G, H. Now you might notice some preprocessor commands here. <tt>%assign</tt>, <tt>%rep</tt>, etc are preprocessor commands.		Now <tt>r0</tt> has our source pointer, and <tt>r3</tt> has A+B+C+D. While the CPU is busy doing that, we'll go and do part 2, the E+F+G+H. Unfortunately, these bytes aren't in a straight line ("straight line" meaning "adjacent in memory"). So we can't just load EFGH and sad them. We'll have to do it the naive/slow way. So, now we're going to load E, F, G, H. Now you might notice some preprocessor commands here. <tt>%assign</tt>, <tt>%rep</tt>, etc are preprocessor commands.

	So, first step: load E into <tt>r1d</tt~~><br~~>		So, first step: load E into <tt>r1d</tt>
	<pre>movzx r1d, byte [r0-1]</pre>		<pre>movzx r1d, byte [r0-1]</pre>
	<tt>movzx</tt> means "move, with zero extend". In C this would be: int r1d = r0[-1];		<tt>movzx</tt> means "move, with zero extend". In C this would be: int r1d = r0[-1];
Line 110:		Line 110:
	:<A> It is a macro. Note the pre-processed code above. Everything starting with % in yasm syntax is a macro.		:<A> It is a macro. Note the pre-processed code above. Everything starting with % in yasm syntax is a macro.

	~~<br>~~ Ok, now we have to do step 3: calculating A+B+C+D+E+F+G+H+4 / 8		Ok, now we have to do step 3: calculating A+B+C+D+E+F+G+H+4 / 8
	<pre>lea r1d, [r1+r3+4]</pre>		<pre>lea r1d, [r1+r3+4]</pre>
	First, let's go over x86 addressing. What you can put inside the brackets is not infinite. Here's the capabilities, specifically: [REG1 + REG2 * {1,2,4,8} + CONST]. A register, plus another register * 1/2/4/8, plus a constant (positive or negative). As you might note, this is pretty useful for accessing things like arrays. E.g. array[n+5], where array is an int array, would be: [array + n*4 + 20]		First, let's go over x86 addressing. What you can put inside the brackets is not infinite. Here's the capabilities, specifically: [REG1 + REG2 * {1,2,4,8} + CONST]. A register, plus another register * 1/2/4/8, plus a constant (positive or negative). As you might note, this is pretty useful for accessing things like arrays. E.g. array[n+5], where array is an int array, would be: [array + n*4 + 20]
Line 131:		Line 131:
	:<A> +4 for correct rounding, >> 3 to divide (>>3 = /(2^3) = /8).		:<A> +4 for correct rounding, >> 3 to divide (>>3 = /(2^3) = /8).

	~~<br>~~ Now for the final part: storing the results.		Now for the final part: storing the results.
	<pre>imul r1d, 0x01010101</pre>		<pre>imul r1d, 0x01010101</pre>
	This is called a "splat" and you may have seen it in C as well. We're turning an 8-bit value into 4x that value, e.g. A -> AAAA		This is called a "splat" and you may have seen it in C as well. We're turning an 8-bit value into 4x that value, e.g. A -> AAAA
Line 152:		Line 152:
	:This needs a mov on x86, so that's 4 instructions.		:This needs a mov on x86, so that's 4 instructions.

	~~<br>~~ So <tt>psadbw</tt> is pretty awesome. It's very awesome for doing what its name implies you should do with it, that is -- SADs -- sum of absolute differences. So let's open sad-a.asm and hop down to line 95 ([http://git.videolan.org/?p=x264.git;a=blob;f=common/x86/sad-a.asm;h=0a96837aaa4c54f624b63c020872b74a790f1ffd;hb=HEAD#l95 git link]). Also open common/pixel.c and look at the first function: SAD ([http://git.videolan.org/?p=x264.git;a=blob;f=common/pixel.c;h=7fa497c7cf151df5795bb105895760fde89facb6;hb=HEAD#l44 git link]). This function is pretty simple. You should be able to see how it works. Look only at the C for now.		So <tt>psadbw</tt> is pretty awesome. It's very awesome for doing what its name implies you should do with it, that is -- SADs -- sum of absolute differences. So let's open sad-a.asm and hop down to line 95 ([http://git.videolan.org/?p=x264.git;a=blob;f=common/x86/sad-a.asm;h=0a96837aaa4c54f624b63c020872b74a790f1ffd;hb=HEAD#l95 git link]). Also open common/pixel.c and look at the first function: SAD ([http://git.videolan.org/?p=x264.git;a=blob;f=common/pixel.c;h=7fa497c7cf151df5795bb105895760fde89facb6;hb=HEAD#l44 git link]). This function is pretty simple. You should be able to see how it works. Look only at the C for now.

	So as you'll notice, the C SAD has 7 different versions for 16x16, 16x8, 8x16, etc and it's instantiated via a macro. So, for our asm, we also need 7 versions and we also don't want to write the function 7 times, just like in the case of C we didn't.		So as you'll notice, the C SAD has 7 different versions for 16x16, 16x8, 8x16, etc and it's instantiated via a macro. So, for our asm, we also need 7 versions and we also don't want to write the function 7 times, just like in the case of C we didn't.
Line 161:		Line 161:
	:<A> Yes, it's one of three macros, look above, each one does 2 rows worth of SAD for width 4, width 8, and width 16. It picks the right one based on the width and it %reps it based on the height.		:<A> Yes, it's one of three macros, look above, each one does 2 rows worth of SAD for width 4, width 8, and width 16. It picks the right one based on the width and it %reps it based on the height.

	~~<br>~~ Now, start analyzing the 3 macros above (the sad macros) and trying to figure out how they work. Note mm0 is the accumulator which is why it's zeroed at the start.		Now, start analyzing the 3 macros above (the sad macros) and trying to figure out how they work. Note mm0 is the accumulator which is why it's zeroed at the start.

	:<Q> The order of args is the same as in the C function?		:<Q> The order of args is the same as in the C function?
Line 179:		Line 179:
	:<A> We're incrementing the pointer by 2*stride		:<A> We're incrementing the pointer by 2*stride

	~~<br>~~ Now you should understand what SAD_INC_2x4P does, the others work similarly except without the punpck magic because they don't need it.		Now you should understand what SAD_INC_2x4P does, the others work similarly except without the punpck magic because they don't need it.

	:<Q> Why is the lea out of order in SAD_INC_2x8P? By out of order i mean not next to each other.		:<Q> Why is the lea out of order in SAD_INC_2x8P? By out of order i mean not next to each other.
Line 195:		Line 195:
	:<A> psadbw		:<A> psadbw

	~~<br>~~ Now let's get a bit to how we measure performance. For any asm instruction, there are three things that matter: latency, inverse throughput, and execution units. The first two are represented with notation like this: "3/1". This means a psadbw takes 3 clocks to finish from when it's started and you can do one of them per cycle. Another example is <tt>mov</tt>. Between two registers it is 1/0.33, takes 1 cycle, and you can do 3 per clock.		Now let's get a bit to how we measure performance. For any asm instruction, there are three things that matter: latency, inverse throughput, and execution units. The first two are represented with notation like this: "3/1". This means a psadbw takes 3 clocks to finish from when it's started and you can do one of them per cycle. Another example is <tt>mov</tt>. Between two registers it is 1/0.33, takes 1 cycle, and you can do 3 per clock.

	Execution unit usage is a bit trickier. Not all execution units can do all instructions. Intel chips have 6 execution units: p0, p1, p2, p3, p4, p5		Execution unit usage is a bit trickier. Not all execution units can do all instructions. Intel chips have 6 execution units: p0, p1, p2, p3, p4, p5
Line 208:		Line 208:
	Generally execution units aren't important until you get into serious optimizing but they can often affect the best instruction choices. For example, if an execution unit is sitting around doing nothing for a whole function.		Generally execution units aren't important until you get into serious optimizing but they can often affect the best instruction choices. For example, if an execution unit is sitting around doing nothing for a whole function.

	~~<br>~~ The instruction tables sheet here http://agner.org/optimize/ has all the information on latency, execution units, and inverse throughput for a wide variety of CPUs.		The instruction tables sheet here http://agner.org/optimize/ has all the information on latency, execution units, and inverse throughput for a wide variety of CPUs.

	:<Q> How about branching? I heard branching ruins things.		:<Q> How about branching? I heard branching ruins things.
Line 217:		Line 217:
	So the loads are the bottleneck. This is an important thing to understand: it's possible for one type of operation to bottleneck a function. Loads are a common example. In this case, SAD is so fast that it is effectively free, as we're sitting around waiting for loads the whole time. The actual run-time of the function is about 22 clocks. Which is fitting for 16 + start + end + overhead.		So the loads are the bottleneck. This is an important thing to understand: it's possible for one type of operation to bottleneck a function. Loads are a common example. In this case, SAD is so fast that it is effectively free, as we're sitting around waiting for loads the whole time. The actual run-time of the function is about 22 clocks. Which is fitting for 16 + start + end + overhead.

	~~<br>~~ So that's some basic performance analysis for you. How long the function should take in theory, how long each instruction takes in theory, and how you can be bottlenecked.		So that's some basic performance analysis for you. How long the function should take in theory, how long each instruction takes in theory, and how you can be bottlenecked.

	:<Q> Is there anything that does this automatically for you?		:<Q> Is there anything that does this automatically for you?