Pliant patch forum

Pliant patch forum

i386 optimizer v24

Enhancements to the core optimizer for i386.
Patch 03177AP 
Patch section Release *
pliant/language/optimizer/optimize.c 2003/01/24 08:05:50 485 modified lines browse review
pliant/language/basic/basic.c 2003/01/24 08:06:30 4 modified lines browse review
pliant/language/startup/startup.c 2003/01/24 08:09:42 1 modified line browse review
pliant/language/generator/generator_context.c 2003/01/24 08:04:31 48 modified lines browse review
pliant/language/generator/generator_context.pli 2003/01/24 08:00:33 0 modified line browse review
pliant/language/compiler/argument/argument2.pli 2003/01/24 08:08:24 1 modified line browse review
pliant/language/compiler/argument/argument.c 2003/01/24 08:07:20 51 modified lines browse review
Browse patch files tree
Download the patch  Download as a ready to extract .tgz tarball
Message posted by max on 2003/01/24 07:54:25

This is the new, *MUCH* improved patch for the i386 optimizer code.
Some parts of the patch are actually portable and not related to i386 at all.

As an example of the optimization performed by this patch, consider this code
coming from module "/pliant/language/type/text/cstr.pli":
it calculates the length of a CStr.

------------------------------------------

module "/pliant/language/compiler.pli"
module "/pliant/language/unsafe.pli"

constant maxlen 2^20

#method sz len -> l
function 'sample function' sz -> l
  arg CStr sz ; arg Int l
  var Address z := memory_search sz:characters maxlen "[0]":characters 1
  l := (cast z Int)-(cast sz:characters Int)
------------------------------------------
Message posted by max on 2003/01/24 07:56:29

Ok, this is how pliant-80 compiles the sample code above at debug 0:

---------------------------------------------

sample function (file:strlen.pli (internals) 7 1) sz l:
  0: i386_push EBX  (Int  ) at
  1: i386_sub 12 ESP  (Int Int  ) at
  4: i386_mov EAX [ESP+8]  (Int Int  ) at
  8: i386_mov ESP EDX  (Int Int  ) at
  10: i386_mov c8 EAX  (Int Int  ) at
  15: build Universal  (Type Universal  ) at
  20: i386_lea [ESP+8] EAX  (Int Int  ) at file:strlen.pli (internals) 9 34
  24: i386_mov EAX EBX  (Int Int  ) at file:strlen.pli (internals) 9 34
  26: i386_mov ESP EDX  (Int Int  ) at file:strlen.pli (internals) 9 55
  28: i386_mov c10 EAX  (Int Int  ) at file:strlen.pli (internals) 9 55
  33: copy  (Str Str  ) at file:strlen.pli (internals) 9 55
  38: i386_mov ESP EAX  (Int Int  ) at file:strlen.pli (internals) 9 55
  40: i386_push c5  (Int  ) at file:strlen.pli (internals) 9 20
  42: i386_mov [EAX+0] ECX  (Int Int  ) at file:strlen.pli (internals) 9 20
  44: i386_mov c1 EDX  (Int Int  ) at file:strlen.pli (internals) 9 20
  49: i386_mov EBX EAX  (Int Int  ) at file:strlen.pli (internals) 9 20
  51: i386_mov [EAX+0] EAX  (Int Int  ) at file:strlen.pli (internals) 9 20
  53: memory_search  (Address Int Address Int Address  ) at file:strlen.pli (internals) 9 20
  58: i386_mov EAX EBX  (Int Int  ) at file:strlen.pli (internals) 9 20
  60: i386_lea [ESP+8] EAX  (Int Int  ) at file:strlen.pli (internals) 10 27
  64: i386_mov [EAX+0] EAX  (Int Int  ) at file:strlen.pli (internals) 10 22
  66: cast Int  (Address Int  ) at file:strlen.pli (internals) 10 22
  71: i386_mov EBX ECX  (Int Int  ) at file:strlen.pli (internals) 10 20
  73: i386_sub EAX ECX  (Int Int  ) at file:strlen.pli (internals) 10 20
  75: i386_mov ECX EBX  (Int Int  ) at file:strlen.pli (internals) 10 20
  77: i386_mov ESP EDX  (Int Int  ) at
  79: i386_mov c17 EAX  (Int Int  ) at
  84: destroy Universal  (Type Universal  ) at
  89: i386_mov EBX EAX  (Int Int  ) at
  91: i386_add 12 ESP  (Int Int  ) at
  94: i386_pop EBX  (Int  ) at
  95: i386_return 0  (Int  ) at
