DEV Community: Plume

DPIR: Data Propagating Intermediate Representation

Plume — Thu, 06 Jan 2022 09:28:56 +0000

DPIR：Data Propagation Intermediate Representation

Traditional data propagation generally use DXL(Data eXchange Language e.g. XML, YAML, JSON) as the data carrier.

This approach have two penalties:

DXLs are very high-level, convenient for user to edit but Inconvenient for program to parse.
There are too many DXLs exist, programs use different DXLs can't exchange data directly.

Here I introduce a better way for data propagation: design a intermediate representation for data propagation.
I name it DPIR(Data Propagating Intermediate Representation).

DPIR should be low-level enough for programs to access efficiently and expressive enough for transforming to and from DXLs with no information lose.

Preliminary Design of DPIR

String encoding is another problem for data propagation, to avoid this problem DPIR save strings in a individual file: StrFile.
Non-string data is saved in DataFile.

StrFile

StrFile's name form is: name.dpir-str-encode.
Where name is the source file's name and encode is the string encoding used.

For example: DPIR from config.json, it's StrFile's name should be config.dpir-str-encode.

For the StrFile saved with UTF-8 it's name should be config.dpir-str-utf8;

For the StrFile saved with UTF-16 LE it's name should be config.dpir-str-utf16le;

For the StrFile saved with UTF-16 BE it's name should be config.dpir-str-utf16be.

There can be multiple StrFiles's saved with different encodings in a single DPIR.

The strings in StrFile are terminated with \n and accessed with index started from 1, the index 0 is used to represent empty string("").
Therefore the line number of a line is also the index of the string saved in this line.

DataFile

DataFile's name form is: name.dpir-data where name is source file's name.

There's a format description in GO-like syntax for DataFile:

// structure of whole file, fields aligned to block size。
type full_file struct{
  fileHead    file_head      // fileHead holds some global metadata.
  root        array_table/map_tabl/list_table/struct_table/string/integer/float/complex
  // field root is root of the whole data structure, it can be a array table, a map table, a list table, a struct table, a string, a integer, a float-point number, or a complex number.

  // followed by subsequent tables(if root is a table).
}
//--------------------------------------------------









//*******************************************************************
type file_head struct{
  blockSizeLog        uint8    // specified blockSize：blockSize=1 << blockSizeLog
  fileHeadSize        uint8    // size of file_head, block unit.
  majorVersion        uint8    // major version.
  minorVersion        uint8    // minor version.
  generalEncodeFlag   byte    // specified UTF and ASCII encoding, can be combined with '|'.
  charSetFlag         byte    // specified char set.
  encodeFormatFlag    byte    // specified encodings of char set specified by charSetFlag, can be combined with '|'.
  rootTypeFlag        byte    // specified type of root
  sonKeyTypeFlag      byte    // (when rootTypeFlag is TYPE_MAP)specified keyType of all entrys in root table.
  sonValueTypeFlag    byte    // (when rootTypeFlag is TYPE_ARRAY or TYPE_MAP)specified valueType of all entrys in root table.
  reserveFileHead     [n]byte  // reserve space, used to align file_head to block size.
}
// generalEncodeFlag:
const(
  ASCII      =  1<<iota
  UTF8
  UTF16LE
  UTF16BE
  UTF32LE
  UTF32BE
)


// charSetFlag:
const(
  CHINESE      = 1+iota        // Chinese char set.
  JAPANESE                    //  Japanese char set。
  // and so on
)


// encodeFormatFlag:
const(
  FLAG1    =  1<<iota  
  FLAG2
  FLAG3
  FLAG4
  FLAG5
  FLAG6
  FLAG7
  FLAG8
)
// For example:
// When charSetFlag is CHINESE, FLAG1 represent GBK, FLAG2 represent GB2312, FLAG3 represent GB18030 ...
// When charSetFlag is JAPANESE, FLAG1 represent Shift_JIS, FLAG2 represent EUC_JP, FLAG3 represent ISO-2022-JP ...





