[LLVMdev] How to define 'kill' in traditional Available Expressions analysis?

[Rekha R]

Hi,

Currently I am in the process of understanding the LLVM code base. For this
purpose I am trying to implement the traditional Available Expressions
analysis (as in ALSU, based on lexical aspect of an expression).

So, given an instruction, we have to define expressions generated by the
Instruction and other expressions killed by this instruction. Say for
example, in the following code segment

 %1 = call i8* @malloc(i32 4)                    ; <i8*> [#uses=1]
  %2 = bitcast i8* %1 to i32*                     ; <i32*> [#uses=4]
  store i32 5, i32* %2
  %3 = load i32* %2                               ; <i32> [#uses=1]
  %4 = add nsw i32 %3, 10                         ; <i32> [#uses=0]
  store i32 20, i32* %2
  %5 = load i32* %2                               ; <i32> [#uses=1]
  %6 = add nsw i32 %5, 10

when processing the second store instruction, in particular, it should kill
the instruction labelled %3.

My question is, when processing a statement how to identify the
instructions it can kill? (As I have already mentioned, I am concentrating
on the lexical aspect of an Instruction and not on the value based aspect,
as in SSA. Hence the need for doing 'kill'.)

This question arose because, based on my understanding of the concept of an
Instruction in LLVM IR, values (operands) used by an instruction points to
the definition of that value and not to other uses of the same value. (Or
that is how I understood the concept of an Instruction in LLVM IR. Kindly
correct me if I am wrong.) Hence I need some mechanism to track other uses
of the same value.

-- 
Rekha
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131011/b03d4729/attachment.html>