function executable size is 96 bytes

---------------------------------------------
Message posted by max on 2003/01/24 07:58:16

And this is how the same code is compiled using my patch (still at debug 0)

I think the difference is quite impressive.

---------------------------------------------

sample function (file:strlen.pli (internals) 7 1) sz -> l+a13:
 L0: i386_push EBX  (Int  ) at
 L1: i386_sub 4 ESP  (Int Int  ) at
 L4: i386_mov EAX [ESP+0]  (Int Int  ) at
 L7: i386_mov ESP EAX  (Int Int  ) at file:strlen.pli (internals) 9 34
 L9: i386_mov EAX EBX  (Int Int  ) at file:strlen.pli (internals) 9 34
 LB: i386_mov c16 EAX  (Int Int  ) at file:strlen.pli (internals) 9 55
 L10: i386_push c6+a7  (Int  ) at file:strlen.pli (internals) 9 20
 L12: i386_mov [EAX+0] ECX  (Int Int  ) at file:strlen.pli (internals) 9 20
 L14: i386_mov c1+a2 EDX  (Int Int  ) at file:strlen.pli (internals) 9 20
 L19: i386_mov EBX EAX  (Int Int  ) at file:strlen.pli (internals) 9 20
 L1B: i386_mov [EAX+0] EAX  (Int Int  ) at file:strlen.pli (internals) 9 20
 L1D: memory_search  (Address Int Address Int -> Address  ) at file:strlen.pli (internals) 9 20
 L22: i386_mov ESP ECX  (Int Int  ) at file:strlen.pli (internals) 10 27
 L24: i386_sub [ECX+0] EAX  (Int Int  ) at file:strlen.pli (internals) 10 20
 L26: i386_add 4 ESP  (Int Int  ) at
 L29: i386_pop EBX  (Int  ) at
 L2A: i386_return 0  (Int  ) at
function executable size is 43 bytes

---------------------------------------------
Message posted by max on 2003/01/24 08:23:47
In case you were affectionate to the original example

------------------------------------

module "/pliant/language/unsafe.pli"

constant Value Int

type my_Array
  field Address items
  field Int nb


# this was
# method a '' k -> v

function 'sample function' a k -> v
  arg my_Array a ; arg Int k ; arg_C Value v
  check k>=0 and k<a:nb "out of range array index"
  # v :> (a:items translate Value k) map Value
  (addressof Pointer:Value v) map Address := a:items translate Value k

------------------------------------

this patch now compiles it as (at debug 1)

------------------------------------

sample function (file:array.pli (internals) 14 1) [a5+0] k -> v:
 L0: i386_push EBP  (Int  ) at
 L1: i386_mov ESP EBP  (Int Int  ) at
 L3: i386_push EBX  (Int  ) at
 L4: i386_sub 4 ESP  (Int Int  ) at
 L7: i386_mov ESP ECX  (Int Int  ) at file:array.pli (internals) 18 4
 L9: i386_mov ECX EBX  (Int Int  ) at file:array.pli (internals) 18 4
 LB: i386_mov 2 ECX  (Int Int  ) at file:array.pli (internals) 18 43
 L10: i386_shl EDX ECX  (Int Int  /pliant/language/type/number/int.pli (internals) 835 3) at file:array.pli (internals) 18 43
 L12: i386_mov [EAX+0] EAX  (Int Int  ) at file:array.pli (internals) 18 43
 L14: i386_add EDX EAX  (Int Int  ) at file:array.pli (internals) 18 43
 L16: i386_mov EBX ECX  (Int Int  ) at file:array.pli (internals) 18 43
 L18: i386_mov EAX [ECX+0]  (Int Int  ) at file:array.pli (internals) 18 43
 L1A: i386_mov [ESP+0] EAX  (Int Int  ) at
 L1D: i386_add 4 ESP  (Int Int  ) at
 L20: i386_pop EBX  (Int  ) at
 L21: i386_pop EBP  (Int  ) at
 L22: i386_return 0  (Int  ) at
function executable size is 35 bytes

------------------------------------

instead of the original 41 bytes.

Message posted by max on 2003/01/24 08:26:47

P.S. to see what the new optimizer is actually optimizing away,
run pliant at 'verbose 3'

Message posted by hubert.tonneau on 2003/01/24 11:02:11
I did an implementation of my own without looking at yours, and get the
exact same result on the first example, but no improvement on the second.
So you win: now I'm going to carrefully review your changes and start to apply.

Please keep on this absolutely great work !