(*
 * Copyright (c) 2001 Stefan Kral
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *)


(* In this module some instructions are moved to improve a schedule
 * generated by the scheduler. *)

open List
open Util
open VSimdBasics


(* operates on list that is in-order *)
let move_vinstr_down' stop i = 
  let i_regs = vsimdinstrToWrites i @ vsimdinstrToReads i in
  let rec move_vinstr_down' = function
    | [] -> [i]
    | x::xs as xxs ->
        let x_srcs = vsimdinstrToSrcregs x in
	  if stop x || exists (fun x -> mem x i_regs) x_srcs then
	    i::xxs
	  else
	    x::(move_vinstr_down' xs) in
  move_vinstr_down' 

let move_vinstr_down = move_vinstr_down' (fun _ -> false)


(* operates on list in reversed order *)
let move_vinstr_up' stop i = 
  let i_srcs = vsimdinstrToSrcregs i in
  let rec move_vinstr_up' = function
    | [] -> [i]
    | x::xs as xxs ->
	let x_regs = vsimdinstrToWrites x @ vsimdinstrToReads x in
          if stop x || exists (fun x -> mem x i_srcs) x_regs then
	    i::xxs
	  else
	    x::(move_vinstr_up' xs) in
  move_vinstr_up'

let move_vinstr_up = move_vinstr_up' (fun _ -> false)


(* pass 1: move loads down *)
let rec move_loads_down = function
  | []	  -> []
  | x::xs -> 
      let xs' = move_loads_down xs in
        if vsimdinstrIsLoad x then 
	  move_vinstr_down' vsimdinstrIsStore x xs' 
	else 
	  x::xs'

(* pass 2: move stores up *)
let move_stores_up =
  let rec move_stores_up' bag = function
    | [] -> rev bag
    | x::xs -> 
	let bag' = 
	  if vsimdinstrIsStore x then 
	    move_vinstr_up' vsimdinstrIsLoad x bag 
	  else 
	    x::bag 
	  in
	    move_stores_up' bag' xs in
  move_stores_up' []


(* pass 3: move unaryops up *)
let vsimdunaryopWantsUp = function
  | V_Id -> failwith "vsimdunaryopWantsUp: encountered v-copy instr!"
  | V_Swap -> false
  | V_Chs _ -> true
  | V_MulConst _ -> true

let move_unaryops_up =
  let rec move_unaryops_up' bag = function
    | [] -> rev bag
    | (V_SimdUnaryOp(op,s,_) as x)::xs 
      when vsimdunaryopWantsUp op &&
	   not (exists (fun i -> mem s (vsimdinstrToSrcregs i)) xs) -> 
	move_unaryops_up' (move_vinstr_up x bag) xs
    | x::xs ->
	move_unaryops_up' (x::bag) xs in
  move_unaryops_up' []


(* pass 4: move unaryops down *)
let vsimdunaryopWantsDown = function
  | V_Id -> failwith "vsimdunaryopWantsDown: encountered v-copy instr!"
  | V_Swap -> true
  | V_Chs _ -> true
  | V_MulConst _ -> false

let rec move_unaryops_down = function
  | []	  -> []
  | (V_SimdUnaryOp(op,s,_) as x)::xs when vsimdunaryopWantsDown op  ->
      move_vinstr_down x (move_unaryops_down xs)
  | x::xs -> 
      x::(move_unaryops_down xs)


(* pass 5: move binops up *)
let move_binops_up =
  let rec move_binops_up' bag = function
    | [] -> rev bag
    | (V_SimdBinOp(op,s1,s2,_) as x)::xs 
      when not (exists (fun i -> mem s1 (vsimdinstrToSrcregs i)) xs) &&
	   not (exists (fun i -> mem s2 (vsimdinstrToSrcregs i)) xs) ->
	move_binops_up' (move_vinstr_up x bag) xs
    | x::xs ->
	move_binops_up' (x::bag) xs in
  move_binops_up' []

(****************************************************************************)

let vsimdinstrToNormalized = function
  | V_SimdBinOp(V_Add, s1,s2,d) when s1>s2 -> V_SimdBinOp(V_Add, s2,s1,d)
  | V_SimdBinOp(V_Sub, s1,s2,d) when s1>s2 -> V_SimdBinOp(V_SubR,s2,s1,d)
  | V_SimdBinOp(V_SubR,s1,s2,d) when s1>s2 -> V_SimdBinOp(V_Sub, s2,s1,d)
  | x -> x

(****************************************************************************)

let improve_schedule xs0 =
  let xs1 = move_unaryops_down xs0 in
  let xs2 = move_binops_up xs1 in
  let xs3 = move_unaryops_up xs2 in
  let xs4 = move_binops_up xs3 in
  let xs5 = move_stores_up xs4 in
  let xs6 = move_loads_down xs5 in
  let xs7 = move_binops_up xs6 in
    map vsimdinstrToNormalized xs7