Mantis Bug Tracker
Main | My View | View Issues | Change Log | Roadmap
  

View Issue Details [ Jump to Notes ] [ Issue History ] [ Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005774OCamlback end (clambda to assembly)public2012-10-05 19:502015-07-24 10:38
Reporterchambart 
Assigned Tochambart 
PrioritynormalSeverityfeatureReproducibilityalways
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version4.00.0 
Target VersionFixed in Version4.01.0 
Summary0005774: [patch] detect and optimise endiannes conversion with bswap
DescriptionThis patch adds a kind of simple symbolic bitwise interpretation to detect some common patterns.
I have implemented a simple detection of bswap kind of instructions and optimised it on amd64 backend.

It will detect things like that:

let swap16 i =
  ( (i land 0xFF) lsl 8 )
  lor ((i land 0xFF00) lsr 8)

let swap16_2 i =
  ((i lsl 8) land 0xFF00)
  lor ((i land 0xFF00) lsr 8)

let swap32 i =
  Int32.logor
    (Int32.logor
       (Int32.shift_left (Int32.logand i 0xFFl) (8*3))
       (Int32.shift_left (Int32.logand i 0xFF00l) (8*1)))
    (Int32.logor
       (Int32.shift_right_logical (Int32.logand i 0xFF0000l) (8*1))
       (Int32.shift_right_logical (Int32.logand i 0xFF000000l) (8*3)))

let swap64 i =
  Int64.logor
   (Int64.logor
     (Int64.logor
       (Int64.shift_left (Int64.logand i 0xFFL) (8*7))
       (Int64.shift_left (Int64.logand i 0xFF00L) (8*5)))
     (Int64.logor
       (Int64.shift_left (Int64.logand i 0xFF0000L) (8*3))
       (Int64.shift_left (Int64.logand i 0xFF000000L) (8*1))))
   (Int64.logor
     (Int64.logor
       (Int64.shift_right_logical (Int64.logand i 0xFF_00000000L) (8*1))
       (Int64.shift_right_logical (Int64.logand i 0xFF00_00000000L) (8*3)))
     (Int64.logor
       (Int64.shift_right_logical (Int64.logand i 0xFF0000_00000000L) (8*5))
       (Int64.shift_right_logical (Int64.logand i 0xFF000000_00000000L) (8*7))))
Additional InformationUsing it I think that there could be other optimisable instructions like sign extension, some unnecessary tagging/untaging...

The implementation is quadratic in the depth of a boolean expression, but it is possible to make it linear. I didn't notice any difference in compilation time.

The detection method here is made by a brutal pattern matching. It take quite some time to compile the pattern matching. A real detection whould use something smarter to detect more cases.
Tagspatch
Attached Filespatch file icon 0001-Add-a-boolean-operation-interpretation.-Use-it-to-de.patch [^] (30,119 bytes) 2012-10-05 19:50 [Show Content]
patch file icon amd64_selection.patch [^] (1,537 bytes) 2012-10-08 11:07 [Show Content]
patch file icon 0001-Add-bswap-primitives.patch [^] (17,038 bytes) 2012-11-09 20:37 [Show Content]

- Relationships

-  Notes
(0008482)
chambart (developer)
2012-11-09 20:37

 Added a simplified version with only a %bswap primitive and no pattern detection.
(0008617)
frisch (developer)
2012-12-17 12:37

 I believe commit 13106 breaks 32-bit ports (primitive _caml_int64_direct_bswap is not defined).
(0008618)
frisch (developer)
2012-12-17 12:42

 I can fix the build by adding those lines after the definition of caml_int64_direct_bwap:

#else
CAMLprim value caml_int64_direct_bswap(value v)
{ caml_failwith("calling int64_direct_bswap on a 32-bit architecture"); }
#endif

This is probably fine, since this primitive is only used by the amd64 port, but it would be nice if the patch author could confirm it.
(0008619)
frisch (developer)
2012-12-17 16:53

 Actually, the same without CAMLprim, otherwise caml_int64_direct_bswap appears twice in the generated primitives files, and thus in Runtimedef.builtin_primitives (and so it it recorded twice in Symtable, leading to an empty entry in the PRIM table of the generated bytecode programs, which confuses the bytecode interpreter... just spend three hours on that).
(0008620)
chambart (developer)
2012-12-17 17:40

 In fact it is not used at all in the bytecode compiler, so it should not be marked as a CAMLprim.

Sorry for the trouble
(0008621)
chambart (developer)
2012-12-17 17:40

 In fact it is not used at all in the bytecode compiler, so it should not be marked as a CAMLprim
(0008622)
chambart (developer)
2012-12-17 17:56

 The other functions that should not be annotated CAMLprim:
caml_bswap16_direct
caml_int32_direct_bswap
caml_int64_direct_bswap
caml_nativeint_direct_bswap
(0008623)
frisch (developer)
2012-12-17 17:57
edited on: 2012-12-17 18:15

 Thanks! Fixed in commit 13134, 13135, 13136. Btw, does anyone know how to cleanly remove a CAMLprim? The problem is that the committed bootstrap ocamlc requires this primitive, so we cannot simply remove the primitive from ocamlrun. I've simply disabled the test for 'unknown C primitive' temporarily in dynlink.c, but I wonder whether there is a cleaner method.
(0008631)
frisch (developer)
2012-12-19 16:42

 Ok, so now we have some optimized built-in ways to do endianess conversion. Since this is part of the compiler, shouldn't the function be exposed as (external) functions, e.g. in Pervasives? Otherwise, do we assume that those external declarations would be used in third-party projects? (Not that I really care, but since I've lost some time because of this issue, I'm wondering what's the current status of the proposal.)