// typeFlag: for rootTypeFlag，keyTypeFlag，valueTypeFlag，sonKeyTypeFlag and sonValueTypeFlag.
const(
  TYPE_ARRAY      =  iota     // array type
  TYPE_MAP                    // map type
  TYPE_LIST                   // list type
  TYPE_STRUCT                 // struct type
  TYPE_STRING                 // string type
  TYPE_INT8                   // and so on...
  TYPE_INT16
  TYPE_INT32
  TYPE_INT64
  TYPE_INT128
  TYPE_INT256
  TYPE_UINT8
  TYPE_UINT16
  TYPE_UINT32
  TYPE_UINT64
  TYPE_UINT128
  TYPE_UINT256
  TYPE_FLOAT16
  TYPE_FLOAT32
  TYPE_FLOAT64
  TYPE_FLOAT128
  TYPE_FLOAT256
  TYPE_FLOAT512
  TYPE_COMPLEX32
  TYPE_COMPLEX64
  TYPE_COMPLEX128
  TYPE_COMPLEX256
  TYPE_COMPLEX512
  TYPE_COMPLEX1024
)
//----------------------------------------------------------------------










//*******************************************************************
// array table：
type array_table  struct{
  entryNum            uint16   // number of entrys in current table.
  sonKeyTypeFlag      byte     // this field only exist when value of all entrys in current table is map_table(specified by father entry's sonValueType), this field specified keyType of son table's all entrys.
  sonValueTypeFlag    byte     // this field only exist when value of all entrys in current table is map_table or array_table, this field specified valueType of son table's all entrys.
  entrys              [entryNum]array_entry    // entrys of current table.
  reserveTable        [n]byte  // reserved space, used to align current table to block size.
}


// array entry:
type  array_entry    struct{
  value  [valueSize]byte
  // according to father entry's sonValueTypeFlag：
  // if it's TYPE_ARRAY, TYPE_MAP, TYPE_LIST or TYPE_STRUCT，then value is uint16 type，specified son table's offset, relative to current table's end, block unit.
  // if it's TYPE_STRING, then value is uint16 type, specified the index of string in *StrFile*.
  // if it's other type(e.g. int64, complex128), then value is the real value of this entry.
}
//---------------------------------------------------------------------------------------









//*******************************************************************************************
// map table:
type  map_table  struct{
  entryNum           uint16            // specified nuber of entrys in current table.
  sonKeyTypeFlag     byte              // this field only exist when value of all entrys in current table is map_table(specified by father entry's sonValueType), this field specified keyType of son table's all entrys.
  sonValueTypeFlag   byte              // this field only exist when value of all entrys in current table is map_table or array_table, this field specified valueType of son table's all entrys.
  entrys             [entryNum]map_entry      // entrys of current table.
  reserveTable       [n]byte            // reserved space, used to align current table to block size.
}


// map entry
type  map_entry  struct{
  key      [keySize]byte          // current entry's key, type and size is specified by father entry's sonKeyTypeFlag; 
  // if father entry's sonKeyTypeFlag is TYPE_STRING, then key is uint16 type, specified the index of string in *StrFile*.

  value    [valueSize]byte        // current entry's value, according to father entry's sonValueTypeFlag:
  // if it's TYPE_ARRAY, TYPE_MAP, TYPE_LIST or TYPE_STRUCT，then value is uint16 type，specified son table's offset, relative to current table's end, block unit.
  // if it's TYPE_STRING, then value is uint16 type, specified the index of string in *StrFile*.
  // if it's other type(e.g. int64, complex128), then value is the real value of this entry.
}
//-------------------------------------------------------------------------------------









//*************************************************************************************
// list table:
type list_table  struct{
  entryNum      uint16      // specified nuber of entrys in current table.
  entrys        [entryNum]list_entry  // entrys in current table.
  exValues      [n]byte    // real values for types beyond size of 32bit(e.g. int64, complex128).
  reserveTable  [n]byte    // reserved space, used to align current table to block size.
}


