llvm dev - May 2017 - Instruction selection for 'load' based on static vs. dynamic data

Hi,

I've been looking at the new AVR backend lately, and one issue I've
found is that all 'load' IR instructions are matched using the
'ld'
AVR instruction, including 'load's for lookup tables generated from
switches.

On the AVR architecture, RAM and the program image are in completely
separated namespaces. There's a distinct 'lpm' (Load from Program
Memory) instruction that can load data from .text. So the nice way of
getting this to work is to select 'lpm' for those switch lookup table
'load's, thereby avoiding the memory footprint and the runtime cost of
copying the tables to RAM at startup. However, we still need to select
'ld' for other 'load's.

To give a concrete example, here's an LLVM IR snippet that should be
lowered to 'lpm':

     @switch.table = private unnamed_addr constant [15 x i8] 
c"\01\01\01\01\01\00\00\00\00\00\00\00\00\00\01"

     switch.lookup:                                    ; preds = %start
       %2 = sext i8 %0 to i16
       %switch.gep = getelementptr inbounds [15 x i8], [15 x i8]* 
@switch.table, i16 0, i16 %2
       %switch.load = load i8, i8* %switch.gep, align 1
       br label %bb8

and here's one that should be lowered to 'ld':

     %S = type { i8 }

     start:
       %1 = getelementptr inbounds %S, %S* %0, i16 0, i32 0
       %2 = load i8, i8* %1, align 1
       ret i8 %2
     }

So my question is, what kind of pattern matching can I do in my 'lpm'
and 'ld' instructions that it would be able to make a distinction
about these two usecases?


Thanks,
         Gergo

-- 

   .--= ULLA! =-----------------.
    \     http://gergo.erdi.hu   \
     `---= gergo at erdi.hu =-------'
Have you heard about the new OO COBOL language? "ADD 1 TO COBOL GIVING
COBOL"

>
> To give a concrete example, here's an LLVM IR snippet that should be
> lowered to 'lpm':
>
>     @switch.table = private unnamed_addr constant [15 x i8]
> c"\01\01\01\01\01\00\00\00\00\00\00\00\00\00\01"
>
>     switch.lookup:                                    ; preds = %start
>       %2 = sext i8 %0 to i16
>       %switch.gep = getelementptr inbounds [15 x i8], [15 x i8]*
> @switch.table, i16 0, i16 %2
>       %switch.load = load i8, i8* %switch.gep, align 1
>       br label %bb8
>
> and here's one that should be lowered to 'ld':
>
>     %S = type { i8 }
>
>     start:
>       %1 = getelementptr inbounds %S, %S* %0, i16 0, i32 0
>       %2 = load i8, i8* %1, align 1
>       ret i8 %2
>     }
>
> So my question is, what kind of pattern matching can I do in my
'lpm'
> and 'ld' instructions that it would be able to make a distinction
> about these two usecases?

​I can only think of examining the load operand, which is a result of
getelementptr​. Then check the second
argument of getelementptr​ (%0 or @switch.table).

Maybe Leslie (cc'ed) can answer this question.

-- 
Wei-Ren Chen (陳韋任)
Homepage: https://people.cs.nctu.edu.tw/~chenwj
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170508/c6b2d06a/attachment.html>

You can create the differentiation between objects in the data memory 
and in the program memory in LowerGlobalAddress (e.g. you can create 
different ISD opcodes that generate these addresses) and then use those 
to select corresponding instructions.

-Krzysztof

On 5/7/2017 10:39 AM, Dr. ERDI Gergo via llvm-dev wrote:
> Hi,
> 
> I've been looking at the new AVR backend lately, and one issue I've
> found is that all 'load' IR instructions are matched using the
'ld'
> AVR instruction, including 'load's for lookup tables generated from
> switches.
> 
> On the AVR architecture, RAM and the program image are in completely
> separated namespaces. There's a distinct 'lpm' (Load from
Program
> Memory) instruction that can load data from .text. So the nice way of
> getting this to work is to select 'lpm' for those switch lookup
table
> 'load's, thereby avoiding the memory footprint and the runtime cost
of
> copying the tables to RAM at startup. However, we still need to select
> 'ld' for other 'load's.
> 
> To give a concrete example, here's an LLVM IR snippet that should be
> lowered to 'lpm':
> 
>      @switch.table = private unnamed_addr constant [15 x i8] 
> c"\01\01\01\01\01\00\00\00\00\00\00\00\00\00\01"
> 
>      switch.lookup:                                    ; preds = %start
>        %2 = sext i8 %0 to i16
>        %switch.gep = getelementptr inbounds [15 x i8], [15 x i8]* 
> @switch.table, i16 0, i16 %2
>        %switch.load = load i8, i8* %switch.gep, align 1
>        br label %bb8
> 
> and here's one that should be lowered to 'ld':
> 
>      %S = type { i8 }
> 
>      start:
>        %1 = getelementptr inbounds %S, %S* %0, i16 0, i32 0
>        %2 = load i8, i8* %1, align 1
>        ret i8 %2
>      }
> 
> So my question is, what kind of pattern matching can I do in my
'lpm'
> and 'ld' instructions that it would be able to make a distinction
> about these two usecases?
> 
> 
> Thanks,
>          Gergo
> 
-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

On Mon, 8 May 2017, Krzysztof Parzyszek via llvm-dev wrote:
> You can create the differentiation between objects in the data memory and
in
> the program memory in LowerGlobalAddress (e.g. you can create different ISD
> opcodes that generate these addresses) and then use those to select 
> corresponding instructions.
Right, which is how I also understand Zhai Xiang's suggestion with the 
link to existing AVR target code. This is already done to some extent, 
since the AVR backend already inserts an AVRISD::WRAPPER node to mark the 
static data's address.

However, what's still missing with that plan is how to propagate that 
information "upwards". By the time it gets to instruction selection,
the
`getelementptr` is already expanded into some arithmetic expression of a 
base address and some arbitrary offset calculations.

So for example, with this code:

%switch.gep = getelementptr inbounds [15 x i8], [15 x i8]* @switch.table, i16 0,
i16 %2
%switch.load = load i8, i8* %switch.gep, align 1

by instrucion selection time, the argument to 'load' is

(add
   (sign_extend (CopyFromReg %vreg2))
   (WRAPPER TargetGlobalAddress<@switch.table>))

not a WRAPPER directly.