Changes between Version 6 and Version 7 of SIMDVectorExampleInLLVM

Timestamp:

10/25/11 12:55:04 (19 months ago)

Author:

pmonday

Comment:

--

SIMDVectorExampleInLLVM

@@ -198 +198 @@
 }}}
 
+Let's take a look at a program with a substantially larger array of floats to add.  Again, optimizing this would yield very little code and, certainly, lazy evaluation would turn this program into basically a no-op.  Nonetheless, this should speed up by almost a factor of 4 when vectorized.  Here is the C code that helps guide the imperative implementation:
+{{{
+#include <stdio.h>
+
+int main()
+{
+   int sz = 40000;
+   float x[sz], y[sz], z[sz];
+   int i;
+   for (i = 0; i < sz; i++) {
+      x[i] = i;
+      y[i] = i + sz;
+   }
+
+   for (i = 0; i < sz; i += 4) {
+     z[i] = x[i] + y[i];
+     z[i+1] = x[i+1] + y[i+1];
+     z[i+2] = x[i+2] + y[i+2];
+     z[i+3] = x[i+3] + y[i+3];
+   }
+
+   printf("%f %f %f %f\n", z[0], z[1], z[2], z[3]);
+}
+}}}
+
+The resulting non-optimized LLVM code is as follows:
+{{{
+; ModuleID = '/tmp/webcompile/_718_0.bc'
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+@.str = private unnamed_addr constant [13 x i8] c"%f %f %f %f\0A\00"
+
+define i32 @main() nounwind {
+  %1 = alloca i32, align 4
+  %sz = alloca i32, align 4
+  %2 = alloca i8*
+  %i = alloca i32, align 4
+  store i32 0, i32* %1
+  store i32 40000, i32* %sz, align 4
+  %3 = call i8* @llvm.stacksave()
+  store i8* %3, i8** %2
+  %4 = load i32* %sz, align 4
+  %5 = zext i32 %4 to i64
+  %6 = mul i64 4, %5
+  %7 = alloca i8, i64 %6, align 16
+  %8 = bitcast i8* %7 to float*
+  %9 = load i32* %sz, align 4
+  %10 = zext i32 %9 to i64
+  %11 = mul i64 4, %10
+  %12 = alloca i8, i64 %11, align 16
+  %13 = bitcast i8* %12 to float*
+  %14 = load i32* %sz, align 4
+  %15 = zext i32 %14 to i64
+  %16 = mul i64 4, %15
+  %17 = alloca i8, i64 %16, align 16
+  %18 = bitcast i8* %17 to float*
+  store i32 0, i32* %i, align 4
+  br label %19
+
+; <label>:19                                      ; preds = %36, %0
+  %20 = load i32* %i, align 4
+  %21 = load i32* %sz, align 4
+  %22 = icmp slt i32 %20, %21
+  br i1 %22, label %23, label %39
+
+; <label>:23                                      ; preds = %19
+  %24 = load i32* %i, align 4
+  %25 = sitofp i32 %24 to float
+  %26 = load i32* %i, align 4
+  %27 = sext i32 %26 to i64
+  %28 = getelementptr inbounds float* %8, i64 %27
+  store float %25, float* %28
+  %29 = load i32* %i, align 4
+  %30 = load i32* %sz, align 4
+  %31 = add nsw i32 %29, %30
+  %32 = sitofp i32 %31 to float
+  %33 = load i32* %i, align 4
+  %34 = sext i32 %33 to i64
+  %35 = getelementptr inbounds float* %13, i64 %34
+  store float %32, float* %35
+  br label %36
+
+; <label>:36                                      ; preds = %23
+  %37 = load i32* %i, align 4
+  %38 = add nsw i32 %37, 1
+  store i32 %38, i32* %i, align 4
+  br label %19
+
+; <label>:39                                      ; preds = %19
+  store i32 0, i32* %i, align 4
+  br label %40
+
+; <label>:40                                      ; preds = %102, %39
+  %41 = load i32* %i, align 4
+  %42 = load i32* %sz, align 4
+  %43 = icmp slt i32 %41, %42
+  br i1 %43, label %44, label %105
+
+; <label>:44                                      ; preds = %40
+  %45 = load i32* %i, align 4
+  %46 = sext i32 %45 to i64
+  %47 = getelementptr inbounds float* %8, i64 %46
+  %48 = load float* %47
+  %49 = load i32* %i, align 4
+  %50 = sext i32 %49 to i64
+  %51 = getelementptr inbounds float* %13, i64 %50
+  %52 = load float* %51
+  %53 = fadd float %48, %52
+  %54 = load i32* %i, align 4
+  %55 = sext i32 %54 to i64
+  %56 = getelementptr inbounds float* %18, i64 %55
+  store float %53, float* %56
+  %57 = load i32* %i, align 4
+  %58 = add nsw i32 %57, 1
+  %59 = sext i32 %58 to i64
+  %60 = getelementptr inbounds float* %8, i64 %59
+  %61 = load float* %60
+  %62 = load i32* %i, align 4
+  %63 = add nsw i32 %62, 1
+  %64 = sext i32 %63 to i64
+  %65 = getelementptr inbounds float* %13, i64 %64
+  %66 = load float* %65
+  %67 = fadd float %61, %66
+  %68 = load i32* %i, align 4
+  %69 = add nsw i32 %68, 1
+  %70 = sext i32 %69 to i64
+  %71 = getelementptr inbounds float* %18, i64 %70
+  store float %67, float* %71
+  %72 = load i32* %i, align 4
+  %73 = add nsw i32 %72, 2
+  %74 = sext i32 %73 to i64
+  %75 = getelementptr inbounds float* %8, i64 %74
+  %76 = load float* %75
+  %77 = load i32* %i, align 4
+  %78 = add nsw i32 %77, 2
+  %79 = sext i32 %78 to i64
+  %80 = getelementptr inbounds float* %13, i64 %79
+  %81 = load float* %80
+  %82 = fadd float %76, %81
+  %83 = load i32* %i, align 4
+  %84 = add nsw i32 %83, 2
+  %85 = sext i32 %84 to i64
+  %86 = getelementptr inbounds float* %18, i64 %85
+  store float %82, float* %86
+  %87 = load i32* %i, align 4
+  %88 = add nsw i32 %87, 3
+  %89 = sext i32 %88 to i64
+  %90 = getelementptr inbounds float* %8, i64 %89
+  %91 = load float* %90
+  %92 = load i32* %i, align 4
+  %93 = add nsw i32 %92, 3
+  %94 = sext i32 %93 to i64
+  %95 = getelementptr inbounds float* %13, i64 %94
+  %96 = load float* %95
+  %97 = fadd float %91, %96
+  %98 = load i32* %i, align 4
+  %99 = add nsw i32 %98, 3
+  %100 = sext i32 %99 to i64
+  %101 = getelementptr inbounds float* %18, i64 %100
+  store float %97, float* %101
+  br label %102
+
+; <label>:102                                     ; preds = %44
+  %103 = load i32* %i, align 4
+  %104 = add nsw i32 %103, 4
+  store i32 %104, i32* %i, align 4
+  br label %40
+
+; <label>:105                                     ; preds = %40
+  %106 = getelementptr inbounds float* %18, i64 0
+  %107 = load float* %106
+  %108 = fpext float %107 to double
+  %109 = getelementptr inbounds float* %18, i64 1
+  %110 = load float* %109
+  %111 = fpext float %110 to double
+  %112 = getelementptr inbounds float* %18, i64 2
+  %113 = load float* %112
+  %114 = fpext float %113 to double
+  %115 = getelementptr inbounds float* %18, i64 3
+  %116 = load float* %115
+  %117 = fpext float %116 to double
+  %118 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([13 x i8]* @.str, i32 0, i32 0), double %108, double %111, double %114, double %117)
+  %119 = load i8** %2
+  call void @llvm.stackrestore(i8* %119)
+  %120 = load i32* %1
+  ret i32 %120
+}
+
+declare i8* @llvm.stacksave() nounwind
+
+declare i32 @printf(i8*, ...)
+
+declare void @llvm.stackrestore(i8*) nounwind
+}}}
+
+Instead of hand-optimizing the entire sequence, the exercise will merely convert the types to vectors and then alter the loop starting with "label 44" to use vector addition rather then the sequence of adds that is currently being used.  The resulting program is as follows:
+
+{{{
+
+}}}
+
+Timing the execution of the bytecodes yields:
+
+