// list entry:
type  list_entry    struct{
  valueTypeFlag     byte      // specified valueType of current entry.
  sonKeyTypeFlag    byte      // this field only exist when valueTypeFlag is TYPE_MAP, this field specified keyType of son table's all entrys.
  sonValueTypeFlag  byte      // this field only exist when valueTypeFlag is TYPE_MAP or TYPE_ARRAY, this field specified valueType of son table's all entrys.
  value             [n]byte    // the "value" of current entry.
  reserveEntry      [n]byte    // reserved space, used to align current entry to 5 bytes.
  // according to valueTypeFlag：
  // if it's TYPE_ARRAY, TYPE_MAP, TYPE_LIST or TYPE_STRUCT，then value is uint16 type，specified son table's offset, relative to current table's end, block unit.
  // if it's TYPE_STRING, then value is uint16 type, specified the index of string in *StrFile*.
  // if it's number type below size of 32bit(int8-32, uint8-32, float32), then value is the real value of current entry.
  // if it's number type beyond size of 32bit, then value is uint32 type, specified the offset of real value, relative to start of exValues, byte unit.
}
//---------------------------------------------------------------------------------------









//*******************************************************************************************
// struct table:
type  struct_table  struct{
  entryNum      byte    // number of entrys in current table.
  entrys        [entryNum]struct_entry  // entrys of current table.
  exValues      [n]byte  // real values for types beyond size of 32bit(e.g. int64, complex128).
  reserveTable  [n]byte  // reserved space, used to align current table to block size.
}


// struct entry：
type  struct_entry  struct{
  valueTypeFlag     byte      // specified valueType of current entry.
  key               uint16    // index of string in *StrFile*.
  sonKeyTypeFlag    byte      // this field only exist when valueTypeFlag is TYPE_MAP, this field specified keyType of son table's all entrys.
  sonValueTypeFlag  byte      // this field only exist when valueTypeFlag is TYPE_MAP or TYPE_ARRAY, this field specified valueType of son table's all entrys.
  value             [n]byte    // the "value" of current entry.
  reserveEntry      [n]byte    // reserved space, used to align current entry to 7 bytes.
  // according to valueTypeFlag：
  // if it's TYPE_ARRAY, TYPE_MAP, TYPE_LIST or TYPE_STRUCT，then value is uint16 type，specified son table's offset, relative to current table's end, block unit.
  // if it's TYPE_STRING, then value is uint16 type, specified the index of string in *StrFile*.
  // if it's number type below size of 32bit(int8-32, uint8-32, float32), then value is the real value of current entry.
  // if it's number type beyond size of 32bit, then value is uint32 type, specified the offset of real value, relative to start of exValues, byte unit.
}

Module Management for Golang on Win10

Plume — Wed, 15 Dec 2021 07:51:09 +0000

Install and Config Golang on Win10

Create a Module

Create a new directory, in this example, I Created "A:/Learn/Go/Work".
Open cmd or PowerShell, jump to the new directory.
cd /d A:/Learn/Go/Work
Run go mod init Aoi/Sola where Aoi/Sola will be the new module's name. This will create a go.mod File in "A:/Learn/Go/Work", make "A:/Learn/Go/Work" the new module's root directory.

The go.mod file's content will be:

module Aoi/Sola

go 1.17

Where Aoi/Sola is the new module's name, 1.17 is Golang's version number.

Hello World

Create a source file in module's root directory(in this example "A:/Learn/Go/Work").

In this example, I created hello.go.

hello.go's content:

package main // "package main" specifies the package name: "main"

// Golang's main func have no return no argument.
func main(){
  println("Hello World") // Output "Hello World" through standard error.
}

Every source file's first line should be a package <package_name> statement.
A Golang program can only have one "main" package.

Jump to module's root directory(in this example "A:/Learn/Go/Work"), run go run hello.go, you will see "Hello World" in standard error output.

Import Module

Import Remote Module

Create another module in another directory, in this example I created a module named "remote" in "A:/Learn/Go/Remote".
Create a source file in "A:/Learn/Go/Remote", I created remote.go.

remote.go's content：

package remote  // "hello.go" will refer variable Str with name "remote.Str", the package name "remote" is also used as namespace.

var Str = "I Love Aoi Sola" // Variable/Function name's first letter must be uppercase, or they can't be accessed out of current module.