(0008633)
lefessan (developer)
2012-12-19 18:19

 They are exposed in ocplib-endian (https://github.com/OCamlPro/ocplib-endian [^]). Having these primitives is not enough, you have to write your code in such a way that it does not allocate for most functions. This is what ocplib-endian provides.

OPAM makes it easy now to externalize functionalities that would otherwise have had to be in the stdlib/otherlibs.

- Issue History
Date Modified Username Field Change
2012-10-05 19:50 chambart New Issue
2012-10-05 19:50 chambart File Added: 0001-Add-a-boolean-operation-interpretation.-Use-it-to-de.patch
2012-10-08 11:07 chambart File Added: amd64_selection.patch
2012-11-09 20:37 chambart File Added: 0001-Add-bswap-primitives.patch
2012-11-09 20:37 chambart Note Added: 0008482
2012-11-15 19:45 doligez Status new => acknowledged
2012-12-17 12:37 frisch Note Added: 0008617
2012-12-17 12:42 frisch Note Added: 0008618
2012-12-17 16:53 frisch Note Added: 0008619
2012-12-17 17:40 chambart Note Added: 0008620
2012-12-17 17:40 chambart Note Added: 0008621
2012-12-17 17:56 chambart Note Added: 0008622
2012-12-17 17:57 frisch Note Added: 0008623
2012-12-17 18:15 frisch Note Edited: 0008623 View Revisions
2012-12-19 16:42 frisch Note Added: 0008631
2012-12-19 18:19 lefessan Note Added: 0008633
2013-12-16 13:14 doligez Tag Attached: patch
2013-12-17 19:50 chambart Status acknowledged => resolved
2013-12-17 19:50 chambart Fixed in Version => 4.01.0
2013-12-17 19:50 chambart Resolution open => fixed
2013-12-17 19:50 chambart Assigned To => chambart
2015-07-24 10:38 xleroy Status resolved => closed
2017-02-23 16:35 doligez Category OCaml backend (code generation) => Back end (clambda to assembly)
2017-02-23 16:44 doligez Category Back end (clambda to assembly) => back end (clambda to assembly)

Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker