[Project] Question Regarding on Backend Vector Register Allocation

[KyungWonCho]

Matmul3 Benchmark를 제 optimization pass를 적용시켰을때 다음과 같이 변환됩니다.

for.body3:                                        ; preds = %for.cond1
  %add204 = add i32 %mul, %j.0
  %idxprom206 = zext i32 %add204 to i64
  %arrayidx207 = getelementptr inbounds i64, ptr %c, i64 %idxprom206
  %add260 = add i32 %mul28, %j.0
  %idxprom262 = zext i32 %add260 to i64
  %arrayidx263 = getelementptr inbounds i64, ptr %c, i64 %idxprom262
  %add316 = add i32 %mul52, %j.0
  %idxprom318 = zext i32 %add316 to i64
  %arrayidx319 = getelementptr inbounds i64, ptr %c, i64 %idxprom318
  %add372 = add i32 %mul76, %j.0
  %idxprom374 = zext i32 %add372 to i64
  %arrayidx375 = getelementptr inbounds i64, ptr %c, i64 %idxprom374
  %2 = load <4 x i64>, ptr %arrayidx207, align 8
  %3 = extractelement <4 x i64> %2, i64 0
  %4 = extractelement <4 x i64> %2, i64 1
  %5 = extractelement <4 x i64> %2, i64 2
  %6 = extractelement <4 x i64> %2, i64 3
  %7 = load <4 x i64>, ptr %arrayidx263, align 8
  %8 = extractelement <4 x i64> %7, i64 0
  %9 = extractelement <4 x i64> %7, i64 1
  %10 = extractelement <4 x i64> %7, i64 2
  %11 = extractelement <4 x i64> %7, i64 3
  %12 = load <4 x i64>, ptr %arrayidx319, align 8
  %13 = extractelement <4 x i64> %12, i64 0
  %14 = extractelement <4 x i64> %12, i64 1
  %15 = extractelement <4 x i64> %12, i64 2
  %16 = extractelement <4 x i64> %12, i64 3
  %17 = load <4 x i64>, ptr %arrayidx375, align 8
  %18 = extractelement <4 x i64> %17, i64 0
  %19 = extractelement <4 x i64> %17, i64 1
  %20 = extractelement <4 x i64> %17, i64 2
  %21 = extractelement <4 x i64> %17, i64 3
  br label %for.cond4

이걸 Register Allocation이 끝난 후 IR을 보면

