[LLVMdev] identifying all dependent instructions through multi-levels of def-use relationship
John Criswell
criswell at illinois.edu
Wed May 4 17:20:00 PDT 2011
Dear Chuck,
I haven't read all of the details, but it seems that what you need to do
is to clone defs before you clone any uses of the def. To do that, you
want to iterate over the instructions in dominator-tree order.
To do that, you first construct the dominator tree (there is an LLVM
analysis pass that does that). Then, you iterate over the basic blocks
in the dominator tree from the root of the tree to the bottom; make sure
you process each basic block before processing any of its children.
When you process a basic block, you clone the instructions in that basic
block.
This ensures that you process all defs before uses in a def-use chain
for everything except phi-nodes. Phi-nodes are special because they are
not dominated by their inputs. If your phi-node copying is simple, you
want to create a dummy phi-node whose inputs are all undef. After
you've finished copying all instructions, you go back and change the
operands of the phi-nodes to be what you want them to be.
The above works well for simple cases in which knowing where to insert
phi-nodes is easy (e.g., you are inserting instrumentation in such a way
that you are adding a phi-node that mirrors an existing phi-node within
the program). Knowing where to put phi-nodes can be difficult in
general. For such cases, you should make alloca'ed memory locations for
each variable you are adding in the program. You then use load/store
instructions to read/write the data into/out of SSA variables,
eliminating the need to add phi-nodes. Then, when your pass is
finished, run the mem2reg pass; it will convert your alloca'ed variables
into SSA virtual registers and insert phi-nodes for you.
As an aside, knowing how the SSA construction algorithm works is what
led me to understand how to visit defs before uses in LLVM IR. I
recommend reading Cytron et. al.'s paper
(http://portal.acm.org/citation.cfm?id=115320).
-- John T.
On 5/4/11 6:16 PM, Chuck Zhao wrote:
> While working on my optimization pass (a Function Pass), I try to
> replicate a call instruction and insert it at some earlier location
> (similar to LICM).
> However, the instruction I am trying to replicate has dependencies on
> an uncertain number of instructions that are used to generate an address.
>
> A simple example (IR segment):
>
> define void @foo() nounwind {
> entry:
> %a = alloca i32, align 4; ; [0]
> %b = alloca i32, align 4
> %c = alloca i32, align 4
> %d = alloca i32, align 4
> %e = alloca i32, align 4
> %f = alloca i32, align 4
> %A = alloca [100 x i32], align 4
> call void @start_ckpt() nounwind
> %0 = call i32 @puts(i8* getelementptr inbounds ([8 x i8]* @.str, i32
> 0, i32 0)) nounwind
> %a1 = bitcast i32* %a to i8* ; [1]
> call void @bkp_memory(i8* %a1, i32 4) nounwind ; [2] the
> function call instruction that I am about to replicate
>
> I need to make a copy/clone of the call instruction [2]. However,
> I->clone() failed on [2], because [2] has dependency chained
> instructions that all will need to be cloned before itself can.
> The back-trace of dependent instructions go to: [1] and [0]. Thus both
> [1] and [2] need to be cloned in order before replicate [2].
>
>
> A more interesting example is given below (IR Segment):
>
> bb1: ; preds = %bb29,
> %bb30.preheader
> %match_length.354 = phi i32 [ %match_length.2.ph, %bb29 ], [ 2,
> %bb30.preheader ]
> %match_available.153 = phi i32 [ %match_available.0.ph, %bb29 ], [
> 0, %bb30.preheader ]
> tail call void @start_ckpt() nounwind noinline
> %88 = load i32* @ins_h, align 4 ; [0]
> %89 = shl i32 %88, 5 ;[1]
> %90 = load i32* @strstart, align 4 ; [2]
> %91 = add i32 %90, 2 ; [3]
> %92 = getelementptr inbounds [65536 x i8]* @window, i32 0, i32 %91
> ; [4]
> %93 = load i8* %92, align 1 ; [5]
> %94 = zext i8 %93 to i32 ; [6]
> %.masked = and i32 %89, 32736 ;[7]
> %95 = xor i32 %94, %.masked ;[8]
> %take_addr = getelementptr i32* @ins_h
> %96 = bitcast i32* %take_addr to i8*
> call void @bkp_memory(i8* %96, i32 4)
> store i32 %95, i32* @ins_h, align 4
> %97 = and i32 %90, 32767
> %.sum39 = or i32 %95, 32768
> %98 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32 %.sum39
> %99 = load i16* %98, align 2
> %100 = zext i16 %99 to i32
> %101 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32 %97
> %take_addr1 = getelementptr i16* %101
> %102 = bitcast i16* %take_addr1 to i8*
> call void @bkp_memory(i8* %102, i32 2)
> store i16 %99, i16* %101, align 2
> %103 = trunc i32 %90 to i16
> %.sum73 = or i32 %95, 32768 ;[9]
> %104 = getelementptr inbounds [65536 x i16]* @prev, i32 0, i32
> %.sum73 ;[10]
> %take_addr2 = getelementptr i16* %104 ; [11]
> %105 = bitcast i16* %take_addr2 to i8* ;[12]
> call void @bkp_memory(i8* %105, i32 2); [13]
>
> Again, attempting to replicate a call instruction [13]. But, this time
> the dependency chain is much longer and goes way further back, which
> includes [0] .. [12].
>
> Knowing this dependency chain could be arbitrarily long, with multiple
> levels of use-def and def-use relationships. The termination
> conditions could be one of:
> (1). local variable declaration (Alloca)
> (2). global variable
> (3). const
>
> I think it will need a depth-first or breath-first search to identify
> all related instructions before the I->clone() can possibly happen.
>
> I am asking if there is a known-good way of doing this, or some LLVM
> API provided, since making a copy of an existing LLVM instruction
> seems to be a very common task in code transformations.
>
>
> Thank you very much
>
> Chuck
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110504/781be4d4/attachment.html>
More information about the llvm-dev
mailing list