## File: isl_ast_build_expr.c

package info (click to toggle)
isl 0.20-2
 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492 /* * Copyright 2012-2014 Ecole Normale Superieure * Copyright 2014 INRIA Rocquencourt * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt, * B.P. 105 - 78153 Le Chesnay, France */ #include #include #include #include #include #include #include #include #include /* Compute the "opposite" of the (numerator of the) argument of a div * with denominator "d". * * In particular, compute * * -aff + (d - 1) */ static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff, __isl_take isl_val *d) { aff = isl_aff_neg(aff); aff = isl_aff_add_constant_val(aff, d); aff = isl_aff_add_constant_si(aff, -1); return aff; } /* Internal data structure used inside isl_ast_expr_add_term. * The domain of "build" is used to simplify the expressions. * "build" needs to be set by the caller of isl_ast_expr_add_term. * "cst" is the constant term of the expression in which the added term * appears. It may be modified by isl_ast_expr_add_term. * * "v" is the coefficient of the term that is being constructed and * is set internally by isl_ast_expr_add_term. */ struct isl_ast_add_term_data { isl_ast_build *build; isl_val *cst; isl_val *v; }; /* Given the numerator "aff" of the argument of an integer division * with denominator "d", check if it can be made non-negative over * data->build->domain by stealing part of the constant term of * the expression in which the integer division appears. * * In particular, the outer expression is of the form * * v * floor(aff/d) + cst * * We already know that "aff" itself may attain negative values. * Here we check if aff + d*floor(cst/v) is non-negative, such * that we could rewrite the expression to * * v * floor((aff + d*floor(cst/v))/d) + cst - v*floor(cst/v) * * Note that aff + d*floor(cst/v) can only possibly be non-negative * if data->cst and data->v have the same sign. * Similarly, if floor(cst/v) is zero, then there is no point in * checking again. */ static int is_non_neg_after_stealing(__isl_keep isl_aff *aff, __isl_keep isl_val *d, struct isl_ast_add_term_data *data) { isl_aff *shifted; isl_val *shift; int is_zero; int non_neg; if (isl_val_sgn(data->cst) != isl_val_sgn(data->v)) return 0; shift = isl_val_div(isl_val_copy(data->cst), isl_val_copy(data->v)); shift = isl_val_floor(shift); is_zero = isl_val_is_zero(shift); if (is_zero < 0 || is_zero) { isl_val_free(shift); return is_zero < 0 ? -1 : 0; } shift = isl_val_mul(shift, isl_val_copy(d)); shifted = isl_aff_copy(aff); shifted = isl_aff_add_constant_val(shifted, shift); non_neg = isl_ast_build_aff_is_nonneg(data->build, shifted); isl_aff_free(shifted); return non_neg; } /* Given the numerator "aff' of the argument of an integer division * with denominator "d", steal part of the constant term of * the expression in which the integer division appears to make it * non-negative over data->build->domain. * * In particular, the outer expression is of the form * * v * floor(aff/d) + cst * * We know that "aff" itself may attain negative values, * but that aff + d*floor(cst/v) is non-negative. * Find the minimal positive value that we need to add to "aff" * to make it positive and adjust data->cst accordingly. * That is, compute the minimal value "m" of "aff" over * data->build->domain and take * * s = ceil(m/d) * * such that * * aff + d * s >= 0 * * and rewrite the expression to * * v * floor((aff + s*d)/d) + (cst - v*s) */ static __isl_give isl_aff *steal_from_cst(__isl_take isl_aff *aff, __isl_keep isl_val *d, struct isl_ast_add_term_data *data) { isl_set *domain; isl_val *shift, *t; domain = isl_ast_build_get_domain(data->build); shift = isl_set_min_val(domain, aff); isl_set_free(domain); shift = isl_val_neg(shift); shift = isl_val_div(shift, isl_val_copy(d)); shift = isl_val_ceil(shift); t = isl_val_copy(shift); t = isl_val_mul(t, isl_val_copy(data->v)); data->cst = isl_val_sub(data->cst, t); shift = isl_val_mul(shift, isl_val_copy(d)); return isl_aff_add_constant_val(aff, shift); } /* Create an isl_ast_expr evaluating the div at position "pos" in "ls". * The result is simplified in terms of data->build->domain. * This function may change (the sign of) data->v. * * "ls" is known to be non-NULL. * * Let the div be of the form floor(e/d). * If the ast_build_prefer_pdiv option is set then we check if "e" * is non-negative, so that we can generate * * (pdiv_q, expr(e), expr(d)) * * instead of * * (fdiv_q, expr(e), expr(d)) * * If the ast_build_prefer_pdiv option is set and * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative. * If so, we can rewrite * * floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d) * * and still use pdiv_q, while changing the sign of data->v. * * Otherwise, we check if * * e + d*floor(cst/v) * * is non-negative and if so, replace floor(e/d) by * * floor((e + s*d)/d) - s * * with s the minimal shift that makes the argument non-negative. */ static __isl_give isl_ast_expr *var_div(struct isl_ast_add_term_data *data, __isl_keep isl_local_space *ls, int pos) { isl_ctx *ctx = isl_local_space_get_ctx(ls); isl_aff *aff; isl_ast_expr *num, *den; isl_val *d; enum isl_ast_op_type type; aff = isl_local_space_get_div(ls, pos); d = isl_aff_get_denominator_val(aff); aff = isl_aff_scale_val(aff, isl_val_copy(d)); den = isl_ast_expr_from_val(isl_val_copy(d)); type = isl_ast_op_fdiv_q; if (isl_options_get_ast_build_prefer_pdiv(ctx)) { int non_neg = isl_ast_build_aff_is_nonneg(data->build, aff); if (non_neg >= 0 && !non_neg) { isl_aff *opp = oppose_div_arg(isl_aff_copy(aff), isl_val_copy(d)); non_neg = isl_ast_build_aff_is_nonneg(data->build, opp); if (non_neg >= 0 && non_neg) { data->v = isl_val_neg(data->v); isl_aff_free(aff); aff = opp; } else isl_aff_free(opp); } if (non_neg >= 0 && !non_neg) { non_neg = is_non_neg_after_stealing(aff, d, data); if (non_neg >= 0 && non_neg) aff = steal_from_cst(aff, d, data); } if (non_neg < 0) aff = isl_aff_free(aff); else if (non_neg) type = isl_ast_op_pdiv_q; } isl_val_free(d); num = isl_ast_expr_from_aff(aff, data->build); return isl_ast_expr_alloc_binary(type, num, den); } /* Create an isl_ast_expr evaluating the specified dimension of "ls". * The result is simplified in terms of data->build->domain. * This function may change (the sign of) data->v. * * The isl_ast_expr is constructed based on the type of the dimension. * - divs are constructed by var_div * - set variables are constructed from the iterator isl_ids in data->build * - parameters are constructed from the isl_ids in "ls" */ static __isl_give isl_ast_expr *var(struct isl_ast_add_term_data *data, __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos) { isl_ctx *ctx = isl_local_space_get_ctx(ls); isl_id *id; if (type == isl_dim_div) return var_div(data, ls, pos); if (type == isl_dim_set) { id = isl_ast_build_get_iterator_id(data->build, pos); return isl_ast_expr_from_id(id); } if (!isl_local_space_has_dim_id(ls, type, pos)) isl_die(ctx, isl_error_internal, "unnamed dimension", return NULL); id = isl_local_space_get_dim_id(ls, type, pos); return isl_ast_expr_from_id(id); } /* Does "expr" represent the zero integer? */ static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr) { if (!expr) return -1; if (expr->type != isl_ast_expr_int) return 0; return isl_val_is_zero(expr->u.v); } /* Create an expression representing the sum of "expr1" and "expr2", * provided neither of the two expressions is identically zero. */ static __isl_give isl_ast_expr *ast_expr_add(__isl_take isl_ast_expr *expr1, __isl_take isl_ast_expr *expr2) { if (!expr1 || !expr2) goto error; if (ast_expr_is_zero(expr1)) { isl_ast_expr_free(expr1); return expr2; } if (ast_expr_is_zero(expr2)) { isl_ast_expr_free(expr2); return expr1; } return isl_ast_expr_add(expr1, expr2); error: isl_ast_expr_free(expr1); isl_ast_expr_free(expr2); return NULL; } /* Subtract expr2 from expr1. * * If expr2 is zero, we simply return expr1. * If expr1 is zero, we return * * (isl_ast_op_minus, expr2) * * Otherwise, we return * * (isl_ast_op_sub, expr1, expr2) */ static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1, __isl_take isl_ast_expr *expr2) { if (!expr1 || !expr2) goto error; if (ast_expr_is_zero(expr2)) { isl_ast_expr_free(expr2); return expr1; } if (ast_expr_is_zero(expr1)) { isl_ast_expr_free(expr1); return isl_ast_expr_neg(expr2); } return isl_ast_expr_sub(expr1, expr2); error: isl_ast_expr_free(expr1); isl_ast_expr_free(expr2); return NULL; } /* Return an isl_ast_expr that represents * * v * (aff mod d) * * v is assumed to be non-negative. * The result is simplified in terms of build->domain. */ static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v, __isl_keep isl_aff *aff, __isl_keep isl_val *d, __isl_keep isl_ast_build *build) { isl_ast_expr *expr; isl_ast_expr *c; if (!aff) return NULL; expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build); c = isl_ast_expr_from_val(isl_val_copy(d)); expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr, c); if (!isl_val_is_one(v)) { c = isl_ast_expr_from_val(isl_val_copy(v)); expr = isl_ast_expr_mul(c, expr); } return expr; } /* Create an isl_ast_expr that scales "expr" by "v". * * If v is 1, we simply return expr. * If v is -1, we return * * (isl_ast_op_minus, expr) * * Otherwise, we return * * (isl_ast_op_mul, expr(v), expr) */ static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr, __isl_take isl_val *v) { isl_ast_expr *c; if (!expr || !v) goto error; if (isl_val_is_one(v)) { isl_val_free(v); return expr; } if (isl_val_is_negone(v)) { isl_val_free(v); expr = isl_ast_expr_neg(expr); } else { c = isl_ast_expr_from_val(v); expr = isl_ast_expr_mul(c, expr); } return expr; error: isl_val_free(v); isl_ast_expr_free(expr); return NULL; } /* Add an expression for "*v" times the specified dimension of "ls" * to expr. * If the dimension is an integer division, then this function * may modify data->cst in order to make the numerator non-negative. * The result is simplified in terms of data->build->domain. * * Let e be the expression for the specified dimension, * multiplied by the absolute value of "*v". * If "*v" is negative, we create * * (isl_ast_op_sub, expr, e) * * except when expr is trivially zero, in which case we create * * (isl_ast_op_minus, e) * * instead. * * If "*v" is positive, we simply create * * (isl_ast_op_add, expr, e) * */ static __isl_give isl_ast_expr *isl_ast_expr_add_term( __isl_take isl_ast_expr *expr, __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos, __isl_take isl_val *v, struct isl_ast_add_term_data *data) { isl_ast_expr *term; if (!expr) return NULL; data->v = v; term = var(data, ls, type, pos); v = data->v; if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) { v = isl_val_neg(v); term = scale(term, v); return ast_expr_sub(expr, term); } else { term = scale(term, v); return ast_expr_add(expr, term); } } /* Add an expression for "v" to expr. */ static __isl_give isl_ast_expr *isl_ast_expr_add_int( __isl_take isl_ast_expr *expr, __isl_take isl_val *v) { isl_ast_expr *expr_int; if (!expr || !v) goto error; if (isl_val_is_zero(v)) { isl_val_free(v); return expr; } if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) { v = isl_val_neg(v); expr_int = isl_ast_expr_from_val(v); return ast_expr_sub(expr, expr_int); } else { expr_int = isl_ast_expr_from_val(v); return ast_expr_add(expr, expr_int); } error: isl_ast_expr_free(expr); isl_val_free(v); return NULL; } /* Internal data structure used inside extract_modulos. * * If any modulo expressions are detected in "aff", then the * expression is removed from "aff" and added to either "pos" or "neg" * depending on the sign of the coefficient of the modulo expression * inside "aff". * * "add" is an expression that needs to be added to "aff" at the end of * the computation. It is NULL as long as no modulos have been extracted. * * "i" is the position in "aff" of the div under investigation * "v" is the coefficient in "aff" of the div * "div" is the argument of the div, with the denominator removed * "d" is the original denominator of the argument of the div * * "nonneg" is an affine expression that is non-negative over "build" * and that can be used to extract a modulo expression from "div". * In particular, if "sign" is 1, then the coefficients of "nonneg" * are equal to those of "div" modulo "d". If "sign" is -1, then * the coefficients of "nonneg" are opposite to those of "div" modulo "d". * If "sign" is 0, then no such affine expression has been found (yet). */ struct isl_extract_mod_data { isl_ast_build *build; isl_aff *aff; isl_ast_expr *pos; isl_ast_expr *neg; isl_aff *add; int i; isl_val *v; isl_val *d; isl_aff *div; isl_aff *nonneg; int sign; }; /* Given that data->v * div_i in data->aff is equal to * * f * (term - (arg mod d)) * * with data->d * f = data->v, add * * f * term * * to data->add and * * abs(f) * (arg mod d) * * to data->neg or data->pos depending on the sign of -f. */ static int extract_term_and_mod(struct isl_extract_mod_data *data, __isl_take isl_aff *term, __isl_take isl_aff *arg) { isl_ast_expr *expr; int s; data->v = isl_val_div(data->v, isl_val_copy(data->d)); s = isl_val_sgn(data->v); data->v = isl_val_abs(data->v); expr = isl_ast_expr_mod(data->v, arg, data->d, data->build); isl_aff_free(arg); if (s > 0) data->neg = ast_expr_add(data->neg, expr); else data->pos = ast_expr_add(data->pos, expr); data->aff = isl_aff_set_coefficient_si(data->aff, isl_dim_div, data->i, 0); if (s < 0) data->v = isl_val_neg(data->v); term = isl_aff_scale_val(term, isl_val_copy(data->v)); if (!data->add) data->add = term; else data->add = isl_aff_add(data->add, term); if (!data->add) return -1; return 0; } /* Given that data->v * div_i in data->aff is of the form * * f * d * floor(div/d) * * with div nonnegative on data->build, rewrite it as * * f * (div - (div mod d)) = f * div - f * (div mod d) * * and add * * f * div * * to data->add and * * abs(f) * (div mod d) * * to data->neg or data->pos depending on the sign of -f. */ static int extract_mod(struct isl_extract_mod_data *data) { return extract_term_and_mod(data, isl_aff_copy(data->div), isl_aff_copy(data->div)); } /* Given that data->v * div_i in data->aff is of the form * * f * d * floor(div/d) (1) * * check if div is non-negative on data->build and, if so, * extract the corresponding modulo from data->aff. * If not, then check if * * -div + d - 1 * * is non-negative on data->build. If so, replace (1) by * * -f * d * floor((-div + d - 1)/d) * * and extract the corresponding modulo from data->aff. * * This function may modify data->div. */ static int extract_nonneg_mod(struct isl_extract_mod_data *data) { int mod; mod = isl_ast_build_aff_is_nonneg(data->build, data->div); if (mod < 0) goto error; if (mod) return extract_mod(data); data->div = oppose_div_arg(data->div, isl_val_copy(data->d)); mod = isl_ast_build_aff_is_nonneg(data->build, data->div); if (mod < 0) goto error; if (mod) { data->v = isl_val_neg(data->v); return extract_mod(data); } return 0; error: data->aff = isl_aff_free(data->aff); return -1; } /* Is the affine expression of constraint "c" "simpler" than data->nonneg * for use in extracting a modulo expression? * * We currently only consider the constant term of the affine expression. * In particular, we prefer the affine expression with the smallest constant * term. * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0, * then we would pick x >= 0 * * More detailed heuristics could be used if it turns out that there is a need. */ static int mod_constraint_is_simpler(struct isl_extract_mod_data *data, __isl_keep isl_constraint *c) { isl_val *v1, *v2; int simpler; if (!data->nonneg) return 1; v1 = isl_val_abs(isl_constraint_get_constant_val(c)); v2 = isl_val_abs(isl_aff_get_constant_val(data->nonneg)); simpler = isl_val_lt(v1, v2); isl_val_free(v1); isl_val_free(v2); return simpler; } /* Check if the coefficients of "c" are either equal or opposite to those * of data->div modulo data->d. If so, and if "c" is "simpler" than * data->nonneg, then replace data->nonneg by the affine expression of "c" * and set data->sign accordingly. * * Both "c" and data->div are assumed not to involve any integer divisions. * * Before we start the actual comparison, we first quickly check if * "c" and data->div have the same non-zero coefficients. * If not, then we assume that "c" is not of the desired form. * Note that while the coefficients of data->div can be reasonably expected * not to involve any coefficients that are multiples of d, "c" may * very well involve such coefficients. This means that we may actually * miss some cases. * * If the constant term is "too large", then the constraint is rejected, * where "too large" is fairly arbitrarily set to 1 << 15. * We do this to avoid picking up constraints that bound a variable * by a very large number, say the largest or smallest possible * variable in the representation of some integer type. */ static isl_stat check_parallel_or_opposite(__isl_take isl_constraint *c, void *user) { struct isl_extract_mod_data *data = user; enum isl_dim_type c_type[2] = { isl_dim_param, isl_dim_set }; enum isl_dim_type a_type[2] = { isl_dim_param, isl_dim_in }; int i, t; int n[2]; int parallel = 1, opposite = 1; for (t = 0; t < 2; ++t) { n[t] = isl_constraint_dim(c, c_type[t]); for (i = 0; i < n[t]; ++i) { int a, b; a = isl_constraint_involves_dims(c, c_type[t], i, 1); b = isl_aff_involves_dims(data->div, a_type[t], i, 1); if (a != b) parallel = opposite = 0; } } if (parallel || opposite) { isl_val *v; v = isl_val_abs(isl_constraint_get_constant_val(c)); if (isl_val_cmp_si(v, 1 << 15) > 0) parallel = opposite = 0; isl_val_free(v); } for (t = 0; t < 2; ++t) { for (i = 0; i < n[t]; ++i) { isl_val *v1, *v2; if (!parallel && !opposite) break; v1 = isl_constraint_get_coefficient_val(c, c_type[t], i); v2 = isl_aff_get_coefficient_val(data->div, a_type[t], i); if (parallel) { v1 = isl_val_sub(v1, isl_val_copy(v2)); parallel = isl_val_is_divisible_by(v1, data->d); v1 = isl_val_add(v1, isl_val_copy(v2)); } if (opposite) { v1 = isl_val_add(v1, isl_val_copy(v2)); opposite = isl_val_is_divisible_by(v1, data->d); } isl_val_free(v1); isl_val_free(v2); } } if ((parallel || opposite) && mod_constraint_is_simpler(data, c)) { isl_aff_free(data->nonneg); data->nonneg = isl_constraint_get_aff(c); data->sign = parallel ? 1 : -1; } isl_constraint_free(c); if (data->sign != 0 && data->nonneg == NULL) return isl_stat_error; return isl_stat_ok; } /* Given that data->v * div_i in data->aff is of the form * * f * d * floor(div/d) (1) * * see if we can find an expression div' that is non-negative over data->build * and that is related to div through * * div' = div + d * e * * or * * div' = -div + d - 1 + d * e * * with e some affine expression. * If so, we write (1) as * * f * div + f * (div' mod d) * * or * * -f * (-div + d - 1) - f * (div' mod d) * * exploiting (in the second case) the fact that * * f * d * floor(div/d) = -f * d * floor((-div + d - 1)/d) * * * We first try to find an appropriate expression for div' * from the constraints of data->build->domain (which is therefore * guaranteed to be non-negative on data->build), where we remove * any integer divisions from the constraints and skip this step * if "div" itself involves any integer divisions. * If we cannot find an appropriate expression this way, then * we pass control to extract_nonneg_mod where check * if div or "-div + d -1" themselves happen to be * non-negative on data->build. * * While looking for an appropriate constraint in data->build->domain, * we ignore the constant term, so after finding such a constraint, * we still need to fix up the constant term. * In particular, if a is the constant term of "div" * (or d - 1 - the constant term of "div" if data->sign < 0) * and b is the constant term of the constraint, then we need to find * a non-negative constant c such that * * b + c \equiv a mod d * * We therefore take * * c = (a - b) mod d * * and add it to b to obtain the constant term of div'. * If this constant term is "too negative", then we add an appropriate * multiple of d to make it positive. * * * Note that the above is a only a very simple heuristic for finding an * appropriate expression. We could try a bit harder by also considering * sums of constraints that involve disjoint sets of variables or * we could consider arbitrary linear combinations of constraints, * although that could potentially be much more expensive as it involves * the solution of an LP problem. * * In particular, if v_i is a column vector representing constraint i, * w represents div and e_i is the i-th unit vector, then we are looking * for a solution of the constraints * * \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i * * with \lambda_i >= 0 and alpha_i of unrestricted sign. * If we are not just interested in a non-negative expression, but * also in one with a minimal range, then we don't just want * c = \sum_i lambda_i v_i to be non-negative over the domain, * but also beta - c = \sum_i mu_i v_i, where beta is a scalar * that we want to minimize and we now also have to take into account * the constant terms of the constraints. * Alternatively, we could first compute the dual of the domain * and plug in the constraints on the coefficients. */ static int try_extract_mod(struct isl_extract_mod_data *data) { isl_basic_set *hull; isl_val *v1, *v2; int r, n; if (!data->build) goto error; n = isl_aff_dim(data->div, isl_dim_div); if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n)) return extract_nonneg_mod(data); hull = isl_set_simple_hull(isl_set_copy(data->build->domain)); hull = isl_basic_set_remove_divs(hull); data->sign = 0; data->nonneg = NULL; r = isl_basic_set_foreach_constraint(hull, &check_parallel_or_opposite, data); isl_basic_set_free(hull); if (!data->sign || r < 0) { isl_aff_free(data->nonneg); if (r < 0) goto error; return extract_nonneg_mod(data); } v1 = isl_aff_get_constant_val(data->div); v2 = isl_aff_get_constant_val(data->nonneg); if (data->sign < 0) { v1 = isl_val_neg(v1); v1 = isl_val_add(v1, isl_val_copy(data->d)); v1 = isl_val_sub_ui(v1, 1); } v1 = isl_val_sub(v1, isl_val_copy(v2)); v1 = isl_val_mod(v1, isl_val_copy(data->d)); v1 = isl_val_add(v1, v2); v2 = isl_val_div(isl_val_copy(v1), isl_val_copy(data->d)); v2 = isl_val_ceil(v2); if (isl_val_is_neg(v2)) { v2 = isl_val_mul(v2, isl_val_copy(data->d)); v1 = isl_val_sub(v1, isl_val_copy(v2)); } data->nonneg = isl_aff_set_constant_val(data->nonneg, v1); isl_val_free(v2); if (data->sign < 0) { data->div = oppose_div_arg(data->div, isl_val_copy(data->d)); data->v = isl_val_neg(data->v); } return extract_term_and_mod(data, isl_aff_copy(data->div), data->nonneg); error: data->aff = isl_aff_free(data->aff); return -1; } /* Check if "data->aff" involves any (implicit) modulo computations based * on div "data->i". * If so, remove them from aff and add expressions corresponding * to those modulo computations to data->pos and/or data->neg. * * "aff" is assumed to be an integer affine expression. * * In particular, check if (v * div_j) is of the form * * f * m * floor(a / m) * * and, if so, rewrite it as * * f * (a - (a mod m)) = f * a - f * (a mod m) * * and extract out -f * (a mod m). * In particular, if f > 0, we add (f * (a mod m)) to *neg. * If f < 0, we add ((-f) * (a mod m)) to *pos. * * Note that in order to represent "a mod m" as * * (isl_ast_op_pdiv_r, a, m) * * we need to make sure that a is non-negative. * If not, we check if "-a + m - 1" is non-negative. * If so, we can rewrite * * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m) * * and still extract a modulo. */ static int extract_modulo(struct isl_extract_mod_data *data) { data->div = isl_aff_get_div(data->aff, data->i); data->d = isl_aff_get_denominator_val(data->div); if (isl_val_is_divisible_by(data->v, data->d)) { data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d)); if (try_extract_mod(data) < 0) data->aff = isl_aff_free(data->aff); } isl_aff_free(data->div); isl_val_free(data->d); return 0; } /* Check if "aff" involves any (implicit) modulo computations. * If so, remove them from aff and add expressions corresponding * to those modulo computations to *pos and/or *neg. * We only do this if the option ast_build_prefer_pdiv is set. * * "aff" is assumed to be an integer affine expression. * * A modulo expression is of the form * * a mod m = a - m * floor(a / m) * * To detect them in aff, we look for terms of the form * * f * m * floor(a / m) * * rewrite them as * * f * (a - (a mod m)) = f * a - f * (a mod m) * * and extract out -f * (a mod m). * In particular, if f > 0, we add (f * (a mod m)) to *neg. * If f < 0, we add ((-f) * (a mod m)) to *pos. */ static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff, __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg, __isl_keep isl_ast_build *build) { struct isl_extract_mod_data data = { build, aff, *pos, *neg }; isl_ctx *ctx; int n; if (!aff) return NULL; ctx = isl_aff_get_ctx(aff); if (!isl_options_get_ast_build_prefer_pdiv(ctx)) return aff; n = isl_aff_dim(data.aff, isl_dim_div); for (data.i = 0; data.i < n; ++data.i) { data.v = isl_aff_get_coefficient_val(data.aff, isl_dim_div, data.i); if (!data.v) return isl_aff_free(aff); if (isl_val_is_zero(data.v) || isl_val_is_one(data.v) || isl_val_is_negone(data.v)) { isl_val_free(data.v); continue; } if (extract_modulo(&data) < 0) data.aff = isl_aff_free(data.aff); isl_val_free(data.v); if (!data.aff) break; } if (data.add) data.aff = isl_aff_add(data.aff, data.add); *pos = data.pos; *neg = data.neg; return data.aff; } /* Check if aff involves any non-integer coefficients. * If so, split aff into * * aff = aff1 + (aff2 / d) * * with both aff1 and aff2 having only integer coefficients. * Return aff1 and add (aff2 / d) to *expr. */ static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff, __isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build) { int i, j, n; isl_aff *rat = NULL; isl_local_space *ls = NULL; isl_ast_expr *rat_expr; isl_val *v, *d; enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div }; enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div }; if (!aff) return NULL; d = isl_aff_get_denominator_val(aff); if (!d) goto error; if (isl_val_is_one(d)) { isl_val_free(d); return aff; } aff = isl_aff_scale_val(aff, isl_val_copy(d)); ls = isl_aff_get_domain_local_space(aff); rat = isl_aff_zero_on_domain(isl_local_space_copy(ls)); for (i = 0; i < 3; ++i) { n = isl_aff_dim(aff, t[i]); for (j = 0; j < n; ++j) { isl_aff *rat_j; v = isl_aff_get_coefficient_val(aff, t[i], j); if (!v) goto error; if (isl_val_is_divisible_by(v, d)) { isl_val_free(v); continue; } rat_j = isl_aff_var_on_domain(isl_local_space_copy(ls), l[i], j); rat_j = isl_aff_scale_val(rat_j, v); rat = isl_aff_add(rat, rat_j); } } v = isl_aff_get_constant_val(aff); if (isl_val_is_divisible_by(v, d)) { isl_val_free(v); } else { isl_aff *rat_0; rat_0 = isl_aff_val_on_domain(isl_local_space_copy(ls), v); rat = isl_aff_add(rat, rat_0); } isl_local_space_free(ls); aff = isl_aff_sub(aff, isl_aff_copy(rat)); aff = isl_aff_scale_down_val(aff, isl_val_copy(d)); rat_expr = isl_ast_expr_from_aff(rat, build); rat_expr = isl_ast_expr_div(rat_expr, isl_ast_expr_from_val(d)); *expr = ast_expr_add(*expr, rat_expr); return aff; error: isl_aff_free(rat); isl_local_space_free(ls); isl_aff_free(aff); isl_val_free(d); return NULL; } /* Construct an isl_ast_expr that evaluates the affine expression "aff", * The result is simplified in terms of build->domain. * * We first extract hidden modulo computations from the affine expression * and then add terms for each variable with a non-zero coefficient. * Finally, if the affine expression has a non-trivial denominator, * we divide the resulting isl_ast_expr by this denominator. */ __isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff, __isl_keep isl_ast_build *build) { int i, j; int n; isl_val *v; isl_ctx *ctx = isl_aff_get_ctx(aff); isl_ast_expr *expr, *expr_neg; enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div }; enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div }; isl_local_space *ls; struct isl_ast_add_term_data data; if (!aff) return NULL; expr = isl_ast_expr_alloc_int_si(ctx, 0); expr_neg = isl_ast_expr_alloc_int_si(ctx, 0); aff = extract_rational(aff, &expr, build); aff = extract_modulos(aff, &expr, &expr_neg, build); expr = ast_expr_sub(expr, expr_neg); ls = isl_aff_get_domain_local_space(aff); data.build = build; data.cst = isl_aff_get_constant_val(aff); for (i = 0; i < 3; ++i) { n = isl_aff_dim(aff, t[i]); for (j = 0; j < n; ++j) { v = isl_aff_get_coefficient_val(aff, t[i], j); if (!v) expr = isl_ast_expr_free(expr); if (isl_val_is_zero(v)) { isl_val_free(v); continue; } expr = isl_ast_expr_add_term(expr, ls, l[i], j, v, &data); } } expr = isl_ast_expr_add_int(expr, data.cst); isl_local_space_free(ls); isl_aff_free(aff); return expr; } /* Add terms to "expr" for each variable in "aff" with a coefficient * with sign equal to "sign". * The result is simplified in terms of data->build->domain. */ static __isl_give isl_ast_expr *add_signed_terms(__isl_take isl_ast_expr *expr, __isl_keep isl_aff *aff, int sign, struct isl_ast_add_term_data *data) { int i, j; isl_val *v; enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div }; enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div }; isl_local_space *ls; ls = isl_aff_get_domain_local_space(aff); for (i = 0; i < 3; ++i) { int n = isl_aff_dim(aff, t[i]); for (j = 0; j < n; ++j) { v = isl_aff_get_coefficient_val(aff, t[i], j); if (sign * isl_val_sgn(v) <= 0) { isl_val_free(v); continue; } v = isl_val_abs(v); expr = isl_ast_expr_add_term(expr, ls, l[i], j, v, data); } } isl_local_space_free(ls); return expr; } /* Should the constant term "v" be considered positive? * * A positive constant will be added to "pos" by the caller, * while a negative constant will be added to "neg". * If either "pos" or "neg" is exactly zero, then we prefer * to add the constant "v" to that side, irrespective of the sign of "v". * This results in slightly shorter expressions and may reduce the risk * of overflows. */ static int constant_is_considered_positive(__isl_keep isl_val *v, __isl_keep isl_ast_expr *pos, __isl_keep isl_ast_expr *neg) { if (ast_expr_is_zero(pos)) return 1; if (ast_expr_is_zero(neg)) return 0; return isl_val_is_pos(v); } /* Check if the equality * * aff = 0 * * represents a stride constraint on the integer division "pos". * * In particular, if the integer division "pos" is equal to * * floor(e/d) * * then check if aff is equal to * * e - d floor(e/d) * * or its opposite. * * If so, the equality is exactly * * e mod d = 0 * * Note that in principle we could also accept * * e - d floor(e'/d) * * where e and e' differ by a constant. */ static int is_stride_constraint(__isl_keep isl_aff *aff, int pos) { isl_aff *div; isl_val *c, *d; int eq; div = isl_aff_get_div(aff, pos); c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos); d = isl_aff_get_denominator_val(div); eq = isl_val_abs_eq(c, d); if (eq >= 0 && eq) { aff = isl_aff_copy(aff); aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0); div = isl_aff_scale_val(div, d); if (isl_val_is_pos(c)) div = isl_aff_neg(div); eq = isl_aff_plain_is_equal(div, aff); isl_aff_free(aff); } else isl_val_free(d); isl_val_free(c); isl_aff_free(div); return eq; } /* Are all coefficients of "aff" (zero or) negative? */ static int all_negative_coefficients(__isl_keep isl_aff *aff) { int i, n; if (!aff) return 0; n = isl_aff_dim(aff, isl_dim_param); for (i = 0; i < n; ++i) if (isl_aff_coefficient_sgn(aff, isl_dim_param, i) > 0) return 0; n = isl_aff_dim(aff, isl_dim_in); for (i = 0; i < n; ++i) if (isl_aff_coefficient_sgn(aff, isl_dim_in, i) > 0) return 0; return 1; } /* Give an equality of the form * * aff = e - d floor(e/d) = 0 * * or * * aff = -e + d floor(e/d) = 0 * * with the integer division "pos" equal to floor(e/d), * construct the AST expression * * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(e), expr(d)), expr(0)) * * If e only has negative coefficients, then construct * * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(-e), expr(d)), expr(0)) * * instead. */ static __isl_give isl_ast_expr *extract_stride_constraint( __isl_take isl_aff *aff, int pos, __isl_keep isl_ast_build *build) { isl_ctx *ctx; isl_val *c; isl_ast_expr *expr, *cst; if (!aff) return NULL; ctx = isl_aff_get_ctx(aff); c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos); aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0); if (all_negative_coefficients(aff)) aff = isl_aff_neg(aff); cst = isl_ast_expr_from_val(isl_val_abs(c)); expr = isl_ast_expr_from_aff(aff, build); expr = isl_ast_expr_alloc_binary(isl_ast_op_zdiv_r, expr, cst); cst = isl_ast_expr_alloc_int_si(ctx, 0); expr = isl_ast_expr_alloc_binary(isl_ast_op_eq, expr, cst); return expr; } /* Construct an isl_ast_expr that evaluates the condition "constraint", * The result is simplified in terms of build->domain. * * We first check if the constraint is an equality of the form * * e - d floor(e/d) = 0 * * i.e., * * e mod d = 0 * * If so, we convert it to * * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(e), expr(d)), expr(0)) * * Otherwise, let the constraint by either "a >= 0" or "a == 0". * We first extract hidden modulo computations from "a" * and then collect all the terms with a positive coefficient in cons_pos * and the terms with a negative coefficient in cons_neg. * * The result is then of the form * * (isl_ast_op_ge, expr(pos), expr(-neg))) * * or * * (isl_ast_op_eq, expr(pos), expr(-neg))) * * However, if the first expression is an integer constant (and the second * is not), then we swap the two expressions. This ensures that we construct, * e.g., "i <= 5" rather than "5 >= i". * * Furthermore, is there are no terms with positive coefficients (or no terms * with negative coefficients), then the constant term is added to "pos" * (or "neg"), ignoring the sign of the constant term. */ static __isl_give isl_ast_expr *isl_ast_expr_from_constraint( __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build) { int i, n; isl_ctx *ctx; isl_ast_expr *expr_pos; isl_ast_expr *expr_neg; isl_ast_expr *expr; isl_aff *aff; int eq; enum isl_ast_op_type type; struct isl_ast_add_term_data data; if (!constraint) return NULL; aff = isl_constraint_get_aff(constraint); eq = isl_constraint_is_equality(constraint); isl_constraint_free(constraint); n = isl_aff_dim(aff, isl_dim_div); if (eq && n > 0) for (i = 0; i < n; ++i) { int is_stride; is_stride = is_stride_constraint(aff, i); if (is_stride < 0) goto error; if (is_stride) return extract_stride_constraint(aff, i, build); } ctx = isl_aff_get_ctx(aff); expr_pos = isl_ast_expr_alloc_int_si(ctx, 0); expr_neg = isl_ast_expr_alloc_int_si(ctx, 0); aff = extract_modulos(aff, &expr_pos, &expr_neg, build); data.build = build; data.cst = isl_aff_get_constant_val(aff); expr_pos = add_signed_terms(expr_pos, aff, 1, &data); data.cst = isl_val_neg(data.cst); expr_neg = add_signed_terms(expr_neg, aff, -1, &data); data.cst = isl_val_neg(data.cst); if (constant_is_considered_positive(data.cst, expr_pos, expr_neg)) { expr_pos = isl_ast_expr_add_int(expr_pos, data.cst); } else { data.cst = isl_val_neg(data.cst); expr_neg = isl_ast_expr_add_int(expr_neg, data.cst); } if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int && isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) { type = eq ? isl_ast_op_eq : isl_ast_op_le; expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos); } else { type = eq ? isl_ast_op_eq : isl_ast_op_ge; expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg); } isl_aff_free(aff); return expr; error: isl_aff_free(aff); return NULL; } /* Wrapper around isl_constraint_cmp_last_non_zero for use * as a callback to isl_constraint_list_sort. * If isl_constraint_cmp_last_non_zero cannot tell the constraints * apart, then use isl_constraint_plain_cmp instead. */ static int cmp_constraint(__isl_keep isl_constraint *a, __isl_keep isl_constraint *b, void *user) { int cmp; cmp = isl_constraint_cmp_last_non_zero(a, b); if (cmp != 0) return cmp; return isl_constraint_plain_cmp(a, b); } /* Construct an isl_ast_expr that evaluates the conditions defining "bset". * The result is simplified in terms of build->domain. * * If "bset" is not bounded by any constraint, then we construct * the expression "1", i.e., "true". * * Otherwise, we sort the constraints, putting constraints that involve * integer divisions after those that do not, and construct an "and" * of the ast expressions of the individual constraints. * * Each constraint is added to the generated constraints of the build * after it has been converted to an AST expression so that it can be used * to simplify the following constraints. This may change the truth value * of subsequent constraints that do not satisfy the earlier constraints, * but this does not affect the outcome of the conjunction as it is * only true if all the conjuncts are true (no matter in what order * they are evaluated). In particular, the constraints that do not * involve integer divisions may serve to simplify some constraints * that do involve integer divisions. */ __isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set( __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset) { int i, n; isl_constraint *c; isl_constraint_list *list; isl_ast_expr *res; isl_set *set; list = isl_basic_set_get_constraint_list(bset); isl_basic_set_free(bset); list = isl_constraint_list_sort(list, &cmp_constraint, NULL); if (!list) return NULL; n = isl_constraint_list_n_constraint(list); if (n == 0) { isl_ctx *ctx = isl_constraint_list_get_ctx(list); isl_constraint_list_free(list); return isl_ast_expr_alloc_int_si(ctx, 1); } build = isl_ast_build_copy(build); c = isl_constraint_list_get_constraint(list, 0); bset = isl_basic_set_from_constraint(isl_constraint_copy(c)); set = isl_set_from_basic_set(bset); res = isl_ast_expr_from_constraint(c, build); build = isl_ast_build_restrict_generated(build, set); for (i = 1; i < n; ++i) { isl_ast_expr *expr; c = isl_constraint_list_get_constraint(list, i); bset = isl_basic_set_from_constraint(isl_constraint_copy(c)); set = isl_set_from_basic_set(bset); expr = isl_ast_expr_from_constraint(c, build); build = isl_ast_build_restrict_generated(build, set); res = isl_ast_expr_and(res, expr); } isl_constraint_list_free(list); isl_ast_build_free(build); return res; } /* Construct an isl_ast_expr that evaluates the conditions defining "set". * The result is simplified in terms of build->domain. * * If "set" is an (obviously) empty set, then return the expression "0". * * If there are multiple disjuncts in the description of the set, * then subsequent disjuncts are simplified in a context where * the previous disjuncts have been removed from build->domain. * In particular, constraints that ensure that there is no overlap * with these previous disjuncts, can be removed. * This is mostly useful for disjuncts that are only defined by * a single constraint (relative to the build domain) as the opposite * of that single constraint can then be removed from the other disjuncts. * In order not to increase the number of disjuncts in the build domain * after subtracting the previous disjuncts of "set", the simple hull * is computed after taking the difference with each of these disjuncts. * This means that constraints that prevent overlap with a union * of multiple previous disjuncts are not removed. * * "set" lives in the internal schedule space. */ __isl_give isl_ast_expr *isl_ast_build_expr_from_set_internal( __isl_keep isl_ast_build *build, __isl_take isl_set *set) { int i, n; isl_basic_set *bset; isl_basic_set_list *list; isl_set *domain; isl_ast_expr *res; list = isl_set_get_basic_set_list(set); isl_set_free(set); if (!list) return NULL; n = isl_basic_set_list_n_basic_set(list); if (n == 0) { isl_ctx *ctx = isl_ast_build_get_ctx(build); isl_basic_set_list_free(list); return isl_ast_expr_from_val(isl_val_zero(ctx)); } domain = isl_ast_build_get_domain(build); bset = isl_basic_set_list_get_basic_set(list, 0); set = isl_set_from_basic_set(isl_basic_set_copy(bset)); res = isl_ast_build_expr_from_basic_set(build, bset); for (i = 1; i < n; ++i) { isl_ast_expr *expr; isl_set *rest; rest = isl_set_subtract(isl_set_copy(domain), set); rest = isl_set_from_basic_set(isl_set_simple_hull(rest)); domain = isl_set_intersect(domain, rest); bset = isl_basic_set_list_get_basic_set(list, i); set = isl_set_from_basic_set(isl_basic_set_copy(bset)); bset = isl_basic_set_gist(bset, isl_set_simple_hull(isl_set_copy(domain))); expr = isl_ast_build_expr_from_basic_set(build, bset); res = isl_ast_expr_or(res, expr); } isl_set_free(domain); isl_set_free(set); isl_basic_set_list_free(list); return res; } /* Construct an isl_ast_expr that evaluates the conditions defining "set". * The result is simplified in terms of build->domain. * * If "set" is an (obviously) empty set, then return the expression "0". * * "set" lives in the external schedule space. * * The internal AST expression generation assumes that there are * no unknown divs, so make sure an explicit representation is available. * Since the set comes from the outside, it may have constraints that * are redundant with respect to the build domain. Remove them first. */ __isl_give isl_ast_expr *isl_ast_build_expr_from_set( __isl_keep isl_ast_build *build, __isl_take isl_set *set) { if (isl_ast_build_need_schedule_map(build)) { isl_multi_aff *ma; ma = isl_ast_build_get_schedule_map_multi_aff(build); set = isl_set_preimage_multi_aff(set, ma); } set = isl_set_compute_divs(set); set = isl_ast_build_compute_gist(build, set); return isl_ast_build_expr_from_set_internal(build, set); } /* State of data about previous pieces in * isl_ast_build_expr_from_pw_aff_internal. * * isl_state_none: no data about previous pieces * isl_state_single: data about a single previous piece * isl_state_min: data represents minimum of several pieces * isl_state_max: data represents maximum of several pieces */ enum isl_from_pw_aff_state { isl_state_none, isl_state_single, isl_state_min, isl_state_max }; /* Internal date structure representing a single piece in the input of * isl_ast_build_expr_from_pw_aff_internal. * * If "state" is isl_state_none, then "set_list" and "aff_list" are not used. * If "state" is isl_state_single, then "set_list" and "aff_list" contain the * single previous subpiece. * If "state" is isl_state_min, then "set_list" and "aff_list" contain * a sequence of several previous subpieces that are equal to the minimum * of the entries in "aff_list" over the union of "set_list" * If "state" is isl_state_max, then "set_list" and "aff_list" contain * a sequence of several previous subpieces that are equal to the maximum * of the entries in "aff_list" over the union of "set_list" * * During the construction of the pieces, "set" is NULL. * After the construction, "set" is set to the union of the elements * in "set_list", at which point "set_list" is set to NULL. */ struct isl_from_pw_aff_piece { enum isl_from_pw_aff_state state; isl_set *set; isl_set_list *set_list; isl_aff_list *aff_list; }; /* Internal data structure for isl_ast_build_expr_from_pw_aff_internal. * * "build" specifies the domain against which the result is simplified. * "dom" is the domain of the entire isl_pw_aff. * * "n" is the number of pieces constructed already. * In particular, during the construction of the pieces, "n" points to * the piece that is being constructed. After the construction of the * pieces, "n" is set to the total number of pieces. * "max" is the total number of allocated entries. * "p" contains the individual pieces. */ struct isl_from_pw_aff_data { isl_ast_build *build; isl_set *dom; int n; int max; struct isl_from_pw_aff_piece *p; }; /* Initialize "data" based on "build" and "pa". */ static isl_stat isl_from_pw_aff_data_init(struct isl_from_pw_aff_data *data, __isl_keep isl_ast_build *build, __isl_keep isl_pw_aff *pa) { int n; isl_ctx *ctx; ctx = isl_pw_aff_get_ctx(pa); n = isl_pw_aff_n_piece(pa); if (n == 0) isl_die(ctx, isl_error_invalid, "cannot handle void expression", return isl_stat_error); data->max = n; data->p = isl_calloc_array(ctx, struct isl_from_pw_aff_piece, n); if (!data->p) return isl_stat_error; data->build = build; data->dom = isl_pw_aff_domain(isl_pw_aff_copy(pa)); data->n = 0; return isl_stat_ok; } /* Free all memory allocated for "data". */ static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data *data) { int i; isl_set_free(data->dom); if (!data->p) return; for (i = 0; i < data->max; ++i) { isl_set_free(data->p[i].set); isl_set_list_free(data->p[i].set_list); isl_aff_list_free(data->p[i].aff_list); } free(data->p); } /* Initialize the current entry of "data" to an unused piece. */ static void set_none(struct isl_from_pw_aff_data *data) { data->p[data->n].state = isl_state_none; data->p[data->n].set_list = NULL; data->p[data->n].aff_list = NULL; } /* Store "set" and "aff" in the current entry of "data" as a single subpiece. */ static void set_single(struct isl_from_pw_aff_data *data, __isl_take isl_set *set, __isl_take isl_aff *aff) { data->p[data->n].state = isl_state_single; data->p[data->n].set_list = isl_set_list_from_set(set); data->p[data->n].aff_list = isl_aff_list_from_aff(aff); } /* Extend the current entry of "data" with "set" and "aff" * as a minimum expression. */ static isl_stat extend_min(struct isl_from_pw_aff_data *data, __isl_take isl_set *set, __isl_take isl_aff *aff) { int n = data->n; data->p[n].state = isl_state_min; data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set); data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff); if (!data->p[n].set_list || !data->p[n].aff_list) return isl_stat_error; return isl_stat_ok; } /* Extend the current entry of "data" with "set" and "aff" * as a maximum expression. */ static isl_stat extend_max(struct isl_from_pw_aff_data *data, __isl_take isl_set *set, __isl_take isl_aff *aff) { int n = data->n; data->p[n].state = isl_state_max; data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set); data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff); if (!data->p[n].set_list || !data->p[n].aff_list) return isl_stat_error; return isl_stat_ok; } /* Extend the domain of the current entry of "data", which is assumed * to contain a single subpiece, with "set". If "replace" is set, * then also replace the affine function by "aff". Otherwise, * simply free "aff". */ static isl_stat extend_domain(struct isl_from_pw_aff_data *data, __isl_take isl_set *set, __isl_take isl_aff *aff, int replace) { int n = data->n; isl_set *set_n; set_n = isl_set_list_get_set(data->p[n].set_list, 0); set_n = isl_set_union(set_n, set); data->p[n].set_list = isl_set_list_set_set(data->p[n].set_list, 0, set_n); if (replace) data->p[n].aff_list = isl_aff_list_set_aff(data->p[n].aff_list, 0, aff); else isl_aff_free(aff); if (!data->p[n].set_list || !data->p[n].aff_list) return isl_stat_error; return isl_stat_ok; } /* Construct an isl_ast_expr from "list" within "build". * If "state" is isl_state_single, then "list" contains a single entry and * an isl_ast_expr is constructed for that entry. * Otherwise a min or max expression is constructed from "list" * depending on "state". */ static __isl_give isl_ast_expr *ast_expr_from_aff_list( __isl_take isl_aff_list *list, enum isl_from_pw_aff_state state, __isl_keep isl_ast_build *build) { int i, n; isl_aff *aff; isl_ast_expr *expr; enum isl_ast_op_type op_type; if (state == isl_state_single) { aff = isl_aff_list_get_aff(list, 0); isl_aff_list_free(list); return isl_ast_expr_from_aff(aff, build); } n = isl_aff_list_n_aff(list); op_type = state == isl_state_min ? isl_ast_op_min : isl_ast_op_max; expr = isl_ast_expr_alloc_op(isl_ast_build_get_ctx(build), op_type, n); if (!expr) goto error; for (i = 0; i < n; ++i) { isl_ast_expr *expr_i; aff = isl_aff_list_get_aff(list, i); expr_i = isl_ast_expr_from_aff(aff, build); if (!expr_i) goto error; expr->u.op.args[i] = expr_i; } isl_aff_list_free(list); return expr; error: isl_aff_list_free(list); isl_ast_expr_free(expr); return NULL; } /* Extend the expression in "next" to take into account * the piece at position "pos" in "data", allowing for a further extension * for the next piece(s). * In particular, "next" is set to a select operation that selects * an isl_ast_expr corresponding to data->aff_list on data->set and * to an expression that will be filled in by later calls. * Return a pointer to this location. * Afterwards, the state of "data" is set to isl_state_none. * * The constraints of data->set are added to the generated * constraints of the build such that they can be exploited to simplify * the AST expression constructed from data->aff_list. */ static isl_ast_expr **add_intermediate_piece(struct isl_from_pw_aff_data *data, int pos, isl_ast_expr **next) { isl_ctx *ctx; isl_ast_build *build; isl_ast_expr *ternary, *arg; isl_set *set, *gist; set = data->p[pos].set; data->p[pos].set = NULL; ctx = isl_ast_build_get_ctx(data->build); ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3); gist = isl_set_gist(isl_set_copy(set), isl_set_copy(data->dom)); arg = isl_ast_build_expr_from_set_internal(data->build, gist); ternary = isl_ast_expr_set_op_arg(ternary, 0, arg); build = isl_ast_build_copy(data->build); build = isl_ast_build_restrict_generated(build, set); arg = ast_expr_from_aff_list(data->p[pos].aff_list, data->p[pos].state, build); data->p[pos].aff_list = NULL; isl_ast_build_free(build); ternary = isl_ast_expr_set_op_arg(ternary, 1, arg); data->p[pos].state = isl_state_none; if (!ternary) return NULL; *next = ternary; return &ternary->u.op.args[2]; } /* Extend the expression in "next" to take into account * the final piece, located at position "pos" in "data". * In particular, "next" is set to evaluate data->aff_list * and the domain is ignored. * Return isl_stat_ok on success and isl_stat_error on failure. * * The constraints of data->set are however added to the generated * constraints of the build such that they can be exploited to simplify * the AST expression constructed from data->aff_list. */ static isl_stat add_last_piece(struct isl_from_pw_aff_data *data, int pos, isl_ast_expr **next) { isl_ast_build *build; if (data->p[pos].state == isl_state_none) isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid, "cannot handle void expression", return isl_stat_error); build = isl_ast_build_copy(data->build); build = isl_ast_build_restrict_generated(build, data->p[pos].set); data->p[pos].set = NULL; *next = ast_expr_from_aff_list(data->p[pos].aff_list, data->p[pos].state, build); data->p[pos].aff_list = NULL; isl_ast_build_free(build); data->p[pos].state = isl_state_none; if (!*next) return isl_stat_error; return isl_stat_ok; } /* Return -1 if the piece "p1" should be sorted before "p2" * and 1 if it should be sorted after "p2". * Return 0 if they do not need to be sorted in a specific order. * * Pieces are sorted according to the number of disjuncts * in their domains. */ static int sort_pieces_cmp(const void *p1, const void *p2, void *arg) { const struct isl_from_pw_aff_piece *piece1 = p1; const struct isl_from_pw_aff_piece *piece2 = p2; int n1, n2; n1 = isl_set_n_basic_set(piece1->set); n2 = isl_set_n_basic_set(piece2->set); return n1 - n2; } /* Construct an isl_ast_expr from the pieces in "data". * Return the result or NULL on failure. * * When this function is called, data->n points to the current piece. * If this is an effective piece, then first increment data->n such * that data->n contains the number of pieces. * The "set_list" fields are subsequently replaced by the corresponding * "set" fields, after which the pieces are sorted according to * the number of disjuncts in these "set" fields. * * Construct intermediate AST expressions for the initial pieces and * finish off with the final pieces. */ static isl_ast_expr *build_pieces(struct isl_from_pw_aff_data *data) { int i; isl_ast_expr *res = NULL; isl_ast_expr **next = &res; if (data->p[data->n].state != isl_state_none) data->n++; if (data->n == 0) isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid, "cannot handle void expression", return NULL); for (i = 0; i < data->n; ++i) { data->p[i].set = isl_set_list_union(data->p[i].set_list); if (data->p[i].state != isl_state_single) data->p[i].set = isl_set_coalesce(data->p[i].set); data->p[i].set_list = NULL; } if (isl_sort(data->p, data->n, sizeof(data->p[0]), &sort_pieces_cmp, NULL) < 0) return isl_ast_expr_free(res); for (i = 0; i + 1 < data->n; ++i) { next = add_intermediate_piece(data, i, next); if (!next) return isl_ast_expr_free(res); } if (add_last_piece(data, data->n - 1, next) < 0) return isl_ast_expr_free(res); return res; } /* Is the domain of the current entry of "data", which is assumed * to contain a single subpiece, a subset of "set"? */ static isl_bool single_is_subset(struct isl_from_pw_aff_data *data, __isl_keep isl_set *set) { isl_bool subset; isl_set *set_n; set_n = isl_set_list_get_set(data->p[data->n].set_list, 0); subset = isl_set_is_subset(set_n, set); isl_set_free(set_n); return subset; } /* Is "aff" a rational expression, i.e., does it have a denominator * different from one? */ static isl_bool aff_is_rational(__isl_keep isl_aff *aff) { isl_bool rational; isl_val *den; den = isl_aff_get_denominator_val(aff); rational = isl_bool_not(isl_val_is_one(den)); isl_val_free(den); return rational; } /* Does "list" consist of a single rational affine expression? */ static isl_bool is_single_rational_aff(__isl_keep isl_aff_list *list) { isl_bool rational; isl_aff *aff; if (isl_aff_list_n_aff(list) != 1) return isl_bool_false; aff = isl_aff_list_get_aff(list, 0); rational = aff_is_rational(aff); isl_aff_free(aff); return rational; } /* Can the list of subpieces in the last piece of "data" be extended with * "set" and "aff" based on "test"? * In particular, is it the case for each entry (set_i, aff_i) that * * test(aff, aff_i) holds on set_i, and * test(aff_i, aff) holds on set? * * "test" returns the set of elements where the tests holds, meaning * that test(aff_i, aff) holds on set if set is a subset of test(aff_i, aff). * * This function is used to detect min/max expressions. * If the ast_build_detect_min_max option is turned off, then * do not even try and perform any detection and return false instead. * * Rational affine expressions are not considered for min/max expressions * since the combined expression will be defined on the union of the domains, * while a rational expression may only yield integer values * on its own definition domain. */ static isl_bool extends(struct isl_from_pw_aff_data *data, __isl_keep isl_set *set, __isl_keep isl_aff *aff, __isl_give isl_basic_set *(*test)(__isl_take isl_aff *aff1, __isl_take isl_aff *aff2)) { int i, n; isl_bool is_rational; isl_ctx *ctx; isl_set *dom; is_rational = aff_is_rational(aff); if (is_rational >= 0 && !is_rational) is_rational = is_single_rational_aff(data->p[data->n].aff_list); if (is_rational < 0 || is_rational) return isl_bool_not(is_rational); ctx = isl_ast_build_get_ctx(data->build); if (!isl_options_get_ast_build_detect_min_max(ctx)) return isl_bool_false; dom = isl_ast_build_get_domain(data->build); set = isl_set_intersect(dom, isl_set_copy(set)); n = isl_set_list_n_set(data->p[data->n].set_list); for (i = 0; i < n ; ++i) { isl_aff *aff_i; isl_set *valid; isl_set *dom, *required; isl_bool is_valid; aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i); valid = isl_set_from_basic_set(test(isl_aff_copy(aff), aff_i)); required = isl_set_list_get_set(data->p[data->n].set_list, i); dom = isl_ast_build_get_domain(data->build); required = isl_set_intersect(dom, required); is_valid = isl_set_is_subset(required, valid); isl_set_free(required); isl_set_free(valid); if (is_valid < 0 || !is_valid) { isl_set_free(set); return is_valid; } aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i); valid = isl_set_from_basic_set(test(aff_i, isl_aff_copy(aff))); is_valid = isl_set_is_subset(set, valid); isl_set_free(valid); if (is_valid < 0 || !is_valid) { isl_set_free(set); return is_valid; } } isl_set_free(set); return isl_bool_true; } /* Can the list of pieces in "data" be extended with "set" and "aff" * to form/preserve a minimum expression? * In particular, is it the case for each entry (set_i, aff_i) that * * aff >= aff_i on set_i, and * aff_i >= aff on set? */ static isl_bool extends_min(struct isl_from_pw_aff_data *data, __isl_keep isl_set *set, __isl_keep isl_aff *aff) { return extends(data, set, aff, &isl_aff_ge_basic_set); } /* Can the list of pieces in "data" be extended with "set" and "aff" * to form/preserve a maximum expression? * In particular, is it the case for each entry (set_i, aff_i) that * * aff <= aff_i on set_i, and * aff_i <= aff on set? */ static isl_bool extends_max(struct isl_from_pw_aff_data *data, __isl_keep isl_set *set, __isl_keep isl_aff *aff) { return extends(data, set, aff, &isl_aff_le_basic_set); } /* This function is called during the construction of an isl_ast_expr * that evaluates an isl_pw_aff. * If the last piece of "data" contains a single subpiece and * if its affine function is equal to "aff" on a part of the domain * that includes either "set" or the domain of that single subpiece, * then extend the domain of that single subpiece with "set". * If it was the original domain of the single subpiece where * the two affine functions are equal, then also replace * the affine function of the single subpiece by "aff". * If the last piece of "data" contains either a single subpiece * or a minimum, then check if this minimum expression can be extended * with (set, aff). * If so, extend the sequence and return. * Perform the same operation for maximum expressions. * If no such extension can be performed, then move to the next piece * in "data" (if the current piece contains any data), and then store * the current subpiece in the current piece of "data" for later handling. */ static isl_stat ast_expr_from_pw_aff(__isl_take isl_set *set, __isl_take isl_aff *aff, void *user) { struct isl_from_pw_aff_data *data = user; isl_bool test; enum isl_from_pw_aff_state state; state = data->p[data->n].state; if (state == isl_state_single) { isl_aff *aff0; isl_set *eq; isl_bool subset1, subset2 = isl_bool_false; aff0 = isl_aff_list_get_aff(data->p[data->n].aff_list, 0); eq = isl_aff_eq_set(isl_aff_copy(aff), aff0); subset1 = isl_set_is_subset(set, eq); if (subset1 >= 0 && !subset1) subset2 = single_is_subset(data, eq); isl_set_free(eq); if (subset1 < 0 || subset2 < 0) goto error; if (subset1) return extend_domain(data, set, aff, 0); if (subset2) return extend_domain(data, set, aff, 1); } if (state == isl_state_single || state == isl_state_min) { test = extends_min(data, set, aff); if (test < 0) goto error; if (test) return extend_min(data, set, aff); } if (state == isl_state_single || state == isl_state_max) { test = extends_max(data, set, aff); if (test < 0) goto error; if (test) return extend_max(data, set, aff); } if (state != isl_state_none) data->n++; set_single(data, set, aff); return isl_stat_ok; error: isl_set_free(set); isl_aff_free(aff); return isl_stat_error; } /* Construct an isl_ast_expr that evaluates "pa". * The result is simplified in terms of build->domain. * * The domain of "pa" lives in the internal schedule space. */ __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal( __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa) { struct isl_from_pw_aff_data data = { NULL }; isl_ast_expr *res = NULL; pa = isl_ast_build_compute_gist_pw_aff(build, pa); pa = isl_pw_aff_coalesce(pa); if (!pa) return NULL; if (isl_from_pw_aff_data_init(&data, build, pa) < 0) goto error; set_none(&data); if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) >= 0) res = build_pieces(&data); isl_pw_aff_free(pa); isl_from_pw_aff_data_clear(&data); return res; error: isl_pw_aff_free(pa); isl_from_pw_aff_data_clear(&data); return NULL; } /* Construct an isl_ast_expr that evaluates "pa". * The result is simplified in terms of build->domain. * * The domain of "pa" lives in the external schedule space. */ __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff( __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa) { isl_ast_expr *expr; if (isl_ast_build_need_schedule_map(build)) { isl_multi_aff *ma; ma = isl_ast_build_get_schedule_map_multi_aff(build); pa = isl_pw_aff_pullback_multi_aff(pa, ma); } expr = isl_ast_build_expr_from_pw_aff_internal(build, pa); return expr; } /* Set the ids of the input dimensions of "mpa" to the iterator ids * of "build". * * The domain of "mpa" is assumed to live in the internal schedule domain. */ static __isl_give isl_multi_pw_aff *set_iterator_names( __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa) { int i, n; n = isl_multi_pw_aff_dim(mpa, isl_dim_in); for (i = 0; i < n; ++i) { isl_id *id; id = isl_ast_build_get_iterator_id(build, i); mpa = isl_multi_pw_aff_set_dim_id(mpa, isl_dim_in, i, id); } return mpa; } /* Construct an isl_ast_expr of type "type" with as first argument "arg0" and * the remaining arguments derived from "mpa". * That is, construct a call or access expression that calls/accesses "arg0" * with arguments/indices specified by "mpa". */ static __isl_give isl_ast_expr *isl_ast_build_with_arguments( __isl_keep isl_ast_build *build, enum isl_ast_op_type type, __isl_take isl_ast_expr *arg0, __isl_take isl_multi_pw_aff *mpa) { int i, n; isl_ctx *ctx; isl_ast_expr *expr; ctx = isl_ast_build_get_ctx(build); n = isl_multi_pw_aff_dim(mpa, isl_dim_out); expr = isl_ast_expr_alloc_op(ctx, type, 1 + n); expr = isl_ast_expr_set_op_arg(expr, 0, arg0); for (i = 0; i < n; ++i) { isl_pw_aff *pa; isl_ast_expr *arg; pa = isl_multi_pw_aff_get_pw_aff(mpa, i); arg = isl_ast_build_expr_from_pw_aff_internal(build, pa); expr = isl_ast_expr_set_op_arg(expr, 1 + i, arg); } isl_multi_pw_aff_free(mpa); return expr; } static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal( __isl_keep isl_ast_build *build, enum isl_ast_op_type type, __isl_take isl_multi_pw_aff *mpa); /* Construct an isl_ast_expr that accesses the member specified by "mpa". * The range of "mpa" is assumed to be wrapped relation. * The domain of this wrapped relation specifies the structure being * accessed, while the range of this wrapped relation spacifies the * member of the structure being accessed. * * The domain of "mpa" is assumed to live in the internal schedule domain. */ static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_member( __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa) { isl_id *id; isl_multi_pw_aff *domain; isl_ast_expr *domain_expr, *expr; enum isl_ast_op_type type = isl_ast_op_access; domain = isl_multi_pw_aff_copy(mpa); domain = isl_multi_pw_aff_range_factor_domain(domain); domain_expr = isl_ast_build_from_multi_pw_aff_internal(build, type, domain); mpa = isl_multi_pw_aff_range_factor_range(mpa); if (!isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out)) isl_die(isl_ast_build_get_ctx(build), isl_error_invalid, "missing field name", goto error); id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out); expr = isl_ast_expr_from_id(id); expr = isl_ast_expr_alloc_binary(isl_ast_op_member, domain_expr, expr); return isl_ast_build_with_arguments(build, type, expr, mpa); error: isl_multi_pw_aff_free(mpa); return NULL; } /* Construct an isl_ast_expr of type "type" that calls or accesses * the element specified by "mpa". * The first argument is obtained from the output tuple name. * The remaining arguments are given by the piecewise affine expressions. * * If the range of "mpa" is a mapped relation, then we assume it * represents an access to a member of a structure. * * The domain of "mpa" is assumed to live in the internal schedule domain. */ static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal( __isl_keep isl_ast_build *build, enum isl_ast_op_type type, __isl_take isl_multi_pw_aff *mpa) { isl_ctx *ctx; isl_id *id; isl_ast_expr *expr; if (!mpa) goto error; if (type == isl_ast_op_access && isl_multi_pw_aff_range_is_wrapping(mpa)) return isl_ast_build_from_multi_pw_aff_member(build, mpa); mpa = set_iterator_names(build, mpa); if (!build || !mpa) goto error; ctx = isl_ast_build_get_ctx(build); if (isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out)) id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out); else id = isl_id_alloc(ctx, "", NULL); expr = isl_ast_expr_from_id(id); return isl_ast_build_with_arguments(build, type, expr, mpa); error: isl_multi_pw_aff_free(mpa); return NULL; } /* Construct an isl_ast_expr of type "type" that calls or accesses * the element specified by "pma". * The first argument is obtained from the output tuple name. * The remaining arguments are given by the piecewise affine expressions. * * The domain of "pma" is assumed to live in the internal schedule domain. */ static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff_internal( __isl_keep isl_ast_build *build, enum isl_ast_op_type type, __isl_take isl_pw_multi_aff *pma) { isl_multi_pw_aff *mpa; mpa = isl_multi_pw_aff_from_pw_multi_aff(pma); return isl_ast_build_from_multi_pw_aff_internal(build, type, mpa); } /* Construct an isl_ast_expr of type "type" that calls or accesses * the element specified by "mpa". * The first argument is obtained from the output tuple name. * The remaining arguments are given by the piecewise affine expressions. * * The domain of "mpa" is assumed to live in the external schedule domain. */ static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff( __isl_keep isl_ast_build *build, enum isl_ast_op_type type, __isl_take isl_multi_pw_aff *mpa) { int is_domain; isl_ast_expr *expr; isl_space *space_build, *space_mpa; space_build = isl_ast_build_get_space(build, 0); space_mpa = isl_multi_pw_aff_get_space(mpa); is_domain = isl_space_tuple_is_equal(space_build, isl_dim_set, space_mpa, isl_dim_in); isl_space_free(space_build); isl_space_free(space_mpa); if (is_domain < 0) goto error; if (!is_domain) isl_die(isl_ast_build_get_ctx(build), isl_error_invalid, "spaces don't match", goto error); if (isl_ast_build_need_schedule_map(build)) { isl_multi_aff *ma; ma = isl_ast_build_get_schedule_map_multi_aff(build); mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma); } expr = isl_ast_build_from_multi_pw_aff_internal(build, type, mpa); return expr; error: isl_multi_pw_aff_free(mpa); return NULL; } /* Construct an isl_ast_expr that calls the domain element specified by "mpa". * The name of the function is obtained from the output tuple name. * The arguments are given by the piecewise affine expressions. * * The domain of "mpa" is assumed to live in the external schedule domain. */ __isl_give isl_ast_expr *isl_ast_build_call_from_multi_pw_aff( __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa) { return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_call, mpa); } /* Construct an isl_ast_expr that accesses the array element specified by "mpa". * The name of the array is obtained from the output tuple name. * The index expressions are given by the piecewise affine expressions. * * The domain of "mpa" is assumed to live in the external schedule domain. */ __isl_give isl_ast_expr *isl_ast_build_access_from_multi_pw_aff( __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa) { return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_access, mpa); } /* Construct an isl_ast_expr of type "type" that calls or accesses * the element specified by "pma". * The first argument is obtained from the output tuple name. * The remaining arguments are given by the piecewise affine expressions. * * The domain of "pma" is assumed to live in the external schedule domain. */ static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff( __isl_keep isl_ast_build *build, enum isl_ast_op_type type, __isl_take isl_pw_multi_aff *pma) { isl_multi_pw_aff *mpa; mpa = isl_multi_pw_aff_from_pw_multi_aff(pma); return isl_ast_build_from_multi_pw_aff(build, type, mpa); } /* Construct an isl_ast_expr that calls the domain element specified by "pma". * The name of the function is obtained from the output tuple name. * The arguments are given by the piecewise affine expressions. * * The domain of "pma" is assumed to live in the external schedule domain. */ __isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff( __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma) { return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_call, pma); } /* Construct an isl_ast_expr that accesses the array element specified by "pma". * The name of the array is obtained from the output tuple name. * The index expressions are given by the piecewise affine expressions. * * The domain of "pma" is assumed to live in the external schedule domain. */ __isl_give isl_ast_expr *isl_ast_build_access_from_pw_multi_aff( __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma) { return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_access, pma); } /* Construct an isl_ast_expr that calls the domain element * specified by "executed". * * "executed" is assumed to be single-valued, with a domain that lives * in the internal schedule space. */ __isl_give isl_ast_node *isl_ast_build_call_from_executed( __isl_keep isl_ast_build *build, __isl_take isl_map *executed) { isl_pw_multi_aff *iteration; isl_ast_expr *expr; iteration = isl_pw_multi_aff_from_map(executed); iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration); iteration = isl_pw_multi_aff_intersect_domain(iteration, isl_ast_build_get_domain(build)); expr = isl_ast_build_from_pw_multi_aff_internal(build, isl_ast_op_call, iteration); return isl_ast_node_alloc_user(expr); }