Re: suggestion for Merging LLVM

[Jeff Garzik <jeff@garzik.org>]

On 11/22/2011 03:38 PM, Pekka Enberg wrote:
> So pasting the above test program tohttp://llvm.org/demo/  and
> switching to "LLVM C++ API code" target seems to suggest you're
> interested in the LLVMReplaceAllUsesWith() API for forward references.

Sent pull req via github.

List implementation is cheesy (inefficient if list ever gets woefully 
large) singly-linked list, but it is pretty simple.  Turned out that 
postponing LLVMAddIncoming() call works better than 
LLVMReplaceAllUsesWith() API:


(warning: do not apply directly, patch is unfortunately word-wrapped; 
see pull request)

--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -17,11 +17,21 @@
  #include "linearize.h"
  #include "flow.h"

+struct phi_fwd {
+       struct phi_fwd                  *next;
+
+       LLVMValueRef                    phi;
+       pseudo_t                        pseudo;
+       bool                            resolved;
+};
+
  struct function {
         LLVMBuilderRef                  builder;
         LLVMTypeRef                     type;
         LLVMValueRef                    fn;
         LLVMModuleRef                   module;
+
+       struct phi_fwd                  *fwd_list;
  };

  static inline bool symbol_is_fp_type(struct symbol *sym)
@@ -794,6 +804,67 @@ static void output_op_call(struct function *fn, 
struct instruction *insn)
         insn->target->priv = target;
  }

+static void store_phi_fwd(struct function *fn, LLVMValueRef phi,
+                         pseudo_t pseudo)
+{
+       struct phi_fwd *fwd;
+
+       fwd = calloc(1, sizeof(*fwd));
+       fwd->phi = phi;
+       fwd->pseudo = pseudo;
+
+       /* append fwd ref to function-wide list */
+       if (!fn->fwd_list)
+               fn->fwd_list = fwd;
+       else {
+               struct phi_fwd *last = fn->fwd_list;
+
+               while (last->next)
+                       last = last->next;
+               last->next = fwd;
+       }
+}
+
+static void output_phi_fwd(struct function *fn, pseudo_t pseudo, 
LLVMValueRef v)
+{
+       struct phi_fwd *fwd = fn->fwd_list;
+
+       while (fwd) {
+               struct phi_fwd *tmp;
+
+               tmp = fwd;
+               fwd = fwd->next;
+
+               if (tmp->pseudo == pseudo && !tmp->resolved) {
+                       LLVMValueRef phi_vals[1];
+                       LLVMBasicBlockRef phi_blks[1];
+
+                       phi_vals[0] = v;
+                       phi_blks[0] = pseudo->def->bb->priv;
+
+                       LLVMAddIncoming(tmp->phi, phi_vals, phi_blks, 1);
+
+                       tmp->resolved = true;
+               }
+       }
+}
+
+static void output_op_phisrc(struct function *fn, struct instruction *insn)
+{
+       LLVMValueRef v;
+
+       assert(insn->target->priv == NULL);
+
+       /* target = src */
+       v = pseudo_to_value(fn, insn, insn->phi_src);
+       insn->target->priv = v;
+
+       assert(insn->target->priv != NULL);
+
+       /* resolve forward references to this phi source, if present */
+       output_phi_fwd(fn, insn->target, v);
+}
+
  static void output_op_phi(struct function *fn, struct instruction *insn)
  {
         pseudo_t phi;
@@ -803,7 +874,7 @@ static void output_op_phi(struct function *fn, 
struct instruction *insn)
                                 "phi");
         int pll = 0;
         FOR_EACH_PTR(insn->phi_list, phi) {
-               if (pseudo_to_value(fn, insn, phi))     /* skip VOID */
+               if (pseudo_to_value(fn, insn, phi))     /* skip VOID, 
fwd refs*/
                         pll++;
         } END_FOR_EACH_PTR(phi);

@@ -815,11 +886,13 @@ static void output_op_phi(struct function *fn, 
struct instruction *insn)
                 LLVMValueRef v;

                 v = pseudo_to_value(fn, insn, phi);
-               if (v) {                        /* skip VOID */
+               if (v) {                        /* skip VOID, fwd refs */
                         phi_vals[idx] = v;
                         phi_blks[idx] = phi->def->bb->priv;
                         idx++;
                 }
+               else if (phi->type == PSEUDO_PHI)       /* fwd ref */
+                       store_phi_fwd(fn, target, phi);
         } END_FOR_EACH_PTR(phi);

         LLVMAddIncoming(target, phi_vals, phi_blks, pll);
@@ -916,8 +989,7 @@ static void output_insn(struct function *fn, struct 
instruction *insn)
                 assert(0);
                 break;
         case OP_PHISOURCE:
-               /* target = src */
-               insn->target->priv = pseudo_to_value(fn, insn, 
insn->phi_src);
+               output_op_phisrc(fn, insn);
                 break;
         case OP_PHI:
                 output_op_phi(fn, insn);
@@ -1026,7 +1098,7 @@ static void output_fn(LLVMModuleRef module, struct 
entrypoint *ep)
         struct symbol *ret_type = sym->ctype.base_type->ctype.base_type;
         LLVMTypeRef arg_types[MAX_ARGS];
         LLVMTypeRef return_type;
-       struct function function;
+       struct function function = { .module = module };
         struct basic_block *bb;
         struct symbol *arg;
         const char *name;
@@ -1043,8 +1115,6 @@ static void output_fn(LLVMModuleRef module, struct 
entrypoint *ep)

         return_type = symbol_type(module, ret_type);

-       function.module = module;