for.body3:                                        ; preds = %for.cond1
  %26 = inttoptr i64 %0 to ptr
  %27 = load i64, ptr %26, align 8
  %28 = trunc i64 %27 to i32
  %add204 = add i32 %28, %j.0
  %idxprom206 = zext i32 %add204 to i64
  %29 = ptrtoint ptr %c to i64
  %30 = bitcast i64 %idxprom206 to i64
  %31 = mul i64 %30, %6
  %32 = add i64 %29, %31                    ; %32 = %c + (%i.0 * %dim + %j.0) * 8
  %33 = call i64 @const_i64(i64 928)
  %34 = add i64 %0, %33                     ; sp + 928
  %35 = inttoptr i64 %34 to ptr
  store i64 %32, ptr %35, align 8           ; %32 저장(sp + 928)
  %36 = inttoptr i64 %32 to ptr
  %37 = call i64 @const_i64(i64 904)
  %38 = add i64 %0, %37
  %39 = inttoptr i64 %38 to ptr
  %40 = load i64, ptr %39, align 8
  %41 = trunc i64 %40 to i32
  %add260 = add i32 %41, %j.0
  %idxprom262 = zext i32 %add260 to i64
  %42 = ptrtoint ptr %c to i64
  %43 = bitcast i64 %idxprom262 to i64
  %44 = mul i64 %43, %6
  %45 = add i64 %42, %44
  %46 = call i64 @const_i64(i64 936)
  %47 = add i64 %0, %46
  %48 = inttoptr i64 %47 to ptr
  store i64 %45, ptr %48, align 8
  %49 = inttoptr i64 %45 to ptr
  %50 = call i64 @const_i64(i64 912)
  %51 = add i64 %0, %50
  %52 = inttoptr i64 %51 to ptr
  %53 = load i64, ptr %52, align 8
  %54 = trunc i64 %53 to i32
  %add316 = add i32 %54, %j.0
  %idxprom318 = zext i32 %add316 to i64
  %55 = ptrtoint ptr %c to i64
  %56 = bitcast i64 %idxprom318 to i64
  %57 = mul i64 %56, %6
  %58 = add i64 %55, %57
  %59 = call i64 @const_i64(i64 944)
  %60 = add i64 %0, %59
  %61 = inttoptr i64 %60 to ptr
  store i64 %58, ptr %61, align 8
  %62 = inttoptr i64 %58 to ptr
  %63 = call i64 @const_i64(i64 920)
  %64 = add i64 %0, %63
  %65 = inttoptr i64 %64 to ptr
  %66 = load i64, ptr %65, align 8
  %67 = trunc i64 %66 to i32
  %add372 = add i32 %67, %j.0
  %idxprom374 = zext i32 %add372 to i64
  %68 = ptrtoint ptr %c to i64
  %69 = bitcast i64 %idxprom374 to i64
  %70 = mul i64 %69, %6
  %71 = add i64 %68, %70
  %72 = call i64 @const_i64(i64 952)
  %73 = add i64 %0, %72
  %74 = inttoptr i64 %73 to ptr
  store i64 %71, ptr %74, align 8
  %75 = inttoptr i64 %71 to ptr
  %76 = call i64 @const_i64(i64 928)
  %77 = add i64 %0, %76                         ; sp + 928 
  %78 = inttoptr i64 %77 to ptr
  %79 = load i64, ptr %78, align 8              ; %79 = %32 = %c + (%i.0 * %dim + %j.0) * 8
  %80 = inttoptr i64 %79 to ptr
  %81 = load <4 x i64>, ptr %80, align 8        ; %81 = load <4 x i64>, ptr %arrayidx207, align 8
  %82 = call i64 @const_i64(i64 8)
  %83 = add i64 %0, %82                         ; sp + 8
  %84 = inttoptr i64 %83 to ptr
  store <4 x i64> %81, ptr %84, align 32        ; sp + 8에 %81 저장
  %85 = call i64 @const_i64(i64 8)
  %86 = add i64 %0, %85                         ; sp + 8
  %87 = inttoptr i64 %86 to ptr
  %88 = load <4 x i64>, ptr %87, align 32       ; %88 = %81(sp + 8)
  %89 = extractelement <4 x i64> %88, i64 %1    ; %89 = %88(%81)의 0번째 
  %90 = call i64 @const_i64(i64 960)
  %91 = add i64 %0, %90                     
  %92 = inttoptr i64 %91 to ptr
  store i64 %89, ptr %92, align 8
  %93 = call i64 @const_i64(i64 8)
  %94 = add i64 %0, %93                         ; sp + 8
  %95 = inttoptr i64 %94 to ptr
  %96 = load <4 x i64>, ptr %95, align 32       ; %96 = %81(sp + 8)
  %97 = extractelement <4 x i64> %96, i64 %3    ; %97 = %96(%81)의 1번째
  %98 = call i64 @const_i64(i64 976)
  %99 = add i64 %0, %98
  %100 = inttoptr i64 %99 to ptr
  store i64 %97, ptr %100, align 8
  %101 = call i64 @const_i64(i64 8)
  %102 = add i64 %0, %101                       ; sp + 8
  %103 = inttoptr i64 %102 to ptr
  %104 = load <4 x i64>, ptr %103, align 32     ; %104 = %81(sp + 8)
  %105 = extractelement <4 x i64> %104, i64 %7  ; %105 = %104(%81)의 2번째
  %106 = call i64 @const_i64(i64 992)
  %107 = add i64 %0, %106
  %108 = inttoptr i64 %107 to ptr
  store i64 %105, ptr %108, align 8
  %109 = call i64 @const_i64(i64 8)
  %110 = add i64 %0, %109                       ; sp + 8
  %111 = inttoptr i64 %110 to ptr
  %112 = load <4 x i64>, ptr %111, align 32     ; %112 = %81(sp + 8)
  %113 = extractelement <4 x i64> %112, i64 %8  ; %113 = %112(%81)의 3번째
  %114 = call i64 @const_i64(i64 1008)
  %115 = add i64 %0, %114
  %116 = inttoptr i64 %115 to ptr
  store i64 %113, ptr %116, align 8
  %117 = call i64 @const_i64(i64 936)
  %118 = add i64 %0, %117
  %119 = inttoptr i64 %118 to ptr
  %120 = load i64, ptr %119, align 8
  %121 = inttoptr i64 %120 to ptr
  %122 = load <4 x i64>, ptr %121, align 8
  %123 = call i64 @const_i64(i64 8)
  %124 = add i64 %0, %123
  %125 = inttoptr i64 %124 to ptr
  store <4 x i64> %122, ptr %125, align 32
  %126 = call i64 @const_i64(i64 8)
  %127 = add i64 %0, %126
  %128 = inttoptr i64 %127 to ptr
  %129 = load <4 x i64>, ptr %128, align 32
  %130 = extractelement <4 x i64> %129, i64 %1
  %131 = call i64 @const_i64(i64 1024)
  %132 = add i64 %0, %131
  %133 = inttoptr i64 %132 to ptr
  store i64 %130, ptr %133, align 8
  %134 = call i64 @const_i64(i64 8)
  %135 = add i64 %0, %134
  %136 = inttoptr i64 %135 to ptr
  %137 = load <4 x i64>, ptr %136, align 32
  %138 = extractelement <4 x i64> %137, i64 %3
  %139 = call i64 @const_i64(i64 1040)
  %140 = add i64 %0, %139
  %141 = inttoptr i64 %140 to ptr
  store i64 %138, ptr %141, align 8
  %142 = call i64 @const_i64(i64 8)
  %143 = add i64 %0, %142
  %144 = inttoptr i64 %143 to ptr
  %145 = load <4 x i64>, ptr %144, align 32
  %146 = extractelement <4 x i64> %145, i64 %7
  %147 = call i64 @const_i64(i64 1056)
  %148 = add i64 %0, %147
  %149 = inttoptr i64 %148 to ptr
  store i64 %146, ptr %149, align 8
  %150 = call i64 @const_i64(i64 8)
  %151 = add i64 %0, %150
  %152 = inttoptr i64 %151 to ptr
  %153 = load <4 x i64>, ptr %152, align 32
  %154 = extractelement <4 x i64> %153, i64 %8
  %155 = call i64 @const_i64(i64 1072)
  %156 = add i64 %0, %155
  %157 = inttoptr i64 %156 to ptr
  store i64 %154, ptr %157, align 8
  %158 = call i64 @const_i64(i64 944)
  %159 = add i64 %0, %158
  %160 = inttoptr i64 %159 to ptr
  %161 = load i64, ptr %160, align 8
  %162 = inttoptr i64 %161 to ptr
  %163 = load <4 x i64>, ptr %162, align 8
  %164 = call i64 @const_i64(i64 8)
  %165 = add i64 %0, %164
  %166 = inttoptr i64 %165 to ptr
  store <4 x i64> %163, ptr %166, align 32
  %167 = call i64 @const_i64(i64 8)
  %168 = add i64 %0, %167
  %169 = inttoptr i64 %168 to ptr
  %170 = load <4 x i64>, ptr %169, align 32
  %171 = extractelement <4 x i64> %170, i64 %1
  %172 = call i64 @const_i64(i64 1088)
  %173 = add i64 %0, %172
  %174 = inttoptr i64 %173 to ptr
  store i64 %171, ptr %174, align 8
  %175 = call i64 @const_i64(i64 8)
  %176 = add i64 %0, %175
  %177 = inttoptr i64 %176 to ptr
  %178 = load <4 x i64>, ptr %177, align 32
  %179 = extractelement <4 x i64> %178, i64 %3
  %180 = call i64 @const_i64(i64 1104)
  %181 = add i64 %0, %180
  %182 = inttoptr i64 %181 to ptr
  store i64 %179, ptr %182, align 8
  %183 = call i64 @const_i64(i64 8)
  %184 = add i64 %0, %183
  %185 = inttoptr i64 %184 to ptr
  %186 = load <4 x i64>, ptr %185, align 32
  %187 = extractelement <4 x i64> %186, i64 %7
  %188 = call i64 @const_i64(i64 1120)
  %189 = add i64 %0, %188
  %190 = inttoptr i64 %189 to ptr
  store i64 %187, ptr %190, align 8
  %191 = call i64 @const_i64(i64 8)
  %192 = add i64 %0, %191
  %193 = inttoptr i64 %192 to ptr
  %194 = load <4 x i64>, ptr %193, align 32
  %195 = extractelement <4 x i64> %194, i64 %8
  %196 = call i64 @const_i64(i64 1136)
  %197 = add i64 %0, %196
  %198 = inttoptr i64 %197 to ptr
  store i64 %195, ptr %198, align 8
  %199 = call i64 @const_i64(i64 952)
  %200 = add i64 %0, %199
  %201 = inttoptr i64 %200 to ptr
  %202 = load i64, ptr %201, align 8
  %203 = inttoptr i64 %202 to ptr
  %204 = load <4 x i64>, ptr %203, align 8
  %205 = call i64 @const_i64(i64 8)
  %206 = add i64 %0, %205
  %207 = inttoptr i64 %206 to ptr
  store <4 x i64> %204, ptr %207, align 32
  %208 = call i64 @const_i64(i64 8)
  %209 = add i64 %0, %208
  %210 = inttoptr i64 %209 to ptr
  %211 = load <4 x i64>, ptr %210, align 32
  %212 = extractelement <4 x i64> %211, i64 %1
  %213 = call i64 @const_i64(i64 1152)
  %214 = add i64 %0, %213
  %215 = inttoptr i64 %214 to ptr
  store i64 %212, ptr %215, align 8
  %216 = call i64 @const_i64(i64 8)
  %217 = add i64 %0, %216
  %218 = inttoptr i64 %217 to ptr
  %219 = load <4 x i64>, ptr %218, align 32
  %220 = extractelement <4 x i64> %219, i64 %3
  %221 = call i64 @const_i64(i64 1168)
  %222 = add i64 %0, %221
  %223 = inttoptr i64 %222 to ptr
  store i64 %220, ptr %223, align 8
  %224 = call i64 @const_i64(i64 8)
  %225 = add i64 %0, %224
  %226 = inttoptr i64 %225 to ptr
  %227 = load <4 x i64>, ptr %226, align 32
  %228 = extractelement <4 x i64> %227, i64 %7
  %229 = call i64 @const_i64(i64 1184)
  %230 = add i64 %0, %229
  %231 = inttoptr i64 %230 to ptr
  store i64 %228, ptr %231, align 8
  %232 = call i64 @const_i64(i64 8)
  %233 = add i64 %0, %232
  %234 = inttoptr i64 %233 to ptr
  %235 = load <4 x i64>, ptr %234, align 32
  %236 = extractelement <4 x i64> %235, i64 %8
  %237 = call i64 @const_i64(i64 1200)
  %238 = add i64 %0, %237
  %239 = inttoptr i64 %238 to ptr
  store i64 %236, ptr %239, align 8
  %240 = mul i32 %2, %4
  br label %for.cond4

중간에 scalar register의 경우에 usage가 커서 stack에 저장되는것이 맞지만, vector load를 하고 하나씩 extract를 할때 한번에 하나씩 vector load를 하는 것 같아 cost가 비정상적으로 많이 증가되는데 이것이 의도된 변환인지 아닌지가 궁금합니다.

[strikef]

optimization 과정까지 끝나고 backend로 넘어가기 직전의 전체 IR을 올려주시거나 메일로 보내주실 수 있을까요?

[KyungWonCho]

메일로 보냈습니다!

[strikef]

백엔드 버그가 맞으며, register allocation 과정에서 버그로 과도한 register pressure가 발생하는 것 같습니다. 수정 예정입니다.

[strikef]

Register pressure가 과도한 상황에서 allocation 과정이 상당히 비효율적으로 일어나는 문제가 추가로 발견되어 현재 수정 대책을 찾는 중입니다.