Changes between Version 6 and Version 7 of SIMDVectorExampleInLLVM


Ignore:
Timestamp:
Oct 25, 2011 7:55:04 PM (4 years ago)
Author:
pmonday
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • SIMDVectorExampleInLLVM

    v6 v7  
    198198}}}
    199199
     200Let'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:
     201{{{
     202#include <stdio.h>
     203
     204int main()
     205{
     206   int sz = 40000;
     207   float x[sz], y[sz], z[sz];
     208   int i;
     209   for (i = 0; i < sz; i++) {
     210      x[i] = i;
     211      y[i] = i + sz;
     212   }
     213
     214   for (i = 0; i < sz; i += 4) {
     215     z[i] = x[i] + y[i];
     216     z[i+1] = x[i+1] + y[i+1];
     217     z[i+2] = x[i+2] + y[i+2];
     218     z[i+3] = x[i+3] + y[i+3];
     219   }
     220
     221   printf("%f %f %f %f\n", z[0], z[1], z[2], z[3]);
     222}
     223}}}
     224
     225The resulting non-optimized LLVM code is as follows:
     226{{{
     227; ModuleID = '/tmp/webcompile/_718_0.bc'
     228target 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"
     229target triple = "x86_64-unknown-linux-gnu"
     230
     231@.str = private unnamed_addr constant [13 x i8] c"%f %f %f %f\0A\00"
     232
     233define i32 @main() nounwind {
     234  %1 = alloca i32, align 4
     235  %sz = alloca i32, align 4
     236  %2 = alloca i8*
     237  %i = alloca i32, align 4
     238  store i32 0, i32* %1
     239  store i32 40000, i32* %sz, align 4
     240  %3 = call i8* @llvm.stacksave()
     241  store i8* %3, i8** %2
     242  %4 = load i32* %sz, align 4
     243  %5 = zext i32 %4 to i64
     244  %6 = mul i64 4, %5
     245  %7 = alloca i8, i64 %6, align 16
     246  %8 = bitcast i8* %7 to float*
     247  %9 = load i32* %sz, align 4
     248  %10 = zext i32 %9 to i64
     249  %11 = mul i64 4, %10
     250  %12 = alloca i8, i64 %11, align 16
     251  %13 = bitcast i8* %12 to float*
     252  %14 = load i32* %sz, align 4
     253  %15 = zext i32 %14 to i64
     254  %16 = mul i64 4, %15
     255  %17 = alloca i8, i64 %16, align 16
     256  %18 = bitcast i8* %17 to float*
     257  store i32 0, i32* %i, align 4
     258  br label %19
     259
     260; <label>:19                                      ; preds = %36, %0
     261  %20 = load i32* %i, align 4
     262  %21 = load i32* %sz, align 4
     263  %22 = icmp slt i32 %20, %21
     264  br i1 %22, label %23, label %39
     265
     266; <label>:23                                      ; preds = %19
     267  %24 = load i32* %i, align 4
     268  %25 = sitofp i32 %24 to float
     269  %26 = load i32* %i, align 4
     270  %27 = sext i32 %26 to i64
     271  %28 = getelementptr inbounds float* %8, i64 %27
     272  store float %25, float* %28
     273  %29 = load i32* %i, align 4
     274  %30 = load i32* %sz, align 4
     275  %31 = add nsw i32 %29, %30
     276  %32 = sitofp i32 %31 to float
     277  %33 = load i32* %i, align 4
     278  %34 = sext i32 %33 to i64
     279  %35 = getelementptr inbounds float* %13, i64 %34
     280  store float %32, float* %35
     281  br label %36
     282
     283; <label>:36                                      ; preds = %23
     284  %37 = load i32* %i, align 4
     285  %38 = add nsw i32 %37, 1
     286  store i32 %38, i32* %i, align 4
     287  br label %19
     288
     289; <label>:39                                      ; preds = %19
     290  store i32 0, i32* %i, align 4
     291  br label %40
     292
     293; <label>:40                                      ; preds = %102, %39
     294  %41 = load i32* %i, align 4
     295  %42 = load i32* %sz, align 4
     296  %43 = icmp slt i32 %41, %42
     297  br i1 %43, label %44, label %105
     298
     299; <label>:44                                      ; preds = %40
     300  %45 = load i32* %i, align 4
     301  %46 = sext i32 %45 to i64
     302  %47 = getelementptr inbounds float* %8, i64 %46
     303  %48 = load float* %47
     304  %49 = load i32* %i, align 4
     305  %50 = sext i32 %49 to i64
     306  %51 = getelementptr inbounds float* %13, i64 %50
     307  %52 = load float* %51
     308  %53 = fadd float %48, %52
     309  %54 = load i32* %i, align 4
     310  %55 = sext i32 %54 to i64
     311  %56 = getelementptr inbounds float* %18, i64 %55
     312  store float %53, float* %56
     313  %57 = load i32* %i, align 4
     314  %58 = add nsw i32 %57, 1
     315  %59 = sext i32 %58 to i64
     316  %60 = getelementptr inbounds float* %8, i64 %59
     317  %61 = load float* %60
     318  %62 = load i32* %i, align 4
     319  %63 = add nsw i32 %62, 1
     320  %64 = sext i32 %63 to i64
     321  %65 = getelementptr inbounds float* %13, i64 %64
     322  %66 = load float* %65
     323  %67 = fadd float %61, %66
     324  %68 = load i32* %i, align 4
     325  %69 = add nsw i32 %68, 1
     326  %70 = sext i32 %69 to i64
     327  %71 = getelementptr inbounds float* %18, i64 %70
     328  store float %67, float* %71
     329  %72 = load i32* %i, align 4
     330  %73 = add nsw i32 %72, 2
     331  %74 = sext i32 %73 to i64
     332  %75 = getelementptr inbounds float* %8, i64 %74
     333  %76 = load float* %75
     334  %77 = load i32* %i, align 4
     335  %78 = add nsw i32 %77, 2
     336  %79 = sext i32 %78 to i64
     337  %80 = getelementptr inbounds float* %13, i64 %79
     338  %81 = load float* %80
     339  %82 = fadd float %76, %81
     340  %83 = load i32* %i, align 4
     341  %84 = add nsw i32 %83, 2
     342  %85 = sext i32 %84 to i64
     343  %86 = getelementptr inbounds float* %18, i64 %85
     344  store float %82, float* %86
     345  %87 = load i32* %i, align 4
     346  %88 = add nsw i32 %87, 3
     347  %89 = sext i32 %88 to i64
     348  %90 = getelementptr inbounds float* %8, i64 %89
     349  %91 = load float* %90
     350  %92 = load i32* %i, align 4
     351  %93 = add nsw i32 %92, 3
     352  %94 = sext i32 %93 to i64
     353  %95 = getelementptr inbounds float* %13, i64 %94
     354  %96 = load float* %95
     355  %97 = fadd float %91, %96
     356  %98 = load i32* %i, align 4
     357  %99 = add nsw i32 %98, 3
     358  %100 = sext i32 %99 to i64
     359  %101 = getelementptr inbounds float* %18, i64 %100
     360  store float %97, float* %101
     361  br label %102
     362
     363; <label>:102                                     ; preds = %44
     364  %103 = load i32* %i, align 4
     365  %104 = add nsw i32 %103, 4
     366  store i32 %104, i32* %i, align 4
     367  br label %40
     368
     369; <label>:105                                     ; preds = %40
     370  %106 = getelementptr inbounds float* %18, i64 0
     371  %107 = load float* %106
     372  %108 = fpext float %107 to double
     373  %109 = getelementptr inbounds float* %18, i64 1
     374  %110 = load float* %109
     375  %111 = fpext float %110 to double
     376  %112 = getelementptr inbounds float* %18, i64 2
     377  %113 = load float* %112
     378  %114 = fpext float %113 to double
     379  %115 = getelementptr inbounds float* %18, i64 3
     380  %116 = load float* %115
     381  %117 = fpext float %116 to double
     382  %118 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([13 x i8]* @.str, i32 0, i32 0), double %108, double %111, double %114, double %117)
     383  %119 = load i8** %2
     384  call void @llvm.stackrestore(i8* %119)
     385  %120 = load i32* %1
     386  ret i32 %120
     387}
     388
     389declare i8* @llvm.stacksave() nounwind
     390
     391declare i32 @printf(i8*, ...)
     392
     393declare void @llvm.stackrestore(i8*) nounwind
     394}}}
     395
     396Instead 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:
     397
     398{{{
     399
     400}}}
     401
     402Timing the execution of the bytecodes yields:
     403
     404