google transpile error need help

[tararagi]

Dear Sir,

I compiled my cc file, but got an error I can't handle. I would be happy with your help.

The code is a "quick sort" implementation as attached, and the error message is the following.

root@2ea39926f6ce:/usr/src/fhe# bazel build -c opt //transpiler/examples/test5:test5_tfhe.transpiled_files
:
Use --sandbox_debug to see verbose messages from the sandbox
Parsing file 'transpiler/examples/test5/test5.cc' with clang...
Generating IR...
/bin/bash: line 1: 15903 Segmentation fault bazel-out/k8-opt-exec-2B5CBBC6/bin/external/com_google_xls/xls/contrib/xlscc/xlscc transpiler/examples/test5/test5.cc -meta_out bazel-out/k8-opt/bin/transpiler/examples/test5/test5_tfhe_meta.proto > bazel-out/k8-opt/bin/transpiler/examples/test5/test5_tfhe.ir
Target //transpiler/examples/test5:test5_tfhe.transpiled_files failed to build
Use --verbose_failures to see the command lines of failed build steps.
INFO: Elapsed time: 0.256s, Critical Path: 0.04s
INFO: 2 processes: 2 internal.
FAILED: Build did NOT complete successfully

In my code, I have used "break" control and recursive call. Does they cause any problem in transpile?

I am appreciate it very much if you help me.

Best regards! -- Tadashi Araragi

test5.zip

[j2kun]

I've reduced your example to the following slightly simplified subset (with no recursive calls or structs) and it still times out when compiling

