Converting into SSA form

Hi,

Can anyone tell me, whether it is possible to convert a program into
SSA form without considering algebric equivalence ?

regards,
Chayan

You can use STOREs and LOADs on memory and then use mem2reg pass.

But, the mem2reg pass removes all load store instructions. It replaces
all variables by their if possible (kind of constant propagation). I
have generated the bitcode of the source program and the applied the
mem2reg pass and obviously not getting desired thing.

What I want is convert it into SSA form without replacing any variable
by their constant value. Please elaborate on your point.

Also, what call an inbuilt pass from my own pass after doing some analysis.

Thank you & regards,
Chayan

Hello Chayan-

I think you might find Kaleidoscope tutorial (LLVM Tutorial: Table of Contents — LLVM 16.0.0git documentation), particularly the section on mutable variables and SSA construction (http://llvm.org/docs/tutorial/LangImpl7.html), useful here.

Alistair

Can you give a short sample program and what you expect the output to look like?

-Eli

Suppose my Input function is like :

myfunc(int x,int y){
    int a=2, b=3,c=5;
    if(x>y) {
        c=a+b;
        a=6;
    }
    else {
        c=a*b;
        b=4;
    }
    a=c+a;
    c=a+b;
}

and the output should be :

myfunc(int x,int y){
    int a.0=2, b.0=3,c.0=5;
    if(x>y) {
        c.1=a.0+b.0;
        a.1=6;
    }
    else {
        c.2=a.0*b.0;
        b.1=4;
    }
    a.2=phi(a.1,a.0);
    b.2=phi(b.0,b.1);
    c.3=phi(c.1,c.2);
    a.3=c.3+a.2;
    c.4=a.3+b.2;
}

Thank you for your response.

There is no existing pass to do this in LLVM, mostly because it
wouldn't be useful for optimizing programs. From your input, mem2reg
produces:

define i32 @myfunc(i32 %x, i32 %y) nounwind {
entry:
  %cmp = icmp sgt i32 %x, %y ; <i1> [#uses=1]
  br i1 %cmp, label %if.then, label %if.else

if.then: ; preds = %entry
  %add = add nsw i32 2, 3 ; <i32> [#uses=1]
  br label %if.end

if.else: ; preds = %entry
  %mul = mul i32 2, 3 ; <i32> [#uses=1]
  br label %if.end

if.end: ; preds = %if.else, %if.then
  %a.0 = phi i32 [ 6, %if.then ], [ 2, %if.else ] ; <i32> [#uses=1]
  %b.0 = phi i32 [ 3, %if.then ], [ 4, %if.else ] ; <i32> [#uses=1]
  %c.0 = phi i32 [ %add, %if.then ], [ %mul, %if.else ] ; <i32> [#uses=1]
  %add8 = add nsw i32 %c.0, %a.0 ; <i32> [#uses=1]
  %add11 = add nsw i32 %add8, %b.0 ; <i32> [#uses=1]
  ret i32 %add11
}

In order to preserve the constants' names from the original program,
mem2reg would have to insert operations like

%a.0 = bitcast i32 2 to i32

which subsequent optimizers would have to remove again, slowing down
compilation unnecessarily.

The original program does have an instruction
  store i32 %add11, i32* %c
Without inserting extraneous instructions, mem2reg could rename %add11
to %c.1 when it eliminates that store, which might make the optimized
form a little easier to read. On the other hand, doing that would slow
down mem2reg (I don't know how much), so it shouldn't be on by
default.

What are you really trying to do?

Hi Jeffrey,

Actually I am trying to implement "E-path PRE" which is based on
non-algebric equivallence. So, the variable names need to be
preserved.

You said that I need to insert these to preserve variable
%a.0 = bitcast i32 2 to i32

So, these need to be inserted before the mem2reg pass or within the pass.
In first case, how to call an inbuilt pass after doing some analysis
In second case, how to change/modify an inbuilt pass?

Please elaborate on this.

Thank you,
Chayan

Then why do you want to run mem2reg before your optimization in the first place?

-Eli

E-path PRE requires the program in SSA form like SSAPRE algorithm.
Then it finds the eliminatable path (e-path) for an expression and
converts partially redundant to fully redundant and removes redundancy

Chayan

E-path PRE requires the program in SSA form like SSAPRE algorithm.
Then it finds the eliminatable path (e-path) for an expression and
converts partially redundant to fully redundant and removes redundancy

An SSA-based algorithm is usually expressed in terms of SSA registers,
not variables from before conversion to SSA, but I won't question your
algorithm.

If you want control over the mem2reg process, don't use the pass; you
can call llvm::PromoteMemToReg directly.

-Eli