From dbc5521ef947c4b16cb1993e11a2517f5937e028 Mon Sep 17 00:00:00 2001 From: Tobias Grosser Date: Sat, 31 Dec 2016 07:46:11 +0000 Subject: [PATCH] Update to isl-0.18-43-g0b4256f Even more isl coalesce changes. git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@290783 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/External/isl/GIT_HEAD_ID | 2 +- lib/External/isl/doc/manual.pdf | Bin 475438 -> 475433 bytes lib/External/isl/isl_affine_hull.c | 212 ----------------- lib/External/isl/isl_coalesce.c | 289 ++++++++++++++++++---- lib/External/isl/isl_constraint.c | 3 +- lib/External/isl/isl_constraint_private.h | 2 + lib/External/isl/isl_local.c | 59 ++++- lib/External/isl/isl_local.h | 1 + lib/External/isl/isl_local_space.c | 92 ++++++- lib/External/isl/isl_local_space_private.h | 2 + lib/External/isl/isl_map.c | 369 ++++++++++++++++++++++++----- lib/External/isl/isl_map_private.h | 9 + lib/External/isl/isl_map_simplify.c | 2 + lib/External/isl/isl_test.c | 4 + lib/External/isl/isl_val_private.h | 2 + test/ScopInfo/switch-3.ll | 2 +- 16 files changed, 718 insertions(+), 332 deletions(-) diff --git a/lib/External/isl/GIT_HEAD_ID b/lib/External/isl/GIT_HEAD_ID index 86302141..181aa3fe 100644 --- a/lib/External/isl/GIT_HEAD_ID +++ b/lib/External/isl/GIT_HEAD_ID @@ -1 +1 @@ -isl-0.18-28-gccb9f33 +isl-0.18-43-g0b4256f diff --git a/lib/External/isl/doc/manual.pdf b/lib/External/isl/doc/manual.pdf index 61f0077d3d9c4a81e02f0c3f2e7a95e711e9c2e5..b064c4779a9d86dbff3d3b862d0c43d4db70953a 100644 GIT binary patch delta 5200 zcwU88c{J2t*vAZm3`Mq?F!p2{W5$+c7`w>6jHQ`uGem0a#n)0&$r6pdY-3HtNLeyc zNe$W8La9mCO0w7M_n!0q{r>T}=bq<&KA&@*bD#S>_fe8WO_D_8NzPo2b@o%h^-P1a zJ;XpI8djjk#SH9*U)(D

AiBP%WC~5L9b)8)BR)CW}fADxtYLT z?9#-I3XMBnRW*;-&3~8*vMO!yLGZZD+gCIsr7oeRcFA7bf035XUuc-7p7Ef_y>sxP zoBqWS6~ge8k^En;g+H>C70>wgMP#j4l1bE+DKJVFRxyCdjcxsI5J%4qO?mXTEXyn4 zZ^x>dt5MY($G&V0aiL@!*9{yO`yn_E0XhWu5S)kLYQ=Fu^5m2?HIO=JO^miOQbQ4m zR8-w(t&g2<6HW3qO)3rk z9#j?2rst|VII90Us>-|PP5xF?|KLskWqgHPg>8bCmEswzZEor7sB6;p!znp_h!D^< zK5~k!mEK6Ef`7{O;(la^CM_F#QT_T|c2uToY>M$yO4!1sGaQBm(7E#yS} z8;H0J#A{AM@m{@sdMq86^yNugml_ejLB6M?F_NTgZw4lRd^n)a%ib=wQFJ!-IrA79Lx}*XOkwX$CK(wfkTfR>p?Sv z1LgJho86K07`lJ$CIK=nI4wBF)hHAq4uoU{$xdE(#d?-ZgNHR*NJmvm+Tiq(Vr*em z8)U_-(5&60MVMadZP9)vLW&e65mm_-k{$$EG=*EVo3})+E)FYJ(Q^ z3;r0`x&S$U5Kc?RBc-E#R&*b_lXJwOL{A_Bm#mpQenZQ|1$6p$<;I}W$&(b)jUhXG z7i>cbwB-A5{}eV`Nh3QKb39<0-HQoFeL_uxr;oabZ=WjIe@M*TaT`(?;;ISy>}BC; z>hvZr+(B=u&TwTg>|P2xIv^y+?%Rd#!PJ0qj86vp#b^_X&ZeQ86%-$)m;>>&^dusKA2=i-pY_G-G=n> zKO?=V<~|=Z%i_@dNqHZl_&*^(S|a0_@S%BlQ|?!9dSvaHKO|ASENlaHXx2~SCBYBP zOi$g(`|MCi+qwBrbd__z;jG_P4yo^Nc5ODzik;UZ@OtN<*UT+(RT^UiWnSKl&*sj3 zx^}=d0U18QPet4|X3=+67EGUNzIbvhJ{=kRk}ow6c8sEM9%aVtNX-}2fXc8e=U(TsbAp4rPOc< z;@4EL6p?VbOsGC9Bq9b?a{DeMT&kaT1!Mfd1 zV6=Qzxck>umGwI}INKoMc8~2Z8*B}vf?a2~QHu=uIFDS!d>fSwniSZ@8tHIb+5ms~ zXbS{J(M`9OpU05g=}E_s7Y1JSj>dANB|1>3u!>@i1%!ZIVe>CF4D!l8r*$^rMbWa9 zTXIS$tYTq*fRpS*5Mky~HXc~FbEDhz=4@CWF1N$fl9f;R0M9r?n9o*ygS^2LjEJzY zqV|lM#O0E+!KU{*0$7uK|QQFwUIb=Yzt>RL~7j=hPPzy_cR}w?eLESZ*VeWi(tN0}C zm}$1j(*F}j7Q4CP>kw3-{?8I-F7wfS)Neq@e>nVG>CCNB+p~tUAp*d2;0#%cg!xtz zgjsYg7orz#gg4On6DG>kD9;^ap@mt|X)k@{BxPkia@y9`fg0N|iM}_M=H|Rj)pJGP zz64&*KJ7GLiTiemZ{GB7mKlz;<#%q0+(Qv$ zC)xBVvp)7Xk+6f!28UXx(b+J?&n}?xH>sB6LRQPJ!x&f7|!eyxvw1)wmMo0KLNY_qJ!hWDs?n>&Lkd zp?`iX0K;qYJCFGG|^yaERIa>R5m4;oKdVZXnLYn$U zUS;+9-ssttubT!OyE5lglg*ml_-lwfZ_c-Om0RT*o!&!{{7Z) zqBi}RZ}KUB?9$}Kvdboxzasr0<__8b8>kclt_hjbsY|(R&*M1rcZr8ATmq{|j|1w= z@WR!cHNHUeUkgu$R^!;pzaZLJBG-J?L8ozn^n&&pTReObyvlMlRIUg8PEe!N%~Hqv9|WU+f0+wjqh{0+4;$TX|3?uk zUunY4s(l)c6$;>|iDAc2XtaI;BFXx{)qk3Hq5am>+@>|c1o;YQ=zpbRU(R4}T5Qvf zQMRt)q2+`VY5DCJJGZKgC5tp#7cl?5U?eegE0W2ULg!bn%wE^J2dw2V?d3vW*_M15R?b38glkqK zqg(@>Uou|7?ETk1_>dn?*an}|_xNyr?Os$JyQpYuatKS!NTwe$`NaKV=qJ!{B%2EU zW!bCIC+j*jDc<@az`~x4p=zaJ=Z+R;e&qaV%eYt@mHIoO$nsksOL{&S#o9olTT>Np z8?a_|5%r>kr{|aYwt}@pT6C`ey9Hv+HplZ?Fp!o9Q4h>JQvcn;8|V?&4iqcMw)V;8 z@^U9!Phhqv=bV?t7{phXC{nw@vS(+}HY27+WR>SAVJjivy_!;ZI$=^$s zB*U?slccp^K%QKP#Z;qPe?Ou36O^kpwnX1s&Ts@J3M?@XHsvuF${~7K&}8V^#Wgpa z!6bVD!){|m34>1ZF5yHMw(d}ZCZW>|$&IDw3L)x?YEl0)HsY zXHX!P84TFf?-@(!fcf(#;_6`hNwV{eF>%W{ZGbI3NgBz=)erYF8rAr0e#3fc?W7KI zcG0foK3Ep3Tu{Y?cR4|Qf1gc`7D+3N3N=W=fA!;O&eXoR)Hy?`d%PH>S#PXG(LVJFN~pUOZjsNyKB;L`()1dk7a*Sf zdn*|&JOQdirekM}fO3-jp#Y$bW@iBLxB^#>h~xSmL8x_&nEFvZB$3CL>gXH4xg12| zEIw>w6aTzmuT_Yhj=3>&7qU{$+UPty9LAm(Eqfwp8kxIGul6d4PX(1{43!@kK34gz zgn!3WWMiEoJ`#MSTwL~E@B5{MEbF|=3bT-hj(Q=pTZRoi3vG8L{eMT72Q2|@O-M*v z_2<&NB3f6XJ_}|k@h4kv zwN9>ja|QFrM2+UMF}quX8zat1HqN28^p$OcCp_$V=u9t8E%x`QvG>8J>jQ(?+fR_D z+C)jm+PFyHpNWvVpGi8qR{}8}kZO=2ZiQmbS=+n#4yj|+!oC9TC*1IlHLQq(8w-&* z+f_Bg3t@PMWTWT`Xte|so}@Mi-NhFA4>*&~K~0U~co;C3SKD>UBaLbIbJR5F>HAXdP zY+m@i%?|zLk9GBU{BR=`E$A`Zyt24jdskxvj@6yy)=K2H=V`Q#SFQ$mV#k|is=^b1 zQ}$4I+xxS|WVn4L(d5f=A`FHVs&2UuT+Ux2itp&=&2XHC{_ow>le7*8UNZk6Pa9Sn zQTOFacl;nE$B&=wYNio5Jt5%TpE#_6{pU|{^I1MSx^qYL+#l1M|=JgT&jSH%F)A9#tl$zg(1WcfDu-DIPBTRw`G08_VkbJ zh-Y%bO0C|htwmNh1$@zT!?_Ax7150A6n55kANjTE8m2s7`Z}<*caA+gp_l<`f4I`B zZ9Q^CeAap|w$sA(&raEki;%0Q7d9TJy&t*xe)`V)C|<*LM%;6|A2Hc$8wZIEuP%;@ z9VAoZqGKR%OH4dn<22l^*tk;CUYy$q|Sl1*PZM0cisO}ARSmUU1mtAPS z)PvTAQxdH!0&r*8lNI$VE_y`&e8YQo_^C?3mHhH;kdF&_^sU}_#^twfL%rsFnQ!m! z2;HNf>RY)V5LO9Sb?dh#gyN;3q!!n?q8|>!;YSDzpmGz|HFkN%qobeGR2iYqE-r^C z1y^JdWD$43rpndeYbt{f+ubCq2P(%}6N-e6cKo+=C(N`aAi3nK6WqDNwM*LBxAxf$ zpo?VeSx_u&a3tYA*Kag}&Rz=T4#AQ@aU!(!lKkh4RCAeP5Vh>A%T6QRSgt*4;Fn|lEZ(ef2#TW2Jb8EEck8{&m^|&%Noa=$-9}&8nX1?;HsBN!*_w;VnRi0Op`sc(1h11sdX2>mh zTKF>Fbkk)stL|ID+7Ie)E#12fGO5G5S48e>jUue4^+an?FUE_mY;O+or+~4vDIjoSB>DlVuxcd+P#j|rQy<1((4C~FC+|NaM2Od zr*&-1$GU61slV&smr}2P%7lM5#afY3PPbQksKy1_UjQX9#g9? zsai#`wDSYDSTfrW<_qHPz_e2P{?z$u(B+TB^$U&{`8>vwl$jI;YwAd+0Q>H0XFLk16*J(s^>Vydp2VLSGl2eer_yqKsn`&Sp zJ}ye*IOTSprs>f_oGxM1$FI|PsjViti%r_fc#hLVr#$Tzt=`E10~=SS=}|oj4L+~) zL_}u#3y&`9PdOTm3k`Xu2(`M7#-eQ-gnwBMyuIioOp2j>!TXg%NhYWdw^J8P5ch}U ziD5Ylior*#gqI|St_Jf2oE_&GD)!>B{gy@17f3FWvoJV+M@aT=z7w>-uAopKYFF4$ zSV4VSk00OCb>4Ge#XHps+9o){V4qt)Cp!%B+ZFvZ9E3png~mN;qEwktJyd>zory`d zr2#4IK9xHXT6NsEOjDZ&zrKBys>M1%%rUGkO5@M^tipU){tx{Xe!c#o2fO1wIuUK< zEIy|-ej>-TyW~k~ujj4Cb6skXJv?JvHM{?3UXdv0QLj9OsfFLI&>AZiqv@mmiXq2} z9cdt1v{Uvk2k9J;=xcMEO*}A1<-I5M&`=t`g}Ntm$Y4>@?YU}cMpO#}V(h~nC6y=| z{}LPrb5@B;x7iGB6MVWOdWh+xq^}7d&e3>ndwc>9mr~9CrR*+M_4LryA2X5M-IhfD z<)DKOb{q(Y%%GU{PGUfNrT@x9=G302_+R&+K;v7KyT$1RI^v z$8qn9n?#*&CyRe2#`DFS>B8PQih3&T>WVHW)dbuxP)d?V0#B4$yw6J{+lXpwdY78n z#6Q{*T|$?AC)=?l$`qdROFoxBB+N_`$s*r%VBRujC#(24mL<(res`J+UB{zRSlP3^KJ z@OYpB)7b|+gS(YcLTu>Go6-tk2{q|n&bY#j^-$oacWU~lp_%+pQea53hwC}vQNc)) z;|dx(+Qf8dd`yT+ApRQw!3T{KMcnNFb^O(DzN5fmHas9LOeiTHt{d3@kB$x^>aSqB zO6PsOtg}=Qv;Z;`WX7<%b>)6YadiVkP)Q+gON zUNYoGrDJ@c&L#;RvfpNjGoasaNYEoXXh3qGhbO)FIVrEC-oxFP7k8v1N zOV|_aDSHq$*02B46MrjUb;rIr_847XJE#~p60cFnot|5D%)ZOQ9-`KVzDK-*J2J|1 z&)&zSq4FWFM*1f29p8qaS4HwS!3K16ebw|upj7067)6DNAD*wc3c~~XeEU|OzY(1G zeKSBy32?`rd!744~-;gTZ3g zDm+U=L3vu2!flTgfYQ7qZL)cfJ9eSS0FGDx&7YS3x`O@jy!De!v=A>*9$#1J`Bp9$ zdg@r89>K73+f}tf^Of()cp1nr{S4NX5!ejYSRuFnxs!poI;9hJK(wVsDgar&$F~z{ zVx$Wkif_jrjdrI{w(`tw&AYT|dj4~4hF9^JQ3!Q*z)*$Zn*F8KR>rt*gexigwNC3w z&=3j688s*fU-y|#e+c7*Yjq6$`gS(!4aBScUi{cz6>G!3tAf3DORHQ#da=s}b z*&`RM2J&ffS-ddD+qF8G8vMQlJ#mM>z9aL>dXx4uaSqXs;Tdi|E9uvNj@oJ zL^-{!`nZ74?5JxD+x`wi&Y;{;;AC=iz!R$cN7DP+17{6eVI~24U7>dAn7d9T@W-KX z5Mw(IBHHtd^}HQ}S8)#>azU^69CSv7(Aj&p(`dMwBirYRMB5zsRII8FDS#dM$$u0Y z7AMCpl`7GR^C;|{WW1#L)*PdeTVon&E;V3U_NDziS{Rd8pHUTl2?rxqe`cl;8=Hr= zs72t7SkI6%L{}L>fVJTd&80Jq%LD?LPBcMyEe}sn)|egd#rIe#&5#$gb2F+((RX{s ziSweb)5V^xS}U>9)2|;oAfVlhFYUv--xLJx$P@c@w6qx%8PUkOP?FDm(Tg>?Y*~^I zs8`5dYImjdt9Ez|Q^{jugEWP?G~C2luB;uh4eL?fPP?KL#{ z)s^DGpteRn5*c#0iSk`&tuJ$<5OdPRhUBRvAXW7pb$e+&<2#$h%lyRguPb zkv09Pi_cJUp-Q7(%X$6fq*y`c!grH9l7z|;+Z$I5-OJHilR@PGDX9gzZ%Ec_YYyOz z#$ax4tM#}f$z0HlmNL32r$qF}&k&AHORW+V*M2r^RR9Vk$1$@5cMtMuE-jr&YN2sq zA=8{pnbknR1<4l19-TxBBz+Y~gsm`d!tu8R4vzfkYmZuz0MQXvfA7AwXd@j6;EeRW zmto1+ft*5+rL~oACBlE%ucKrbN$L{##x~x#PJnSi)vxtMf7c-p#kmrW*yZlxn`!3} zz*0u^FAl2|z*b}A><;C#Xz$AKUu)jAHD8#rk55&Gs^^{AlFoi5LQ*F63B2<9JUJJ0 zu}U32{86E#>z#Q>!9j_P+j?(B=-8x`aT)6fXX=xz%@4zrrqiCU{GE&A9Qm!XcZKzI zN;>sZkXs2~SlCV?$liDPsVk)loKZMAIXl5Z$JrMCGdWU_;R5j|3H$f$jkU?32Y_;3 z>gC#7OBbkzl@V}Q89BdB>D&ZE3i(kgXWj}^4+|r2AA87HF+d6rZta`ce@Q!hZa2vz zgNn8{GM&>~Of=`UUN0TA%dfAM345yZNmekmIfSk88au#hde_8rnw%Bo z34uEj*>156joiBfKCBvi@=*7rIj6e)wCytE)*p*gNVY}?<&I^KBc;swUE&9c;J)3N zvXZM4C&J*ReXXyYa$FQ@-9;}*eq!u?Y#b!Po{(GI0;gbxgz!46o+laX=oUMfucx(2 zKO8E z+Vu&)9|N#Vb0hN`**kpn%jOK{_jf+{Y`DXWpa@6N0f~n4r_PUi`gW(f^bM=k7aS~z z&(2U)s@3_m3**(~)%@3X;mp*=mLmB)Fm9?_@53q1zImpar`OQN32@b{y|`1BsSic*kI)5k!sV^6l-?-&T*)7LUb$U8D%-fE@!xUpimZ{-OODHenC+y z7zxAuJIuYQUwC~nu+V&7t&lP&Q^-r4i>&E%e5$UG(O8xCF3|qR!N}~&!%m0)+7l+< z8#n6WUD`@m4Uk64&yr0_43JY{1ERff#Xmh=1pY*E)o5hVg1}NzqTZaepEWy9H_YyDx0=$^{*{ z%#%g(4warMCEI$}hwhwley4}*Ph7Le0~|fst$>t&EWUg1UOl>76PfuqqFFQ~bIl@B zA7n_?g;moArR16NZff0*#6y?gf!=8p`RL14k?i zkN8v^X1c9>xY?M*Y#T$9%xl)9$~tetTnkFfeYk#Oeu~R?N zQOG#PU=*m2fhoMY)@pM2nNPpA3AmT?MHqxBrff}7@#I~mAoWmfi?}qU$+oYJFc-4f}#0e1v2w_{OA&7khT{zkC)>W zD=$)>f_cEB=EMWm_;TQrKdculF9h(c`=c*EhHMpb=~NER2I3nB(l4iQuQTBkN9*Yg zphtJQA>Tc#nR6a$wdQWX8tfxy(|aQRmFY*5PljAXa-R98x|OWpp2+EcglLy!!Ms*>m>)t<`l z>;|Lm%J10*PAuxl`ly`F?5V(PtP8jHz#ly3Rl^_l{b#AAxm-YW6>(%+BeTM14J|HG zMOx*#mO{EOmSPd7g^}TZ$w1Fxt0~kT(2^c)k^q9yvi3$1x$4;Aw{%74sD^LLrkVpO)C*Vt& z)mj_+;sk^=DZQF)g5cWLSJCCm^23193VvKG^mqat#TRZZSwj_F9TW|=l!S9lu|S3z zAe*N%S?w6Gg3`~K&#GNrn1>SCU)iV5yn_eq - 1; i >= 0; --i) { - if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) == -1) - continue; - isl_basic_map_drop_equality(bmap, i); - } - - for (i = bmap->n_ineq - 1; i >= 0; --i) { - if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) == -1) - continue; - isl_basic_map_drop_inequality(bmap, i); - } - - bmap = isl_basic_map_add_known_div_constraints(bmap); - return bmap; -} - -/* Drop all constraints in bset that involve any of the dimensions - * first to first+n-1. - */ -__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving( - __isl_take isl_basic_set *bset, unsigned first, unsigned n) -{ - return isl_basic_map_drop_constraints_involving(bset, first, n); -} - -/* Drop all constraints in bmap that do not involve any of the dimensions - * first to first + n - 1 of the given type. - */ -__isl_give isl_basic_map *isl_basic_map_drop_constraints_not_involving_dims( - __isl_take isl_basic_map *bmap, - enum isl_dim_type type, unsigned first, unsigned n) -{ - int i; - unsigned dim; - - if (n == 0) { - isl_space *space = isl_basic_map_get_space(bmap); - isl_basic_map_free(bmap); - return isl_basic_map_universe(space); - } - bmap = isl_basic_map_cow(bmap); - if (!bmap) - return NULL; - - dim = isl_basic_map_dim(bmap, type); - if (first + n > dim || first + n < first) - isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, - "index out of bounds", return isl_basic_map_free(bmap)); - - first += isl_basic_map_offset(bmap, type) - 1; - - for (i = bmap->n_eq - 1; i >= 0; --i) { - if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) != -1) - continue; - isl_basic_map_drop_equality(bmap, i); - } - - for (i = bmap->n_ineq - 1; i >= 0; --i) { - if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) != -1) - continue; - isl_basic_map_drop_inequality(bmap, i); - } - - bmap = isl_basic_map_add_known_div_constraints(bmap); - return bmap; -} - -/* Drop all constraints in bset that do not involve any of the dimensions - * first to first + n - 1 of the given type. - */ -__isl_give isl_basic_set *isl_basic_set_drop_constraints_not_involving_dims( - __isl_take isl_basic_set *bset, - enum isl_dim_type type, unsigned first, unsigned n) -{ - return isl_basic_map_drop_constraints_not_involving_dims(bset, - type, first, n); -} - -/* Drop all constraints in bmap that involve any of the dimensions - * first to first + n - 1 of the given type. - */ -__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving_dims( - __isl_take isl_basic_map *bmap, - enum isl_dim_type type, unsigned first, unsigned n) -{ - unsigned dim; - - if (!bmap) - return NULL; - if (n == 0) - return bmap; - - dim = isl_basic_map_dim(bmap, type); - if (first + n > dim || first + n < first) - isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, - "index out of bounds", return isl_basic_map_free(bmap)); - - bmap = isl_basic_map_remove_divs_involving_dims(bmap, type, first, n); - first += isl_basic_map_offset(bmap, type) - 1; - return isl_basic_map_drop_constraints_involving(bmap, first, n); -} - -/* Drop all constraints in bset that involve any of the dimensions - * first to first + n - 1 of the given type. - */ -__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving_dims( - __isl_take isl_basic_set *bset, - enum isl_dim_type type, unsigned first, unsigned n) -{ - return isl_basic_map_drop_constraints_involving_dims(bset, - type, first, n); -} - -/* Drop constraints from "map" by applying "drop" to each basic map. - */ -static __isl_give isl_map *drop_constraints(__isl_take isl_map *map, - enum isl_dim_type type, unsigned first, unsigned n, - __isl_give isl_basic_map *(*drop)(__isl_take isl_basic_map *bmap, - enum isl_dim_type type, unsigned first, unsigned n)) -{ - int i; - unsigned dim; - - if (!map) - return NULL; - - dim = isl_map_dim(map, type); - if (first + n > dim || first + n < first) - isl_die(isl_map_get_ctx(map), isl_error_invalid, - "index out of bounds", return isl_map_free(map)); - - map = isl_map_cow(map); - if (!map) - return NULL; - - for (i = 0; i < map->n; ++i) { - map->p[i] = drop(map->p[i], type, first, n); - if (!map->p[i]) - return isl_map_free(map); - } - - if (map->n > 1) - ISL_F_CLR(map, ISL_MAP_DISJOINT); - - return map; -} - -/* Drop all constraints in map that involve any of the dimensions - * first to first + n - 1 of the given type. - */ -__isl_give isl_map *isl_map_drop_constraints_involving_dims( - __isl_take isl_map *map, - enum isl_dim_type type, unsigned first, unsigned n) -{ - if (n == 0) - return map; - return drop_constraints(map, type, first, n, - &isl_basic_map_drop_constraints_involving_dims); -} - -/* Drop all constraints in "map" that do not involve any of the dimensions - * first to first + n - 1 of the given type. - */ -__isl_give isl_map *isl_map_drop_constraints_not_involving_dims( - __isl_take isl_map *map, - enum isl_dim_type type, unsigned first, unsigned n) -{ - if (n == 0) { - isl_space *space = isl_map_get_space(map); - isl_map_free(map); - return isl_map_universe(space); - } - return drop_constraints(map, type, first, n, - &isl_basic_map_drop_constraints_not_involving_dims); -} - -/* Drop all constraints in set that involve any of the dimensions - * first to first + n - 1 of the given type. - */ -__isl_give isl_set *isl_set_drop_constraints_involving_dims( - __isl_take isl_set *set, - enum isl_dim_type type, unsigned first, unsigned n) -{ - return isl_map_drop_constraints_involving_dims(set, type, first, n); -} - -/* Drop all constraints in "set" that do not involve any of the dimensions - * first to first + n - 1 of the given type. - */ -__isl_give isl_set *isl_set_drop_constraints_not_involving_dims( - __isl_take isl_set *set, - enum isl_dim_type type, unsigned first, unsigned n) -{ - return isl_map_drop_constraints_not_involving_dims(set, type, first, n); -} - /* Construct an initial underapproximation of the hull of "bset" * from "sample" and any of its adjacent points that also belong to "bset". */ diff --git a/lib/External/isl/isl_coalesce.c b/lib/External/isl/isl_coalesce.c index 09d9c7cc..cd85cf1d 100644 --- a/lib/External/isl/isl_coalesce.c +++ b/lib/External/isl/isl_coalesce.c @@ -25,9 +25,11 @@ #include "isl_tab.h" #include #include +#include #include #include #include +#include #include #include @@ -2183,36 +2185,192 @@ static enum isl_change coalesce_local_pair(int i, int j, * * floor((f(x) + shift * d)/d) - shift */ -static int shift_div(struct isl_coalesce_info *info, int div, isl_int shift) +static isl_stat shift_div(struct isl_coalesce_info *info, int div, + isl_int shift) { unsigned total; info->bmap = isl_basic_map_shift_div(info->bmap, div, 0, shift); if (!info->bmap) - return -1; + return isl_stat_error; total = isl_basic_map_dim(info->bmap, isl_dim_all); total -= isl_basic_map_dim(info->bmap, isl_dim_div); if (isl_tab_shift_var(info->tab, total + div, shift) < 0) - return -1; + return isl_stat_error; - return 0; + return isl_stat_ok; +} + +/* If the integer division at position "div" is defined by an equality, + * i.e., a stride constraint, then change the integer division expression + * to have a constant term equal to zero. + * + * Let the equality constraint be + * + * c + f + m a = 0 + * + * The integer division expression is then of the form + * + * a = floor((-f - c')/m) + * + * The integer division is first shifted by t = floor(c/m), + * turning the equality constraint into + * + * c - m floor(c/m) + f + m a' = 0 + * + * i.e., + * + * (c mod m) + f + m a' = 0 + * + * That is, + * + * a' = (-f - (c mod m))/m = floor((-f)/m) + * + * because a' is an integer and 0 <= (c mod m) < m. + * The constant term of a' can therefore be zeroed out. + */ +static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div) +{ + isl_bool defined; + isl_stat r; + isl_constraint *c; + isl_int shift, stride; + + defined = isl_basic_map_has_defining_equality(info->bmap, isl_dim_div, + div, &c); + if (defined < 0) + return isl_stat_error; + if (!defined) + return isl_stat_ok; + if (!c) + return isl_stat_error; + isl_int_init(shift); + isl_int_init(stride); + isl_constraint_get_constant(c, &shift); + isl_constraint_get_coefficient(c, isl_dim_div, div, &stride); + isl_int_fdiv_q(shift, shift, stride); + r = shift_div(info, div, shift); + isl_int_clear(stride); + isl_int_clear(shift); + isl_constraint_free(c); + if (r < 0) + return isl_stat_error; + info->bmap = isl_basic_map_set_div_expr_constant_num_si_inplace( + info->bmap, div, 0); + if (!info->bmap) + return isl_stat_error; + return isl_stat_ok; +} + +/* The basic maps represented by "info1" and "info2" are known + * to have the same number of integer divisions. + * Check if pairs of integer divisions are equal to each other + * despite the fact that they differ by a rational constant. + * + * In particular, look for any pair of integer divisions that + * only differ in their constant terms. + * If either of these integer divisions is defined + * by stride constraints, then modify it to have a zero constant term. + * If both are defined by stride constraints then in the end they will have + * the same (zero) constant term. + */ +static isl_stat harmonize_stride_divs(struct isl_coalesce_info *info1, + struct isl_coalesce_info *info2) +{ + int i, n; + int total; + + total = isl_basic_map_total_dim(info1->bmap); + n = isl_basic_map_dim(info1->bmap, isl_dim_div); + for (i = 0; i < n; ++i) { + isl_bool known, harmonize; + + known = isl_basic_map_div_is_known(info1->bmap, i); + if (known >= 0 && known) + known = isl_basic_map_div_is_known(info2->bmap, i); + if (known < 0) + return isl_stat_error; + if (!known) + continue; + harmonize = isl_basic_map_equal_div_expr_except_constant( + info1->bmap, i, info2->bmap, i); + if (harmonize < 0) + return isl_stat_error; + if (!harmonize) + continue; + if (normalize_stride_div(info1, i) < 0) + return isl_stat_error; + if (normalize_stride_div(info2, i) < 0) + return isl_stat_error; + } + + return isl_stat_ok; +} + +/* If "shift" is an integer constant, then shift the integer division + * at position "div" of the basic map represented by "info" by "shift". + * If "shift" is not an integer constant, then do nothing. + * If "shift" is equal to zero, then no shift needs to be performed either. + * + * That is, if the integer division has the form + * + * floor(f(x)/d) + * + * then replace it by + * + * floor((f(x) + shift * d)/d) - shift + */ +static isl_stat shift_if_cst_int(struct isl_coalesce_info *info, int div, + __isl_keep isl_aff *shift) +{ + isl_bool cst; + isl_stat r; + isl_int d; + isl_val *c; + + cst = isl_aff_is_cst(shift); + if (cst < 0 || !cst) + return cst < 0 ? isl_stat_error : isl_stat_ok; + + c = isl_aff_get_constant_val(shift); + cst = isl_val_is_int(c); + if (cst >= 0 && cst) + cst = isl_bool_not(isl_val_is_zero(c)); + if (cst < 0 || !cst) { + isl_val_free(c); + return cst < 0 ? isl_stat_error : isl_stat_ok; + } + + isl_int_init(d); + r = isl_val_get_num_isl_int(c, &d); + if (r >= 0) + r = shift_div(info, div, d); + isl_int_clear(d); + + isl_val_free(c); + + return r; } /* Check if some of the divs in the basic map represented by "info1" * are shifts of the corresponding divs in the basic map represented - * by "info2". If so, align them with those of "info2". - * Only do this if "info1" and "info2" have the same number + * by "info2", taking into account the equality constraints "eq1" of "info1" + * and "eq2" of "info2". If so, align them with those of "info2". + * "info1" and "info2" are assumed to have the same number * of integer divisions. * * An integer division is considered to be a shift of another integer - * division if one is equal to the other plus a constant. + * division if, after simplification with respect to the equality + * constraints of the other basic map, one is equal to the other + * plus a constant. * * In particular, for each pair of integer divisions, if both are known, - * have identical coefficients (apart from the constant term) and - * if the difference between the constant terms (taking into account - * the denominator) is an integer, then move the difference outside. - * That is, if one integer division is of the form + * have the same denominator and are not already equal to each other, + * simplify each with respect to the equality constraints + * of the other basic map. If the difference is an integer constant, + * then move this difference outside. + * That is, if, after simplification, one integer division is of the form * * floor((f(x) + c_1)/d) * @@ -2223,49 +2381,99 @@ static int shift_div(struct isl_coalesce_info *info, int div, isl_int shift) * and n = (c_2 - c_1)/d is an integer, then replace the first * integer division by * - * floor((f(x) + c_1 + n * d)/d) - n = floor((f(x) + c_2)/d) - n + * floor((f_1(x) + c_1 + n * d)/d) - n, + * + * where floor((f_1(x) + c_1 + n * d)/d) = floor((f2(x) + c_2)/d) + * after simplification with respect to the equality constraints. */ -static int harmonize_divs(struct isl_coalesce_info *info1, - struct isl_coalesce_info *info2) +static isl_stat harmonize_divs_with_hulls(struct isl_coalesce_info *info1, + struct isl_coalesce_info *info2, __isl_keep isl_basic_set *eq1, + __isl_keep isl_basic_set *eq2) { int i; int total; - - if (!info1->bmap || !info2->bmap) - return -1; - - if (info1->bmap->n_div != info2->bmap->n_div) - return 0; - if (info1->bmap->n_div == 0) - return 0; + isl_local_space *ls1, *ls2; total = isl_basic_map_total_dim(info1->bmap); + ls1 = isl_local_space_wrap(isl_basic_map_get_local_space(info1->bmap)); + ls2 = isl_local_space_wrap(isl_basic_map_get_local_space(info2->bmap)); for (i = 0; i < info1->bmap->n_div; ++i) { - isl_int d; - int r = 0; + isl_stat r; + isl_aff *div1, *div2; - if (isl_int_is_zero(info1->bmap->div[i][0]) || - isl_int_is_zero(info2->bmap->div[i][0])) + if (!isl_local_space_div_is_known(ls1, i) || + !isl_local_space_div_is_known(ls2, i)) continue; if (isl_int_ne(info1->bmap->div[i][0], info2->bmap->div[i][0])) continue; - if (isl_int_eq(info1->bmap->div[i][1], info2->bmap->div[i][1])) - continue; - if (!isl_seq_eq(info1->bmap->div[i] + 2, - info2->bmap->div[i] + 2, total)) + if (isl_seq_eq(info1->bmap->div[i] + 1, + info2->bmap->div[i] + 1, 1 + total)) continue; - isl_int_init(d); - isl_int_sub(d, info2->bmap->div[i][1], info1->bmap->div[i][1]); - if (isl_int_is_divisible_by(d, info1->bmap->div[i][0])) { - isl_int_divexact(d, d, info1->bmap->div[i][0]); - r = shift_div(info1, i, d); - } - isl_int_clear(d); + div1 = isl_local_space_get_div(ls1, i); + div2 = isl_local_space_get_div(ls2, i); + div1 = isl_aff_substitute_equalities(div1, + isl_basic_set_copy(eq2)); + div2 = isl_aff_substitute_equalities(div2, + isl_basic_set_copy(eq1)); + div2 = isl_aff_sub(div2, div1); + r = shift_if_cst_int(info1, i, div2); + isl_aff_free(div2); if (r < 0) - return -1; + break; } + isl_local_space_free(ls1); + isl_local_space_free(ls2); - return 0; + if (i < info1->bmap->n_div) + return isl_stat_error; + return isl_stat_ok; +} + +/* Check if some of the divs in the basic map represented by "info1" + * are shifts of the corresponding divs in the basic map represented + * by "info2". If so, align them with those of "info2". + * Only do this if "info1" and "info2" have the same number + * of integer divisions. + * + * An integer division is considered to be a shift of another integer + * division if, after simplification with respect to the equality + * constraints of the other basic map, one is equal to the other + * plus a constant. + * + * First check if pairs of integer divisions are equal to each other + * despite the fact that they differ by a rational constant. + * If so, try and arrange for them to have the same constant term. + * + * Then, extract the equality constraints and continue with + * harmonize_divs_with_hulls. + */ +static isl_stat harmonize_divs(struct isl_coalesce_info *info1, + struct isl_coalesce_info *info2) +{ + isl_basic_map *bmap1, *bmap2; + isl_basic_set *eq1, *eq2; + isl_stat r; + + if (!info1->bmap || !info2->bmap) + return isl_stat_error; + + if (info1->bmap->n_div != info2->bmap->n_div) + return isl_stat_ok; + if (info1->bmap->n_div == 0) + return isl_stat_ok; + + if (harmonize_stride_divs(info1, info2) < 0) + return isl_stat_error; + + bmap1 = isl_basic_map_copy(info1->bmap); + bmap2 = isl_basic_map_copy(info2->bmap); + eq1 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap1)); + eq2 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap2)); + r = harmonize_divs_with_hulls(info1, info2, eq1, eq2); + isl_basic_set_free(eq1); + isl_basic_set_free(eq2); + + return r; } /* Do the two basic maps live in the same local space, i.e., @@ -2947,7 +3155,8 @@ static __isl_give isl_aff_list *set_up_substitutions( isl_aff *aff; if (j < n_div_j && - isl_seq_eq(bmap_i->div[i], bmap_j->div[j], 2 + total)) { + isl_basic_map_equal_div_expr_part(bmap_i, i, bmap_j, j, + 0, 2 + total)) { ++j; list = isl_aff_list_add(list, isl_aff_copy(aff_nan)); continue; diff --git a/lib/External/isl/isl_constraint.c b/lib/External/isl/isl_constraint.c index 490b191d..3d4391a7 100644 --- a/lib/External/isl/isl_constraint.c +++ b/lib/External/isl/isl_constraint.c @@ -473,7 +473,8 @@ const char *isl_constraint_get_dim_name(__isl_keep isl_constraint *constraint, isl_local_space_get_dim_name(constraint->ls, type, pos) : NULL; } -void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v) +void isl_constraint_get_constant(__isl_keep isl_constraint *constraint, + isl_int *v) { if (!constraint) return; diff --git a/lib/External/isl/isl_constraint_private.h b/lib/External/isl/isl_constraint_private.h index 5cef0170..26a86303 100644 --- a/lib/External/isl/isl_constraint_private.h +++ b/lib/External/isl/isl_constraint_private.h @@ -21,6 +21,8 @@ struct isl_constraint { struct isl_constraint *isl_basic_set_constraint(struct isl_basic_set *bset, isl_int **line); +void isl_constraint_get_constant(__isl_keep isl_constraint *constraint, + isl_int *v); void isl_constraint_get_coefficient(__isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos, isl_int *v); __isl_give isl_constraint *isl_constraint_set_constant( diff --git a/lib/External/isl/isl_local.c b/lib/External/isl/isl_local.c index 7725af9d..c8240b91 100644 --- a/lib/External/isl/isl_local.c +++ b/lib/External/isl/isl_local.c @@ -11,16 +11,59 @@ #include /* Given a matrix "div" representing local variables, - * does the variable at position "pos" have an explicit representation? + * is the variable at position "pos" marked as not having + * an explicit representation? + * Note that even if this variable is not marked in this way and therefore + * does have an explicit representation, this representation may still + * depend (indirectly) on other local variables that do not + * have an explicit representation. + */ +isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_mat *div, int pos) +{ + if (!div) + return isl_bool_error; + if (pos < 0 || pos >= div->n_row) + isl_die(isl_mat_get_ctx(div), isl_error_invalid, + "position out of bounds", return isl_bool_error); + return isl_int_is_zero(div->row[pos][0]); +} + +/* Given a matrix "div" representing local variables, + * does the variable at position "pos" have a complete explicit representation? + * Having a complete explicit representation requires not only + * an explicit representation, but also that all local variables + * that appear in this explicit representation in turn have + * a complete explicit representation. */ isl_bool isl_local_div_is_known(__isl_keep isl_mat *div, int pos) { + isl_bool marked; + int i, n, off; + if (!div) return isl_bool_error; if (pos < 0 || pos >= div->n_row) isl_die(isl_mat_get_ctx(div), isl_error_invalid, "position out of bounds", return isl_bool_error); - return !isl_int_is_zero(div->row[pos][0]); + + marked = isl_local_div_is_marked_unknown(div, pos); + if (marked < 0 || marked) + return isl_bool_not(marked); + + n = isl_mat_rows(div); + off = isl_mat_cols(div) - n; + + for (i = n - 1; i >= 0; --i) { + isl_bool known; + + if (isl_int_is_zero(div->row[pos][off + i])) + continue; + known = isl_local_div_is_known(div, i); + if (known < 0 || !known) + return known; + } + + return isl_bool_true; } /* Compare two matrices representing local variables, defined over @@ -37,7 +80,7 @@ int isl_local_cmp(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2) { int i; int cmp; - int known1, known2; + isl_bool unknown1, unknown2; int last1, last2; int n_col; @@ -53,13 +96,13 @@ int isl_local_cmp(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2) n_col = isl_mat_cols(div1); for (i = 0; i < div1->n_row; ++i) { - known1 = isl_local_div_is_known(div1, i); - known2 = isl_local_div_is_known(div2, i); - if (!known1 && !known2) + unknown1 = isl_local_div_is_marked_unknown(div1, i); + unknown2 = isl_local_div_is_marked_unknown(div2, i); + if (unknown1 && unknown2) continue; - if (!known1) + if (unknown1) return 1; - if (!known2) + if (unknown2) return -1; last1 = isl_seq_last_non_zero(div1->row[i] + 1, n_col - 1); last2 = isl_seq_last_non_zero(div2->row[i] + 1, n_col - 1); diff --git a/lib/External/isl/isl_local.h b/lib/External/isl/isl_local.h index f989fcbe..0970509e 100644 --- a/lib/External/isl/isl_local.h +++ b/lib/External/isl/isl_local.h @@ -3,6 +3,7 @@ #include +isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_mat *div, int pos); isl_bool isl_local_div_is_known(__isl_keep isl_mat *div, int pos); int isl_local_cmp(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2); diff --git a/lib/External/isl/isl_local_space.c b/lib/External/isl/isl_local_space.c index 9bc8c8de..daefc917 100644 --- a/lib/External/isl/isl_local_space.c +++ b/lib/External/isl/isl_local_space.c @@ -280,10 +280,62 @@ __isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls, return ls ? isl_space_get_dim_id(ls->dim, type, pos) : NULL; } +/* Return the argument of the integer division at position "pos" in "ls". + * All local variables in "ls" are known to have a (complete) explicit + * representation. + */ +static __isl_give isl_aff *extract_div(__isl_keep isl_local_space *ls, int pos) +{ + isl_aff *aff; + + aff = isl_aff_alloc(isl_local_space_copy(ls)); + if (!aff) + return NULL; + isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size); + return aff; +} + +/* Return the argument of the integer division at position "pos" in "ls". + * The integer division at that position is known to have a complete + * explicit representation, but some of the others do not. + * Remove them first because the domain of an isl_aff + * is not allowed to have unknown local variables. + */ +static __isl_give isl_aff *drop_unknown_divs_and_extract_div( + __isl_keep isl_local_space *ls, int pos) +{ + int i, n; + isl_bool unknown; + isl_aff *aff; + + ls = isl_local_space_copy(ls); + n = isl_local_space_dim(ls, isl_dim_div); + for (i = n - 1; i >= 0; --i) { + unknown = isl_local_space_div_is_marked_unknown(ls, i); + if (unknown < 0) + ls = isl_local_space_free(ls); + else if (!unknown) + continue; + ls = isl_local_space_drop_dims(ls, isl_dim_div, i, 1); + if (pos > i) + --pos; + } + aff = extract_div(ls, pos); + isl_local_space_free(ls); + return aff; +} + +/* Return the argument of the integer division at position "pos" in "ls". + * The integer division is assumed to have a complete explicit + * representation. If some of the other integer divisions + * do not have an explicit representation, then they need + * to be removed first because the domain of an isl_aff + * is not allowed to have unknown local variables. + */ __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls, int pos) { - isl_aff *aff; + isl_bool known; if (!ls) return NULL; @@ -292,18 +344,23 @@ __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls, isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, "index out of bounds", return NULL); - if (isl_int_is_zero(ls->div->row[pos][0])) + known = isl_local_space_div_is_known(ls, pos); + if (known < 0) + return NULL; + if (!known) isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, "expression of div unknown", return NULL); if (!isl_local_space_is_set(ls)) isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, "cannot represent divs of map spaces", return NULL); - aff = isl_aff_alloc(isl_local_space_copy(ls)); - if (!aff) + known = isl_local_space_divs_known(ls); + if (known < 0) return NULL; - isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size); - return aff; + if (known) + return extract_div(ls, pos); + else + return drop_unknown_divs_and_extract_div(ls, pos); } __isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls) @@ -725,7 +782,22 @@ error: return NULL; } -/* Does "ls" have an explicit representation for div "div"? +/* Is the local variable "div" of "ls" marked as not having + * an explicit representation? + * Note that even if this variable is not marked in this way and therefore + * does have an explicit representation, this representation may still + * depend (indirectly) on other local variables that do not + * have an explicit representation. + */ +isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls, + int div) +{ + if (!ls) + return isl_bool_error; + return isl_local_div_is_marked_unknown(ls->div, div); +} + +/* Does "ls" have a complete explicit representation for div "div"? */ isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div) { @@ -744,9 +816,9 @@ isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls) return isl_bool_error; for (i = 0; i < ls->div->n_row; ++i) { - isl_bool known = isl_local_space_div_is_known(ls, i); - if (known < 0 || !known) - return known; + isl_bool unknown = isl_local_space_div_is_marked_unknown(ls, i); + if (unknown < 0 || unknown) + return isl_bool_not(unknown); } return isl_bool_true; diff --git a/lib/External/isl/isl_local_space_private.h b/lib/External/isl/isl_local_space_private.h index 50626d56..427c4a4d 100644 --- a/lib/External/isl/isl_local_space_private.h +++ b/lib/External/isl/isl_local_space_private.h @@ -33,6 +33,8 @@ unsigned isl_local_space_offset(__isl_keep isl_local_space *ls, __isl_give isl_local_space *isl_local_space_replace_divs( __isl_take isl_local_space *ls, __isl_take isl_mat *div); +isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls, + int div); isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div); isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls); diff --git a/lib/External/isl/isl_map.c b/lib/External/isl/isl_map.c index 5d22aa2d..2f1c906a 100644 --- a/lib/External/isl/isl_map.c +++ b/lib/External/isl/isl_map.c @@ -1483,6 +1483,24 @@ int isl_basic_set_alloc_div(struct isl_basic_set *bset) return isl_basic_map_alloc_div(bset_to_bmap(bset)); } +/* Check that there are "n" dimensions of type "type" starting at "first" + * in "bmap". + */ +static isl_stat isl_basic_map_check_range(__isl_keep isl_basic_map *bmap, + enum isl_dim_type type, unsigned first, unsigned n) +{ + unsigned dim; + + if (!bmap) + return isl_stat_error; + dim = isl_basic_map_dim(bmap, type); + if (first + n > dim || first + n < first) + isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, + "position or range out of bounds", + return isl_stat_error); + return isl_stat_ok; +} + /* Insert an extra integer division, prescribed by "div", to "bmap" * at (integer division) position "pos". * @@ -1492,7 +1510,7 @@ int isl_basic_set_alloc_div(struct isl_basic_set *bset) __isl_give isl_basic_map *isl_basic_map_insert_div( __isl_take isl_basic_map *bmap, int pos, __isl_keep isl_vec *div) { - int i, k, n_div; + int i, k; bmap = isl_basic_map_cow(bmap); if (!bmap || !div) @@ -1501,10 +1519,8 @@ __isl_give isl_basic_map *isl_basic_map_insert_div( if (div->size != 1 + 1 + isl_basic_map_dim(bmap, isl_dim_all)) isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, "unexpected size", return isl_basic_map_free(bmap)); - n_div = isl_basic_map_dim(bmap, isl_dim_div); - if (pos < 0 || pos > n_div) - isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, - "invalid position", return isl_basic_map_free(bmap)); + if (isl_basic_map_check_range(bmap, isl_dim_div, pos, 0) < 0) + return isl_basic_map_free(bmap); bmap = isl_basic_map_extend_space(bmap, isl_basic_map_get_space(bmap), 1, 0, 2); @@ -2032,10 +2048,8 @@ __isl_give isl_set *isl_set_remove_divs(__isl_take isl_set *set) struct isl_basic_map *isl_basic_map_remove_dims(struct isl_basic_map *bmap, enum isl_dim_type type, unsigned first, unsigned n) { - if (!bmap) - return NULL; - isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type), - goto error); + if (isl_basic_map_check_range(bmap, type, first, n) < 0) + return isl_basic_map_free(bmap); if (n == 0 && !isl_space_is_named_or_nested(bmap->dim, type)) return bmap; bmap = isl_basic_map_eliminate_vars(bmap, @@ -2046,9 +2060,6 @@ struct isl_basic_map *isl_basic_map_remove_dims(struct isl_basic_map *bmap, return bmap; bmap = isl_basic_map_drop(bmap, type, first, n); return bmap; -error: - isl_basic_map_free(bmap); - return NULL; } /* Return true if the definition of the given div (recursively) involves @@ -2276,10 +2287,8 @@ __isl_give isl_basic_map *isl_basic_map_remove_divs_involving_dims( { int i; - if (!bmap) - return NULL; - isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type), - goto error); + if (isl_basic_map_check_range(bmap, type, first, n) < 0) + return isl_basic_map_free(bmap); first += isl_basic_map_offset(bmap, type); for (i = bmap->n_div - 1; i >= 0; --i) { @@ -2293,9 +2302,6 @@ __isl_give isl_basic_map *isl_basic_map_remove_divs_involving_dims( } return bmap; -error: - isl_basic_map_free(bmap); - return NULL; } __isl_give isl_basic_set *isl_basic_set_remove_divs_involving_dims( @@ -2349,13 +2355,9 @@ isl_bool isl_basic_map_involves_dims(__isl_keep isl_basic_map *bmap, { int i; - if (!bmap) + if (isl_basic_map_check_range(bmap, type, first, n) < 0) return isl_bool_error; - if (first + n > isl_basic_map_dim(bmap, type)) - isl_die(bmap->ctx, isl_error_invalid, - "index out of bounds", return isl_bool_error); - first += isl_basic_map_offset(bmap, type); for (i = 0; i < bmap->n_eq; ++i) if (isl_seq_first_non_zero(bmap->eq[i] + first, n) >= 0) @@ -2407,6 +2409,211 @@ isl_bool isl_set_involves_dims(__isl_keep isl_set *set, return isl_map_involves_dims(set, type, first, n); } +/* Drop all constraints in bmap that involve any of the dimensions + * first to first+n-1. + */ +static __isl_give isl_basic_map *isl_basic_map_drop_constraints_involving( + __isl_take isl_basic_map *bmap, unsigned first, unsigned n) +{ + int i; + + if (n == 0) + return bmap; + + bmap = isl_basic_map_cow(bmap); + + if (!bmap) + return NULL; + + for (i = bmap->n_eq - 1; i >= 0; --i) { + if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) == -1) + continue; + isl_basic_map_drop_equality(bmap, i); + } + + for (i = bmap->n_ineq - 1; i >= 0; --i) { + if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) == -1) + continue; + isl_basic_map_drop_inequality(bmap, i); + } + + bmap = isl_basic_map_add_known_div_constraints(bmap); + return bmap; +} + +/* Drop all constraints in bset that involve any of the dimensions + * first to first+n-1. + */ +__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving( + __isl_take isl_basic_set *bset, unsigned first, unsigned n) +{ + return isl_basic_map_drop_constraints_involving(bset, first, n); +} + +/* Drop all constraints in bmap that do not involve any of the dimensions + * first to first + n - 1 of the given type. + */ +__isl_give isl_basic_map *isl_basic_map_drop_constraints_not_involving_dims( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned first, unsigned n) +{ + int i; + + if (n == 0) { + isl_space *space = isl_basic_map_get_space(bmap); + isl_basic_map_free(bmap); + return isl_basic_map_universe(space); + } + bmap = isl_basic_map_cow(bmap); + if (!bmap) + return NULL; + + if (isl_basic_map_check_range(bmap, type, first, n) < 0) + return isl_basic_map_free(bmap); + + first += isl_basic_map_offset(bmap, type) - 1; + + for (i = bmap->n_eq - 1; i >= 0; --i) { + if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) != -1) + continue; + isl_basic_map_drop_equality(bmap, i); + } + + for (i = bmap->n_ineq - 1; i >= 0; --i) { + if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) != -1) + continue; + isl_basic_map_drop_inequality(bmap, i); + } + + bmap = isl_basic_map_add_known_div_constraints(bmap); + return bmap; +} + +/* Drop all constraints in bset that do not involve any of the dimensions + * first to first + n - 1 of the given type. + */ +__isl_give isl_basic_set *isl_basic_set_drop_constraints_not_involving_dims( + __isl_take isl_basic_set *bset, + enum isl_dim_type type, unsigned first, unsigned n) +{ + return isl_basic_map_drop_constraints_not_involving_dims(bset, + type, first, n); +} + +/* Drop all constraints in bmap that involve any of the dimensions + * first to first + n - 1 of the given type. + */ +__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving_dims( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned first, unsigned n) +{ + if (!bmap) + return NULL; + if (n == 0) + return bmap; + + if (isl_basic_map_check_range(bmap, type, first, n) < 0) + return isl_basic_map_free(bmap); + + bmap = isl_basic_map_remove_divs_involving_dims(bmap, type, first, n); + first += isl_basic_map_offset(bmap, type) - 1; + return isl_basic_map_drop_constraints_involving(bmap, first, n); +} + +/* Drop all constraints in bset that involve any of the dimensions + * first to first + n - 1 of the given type. + */ +__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving_dims( + __isl_take isl_basic_set *bset, + enum isl_dim_type type, unsigned first, unsigned n) +{ + return isl_basic_map_drop_constraints_involving_dims(bset, + type, first, n); +} + +/* Drop constraints from "map" by applying "drop" to each basic map. + */ +static __isl_give isl_map *drop_constraints(__isl_take isl_map *map, + enum isl_dim_type type, unsigned first, unsigned n, + __isl_give isl_basic_map *(*drop)(__isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned first, unsigned n)) +{ + int i; + unsigned dim; + + if (!map) + return NULL; + + dim = isl_map_dim(map, type); + if (first + n > dim || first + n < first) + isl_die(isl_map_get_ctx(map), isl_error_invalid, + "index out of bounds", return isl_map_free(map)); + + map = isl_map_cow(map); + if (!map) + return NULL; + + for (i = 0; i < map->n; ++i) { + map->p[i] = drop(map->p[i], type, first, n); + if (!map->p[i]) + return isl_map_free(map); + } + + if (map->n > 1) + ISL_F_CLR(map, ISL_MAP_DISJOINT); + + return map; +} + +/* Drop all constraints in map that involve any of the dimensions + * first to first + n - 1 of the given type. + */ +__isl_give isl_map *isl_map_drop_constraints_involving_dims( + __isl_take isl_map *map, + enum isl_dim_type type, unsigned first, unsigned n) +{ + if (n == 0) + return map; + return drop_constraints(map, type, first, n, + &isl_basic_map_drop_constraints_involving_dims); +} + +/* Drop all constraints in "map" that do not involve any of the dimensions + * first to first + n - 1 of the given type. + */ +__isl_give isl_map *isl_map_drop_constraints_not_involving_dims( + __isl_take isl_map *map, + enum isl_dim_type type, unsigned first, unsigned n) +{ + if (n == 0) { + isl_space *space = isl_map_get_space(map); + isl_map_free(map); + return isl_map_universe(space); + } + return drop_constraints(map, type, first, n, + &isl_basic_map_drop_constraints_not_involving_dims); +} + +/* Drop all constraints in set that involve any of the dimensions + * first to first + n - 1 of the given type. + */ +__isl_give isl_set *isl_set_drop_constraints_involving_dims( + __isl_take isl_set *set, + enum isl_dim_type type, unsigned first, unsigned n) +{ + return isl_map_drop_constraints_involving_dims(set, type, first, n); +} + +/* Drop all constraints in "set" that do not involve any of the dimensions + * first to first + n - 1 of the given type. + */ +__isl_give isl_set *isl_set_drop_constraints_not_involving_dims( + __isl_take isl_set *set, + enum isl_dim_type type, unsigned first, unsigned n) +{ + return isl_map_drop_constraints_not_involving_dims(set, type, first, n); +} + /* Does local variable "div" of "bmap" have a complete explicit representation? * Having a complete explicit representation requires not only * an explicit representation, but also that all local variables @@ -3407,8 +3614,8 @@ __isl_give isl_basic_map *isl_basic_map_move_dims( if (n == 0) return bmap; - isl_assert(bmap->ctx, src_pos + n <= isl_basic_map_dim(bmap, src_type), - goto error); + if (isl_basic_map_check_range(bmap, src_type, src_pos, n) < 0) + return isl_basic_map_free(bmap); if (dst_type == src_type && dst_pos == src_pos) return bmap; @@ -3701,8 +3908,8 @@ __isl_give isl_basic_map *isl_basic_map_project_out( if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) return isl_basic_map_remove_dims(bmap, type, first, n); - isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type), - goto error); + if (isl_basic_map_check_range(bmap, type, first, n) < 0) + return isl_basic_map_free(bmap); bmap = move_last(bmap, type, first, n); bmap = isl_basic_map_cow(bmap); @@ -5632,27 +5839,19 @@ error: struct isl_basic_map *isl_basic_map_fix_si(struct isl_basic_map *bmap, enum isl_dim_type type, unsigned pos, int value) { - if (!bmap) - return NULL; - isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error); + if (isl_basic_map_check_range(bmap, type, pos, 1) < 0) + return isl_basic_map_free(bmap); return isl_basic_map_fix_pos_si(bmap, isl_basic_map_offset(bmap, type) + pos, value); -error: - isl_basic_map_free(bmap); - return NULL; } __isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap, enum isl_dim_type type, unsigned pos, isl_int value) { - if (!bmap) - return NULL; - isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error); + if (isl_basic_map_check_range(bmap, type, pos, 1) < 0) + return isl_basic_map_free(bmap); return isl_basic_map_fix_pos(bmap, isl_basic_map_offset(bmap, type) + pos, value); -error: - isl_basic_map_free(bmap); - return NULL; } /* Fix the value of the variable at position "pos" of type "type" of "bmap" @@ -5666,9 +5865,8 @@ __isl_give isl_basic_map *isl_basic_map_fix_val(__isl_take isl_basic_map *bmap, if (!isl_val_is_int(v)) isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, "expecting integer value", goto error); - if (pos >= isl_basic_map_dim(bmap, type)) - isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, - "index out of bounds", goto error); + if (isl_basic_map_check_range(bmap, type, pos, 1) < 0) + goto error; pos += isl_basic_map_offset(bmap, type); bmap = isl_basic_map_fix_pos(bmap, pos, v->n); isl_val_free(v); @@ -5883,9 +6081,8 @@ static __isl_give isl_basic_map *basic_map_bound_si( { int j; - if (!bmap) - return NULL; - isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error); + if (isl_basic_map_check_range(bmap, type, pos, 1) < 0) + return isl_basic_map_free(bmap); pos += isl_basic_map_offset(bmap, type); bmap = isl_basic_map_cow(bmap); bmap = isl_basic_map_extend_constraints(bmap, 0, 1); @@ -6000,11 +6197,8 @@ static __isl_give isl_basic_map *basic_map_bound( { int j; - if (!bmap) - return NULL; - if (pos >= isl_basic_map_dim(bmap, type)) - isl_die(bmap->ctx, isl_error_invalid, - "index out of bounds", goto error); + if (isl_basic_map_check_range(bmap, type, pos, 1) < 0) + return isl_basic_map_free(bmap); pos += isl_basic_map_offset(bmap, type); bmap = isl_basic_map_cow(bmap); bmap = isl_basic_map_extend_constraints(bmap, 0, 1); @@ -6983,11 +7177,8 @@ __isl_give isl_basic_map *isl_basic_map_mark_div_unknown( isl_bool isl_basic_map_div_is_marked_unknown(__isl_keep isl_basic_map *bmap, int div) { - if (!bmap) + if (isl_basic_map_check_range(bmap, isl_dim_div, div, 1) < 0) return isl_bool_error; - if (div < 0 || div >= isl_basic_map_dim(bmap, isl_dim_div)) - isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, - "position out of bounds", return isl_bool_error); return isl_int_is_zero(bmap->div[div][0]); } @@ -10389,12 +10580,9 @@ static isl_bool basic_map_dim_is_bounded(__isl_keep isl_basic_map *bmap, { int i; - if (!bmap) + if (isl_basic_map_check_range(bmap, type, pos, 1) < 0) return isl_bool_error; - isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), - return isl_bool_error); - pos += isl_basic_map_offset(bmap, type); for (i = 0; i < bmap->n_div; ++i) { @@ -13178,6 +13366,69 @@ __isl_give isl_set *isl_set_preimage_multi_pw_aff(__isl_take isl_set *set, return isl_map_preimage_multi_pw_aff(set, isl_dim_set, mpa); } +/* Are the "n" "coefficients" starting at "first" of the integer division + * expressions at position "pos1" in "bmap1" and "pos2" in "bmap2" equal + * to each other? + * The "coefficient" at position 0 is the denominator. + * The "coefficient" at position 1 is the constant term. + */ +isl_bool isl_basic_map_equal_div_expr_part(__isl_keep isl_basic_map *bmap1, + int pos1, __isl_keep isl_basic_map *bmap2, int pos2, + unsigned first, unsigned n) +{ + if (isl_basic_map_check_range(bmap1, isl_dim_div, pos1, 1) < 0) + return isl_bool_error; + if (isl_basic_map_check_range(bmap2, isl_dim_div, pos2, 1) < 0) + return isl_bool_error; + return isl_seq_eq(bmap1->div[pos1] + first, + bmap2->div[pos2] + first, n); +} + +/* Are the integer division expressions at position "pos1" in "bmap1" and + * "pos2" in "bmap2" equal to each other, except that the constant terms + * are different? + */ +isl_bool isl_basic_map_equal_div_expr_except_constant( + __isl_keep isl_basic_map *bmap1, int pos1, + __isl_keep isl_basic_map *bmap2, int pos2) +{ + isl_bool equal; + unsigned total; + + if (!bmap1 || !bmap2) + return isl_bool_error; + total = isl_basic_map_total_dim(bmap1); + if (total != isl_basic_map_total_dim(bmap2)) + isl_die(isl_basic_map_get_ctx(bmap1), isl_error_invalid, + "incomparable div expressions", return isl_bool_error); + equal = isl_basic_map_equal_div_expr_part(bmap1, pos1, bmap2, pos2, + 0, 1); + if (equal < 0 || !equal) + return equal; + equal = isl_basic_map_equal_div_expr_part(bmap1, pos1, bmap2, pos2, + 1, 1); + if (equal < 0 || equal) + return isl_bool_not(equal); + return isl_basic_map_equal_div_expr_part(bmap1, pos1, bmap2, pos2, + 2, total); +} + +/* Replace the numerator of the constant term of the integer division + * expression at position "div" in "bmap" by "value". + * The caller guarantees that this does not change the meaning + * of the input. + */ +__isl_give isl_basic_map *isl_basic_map_set_div_expr_constant_num_si_inplace( + __isl_take isl_basic_map *bmap, int div, int value) +{ + if (isl_basic_map_check_range(bmap, isl_dim_div, div, 1) < 0) + return isl_basic_map_free(bmap); + + isl_int_set_si(bmap->div[div][1], value); + + return bmap; +} + /* Is the point "inner" internal to inequality constraint "ineq" * of "bset"? * The point is considered to be internal to the inequality constraint, diff --git a/lib/External/isl/isl_map_private.h b/lib/External/isl/isl_map_private.h index 882faa4a..db39f43f 100644 --- a/lib/External/isl/isl_map_private.h +++ b/lib/External/isl/isl_map_private.h @@ -528,4 +528,13 @@ int isl_basic_set_count_upto(__isl_keep isl_basic_set *bset, isl_int max, isl_int *count); int isl_set_count_upto(__isl_keep isl_set *set, isl_int max, isl_int *count); +isl_bool isl_basic_map_equal_div_expr_part(__isl_keep isl_basic_map *bmap1, + int pos1, __isl_keep isl_basic_map *bmap2, int pos2, + unsigned first, unsigned n); +isl_bool isl_basic_map_equal_div_expr_except_constant( + __isl_keep isl_basic_map *bmap1, int pos1, + __isl_keep isl_basic_map *bmap2, int pos2); +__isl_give isl_basic_map *isl_basic_map_set_div_expr_constant_num_si_inplace( + __isl_take isl_basic_map *bmap, int div, int value); + #endif diff --git a/lib/External/isl/isl_map_simplify.c b/lib/External/isl/isl_map_simplify.c index 7acd2a7a..d47b59e5 100644 --- a/lib/External/isl/isl_map_simplify.c +++ b/lib/External/isl/isl_map_simplify.c @@ -5304,6 +5304,8 @@ __isl_give isl_basic_map *isl_basic_map_shift_div( int i; unsigned total; + if (isl_int_is_zero(shift)) + return bmap; if (!bmap) return NULL; diff --git a/lib/External/isl/isl_test.c b/lib/External/isl/isl_test.c index 42a5b63c..905032e6 100644 --- a/lib/External/isl/isl_test.c +++ b/lib/External/isl/isl_test.c @@ -1850,6 +1850,10 @@ struct { "9*floor((-4a + 2c)/9) <= -3 - 4a + 2c) or " "(exists (e0 = floor((-16 + 2c)/9): a = 4 and " "b = 3 and 9e0 <= -19 + 2c)) }" }, + { 1, "{ [a, b, c] : (b = -1 + a and 0 < a <= 3 and " + "9*floor((-4a + 2c)/9) <= -3 - 4a + 2c) or " + "(a = 4 and b = 3 and " + "9*floor((-16 + 2c)/9) <= -19 + 2c) }" }, { 0, "{ [a, b, c] : (b <= 2 and b <= -2 + a) or " "(b = -1 + a and 0 < a <= 3 and " "9*floor((-4a + 2c)/9) <= -3 - 4a + 2c) or " diff --git a/lib/External/isl/isl_val_private.h b/lib/External/isl/isl_val_private.h index ec1076dd..0757dcde 100644 --- a/lib/External/isl/isl_val_private.h +++ b/lib/External/isl/isl_val_private.h @@ -34,6 +34,8 @@ __isl_give isl_val *isl_val_rat_from_isl_int(isl_ctx *ctx, isl_int n, isl_int d); __isl_give isl_val *isl_val_cow(__isl_take isl_val *val); +int isl_val_get_num_isl_int(__isl_keep isl_val *v, isl_int *n); + int isl_val_involves_dims(__isl_keep isl_val *v, enum isl_dim_type type, unsigned first, unsigned n); __isl_give isl_val *isl_val_insert_dims(__isl_take isl_val *v, diff --git a/test/ScopInfo/switch-3.ll b/test/ScopInfo/switch-3.ll index 1f8bd01d..36d9ce18 100644 --- a/test/ScopInfo/switch-3.ll +++ b/test/ScopInfo/switch-3.ll @@ -29,7 +29,7 @@ ; CHECK-NEXT: [N] -> { Stmt_sw_bb[i0] -> MemRef_A[i0] }; ; CHECK-NEXT: Stmt_sw_bb_1 ; CHECK-NEXT: Domain := -; CHECK-NEXT: [N] -> { Stmt_sw_bb_1[i0] : 0 <= i0 < N and 4*floor((2 + i0)/4) <= i0 }; +; CHECK-NEXT: [N] -> { Stmt_sw_bb_1[i0] : 0 <= i0 < N and 4*floor((i0)/4) >= -1 + i0 }; ; CHECK-NEXT: Schedule := ; CHECK-NEXT: [N] -> { Stmt_sw_bb_1[i0] -> [i0, 3] }; ; CHECK-NEXT: ReadAccess := [Reduction Type: +] [Scalar: 0] -- 2.11.4.GIT