#pragma hls_top
void sort(int list[10], char L, char R) {
  char i, j;
  int pv;
  int tmp;

  i = L;
  j = R;

  pv = list[(L + R) / 2];

#pragma hls_unroll yes
  for (char k = 0; k < 4; k++) {
#pragma hls_unroll yes
    for (char ki = 0; ki < 4; ki++) {
      if (list[i] < pv) break;
      i++;
    }

#pragma hls_unroll yes
    for (char kj = 0; kj < 4; kj++) {
      if (pv < list[j]) break;
      j--;
    }

    if (i >= j) break;

    tmp = list[i];
    list[i] = list[j];
    list[j] = tmp;

    i++;
    j--;
  }

However, when I remove the second nested loop, it compiles after about 3 minutes.

This project uses xlscc, which in turn uses a solver to prove the compiled code terminates before unrolling the loops within. It seems that their solver is having difficulty proving this code terminates. I can try tinkering with it to see if it's superficial, but I imagine your segfault may be related to this. I've also reached out to the XLS team internally to see if they can diagnose the issue.

[tararagi]

I have parametrized the length of "for loop" as below, and got another compile Error message.

List Test5::process(List x, int L, int R, int n) {

int i, j; int pv; int tmp;

i = L; j = R;

pv = x.list[(L + R)/2];

pragma hls_unroll yes

for(int k=0; k<n; k++){

      #pragma hls_unroll yes
      for(int ki=0; ki<n; ki++){
            if(x.list[i] < pv)
              break;

            i++;
      }

      #pragma hls_unroll yes
      for(int kj=0; kj<n; kj++){
            if(pv < x.list[j])
              break;

            j--;
      }

Use --sandbox_debug to see verbose messages from the sandbox Parsing file 'transpiler/examples/test5/test5.cc' with clang... Generating IR... UNIMPLEMENTED: Param not implemented in IrInterpreter Target //transpiler/examples/test5:test5_tfhe.transpiled_files failed to build Use --verbose_failures to see the command lines of failed build steps. INFO: Elapsed time: 9.180s, Critical Path: 0.99s INFO: 2 processes: 2 internal. FAILED: Build did NOT complete successfully

[j2kun]

What is the build rule you set up for this one (i.e., the params to fhe_cc_library)? I think this is a missing feature from the interpreter=True for optimizer=xls, and you might be able to bypass it by using optimizer=yosys

[j2kun]

For context, this is the line it's hitting https://github.com/google/xls/blob/52c8e7e30dfa25cbafe99815f80d214c414364dd/xls/interpreter/ir_interpreter.cc#L720

Though if it's failing at the step of generating the IR, that may not be what I mentioned in the previous comment...

[j2kun]

Oh I think I see now. When n is an argument to the function then it can't unroll the loop because it doesn't know how many iterations to unroll. For any FHE program, all loops need to have statically-known bounds. And in this case the number of iterations of the loop is going to be converted by the compiler to an encrypted parameter, so this is simply not possible.

[tararagi]

Thank you for your reply. I understand parametrized length of "for loop" is not possible.

Meanwhile, I removed the "break" controls from the code as below. because transpile of "branch pruning" could be hard task for FHE. But after about 3 hours compiling, I got the following error message. I can not see what is going on.

root@2ea39926f6ce:/usr/src/fhe# bazel build -c opt //transpiler/examples/test6:test6_tfhe.transpiled_files INFO: Analyzed target //transpiler/examples/test6:test6_tfhe.transpiled_files (0 packages loaded, 0 targets configured). INFO: Found 1 target... INFO: From Action transpiler/examples/test6/test6_tfhe.ir: Parsing file 'transpiler/examples/test6/test6.cc' with clang... Generating IR... ERROR: /usr/src/fhe/transpiler/examples/test6/BUILD:5:15: Action transpiler/examples/test6/test6_tfhe.opt.bool.opt.ir failed: (Killed): bash failed: error executing command /bin/bash -c ... (remaining 1 argument(s) skipped)

Use --sandbox_debug to see verbose messages from the sandbox bash failed: error executing command /bin/bash -c ... (remaining 1 argument(s) skipped)

Use --sandbox_debug to see verbose messages from the sandbox /bin/bash: line 1: 18264 Killed bazel-out/k8-opt-exec-2B5CBBC6/bin/external/com_google_xls/xls/tools/opt_main bazel-out/k8-opt/bin/transpiler/examples/test6/test6_tfhe.opt.bool.ir --top $(cat bazel-out/k8-opt/bin/transpiler/examples/test6/test6_tfhe.entry) > bazel-out/k8-opt/bin/transpiler/examples/test6/test6_tfhe.opt.bool.opt.ir Target //transpiler/examples/test6:test6_tfhe.transpiled_files failed to build Use --verbose_failures to see the command lines of failed build steps. INFO: Elapsed time: 12475.081s, Critical Path: 12474.02s INFO: 8 processes: 2 internal, 6 processwrapper-sandbox. FAILED: Build did NOT complete successfully root@2ea39926f6ce:/usr/src/fhe#

-- code --

List Test6::process(List x, int L, int R) {

int i, j; int pv; int tmp; bool flag0, flag;

i = L; j = R;

pv = x.list[(L + R)/2];

flag0 = true;

pragma hls_unroll yes

for(int k=0; k<4; k++){ // len(x.list) = 4

  flag = true;
  #pragma hls_unroll yes
  for(int ki=0; ki<4; ki++){ 
    if(x.list[i] < pv)
      flag = false;

    if(flag)
        i++;
  }

  flag = true;
  #pragma hls_unroll yes
  for(int kj=0; kj<4; kj++){
    if(pv < x.list[j])
      flag = true;

    if(flag)
        j--;
  }

  if(i>=j)
      flag0 = false;

  if(flag0){
      tmp = x.list[i];
      x.list[i] = x.list[j];
      x.list[j] = tmp;

      i++;
      j--;
  }

}

/* if(L < i-1) process(x, L, i-1);

if(j+1 < R) process(x, j+1, R); */

return x; }

-- end of code ---

[j2kun]

After talking with the XLS team they agreed the solver was struggling to prove the loops unroll, but what I learned is that it wasn't that it's hard to prove they unroll, but that it's hard for the solver to find the minimal unrolling, which is what it does. The nested breaks inside of if statements apparently make this difficult.

As a workaround, they added this [new parameter to xlscc] (https://github.com/google/xls/commit/500af15385eb18414d85a3ff1e9c3d19dd289d89) that allows one to set an effective time limit on the loop unrolling solver, and a quick test shows that it causes the compilation to succeed.

I have to integrate this flag into the project so that it is passed to xlscc by default and configurable by the user, which should be done this week.

[tararagi]

Thank you for your message and management. I will wait for that integration.

[j2kun]

The fix is in review. However, I did notice that, even though it compiles, with the recursive calls included the resulting circuit has some 600,000 gates. I would expect such a program to take maybe 24h to run, which may be an issue for you.

[tararagi]

Thank you for the notification. The huge circuit is no problem but important information. I want to know how coding structures effect on the efficiency of FHE computations.

[j2kun]

The fix is taking a bit longer than expected, because upgrading the version of XLS to get this new parameter resulted in some unrelated build errors that required some project reconfiguration. A patch is in the works and I hope it will be through today or tomorrow.

[j2kun]

This commit should fix the issue https://github.com/google/fully-homomorphic-encryption/commit/c3df97c1053fb14961a0761531445f38aaa7cead

[tararagi]

Thank you very much for your work of the fixing. I will try it.