Then push "A:/Learn/Go/Remote" to a remote repository and change the module name to the repository's url:

Change Module Name1

Change Module Name2

Change hello.go's content to：

package main

import "github.com/ChengAnXu2014/GoModule"   // module name is also remote repository's URL.

func main(){
  println(remote.Str)    // refer varialbe Str with "remote.Str".
}

Run go mod tidy in "A:/Learn/Go/Work" to upgrade module Aoi/Sola's go.mod file.
Golang will download module github.com/ChengAnXu2014/GoModule's content to the directory specified by environment variable GOPATH.

And module Aoi/Sola's go.mod file's content will be like:

module Aoi/Sola

go 1.17

require github.com/ChengAnXu2014/GoModule v0.0.0-20210624111742-626d6b55d79e // means current module require module `github.com/ChengAnXu2014/GoModule`.
// if any tags is created, the most recent tag's commit will be used, vx.x.x will be the most recent tag number.
// if no tag is created, the most recent commit is used, vx.x.x will be v0.0.0
// 20210624111742 is the used commit's commit time(2021/06/24 11:17:42).
// 626d6b55d79e is the used commit's name, and is also the used commit's checksum.

For security, Golang won't access third-party repository by default, to change that you must set the environment variable GOPRIVATE(see below).

Now run go run hello.go in "A:/Learn/Go/Work", "I Love Aoi Sola" will be output through standard error.

If you changed remote module, then delete "require ..." statement from module Aoi/Sola's go.mod and run go mod tidy.
Golang will download from remote module and upgrade module Aoi/Sola's go.mod again.

GOPRIVATE

For security, Golang won't access third-party repository by default, to change that you must set the environment variable GOPRIVATE.

Set GOPRIVATE

Multiple URLs can be separated by ,.

Import Local Module

Change "A:/Learn/Go/Remote/remote.go" to:

package remote

var Str = "I'm Local Module!!!"

Change module Aoi/Sola's go.mod to:

module Aoi/Sola

go 1.17

replace github.com/ChengAnXu2014/GoModule => A:/Learn/Go/Remote

delete "require..." statement and add "replace..." statement to map github.com/ChengAnXu2014/GoModule to local directory "A:/Learn/Go/Remote"

Then run go mod tidy in "A:/Learn/Go/Work" to upgrade module Aoi/Sola's go.mod.

Run go run hello.go in "A:/Learn/Go/Work", you will see "I'm Local Module!!!" in standard error output.

Install and Config Golang on Windows10

Plume — Fri, 19 Nov 2021 06:42:29 +0000

Download Page: https://golang.org.dl

.msi is Windows's new install package file just double click it to install.

Environment Variable Config

Variable GO111MODULE's value should be set to "on" to enable module control tools(go mod tools).

Variable GOBIN's value should be set to "$go/bin" where the "$go" is the directory where you installed Golang.
So that the Windows system can find the go tools in "$go/bin" when you perform them in cmd.

Variable GOPATH's value should be a path, which will be used to save the modules installed from the remote repository.

LLVM-IR

Plume — Sun, 14 Nov 2021 10:38:08 +0000

Navigation

3 Equivalent Forms
Infinite Virtual Register Set
load and store Instruction
Three Address Form Assignment
Static Single Assignment
Global and Local Identifiers
icmp Instruction

To Be Continued...

3 Equivalent Forms

LLVM-IR have 3 equivalent forms:

textual form for developers to read and edit manually.
binary form(also called bitcode form) for storing on disk(in .o and .exe files).
in-memory form for compilers and optimizers to use.

These 3 forms can be transformed between each other with no information lose.
Since these 3 forms are equivalent and only the textual form of them is readable, we only introduce the textual form in this article.

Infinite Virtual Register Set

LLVM-IR use a Virtual Register Set which have infinite virtual registers.
When LLVM-IR code is transformed to Native Code, the virtual registers are maped to the real registers of the Host Machine.
Since the Host Machine's registers are finite, the used registers that are nolonger referenced will be reused to map new virtual registers.

Code 1 LLVM-IR Code for Infinite Virtual Register Set:

