Loop interchange rough analysis

loop_ichg.rb

def show_iv(iv)
   "(%s)"%(iv.collect{|x|x.to_s}.join(","))
end

def sub_iv(iv0, iv1)
   iv0.zip(iv1).collect{|x0,x1| x0 - x1}
end

def add_dependence(iv, ds, us, du_lst)
   us.each do |u|
      du_lst.reverse.each do |iv_, ds_, us_|
         unless ds_.index(u).nil? then
            dv = sub_iv(iv, iv_)
            printf "  Flow: %s, %s -> %s, d:%s\n", u, show_iv(iv_), show_iv(iv), show_iv(dv)
            break
         end
      end
   end

   ds.each do |d|
      du_lst.reverse.each do |iv_, ds_, us_|
         unless us_.index(d).nil? then
            dv = sub_iv(iv, iv_)
            printf "  Anti: %s, %s -> %s, d:%s\n", d, show_iv(iv_), show_iv(iv), show_iv(dv)
            break
         end
      end
   end

   du_lst.push [iv, ds, us]
end

N = 4

du_lst = []

(2..N).each do |i|
   (2..N).each do |j|
      (2..(N-1)).each do |k|
         iv = [i-2,j-2,k-2]
         str0 = "A[#{i},#{j},#{k}]"
         str1 = "A[#{i-1},#{j-1},#{k-1}]"
         str2 = "A[#{i-1},#{j-1},#{k+1}]"
         printf "%s: %s = (%s + %s)/2\n", show_iv(iv), str0, str1, str2
         add_dependence(iv, [str0], [str1,str2], du_lst)
      end
   end
end

printf "\n\n----\n\n"

du_lst = []

(2..N).each do |i|
   (2..(N-1)).each do |k|
      (2..N).each do |j|
         iv = [i-2,k-2,j-2]
         str0 = "A[#{i},#{j},#{k}]"
         str1 = "A[#{i-1},#{j-1},#{k-1}]"
         str2 = "A[#{i-1},#{j-1},#{k+1}]"
         printf "%s: %s = (%s + %s)/2\n", show_iv(iv), str0, str1, str2
         add_dependence(iv, [str0], [str1,str2], du_lst)
      end
   end
end

printf "\n\n----\n\n"

du_lst = []

(2..(N-1)).each do |k|
   (2..N).each do |i|
      (2..N).each do |j|
         iv = [k-2,i-2,j-2]
         str0 = "A[#{i},#{j},#{k}]"
         str1 = "A[#{i-1},#{j-1},#{k-1}]"
         str2 = "A[#{i-1},#{j-1},#{k+1}]"
         printf "%s: %s = (%s + %s)/2\n", show_iv(iv), str0, str1, str2
         add_dependence(iv, [str0], [str1,str2], du_lst)
      end
   end
end

result.txt

(0,0,0): A[2,2,2] = (A[1,1,1] + A[1,1,3])/2
(0,0,1): A[2,2,3] = (A[1,1,2] + A[1,1,4])/2
(0,1,0): A[2,3,2] = (A[1,2,1] + A[1,2,3])/2
(0,1,1): A[2,3,3] = (A[1,2,2] + A[1,2,4])/2
(0,2,0): A[2,4,2] = (A[1,3,1] + A[1,3,3])/2
(0,2,1): A[2,4,3] = (A[1,3,2] + A[1,3,4])/2
(1,0,0): A[3,2,2] = (A[2,1,1] + A[2,1,3])/2
(1,0,1): A[3,2,3] = (A[2,1,2] + A[2,1,4])/2
(1,1,0): A[3,3,2] = (A[2,2,1] + A[2,2,3])/2
  Flow: A[2,2,3], (0,0,1) -> (1,1,0), d:(1,1,-1)
(1,1,1): A[3,3,3] = (A[2,2,2] + A[2,2,4])/2
  Flow: A[2,2,2], (0,0,0) -> (1,1,1), d:(1,1,1)
(1,2,0): A[3,4,2] = (A[2,3,1] + A[2,3,3])/2
  Flow: A[2,3,3], (0,1,1) -> (1,2,0), d:(1,1,-1)
(1,2,1): A[3,4,3] = (A[2,3,2] + A[2,3,4])/2
  Flow: A[2,3,2], (0,1,0) -> (1,2,1), d:(1,1,1)
(2,0,0): A[4,2,2] = (A[3,1,1] + A[3,1,3])/2
(2,0,1): A[4,2,3] = (A[3,1,2] + A[3,1,4])/2
(2,1,0): A[4,3,2] = (A[3,2,1] + A[3,2,3])/2
  Flow: A[3,2,3], (1,0,1) -> (2,1,0), d:(1,1,-1)
(2,1,1): A[4,3,3] = (A[3,2,2] + A[3,2,4])/2
  Flow: A[3,2,2], (1,0,0) -> (2,1,1), d:(1,1,1)
(2,2,0): A[4,4,2] = (A[3,3,1] + A[3,3,3])/2
  Flow: A[3,3,3], (1,1,1) -> (2,2,0), d:(1,1,-1)