%a = add i64 9,  8      ; i64 is 64-bit integer type
%b = add i64 %a, 7      ; after ';' are Comments
%c = add i64 %b, %a     ; LLVM-IR's register name must have a prefix: "%"
%d = add i64 %c, %b
%e = add i64 %d, %c
...

Code 2 Pseudo Code After Register Mapping:

AX = add i64 9,  8
BX = add i64 AX, 7
CX = add i64 BX, AX
AX = add i64 CX, BX
BX = add i64 AX, CX
...

Virtual Registers can be used to hold scalar values: integers, floating-point numbers, pointers.

`load` and `store` Instruction

load instruction is used to "read" from memory, and is the only way to "read" from memory;
store instruction is used to "write" to memory, and is the only way to "write" to memory.
load and store access memory with a pointer.

Code 3 LLVM-IR Code for load and store:

%a = load i64, i64* %ptr      ; load i64 type value from memory pointed by i64* type pointer register %ptr
store  i64 99, i64* %ptr      ; store i64 type value 99 into memory pointed by i64* type pointer register %ptr

Three Address Form Assignment

LLVM-IR's assignment-statements always have a =, and there must be one and only one register at the left side of the =.
You can see that, the assignment-statements in Code 1, Code 2 and Code 3 are all in Three Address Form.

Static Single Assignment

In LLVM-IR code, there can be only one assignment-statement for each register.
Although loop code can perform one assignment-statement many times, phi instruction can put many possible values at right side of a assignment-statement's =, SSA(Static Single Assignment) and TAF(Three Adress Form) still significantly simplifies the data-flow of LLVM-IR code, so that many analyses can get the data-flow information they need from LLVM-IR code without any sophisticated data-flow analysis.

But how can we transform non-SSA source code to SSA LLVM-IR code?

Code 4 non-SSA Go Code:

var a i64 = 99
a = 88
a = 77
a = 66

Code 5 Corresponding SSA LLVM-IR Code:

%a = i64 99
%0 = i64 88
%1 = i64 77
%2 = i64 66

When transform non-SSA source code to SSA LLVM-IR code, the compiler auto generate register names with % prefix and numbers.

Global and Local Identifiers

LLVM-IR have two kinds of identifiers: Global Identifier and Local Identifier.
Global Identifiers begin with the @ character, Local Identifiers begin with the % character.
Global Identifiers contain Global Variable names and Function names.
Local Identifiers contain Register names, Label names and User Defined Type names.

We'll illustrate Global Variables later, Labels are similar to the labels in high-level languages.

Code 6 GO Code for Label:

var i i64 = 0
// 'loop' is a label
loop:
i++
println(i)
if i != 10{goto loop}
// other code

Code 7 LLVM-IR Code for Label:

; 'enter', 'loop', 'end' are labels
enter:
    %i = i64 0
loop:
    %i1   = phi i64 [ %i, %enter ], [ %i2, %loop ]     ; if dominated by label 'enter' %i1 = %i;     if dominated by label 'loop' %i1 = %i2.
    %i2   = add i64 %i1, 1
    %cond = icmp ne i64 %i2, 10      ; if %i2 != 10 %cond is "true";     otherwise %cond is "false"
    br i1 %cond, label %loop, label %end      ; if %cond is "true" jump to label 'loop';     otherwise jump to label 'end'
end:
    ;code for label 'end'

icmp, br and phi instructions will be illustrated later.

Struct is a typical example of User Defined Types.

Code 8 GO Code for Struct:

// 'usertype' is a user defined type name
type usertype struct{
    a i8
    b i16
    c i32
    d i64
}

Code 9 LLVM-IR Code for Struct:

%usertype = type { i8, i16, i32, i64 }      ; '%usertype' is a user defined type name

`icmp` Instruction

icmp is used to compare values, return a bool value.

Syntax:

<result> = icmp <cond> <ty> <op1>, <op2>

<cond> is keyword that indicates witch kind of compare to perform.

<ty> is the type of <op1> and <op2>.

<op1> and <op2> are the values to be compared, they can be integer, float-pointing or pointer type, and they must be in the same type.

<cond>s:

eq: equal
ne: not equal
ugt: unsigned greater than
uge: unsigned greater or equal
ult: unsigned less than
ule: unsigned less or equal
sgt: signed greater than
sge: signed greater or equal
slt: signed less than
sle: signed less or equal

Examples:

Code 10 Simple examples for icmp:

%result1 = icmp eq i32 4, 5          ; yields: %result1=false
%result2 = icmp ult i16  4, 5        ; yields: %result2=true
%result3 = icmp sgt i16  4, 5        ; yields: %result3=false
%result4 = icmp sge i16  4, 5        ; yields: %result4=false

Code 11 Complicated examples for icmp:

; Use <cond> ne(not equal) to compare float* type pointer %X and itself.
%result5 = icmp ne float* %X, %X     ; yields: %result5=false

; Use <cond> ule(unsigned less or equal) to compare -4 and 5
; first convert -4 to unsigned 252, then compare 252 and 5
; 252 > 5, so -4 ule 5 is false.
%result6 = icmp ule i16 -4, 5        ; yields: %result6=false

Code 12 Unsure examples for icmp:

; These examples combine two compare operations in one instruction:
; 1. Use <cond> ugt(unsigned greater than) to compare i16 type values 0 and 1; 0 < 1, so 0 ugt 1 is false.
; 2. Use <cond> ugt to compare i16 type values 3 and 2; 3 > 2, so 3 ugt 2 is true.

<%result7, %result8> = icmp ugt <2 x i16> <i16 0, i16 3>, <i16 1, i16 2>    ; yields: %result7=false; %result8=true
%resultptr = icmp ugt <2 x i16> <i16 0, i16 3>, <i16 1, i16 2> ; %resultptr is a <2 x i1>* type pointer, the vector it points to is <i1 0, i1 1> where 'i1 0' represents false, 'i1 1' represents true.

There is no example for multiple compare in LLVM-IR's documentation so I make two by myself, I'm not sure which one is correct or they are all uncorrect.

To Be Continued...

br Instruction
phi Instruction
Global Variable

Overview of LLVM Architecture

Plume — Mon, 01 Nov 2021 07:22:44 +0000

First of all, let's see a graph of LLVM Architecture.

Picture 1: Click here to see HD picture

As you can see in Picture 1, source code of arbitrary language(C, C++, Go, etc) are compiled by an appropriate compiler to LLVM-IR(LLVM's Intermidiate code Representation) codes, these LLVM-IR codes are saved in .o files(object files).
Then, an Optimizing Linker is used to link the .o files, libraries of the native system, and libraries of LLVM Architecture into a .exe file, the .exe file contains both LLVM-IR and native code(Machine Code which can run on the Host Machine).

Now, let's have a break

Before we continue describing Picture 1, we'd better illustrate the meaning of Offline and Profile & Trace Info first.

According to the context, Offline can mean:

While .exe file is not running(in idle time).
After .exe file is generated.
After the program(.exe file) is installed.
On Host Machine(User's Computer).
Without source code(.c, .cpp, .go, etc).

Profile means:

Information about which regions of the .exe file's code runs more frequently on Host Machine, these frequently-run code regions are called Hot Codes.

Continue

After .exe file is generated, the Run-time Optimizer is used to capture Profile & Trace Info, use the information contained by Profile to find Hot Code, optimize the LLVM-IR contained by .exe file to improve Hot Code's performance at the cost of Cold Code's performance. This kind of optimization is called Profile-guided Optimization.
Then, the Run-time Optimizer passes the generated Native Code to Host Machine to run it.

Sometimes, the Profile-guided Optimization is too sophisticated to perform at run-time or the Profile-guided Optimization is valuable enough to retain long-term, so the Profile information is passed to the Offline Reoptimizer, the Offline Reoptimizer use the information contained by Profile to find Hot Code, optimize the LLVM-IR contained by .exe file to improve Hot Code's performance at the cost of Cold Code's performance.
Then, the Offline Reoptimizer passes the reoptimized LLVM-IR and Native Code to .exe file to save them long-term.