(2,2,1): A[4,4,3] = (A[3,3,2] + A[3,3,4])/2
  Flow: A[3,3,2], (1,1,0) -> (2,2,1), d:(1,1,1)


----

(0,0,0): A[2,2,2] = (A[1,1,1] + A[1,1,3])/2
(0,0,1): A[2,3,2] = (A[1,2,1] + A[1,2,3])/2
(0,0,2): A[2,4,2] = (A[1,3,1] + A[1,3,3])/2
(0,1,0): A[2,2,3] = (A[1,1,2] + A[1,1,4])/2
(0,1,1): A[2,3,3] = (A[1,2,2] + A[1,2,4])/2
(0,1,2): A[2,4,3] = (A[1,3,2] + A[1,3,4])/2
(1,0,0): A[3,2,2] = (A[2,1,1] + A[2,1,3])/2
(1,0,1): A[3,3,2] = (A[2,2,1] + A[2,2,3])/2
  Flow: A[2,2,3], (0,1,0) -> (1,0,1), d:(1,-1,1)
(1,0,2): A[3,4,2] = (A[2,3,1] + A[2,3,3])/2
  Flow: A[2,3,3], (0,1,1) -> (1,0,2), d:(1,-1,1)
(1,1,0): A[3,2,3] = (A[2,1,2] + A[2,1,4])/2
(1,1,1): A[3,3,3] = (A[2,2,2] + A[2,2,4])/2
  Flow: A[2,2,2], (0,0,0) -> (1,1,1), d:(1,1,1)
(1,1,2): A[3,4,3] = (A[2,3,2] + A[2,3,4])/2
  Flow: A[2,3,2], (0,0,1) -> (1,1,2), d:(1,1,1)
(2,0,0): A[4,2,2] = (A[3,1,1] + A[3,1,3])/2
(2,0,1): A[4,3,2] = (A[3,2,1] + A[3,2,3])/2
  Flow: A[3,2,3], (1,1,0) -> (2,0,1), d:(1,-1,1)
(2,0,2): A[4,4,2] = (A[3,3,1] + A[3,3,3])/2
  Flow: A[3,3,3], (1,1,1) -> (2,0,2), d:(1,-1,1)
(2,1,0): A[4,2,3] = (A[3,1,2] + A[3,1,4])/2
(2,1,1): A[4,3,3] = (A[3,2,2] + A[3,2,4])/2
  Flow: A[3,2,2], (1,0,0) -> (2,1,1), d:(1,1,1)
(2,1,2): A[4,4,3] = (A[3,3,2] + A[3,3,4])/2
  Flow: A[3,3,2], (1,0,1) -> (2,1,2), d:(1,1,1)


----

(0,0,0): A[2,2,2] = (A[1,1,1] + A[1,1,3])/2
(0,0,1): A[2,3,2] = (A[1,2,1] + A[1,2,3])/2
(0,0,2): A[2,4,2] = (A[1,3,1] + A[1,3,3])/2
(0,1,0): A[3,2,2] = (A[2,1,1] + A[2,1,3])/2
(0,1,1): A[3,3,2] = (A[2,2,1] + A[2,2,3])/2
(0,1,2): A[3,4,2] = (A[2,3,1] + A[2,3,3])/2
(0,2,0): A[4,2,2] = (A[3,1,1] + A[3,1,3])/2
(0,2,1): A[4,3,2] = (A[3,2,1] + A[3,2,3])/2
(0,2,2): A[4,4,2] = (A[3,3,1] + A[3,3,3])/2
(1,0,0): A[2,2,3] = (A[1,1,2] + A[1,1,4])/2
  Anti: A[2,2,3], (0,1,1) -> (1,0,0), d:(1,-1,-1)
(1,0,1): A[2,3,3] = (A[1,2,2] + A[1,2,4])/2
  Anti: A[2,3,3], (0,1,2) -> (1,0,1), d:(1,-1,-1)
(1,0,2): A[2,4,3] = (A[1,3,2] + A[1,3,4])/2
(1,1,0): A[3,2,3] = (A[2,1,2] + A[2,1,4])/2
  Anti: A[3,2,3], (0,2,1) -> (1,1,0), d:(1,-1,-1)
(1,1,1): A[3,3,3] = (A[2,2,2] + A[2,2,4])/2
  Flow: A[2,2,2], (0,0,0) -> (1,1,1), d:(1,1,1)
  Anti: A[3,3,3], (0,2,2) -> (1,1,1), d:(1,-1,-1)
(1,1,2): A[3,4,3] = (A[2,3,2] + A[2,3,4])/2
  Flow: A[2,3,2], (0,0,1) -> (1,1,2), d:(1,1,1)
(1,2,0): A[4,2,3] = (A[3,1,2] + A[3,1,4])/2
(1,2,1): A[4,3,3] = (A[3,2,2] + A[3,2,4])/2
  Flow: A[3,2,2], (0,1,0) -> (1,2,1), d:(1,1,1)
(1,2,2): A[4,4,3] = (A[3,3,2] + A[3,3,4])/2
  Flow: A[3,3,2], (0,1,1) -> (1,2,2), d:(1,1,1)